А.2. Основные теоремы двойственности

Теорема 1 (соотношения двойственности) [4]

Пусть прямая и двойственная задачи имеют допустимые решения. И пусть x и y – это допустимые решения прямой и двойственной задач соответственно. Тогда справедливо неравенство

, (А.5)

при чём для достижения равенства в (А.5) необходимо и достаточно выполнение условий:

; (А.6)

. (А.7)

Соотношения (А.6) и (А.7) называются соотношениями дополняющей нежёсткости.

Следствие 1 теоремы 1

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

Следствие 2 теоремы 1

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

Теорема 2 (о равенстве значений пары двойственных задач)

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

При решении прямой задачи возможна только одна из следующих взаимоисключающих друг друга ситуаций:

I прямая задача имеет решение;

II целевая функция неограниченна сверху на множестве допустимых решений;

III прямая задача имеет решение/

Аналогично, при решении двойственной задачи возможна только одна из следующих взаимоисключающих ситуаций:

I’ двойственная задача имеет решение;

II’ целевая функция двойственной задачи не ограничена снизу на множестве допустимых решений;

III’ двойственная задача не имеет допустимых решение.

Комбинируя попарно ситуации I, II, III с I’, II’, III’ получаем, что принципиально возможны следующие 9 пар, которые можно представить в виде таблицы А2.

Таблица А.2

	I (o'k)	II ()	III ()
I' (o'k)	1)	2)	3)
II' ()	4)	5)	6)
III' ()	7)	8)	9)

Согласно следующей теореме, никакие пары, кроме 1), 6), 8), 9) не возможны вообще.

Теорема 3 (двойственности)

Для пары взаимно-двойственных задач имеет место один из следующих взаимоисключающих случаев:

1) Прямая и двойственная задачи имеют решения, причём значения задач совпадают.

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

3) Двойственная задача имеет непустое множество допустимых решений, её целевая функция не ограничена снизу; прямая задача не имеет допустимых решений.

4) Прямая и двойственная задачи не имеют допустимых решений.