Контрольная работа: Математичне програмування

Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Для цього у порожню клітинку (1;5) переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд:

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5 [-] 100	2	3	6	1 [+] 50	0	u1 = 0
а2 = 320	1 [+]	1 120	4 100	4 [-] 100	2	0	u2 = 5
а3 = 400	4	1	2	3 [+] 100	5 [-] 250	0 50	u3 = 4
vj	v1 = 5	v2 = -4	v3 = -1	v4 = -1	v5 = 1	v6 = -4

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

(2;1): 5 + 5 > 1; ∆21 = 5 + 5 - 1 = 9

(2;5): 5 + 1 > 2; ∆25 = 5 + 1 - 2 = 4

(2;6): 5 + -4 > 0; ∆26 = 5 + -4 - 0 = 1

(3;1): 4 + 5 > 4; ∆31 = 4 + 5 - 4 = 5