Выпуклый анализ. Теория двойственности в линейном программировании. Лекция 29

11. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ (ПРОДОЛЖЕНИЕ)

11.5. Теоремы двойственности и равновесия.

11.5. Теоремы двойственности и равновесия.

Справедлива следующая теорема,

которую обычно называют

Выпишем функцию Лагранжа для задачи 3д(а).

где

Сравним функцию Лагранжа для двойственной задачи

Приходим к равенству

где

Пусть

Тогда

Таким образом,

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

Тогда по теореме

Выше установлено, что

Тогда по теореме 9.2

В силу (1)

справедливо равенство

Аналогично устанавливается, что

следует

Из (2) выводим

то целевая функция

Наоборот, если

Теорема доказана.

Теорема 3 (равновесия).

Доказательство.

Из неравенства (2)

следует

В силу теоремы 1 справедливо равенство

все знаки неравенства в (6)

Имеем

Из (7) выводим

Аналогично из (7)

следует

Теорема доказана.

Пример 1.

Рассмотрим задачу линейного программирования

Построим двойственную к ней задачу:

является допустимой для прямой задачи,

так

,

,

является допустимой для двойственной задачи,

,

,

,

так как выполняются соотношения

По теореме 2 обе взаимодвойственные задачи имеют решение.

Решение прямой задачи:

Вычислим второе ограничение основной задачи,

Имеем