замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=1x11+4x12+2x13+1x14+2x15+2x21+2x22+3x23+1x24+3x25+3x31+4x32+5x33+6x34+ +7x35.
Загалом математична модель сформульованої задачі має вигляд:
minZ=1x11+4x12+2x13+1x14+2x15+2x21+2x22+3x23+1x24+3x25+3x31+4x32+5x33+6x34+ +7x35.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai | Bj | ui | ||||
b1 = 100 | b2 = 20 | b3 = 70 | b4=90 | b5=180 | ||
а1 = 300 | 1100 | 4[-]20 | 270 | 190 | 2[+]20 | u1 = 0 |
а2 = 90 | 2 | 2 | 3 | 1 | 390 | u2 = 1 |
а3 = 70 | 3 | 4[+] | 5 | 6 | 7[-]70 | u3 = 5 |
vj | v1 =1 | v2 =4 | v3 =2 | v4 =1 | v5 =2 |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m+n-1=7. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1=0, u2=1, u3=5, v1=1, v2=4, v3=2 v4=1, v5=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;2): 1 + 4 > 2; ∆22 = 1 + 4 - 2 = 3
(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1
(3;1): 5 + 1 > 3; ∆31 = 5 + 1 - 3 = 3
(3;2): 5 + 4 > 4; ∆32 = 5 + 4 - 4 = 5
(3;3): 5 + 2 > 5; ∆33 = 5 + 2 - 5 = 2
max(3,1,3,5,2) = 5
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;2): 4. Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai | Bj | ui | ||||
b1 = 100 | b2 = 20 | b3 = 70 | b4=90 | b5=180 | ||
а1 = 300 | 1[-]100 | 4 | 270 | 190 | 2[+] 40 | u1 = 0 |
а2 = 90 | 2 | 2 | 3 | 1 | 390 | u2 = 1 |
а3 = 70 | 3[+] | 420 | 5 | 6 | 7[-] 50 | u3 = 5 |
vj | v1 =1 | v2 =-1 | v3 =2 | v4 =1 | v5 =2 |
Похожие работы
Интересная статья: Быстрое написание курсовой работы