Элементы выпуклого анализа.

Линейная комбинация векторов (*) R=a₁A₁+…+a_nA_n называется выпуклой, если выполняется условие:

a_i=1 и все a_i неотрицательны.

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

Определение: множество называется выпуклым, если вместе с каждой парой своих элементов, оно содержит все их выпуклые комбинации.

выпуклое невыпуклое

множество множество

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

Ограниченный и Неограниченный

многогранники решения.

Определение: угловая точка многогранника решений – это такая точка многогранника, которая не является выпуклой линейной комбинацией никаких других точек многогранника (не лежит на отрезке, соединяющим две другие точки многогранника).

Если система ограничений содержит конечное число неравенств, то число угловых точек будет конечно и не превосходит С _{-числа сочетаний.}

Теорема № 1.

1. Множество решений задачи линейного программирования (если оно не пусто) является выпуклым многогранником.

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

3. Любая точка многогранника решений является линейно - выпуклой комбинацией его угловых точек. Опорное и базисное решение.

Если система линейных уравнений имеет переменных больше, чем уравнений, то она имеет бесконечное множество решений, в каждом из которых некоторые переменные полагают как базисные, а некоторые как свободные, причем базисных ровно столько, сколько уравнений в системе, а свободных n-m, где n – число переменных, а m – число уравнений. Применительно к задачам линейного программирования при переходе к канонической форме всегда имеем систему, в которой число неизвестных больше числа уравнений. При этом столбец B является линейной комбинацией (см. векторное представление задач) векторов A₁+…+A_n и некоторых дополнительных, которые возникают в результате перехода к канонической форме. Следовательно, в качестве базисных переменных можно выбрать только m-переменных, а остальные все переменные в силу их не отрицательности положить равными нулю. Такое решение называется опорным.

Рассмотрим канонический вид задачи ЛП:

Z=C₁X₁+…+C_nX_n max

(*) A₁X₁+…+A_nX_n=B

Xj_0 j= .

B>0

Алгебраическая характеристика угловой точки.

Теорема 2.1.

Если система векторов A₁…A_n канонической формы (*), где вектора A₁…A_n линейно независимы и где m n и все Xj 0 и такова, что A₁X₁+…A_nX_n=B, то точка X=(b₁…b_n ) является угловой точкой многогранника решений. Если точка X=(X₁…X_n) является угловой точкой многогранника решений, то вектора A₁…A_n (m n) в системе уравнений (*) являются линейно независимыми.

Следствие 1: Так как вектора A₁…A_n имеют размерность m , то угловая точка многогранника решений имеет более чем m положительных координат, а в силу не отрицательности переменных остальные координаты равны нулю.

Следствие 2: Для любой угловой точки в разложении (*) имеется не более чем m линейно независимых векторов.

Определение: опорный план называется невырожденным, если он содержит ровно m положительных компонентов и вырожденным, если он содержит положительных компонент строго меньше m.

Заключение:

• опорный план соответствует угловой точки

• число опорных планов конечно

• оптимальный план всегда существует, если множество решений не пусто

• оптимальный план находится среди опорных (их число конечно)

• на этих выводах основан симплексный метод решения задач линейного программирования.