Построение исходного опорного плана

Построение опорных планов, а также преобразование их будем производить непосредственно в распределительной таблице. Если в плане перевозок переменная х_ik равна некоторому числу а ≠ 0, то это число записываем в соот­ветствующую клетку (i; k) и считаем ее занятой или ба­зисной, если же х_ik = 0, то клетку (i; k) оставляем свобод­ной. При этом число занятых опорным планом клеток в соответствии с теоремой 5.2 должно быть равно т+п -1, а остальные тп - (т+п- 1) = (т -1) (п- 1) клеток бу­дут свободными.

Рассмотрим правило «северо-западного угла». Сущ­ность его состоит в следующем. Пользуясь табл. 5.1, будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клет­ки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1; 1) занесем меньшее из чисел a ₁, b ₁, т. е. x ₁₁ = min (a ₁, b ₁). Если a ₁> b ₁, т. е. x ₁₁ = b ₁ и пер­вый потребитель В ₁ будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принима­ется; в нем переменные х_ik =0 для i =2, т.

Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел a ₁- b ₁, и b ₂, т. е. x ₁₂ = min (a ₁- b ₁, b ₂). Если a ₁- b ₁< b ₂, то запасы первого поставщика исчерпаны и первая строка таблицы в дальнейшем в расчет не принимается. Переходим к аналогичному распределению запаса груза второго по­ставщика.

Если a ₁< b ₁, т. е. x ₁₁ = a ₁. При этом запас первого поставщика будет исчерпан, а потому х_ik =0 для k =2, п. Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2; 1) заносим наименьшее из чисел (а ₂, b ₁- а ₁).

Заполнив таким образом клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по вто­рой, третьей и последующим строкам (столбцам) произво­дится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы. Последней заполняется клетка (т; п).

Проиллюстрируем правило «северо-западного угла» на примере.

Пример 5.1. Составить план перевозок зерна из районов А1, А2, А3 и А4, в которых запасы составляют соответственно 800, 700, 1000 и 500 тыс.ц, на три элеватора В1, В2 и В3 мощностью 1000, 1100 и 900 тыс.ц. Затраты на перевозку 1 ц зерна из районов на элеваторы приведены в табл. 5.2.

Таблица 5.2

Районы	Элеваторы	Запас в районе
В1	В2	В3
Затраты на перевозку 1 ц, руб.
А1
А2
А3
А4
Мощность элеватора

Решение. Установим характер задачи. Поскольку

800+700+1000+500=1000 + 1100+900=3000,

заключаем, что данная ТЗ обладает закрытой моделью. В клетку (1; 1) табл. 5.3 помещаем x ₁₁ = min (800, 1000) =800 тыс. ц зерна. Весь запас зерна района А1 отгружен на элеватор В1. Недостающее количество зерна на элеватор В1 поставляется из района А2: в клетку (2; 1) поме­щаем x ₂₁ = min (700, 1000 - 800) =200 тыс. ц. В этом случае мощность элеватора В1 будет полностью использована. Остаток зерна района А2 отправляем на элеватор В2: в клетку (2; 2) помещаем x ₂₂ = min (700 - 200, 1100) =500 тыс. ц зерна. Запас зерна района А2 исчерпан, и пере­ходим к перевозке зерна района А3. В клетку (3; 2) помещаем x ₃₂ = min (1000, 1100 - 500) = 600 тыс. ц зерна. Мощность элеватора В2 полностью использована. Поставку зерна производим на элеватор В3. В клетку (3; 3) помещаем x ₃₃ = min (900, 1000 - 600) =400 тыс. ц зерна. Отгрузка зерна из района А3 полностью произведена. Производим от­грузку зерна из района А4. В клетку (4; 3) помещаем x ₄₃ = min (500, 900 - 400) =500 тыс. ц зерна. В результате полной отгрузки зерна на элеваторы получили план перевозок X ₁ (табл. 5.3).

Таблица 5.3

Районы	Элеваторы	Запас в районе
В1	В2	В3
Затраты на перевозку 1 ц, руб.
А1
А2
А3
А4
Мощность элеватора

Суммарные расходы на перевозку зерна составят:

f (X ₁) = 3*800+7*200+2*500+3*600+3*400+7*500=12 100 руб.

Рассмотрим правило «минимального элемента». Сущ­ность его состоит в следующем. Просматриваются тарифы табл. 5.1 и в первую очередь заполняется клетка с мини­мальным значением тарифа. При этом в клетку записы­вается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую по­ставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся кле­ток таблицы снова выбирают клетку с наименьшим тари­фом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать т+п- 1 загруженных клеток. В процессе заполнения таблицы могут быть одно­временно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовле­творяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 - «нуль-за­грузка», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.

Пример 5.2. Проиллюстрируем правило «минимального элемента» для транспортной задачи, представленной табл. 5.2, и сравним значения целевых функций для планов, получен­ных по правилу «северо-западного угла» и правилу «ми­нимального элемента».

Решение. Просматривая табл. 5.2, замечаем, что минимальные затраты на перевозку зерна соответствуют маршруту А2-В2, поэтому в клетку (2; 2) табл. 5.4 помещаем x ₂₂ = min (700, 1100) =700 тыс. ц зерна. В этом случае вторая строка таблицы в дальнейшем в расчет не принимается, так как запас зерна в районе А2 полностью доставлен на элеватор В2.

Просматриваем оставшиеся клетки таблицы. Наименьшие тарифы имеют клетки (1; 1), (3; 2) – 4. В клетку (1; 1) помещаем x ₁₁ = min (800, 1000) = 800 тыс. ц, а в клетку (3; 2) x ₃₂ = min (1000, 1100 - 700) =400 тыс. ц.

Далее по величине тарифа следует загружать клетки (3; 1), (4; 2),
(2; 3). Однако в результате загрузки клеток (1; 1), (2; 2), (3; 2) запас зерна в районах А1 и А2 и частично в районе А4 исчерпан. Мощность элеватора В2 полностью использована, а мощность элеватора В1 использована на
800 тыс. ц. Поэтому помещаем необходимое количество зерна в клетку (3; 1): x ₃₁ = min (1000 - 400, 1000 - 800) = 200 тыс. ц. После этого мощность элева­тора В1 полностью использована. Остался элеватор В3, который может принять зерно из районов А3 и А4. В районе А3 осталось зерна

1000 – 400 - 200=400 тыс. ц,

а в районе А4 - 500 тыс. ц. В клетки (3; 3); (4; 3) помещаем необходимые количества зерна: x ₃₃=400 тыс. ц, x ₃₄=500 тыс. ц.

Таблица 5.4

Районы	Элеваторы	Запас в районе
В1	В2	В3
Затраты на перевозку 1 ц, руб.
А1
А2
А3
А4
Мощность элеватора

В результате полного распределения зерна получаем план Х ₂, для которого значение целевой функции

f (X ₂) = 3*800+2*700+4*200+3*400+3*400+7*500 =11 300 руб.

Сравнивая значения целевых функций для планов Х ₁ и Х ₂, получен­ных по правилам «северо-западного угла» и «минимального элемента», замечаем, что транспортные расходы по плану Х ₂ на перевозку зерна из районов на элеваторы меньше на 800 руб.

Будет ли этот план оптимальным? Чтобы ответить на этот вопрос, необходимо знать признак оптимальности.

Теорема 5.3. Если план транспортной за­дачи является оптимальным, то ему соответствует система из m+n чисел , удовлетворяющих условиям для и для

Числа называются потенциалами соответствен­но i -го поставщика и j -го потребителя.

Доказательство. Транспортную задачу можно рассматривать как двойственную задачу к некоторой исходной задаче, решаемой на максимум. По­строим эту задачу. Так, если i -му ограничению двойст­венной задачи в исходной задаче соответствует переменная , а j -му ограниче­нию – переменная , то исходной будет задача: найти максимальное значение функции

при ограничениях

,

Оптимальным для двойственной задачи является план х*,а для исходной Y* = (). Для пары взаимодвойст­венных задач на основании первой теоремы двойственно­сти имеет место равенство , а по второй теоре­ме двойственности выполняются условия для и для

Из теоремы следует, что для оптимального плана ТЗ необходимо выполнение условий:

1) каждой занятой клетке в распределительной табли­це соответствует сумма потенциалов, равная тарифу этой клетки, т. е. ;

2) каждой свободной клетке соответствует сумма по­тенциалов, не превышающая тарифа этой клетки, т. е.

Доказанная теорема носит название теоремы о потен­циалах. На ней основан специальный метод решения ТЗ, названный методом потенциалов.