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

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

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

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

2. Все неравенства системы ограничений приводятся к одному виду: если в исходной задаче ищут максимум целевой функции, то все неравенства системы приводятся к виду «≤», а если минимум - к виду «≥», для этого неравенства, не удовлетворяющие требованиям, умножают на (- 1).

3. Составляется расширенная матрица А, в которую включают матрицу коэффициентов при переменных, столбец правых частей исходной системы ограничений и строку коэффициентов при переменных в целевой функции. Определяется матрица А', транспонированная к матрице А:

® .

4. На основании полученной матрицы А' формируется двойственная задача и условия неотрицательности переменных (таблица 2.11).

Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. Коэффициенты при переменных в целевой функции двойственной задачи - свободные члены (b_i), а правые части в ограничениях двойственной задачи (с_j) - коэффициенты при переменных в целевой функции прямой задачи. Знаки неравенств меняются на противоположные. Условие неотрицательности переменных имеется в обеих задачах.

Таблица 3.5

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

Если задача ЛП содержит ограничения в форме равенств, ограничениями двойственной задачи будут неравенства:

- если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства «≥», если максимум, то «≤»;

- переменные у_i - произвольные по знаку, т.е. могут принимать как положительные, так и отрицательные значения.

Если прямая задача имеет решение, то и двойственная задача тоже имеет решение, причем , поэтому для отыскания оптимума достаточно решить одну какую-либо из задач двойственной пары.

Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых планов, то система ограничений другой задачи противоречива.

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

Оптимальный план двойственной задачи позволяет оценить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи. Дефицитный ресурс (полностью использованный в производстве) имеет положительную оценку (y_i ^*>0), a ресурс недефицитный (избыточный) имеет нулевую оценку(y_i ^*= 0). Величина двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества соответствующего ресурса на единицу.

При одновременном изменении ресурсов всех видов на величину Db_i (i =1, …, m) можно оценить их суммарное влияние на значение целевой функции:

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

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

Пример. Для производства четырех видов продукции П₁, П₂, П₃, П₄ используются три вида ресурсов. Затраты каждого из видов ресурсов на ед. продукции, запасы ресурсов и прибыль, получаемая с ед. продукции каждого вида, приведены в таблице 3.6. Определить план производства, при котором обеспечивается максимальная прибыль.

Таблица 3.6

Ресурсы	Норма расхода ресурса на ед. продукции	Запас ресурса
П1	П2	П3	П4
Трудовые
Сырье
Оборудование
Прибыль					-

Обозначим через х₁ план производства продукции П₁, х₂ - продукции П₂, х₃ - продукции П₃, х₄ - продукции П₄.

Математическая модель задачи:

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

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

Решение. Обозначим через y₁ - двойственную оценку дефицитности трудовых ресурсов, через y₂ – ресурсов сырья, y₃ - оборудования. Тогда прямая и двойственная задачи формулируются:

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

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

Решение прямой задачи дает оптимальный план производства продукции П₁, П₂, П₃, П₄, а решение двойственной задачи - оптимальную систему оценок ресурсов, используемых для производства этой продукции:

Двойственные оценки ресурсов y_i ^* – это оценочные коэффициенты D_j дополнительных переменных х₅, х₆, х₇ в последней симплексной таблице (таблица 3.7).

Таблица 3.7

ci	БП								bi
x1	x2	x3	x4	x5	x6	x7
	x1		2/3		- 1/2	5/3		- 1/6
	x6		- 1/3			- 22/3		1/3
	x3		1/3		3/2	- 2/3		1/6
Dj

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

Трудовые ресурсы и оборудование используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки y₁, y₃, отличные от нуля. Значит, ресурсы сырья недоиспользуются (на х₆ =26 ед.).

Увеличение количества трудовых ресурсов на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства продукции, при котором общая прибыль возрастет на 20 д. е. и станет равной 1320 + 20 = 1340 д. е. Анализ полученных оптимальных значений новой прямой задачи показывает, что это увеличение общей прибыли достигается за счет увеличения производства продукции П₁ на 1,67 ед. (5/3) и сокращения выпуска продукции П₃ на 0,67 ед. (2/3) (таблица 2.9). Вследствие этого использование ресурса сырья увеличивается на 7,33 ед. (22/3).

Точно так же увеличение на 1 ед. количества оборудования позволит перейти к новому оптимальному плану производства, при котором прибыль возрастет на 10 д. е. и составит 1330 д. е., что достигается за счет уменьшения выпуска продукции П₁ на 0,17 ед. и увеличения выпуска продукции П₃ на 0,17 ед., причем объем используемого ресурса сырья уменьшается на 0,33 ед.

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

Второе и четвертое ограничения выполняются как строгие неравенства, т. е. двойственные оценки всех ресурсов на производство единицы продукции П₂ и П₄ выше цены этих видов продукции и, следовательно, выпускать их невыгодно. Их производство и не предусмотрено оптимальным планом прямой задачи.

Дата добавления: 2014-10-22