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

Двойственная (обратная) задача - это задача линейного программирования формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи.

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

1. Число переменных в двойственной задаче равно числу ограничений в прямой задаче. Каждому i-му ограничению исходной задачи соответствует переменная yi и, наоборот, каждому j-му ограничению двойственной задачи соответствует переменная xj исходной задачи.
2. Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов системы ограничений прямой задачи путем транспонирования.
3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

4. Свободными членами системы ограничений двойственной задачи являются коэффициенты целевой функции прямой задачи.
5. Двойственная задача решается на минимум, если целевая функция прямой задачи задается на максимум, и наоборот.
6. Коэффициентами целевой функции двойственной задачи служат свободные члены системы ограничений прямой задачи.

7. Если переменная прямой задачи , то j-ое условие системы ограничений двойственной задачи является неравенством. Если xj -ое – любое число, то j-ое условие двойственной задачи представляет собой уравнение.
8. Если i-ое соотношение прямой задачи является неравенством, то соответствующая оценка i-ого ресурса – переменная , если i-е соотношение представляет собой уравнение, то переменная двойственной задачи yi-ое – любое число.

Математические модели двойственных задач могут быть симметричными и несимметричными.
В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а в двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными.
В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.

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

Первая (основная) теорема двойственности

Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения.
Замечание. Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное.
Это связано с тем, что при нарушении единственности оптимального решения исходной задачи в выражении линейной функции ее оптимального решения через неосновные переменные отсутствует хотя бы одна из основных переменных.

Компоненты оптимального решения двойственной задачи называются оптимальными (двойственными) оценками исходной задачи.
Канторович Л.В. назвал их объективно обусловленными оценками (скрытые доходы, маргинальные оценки, разрешающие множители).
Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (т.е. полностью используемые) ресурсы получают ненулевые оценки, а недефицитные – нулевые оценки.
В оптимальный план производства могут попасть только рентабельные, неубыточные виды продукции (правда, критерий рентабельности здесь своеобразный: цена продукции не превышает затраты на потребляемые при ее изготовлении ресурсы, а в точности равна им).

Для выяснения того, что показывают численные значения объективно обусловленных оценок ресурсов, рассмотрим следующую теорему.
Третья теорема двойственности.

1.4.3. Двойственный симплекс- метод
Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимальное решение исходной задачи находится с помощью теорем двойственности, называется двойственным симплексным методом.
Этот метод бывает выгодно применять, когда первое базисное решение исходной задачи недопустимое или, например, когда число ее ограничений m больше числа переменных n.

Алгоритм двойственного симплексного метода включает следующие этапы
1. Составление псевдоплана.
Систему ограничений двойственной задачи требуется привести к системе неравенств смысла « ».
Для этого обе части неравенств смысла « » необходимо умножить на (-1).
Затем от системы неравенств смысла « » переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. Первый опорный план заносят в симплексную таблицу.

2. Проверка плана на оптимальность.
Если в полученном опорном плане не выполняются условие оптимальности, то решаем задачу симплексном методом.
Если в опорном плане условия оптимальности удовлетворяются и все значения базисных переменных – положительные числа, то получен оптимальный план.
Наличие отрицательных значений в столбце значений базисных переменных свидетельствуют о получении псевдоплана.

3. Выбор ведущих строки и столбца.
Среди отрицательных значений базисных переменных выбирают наибольшее по абсолютной величине. Строка, соответствующая этому значению, является ведущей. Симплексную таблицу дополняют строкой , в которую заносят взятые по абсолютной величине результаты деления коэффициентов индексной строки на отрицательные коэффициенты ведущей строки. Минимальные значения определяют ведущий столбец и переменную, вводимую в базис. На пересечении ведущих строки и столбца находится разрешающий элемент.