Контрольная работа: Оптимізація економічних показників
4x1+x2≤12
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
8x1 + 6x2 + 1x3 + 0x4 + 0x5 + 0x6 = 48
1x1-2x2 + 0x3-1x4 + 0x5 + 1x6 = -5
4x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 = 12
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = -1 x1 +2 x2 +M x6 =>min
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 0 | x3 | 33 | 11 | 0 | 1 | -3 | 0 | 3 | 0 |
| x2 | 2.5 | -0.5 | 1 | 0 | 0.5 | 0 | -0.5 | 0 | |
| x5 | 9.5 | 4.5 | 0 | 0 | -0.5 | 1 | 0.5 | 0 | |
| Індексний рядок | F(X) | 5 | 0 | 0 | 0 | 1 | 0 | -100001 | 0 |
У базисному стовпчику всі елементи позитивні.
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x3 | 33 | 11 | 0 | 1 | -3 | 0 | 3 | 0 |
| x2 | 2.5 | -0.5 | 1 | 0 | 0.5 | 0 | -0.5 | 5 | |
| x5 | 9.5 | 4.5 | 0 | 0 | -0.5 | 1 | 0.5 | 0 | |
| Індекснийрядок | F(X1) | 5 | 0 | 0 | 0 | 1 | 0 | -100001 | 0 |
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти. Враховуючи вказане будуємо новий план здійснивши відповідні розрахунки. У якості ведучого виберемо стовпець, відповідної змінної x4, так як найбільший коефіцієнт за модулем.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x3 | 48 | 8 | 6 | 1 | 0 | 0 | 0 | 6 |
| x4 | 5 | -1 | 2 | 0 | 1 | 0 | -1 | 0 | |
| x5 | 12 | 4 | 1 | 0 | 0 | 1 | 0 | 3 | |
| Індекснийрядок | F(X2) | 0 | 1 | -2 | 0 | 0 | 0 | -100000 | 0 |
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти. Враховуючи вказане будуємо новий план здійснивши відповідні розрахунки. У якості ведучого виберемо стовпець, відповідної змінної x1, так як найбільший коефіцієнт за модулем.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 3 | x3 | 24 | 0 | 4 | 1 | 0 | -2 | 0 | 6 |
| x4 | 8 | 0 | 2.25 | 0 | 1 | 0.25 | -1 | 0 | |
| x1 | 3 | 1 | 0.25 | 0 | 0 | 0.25 | 0 | 3 | |
| Індекснийрядок | F(X3) | -3 | 0 | -2.25 | 0 | 0 | -0.25 | -100000 | 0 |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
Оптимальний план можна записати так:
x3 = 24
x4 = 8
x1 = 3
F(X) = -1*3 = -3
Визначаємо оптимальний план двоїстої задачі до поставленої задачі лінійного програмування.
F(Y) = -48Y1-5Y2+12Y3 (max)
Обмеження:
-8Y1+1Y2+4Y3≤-1
-6Y1-2Y2+1Y3≤2
Y1≥0
Y2≥0
Y3≥0
лінійний програмування транспортна задача
Оскільки, у правій частині присутні від’ємні значення, перемножимо відповідні строки на (-1).
Визначимо максимальне значення цільової функції