Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

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

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

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

 

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

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

Таблиця 5.9

 

Пп Пв В1 В2 В3 В4 Запаси αi
А1 2 15 1 4 5 7 11 6    
А2 5 7 4 18 8 14 9    
А3 3 4 2 11 6 7 12 13    
Потреби         70=70  
βj            

 

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

Покладемо α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

Пп Пв В1 В2 В3 В4 Запаси αi
А1
-
2

5

1 4 0 7
+
6

10

   
А2 5 17 4 18 3 8   9 9    
А3
+
8 7

7 11 6 17
-
12

3

   
Потреби         70=70  
βj            

 

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

Таблиця 5.11

Пп Пв В1 В2 В3 В4 Запаси αi
А1 2 2 1 4 -4 7 6    
А2 5 17 4 18 -1 8   9 9    
А3 4 2 11 6 17 8 12    
Потреби         70=70  
βj     -4      

Після зрушення одержимо опорний план, записаний у таблиці 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 гр. од.

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 897; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.