Лінійне програмування. Постановка задачі лінійного програмування

Лінійне програмування має вигляд лінійної математичної моделі, яка складається з трьох частин:

1. 1. Функції мети для якої знаходимо оптимальне значення

      

      де – апибуток від реалізації однієї i-ї продукції, а – кількість даної продукції. Якщо в (1) змінити знаки коефіццієнтів на протилежні, то функція змінюється на і навпаки.

   2. Обмеження по запасу ресурсів:

      

      де – нориа витрат i-го ресурсу; – кількість продукції j-го виду, випуск одиниці якої потребує  витрат, також слід зазначити, що виличина  не повинна бути від’ємною; – запаси i-го ресурсу; i=1,…,m – порядковий номер ресурсу; j=1,…,n – порядковий номер продукції.

1. Вимоги додатності змінних (кількість випущеної продукції не може бути від’ємнм числом). Систему нерівностей (2) або (3) зводять до системи рівностей наступний чином: до системи (2) додаємо додаткові додатні змінні ; від системи (3) віднімаємо додаткові додатні змінні .

У результаті ми повинні розглядати таку систему рівнянь:

1. Фуекція мети (1), основним призначенням якої є отримання оптимального розв’язку для області, яка визначається системою обмежень (4).
2. Система обмежень:

   

   де .

Розв’язок , при якому функція мети F приймає оптимальне значення називається оптимальним розв’язком. Більшість задач лінійного програмування мають один оптимальний розв’язок. Але бувають випадки, коли система рівнянь є несуміснобю, в такому випадку задача не має оптимального розв’язку.