Оптимізація плану виробництва

Рішення симплексним методом online
Загальна постановка задачі планування виробництва: необхідно визначити план виробництва одного або кількох видів продукції, який забезпечує найбільш раціональне використання наявних матеріальних, фінансових та інших видів ресурсів. Такий план повинен бути оптимальним з точки зору обраного критерію - максимуму прибутку, мінімум витрат на виробництво і т.д.
n - кількість продуктів, що випускаються;
m - кількість використовуваних виробничих ресурсів (наприклад, виробничі потужності, сировина, робоча сила);
aij - обсяг витрат i-го ресурсу на випуск одиниці j-ї продукції;
cj - прибуток від випуску і реалізації одиниці j-го продукту;
bi - кількість наявного i-го ресурсу;
xj - обсяг випуску j-го продукту.

Формально задача оптимізації виробничої програми може бути описана за допомогою наступної моделі лінійного програмування:
моделі лінійного програмування

i = 1,.., m
xj ≥ 0, j = 1,…, n
Тут (1) - цільова функція (максимум прибутку);
(2) - система спеціальних обмежень (constraint) на обсяг фактично наявних ресурсів;
(3) - система загальних обмежень (на невід''ємності перемінних);
xj - мінлива (variable).
Задача (1) - (3) називається задачею лінійного програмування в стандартній формі на максимум.
Завдання лінійного програмування в стандартній формі на мінімум має вигляд:

Завдання лінійного програмування


i = 1,.., m
xj ≥ 0, j = 1,…, n
Вектор x = (х1, x2, ..., xn), компоненти х) якого задовольняють обмеженням (2) та (3) (або (5) і (6) у задачі на мінімум), називається допустимим рішенням або допустимим планом задачі лінійного програмування (ЛП).
Сукупність усіх допустимих планів називається безліччю допустимих планів.
Допустиме рішення задачі ЛП, на якому цільова функція (1) (або (3) в задачі на мінімум) досягає максимального (мінімального) значення, називається оптимальним рішенням задачі ЛП.
З кожною завданням ЛП пов'язують інше завдання ЛП, що записується за певними правилами і називається двоїстої завданням ЛП.
Двоїстої до задачі ЛП (1) - (3) є завдання:


i = 1,.., m
xj ≥ 0, j = 1,…, n
Відповідно, двоїстої до задачі ЛП (7) - (9) є задача (1) - (3). Кожній змінної (спеціальне обмеження) вихідної задачі відповідає спеціальне обмеження (змінна) двоїстої задачі. Якщо вихідна задача ЛП має рішення, то має рішення і двоїста до неї завдання, при цьому значення цільових функцій для відповідних оптимальних рішень рівні.
Компонента у*i оптимального рішення двоїстої задачі (7) - (9) називається двоїстої оцінкою (Dual Value) обмеження вихідної задачі ЛП.
Нехай ,
де ХJ - компонента допустимого рішення задачі (1) - (3).
Тоді при виконанні умов невироджених оптимального рішення мають місце наступні співвідношення:

i = 1,.., m
Змінимо значення правій частині bi одного основного обмеження (RHS) вихідної задачі ЛП.
Нехай b'i - мінімальне значення правій частині основного обмеження, при якому рішення у * двоїстої задачі не зміниться. Тоді величину b'i називають нижньою межею (Lower Bound) стійкості по правій частині обмеження.
Нехай b''i - максимальне значення правій частині основного обмеження, при якому рішення у* двоїстої задачі не зміниться. Тоді величину b''i називають верхньою межею (Upper Bound) стійкості по правій частині обмеження.
Змінимо значення одного коефіцієнта cj цільової функції вихідної задачіЛП.
Нехай Су'-мінімальне значення коефіцієнта цільової функції, при якому оптимальне рішення х вихідної задачі не зміниться. Тоді величину Cj називають нижньою межею стійкості за коефіцієнтом цільової функції.
Нехай с"- максимальне значення коефіцієнта цільової функції, при якому оптимальне рішення х* вихідної задачі не зміниться. Тоді величину cj називають верхньою межею стійкості за коефіцієнтом цільової функції.