Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности

y₃ £ 0.

Решение исходной задачи находим симплексным методом (табл. 1.2).

i	Базис	С базиса	A0	0	1	0	-1	-3	0
				A1	A2	A3	A4	A5	A6
1 2 3	A1 A3 A6	0 0 0	1 2 5	1 0 0	2 -4 3	0 1 0	-1 2 0	1 -1 1	0 0 1
m + 1	Zi - Cj		0	0	-1	0	1	3	0
1 2 3	A5 A3 A6	-3 0 0	1 3 4	1 1 -1	2 -2 1	0 1 0	-1 1 1	1 0 0	0 0 1
m + 1	Zi - Cj		-3	-3	-7	0	4	0	0
1 2 3	A5 A4 A6	-3 -1 0	4 3 1	2 1 -2	0 -2 3	1 1 -1	0 1 0	1 0 0	0 0 1
m + 1	Zi - Cj		-15	-7	1	-4	0	0	0
1 2 3	A5 A4 A2	-3 -1 1	4 11/3 1/3	3 -1/3 -2/3	0 0 1	1 1/3 -1/3	0 1 0	1 0 0	0 2/3 1/3
m + 1	Zi - Cj		-46/3	-19/3	0	-11/3	0	0	-1/3

Оптимальный план исходной задачи X* =(0; 1/3; 0; 11/3; 4; 0), при котором Z_min = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственнойзадачи. Согласно теореме двойственности оптимальный план двойствен­ной задачи находится из соотношения Y* = C*D ^-1 , где матрица D ^-1 - матрица, обратная матрице, составленной из компонент векторов, вхо­дящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A₅ , A₄ , A₂ ; значит,

1 -1 2

D = ( A₅ , A₄ , A₂ ) = -1 2 -4

1 0 3

Обратная матрица D ^-1 образована из коэффициентов, стоящих в столбцах A₁ , A₃ , A₆ четвертой итерации:

2 1 0

D^-1 = -1/3 1/3 2/3

-2/3 -1/3 1/3

Из этой же итерации следует С* = (— 3; —1; 1). Таким образом

2 1 0

Y = С* D^-1 = (-3; -1; 1) · -1/3 1/3 2/3

-2/3 -1/3 1/3

Y*=(-19/3; -11/3; -1/3),

т. е. y _i = С*Х _i , где Х _i — коэффициенты разложения последней ите­рации, стоящие в столбцах векторов первоначального единичного базиса.

Итак, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней приба­вить соответствующее значение коэффициента линейной функции:

у ₁ = — 19/3 + 0 = — 19/3; y₂ = -11/3 + 0 = -11/3; у ₃ = -1/3+0 = -1/3. При этом плане max f = -46/3.

3. Симметричные двойственные задачи

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

Исходная задача. Найти матрицу-столбец Х = (x₁ , x₂ , …, x_n ), которая удовлетворяет системе ограничений

(1.12). АХ >А₀ , Х >0

и минимизирует линейнуюфункцию Z = СХ.

Двойственная задача. Найти матрицу-строку Y = (y₁ , y₂ , …, y_n ), которая удовлетворяет системе ограничений YA £C , Y ³0 и максимизирует линейную функцию f = YA ₀ .

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

Используя симметричность, можно выбрать задачу, более удоб­ную для решения. Объем задачи, решаемой с помощью ЭВМ, ограни­чен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формули­ровке. При вычислениях без помощи машин использование двойствен­ности упрощает вычисления.

Исходная задача. Найти минимальное значение линейной функции Z = x₁ + 2x₂ + 3x₃ при ограничениях

2x₁ + 2x₂ - x₃ ³ 2,

x₁ - x₂ - 4x₃ £ -3, x_i ³ 0 (i=1,2,3)

x₁ + x₂ - 2x₃ ³ 6,