Двойственность в задачах линейного программирования

Теория двойственности представляет собой весьма важное, как с чисто теоретической, так и с практической точки зрения, направление математического программирования. Основной идеей теории двойственности является то, что для каждой задачи линейного программирования (ЛП) существует некоторая задача ЛП, решение которой тесно связано с решением прямой. Между решениями прямой и двойственной задач имеется ряд важных соотношений, полезных при исследовании общих свойств оптимального решения задач ЛП и проверке оптимальности допустимого решения.
Рассмотрим задачу: найти min f(x), x Є Rn (1)
при ограничениях gj( x)≤ 0, j = 1, m; m<n.                 
Эту задачу называют прямой. Существует связанная с ней задача максимизации, называемая  двойственной:
L(x,λ) = max
, (2)
где L(x,λ) – функция Лагранжа.
Понятие двойственности устанавливает определенные отношения между решениями прямой и двойственной задач.
Определение. Две экстремальные задачи называются эквивалентными, если множества их решения совпадают, либо обе задачи не имеют решений.

Двойственность

Теория двойственности представляет собой фундаментальное понятие в математическом программировании, имеющее теоретическое и практическое значение.
Основная идея теории двойственности: для каждой задачи ЛП существует некоторая задача ЛП, решение которой тесно связано с прямой. Между решениями прямой и двойственной задач имеется ряд важных соотношений, полезных при исследовании общих свойств оптимального решения ЗЛП и проверке оптимальности допустимого решения.
Двойственная задача к ЗЛП в стандартной форме: рассмотрим ЗЛП (в стандартной форме)
min Z = C*X,
A*X = B,
X ≥ 0
 (П) Прямая задача.
Каждому i–му (i = 1,m) ограничению поставим в соответствие переменное ui, положительное, отрицательное или нуль (называемое двойственным переменным), и рассмотрим ЗЛП.
max W = U*B
U* AT ≤ C, AT*U ≤ C
(Д) Двойственная задача
где U есть, так называемый, вектор–строка (u1, u2, …, um).
Линейная задача (Д) тесно связана с линейной задачей (П):
- матрица ограничений (Д) есть транспонированная матрица задачи (П);
- вектор "цен"  для задачи (П) есть вектор правых частей ограничений задачи (Д) и наоборот.
Данная таблица соответствий между прямой и двойственной задачами позволяет  записать непосредственно двойственную задачу для любой линейной задачи.
Таблица

Прямая

Двойственная

Целевая функция (min)

Правая часть ограничений

Правая часть ограничений

Целевая функция (max)

A – матрица ограничений

AT – матрица ограничений

i–ое ограничение: ≥ 0, (≤0)

Переменная ui ≥ 0, (≤0)

i–ое ограничение: = 0

Переменная ui ≠ 0

Переменная x ≥ 0

j–ое ограничение: ≤ 0

Переменная x ≠ 0

j–ое ограничение: = 0

Замечание: двойственная к двойственной задаче совпадает с прямой.

Пример:       

т.е. вторая переменная не ограничена по знаку, она может быть как больше 0, так и меньше 0.
Построим двойственную задачу. Так как число ограничений равно трем, то имеем три переменных: u1, u2, u3. ЦФ задачи (Д) имеет вид:
max W = U*B = u1b1 + u2b2 + u3b3  = u1 + 4u2 + 3u3
В прямой задаче имеем матрицу А.
В задаче (Д) имеем транспонированную матрицу:  .
Таким образом, двойственная задача выглядит так:
max W = u1 + 4u2 + 3u3

Теорема двойственности. Если X и U - соответственно допустимые решения произвольных прямой и двойственной задач, то Z = C*X ≥ W = U*B.
Следствие из теоремы. Если X*, U* - соответственно решения прямой и двойственной задач, удовлетворяющих равенству C*X* = U*B, то планы X* и  U* оптимальные решения прямой и двойственной задач соответственно.
Теорема. Пусть заданы прямая и двойственная задачи:
а) если прямая и двойственная задачи имеют решения, то каждая из этих задач имеет оптимальное решение и
Z* = min(П) = max(Д) = W*
б) если одна из них имеет неограниченный оптимум, то другая не имеет решения.
Теорема. Два решения (X и U) соответственно прямой и двойственной задач оптимальны тогда и только тогда, если выполняется условие: 
(U* Aj - cj)*xj = 0; j = 1, n,  где Aj  –  j–й столбец матрицы A.

загрузка...