1.7. Теория двойственности

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

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

	Исходная задача	Двойственная задача
	Симметричные пары
1.
2.

	Исходная задача	Двойственная задача
	Несимметричные пары
3.
4.

Здесь , , .

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

1. Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными – в левой.

2. Ограничения – неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

3. Если знаки неравенств в ограничениях исходной задачи « », то целевая функция должна максими­зироваться, а если « », то минимизироваться.

4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограниче­нию-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.

5. Целевая функция двойственной задачи имеет вид ,

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

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

7. Каждому неизвестному , исходной задачи соот­ветствует ограничение в двойственной задаче. Совокупность этих ог­раничений (вместе с условиями неотрицательности неизвестных , соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойствен­ной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными – в левых. Все знаки неравенств имеют вид « », если , и « », если .

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

Пример 9. Составить задачу, двойственную к данной

,

Решение:

Умножим первое ограничение – неравенство на . Задача примет вид исходной задачи симметричной пары двойственных задач.

Т.к. система ограничений исходной задачи имеет два ограничения, то двойственная задача будет содержать две переменные: и .

Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функцию

Функция минимизируется, так как целевая функция исходной задачи максимизируется.

Умножим коэффициенты при в системе ограничений на соответствующие переменные двойственной задачи и сложим их, получим . Данная сумма больше или равна коэффициенту при в целевой функции . Неравенство имеет вид « », потому что целевая функция двой­ственной задачи минимизируется. Аналогично составляют ограниче­ние двойственной задачи для переменной :

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

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

Таким образом, двойственная задача имеет вид:

Установить взаимосвязь между оптимальными решениями пары двойственных задач позволяют теоремы двойственности. Решив одну из па­ры двойственных задач, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие.

Возможны следу­ющие случаи:

• обе задачи из пары двойственных имеют оптимальные решения;

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

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

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

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

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

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

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

, ;

, .

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