19. Основные положения теории двойственности

Прямая задача

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

не ограничен в знаке

Теорема 4.1. Пусть – планы соответственно прямой и двойственной ЗЛП, тогда:

(4.12)

Теорема 4.2. Пусть – планы соответственно прямой и двойственной ЗЛП и , тогда – решения соответственно прямой и двойственной задач.

Теорема 4.3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем

. (4.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Теорема 4.4. Планы Соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда

. (4.14)

Условия (4.14) называются условиями дополнительной нежесткости.

Примечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:

. (4.15)

Примечание 2. Если прямая ЗЛП записана не в канонической форме, то условия дополнительной нежесткости для этой ЗЛП и двойственной к ней ЗЛП могут быть записаны в следующем виде:

Если хj* > 0, то ,

Если то yi* = 0, (4.16)

Если yi* > 0, то

Если , то хj* = 0.

Получение оптимального плана двойственной задачи на основании теоремы 4.4.

Пример 4.5. Рассмотрим задачу:

(4.17)

Ее решение . Найдем решение задачи, двойственной к (4.17), используя теорему 4.4. Запишем двойственную к (4.17) задачу:

(4.18)

Применяем соотношение (4.16). Так как х1* = 3/2 > 0, то 3у1* + 4у2* + у3* = 2. Далее, так как 3х1* + х2* = 9/2 + 0 > 3, то у1* = 0, и так как х1* + 2х2* = 3/2 + 0 < 3, то у3* = 0. В итоге имеем:

3у1* + 4у2* + у3* = 2, у1* = у3* = 0,

Т. е. вектор является решением задачи (4.18) на основании теоремы 4.4. Вычислим , что соответствует утверждению теоремы 4.3.

Пример 4.6. Найти решение прямой и двойственной задач.

Прямая задача

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

Max= 5Х1 + 12Х2 + 4Х3

Х1 +2Х2 +Х3 ≤ 10

2Х1 – Х2 + 3Х3 = 8

Х2,3 ≥ 0

Х1 не ограничена в знаке

Min= 10Y1 + 8Y2

Y1 +2Y2 = 5

2Y1 – Y2 ≥ 12

Y1 + 3Y2 ≥ 4

Y1 ≥ 0

У2 не ограничена в знаке

(а)

(б)

(в)

(г)

Двойственная задача содержит две переменные, т. е. ее можно решать графически (рис. 4.1).

Рис. 4.1

Как видно из рис. 4.1, область допустимых решений – планов двойственной ЗЛП – Q представляет собой отрезок АВ, лежащий на прямой Y1 + 2Y2 = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10Y1 + 8Y2 = const в направлении, противоположном вектору = (10; 8), получаем точку А, в которой достигается минимум функции . Находим координаты точки А, которая является пересечением двух прямых:

Y1 + 2 Y2 = 5,

2 Y1 – Y2 = 12,

Откуда

= 29/5; = -2/5 и = 54 .

Ипользуя теорему 4.4, находим решение исходной задачи. Так как > 0 и < 0, то оба ограничения прямой задачи имеют вид строгих равенств:

Х1 + 2Х2 + 3Х3 = 10;

2Х1 – Х2 + 3Х3 = 8. (4.19)

Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства (29/5 – 6/5 = 24/5 > 4), то = 0. Решая систему (4.19), получаем

= 26/5; = 12/5; = 0; f() = 54,8.

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

Пусть прямая задача имеет вид основной ЗЛП:

(4.20)

Двойственная к ней ЗЛП имеет вид:

;

. (4.21)

Предположим, что ЗЛП (4.20) имеет решение. Решения обеих задач могут быть записаны в виде:

= ; = ,

Где = = (, …, )

Матрица, обратная для базисной подматрицы . Матрица подматрицы расположена на месте единичной подматрицы в исходной матрице.

Кроме того, можно показать, что

, , (4.22)

Откуда следует, что i-я компонента решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы () равна разности между левой и правой частями ограничений двойственной ЗЛП: