9.10. теоремы двойственности в линейном программировании

9.10. теоремы двойственности в линейном программировании

Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности. Для взаимно двойственных задач (9.25)—(9.28) и (9.29)—(9.32) имеет место один из четырех взаимоисключающих случаев:

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

В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.

В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи пустое допустимое множество.

Обе задачи (прямая и двойственная) имеют пустые допустимые множества.

Вторая теорема двойственности. Пусть сс° = (х°, х\%,х?,x°) —

допустимое решение прямой задачи (9.25)—(9.28), а Р° = (у®, у\%, у9, yfy — допустимое решение двойственной задачи (9.29)— (9.32). Для того чтобы а0 и Р° были оптимальными решениями соответственно задач (9.25)—(9.28) и (9.29)—(9.32), необходимо и достаточно, чтобы выполнялись следующие соотношения:

( т

Х°

= 0, / = 1,2,..., и, (9.33)

i=l J

Л

= 0, / = 1,2,..., т. (9.34)

Условия (9.33), (9.34) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи. Поэтому для решения некоторой задачи линейного программирования можно вначале решить двойственную ей задачу, а затем определить оптимальное решение исходной задачи.

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

240

На основании второй теоремы двойственности можно сформулировать критерий оптимальности для допустимого решения задачи линейного программирования.

Критерий оптимальности. Пусть а0 = (х,, х2, ...,х^, х°п) — допустимое решение задачи (9.25)—(9.28). Вектор а0 является оптимальным решением этой задачи тогда и только тогда, когда среди решений системы уравнений

т

2>^,-уу. = 0 прих°*0, (9.35)

г=1

у,=0 приХаЛ0<й,. (9.36)

У=1

содержится хотя бы одно допустимое решение задачи (9.29)—(9.32), двойственной к задаче (9.25)—(9.28).

О Пример. Вектор а = (3; 0; 1; 3) является допустимым решением задачи

/= -2ху х2 + х3 + х4(тах),

Х-^ Х^ Н~ 2^С^ ^4 =

Зх2 7х3 + Зх4 = 2,

х^ И2-Х^ = 2Э

Xj>0, j= 1,2, 3,4.

В данном случае соотношения вида (9.36) отсутствуют, а из условий (9.35) имеем

У = -2,

' 2уу 1у2 + 2^з = 1,

ГУ + ЪУ2 = L Отсюда ух -2, у2 -1/3, у3 4/3. Нетрудно проверить, что Р (-2; -1/3; 4/3) — решение системы ограничений двойственной задачи

' У! > -2,

-Уі + 3j>2 + Уз> -1> 2-Уі ~ 7у2 + 2Уз ^ -^+3у2 >1.

241

Следовательно, а = (3; 0; 1; 3) — оптимальное решение нашей задачи (из второй теоремы двойственности сразу следует, что Р = (-2; -1/3; 4/3) — оптимальное решение задачи, двойственной к данной). •