Лінійне програмування має вигляд лінійної математичної моделі, яка складається з трьох частин:
-
- Функції мети для якої знаходимо оптимальне значення
де – апибуток від реалізації однієї i-ї продукції, а – кількість даної продукції. Якщо в (1) змінити знаки коефіццієнтів на протилежні, то функція змінюється на і навпаки.
- Обмеження по запасу ресурсів:
де – нориа витрат i-го ресурсу; – кількість продукції j-го виду, випуск одиниці якої потребує витрат, також слід зазначити, що виличина не повинна бути від’ємною; – запаси i-го ресурсу; i=1,…,m – порядковий номер ресурсу; j=1,…,n – порядковий номер продукції.
- Функції мети для якої знаходимо оптимальне значення
- Вимоги додатності змінних (кількість випущеної продукції не може бути від’ємнм числом). Систему нерівностей (2) або (3) зводять до системи рівностей наступний чином: до системи (2) додаємо додаткові додатні змінні ; від системи (3) віднімаємо додаткові додатні змінні .
У результаті ми повинні розглядати таку систему рівнянь:
- Фуекція мети (1), основним призначенням якої є отримання оптимального розв’язку для області, яка визначається системою обмежень (4).
- Система обмежень:
де .
Розв’язок , при якому функція мети F приймає оптимальне значення називається оптимальним розв’язком. Більшість задач лінійного програмування мають один оптимальний розв’язок. Але бувають випадки, коли система рівнянь є несуміснобю, в такому випадку задача не має оптимального розв’язку.