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) — оптимальное решение задачи, двойственной к данной). •
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы