Рассмотрим пару задач ЛП вида:
Задачу (I) называют прямой задачей ЛП, а (II) - двойственной. Ограничения задач (I) и (II), соответствующие друг другу (по стрелке),
называются сопряженными. Заметим, что задача двойственная к (II),
есть исходная прямая задача, т.е. соотношение двойственности взаимное. Поэтому можно любую из такой пары задач считать прямой, а другую двойственной.
Грубо говоря, двойственная задача - это на 900 повернутая исходная прямая задача. В этой связи полезно усвоить следующую схему соответствия.
Построить двойственную задачу к следующей задаче ЛП:
Прежде чем приступать к
построению двойственной задачи, необходимо
упорядочить запись исходной: согласовать знаки
неравенств в ограничениях задачи с целевой
функцией. Так как целевая функция
минимизируется, то неравенства должны быть
записаны с помощью знака 
Для этого второе неравенство умножим на -1:
Теперь, вводя двойственные переменные
запишем в соответствии с указанным правилом пару двойственных задач:
Задача слева - исходная прямая задача, задача справа - двойственная к исходной задаче.
Рассмотрим стандартную задачу ЛП и двойственную к ней :
Пара двойственных задач (I) и (II) называется парой симметрических двойственных задач.
Не ограничивая общности, теорию двойственности можно рассматривать для пары симметрических задач, поскольку для любой задачи ЛП существует эквивалентная ей стандартная задача ЛП(1) и поэтому теоремы, справедливые для пары симметрических двойственных задач, будут справедливы для пары общих двойственных задач.
Рассмотрим пару симметрических двойственных задач в матричной форме записи
Здесь
А- матрица из m строк и n
столбцов, 
-
транспонированная матрица. Введем обозначения
для допустимых областей задачи (I) и (II)
Основное неравенство двойственности
Для любых допустимых
решений прямой задачи х и для любых допустимых
решений двойственной задачи у выполняется
неравенство 
Доказательство.
Из системы ограничений
задачи 
Из системы ограничений задачи
Объединяя полученные
неравенства, имеем 
Теорема доказана.
Если для некоторых
допустимых решений 
выполняется равенство значений целевых
функций 
то х*, у* -
оптимальные решения задачи I и II соответственно.
Доказательство.
Пусть 
- произвольное допустимое решение
задачи (I). По основному неравенству
двойственности имеем
По определению это означает, что х* - оптимальное решение задачи (I). Аналогично доказывается, что у* - оптимальное решение задачи (II).
Следствие доказано.
Канонической комбинацией неравенств системы
называется неравенство вида
, где 
, i=1,..., m.
Неравенство вида 
называется противоречием,
если ему не удовлетворяет ни один вектор 
Замечание 1.
В противоречивом
неравенстве
выполняется :
Доказательство.
1) Если 
, то вектор х=(0,...,0) удовлетворяет
неравенству
поэтому b<0.
2) Если существует j
удовлетворяет неравенству
.
Замечание доказано.
Система (S) называется несовместной,
если ей не удовлетворяет ни один вектор 
Лемма 1 (Фаркаша).
Если система (S) несовместна, то существует ее каноническая комбинация, являющаяся противоречивым неравенством.
Система (S) называется несовместной
при 
, если ей не
удовлетворяет ни один вектор .Неравенство вида называется противоречивым
при , если ему не
удовлетворяет ни один вектор .
Замечание 2.
В противоречивом при неравенстве
выполняется
Доказательство.
1) Если , то вектор х=0 удовлетворяет
неравенству. Следовательно b<0.
2) Если существует j
удовлетворяет неравенству
.
Замечание доказано.
Вторая лемма Фаркаша.
Если система (S)
несовместна при ,
то существует ее коническая комбинация,
являющаяся неравенством, противоречивым при .
Рассмотрим пару симметрических двойственных задач
Основная лемма.
Пусть допустимая
область задачи (I) непустая и для любого 
выполняется 
Тогда существует 
, для которого выполняется 
Доказательство.
Утверждение леммы
означает, что существует вектор 
удовлетворяющий
системе
Предположим, что система (S)
несовместна при 
Тогда по второй лемме Фаркаша существует каноническая комбинация, которая является неравенством, противоречивы при
Перепишем это неравенство в виде :
По замечанию 2 в неравенстве, противоречивом при
Для 
возможны два случая :
Случай 1. Если , то делим полученные неравенства
(+) на 
:
В результате получим вектор
Это противоречит условию леммы.
Случай 1. Если 
, то система (+)
принимает вид
Рассмотрим вектор
Заметим, что для любого t>0
вектор 
Действительно, подставляя
координаты вектора 
в
ограничения задачи (I), получим
для всех i=1,...,m.
Неотрицательность вектора
получается из
неотрицательности компонент векторов х', a ' и t>0.
Итак, для любого t>0
Значение целевой функции
неограниченно возрастает
при 
, так как
Но по условию леммы для
любого допустимого вектора 
целевая функция ограничена 
Получили
противоречие.
В обоих случаях полученные противоречия возникли из-за того, что было предположение о несовместности системы (S) при
т.е. существует 
для которого
Лемма доказана.
Рассмотрим пару симметричных двойственных задач
Первая теорема двойственности.
Если одна из пары двойственных задач (I) и (II разрешима, то разрешима и другая задача, причем оптимальные значения целевых функций прямой и двойственной задач совпадают
оптимальные планы задач (I) и (II) соответственно.
Доказательство.
1. Пусть задача (I) разрешима, и пусть
т.е. х* - оптимальное решение. Обозначим M= L(х*).
Тогда по основной лемме существует
для которого 
Но по основному неравенству двойственности имеем :
Объединяя последние два
соотношения, имеем 
откуда следует, что у* - оптимальное решение задачи (II) и
2. Пусть теперь задача (II) -разрешима. Построим эквивалентную (II) задачу
Задача (II') разрешима, так как задача (II) разрешима. Тогда по пункту 1 двойственная к (II') задача :
Но эта задача эквивалентна задаче (I). Следовательно, задача (I) разрешима.
Теорема доказана.
Первый критерий оптимальности
Решение 
оптимально тогда и только тогда, когда
существует решение
такое, что 
Доказательство.
Необходимость следует из первой теоремы двойственности.
Достаточность следует из достаточного условия оптимальности.
Рассмотрим пару симметрических двойственных задач ЛП
Вторая теорема двойственности
Чтобы допустимые решения х, у пары двойственных задач (I) и (II) были оптимальными необходимо и достаточно, чтобы выполнялись условия :
Доказательство.
Необходимость. По условию допустимые решения х, у - оптимальны.
то из оптимальности
решений х, у по первой теореме двойственности 
В результате имеем 
Необходимость доказана.
Достаточность. По условию
По первой теореме двойственности получаем, что х, у - оптимальные решения задач (I) и (II).
Достаточность доказана.
Допустимые решения х, у задач (I) и (II) удовлетворяют условиям дополняющей нежесткости (УДН), если при подстановке этих векторов в ограничения задач (I) и (II) хотя бы одно из любой пары сопряженных неравенств обращается в равенство
Второй критерий оптимальности (следствие из условий дополняющей нежесткости)
Чтобы допустимые решения х, у пары двойственных задач (I) и (II) были оптимальны, необходимо и достаточно, чтобы выполнялись соотношения :
Доказательство. Распишем
покоординатно :
Из допустимости решений х и у следует, что
тогда, когда каждое слагаемое в этих равенствах равно нулю
Произведение двух сомножителей, как
известно, равно нулю, тогда и только тогда, когда
хотя бы один из множителей равен нулю.
Следовательно, равенства (*) или, что то же самое
эквивалентны условиям (1)-(4), и по второй теореме двойственности получаем справедливость утверждения.
Критерий доказан.
Замечание Условия (1)-(4) есть условия дополняющей нежесткости, поэтому критерий можно сформулировать более лаконично.
Второй критерий оптимальности
Чтобы допустимые решения х, у пары двойственных задач (I), (II) были оптимальны, необходимо и достаточно, чтобы выполнялись УДН.
Критерий разрешимости задачи ЛП
Точной верхней гранью (супремумом) функции L(х) на множестве D называется такое число М*, что
Если для пары двойственных задач (I),(II)
Доказательство. Предположим противное, т.е.
Обозначим М=L(y). Тогда М<M*
и по определению супремума 
Полученное неравенство противоречит основному неравенству двойственности по которому
Предположение было неверным.
Лемма доказана.
Задача (I) (на максимум) разрешима тогда и только тогда , когда целевая функция L(x) ограничена сверху на непустом допустимом множестве.
Доказательство.
Необходимость. Если задача (I) разрешима, то
Следовательно L(x)
ограничена сверху на 
величиной
L*=L(x*).
Необходимость доказана.
Достаточность. Пусть 
и L(x) ограничена сверху на 
что означает оптимальность вектора у* для задачи (II). Итак, задача (II) разрешима. Тогда по первой теореме двойственности и задача (I) разрешима.
Достаточность доказана.
Малая теорема двойственности.
Если прямая и
двойственная задачи имеют хотя бы по одному
допустимому решению (т.е. , 
), то обе задачи разрешимы.
Доказательство. Пусть
По основному неравенству двойственности
т.е. L(x) ограничена сверху на допустимом множестве. Тогда по критерию разрешимости прямая задача (I) разрешима. По первой теореме двойственности разрешима и двойственная задача (II).
Теорема доказана.
Пусть и
L(x) неограничена сверху на 
Обратное утверждение тоже верно.
Доказательство.
Пусть L(x) неограничена
сверху на . Предположим
противное, т.е. . Тогда
и по основному неравенству двойственности
Получили ограниченность
функции L(x), что противоречит условию.
Следовательно, предположение было неверным и 
.
Докажем обратное утверждение.
Пусть теперь . Предположим противное, т.е. L(x)
ограничена сверху на Тогда по критерию разрешимости задача (I)
разрешима и по первой теореме двойственности
задача (II) разрешима. Но тогда .
Получили противоречие. Следовательно
предположение было неверным и L(x) неограничена
сверху на
Теорема доказана.
Классификация задач ЛП
1. , . Тогда задачи (I) и (II) разрешимы.
2. , . Тогда задачи (I) и (II) неразрешимы.
Задача (I) неразрешима из-за неограниченности
целевой функции. Задача (II) неразрешима из-за
пустоты допустимой области.
3. 
, . Аналогично пункту
2.(только задачи (I) и (II) меняются местами).
4. , I. Пример
Используя теоремы двойственности, решить двойственную задачу, если известно решение прямой задачи.
Пусть решение задачи найдено одним из стандартных методов:
х* = (40, 0, 20), L = 20000. Построим двойственную задачу:
По первой теореме двойственности задача разрешима, причем
Найдем оптимальный план
задачи, используя вторую теорему двойственности. Подставим координаты вектора x* в ограничения задачи (22). Получим
Следовательно, в силу УДН, неравенство
должно выполняться как равенство, то есть
Далее, так как
то в силу УДН,
Получаем систему линейных уравнений
Планы x* = (40, 0, 20) и y* = (125,50,0) удовлетворяют УДН, следовательно, в силу второй теоремы двойственности, являются оптимальными в задачах (22) и (23) соответственно.
Пример
Исследовать вектор x = (1,0,1, -- 1) на оптимальность в задаче ЛП
Вначале надо проверить, является ли вектор x допустимым. Для
этого подставляем координаты вектора в ограничения
Так как второе ограничение
выполняется как строгое неравенство, тов силу
УДН для оптимальности вектора x необходимо
выполнение равенства 
Построим двойственную задачу
Поскольку 
, то из третьего и четвертого
ограничений получаем 
Но по
УДН из условия 
следует, что должно выполняться равенство в
первом ограничении двойственной задачи: 
Подставляя значения 
Следовательно, УДН не выполняются и вектор x =(1,0,1, -1) не является оптимальным в исходной задаче.