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

Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...

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

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

2017-10-11 372
Двойственные задачи линейного программирования и их использование. 0.00 из 5.00 0 оценок
Заказать работу

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

Рассмотрим двойственные задачи линейного программирования на примере задачи о распределении ресурсов. Пусть предприятие выпускает несколько видов продукции: А1, А2, …, Аn, используя ресурсы: В1, В2, …, Вm, причем на изготовление единицы продукции Аj, (j = 1, …, n) требуется aij единиц ресурса Bi (i = 1, …, m). Производство обеспечено сырьем Bi в количестве bi (i = 1, …, m). Стоимость единицы продукции Аj составляет сj ден.ед. (j = 1, …, n). В качестве исходной задачи I возьмем задачу, изложенную в начале раздела 1.2.

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

a11x1+a12x2+…+a1nxn b1

a21x1+a22x2+…+a2nxn b2 (1.26)

Am1x1+am2x2+…+amnxn bm

 

f = c1x1 + c2x2 +… + cnxn Ì max

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

 

Задача II, двойственнaя к исходной задаче I, состоит в следующем. Каковы должны быть цены (оценки) y 1, y2, …, ym единицы ресурсов каждого типа, чтобы при заданных количествах ресурсов b 1, b 2, …, b m стоимости единицы изделий каждого вида c 1, c 2, …, c n общие затраты Z производства были минимальными.

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

a11y1+a21y2+…+am1ym c1

a12y1+a22y2+…+am2ym c2 (1.27)

………

a1ny1+a2ny2+…+amnym cn

 

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

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

Требуется найти такие значения переменных y 1, y 2, …, 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 и yj накладывается условие неотрицательности (x i ≥ 0, i = 1, 2, …, n; yj ≥ 0, j = 1, 2, …, m).

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

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

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

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

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

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

Б) Если мы желаем расширить производство, то анализ величин y j, j = 1, 2, …, m) позволяет выявить «узкие места», сдерживающие рост производства. Если y j > 0, то соответствующий вид ресурса является дефицитным. Чем больше величина y j, тем более дефицитным будет соответствующий вид ресурса. Если yj = 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 1, y 2, …, ym можно найти непосредственно из последней строки симплекс-таблицы, оптимальной для прямой задачи I. Искомые значения y 1, y 2, …, ym равны элементам, лежащим на пересечении последней строки и столбцов, соответствующих дополнительным переменным.

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

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

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

(1.30)

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

Z = 400 y 1+ 900 y 2+ 600 y 3 (1.31)

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

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

Zmin = 400*24 + 900*4 + 600*0 = 13200 (д. ед.) = fmax

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

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

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

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

 


Поделиться с друзьями:

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.019 с.