Алгоритм вирішення транспортної задачі методом потенціалів
1. Відшукуємо вихідний опорний план перевезень (наприклад, методом північно-західного кута). Перехід до пункту 2. 2. Будуємо систему потенціалів. Для цього для кожної базисної 3. Для кожної вільної клітинки (i, j) обчислюємо псевдовартість . Якщо для всіх вільних клітинок , то план є оптимальний, і алгоритм зупиняється. Якщо ж існує вільна клітинка (i, j), для якої , то перехід до пункту 4. 4. Будуємо цикл перерахування, що проходить через клітинку (i, j),
Приклад. Вихідні дані задачі наведені в таблиці 5.9. Методом північно-західного кута знаходимо вихідний опорний план перевезень і записуємо його в ту ж таблицю. Таблиця 5.9
Для визначення потенціалів вирішимо наступну систему:
Покладемо α1=0. Тоді β1=2; α2=3; β2=1; β3=5; α3=1; β4=11. Знайдені потенціали вносимо в таблицю 5.9. Обчислюємо псевдовартості для вільних клітинок і проставляємо їх у ліві верхні кути клітинок. Вибираємо вільну клітку, у якій ; наприклад, виберемо клітинку (1,4). Будуємо цикл перерахування, що проходить через цю клітинку, і зробимо по ньому максимально припустиме зрушення h = 10 (у від’ємних клітинках найменшим перевезенням є х23=10). Після зрушення клітинка (2,3) стає вільною, а клітинка (1,4) - базисною. Одержуємо новий опорний план, записаний у таблиці 5.10.
Таблиця 5.10
Знову будуємо систему потенціалів, розраховуємо псевдовартості, будуємо цикл перерахування, що проходить через клітинку (3,1), робимо по ньому максимально припустиме зрушення величиною h=3. Таблиця 5.11
Після зрушення одержимо опорний план, записаний у таблиці 5.11. Побудувавши систему потенціалів і розрахувавши псевдовартості, бачимо, що для всіх вільних клітинок . Тому опорний план є оптимальний. Отже, оптимальний план має такий вигляд: х11=2; х14=13; х21=17; х22=18; х31=3; х33=17. При цьому fmln = 2• 2 + 13• 6 + 17• 5 + 18• 4 + 3• 4 + 17• 6 =353 гр. од.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|