Загальна постановка задачі

Лінійне програмування – наука про методи дослідження і знаходження екстремальних (найбільших і найменших) значень лінійної функції, на невідомі якої накладаються лінійні обмеження.

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

Математичне вираження цільової функції та її обмежень називається математичною моделлю економічної задачі або економіко-математичною моделлю.

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

при обмеженнях

де - невідомі, - задані сталі величини.

Всі або декілька рівнянь системи обмежень можуть бути записані у вигляді нерівностей.

Математична модель у більш скороченому вигляді може бути записана

з обмеженнями

Припустимим розв’язком (планом) задачі лінійного програмування називається вектор , який задовольняє системі обмежень.

Множина припустимих розв’язків утворює область припустимих розв’язків (ОПР).

Припустиме значення, при якому цільова функція досягає свого екстремального значення, називається оптимальним розв’язком задачі лінійного програмування і позначається .

Базисний припустимий розв’язок є опорним розв’язком, де - ранг системи обмежень.