Лінійне програмування – наука про методи дослідження і знаходження екстремальних (найбільших і найменших) значень лінійної функції, на невідомі якої накладаються лінійні обмеження.
Ця лінійна функція називається цільовою, а обмеження які математично записуються у вигляді рівнянь або нерівностей називаються системою обмежень.
Математичне вираження цільової функції та її обмежень називається математичною моделлю економічної задачі або економіко-математичною моделлю.
У загальному вигляді математична модель задачі лінійного програмування можна записати
при обмеженнях
де - невідомі, - задані сталі величини.
Всі або декілька рівнянь системи обмежень можуть бути записані у вигляді нерівностей.
Математична модель у більш скороченому вигляді може бути записана
з обмеженнями
Припустимим розв’язком (планом) задачі лінійного програмування називається вектор , який задовольняє системі обмежень.
Множина припустимих розв’язків утворює область припустимих розв’язків (ОПР).
Припустиме значення, при якому цільова функція досягає свого екстремального значення, називається оптимальним розв’язком задачі лінійного програмування і позначається .
Базисний припустимий розв’язок є опорним розв’язком, де - ранг системи обмежень.