Економіко-математичне програмування (стр. 2 из 3)
Оптимальний план можна записати так:
x2 = 1
x1 = 3
x5 = 13
F(X) = 3*3 + 2*1 = 11
Складемо двоїсту задачу до прямої задачі.
2y1+3y2+4y3≤3
4y1+2y2+7y3≤2
10y1+11y2+32y3 => max
y1 ≥ 0
y2 ≥ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1черезалгебраїчнідоповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1розташована в стовпцях додаткових змінних.
Тогда Y = C*A-1 =
Оптимальний план двоїстоїзадачідорівнює:
y1 = 0
y2 = 1
y3 = 0
Z(Y) = 10*0+11*1+32*0 = 11
Завдання 3
Розв’язати транспортну задачу.
| 1 | 4 | 2 | 1 | 2 | 300 |
| 2 | 2 | 3 | 1 | 3 | 90 |
| 3 | 4 | 5 | 6 | 7 | 70 |
| 100 | 20 | 70 | 90 | 180 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Перевіримо необхідність і достатність умоврозв'язання задачі: 
Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | Запаси | |
| А1 | 1 | 4 | 2 | 1 | 2 | 300 |
| А2 | 2 | 2 | 3 | 1 | 3 | 90 |
| А3 | 3 | 4 | 5 | 6 | 7 | 70 |
| Потреби | 100 | 20 | 70 | 90 | 180 |
Розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
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 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1
(3;1): 5 + 1 > 3; ∆31 = 5 + 1 - 3 = 3
(3;3): 5 + 2 > 5; ∆33 = 5 + 2 - 5 = 2
max(1,3,2) = 3
Вибираємо максимальну оцінку вільної клітини (3;1): 3
Для цього в перспективну клітку (3;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 5) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
| Ai | Bj | ui | ||||
| b1 = 100 | b2 = 20 | b3 = 70 | b4=90 | b5=180 | ||
| а1 = 300 | 1[-] 50 | 4 | 270 | 190 | 2[+] 90 | u1 = 0 |
| а2 = 90 | 2 | 2[+] | 3 | 1 | 3[-]90 | u2 = 1 |
| а3 = 70 | 3[+] 50 | 4[-] 20 | 5 | 6 | 7 | u3 = 2 |
| vj | v1 =1 | v2 =2 | v3 =2 | v4 =1 | v5 =2 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;2): 1 + 2 > 2; ∆22 = 1 + 2 - 2 = 1
(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1
max(1,1) = 1
Вибираємомаксимальнуоцінкувільноїклітини (2;2): 2
Для цього в перспективну клітку (2;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах.