Оскільки число невідомих перевищує на одиницю число рівнянь, одне з невідомих можна покласти рівним безпідставного числа, наприклад a 1 = 0, і знайти послідовно з рівнянь (10) значення інших невідомих. Після того як всі потенціали знайдені, для кожної з вільних клітин визначають числа
.
Якщо серед чисел а ij немає негативних, то знайдений опорний план є оптимальним. Якщо ж для деякої вільної клітини а ij > 0, то вихідний опорний план не є оптимальним і необхідно перейти до нового опорного плану. Для цього розглядають всі вільні клітини, для яких a ij > О, і серед даних чисел вибирають максимальне. Клітку, якій це число відповідає, слід заповнити. p align="justify"> Заповнюючи обрану клітку, необхідно змінити обсяги поставок, записаних у ряді інших зайнятих клітин і пов'язаних із заповненою так званим циклом. Циклом в таблиці умов транспортної задачі називається ламана лінія, вершини якої розташовані в зайнятих клітинах таблиці, а ланки-вздовж рядків і стовпців, причому в кожній вершині циклу зустрічається рівно дві ланки, одне з яких знаходиться в рядку, а інше - у стовпці, де лінія здійснює поворот на 90 В° . Приклади деяких циклів показані на рис.1.
1) 2) 3)
Рис.1. Можливі цикли
Якщо ламана лінія, що утворює цикл, перетинається, то точки самопересеченія не є вершинами. p align="justify"> При правильній побудові опорного плану для будь-якої вільної клітини можна побудувати лише один цикл. Після того як для обраної вільної клітини він побудований, слід перейти до нового опорного плану. Для цього необхідно перемістити операції в межах клітин, пов'язаних з даною вільної кліткою. Це переміщення виробляють за такими правилами:
1. Кожній з клітин, пов'язаних циклом з даною вільної кліткою, приписують певний знак, причому вільної клітці - знак плюс, а всім іншим клітинам - по черзі знаки мінус і плюс (називатимемо ці клітини мінусовими і плюсовими);
2. У дану вільну клітину переносять менше з чисел x ij , стоять в мінусових клітинах. Одночасно це число додають до відповідних числах, що стоять в плюсових клітинах, і віднімають з чисел, що стоять в мінусових клітинах. Клітка, яка раніше була вільною, стає зайнятою, а мінусова клітка, в якій стояло мінімальне з чисел x ij вважається вільною.
В результаті зазначених вище переміщень вантажів в ...
