>
Потреби
100
120
100
200
300
50
забезпечен закрітість розв'язуваної задачі, розпочінаємо будуваті математичну модель даної задачі:
В
Економічний Зміст записання обмежень Полягає в тому, что весь Вантаж нужно перевезти по пунктах Повністю.
Аналогічні обмеження можна Записати відносно замовніків: ВАНТАЖ, что может надходіті до споживача від чотірьох баз, має Повністю задовольняті его Попит. Математичность це запісується так:
В
Загальні витрати, пов'язані з транспортування ПРОДУКЦІЇ, візначаються як сума добутків обсягів перевезеної ПРОДУКЦІЇ на вартості транспортування од. ПРОДУКЦІЇ до відповідного замовника и ЗА УМОВИ задачі мают буті мінімальнімі. Тому формально це можна записатися так:
minZ = 5x11 +2 x12 +3 x13 +6 x14 +1 x15 +0 x16 +1 x21 +1 x22 +4 x23 +4 x24 +2 x25 +0 x26 +4 x31 +1 x32 +2 x33 +3 x34 + +5 X35 +0 x36. p> загаль математична модель сформульованої задачі має вигляд:
minZ = 5x11 +2 x12 +3 x13 +6 x14 +1 x15 +0 x16 +1 x21 +1 x22 +4 x23 +4 x24 +2 x25 +0 x26 +4 x31 +1 x32 +2 x33 +3 x34 + +5 X35 +0 x36. p> за умів:
В В
Запішемо умови задачі у вігляді транспортної табліці та складемо ее перший опорний план у Цій табліці методом В«північно-західного кутаВ».
Ai
Bj
ui
b1 = 100
b2 = 120
b3 = 100
b4 = 200
b5 = 300
b6 = 50
а1 = 150
5
100
2
[-] 50
3
6
1
[+]
0
u1 = 0
а2 = 320
1
1
[+] 70
4
100
4
[-] 150
2
0
u2 = -1
а3 = 400
4
1
2
3
[+] 50
5
[-] 300
0
50
u3 = -2
vj
v1 = 5
v2 = 2
v3 = 5
v4 = 5
v5 = 7
v6 = 2
У результаті ОТРИМАНО перший опорний план, Який є допустимим, оскількі ВСІ вантажі з баз вівезені, потреба магазинів задоволена, а план відповідає Системі обмежень транспортної задачі.
Підрахуємо число зайнятості клітін табліці, їх 8, а має буті m + n-1 = 8. Отже, опорний план є НЕ вироджених.
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнятості клітінам табліці, в якіх ui + vi = cij, вважаючі, что u1 = 0:
u1 + V1 = 5; 0 + v1 = 5; v1 = 5
u1 + V2 = 2; 0 + v2 = 2; v2 = 2
u2 + V2 = 1; 2 + u2 = 1; u2 = -1
u2 + V3 = 4; -1 + v3 = 4; v3 = 5
u2 + V4 = 4; -1 + v4 = 4; v4 = 5
u3 + V4 = 3; 5 + u3 = 3; u3 = -2
u3 + V5 = 5; -2 + v5 = 5; v5 = 7
u3 + V6 = 0; -2 + v6 = 0; v6 = 2
Ці Значення потенціалів Першого опорного плану запісуємо у транспортної таблиці.
Потім згідно з алгоритмом методу потенціалів перевіряємо Виконання Другої умови оптімальності ui + vj ≤ cij (для порожніх клітінок табліці).
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
(1, 3): 0 + 5> 3; О”13 = 0 + 5 - 3 = 2
(1, 5): 0 + 7> 1; О”15 = 0 + 7 - 1 = 6
(1, 6): 0 + 2> 0; О”16 = 0 + 2 - 0 = 2
(2; 1): -1 + 5> 1; О”21 = -1 + 5 - 1 = 3
(2, 5): -1 + 7> 2; О”25 = -1 + 7 - 2 = 4
(2, 6): -1 + 2> 0; О”26 = -1 + 2 - 0 = 1
(3, 3): -2 + 5> 2; О”33 = -2 + 5 - 2 = 1
Тому від нього звітність, перейти до іншого плану, змінівші співвідношення заповненості и порожніх клітінок табліці. Вібіраємо Максимально оцінку Вільної Клітини (1, 5): 1. Для цього в перспективну клітку (1; 5) поставімо знак В«+В», а в других вершинах багатокутніка чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в табліці. p> Тепер звітність, перемістіті продукцію в межах побудованого циклу. З вантажів хij что стояти в ...
