Симплексний метод лінійного програмування (стр. 2 из 4)
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X)=5x1+3x2 при наступних умовах-обмежень.
8x1-14x2≥14
3x1+2x2≥27
x2≤11
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
8x1-14x2-1x3 + 0x4 + 0x5 = 14
3x1 + 2x2 + 0x3-1x4 + 0x5 = 27
0x1 + 1x2 + 0x3 + 0x4 + 1x5 = 11
Введемо штучні змінні x.
8x1-14x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 14
3x1 + 2x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 27
0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 11
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = 5x1+3x2+Mx6+Mx7 => min
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,0,11,14,27)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | х6 | х7 |
| 0 | х6 | 14 | 8 | -14 | -1 | 0 | 0 | 1 | 0 |
| x7 | 27 | 3 | 2 | 0 | -1 | 0 | 0 | 1 | |
| х5 | 11 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | |
| Індексний рядок | F(X0) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | х7 | min |
| 1 | х6 | 14 | 8 | -14 | -1 | 0 | 0 | 1 | 0 | 1.75 |
| x7 | 27 | 3 | 2 | 0 | -1 | 0 | 0 | 1 | 9 | |
| х5 | 11 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | |
| Індексний рядок | F(X1) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | х7 | min |
| 2 | х1 | 1.75 | 1 | -1.75 | -0.125 | 0 | 0 | 0.125 | 0 | 0 |
| x7 | 21.75 | 0 | 7.25 | 0.375 | -1 | 0 | -0.375 | 1 | 3 | |
| х5 | 11 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 11 | |
| Індексний рядок | F(X2) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | х7 |
| 3 | х1 | 7 | 1 | 0 | -0.0345 | -0.2414 | 0 | 0.0345 | 0.2414 |
| x2 | 3 | 0 | 1 | 0.0517 | -0.1379 | 0 | -0.0517 | 0.1379 | |
| х5 | 8 | 0 | 0 | -0.0517 | 0.1379 | 1 | 0.0517 | -0.1379 | |
| Індексний рядок | F(X3) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оптимальний план можна записати так:
x1 = 7
x2 = 3
x5 = 8
F(X) = 5*7 + 3*3 = 44
Складемо двоїсту задачу до поставленої задачі лінійного програмування.
8y1+3y2≤5
-14y1+2y2+y3≤3
14y1+27y2+11y3 => max
y1 ≥ 0
y2 ≥ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.
Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.
Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.
Тоді Y = C*A-1 =
Запишемо оптимальний план двоїстої задачі:
y1 = 0.02
y2 = 1.62
y3 = 0
Z(Y) = 14*0.02+27*1.62+11*0 = 44
Завдання 3
Розв’язати транспортну задачу.
| 5 | 2 | 3 | 6 | 1 | 200 |
| 1 | 1 | 4 | 4 | 2 | 150 |
| 4 | 3 | 1 | 2 | 1 | 350 |
| 110 | 170 | 200 | 180 | 110 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
У нашому випадку робиться це введенням фіктивного постачальника, оскільки 
. З уведенням фіктивного постачальника в транспортній таблиці додатково заявляється n робочих клітинок.