Оптимальний план виробництва (лінійне програмування)

Рішення.
Позначимо через x1. x4 число виготовляються продуктів. Тоді умову задачі може бути записано в наступному вигляді:

Припишемо кожному з видів сировини, що використовуються для виробництва продукції, подвійну оцінку, відповідно рівну y1. y2 і у3. Тоді загальна оцінка сировини, використовуваного на виробництво продукції, складе

Згідно з умовою, двоїсті оцінки повинні бути такими, щоб загальна оцінка сировини, використовуваного на виробництво одиниці продукції кожного виду, була не меншою ціни одиниці продукції даного виду, т. Е. Y1. y2 і у3 повинні задовольняти наступній системі нерівностей:
8y1 + 4y2 + 4y3 ≥ 25
10y1 + 7y2 + 3y3 ≥ 30
8y1 + 4y2 + 3y3 ≥ 40
10y1 + 6y2 + 5y3 ≥ 35
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0

Як видно, ці завдання утворюють симетричну пару двоїстих задач. Рішення прямої задачі дає оптимальний план виробництва виробів, а рішення двоїстої - оптимальну систему оцінок сировини, використовуваного для виробництва цих виробів. Щоб знайти рішення цих задач, слід спочатку знайти рішення якої-небудь однієї з них.

Наведемо математичну модель завдання до канонічного віду.Для цього позбудемося знаків нерівностей за допомогою введення додаткових змінних і заміни знака нерівності на знак рівності. Додаткова змінна додається для кожного нерівності, причому ця змінна вказується в цільової функції з нульовим коефіцієнтом. Правило введення додаткових змінних: при "> =" - змінна вводиться в нерівність з коефіцієнтом (-1); при "<=" - с коэффициентом (+1).

Економічний сенс введених додаткових змінних - залишки відповідних ресурсів кожного виду. Аби вирішити завдання складемо симплекс-таблицю.
Симплекс-таблиця складається так:
У графі "Базис" записуються вектора змінних, прийняті за базові. На першому етапі це - A5. A6. A7. Засадничими будуть змінні, кожна з яких входить тільки в одне рівняння системи, і немає такого рівняння в яке не входила б хоча б одна з базисних змінних.
Наступного стовпець записуються коефіцієнти цільової функції, що відповідають кожній змінної. Стовпець В - стовпець вільних членів. Далі йдуть стовпці коефіцієнтів Аi при i -й змінної.

Під стовпцем вільних членів записується початкова оцінка F0 = Ci Bi = 0 * 3600 + 0 * 1850 + 0 * 1500 = 0.
Решта оцінки записуються під стовпцями відповідних векторів:
F1 - C1 = 0 * 8 + 0 * 4 + 0 * 4 - 25 = -25
F2 - C2 = 0 * 10 + 0 * 7 + 0 * 3 - 30 = -30
F3 - C3 = 0 * 8 + 0 * 4 + 0 * 3 - 40 = -40
F4 - C4 = 0 * 10 + 0 * 6 + 0 * 5 - 35 = -35
Слід зазначити, що оцінки для базисних векторів завжди дорівнюють нулю.

Перетворення симплекс-таблиці ведеться наступним чином:
Крок 1 Перевіряється критерій оптимальності, суть якого полягає в тому, що всі оцінки повинні бути невід'ємні. У нашому випадку цей критерій не виконаний, тому переходимо до другого кроку.

Крок 2. Для негативних оцінок обчислюються величини:

З цих елементів вибирається той, для якого розрахований твір мінімально, в нашому випадку мінімально -18000, тож вибираємо третій стовпець, а в якості так званого дозволяє елемента вибирається перший елемент третього стовпчика (за значенням θ3) - 8 (виділено в таблиці).

Крок 3. Третій рядок таблиці ділиться на 8 і віднімається з інших рядків з коефіцієнтами, що дозволяють ввести в базис третій стовпець. По суті, застосовується метод виключення невідомих, відомий як метод Жордана - Гаусса.