Правило построения двойственной задачи
1. Упорядочивается запись исходной
задачи, т.е. если целевая функция задачи
максимизируется, то ограничения-неравенства
должны быть вида «
»,
если минимизируется, то вида «
».
Выполнение этих условий достигается
умножением соответствующих ограничений
на
.
2. Если исходная задача является задачей максимизации, то двойственная будет задачей минимизации. При этом вектор, образованный из коэффициентов при неизвестных целевой функции исходной задачи, совпадает с вектором констант в правых частях ограничений двойственной задачи. Аналогично связаны между собой векторы, образованные из коэффициентов при неизвестных целевой функции двойственной задачи, и константы в правых частях ограничений исходной задачи.
3. Каждой переменной
двойственной задачи соответствует
-ое
ограничение исходной задачи, и, наоборот,
каждой переменной
исходной задачи соответствует
-ое
ограничение двойственной задачи.
4. Матрица
из коэффициентов при неизвестных
двойственной задачи образуется
транспонированием матрицы
,
составленной из коэффициентов при
неизвестных исходной задачи.
5. Если на -ую переменную исходной задачи наложено условие неотрицательности, то -ое ограничение двойственной задачи будет неравенством, в противном случае – будет равенством. Аналогично связаны между собой ограничения исходной задачи и переменные двойственной.
Пример 3.1. Для данной ЗЛП построить двойственную задачу:
;
.
Решение. Так как целевая функция на максимум, то все ограничения должны быть « » или «=». Поэтому второе и третье ограничения умножаем на . Получаем следующую систему ограничений
Каждому ограничению прямой задачи
вводим переменную двойственной задачи.
Так как прямая задача содержит три
ограничения-неравенства, то вводим три
переменные двойственной задачи:
.
Причем
.
Матрицу, составленную из коэффициентов при неизвестных исходной задачи, транспонируем:
,
.
Поскольку в прямой задаче целевая функция на максимум, то в двойственной задаче целевая функция будет на минимум, а система всех ограничений будет на « ».
Таким образом, получаем следующую двойственную задачу для исходной прямой ЗЛП:
;
.
Пример 3.2. Для данной ЗЛП построить двойственную задачу:
;
любого знака.
Решение. Так как целевая функция на минимум, то все ограничения должны быть « » или «=». Третье ограничение-неравенство умножаем на . Получаем
Прямая задача содержит четыре ограничения,
следовательно, вводим четыре переменные
двойственной задачи:
.
Поскольку первое, третье и четвертое
ограничения вида «
»,
то
.
Второе ограничение вида «=», значит,
любого знака.
В прямой ЗЛП переменная
,
а
и
любого знака.
Следовательно, в двойственной задаче
первое ограничение будет вида «
»,
второе и третье ограничения вида «=».
Матрицу, составленную из коэффициентов при неизвестных исходной задачи, транспонируем:
,
.
Целевая функция двойственной задачи будет на максимум.
Таким образом, получаем следующую двойственную задачу для исходной прямой ЗЛП:
;
любого знака.