Математичне програмування (стр. 2 из 3)
В якості ведучого виберемо стовпець, відповідної змінної x2, Так як це найбільший коефіцієнт по модулю.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 5 | x1 | 8 | 1 | 0 | 0 | 0.2308 | 0.3077 | 0 |
| x2 | 1 | 0 | 1 | 0 | 0.0769 | -0.2308 | 0 | |
| x3 | 11 | 0 | 0 | 1 | 0.8462 | -0.5385 | -1 | |
| Індексний рядок | F(X5) | 66 | 0 | 0 | 0 | 2 | 2 | 1M |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти.
Оптимальний план можна записати так:
x1 = 8
x2 = 1
x3 = 11
F(X) = 8*8 + 2*1 = 66
Складемо двоїсту задачу до поставленої задачі лінійного програмування.
2y1+3y2+y3≥8
5y1+4y2-3y3≥2
10y1+28y2+5y3 => min
y1 ≤ 0
y2 ≥ 0
y3 ≥ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.
Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1 =
Оптимальний план двоїстої задачі дорівнює:
y1 = 0
y2 = 2
y3 = 2
Z(Y) = 10*0+28*2+5*2 = 66
Завдання 3
Розв’язати транспортну задачу.
| 1 | 4 | 7 | 2 | 3 | 300 |
| 1 | 5 | 3 | 1 | 6 | 90 |
| 2 | 1 | 3 | 1 | 4 | 70 |
| 100 | 20 | 70 | 100 | 180 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
У нашому випадку робиться це введенням фіктивного постачальника, оскільки 
З уведенням фіктивного постачальника в транспортній таблиці додатково заявляється n робочих клітинок.Ціни, додатковим клітинкам, щоб фіктивний рядок був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | Запаси | |
| А1 | 1 | 4 | 7 | 2 | 3 | 300 |
| А2 | 1 | 5 | 3 | 1 | 6 | 90 |
| А3 | 2 | 1 | 3 | 1 | 4 | 70 |
| А4 | 0 | 0 | 0 | 0 | 0 | 10 |
| Потреби | 100 | 20 | 70 | 100 | 180 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=1x11+4x12+7x13+2x14+3x15+1x21+5x22+3x23+1x24+6x25+2x31+1x32+3x33+1x34+ +4x35+0x41+0x42+0x43+0x44+0x45.
Загалом математична модель сформульованої задачі має вигляд:
minZ=1x11+4x12+7x13+2x14+3x15+1x21+5x22+3x23+1x24+6x25+2x31+1x32+3x33+1x34+ +4x35+0x41+0x42+0x43+0x44+0x45.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| Ai | Bj | ui | ||||
| b1 = 100 | b2 = 20 | b3 = 70 | b4=100 | b5=180 | ||
| а1 = 300 | 1100 | 420 | 7[-]70 | 2100 | 3[+]10 | u1 = 0 |
| а2 = 90 | 1 | 5 | 3[+] | 1 | 6[-]90 | u2 = 3 |
| а3 = 70 | 2 | 1 | 3 | 1 | 470 | u3 = 1 |
| а4 = 10 | 0 | 0 | 0 | 0 | 010 | u4 = -3 |
| vj | v1 =1 | v2 =4 | v3 =7 | v4 =2 | v5 =3 | |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1=0, u2=3, u3=1, u4=-3, v1=1, v2=4, v3=7 v4=2, v5=3. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(2;1): 3 + 1 > 1; ∆21 = 3 + 1 - 1 = 3
(2;2): 3 + 4 > 5; ∆22 = 3 + 4 - 5 = 2
(2;3): 3 + 7 > 3; ∆23 = 3 + 7 - 3 = 7
(2;4): 3 + 2 > 1; ∆24 = 3 + 2 - 1 = 4
(3;2): 1 + 4 > 1; ∆32 = 1 + 4 - 1 = 4
(3;3): 1 + 7 > 3; ∆33 = 1 + 7 - 3 = 5
(3;4): 1 + 2 > 1; ∆34 = 1 + 2 - 1 = 2
(4;2): -3 + 4 > 0; ∆42 = -3 + 4 - 0 = 1
(4;3): -3 + 7 > 0; ∆43 = -3 + 7 - 0 = 4
max(3,2,7,4,4,5,2,1,4) = 7
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (2;3): 3. Для цього в перспективну клітку (2;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 3) = 70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
| Ai | Bj | ui | ||||
| b1 = 100 | b2 = 20 | b3 = 70 | b4=100 | b5=180 | ||
| а1 = 300 | 1100 | 420 | 7 | 2[-]100 | 3[+]80 | u1 = 0 |
| а2 = 90 | 1 | 5 | 370 | 1[+] | 6[-]20 | u2 = 3 |
| а3 = 70 | 2 | 1 | 3 | 1 | 470 | u3 = 1 |
| а4 = 10 | 0 | 0 | 0 | 0 | 010 | u4 = -3 |
| vj | v1 =1 | v2 =4 | v3 =0 | v4 =2 | v5 =3 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(2;1): 3 + 1 > 1; ∆21 = 3 + 1 - 1 = 3
(2;2): 3 + 4 > 5; ∆22 = 3 + 4 - 5 = 2
(2;4): 3 + 2 > 1; ∆24 = 3 + 2 - 1 = 4
(3;2): 1 + 4 > 1; ∆32 = 1 + 4 - 1 = 4
(3;4): 1 + 2 > 1; ∆34 = 1 + 2 - 1 = 2
(4;2): -3 + 4 > 0; ∆42 = -3 + 4 - 0 = 1
max(3,2,4,4,2,1) = 4
Вибираємо максимальну оцінку вільної клітини (2;4): 1
Для цього в перспективну клітку (2;4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 5) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
| Ai | Bj | ui | ||||
| b1 = 100 | b2 = 20 | b3 = 70 | b4=100 | b5=180 | ||
| а1 = 300 | 1100 | 4[-]20 | 7 | 280 | 3[+]100 | u1 = 0 |
| а2 = 90 | 1 | 5 | 370 | 120 | 6 | u2 = -1 |
| а3 = 70 | 2 | 1[+] | 3 | 1 | 4[-]70 | u3 = 1 |
| а4 = 10 | 0 | 0 | 0 | 0 | 010 | u4 = -3 |
| vj | v1 =1 | v2 =4 | v3 =4 | v4 =2 | v5 =3 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(3;2): 1 + 4 > 1; ∆32 = 1 + 4 - 1 = 4
(3;3): 1 + 4 > 3; ∆33 = 1 + 4 - 3 = 2
(3;4): 1 + 2 > 1; ∆34 = 1 + 2 - 1 = 2
(4;2): -3 + 4 > 0; ∆42 = -3 + 4 - 0 = 1
(4;3): -3 + 4 > 0; ∆43 = -3 + 4 - 0 = 1
max(4,2,2,1,1) = 4
Вибираємо максимальну оцінку вільної клітини (3;2): 1
Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.