Контрольная работа: Економіко-математичне програмування
які підставимо в цільову функцію:
F(X) = 3x1 + 2x2 + M(10-2x1 -4x2 +x3 ) + M(11-3x1 -2x2 +x4 ) => min
або
F(X) = (3-5M)x1 +(2-6M)x2 +(1M)x3 +(1M)x4 +(21M) => min
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
| 2 | 4 | -1 | 0 | 0 | 1 | 0 |
| 3 | 2 | 0 | -1 | 0 | 0 | 1 |
| 4 | 7 | 0 | 0 | 1 | 0 | 0 |
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і при тому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x6 , x7 , x5 ,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,0,32,10,11)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| 0 | x6 | 10 | 2 | 4 | -1 | 0 | 0 | 1 | 0 |
| x7 | 11 | 3 | 2 | 0 | -1 | 0 | 0 | 1 | |
| x5 | 32 | 4 | 7 | 0 | 0 | 1 | 0 | 0 | |
|
Індексний рядок | F(X0) | 21M | -3+5M | -2+6M | -1M | -1M | 0 | 0 | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 1 | x6 | 10 | 2 | 4 | -1 | 0 | 0 | 1 | 0 | 2.5 |
| x7 | 11 | 3 | 2 | 0 | -1 | 0 | 0 | 1 | 5.5 | |
| x5 | 32 | 4 | 7 | 0 | 0 | 1 | 0 | 0 | 4.57 | |
|
Індексний рядок | F(X1) | 21M | -3+5M | -2+6M | -1M | -1M | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2 , оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 2 | x2 | 2.5 | 0.5 | 1 | -0.25 | 0 | 0 | 0.25 | 0 | 5 |
| x7 | 6 | 2 | 0 | 0.5 | -1 | 0 | -0.5 | 1 | 3 | |
| x5 | 14.5 | 0.5 | 0 | 1.75 | 0 | 1 | -1.75 | 0 | 29 | |
|
Індексний рядок | F(X2) | 5+6M | -2+2M | 0 | -0.5+0.5M | -1M | 0 | 0.5-1.5M | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1 .
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| 3 | x2 | 1 | 0 | 1 | -0.375 | 0.25 | 0 | 0.375 | -0.25 |
| x1 | 3 | 1 | 0 | 0.25 | -0.5 | 0 | -0.25 | 0.5 | |
| x5 | 13 | 0 | 0 | 1.63 | 0.25 | 1 | -1.63 | -0.25 | |
|
Індексний рядок | F(X3) | 11 | 0 | 0 | 0 | -1 | 0 | -1M | 1-1M |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
Оптимальний план можна записати так:
x2 = 1
x1 = 3
x5 = 13
F(X) = 3*3 + 2*1 = 11
Складемо двоїсту задачу до прямої задачі.