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

В математике встречаются ситуации, когда для некоторой задачи (назовем ее I) можно по определенным правилам построить другую задачу II, причем из решения задачи I автоматически вытекает решение задачи II и наоборот. Такие задачи I и II называют двойственными задачами.

Рассмотрим двойственные задачи линейного программирования на примере задачи о распределении ресурсов. Пусть предприятие выпускает несколько видов продукции: А₁, А₂, …, А_n, используя ресурсы: В₁, В₂, …, В_m, причем на изготовление единицы продукции А_j, (j = 1, …, n) требуется a_ij единиц ресурса B_i (i = 1, …, m). Производство обеспечено сырьем B_i в количестве b_i (i = 1, …, m). Стоимость единицы продукции А_j составляет с_j ден.ед. (j = 1, …, n). В качестве исходной задачи I возьмем задачу, изложенную в начале раздела 1.2.

Задача I. Пусть x _j - неизвестное количество продукции А_j (j = 1, …, n). Требуется составить план производства, обеспечивающий наибольшую возможную выручку от продажи выпускаемой продукции. Задача формулируется в стандартной форме

a₁₁x₁+a₁₂x₂+…+a_1nx_n b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n b₂ (1.26)

…

A_m1x₁+a_m2x₂+…+a_mnx_n b_m

 

f = c₁x₁ + c₂x₂ +… + c_nx_n Ì max

x _j ≥ 0, j = 1, …, n.

 

Задача II, двойственнaя к исходной задаче I, состоит в следующем. Каковы должны быть цены (оценки) y ₁, y₂, …, y_m единицы ресурсов каждого типа, чтобы при заданных количествах ресурсов b ₁, b ₂, …, b _m стоимости единицы изделий каждого вида c ₁, c ₂, …, c _n общие затраты Z производства были минимальными.

Сформулируем эту задачу математически. Поскольку стоимость всех ресурсов, затраченных на изготовление единицы изделия каждого вида не может быть меньше стоимости этого изделия, то имеет место следующая система из n неравенств с m неизвестными:

a₁₁y₁+a₂₁y₂+…+a_m1y_m c₁

a₁₂y₁+a₂₂y₂+…+a_m2y_m c₂ (1.27)

………

a_1ny₁+a_2ny₂+…+a_mny_m c_n

 

а общие затраты производства (общая стоимость ресурсов) определяются целевой функцией Z = b ₁ y ₁ + b ₂ y ₂ + … + b _m y _m, (1.28)

где y _j ≥ 0 при всех j = 1,2, …, m (1.29)

Требуется найти такие значения переменных y ₁, y ₂, …, y _m, которые удовлетворяли бы системе ограничений (1.27) и обеспечивали минимум целевой функции Z. Эту задачу в принципе также можно решить симплекс-методом.

Сопоставляя математические формулировки задач I и II, можно обнаружить следующие особенности:

¨ Если в задаче I имеем m неравенств с n неизвестными (система 1.26), то в задаче II имеем m неравенств с n неизвестными (система 1.27); причем знаки неравенств изменяются на противоположные;

¨ Если задача I – задача на максимум целевой функции, то задача II – на минимум другой целевой функции Z;

¨ Коэффициенты a _ij в задаче I описываются матрицей норм затрат ресурсов, а коэффициенты a _ij в задаче II описываются транспонированной матрицей, полученной при перестановке местами строк и столбцов матрицы норм затрат ресурсов.

Рассматриваемую пару задач I и II называют симметричными двойственными задачами, так как система ограничений в них задана неравенствами вида «≤» и «≥» и на переменные x _i и y_j накладывается условие неотрицательности (x _i ≥ 0, i = 1, 2, …, n; y_j ≥ 0, j = 1, 2, …, m).

В теории линейного программирования доказана теорема двойственности, состоящая в том, что если одна из двойственных задач (I или II) имеет оптимальное решение, то и другая задача также имеет оптимальное решение, причем максимум целевой функции f_max прямой задачи и минимум целевой функции Z_min двойственной задачи численно равны, т.е. f_max = Z_min

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

При решении двойственной задачи II для каждого ресурса находят определенное значение условной (теневой) цены единицы этого ресурса: y ₁, y ₂, …, y _m, называемое двойственной оценкой ресурса. Двойственные оценки имеют конкретный экономический смысл и используются при анализе полученных в прямой задаче I оптимальных планов. С их помощью можно:

¨ Выявить степень дефицитности каждого ресурса;

¨ Определить приращение D f целевой функции f при увеличении запаса данного ресурса b _j на одну единицу. При этом используются следующие свойства двойственных оценок y ₁, y ₂, …, y _m.

А) Положительное значение y ₁ могут иметь лишь те виды ресурсов, которые полностью используются при оптимальном плане производства. Оценки ресурса, не полностью используемого в производстве, всегда равны нулю.

Б) Если мы желаем расширить производство, то анализ величин y _j, j = 1, 2, …, m) позволяет выявить «узкие места», сдерживающие рост производства. Если y _j > 0, то соответствующий вид ресурса является дефицитным. Чем больше величина y _j, тем более дефицитным будет соответствующий вид ресурса. Если y_j = 0, то соответствующий вид ресурса, вообще говоря, является избыточным. Т.е. на производстве имеется остаток этого ресурса.

В) Величина y _j, j = 1, 2, …, m для каждого вида ресурса показывает, насколько возросло бы максимальное значение целевой функции f, если бы объем данного ресурса b _j, j = 1, 2, …, m на производстве увеличился бы на единицу. Поэтому величины y _j называют также теневыми ценами ресурсов b _j, j = 1, 2, …, m.

Каждая из задач, прямая и двойственная к ней, являются самостоятельными задачами и могут решаться независимо друг от друга. Достоинством симплексного метода является то, что решение прямой задачи I автоматически приводит к решению и двойственной задачи II.

Решение задачи II, т.е. значения двойственных оценок y ₁, y ₂, …, y_m можно найти непосредственно из последней строки симплекс-таблицы, оптимальной для прямой задачи I. Искомые значения y ₁, y ₂, …, y_m равны элементам, лежащим на пересечении последней строки и столбцов, соответствующих дополнительным переменным.

В качестве примера определим двойственные оценки y ₁, y ₂, y ₃ для ресурсов трех видов и проведем анализ оптимального плана выпуска изделий А и Б для задачи I об использовании сырья, решенной симплексным методом в параграфе 3.

Двойственная задача формулируется следующим образом.

Условия производства описываются системой из n = 2 неравенств с m = 3 неизвестными y ₁, y ₂, y ₃. Система ограничений имеет вид:

(1.30)

Общая стоимость сырья определяется целевой функцией

Z = 400 y ₁+ 900 y ₂+ 600 y ₃ (1.31)

Требуется найти y ₁, y ₂, y ₃, удовлетворяющие системе неравенств (1.30) и обеспечивающие минимум функции (1.31).

При решении прямой задачи I получена оптимальная симплексная таблица 7. В нижней строке этой таблицы для дополнительных переменных x ₃, x ₄, x ₅ находим значения оценок y ₁= 24, y ₂ = 4, y ₃ = 0. Чтобы убедиться в правильности их вычисления, подставим полученные значения y ₁(j = 1, 2, 3) в выражение (1.31) для целевой функции Z

Z_min = 400*24 + 900*4 + 600*0 = 13200 (д. ед.) = f_max

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

Решение двойственной задачи можно истолковать так: сырье 1-го и 2-го видов использовано полностью и имеет положительные оценки (теневые цены) y ₁= 24, y ₂ = 4. Сырье третьего вида использовано не полностью и его оценка y ₃ = 0.

Таким образом, двойственные оценки определяют дефицитность используемого сырья. Величина двойственной оценки показывает, насколько возрастет максимальное значение целевой функции f прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение сырья первого вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства, при котором общая прибыль от реализации f возрастет на 24 (д. ед.). при этом числа в столбце, соответствующем x ₃, в таблице 7 оптимального плана, показывают, что указанное увеличение f может быть достигнуто за счет увеличения выпуска изделий вида А на 4/5 ед. и сокращения выпуска изделий вида В на 3/5 ед. Вследствие этого остатки используемого сырья 3-го вида возрастут на 1 кг. Точно так же увеличение на 1 кг сырья 2-го вида позволит найти такой план, при котором общая прибыль от выпуска изделий возрастет на 4 (д. ед.). Это будет достигнуто за счет увеличения выпуска изделий В на 4/5 ед. и уменьшения выпуска изделий А на 1/5 ед., причем остатки используемого сырья 3-го вида сократятся на 1 кг. При увеличении на 1 кг сырья 3-го вида значение функции f не изменится. Это означает, что сырье третьего вида – недефицитно. На практике сырье каждого вида целесообразно изменять таким образом, чтобы добавочная продукция составляла целое число единиц.

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