Математичне програмування (стр. 2 из 3)
З рівнянь висловлюємо штучні змінні:
x6 = 3-x1+x2+x5
які підставимо в цільову функцію:
F(X) = 3x1 + x2 - M(3-x1+x2+x5) =>max
або
F(X) = (3+1M)x1+(1-1M)x2+(-1M)x5+(-3M) =>max
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x6,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:
X1 = (0,0,2,12,0,3)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 0 | x3 | 2 | -2 | 6 | 1 | 0 | 0 | 0 |
| x4 | 12 | 4 | -3 | 0 | 1 | 0 | 0 | |
| x6 | 3 | 1 | -1 | 0 | 0 | -1 | 1 | |
| Індексний рядок | F(X0) | -3M | -3-1M | -1+1M | 0 | 0 | 1M | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x3 | 2 | -2 | 6 | 1 | 0 | 0 | 0 | 0 |
| x4 | 12 | 4 | -3 | 0 | 1 | 0 | 0 | 3 | |
| x6 | 3 | 1 | -1 | 0 | 0 | -1 | 1 | 3 | |
| Індексна рядок | F(X1) | -3M | -3-1M | -1+1M | 0 | 0 | 1M | 0 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 2 | x3 | 8 | 0 | 4.5 | 1 | 0.5 | 0 | 0 |
| x1 | 3 | 1 | -0.75 | 0 | 0.25 | 0 | 0 | |
| x6 | 0 | 0 | -0.25 | 0 | -0.25 | -1 | 1 | |
| Індексна рядок | F(X2) | 9 | 0 | -3.25+0.25M | 0 | 0.75+0.25M | 1M | 0 |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти.
Оптимальний план можна записати так:
x3 = 8
x1 = 3
x6 = 0
F(X) = 3*3 = 9
Складемо двоїсту задачу до прямої задачі.
-2y1+4y2+y3≥3
6y1-3y2-y3≥1
2y1+12y2+3y3 =>min
y1 ≥ 0
y2 ≥ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1 =
Оптимальний план двоїстої задачі дорівнює:
y1 = 0
y2 = 0.75
y3 = 0
Z(Y) = 2*0+12*0.75+3*0 = 9
Завдання 3
Розв’язати транспортну задачу.
| 1 | 4 | 7 | 9 | 1 | 250 |
| 2 | 3 | 1 | 2 | 4 | 300 |
| 2 | 1 | 3 | 1 | 4 | 150 |
| 110 | 80 | 100 | 90 | 70 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
У нашому випадку робиться це введенням фіктивного постачальника, оскільки 
. З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | В6 | Запаси | |
| А1 | 1 | 4 | 7 | 9 | 1 | 0 | 250 |
| А2 | 2 | 3 | 1 | 2 | 4 | 0 | 300 |
| А3 | 2 | 1 | 3 | 1 | 4 | 0 | 150 |
| Потреби | 110 | 80 | 100 | 90 | 70 | 250 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.
Загалом математична модель сформульованої задачі має вигляд:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| Ai | Bj | ui | |||||
| b1 = 110 | b2 = 80 | b3 = 100 | b4=90 | b5=70 | b6=250 | ||
| а1 = 250 | 1 110 | 4 80 | 7 [-] 60 | 9 | 1 [+] | 0 | u1 = 0 |
| а2 = 300 | 2 | 3 | 1 [+] 40 | 2 90 | 4 [-] 70 | 0 100 | u2 = -6 |
| а3 = 150 | 2 | 1 | 3 | 1 | 4 | 0 150 | u3 = -6 |
| vj | v1 = 1 | v2 = 4 | v3 = 7 | v4 = 8 | v5 = 10 | v6 = 6 | |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u2 + v3 = 1; 7 + u2 = 1; u2 = -6
u2 + v4 = 2; -6 + v4 = 2; v4 = 8
u2 + v5 = 4; -6 + v5 = 4; v5 = 10
u2 + v6 = 0; -6 + v6 = 0; v6 = 6
u3 + v6 = 0; 6 + u3 = 0; u3 = -6
Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;5): 0 + 10 > 1; ∆15 = 0 + 10 - 1 = 9
(1;6): 0 + 6 > 0; ∆16 = 0 + 6 - 0 = 6
(3;4): -6 + 8 > 1; ∆34 = -6 + 8 - 1 = 1
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (1;5): 1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.