7.2. Теоремы двойственности..

Теорема 1. (Первая теорема двойственности). Если одна из взаимно двойственных задач имеет решение, то его имеет и другая, причем = .

Следствие. Если одна из двойственных задач не имеет решения, то и вторая не имеет решения.

Теорема 2. (Вторая теорема двойственности). Для того, чтобы решения ( ), ( )были оптимальны, необходимо и достаточно выполнения условий

, (7)

. (8)

Условия (7), (8) называют условиями дополняющей нежесткости. Используя эти условия, из решений одной из двойственных задач можно найти решения другой задачи.

Пример 1. Пусть имеем исходную задачу распределения ресурсов:

Пусть для производства трех видов товаров Т₁ , Т₂ и Т₃ требуются ресурсы Р₁ и Р₂. Наличие ресурсов, и их нормы расхода, требуемые на производство единицы товара, и прибыль предприятия при реализации единицы товара приводятся в таблице.

	Т1	Т2	Т3	Имеющиеся ресурсы
Р1	3	1	1	b1= 5
Р2	1	1	3	b2= 3
Прибыль от реализации	6	4	6

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

Обозначим через х₁, х₂, х₃ соответственно количество товара Т₁ , Т₂ и Т₃. Тогда математическая модель задачи имеет вид:

(9)

х₁≥0, х₂≥0, х₃

F=

Составим задачу, двойственную задаче (9), (10).

(11)

y₁≥0,y₂≥0

Z= (12)

которую можно решить графически.

у2
			М
								у1

.

Тогда, согласно первой теореме двойственности = =14.

Оптимальные найдем из условий (7)-(8)

1 ,

3 = 0,

,

,

,

откуда получаем

и решения задачи (9)-(10) =14.

Рассмотрим связь между двойственными задачами линейного программирования в каноническом виде на примере 1.Сведем ограничения (9) к ограничениям вида равенств

а ограничения (11)

Тогда получим задачи

Исходная задача (13) х1≥0, х2≥0, х3 F=

Двойственная задача (14) y1≥0,y2≥0, Z=

Рассмотрим решения этих задач (см. пример 1): исходной:

двойственной :

Кроме того, из системы уравнений (14) получим =0 и =4

.

Установим соответствие между первоначальными и дополнительными переменными

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

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

Имеет место следующая теорема, которую также называют второй теоремой двойственности.

Теорема 2’. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, то есть для любых i=1,…,m, j=1,…,n :

если