Контрольная работа: Економіко-математичне програмування

[-]70

u ₃ = 5 v_j v ₁ =1 v ₂ =4 v ₃ =2 v ₄ =1 v ₅ =2

В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.

Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m+n-1=7. Отже, опорний план є не виродженим.

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0:

u ₁ =0, u ₂ =1, u ₃ =5, v ₁ =1, v ₂ =4, v ₃ =2 v ₄ =1, v ₅ =2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності u_i + v_j ≤ c_ij (для порожніх клітинок таблиці).

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

(2;2): 1 + 4 > 2; ∆₂₂ = 1 + 4 - 2 = 3

(2;4): 1 + 1 > 1; ∆₂₄ = 1 + 1 - 1 = 1

(3;1): 5 + 1 > 3; ∆₃₁ = 5 + 1 - 3 = 3

(3;2): 5 + 4 > 4; ∆₃₂ = 5 + 4 - 4 = 5

(3;3): 5 + 2 > 5; ∆₃₃ = 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
	b 1 = 100	b 2 = 20	b 3 = 70	b 4 =90	b 5 =180
а 1 = 300	1 [-]100	4	2 70	1 90	2 [+] 40	u 1 = 0
а 2 = 90	2	2	3	« 1 2 3 4 5 6 7 8 9 10 » К-во Просмотров: 324 Бесплатно скачать Контрольная работа: Економіко-математичне програмування >>> Скачать <<< Меню Поиск