Математическая формулировка и основные особенности задачи линейного программирования.

В наиболее общем виде задача линейного программирования формулируется следующим образом. Найти значения переменных x_i≥0, i = 1,..., n, доставляющих экстремум линейной функции цели

Здесь c^T=[c₁,c₂,...c_n] – транспонированный n-мерный вектор постоянных коэффициентов, x – n-мерный вектор переменных, m – общее число ограничений.

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

Ax{≤ =≥}B,

В сформулированной задаче линейного программирования имеется q ограничений типа неравенств и m - q ограничений типа равенств. Если ограничения типа неравенств отсутствуют, то такая форма записи задачи линейного программирования называется канонической. Общая форма записи ограничений может быть приведена к канонической путем введения дополнительных переменных. Дополнительные неотрицательные переменные вводятся таким образом, чтобы привести ограничения неравенства к виду равенств. В зависимости от знака неравенств будут иметь место следующие выражения:

Таким образом, ограничения приводятся к следующей общей форме:

A₁x = B,

Введение дополнительных переменных не изменяет функции цели и не влияет на оптимальное решение задачи линейного программирования. В дальнейшем ограничимся задачей максимизации функции цели. При этом общность не ограничивается, так как максимизация функции F₁(x) эквивалентна минимизации функции F(x) = -F₁(x).

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

max{c^Tx|A₁x=B,x_i≥i=1,N }

Рассмотрим особенности задач линейного программирования. Система ограничений представляет собой m линейных алгебраических уравнений с N неизвестными переменными. Если N = m и матрица A₁ неособенная (т.е. det A₁≠0) , то существует единственное решение системы и варьировать переменные для обеспечения минимума F(x) оказывается невозможным. Если N < m, то некоторые уравнения являются зависимыми и могут быть исключены, при этом возвращаемся к случаю, когда m = N . Это означает, что задача линейного программирования имеет смысл только при N > m, т.е. когда общее число неизвестных больше числа ограничений. В этом случае из множества решений системы необходимо выбрать такое, которое придает целевой функции максимальное значение.

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

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