Постановка задачи линейного программирования

Простейшим случаем задачи математического программирования является задача линейного программирования. Она соответствует случаю, когда левые части ограничений (3.1) и целевая функция (3.2) представляют собой линейные функции относительно . Любую задачу математического программирования, отличную от сформулированной выше, называют задачей нелинейного программирования. В задачах нелинейного программирования либо целевая функция, либо левые части ограничений, либо то и другое одновременно являются нелинейными функциями относительно .

Рассмотрим более подробно общую постановку задачи линейного программирования. Пусть дана система т линейных независимых уравнений с неизвестными , называемая в дальнейшем системой ограничений задачи линейного программирования

, (3.3)

где, не уменьшая общности, можно считать .

Характерной особенностью данной задачи является то, что число уравнений меньше числа неизвестных, т.е. . Требуется найти неотрицательные значения переменных , которые удовлетворяют уравнениям (3.3) и обращают в минимум целевую функцию

, (3.4)

называемую линейной формой.

Более компактно в матричной форме задача линейного программирования может быть записана так:

, (3.5)

где - матрица размером ; - мерный вектор; - мерные векторы.

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

Иногда в задаче линейного программирования все или некоторые из уравнений вида (3.3) имеют вид неравенств. Так, вместо уравнения в систему (3.3) может входить неравенство вида:

или

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

,

.

Такое изменение приводит просто к увеличению числа переменных, но не меняет существа задачи.

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

Базисом называют любой набор переменных таких, что определитель, составленный из коэффициентов при этих переменных, не равен нулю. Эти переменных называются базисными. Остальные переменных называются свободными.

Если положить все свободные переменные равными нулю и решить полученную систему уравнений с неизвестным, то получим базисное решение.

Допустимым базисным решением является такое базисное решение, которое одновременно допустимо, т.е. которое дает неотрицательные значения базисных переменных.