В целевой функции все коэффициенты при переменных отрицательны, значение функции увеличивать нельзя, аналогично преобразовываем остальные переменные, находим опорный план, из которого определяем x₁ ,x₂ .

Теорема 2:

1. Пересечение замкнутых множеств, множество нетривиальных ограничений.

2. Множество решений системы линейных нестрогих неравенств и уравнений является замкнутым.

αX=(αx₁ ,x₂ ,…, αx_n )

X+Y=(x₁ +y₁ , x₂ +y₂ ,… x_n +y_n )

Линейные координаты X₁ ,X₂ ,…X_n называется точка P=λ₁ x₁ + λ₂ x₂ +…+ λ_k x_k

Теорема 3:

Множество P={λ₁ x₁ + λ₂ x₂ +…+ λ_k x_k } 0≤ h_i ≤1 для i= 1,…k_n åR_i =1, 1≤ i ≤k выпуклая линейная комбинация точек x₁ ,x₂ ,…x_n . Если k=2, то это множество называется отрезком. X₁ ,X₂ – концы отрезка. Угловой точкой замкнутого множества называется точка, которая не является нетривиальной линейной комбинацией точек множества (угловая точка).

Нетривиальность означает, что хотя бы одна из λ отлична от 0 или 1.

Теорема 4:

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

Теорема 5:

Если задача линейного программирования имеет единственное решение, то оно лежит среди угловых точек ОДР. А если решение не одно, то среди решений имеется несколько угловых, таких что множество всех решений является их выпуклой линейной комбинацией.

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

Переход к новому опорному плану

F₁ =F(x₁ ); F₂ =F(x₂ ) F₂ -F₁ =-υ_k Δ_k =F₂ можно доказать, где υ_k рассмотренный выше минимум, который определяется при введении k-ой переменной в базис, а Δ_k =åс_j x_j ⁽¹⁾ -С_k , где n ≤ j ≤1, X₁ =(x₁ ⁽¹⁾ ;x₂ ⁽¹⁾ ;…x_n ⁽¹⁾ )- оценка k-ой переменной, поэтому если решается задача на максимум, то величина ΔF₂ положительной должна быть, Δk – отрицательная. При решении задач на минимум ΔF₂ -отрицательная, Δ_k - положительная. Эти величины вычисляются и если среди ΔF₂ все значения не положительны, то при решении задач на минимум наоборот. Если при решении на максимум среди ΔF₂ несколько положительных, то вводим в базис тот вектор, при котором эта величина достигает максимум, а если задача решается на минимум и среди ΔF₂ несколько отрицательных, то в число базисных включается вектор с наименьшим значением ΔF₂ , то есть с наибольшим по абсолютной величине. При выполнении этих условий гарантируется наибольшее возможное изменении значения функции.

Решение задачи будет единственным, если для любых векторов x_k не входящих в базис, оценки Δ_k ≠0, если хотя бы одно из таких Δ_k =0, то решение не является единственным, для нахождения другого решения переходим к другому опорному плану, включая в базис x_k , где Δ_k =0. Перебор все такие опорные решений составляют их в линейную комбинацию, которая и будет решением задачи.

Если для любого некоторого Δ_k противоречащих условию оптимальности коэффициенты при переменной x_k ≤ 0, то система ограничений не ограничена, то есть оптимального плана не существует.

Двойственная задача

Двойственная задача (ДЗ) – это вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при прямой задачи (ПЗ). Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Для перехода к ДЗ необходимо, чтобы ПЗ была записана в стандартной канонической форме. При представлении ПЗ в стандартной форме в состав переменных x_j включаются также избыточные и остаточные переменные.

Двойственная задача имеет:

1. m переменных, соответствующих числу ограничений прямой задачи;

2. n ограничений, соответствующих числу переменных прямой задачи.

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

· Каждому ограничению b_i ПЗ соответствует переменная y_i ДЗ;

· Каждой переменной x_j ПЗ соответствует ограничение C_j ДЗ;

· Коэффициенты при x_j в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;

· Коэффициенты C_j при x_j в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

· Постоянные ограничений b_i ПЗ становятся коэффициентами целевой функции ДЗ.

Рассмотрим следующие две задачи: