Двойственный симплекс-метод

Основан на связи между решениями прямой и двойственной задач.

Рассмотрим задачу ЛП, представленную в канонической форме:

1)

2)

3)

и задачу двойственную к ней

4)

5)

Пусть Y=(y₁, y₂, …, y_m) – опорный план задачи 4), 5).

Базисом опорного плана задачи 4), 5) либо сопряженным базисом, называется произвольная система m линейно независимых векторов условий задачи 1)-3), для которых не более m ограничений 5) выполняются как строгие равенства и найденное решение удовлетворяет всем неравенствам 5).

Свяжем с каждым сопряженным базисом Б_у = m –мерный вектор Х=(х₁, х₂, …, х_m), компоненты которого удовлетворяют условиям 2) исходной задачи.

Вектор Х=(х₁, х₂, …, х_m), компоненты которого равны коэффициентам разложения вектора А₀=(b₁,b₂, …,b_m) по системе Б_у = называется псевдопланом задачи 1)-3).

Признак оптимальности. Если среди базисных компонентов псевдоплана Х=(х₁, х₂, …, х_m) нет отрицательных, т.е. все , то псевдоплан Х-решение задачи 1)-3).

Свяжем с каждым сопряженным базисом Б_у = матрицу (Х_ij) , элементы которой совпадают с коэффициентами разложения векторов условий А_j задачи 1)-3) по системе Б_у.

Пусть среди базисных компонентов псевдоплана Х=(х₁, х₂, …, х_m) имеются отрицательные. Если среди компонентов х_ij<0 найдется хотя бы один, для которого все х_ij>0, то целевая функция задачи 4)-5) не ограничена снизу на множестве ее планов, а прямая задача 1)-3) не разрешима.

Если среди базисных компонентов Х найдется хотя бы один, для которого существует х_ij<0, то псевдоплан можно улучшать.

Для того, чтобы получить базис нового псевдоплана Х^л, нужно вывести из базиса псевдоплана Х вектор А_r(x_rj<0).

Если х_i0<0 при нескольких значениях r, из базиса нужно вывести вектор с minх_r0. Для определения вектора, который нужно ввести в базис, необходимо найти номер k, на котором достигается минимум отношения.

В базис вводится вектор Ак и определяются параметры следующей итерации по формуле:

F=8x₁+6x₂→max 6)

2х₁+5х₂≤11

4х₁+х₂≤10 7)

х₁, х₂≥0 8)

Приведем к каноническому виду

А1	А2	А3	А4	А0
2х1	+ 5х2	+ 1х3	+ 0х4	= 11
4х1	+ х2	+0 х3	+ 1.х4	= 10

Запишем двойственную к ней

F*=11у₁+10у₂→min

2y₁+4y₂≥8 A₁

5y₁+ y₂ ≥6 A₂

y₁ ≥0 A₃

y₂ ≥0 A₄

Возьмем в качестиве сопряженного базиса вектора А₁, А₃ и из системы

2у₁ +4у₂ = 8

у₁ = 0 найдем значение опорного плана двойственной задачи

у₁ =0, у₂ =2

Данный базис не может быть взят в качестве сопряженного, т.к. второе ограничение не выполняется (2≥6).

Возьмем сопряженным базисом А₂, А₃. Из системы

5у₁ + у₂ = 6

у₁ = 0 находим значения у₁ =0, у₂ =6.

Неравенство 2у₁ +4у₂ ≥ 8 при этих значениях у₁ и у₂ выполняется и, следовательно, система { А₂, А₃} является сопряженным базисом.

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

А₀ = А₂х₂₀ +А₃х₃₀

х₂₀= 10; х₃₀= -39

А₁ = А₂х₂₁ +А₃х₃₁

х₂₁= 4; х₃₁ = -18

А₄ = А₂х₂₄ +А₃х₃₄

х₂₄= 1; х₃₄ = -5

А2	6	4/3	0	1	2/9	1/9
А1	8	39/18 (13/6)	1	0		5/18	(-4)
	∆	60	16	0	0	6

Двойственный симплекс-метод целесообразнее использовать при решении ЗЛП, в которой нужно вводить фиктивные переменные.

F=3x1+2x2+5x3→min 2x1-3x2+x3 ≥ 10 4x1+x2+2x3 ≥ 15 xj ≥ 0 (j= )		=-3x1-2x2-5x3→min 2x1-3x2+x3 –x4 = 10 4x1+x2+2x3 –x5= 15
		Двойственная задача F*=10у1+15у2→min 2у1+4у2 ≥-3 А1 -3у1+ у2 ≥-2 А2 у1 +2у2 ≥-5 А3 -у1 ≥ 0 А4 -у2 ≥ 0 А5

{А₄, А₅} – сопряженный базис → у₁=0; у₂=0

Базисные компоненты псевдоплана Х совпадают с соответствующими составляющими вектора ограничений, взятыми с обратным знаком, а элементы х_ij столбцов A_j равны и противоположны по знаку элементам соответствующих столбцов матрицы условия.

Fmin = 15, x₁ = 5; x₂= … = 0