Контрольная работа: Економіко-математичне програмування
Складаємо симплекс-таблицю:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x3 | 21 | 2 | 3 | 1 | 0 | 0 | 0 | 10.5 |
| x6 | 4 | 1 | 0 | 0 | 0 | 0 | 1 | 4 | |
| x4 | 6 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
| x5 | 10 | 2 | 1 | 0 | 0 | 1 | 0 | 5 | |
| Індексний рядок | F(X1) | -400000 | -100003 | -2 | 0 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1 , оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x3 | 13 | 0 | 3 | 1 | 0 | 0 | -2 | 4.33 |
| x1 | 4 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | |
| x4 | 6 | 0 | 1 | 0 | 1 | 0 | 0 | 6 | |
| x5 | 2 | 0 | 1 | 0 | 0 | 1 | -2 | 2 | |
| Індексний рядок | F(X2) | 12 | 0 | -2 | 0 | 0 | 0 | 100003 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2 .
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | Min |
| 3 | x3 | 7 | 0 | 0 | 1 | 0 | -3 | 4 | 4.33 |
| x1 | 4 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | |
| x4 | 4 | 0 | 0 | 0 | 1 | -1 | 2 | 6 | |
| x2 | 2 | 0 | 1 | 0 | 0 | 1 | -2 | 2 | |
| Індексний рядок | F(X3) | 16 | 0 | 0 | 0 | 0 | 2 | 99999 | 0 |
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1 =4, х2 =2. Прибуток, при випуску продукції за цим планом, становить 16 грн.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Визначимо мінімальне значення цільової функції F(X) = 3x1 +2x2 за таких умов-обмежень.
2x1 +4x2 ≥10
3x1 +2x2 ≥11
4x1 +7x2 ≤32
Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
2x1 + 4x2 -1x3 + 0x4 + 0x5 = 10
3x1 + 2x2 + 0x3 -1x4 + 0x5 = 11
4x1 + 7x2 + 0x3 + 0x4 + 1x5 = 32
Введемо штучні змінні x.
2x1 + 4x2 -1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 10
3x1 + 2x2 + 0x3 -1x4 + 0x5 + 0x6 + 1x7 = 11
4x1 + 7x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 32
Для постановки завдання на мінімум цільову функцію запишемо так:
F(X) = 3x1 +2x2 +Mx6 +Mx7 => min
За використання штучних змінних, що вводяться в цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь висловлюємо штучні змінні:
x6 = 10-2x1 -4x2 +x3