§1.4 Двойственные задачи.

Любой задаче линейного программирования, называемой исходной или прямой. Можно поставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе эти задачи образуют пару двойственных (или сопряженных) задач.

В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи): Симметричные задачи

3. ,	,
4. ,	,

где:

,              ,              ,              ,               .

Правила составления двойственных задач.

1. Во всех ограничениях исходной задачи свободные члены должны находится в правой части, а члены с неизвестными – в левой.
2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.
3. Если знаки неравенств в ограничениях исходной задачи «», то целевая функция должна максимизироваться, а если «», то минимизироваться.
4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.
5. Целевая функция двойственной задачи имеет вид, где – свободный член целевой функции F(X) исходной задачи, – свободные члены в ограничениях исходной задачи, при этом – свободный член именно того ограничения исходной задачи, которому соответствует неизвестная, а  – неизвестные в двойственной задаче.
6. Целевая функция Z(Y) двойственной задачи должна оптимизироваться противоположным по сравнению с F(X) образом, т.е.
   если , то и наоборот.
7. Каждому неизвестному , исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих n ограничений образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными . Все знаки неравенств имеют вид «», если«» если .

Коэффициенты, с которыми неизвестные входят в ограничение, соответствующее неизвестному , совпадают с коэффициентами при этом неизвестном в ограничениях исходной задачи.

Первая теорема двойственности

Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие. Возможны  следующие случаи:

• обе задачи из пары двойственных задач имеют оптимальные решения;
• одна из задач не имеет решения ввиду неограниченности целевой функции, а другая не имеет решения ввиду несовместности системы ограничений.

Теорема 3.

Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.

Экономический смысл первой теоремы двойственности состоит в том, что предприятию безразлично, производить ли продукцию по оптимальному плану и получить максимальную прибыль, либо продавать ресурсы по оптимальным ценам и возместить от продажи равные ей минимальные затраты на ресурсы.

Вторая теорема двойственности

Пусть имеется симметричная пара двойственных задач

Теорема 4. Для того чтобы допустимые решения , являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства:

;

.

Иначе, если при подстановке оптимального решения в систему ограничений ограничение исходной задачи выполняется как строгое неравенство, то координата оптимального решения двойственной задачи равна нулю, и, наоборот, если координата оптимального решения двойственной задачи отлична от нуля, то ограничение исходной задачи удовлетворяется оптимальным решением как равенство.

Пример.

Решая исходную задачу графическим методом, получим , при этом .

По 2-ой теореме двойственности систему ограничений двойственной задачи можно записать в виде равенств:

Подставим в систему ограничений исходной задачи:

Тогда система ограничений двойственной задачи примет вид

Откуда .

Пусть дано решение двойственной задачи , , найдем решение исходной. По 1-ой теореме двойственности . Так как , то по 2-ой теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства;

Откуда , при этом  .