Общая постановка задачи линейной оптимизации

В приведенных выше задачах, а также в ряде других задач, целевая функция линейно зависит от переменных. Если и ограничения на переменные и уравнения связи при этом линейны, то такие задачи составляют предмет линейного программирования.

Задача линейного программирования (ЗЛП) в общем случае может быть сформулирована следующим образом.

Найти значения переменных , доставляющие минимум (максимум) целевой функции:

(4.7)

при условиях

(4.8)

(4.9)

(4.10)

(4.11)

Здесь -заданные весовые коэффициенты целевой функции, положительные, отрицательные, среди которых могут быть также равные нулю; -переменные, которые в ЗЛП в подавляющем большинстве случаях имеют конкретный физический смысл единиц продукции, цены и т. п. и поэтому не могут быть отрицательными. Поэтому условие также входит в систему ограничений. Коэффициенты в ограничениях принимаются действительными числами, положительными или отрицательными, среди которых могут быть равные нулю.

Естественно, что число линейно независимых равенств должно быть меньше числа независимых переменных. Общее же число неравенств может быть произвольным. Если ,т.е. число неизвестных равно числу уравнений (2.8) и система уравнений совместна, то она является определенной и обладает одним единственным решением. В этом случае задача оптимизации теряет смысл. В ЗЛП основной является ситуация, когда и существуют различные решения, среди которых необходимо выбрать оптимальное решение.