Для всіх , та , то він є оптимальним планом транспортної задачі.

Потенціали опорного плану визначаються із системи рівнянь , які записують для всіх заповнених клітинок транспортної таблиці.

4. За допомогою розрахованих потенціалів перевіряють умову оптимальності для порожніх клітинок таблиці. Якщо хоча б для однієї клітинки ця умова нєвиконується, тобто , поточний план є неоптимальним і від нього необхідно перейти до нового опорного плану.

Перехід від одного опорного плану до іншого виконують заповненням клітинки, для якої порушено умову оптимальності. Якщо таких клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто . Для вибраної порожньої клітинки будують цикл перерахування та виконують перерозподіл продукції в межах цього циклу за такими правилами:

1) кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим по черзі — знаки «-» та «+»;

2) у порожню клітинку переносять менше з чисел х_ij, що стоять у клітинках зі знаком «-». Одночасно це число додають до відповідних чисел, які розміщуються в клітинках зі знаком «+».

Отже, клітинка, що була вільною, стає заповненою, а відповідна клітинка з мінімальним числом вважається порожньою. У результаті такого перерозподілу продукції дістанемо новий опорний план транспортної задачі.

5. Новий опорний план перевіряють на оптимальність згідно з п. 3 розглянутого алгоритму.

Розглянемо застосування методу потенціалів для розв'язування транспортних задач, наведених далі.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Методи побудови опорного плану. Впровадження. Двоїстість.	\|	ТЗ за критерієм часу. Двостапна ТЗ. Розв’язання по сітці.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.