Двойственная задача линейного программирования
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется прямой или исходной. Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому говорят о паре взаимно двойственных задач линейного программирования. Пара симметричных двойственных ЗЛП имеет следующий вид:
Прямая задача:
|
Двойственная задача
|
Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.
Прямая задача: сколько и какой продукции надо произвести, чтобы при заданных объемах имеющихся ресурсов и нормах расходов максимизировать выпуск продукции в стоимостном выражении?
Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных и минимизировать общую оценку затрат на ресурсы?
Для построения двойственной задачи необходимо пользоваться следующими правилами:
Основное неравенство теории двойственности
Для любых допустимых планов и пары двойственных задач справедливо неравенство . Его экономическое содержание состоит в том, что для любого допустимого плана производства и любого допустимого вектора оценок ресурсов общая созданная стоимость не превосходит суммарной оценки ресурсов.
Критерий оптимальности Канторовича (достаточный признак оптимальности)
Если для некоторых допустимых планов и пары двойственных задач выполняется равенство , то и являются оптимальными планами соответствующих задач. Экономический смысл критерия следующий: план производства и вектор оценок ресурсов являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.
Теорема существования оптимальных планов пары двойственных задач
Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существования допустимого плана для каждой из них.
Первая теорема двойственности
Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций совпадают . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукта, полученного в результате реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадения значений целевых функций для соответствующих решений пары двойственных задач достаточно для того, чтобы эти решения были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, то есть равенство общей оценки продукции и ресурсов обусловливает убыточность всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставлять и балансировать затраты и результаты системы.
Связь между задачами двойственной пары глубже, чем указано в формулировке теоремы. Решая симплексным методом одну из них, автоматически получаем решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач и оценок в последней симплексной таблице.
… | … | … | … | ||||
| | | | | | | | | | | | | | | |
… | … | … | … | … | |||
… | … | … | … |
Отсюда имеем оптимальный план двойственной задачи. Если прямая задача решается на максимум, то пользуясь соответствием переменных:
и так далее.
Если прямая задача решается на минимум, то:
и так далее.
Вторая теорема двойственности (о дополняющей нежесткости)
Для того, чтобы планы и пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
Эти условия называются условиями дополняющей нежесткости. Из них следует: если какое-либо неравенство системы ограничений одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю. Если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.
Экономически это означает, что если по некоторому оптимальному плану производства расход i-го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а избыточный ресурс (используемый не полностью) имеет нулевую оценку.
Третья теорема двойственности
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения ЗЛП, то есть:
Выясним экономическое содержание третьей теоремы двойственности. Для этого в последнем выражении дифференциалы заменим приращениями. Получим:
При имеем
То есть двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки часто называют скрытыми, теневыми или маргинальными оценками ресурсов.
Задача 1
Постройте модель двойственной задачи для данной задачи линейного программирования, заданной в произвольной форме.
Решение
Воспользуемся правилами для построения двойственной задачи.Заполним вспомогательную таблицу.
ДЗ/ПЗ | min | СП/ЦФ | |||
-18 | 7 | -12 | -2 | ||
-12 | 16 | -12 | 3 | ||
-11 | 3 | -7 | = | -2 | |
0 | 13 | -12 | -1 | ||
max | = | ||||
ЦФ/СП | -18 | 1 | -3 |
Двойственная задача будет иметь следующий вид:
–любого знака,
Задача 2
Для приведенной ниже задачи записать двойственную. Решить одну из них симплексным методом и получить решение другой.
Решение
Приведем задачу к каноническому виду.
Воспользуемся правилами для построения двойственной задачи.
Двойственная задача будет иметь следующий вид:
Приведем двойственную задачу к каноническому виду.
Заполняем симплексную таблицу 0-й итерации.
БП | Симплексные отношения | ||||||||
5 | 4 | 0 | 0 | 0 | 0 | ||||
0 | 3 | 2 | 3 | 1 | 0 | 0 | 0 | 3/2 | |
0 | 4 | 1 | -2 | 0 | 1 | 0 | 0 | 4 | |
0 | 5 | -1 | 1 | 0 | 0 | 1 | 0 | — | |
0 | 6 | 5 | 4 | 0 | 0 | 0 | 1 | 6/5 | |
0 | -5 | -4 | 0 | 0 | 0 | 0 |
На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение), а также онлайн-помощь на экзамене или зачете. Для этого вам нужно только связаться со мной:
Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту.
Подробное решение получите точно в срок или раньше.
Переходим к таблице 1-й итерации:
БП | Симплексные отношения | ||||||||
5 | 4 | 0 | 0 | 0 | 0 | ||||
0 | 3/5 | 0 | 7/5 | 1 | 0 | 0 | -2/5 | ||
0 | 14/5 | 0 | -14/5 | 0 | 1 | 0 | -1/5 | ||
0 | 31/5 | 0 | 9/5 | 0 | 0 | 1 | 1/5 | ||
5 | 6/5 | 1 | 4/5 | 0 | 0 | 0 | 1/5 | ||
6 | 0 | 0 | 0 | 0 | 0 | 1 |
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Соответствие между переменными исходной и двойственной задачи:
|
|
|
|
|
|
| |
| |
| |
| |
| |
| |
|
|
|
|
|
|
На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования:
Задача 3
Дана задача линейного программирования:
Решение прямой задачи:
Найти оптимальное решение двойственной задачи линейного программирования.
Решение
Исходя из вышеописанных правил построения модели двойственной задачи, двойственная задача будет иметь следующий вид:
Найдем оптимальное решение двойственной задачи:
Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения:
Так как для оптимального решения прямой задачи 3-е и 4-е ограничения выполняются как неравенство, то
Для нахождения значений и , получаем:
Ответ
Решение двойственной задачи: