Двойственные задачи линейного программирования

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

Прямая задача:

Двойственную задачу по отношению к прямой задаче составляют согласно правилам.

Целевая функция прямой задачи задается на макси­мум, тогда целевая функция двойственной задачи - на минимум, и наоборот.

Матрица

составленная из коэффициентов в системе ограничений прямой задачи, и аналогичная матрица

в двойственной задаче получаются друг из друга транспо­нированием. Число переменных в двойственной задаче (т) равно числу соотношений (ограничений) в прямой задаче, а число ограничений двойственной задачи (п) - числу пе­ременных в прямой задаче.

Коэффициенты при неизвестных в целевой функции двойственной задачи - свободные члены (bi), а правые ча­сти в ограничениях двойственной задачи (с_j) - коэффици­енты при неизвестных в целевой функции прямой задачи.

Если переменная x_j прямой задачи может принимать только положительные значения (х_j≥ 0), то j -еусловие двой­ственной задачи - условие неравенства вида «≥». Если 1-е соотношение в прямой задаче - неравенство, то i -я пере­менная двойственной задачи z_i≥ 0.

Если прямая задача имеет решение, то и двойствен­ная задача тоже имеет решение, причем max(min) L₁= min(max) L₂, поэтому для отыскания оптимума доста­точно решить одну какую-либо из задач двойственной пары. Обычно решают ту, которая проще.

Оптимальный план двойственной задачи позволяет оце­нить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи.

Пример. Для производства изделий А, В, С использу­ются три различных вида ресурсов. Каждый из видов ре­сурсов может быть использован в количестве, соответствен­но не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на ед. продукции и цена ед. продукции каждого вида (табл. 15).

Определить план производства, при котором обеспечи­вается максимальный доход, и оценить дефицитность каж­дого вида ресурсов, используемых для производства про­дукции.

Оценки, приписываемые каждому виду ресурсов, дол­жны быть такими, чтобы оценка всех используемых ресур­сов была минимальной, а суммарная оценка ресурсов на производство единицы продукции каждого вида - не мень­ше цены единицы продукции данного вида.

Решение. Обозначим через х₁ искомый план произ­водства изделий А, через х₂ - В, x₃ - С, а через z ₁- двойственную оценку дефицитности первого вида ресурса, через z₂ - второго, z₃ - третьего.

Таблица 15

Тогда прямая и двойственная задачи формулируются:

· прямая задача

· двойственная задача

Решение прямой задачи дает оптимальный план произ­водства изделий А, В, С, а решение двойственной задачи - оптимальную систему оценок ресурсов, используемых для производства этих изделий:

Исходя из анализа оптимальных двойственных оценок, можно сделать следующие выводы.

Ресурсы первого и третьего видов используются полно­стью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки ,отличные от нуля, т. е. положительные двойственные оценки имеют ресурсы, полностью потребляемые при оптимальном плане производ­ства. Значит, ресурс второго вида недоиспользуется (на 80 ед.).

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

Так, увеличение количества ресурса первого вида на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при кото­ром общий доход возрастает на 5,75 д. е. и станет равным 1340 + 5,75 = 1345,75 д. е. Анализ полученных оптималь­ных значений новой прямой задачи показывает, что это увеличение общего дохода достигается за счет увеличения производства изделий В на 0,625 ед. и сокращения выпус­ка изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.

Точно так же увеличение на 1 ед. количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастёт на 1,25 д. е. и составит 1340 + 1,25 = 1341,25 д. е., что достигается за счет увеличения выпуска изделий С на 0,25 ед, и уменьшения выпуска В на 0,25 ед., причем объем используемого ресур­са, второго вида возрастает на 0,625 ед.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем:

Первое ограничение выполняется как строгое неравен­ство, т. е. двойственная оценка всех ресурсов на производ­ство единицы изделия А выше цены этого изделия и, следо­вательно, выпускать его невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи.

При одновременном изменении ресурсов всех видов на величину можно оценить их суммарное влияние на значение целевой функции (при условии неизменности двойственных оценок в новой двойственной задаче относительно оценок в первоначальной двойственной задаче):

где - величина возможного (при сохранении оптималь­ного плана первоначальной двойственной задачи) измене­ния (увеличения или уменьшения) ресурса i -го вида.

Поиск по сайту: