ей і ij і з ij , та І то план потенціалом і, значить, оптимальний. Якщо ж хоча б в одній вільній клітці псевдостоімость більше вартості (як у нашому прикладі), то план не є оптимальним і може бути поліпшений переносом перевезень по циклу, відповідному даної вільної клітині. Ціна цього циклу рівна різниці між вартістю і псевдостоімость в цій вільній клітці. У таблиці № 5 ми отримали в двох клітках і ij і з ij , тепер можна побудувати цикл в будь-який з цих двох клітин. Найвигідніше будувати цикл у тій клітці, в якій різниця і ij - з ij максимальна. У нашому випадку в обох клітинах різниця однакова (дорівнює 1), тому, для побудови циклу виберемо, наприклад, клітину (4,2):
Таблиця № 6
ПН ПОВ 1 В 2 < span align = "justify"> У 3 В 4 В 5 a i А 1 1085 426 690А 2 6 + 47865 - 26-1А 3 87 - 271087 + 01А 4 7 - 145 + 46 680b j 76566
Тепер будемо переміщати по циклу число 14, так як воно є мінімальним з чисел, що стоять в клітинах, позначених знаком - . При переміщенні ми будемо віднімати 14 з клітин зі знаком - і додавати до клітин зі знаком + . Після цього необхідно підрахувати потенціали a i і b j і цикл розрахунків повторюється. Отже, ми приходимо до наступного: алгоритмом вирішення транспортної задачі методом потенціалів.
.2 Алгоритм вирішення транспортної задачі методом потенціалів
. Взяти будь опорний план перевезень, в якому відзначені m + n - 1 базисних клітин (інші клітини вільні). p align="justify">. Визначити для цього плану платежі (a i і b j
