Алгоритм вирішення транспортної задачі методом потенціалів

1. Відшукуємо вихідний опорний план перевезень (наприклад, методом північно-західного кута). Перехід до пункту 2.

2. Будуємо систему потенціалів. Для цього для кожної базисної
клітинки (p,q) записуємо рівняння α_p+β_q=c_pq. Виходить
система m+n–1 рівнянь із m+n невідомими потенціалами. Один з
потенціалів вважаємо рівним 0 і знаходимо із системи інші
потенціали. Перехід до пункту 3.

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

4. Будуємо цикл перерахування, що проходить через клітинку (i, j),
робимо по ньому максимально припустиме зрушення, одержавши, таким чином, новий опорний план. Перехід до пункту 2.

Приклад. Вихідні дані задачі наведені в таблиці 5.9.

Методом північно-західного кута знаходимо вихідний опорний план перевезень і записуємо його в ту ж таблицю.

Таблиця 5.9

Пп Пв	В₁	В₂	В₃	В₄	Запаси	α_i
А₁	² 15	^{1 4}	^{5 7}	^{11 6}
А₂	⁵ 7	⁴ 18	⁸	^{14 9}
А₃	^{3 4}	^{2 11}	⁶ 7	¹² 13
Потреби					70=70
β_j

Для визначення потенціалів вирішимо наступну систему:

Покладемо α₁=0. Тоді β₁=2; α₂=3; β₂=1; β₃=5; α₃=1; β₄=11. Знайдені потенціали вносимо в таблицю 5.9.

Обчислюємо псевдовартості для вільних клітинок і проставляємо їх у ліві верхні кути клітинок. Вибираємо вільну клітку, у якій ; наприклад, виберемо клітинку (1,4). Будуємо цикл перерахування, що проходить через цю клітинку, і зробимо по ньому максимально припустиме зрушення h = 10 (у від’ємних клітинках найменшим перевезенням є х₂₃=10). Після зрушення клітинка (2,3) стає вільною, а клітинка (1,4) - базисною. Одержуємо новий опорний план, записаний у таблиці 5.10.

Таблиця 5.10

Пп Пв

В₁

В₂

В₃

В₄

Запаси

α_i

А₁

^{1 4}

^{0 7}

⁶

А₂

⁵ 17

⁴ 18

^{3 8}

^{9 9}

А₃

^{8 7}

^{7 11}

⁶ 17

¹²

Потреби

70=70

β_j

Знову будуємо систему потенціалів, розраховуємо псевдовартості, будуємо цикл перерахування, що проходить через клітинку (3,1), робимо по ньому максимально припустиме зрушення величиною h=3.

Таблиця 5.11

Пп Пв	В₁	В₂	В₃	В₄	Запаси	α_i
А₁	² 2	^{1 4}	^{-4 7}	⁶
А₂	⁵ 17	⁴ 18	^{-1 8}	^{9 9}
А₃	⁴	^{2 11}	⁶ 17	^{8 12}
Потреби					70=70
β_j			-4

Після зрушення одержимо опорний план, записаний у таблиці 5.11. Побудувавши систему потенціалів і розрахувавши псевдовартості, бачимо, що для всіх вільних клітинок . Тому опорний план є оптимальний.

Отже, оптимальний план має такий вигляд: х₁₁=2; х₁₄=13; х₂₁=17; х₂₂=18; х₃₁=3; х₃₃=17.

При цьому f_mln = 2• 2 + 13• 6 + 17• 5 + 18• 4 + 3• 4 + 17• 6 =353 гр. од.

⇐ Предыдущая 5 6 7 8 9 101112 13 14 Следующая ⇒