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

Рассмотрим вначале пару симметричных двойственных задач (см.п.1.11). Пусть дана исходная задача «о ресурсах»:

(1)

.

Тогда двойственная задача, как мы уже знаем, имеет вид:

(2)

.

Теорема 1. Пусть - допустимое решение исходной задачи (1) и - допустимое решение двойственной задачи (2). Тогда справедливо неравенство

. (3)

Доказательство. Умножив каждое ограничение задачи (1) на соответствующую двойственную переменную , получим систему неравенств:

(4)

Сложив все неравенства системы (6), получим оценку целевой функции двойственной задачи:

(5)

Умножив каждое неравенство системы (2) на соответствующую ему переменную , получим систему неравенств:

(6)

Складывая все неравенства системы (6), получаем, что

(7)

Поскольку двойные суммы слева в (5) и (7) отличаются только порядком суммирования и перестановкой множителей и , то они равны друг другу. Отсюда следует, что

(8)

Отсюда следует неравенство (3). Теорема доказана.

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

. (9)

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

Доказательство. Из (3) вытекает, что для любого допустимого решения справедливо неравенство

. (10)

В силу (9) отсюда следует, что - оптимальное решение исходной задачи. Аналогично получаем, что для любого допустимого решения справедливо неравенство

. (11)

В силу (9) отсюда следует, что - оптимальное решение двойственной задачи. Следствие доказано.

Определение. Двойственными оценками называются переменные оптимального решения двойственной задачи.

Следующие две теоремы обычно называют первой и второй теоремами двойственности.

Теорема 2. Пусть существует оптимальное решение исходной задачи. Тогда существует оптимальное решение двойственной задачи и справедливо равенство

. (12)

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

(13)

и

(14)

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

Отметим, что системы (13) и (14) равносильны равенству (12). Действительно, повторив рассуждения доказательства теоремы 1 с заменой неравенств (4) и (6) на соответствующие равенства (13) и (14), вместо неравенства (3) получим равенство (12).

Вторая теорема двойственности может быть также сформулирована следующим образом.

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

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

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

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

Дата добавления: 2014-12-26