1.4. Двойственные задачи лп
Каждой задаче ЛП можно определенным образом сопоставить некоторую другую задачу ЛП, называемую двойственной, по отношению к исходной или прямой. Так, общей задаче ЛП
(1.18)
(1.19)
(1.20)
(1.21)
соответствует двойственная задача следующего вида:
(1.22)
(1.23)
(1.24)
(1.25)
Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи:
− прямая задача является задачей максимизации, двойственная задача – задачей минимизации;
− число m переменных двойственной задачи равно числу ограничений прямой задачи, а число n ограничений двойственной задачи равно числу переменных прямой задачи;
− коэффициенты
целевой функции прямой задачи становятся
свободными членами ограничений
двойственной задачи;
− свободные члены
ограничений
прямой задачи становятся коэффициентами
целевой функции двойственной задачи;
− матрица коэффициентов ограничений двойственной задачи получается транспонированием матрицы коэффициентов ограничений прямой задачи;
− если i-е ограничение прямой задачи является неравенством вида « ≤ », то i-я переменная yi двойственной задачи должна быть неотрицательной, т.е. yi≥0; если i-е ограничение прямой задачи является равенством, то i-я переменная yi двойственной задачи может принимать произвольные значения;
− если j-я
переменная xj
прямой задачи должна быть неотрицательной,
т.е.
,
то j-е
ограничение двойственной задачи является
неравенством вида « ≥ »; если j-я
переменная xj
прямой
задачи может принимать произвольное
значение, то j-е
ограничение двойственной задачи является
равенством.
В свою очередь прямая задача (1.18)÷(1.21) является двойственной по отношению к двойственной задаче (1.22)÷(1.25), рассматриваемой в качестве исходной. Для составления прямой задачи по известной двойственной можно использовать аналогичные вышеприведенным правила.
Задачи (1.18)÷(1.21) и (1.22)÷(1.25) образуют пару задач, называемых в ЛП двойственными задачами.
На практике наибольшее распространение получили симметричные пары двойственных задач, в которых система ограничений задаётся в виде неравенств и на переменные наложено условие неотрицательности. Таким образом, прямая симметричная задача имеет вид
Двойственная симметричная задача имеет вид
Между решениями прямой и двойственной задач существуют определенные зависимости. Так, если одна из двойственных задач имеет оптимальное решение, то и вторая задача имеет оптимальное решение. При этом
где x*, y* – соответственно оптимальные решения прямой и двойственной задач.
Если же одна из задач неразрешима из-за неограниченности целевой функции, то область допустимых решений второй задачи пуста.
Взаимосвязь прямой и двойственной задач позволяет получить оптимальное решение одной из этих задач из данных симплекс-таблицы для оптимального решения другой задачи. В частности, для симметричных задач между оптимальными решениями прямой и двойственной задач и коэффициентами целевых строк симплекс-таблиц, соответствующих этим решениям, существует следующая взаимосвязь:
где
– соответственно коэффициенты целевой
строки прямой и двойственной задач.
Благодаря этой взаимосвязи можно решить более простую из пары задач, а затем по найденному решению отыскать решение другой задачи.
Задачи
1.9. Составить задачу ЛП, двойственную к задаче
1.10. Пищевой рацион должен содержать не менее 8 единиц вещества А, не менее 10 единиц вещества В, не менее 8 единиц вещества С и не менее 30 единиц вещества D.
Имеется 2 вида продуктов питания: П1 и П2. В единице продукта П1 содержатся 1 единица вещества А, 2 единицы вещества В, 1 единица вещества С и 3 единицы вещества D; в единице продукта П2 содержатся 2 единицы вещества А, 1 единица вещества В, 1 единица вещества С и 5 единиц вещества D. Цена единицы продукта П1 составляет 3 д.е., единицы продукта П2 – 2д.е.
Определить, какое требуется количество продуктов П1 и П2, чтобы обеспечить заданные условия при минимальной стоимости рациона.
Составить математические модели прямой и двойственной задач. Решив симплекс–методом более простую из задач, найти решение поставленной задачи.