3.2. Леммы и теоремы двойственности

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

.

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

Лемма 3. Если и , то обе задачи разрешимы.

Лемма 4. Пусть и таковы, что

,

тогда и - оптимальные решения исходной и двойственной задач соответственно.

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

,

где и - оптимальные решения исходной и двойственной задач соответственно.

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

, (3.2.8)

. (3.2.9)

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

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

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

Рассмотрим пример, используя условие и решение примера 1.1.

Алгоритм решения двойственной задачи

Шаг 1. Выписывается двойственная задача (см. алгоритм построения двойственной задачи).

Шаг 2. Просматриваются переменные исходной задачи.

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

Шаг 3. Значения переменных исходной задачи подставляются поочередно в левую часть каждого ограничения этой задачи. Полученное значение сравнивается с правой частью, если получено строгое неравенство, то соответствующая переменная двойственной задачи полагается равной нулю.

Шаг 4. Решается полученная система линейных уравнений относительно двойственных переменных . Решение этой системы есть оптимальное решение двойственной задачи.

Шаг 5. Вычисляется значение целевой функции . Оно должно получиться равным .

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

Пример 3.2. Дана ЗЛП и ее оптимальное решение:

, (3.2.10)

, (3.2.11)

, (3.2.12)

,

, .

Требуется записать двойственную задачу и найти ее решение.

Решение. Выпишем исходную задачу и припишем к ее ограничениям слева двойственные переменные:

	,
	,
	.

Двойственная задача:

,

,

.

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

Так как и , следовательно, оба ограничения двойственной задачи записываются как строгие равенства:

,

.

Подставим поочередно в каждое из неравенств исходной задачи:

,

, следовательно, ,

.

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

То есть .

Вычислим значение целевой функции , из чего следует .