Двойственная задача. 
Неделя здоровья в дошкольном учреждении

Общая схема построения двойственной задачи.

Если задана общая задача ЛП:

где D определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется общая задача ЛП:

где D* определяется системой уравнений и неравенств:

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

• 1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.
• 2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.
• 3. Матрица ограничений задачи, А транспонируется.
• 4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче определяют номера ограничений, имеющих форму неравенств в двойственной задаче .
• 5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче.

Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей.

((D*)*, (f*)*)?(D, f),.

Основные теоремы:

Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают Теорема 2 (о дополняющей не жесткости). Для того чтобы план х* и у* являлись оптимальными решениями соответственно задач линейного программирования и двойственной к ним необходимо и достаточно, чтобы выполнялись следующие соотношения:

Теорема 3 (об оценках). Значение переменных в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f (x*).