Лекция 4.
Теория двойственности в Линейном Программировании (ЛП).
Рассмотрим стандартную задачу ЛП (P) (с ограничениями-неравенствами) и связанную с ней так называемую двойственную к ней задачу (D):
Задача Р Задача D
A x ≤ b AT y ≥ c
(m×n)(n×1)(m×1) (n×m)(m×1)(n×1)
x ≥ 0 y ≥ 0
<c, x> → max <b, y> → min
В покоординатном виде эти задачи имеют следующий вид (здесь и далее суммирование по индексу i от 1 до m, по j - от 1 до n):
Задача Р Задача D
∑ aij xj ≤ bi (i=1,…, m) ∑ aij yi ≥ сj = (j=1,…, n)
xj ≥ 0 (j=1,…, n) yi ≥ 0 (i=1,…,m)
∑cjx j → max ∑ bi yi → min (суммирование по j от 1 до n) (суммирование по i от 1 до m)
Ниже приведен «рецепт» построения двойственной задачи:
1). 
; 2). c ↔ b; 3). max ↔ min; 4). A ↔ AT 5). ≤ ↔ ≥
Утверждение. Задача, двойственная к двойственной, совпадает с исходной (с точностью до обозначений). (Доказать самостоятельно).
Задачи (P) и (D) тесно взаимосвязаны. Они называются взаимодвойственными. Совместный анализ этих задач позволяет легче найти решение и, главное, изучить качественные свойства решений. В частности, если в прямой задаче только два ограничения (m=2) (и сколько угодно переменных), то в двойственной задаче будет только две переменные и ее можно решить графически. После этого с использованием свойств пары двойственных задач легко найти решение исходной задачи (что и будет проделано нами позже в упражнениях).
Главное же, теория двойственности позволяет провести анализ задачи ЛП на чувствительность к изменениям исходных данных, провести т. н. постмодельный анализ полученного решения.
Пример. Построим задачу ЛП, двойственную к следующей:
3x1 + 4x2 – 7x3 ≤ -9
2x2 + 5x3 ≤ 12
4x1 + 15x3 ≤ 16
x1, x2, x3 ≥ 0
Z = 2x1 – 17x2 + 4x3 → max.
Выпишем расширенную матрицу исходной задачи (включающую столбец правой части ограничений и строку коэффициентов целевой функции). Транспонируем ее. Получим расширенную матрицу для двойственной задачи, по которой легко построить задачу (D).
3 4 -7 -9 3 0 4 2
0 2 5 12 çè 4 2 0 -17
4 0 15 16 -7 5 15 4
2 -17 4 Z àmax -9 12 16 Fàmin
Двойственная задача имеет вид:
3y1 + 4y3 ≥ 2
4y1 + 2y2 ≥ -17
-7y1 + 5y2 + 15y3 ≥ 4
y1,y2,y3 ≥0
F = -9y1 + 12y2 + 16y3 → min
Основная лемма: Если x и y – допустимые решения прямой (Р) и двойственной (D) задач, то всегда справедливо соотношение:
∑ cj xj ≤ ∑ ∑ aij xj yi ≤ ∑ bi yi
или, используя скалярное произведение, <с, x> ≤ <Ax, y> ≡ <yTA, x> ≤ <b, y>.
Легко видеть (докажите самостоятельно), что ∑ ∑ aij xj yi = yTAx= <yTA, x>=<Ax,y>
Доказательство леммы: Каждое i-е неравенство задачи (Р) (в координатной форме), умножим на yi ≥0 и сложим: ∑ (∑ aij xj)·yi ≤ ∑ bi yi или
(*) ∑∑ aij xj yi ≤ ∑ bi yi.
Аналогично из ограничений (D), умножая их на xi, …, xn ≥ 0 и складывая, получим:
(**) ∑∑ aij xj yi ≥ ∑ сj xj.
Сопоставляя неравенства (*) и (**) (левые части в них одинаковы), получим соотношение леммы.
Первая теорема двойственности.
Теорема: Допустимое решение х* прямой задачи (P) оптимально тогда и только тогда, когда существует допустимое решение y* двойственной задачи (D) такое, что Z(x*) 
=<с, x*> = <b, y*>= F(y*) 
.
В этом случае y* - оптимальное решение двойственной задачи.
Доказательство:
Достаточность. Пусть x*, y* - допустимые решения прямой и двойственной задач и <с, x*> = <b, y*>. Тогда для любого допустимого решения х по основной лемме имеем:
<с, x> ≤ <b, y*> = <с, x*>,
то есть <с, x> ≤ <с, x*> при любом допустимом x. Это и означает оптимальность решения x*.
С другой стороны, для любого допустимого решения y из основной леммы имеем:
<b,y> ≥ <c, x*>=<b, y*>, т. е. <b,y> ≥ <b, y*>,что и означает оптимальность y*.
Необходимость (без доказательства). Если х* - оптимальное решение задачи (Р), то в двойственной задаче обязательно найдется допустимый вектор y* такой, что значения целевых функций будут равны: <c, x*> = <b, y*>.
Эквивалентная формулировка первой теоремы (симметричная): Если одна из пары двойственных задач имеет оптимальное решение, то и другая задача также имеет оптимальное решение, причем оптимальные значения целевых функций (на оптимальных решениях) совпадают.
Лемма: Если целевая функция ∑bi yi в двойственной задаче (D) не ограничена снизу на множестве допустимых решений y, то прямая задача (Р) не имеет ни одного допустимого решения, то есть несовместна.
Доказательство:
Если бы задача (Р) имела допустимое решение х˚, то по основной лемме для любого допустимого решения y F(y) = ∑ bi yi ≥ ∑ сj xj˚ = const, то есть F(y) ограничена снизу, что противоречит условию леммы. Противоречие доказывает лемму.
Замечание: Эту лемму можно использовать для установления факта несовместности задачи ЛП (то есть как достаточное условие несовместности).
Логически возможны три случая:
1) Обе задачи (Р) и (D) совместны;
2) Обе задачи несовместны;
3) Одна из задач совместна, а другая несовместна.
В последнем случае совместная задача не имеет решения, что может быть вызвано только неограниченностью целевoй функции. Действительно, если бы совместная задача была ограничена по целевой фунции, то она имела бы оптимальное решение. Но тогда по первой теореме двойственности имела бы решение и другая задача, что противоречит предположению пункта 3).
Следующие три примера показывают, что все три возможности осуществляются.
Примеры:
1) 
2х1 + х2 ≤ 4 2y1 + y2 ≥ 1
x1 + 2x2 ≤ 4 y1 + 2y2 ≥ 1
x1, х2 ≥ 0 y1, y2 ≥ 0
Z(x)= x1 + х2 → max F(y)= 4y1 + 4y2 → min
Решите задачи геометрическим способом и убедитесь, что оптимальные решения
x* =(4/3, 4/3), y* = (⅓, ⅓) и Z(x*) = F(y*)= 8/3.
Вывод: В этом примере обе задачи совместны и имеют оптимальное решение.
2) х1 - х2 ≤ 3 y1 - y2 ≥ 1
-x1 + x2 ≤ -4 -y1 + y2 ≥3
x1, х2 ≥ 0 y1, y2 ≥ 0
Z(x)= x1 + 3х2 → max F(y)= 3y1 -4y2 → min
Легко видеть, что здесь обе задачи несовместны. Складывая неравенства, в первой из них получим 0 ≥-1, во второй 0 ≥4, что указывает на несовместность ограничений.
3) х1 - х2 ≤ 1 y1 ≥ 1
-y1 ≥ 0
x1, х2 ≥ 0 y1 ≥ 0
Z(x)= x1 → max F(y)= y1 → min
Здесь первая задача совместна, а вторая – несовместна. Сложив два неравенства, получим 0 ≥1. В соответствии с леммой первая задача должна не иметь оптимального решения. Действительно, она оказывается неограниченной сверху.
Теорема существования. Прямая и двойственная задачи имеют оптимальное решение тогда и только тогда, когда обе задачи имеют допустимые решения.
Доказательство необходимости очевидно. Достаточность следует из того, что по основной лемме целевые функции в обеих задачах будут ограничены (соответственно сверху и снизу) и потому будут иметь (по теореме Вейерштрасса) оптимальные решения.
Определение: Назовем ограничение активным (существенным, эффективным), если оно выполняется в данной точке как равенство и неактивным (несущественным, неэффективным), если оно выполняется как строгое неравенство.