Методи лінійного програмування

9.1. Основна задача лінійного програмування (ОЗЛП)

У надто широкому класі технічних задач показник якості виражається лінійно через параметри керування, а умови, яким повинні задовольняти параметри, що шукаються у вигляді лінійних рівностей, чи нерівностей.

Обчислення максимуму чи мінімуму лінійного показника якості за умови, що змінні, які підлягають визначенню, задовольняють лінійним обмеженням, складає предмет лінійного програмування.

ОЗЛП формулюється наступним чином:

Потрібно знайти значення невід’ємних змінних , які задовольняли б систему m лінійних рівнянь.

(1)

та при зазначених умовах обертали б в мінімум чи максимум лінійну функцію

(2)

Областю допустимих рішень (ОДР) ОЗЛП називається сукупність невід’ємних змінних , які задовольняють систему обмежень (1).

ОЗЛП не обов’язково повинна мати рішення: обмежуючі рівняння можуть суперечити один одному; мати рішення, але не в області невід’ємних значень; лінійна функція може бути не обмежена знизу.

Система обмежень може бути задана у вигляді нерівностей:

(3)

Щоб перейти до ОЗЛП необхідно ввести додаткові змінні в кожне рівняння, щоб вони перетворювали дані нерівності у рівності:

(4)

Наступним етапом буде вираження додаткових базисних змінних через основні (вільні) змінні та .

(5)

Задача полягає в тому, щоб знайти невід’ємні значення (n+m) змінних , щоб вони задовольняли систему m рівнянь і обертали в мінімум чи максимум лінійну цільову функцію ЦФ виду (2).

Для рішення подібного роду задач розроблений симплекс метод.