Двойственность ЗЛП

X={xÎRⁿ, x, Axb}b- вектор размерности n, A- матрица размерности m´n.

f(x) = (c, x)- целевая функция (линейна)

ЗЛП: min f(x)-?, при xÎX- прямая задача линейного программирования.

Построим функцию Лагранжа.

=(c, x)+(l₁,b-Ax)+(l ₂,-x), l₁ÎR^m, l₂ÎRⁿ (подгоняем под g_i(x)£0).

Тогда min(c, x) = max inf [(c, x)+(l₁, b-Ax)+(l₂, -x)], при l₁³0, l₂³0, xÎRⁿ = (см. метод модификации функции Лагранжа) = max inf [(c- A^Tl₁-l₂, x)+(b, l₁)]

при l₁³0, l₂³0, xÎRⁿ =

(l_1, Ax)=(A^Tl₂, x)

= max , при l₁³0, l₂³0

= max (b, l₁) (при l₁³0, l₂³0, с=A^Tl₁+l₂) = max (b, l₁) (при l₁³0, с ³A^Tl₁)

= max (b, l) = (c, x*), с ³A^Tl, l ³0

max (b, l), с ³A^Tl, l ³0- двойственная ЗЛП.

Таким образом, решение исходной ЗЛП может быть сведено к решению новой ЗЛП: максимизация (b, l) по множеству, определенному условиями с ³A^Tl,

l ³0.

Утверждения:

1. Вектор состояния l двойственной ЗЛП имеет размерность m- количество ограничений в исходной задаче (размерность вектора Ax).

2. Количество ограничений (кроме l ³0, неотрицательных) совпадает с размерностью вектора состояний в исходной задаче (вектора x).

3. Суммарное количество ограничений совпадает с (n + m) в обеих задачах.

4. Двойственная задача к двойственной дает исходную.

Когда какую задачу решать - зависит от числа ограничений и от размерности x.

Утверждение:

Двойственные переменные можно рассматривать как коэффициент чувствительности целевой функции к изменению параметров задачи.

Пусть x*, l *- решения прямой и двойственной задач, причем эти решения единственны (достиг. в одной точке минимум x и в одной максимум l)

Тогда f(x*) = (b, l*), несколько изменим b: b®b+Db Þ min увеличился на

(Db, l*). При сдвиге b градиенты не изменились, l_i остались теми же.

Обозначим h(b) = min f(x), Ax ³b, x ³0.

Тогда при малых Db:

h(b+Db) = h(b) + (Db, l*), следовательно при Db® 0 получим:

, для компонент векторов