Исходный опорный план

Первым шагом при решении транспортной задачи является получение допустимого решения, которое называют исходный опорный план. Исходный план можно легко получить, используя простой алгоритм, разработанный Данцигом и названный Чарнсом и Купером “правилом северо-западного угла”, хотя исходный план, полученный этим способом, как правило, весьма далек от оптимального.

“Правило северо-западного угла” формулируется следующим образом:

1. Начать с северо-западного угла исходной таблицы – клетки (1,1), куда дать максимально возможную поставку:

х ₁₁ =miníА₁,В₁ý.

2. Следующую максимально возможную поставку дать либо в клетку (1,2), либо в клетку (2,1), в зависимости от результата первого шага.

3. Продолжить этот процесс шаг за шагом от северо-западного до юго-восточного угла таблицы.

Таким образом, в нашем примере (см. табл. 2.3.3) процесс определения исходного плана происходит следующим образом:

В клетку (1,1) даем максимально возможную поставку:

х ₁₁ =miní50,40ý=40.

После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы выпадает из последующего рассмотрения. Переходим к клетке (1,2) и даем в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 40 единиц своей продукции и у него осталось только 50 – 40 = 10 единиц, получим х ₁₂ =miní10,85ý=10. После этого объемы 1-го производителя полностью реализованы и из рассмотрения выпадает первая строка таблицы. В оставшейся таблице снова находим «северо-западный угол» и т.д. В результате получаем исходное распределение поставок (см. табл. 2.3.3).

Число заполненных клеток в полученном распределении оказалось равным m+n–1=3+3–1 = 5. Это не случайно. Действительно, на каждом шаге (кроме последнего) из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец и строка.

Поэтому число заполненных клеток на единицу меньше, чем сумма числа строк и столбцов, т.е. равно m+n–1. Справедлива теорема (которую мы примем без доказательств) утверждающая, что в оптимальном решении число заполненных клеток (т.е. основных, так называемых базисных переменных) должно быть равно m+n–1.

Существенный недостаток метода “северо-западного угла” состоит в том, что он построен без учета значений транспортных издержек. Можно модифицировать данный метод, избавившись от этого недостатка: на каждом шаге максимально возможную поставку следует давать не в “северо-западную” клетку оставшейся таблицы, а в клетку с наименьшим значением транспортных издержек. При этом распределение поставок оказывается, вообще говоря, ближе к оптимуму, чем распределение, полученное методом “северо-западного угла”. Такой метод получения исходного плана называется методом наименьших затрат. Исходный план, полученный данным методом, приведен в табл. 2.3.4.

Дата добавления: 2015-04-24