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

⇐ ПредыдущаяСтр 8 из 10Следующая ⇒

В основе теории двойственности лежат основные теоремы. Рассмотрим для определенности симметрическую пару двойственных ЗЛП. Пусть прямая задача записана в следующем матричном виде

, , , (9.1)

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

Соответствующая двойственная ЗЛП к прямой задаче (9.1) имеет вид

, , , (9.2)

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

Лемма 9.1 (основное неравенство теории двойственности).Для любых допустимых решений и пары взаимно двойственных задач (9.1), (9.2) справедливо неравенство

. (9.3)

□ Пусть , – допустимые решения задач (9.1), (9.2) соответственно. Умножим систему ограничений прямой задачи на вектор-столбец слева:

Умножим систему ограничений двойственной задачи на вектор-столбец справа:

Тогда получим , то есть для допустимых решений и задач (9.1) и (9.2) соответственно выполняется неравенство (9.3). ■

Лемма 9.2. Если для допустимых решений и пары взаимно двойственных задач (9.1), (9.2) выполняется равенство , то

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

□ В силу неравенства (9.3) для любого допустимого решения задачи (9.1) выполняется неравенство , то есть . Это означает, что , то есть является оптимальным решением задачи (9.1). Аналогично показывается, что является оптимальным решением задачи (9.2). ■

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

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

( ) (9.4)

( ). (9.5)

□ Пусть , есть оптимальные решения задач (9.1) и (9.2) соответственно. При этом согласно теореме 9.1 . Умножим неравенство слева на вектор :

Умножим неравенство справа на вектор-столбец :

Так как , то . Тогда из доказанного выше получим

Итак, . Расписывая покоординатно это равенство, получим равенства (9.4). Аналогично доказывается справедливость равенств (9.5). ■

Равенства (9.4) и (9.5) называются условиями дополняющей нежесткости. Из них следует:

1) если какое-либо неравенство системы ограничений одной из задач не обращается в строгое равенство оптимальным решением этой задачи, то соответствующая компонента оптимального решения двойственной задачи должна равняться нулю;

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

если , то ; если , то ; (9.6)