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

[-]70

0

100

u 2 = -6 а 3 = 150

2

1

3

1

4

0

150

u 3 = -6 vj v 1 =1 v 2 =4 v 3 =7 v 4 =8 v 5 =10 v 6 =6

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

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

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

u 1=0, u 2=-6, u 3=-6, v 1=1, v 2=4, v 3=7 v 4=8, v 5=10, v 6=6. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

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

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

(1;5): 0 + 10 > 1

(1;6): 0 + 6 > 0

(3;4): -6 + 8 > 1

Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А 1B 5): 1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

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

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

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

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

Ai	Bj						ui
b 1 = 110	b 2 = 80	b 3 = 100	b 4=90	b 5=70	b 6=250
а 1 = 250	1 110	4 [-]80	7	« 1 2 3 4 5 6 7 8 9 10 » К-во Просмотров: 362 Бесплатно скачать Контрольная работа: Методика економіко-математичного програмування >>> Скачать <<< Меню Поиск