Часть 2

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

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

Рассмотрим задачу ЛП в самом общем виде, включающем ограничения в виде равенств и неравенств, причём для задачи максимизации ограничения- неравенства должны быть приведены к виду, например:

Определение. задача вида

называется двойственной по отношению к задаче (I).

Связь между решениями прямой и двойственной задач

Лемма 2.1. Если X– некоторый план исходной задачи (2.15, а Y–Y– произвольный план двойственной задачи (2.16), то значение целевой функции исходной задачи при плане X всегда не превосходит значение целевой функции двойственной задачи при плане Y то есть.

Лемма 2.2. Если для некоторых планов и задач (2.15) и (2.16), то - оптимальный план исходной задачи, а - оптимальный план двойственной задачи.

Теорема 2.1. (Первая теорема двойственности). Если одна из пары двойственных задач (2.15) или (2.16) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, то есть

Геометрическая интерпретация двойственных задач

Обе задачи имеют планы

Планы имеет только одна задача

Для каждой задачи двойственной пары множество планов пусто

Экономическая интерпретация двойственных задач

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