Двойственный симплекс-метод и доказательство теоремы двойственности (стр. 3 из 4)

Двойственная задача. Найти матрицу-строку 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,

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

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.

Двойственная задача. Найти максимум линейной функции f = 2y₁+ 3y₂ + 6y₃ + 3y₄при ограничениях

2y₁ - y₂ + y₃ + 2y₄£ 1,

2y₁ + y₂ + y₃ + y₄³ 2,

-y₁+ 4y₂ - 2y₃ - 2y₄³ 3,

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

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

Двойственную задачу решаем симплексным методом (табл. 1.3).

Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), f_max=21/2.

Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A₅, A₆, A₇ : x₁ = 3/2 + 0 = 3/2; x₂ = 9/2 + 0 = 9/2; x₃= 0+ 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Z_min =21/2.

Т а б л и ц а 1.3

i	Базис	С базиса	A0	2				3		6			3		0		0		0
				A1				A2		A3			A4		A5		A6		A7
1 2 3	A5 A3 A7	0 0 0	1 2 3	2 2 -1				-1 1 4		1 1 -2			2 -1 -2		1 0 0		0 1 0		0 0 1
m + 1	Zi - Cj		0	-2				-3		-6			-3		0		0		0
1 2 3	A3 A6 A7	6 0 0	1 1 5	2 0 3				-1 2 6		1 0 0			2 -1 2		1 -1 2		0 1 0		0 0 1
m + 1	Zi - Cj		6		10		-9				0		9		6		0		0
1 2 3	A3 A2 A7	6 3 0	3/2 ½ 2			2 0 3			0 1 0			1 0 0		3/2 -1/2 4		½ -1/2 5		½ ½ 3	0 0 1
m + 1	Zi - Cj		21/2			10			0			0		9/2		3/2		9/2	0

4. Виды математических моделей двойственных задач

На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.

Несимметричные задачи

(1) Исходная задача Двойственная задача

Z_min = CX;f_max = YA₀;

AX = A₀; YA £ С.

X³ 0.

(2) Исходная задача Двойственная задача

Z_max = CX;f_min = YA₀;

AX = A₀; YA ³ С.

X³ 0.

Симметричные задачи

(3) Исходная задача Двойственная задача

Z_min = CX;f_max = YA₀;

AX³A₀; YA £ С.

X³ 0. Y ³ 0.

(4) Исходная задача Двойственная задача

Z_max = CX;f_min = YA₀;

AX£A₀; YA ³ С.

X³ 0. Y ³ 0.

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

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

x₁ – x₂ – x₃£ 4,

x₁ – 5x₂ + x₃³ 5, x_j³ 0 (j = 1, 2, 3).

2x₁ – x₂ + 3x₃³6,

Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель должна иметь вид (3). Переход осуществляется умножением первого неравенства на -1.

Исходная задача:

Z_min = 2x₁ + x₂ + 5x₃при ограничениях

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

x₁ – 5x₂ + x₃³ 5, x_j³ 0 (j = 1, 2, 3).

2x₁ – x₂ + 3x₃³6,

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

f_min = -4x₁ + 5x₂ + 6x₃при ограничениях

-y₁ + y₂ + 2y₃£ 2,

y₁ – 5y₂ - y₃£ 1, y_i³ 0 (i = 1, 2, 3).

2y₁ + y₂ + 3y₃£ 5,

Приведем без доказательства следующую теорему. Теорема 1.1.Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.

Если i-я компонента оптимального плана двойственной задачи положительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

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

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

Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются С_j а оценками плана двойственной задачи – b_i. Решим "двойственную задачу по симплексной таблице, в которой записана исходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит название двойственного симплексного метода,

Пусть необходимо решить исходную задачу линейного программирования, поставленную в общем виде: минимизировать функцию Z =СХ при АХ= A₀, Х³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA₀ при YA £ С. Допустим, что выбран такой базис D = (A₁, А₂, ..., А_i, ..., А_m), при котором хотя бы одна из компонент вектора Х = D^-1A₀ = (x₁, x₂, ..., x_i, ..., x_m) отрицательная (например, x_i < 0), но для всех векторов A_j выполняется соотношение Z_j – C_j£ 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = С_баз D^-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными.