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

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

11.1. Двойственная задача к канонической

11.1. Двойственная задача к канонической задаче линейного программирования.

Рассмотрим каноническую задачу

Задача 1д(а).

формулируется так.

Данная задача эквивалентна следующей.

Задача 1д.

Эквивалентность задачи

Задача 1д(а). является задачей линейного программирования

Здесь

Покажем, что задача двойственная

Тогда

Задача двойственная к задаче 1д(а)

имеет вид

(Задача 1д(а))д.

(Задача 1д(а))д(а).

11.2. Двойственная задача к стандартной задаче линейного программирования.

Рассмотрим стандартную задачу

следует искать среди тех векторов

Двойственная задача

формулируется так.

Данная задача

Здесь

Тогда

Тогда

Задача двойственная к задаче 2д(а)

имеет вид.

(Задача 2д(а))д.

(Задача 2д(а))д(а).

11.3. Двойственная задача к общей задаче линейного программирования.

Рассмотрим общую задачу

Полагаем

Построим функцию Лагранжа для задачи 3.

Имеем

определяемая формулой

здесь выписывается в явном виде.

Действительно,

Двойственная задача:

Задача 3д.

Данная задача эквивалентна следующей.

Задача 3д(а).

Эквивалентность задачи 3д и задача 3д(а)

11.4. Правило построения двойственной задачи.

Задача 3.

Задача 3д(а).

Сформулируем правило,

В двойственной задаче 3д(а)

Матрица ограничений в двойственной задаче

Вектором правых частей ограничений

Пример 1.

Прямая задача.

Двойственная задача.