межах кліток, пов'язаних циклом з даною вільної кліткою, визначають новий опорний план транспортної задачі.
Описаний вище перехід від одного опорного плану задачі до іншому її опорному плану називається зрушенням по циклу перерахунку.
При зсуві по циклу перерахунку число зайнятих клітин залишається незмінним, а саме залишається рівним п + m - 1. При цьому якщо в мінусових клітинах є два (або більше) однакових числа x ij , то звільняють лише одну з таких клітин, а решту залишають зайнятими.
Отриманий новий опорний план завдання перевіряють на оптимальність. Для цього визначають потенціали пунктів відправлення та призначення і знаходять числа для всіх вільних клітин. Якщо серед цих чисел не опиниться негативних, то це свідчить про отримання оптимального плану. Якщо ж такі числа є, то слід перейти до нового опорного плану. В результаті ітераційного процесу після кінцевого числа кроків отримують оптимальний план задачі. p> З викладеного вище випливає, що процес знаходження рішення транспортної задачі методом потенціалів включає наступні етапи:
Знаходять опорний план. При цьому число заповнених клітин має бути рівним п + m - 1.
Знаходять потенціали b j і а i відповідно пунктів призначення і відправлення.
Для кожної вільної клітини визначають число а ij . Якщо серед чисел а ij < span align = "justify"> немає позитивних, то отриманий оптимальний план транспортної задачі, якщо ж вони є, то переходять до нового опорного плану.
Серед позитивних чисел а ij вибирають максимальне, будують для вільної клітини, якої воно відповідає, цикл перерахунку і виробляють зрушення по циклу перерахунку.
Отриманий опорний план перевіряють на оптимальність, тобто знову повторять всі дії починаючи з етапу 2.
При визначенні опорного плану або в процесі виконання завдання може бути отриманий вироджений опорний план. Щоб уникнути в цьому випадку зациклення, слід відповідні нульові елементи опорного плану замінити як завгодно малим позитивним числом ? і вирішувати завдання як невироджених. В оптим...
