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

Теорема 1: Для любых допустимых планов и для исходной и двойственной задач значение целевой функции в задаче максимизации не больше значения целевой функции в задаче минимизации.

(1.17)

Экономический смысл: суммарный доход от реализации продукции не больше суммарной оценки ресурсов.

Теорема 2: Если исходная и двойственная ей задачи имеют допустимый план, то существует оптимальный план исходной задачи и двойственной задачи.

Теорема 3 (первая основная теорема двойственности): Если одна из задач двойственной пары имеет оптимальный план, то другая – также имеет оптимальный план.

Для любых оптимальных планов и имеет место равенство:

(1.18)

Теорема 4: (вторая основная теорема двойственности – теорема о дополнительной нежесткости): Для того чтобы допустимые планы и пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

(1.19)

Это означает, что если какое-либо ограничение одной задачи при подстановке в него оптимального плана обращается в строгое неравенство, то соответствующая этому ограничению переменная в оптимальном плане двойственной задачи равна 0.

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

Если (1.20)

Если (1.21)

Если (1.22)

Если (1.23)

Пример 1.10:

Используя теоремы двойственности найти решение ЗЛП

max f(x) = 7x₁ + x₃ - 4x₄

Решение:

min φ(y) = 6y₁ - y₂

Надо найти х.

Найдем и :

Значения совпали.

Пример 1.11:

Найденное оптимальное решение (см. предыдущую тему):

Запишем двойственную задачу

.