logo
Общая постановка задачи о принятии решения

Геометрическая интерпретация двойственных задач

Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.

Пример 3. Для задачи, состоящей в определении максимального значения функции при условиях

составить двойственную задачу и найти решение обеих задач.

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

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

Как видно из рис. 8, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х*=(2, 6) является оптимальным планом, при котором . Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y*=(1; 4) является оптимальным планом двойственной задачи, при котором Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.

Из рис. 7 видно, что при всяком плане исходной задачи значение целевой функции не больше 46. Одновременно, как видно из рис. 8, значение целевой функции двойственной задачи при любом ее плане не меньше 46. Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при ее произвольном плане.

Пример 4.

Найти решение двойственной пары задач.

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

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

Решение. Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8). Из рис. 7 видно, что исходная задача не имеет оптимального плана из-за неограниченности снизу ее целевой функции на множестве допустимых решений.

Из рис. 10 следует, что двойственная задача не имеет планов, поскольку многоугольник решений ее пуст. Это означает, что если исходная задача двойственной пары не имеет оптимального плана из-за неограниченности на множестве допустимых решений ее целевой функции, то двойственная задача также не имеет планов.

Нахождение решения двойственных задач. Рассмотрим пару двойственных задач – основную задачу линейного программирования (43) – (45) и двойственную к ней задачу (46), (47).

Предположим, что с помощью симплексного метода найден оптимальный план X* задачи (43) – (45) и этот план определяется базисом, образованным векторами .

Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции (43) задачи (43) – (45), а через матрицу, обратную матрице Р, составленной из компонент векторов базиса. Тогда имеет место следующее утверждение.

Теорема 10. Если основная задача линейного программирования имеет оптимальный план X*, то является оптимальным планом двойственной задачи.

Таким образом, если найти симплексным методом оптимальный план задачи (43) – (45), то, используя последнюю симплекс–таблицу, можно определить и и с помощью соотношения найти оптимальный план двойственной задачи (46), (47).

В том случае, когда среди векторов , составленных из коэффициентов при неизвестных в системе уравнений (44), имеется т единичных, указанную матрицу образуют числа первых т строк последней симплекс–таблицы, стоящие в столбцах данных векторов. Тогда нет необходимости определять оптимальный план двойственной задачи умножением на , поскольку компоненты этого плана совпадают с соответствующими элементами (m+1)–й строки столбцов единичных векторов, если данный коэффициент , и равны сумме соответствующего элемента этой строки и если

Сказанное выше имеет место и для симметричной пары двойственных задач. При этом так как система ограничений исходной задачи содержит неравенства вида “ ”, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m+1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным.

Пример 15. Для задачи, состоящей в определении максимального значения функции при условиях

составить двойственную задачу и найти ее решение.

Решение. Двойственная задача по отношению к исходной состоит в нахождении минимума функции при условиях

Чтобы найти решение двойственной задачи, сначала находим решение исходной задачи методом искусственного базиса. Оно приведено в таблице 12. Из последней симплекс-таблицы видно, что двойственная задача имеет решение

Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное совпадает с максимальным значением целевой функции исходной задачи.

Таблица 12

i

Базис

Сб

Р0

1

2

–1

0

0

М

 

 

 

P1

P2

P3

p4

p5

Р6

1

2

3

4

5

1

2

3

4

1

2

3

4

p4

P5

p6

 

p4

P5

p1

 

p2

P5

p1

0

0

М

 

0

0

1

2

0

1

12

17

4

0

–4

14

15

2

2

4

9

4

12

–1

1

2

–1

–2

0

0

1

0

0

0

1

0

4

1

–1

–2

1

7/2

3/2

–1/2

–5/2

1

0

0

0

–2

2

2

1

–2

–1

1

1

2

–2/7

13/7

6/7

9/7

1

0

0

0

0

1

0

0

0

2/7

–3/7

1/7

5/7

0

1

0

0

0

0

1

0

0

0

1

0

0

0

0

1

0

0

1/2

–1/2

1/2

1/2

1/7

–5/7

4/7

6/7