таблиці): А1B4 : u1 + v4 = 0 + 4 = 4 > 1;
А1B5 : u1 + v5 = 0 + 2 = 2 < 5;
А2B1 : u2 + v1 = -3 + 1 = -2 < 1;
А2B2 : u2 + v2 = -3 + 2 = -1 < 2;
А2B4 : u2 + v4 = -3 + 4 = 1 < 3;
А2B5 : u2 + v5 = -3 + 2 = -1 < 1;
А3B1 : u3 + v1 = -1 + 1 = 0 < 2;
А3B2 : u3 + v2 = -1 + 2 = 1 = 1;
А4B1 : u4 + v1 = -2 + 1 = -1 < 0;
А4B2 : u4 + v2 = -2 + 2 = 0 = 0;
А4B3 : u4 + v3 = -2 + 4 = 2 > 0;
А4B4 : u4 + v4 = -2 + 4 = 2 > 0. Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij А1B4 : u1 + v4 = 0 + 4 = 4 > 1;
А4B3 : u4 + v3 = -2 + 4 = 2 > 0;
А4B4 : u4 + v4 = -2 + 4 = 2 > 0. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А1B4): 1
Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B4, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B4 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, , тобто . Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 10 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai | Bj | ui | ||||
b1= 100 | b2= 90 | b3= 200 | b4=30 | b5=80 | ||
а1= 200 | 1100 | 2[-]90 | 4 | 1[+]10 | 5 | u1= 0 |
а2= 120 | 1 | 2 | 1120 | 3 | 1 | u2= 0 |
а3= 150 | 2 | 1[+] | 380 | 3[-]20 | 150 | u3= 2 |
а4= 30 | 0 | 0 | 0 | 0 | 030 | u4= 1 |
vj | v1=1 | v2=2 | v3=1 | v4=1 | V5=-1 |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(А3B1): 2 + 1 = 3 > 2;
(А3B2): 2 + 2 = 4 > 1;
(А4B1): 1 + 1 = 2 > 0;
(А4B2): 1 + 2 = 3 > 0;
(А4B3): 1 + 1 = 2 > 0;
(А4B4): 1 + 1 = 2 > 0.
Вибираємо максимальну оцінку вільної клітини (А3B2): 1
Для цього в перспективну клітку (А3B2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А3B4) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Ai | Bj | ui | ||||
b1= 100 | b2= 90 | b3= 200 | b4=30 | b5=80 | ||
а1= 200 | 1100 | 270 | 4 | 130 | 5 | u1= 0 |
а2= 120 | 1 | 2 | 1120 | 3 | 1 | u2= -3 |
а3= 150 |
Похожие работы
Интересная статья: Быстрое написание курсовой работы