Контрольная работа: Симплексний метод лінійного програмування
Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x4 , x5 , x6
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,1000,800,150)
Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x4 | 1000 | 0.8 | 0.5 | 0.6 | 1 | 0 | 0 | 1666.67 |
| x5 | 800 | 0.4 | 0.4 | 0.3 | 0 | 1 | 0 | 2666.67 | |
| x6 | 150 | 0 | 0.1 | 0.1 | 0 | 0 | 1 | 1500 | |
| Індексний рядок | F(X1) | 0 | -21 | -23 | -25 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х3 , оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x4 | 100 | 0.8 | -0.1 | 0 | 1 | 0 | -6 | 125 |
| x5 | 350 | 0.4 | 0.1 | 0 | 0 | 1 | -3 | 875 | |
| x3 | 1500 | 0 | 1 | 1 | 0 | 0 | 10 | 0 | |
| Індексний рядок | F(X2) | 37500 | -21 | 2 | 0 | 0 | 0 | 250 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1 .
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 3 | x1 | 125 | 1 | -0.13 | 0 | 1.25 | 0 | -7.5 | 0 |
| x5 | 300 | 0 | 0.15 | 0 | -0.5 | 1 | 0 | 2000 | |
| x3 | 1500 | 0 | 1 | 1 | 0 | 0 | 10 | 1500 | |
| Індексний рядок | F(X3) | 40125 | 0 | -0.63 | 0 | 26.25 | 0 | 92.5 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2 , оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 4 | x1 | 312.5 | 1 | 0 | 0.13 | 1.25 | 0 | -6.25 | 0 |
| x5 | 75 | 0 | 0 | -0.15 | -0.5 | 1 | -1.5 | 2000 | |
| x2 | 1500 | 0 | 1 | 1 | 0 | 0 | 10 | 1500 | |
| Індексний рядок | F(X4) | 41062.5 | 0 | 0 | 0.63 | 26.25 | 0 | 98.75 | 0 |
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1 =312.5, х2 =1500. Прибуток, при випуску продукції за цим планом, становить 41062,5 грн.
Завдання 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