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

 

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

Двойственный симплекс-метод называют методом последовательного улучшения оценок. Смысл его заключается в том, что вместо прямой задачи решают двойственную и затем по оптимальным значениям переменных двойственной задачи определяют оптимальные значения прямой задачи, причем оптимальное базисное решение одной задачи получается приравниванием ее новых базисных переменных коэффициентам при соответствующих небазисных переменных в линейной форме двойственной задачи, взятым со знаком “–”.

Двойственный симплекс-метод целесообразно применять, когда в исходной задаче число ограничений значительно больше числа неизвестных. Если в этом случае перейти к двойственной задаче, то симплекс-процедура будет проще, чем для прямой задачи. Кроме того, двойственный симплекс-метод широко применяется в различных методах рашения задач целочислен­ного программирования.

Часто решение двойственной задачи называют псевдопланом, чтобы отличать его от решения прямой задачи, называемого просто планом.

Проще всего проиллюстрировать двойственный метод на примере.

Пример. Рассмотрим следующую задачу линейного программирования:

–x₁ + 2x₂ – 3x₃ ≤ 1;

(2.14)

2x₁ – x₂ – x₃ ≤ –1;

L = – x₁ – 2x₂ – 3x₃ = max;

x₁ ³ 0, x₂ ³ 0 , x₃ ³ 0.

Составим задачу, двойственную (2.14):

-y₁ + 2y₂ ³ –1;

(2.15)

2y₁ – y₂ ³ –2;

-3y₁ –y₂ ³ –3;

L′ = y₁ – y₂ = min;

y₁ ³ 0, y₂ ³ 0.

Вводя добавочные переменные у₃, у₄, у₅, сведем ограничения в виде неравенств к ограничениям в виде равенств. Тогда задача (2.15) примет вид:

–y₁ + 2y₂ – у₃ = –1;

(2.16)

2y₁ – y₂ – у₄ = –2;

–3y₁ – y₂ – у₅ = –3;

L′ = y₁ – y₂ + 0у₃ + 0у₄ + 0у₅ = min;

y₁ ³ 0, y₂ ³ 0, у₃ ³ 0, у₄ ³ 0, у₅ ³ 0.

Решая задачу (2.16) симплекс-методом, получим симплекс-таблицу 2.4.

Таблица 2.4

 

Базисная переменная	Свободный член и ограничение	Небазисная переменная
y1	y2	y3	y4	y5
y1	1/5				-1/5	1/5
y2	12/5				3/5	2/5
y3	28/5				7/5	3/5
L¢	-11/5				-4/5	-1/5

 

Из последней строки табл. 2.4 получим выражение линейной формы через небазисные переменные

L′ = (4/5)y₄ + (1/5)y₅.

Отсюда, если учесть соответствие между переменными,

y₁ <–> x₄; y₂ <–> x₅;

y₃ <–> x₁; y₄ <–> x₂;

y₅ <–> x₃;

получим решение исходной задачи в виде

x₁ = 0; x₂ = 4/5; x₃ = 1/5;

maxL = –11/5.

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

Симплекс-таблица такого типа называется полной или расширенной в отличие от сокращенной симплекс-таблицы предыдущего примера.