Примеры составления двойственной задачи и нахождения двойственных оценок

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

Пример 12. Фирма выпускает продукцию четырех видов: A, B, C, D, используя для ее производства 3 вида ресурсов: S₁, S₂, S₃.
Исходные данные сведены в таблицу.

Ресурс	Расход сырья на производство 1 ед. продукции	Запасы
A	B	C	D
S1
S2
S3
Стоимость ед. продукции, усл. ед.

Составить план выпуска продукции, обеспечивающий максимальную выручку от реализации в стоимостном выражении.

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

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

Составим двойственную задачу к данной.

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

2 шаг. Поставим в соответствие каждому ограничению (по использованию ресурсов) исходной задачи переменную двойственной задачи. Выпишем матрицу коэффициентов системы ограничений исходной задачи, расширив ее столбцом свободных членов и строкой коэффициентов целевой функции.

3 шаг. Транспонируем матрицу.

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

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

Рассмотрим экономическое содержание двойственной задачи:

Оценим ресурсы, необходимые для изготовления продукции. Обозначим через y_i (i =1,…,3) стоимость единицы i - го ресурса.

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

A: (суммарная стоимость ресурсов, используемых при производстве 1 ед. продукции вида А)

B:

C:

D:

Предположим, что некоторая организация решила закупить ресурсы S₁, S₂, S₃ предприятия и необходимо установить оптимальные цены на эти ресурсы y₁, y₂, y₃. Очевидно, что покупающая организация заинтересована в том, чтобы затраты z на все ресурсы в количествах b₁, b₂, b₃ по ценам y₁, y₂, y₃ были минимальными, т.е. .

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

Запишем математическую модель новой задачи.

Таким образом, двойственная задача заключается в поиске такого набора цен (оценок ресурсов) Y =(y₁, y₂, y₃), при котором общие затраты на ресурсы были бы минимальными, при условии, что суммарная оценка ресурсов, используемых для производства каждого вида продукции была бы не менее цены единицы продукции.

Цены ресурсов y₁, y₂, y₃ называют учетными, неявными или теневыми, т.к. это «условные», ненастоящие цены. В отличие от внешних цен на продукцию, известных до начала производства, цены ресурсов являются внутренними, получающимися в результате решения задачи (они не задаются по условию). Поэтому их называют оценками.

Решим исходную задачу в пакете MS Excel.

Рис. Исходные данные прямой задачи в пакете MS Excel

Рис. Результат решения прямой (исходной) задачи в пакете MS Excel

В результате решения задачи получили, что предприятию целесообразно производить 80 ед. продукции вида В, 120 ед. продукции вида D для того, чтобы получить максимальную выручку от ее продажи, составляющую 920 усл. ед.

Рис. Исходные данные двойственной задачи в пакете MS Excel

Рис. Результат решения двойственной задачи в пакете MS Excel

Пример 12. [12]

Производственное предприятие изготавливает два вида изделия А и В. Потребители продукции готовы приобрести за неделю 100 единиц продукции А по цене 3000 руб за единицу и 50 единиц продукции В по цене 3200 руб за единицу.

Предприятие использует в производственном процессе 9 агрегатов. Структура технологических маршрутов предприятия с длительностью операций представлена на рисунке.

Общий фонд времени работы каждого агрегата за неделю 2400 мин (5 дней по 8 часов).

Для производства единицы изделия А используется два вида исходного сырья: «а» по 600 руб/ед и «б» по 400 руб/ед. Изделие В изготавливается из сырья «б» и «в» по 400 руб/ед.

Необходимо определить максимальную прибыль, которую может получить предприятие за неделю, если объем постоянных расходов составляет 100 тыс. руб.

Рис. Производственная структура предприятия

Составим математическую модель задачи:

Переменные:

x₁ – количество изделий А, производимых за планируемую неделю;

x₂ - количество изделий В, производимых за планируемую неделю.

Целевая функция – прибыль предприятия, рублей за неделю:

f = (3000 - 600 – 400) x ₁+ (3200 – 400 – 400) x ₂– 100000 → max

Ограничения на переменные:

по фонду времени работы каждого агрегата:

агрегат 1: 20 ∙x₁ + 0 ∙x₂ ≤ 2400

агрегат 2: 10 ∙x₁ + 0 ∙x₂ ≤ 2400

агрегат 3: 15 ∙x₁ + 0 ∙x₂ ≤ 2400

агрегат 4: 10 ∙x₁ + 0 ∙x₂ ≤ 2400

агрегат 5: 5 ∙x₁ + 5 ∙x₂ ≤ 2400

агрегат 6: 15 ∙x₁ + 30 ∙x₂ ≤ 2400

агрегат 7: 0 ∙x₁ + 10 ∙x₂ ≤ 2400

агрегат 8: 0 ∙x₁ + 20 ∙x₂ ≤ 2400

агрегат 9: 0 ∙x₁ + 15 ∙x₂ ≤ 2400

ограничения со стороны службы сбыта:

спрос на А: 1∙x₁ + 0 ∙x₂ ≤ 100

спрос на В: 0 ∙x₁ + 1 ∙x₂ ≤ 50

неотрицательность переменных: x ₁ ≥ 0, x ₂ ≥ 0.

Таким образом, математическая модель имеет вид:

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

Составим двойственную задачу к данной.

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

2 шаг. Поставим в соответствие каждому ограничению (по использованию ресурсов) исходной задачи переменную двойственной задачи. Выпишем матрицу коэффициентов системы ограничений исходной задачи, расширив ее столбцом свободных членов и строкой коэффициентов целевой функции.

3 шаг. Транспонируем матрицу.

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

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

=120 y₁+240 y₂+160 y₃+240 y₄+480 y₅+160 y₆+ 240 y₇+ 120 y₈+160 y₉+ 100 y₁₀+ 50 y₁₁

Найдем решение прямой задачи, используя надстройку «Поиск решения» в MS Excel.

Рис. Исходные данные прямой задачи в MS Excel

Рис. Окно поиска решения

Рис. Окно установки параметров поиска решения

Рис. Окно результатов поиска решения

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

Результаты решения двойственной задачи можно увидеть при решении ЗЛП в MS Excel, если заказать отчет по результатам и отчет по устойчивости (они выводятся на отдельные листы).

После того, как запущена работа надстройки Поиск решения, в окне Результаты поиска решения предлагается заказать 3 типа отчета. Щёлкнув по первым двум: Результаты и Устойчивость, можно получить отчет по результатам и по устойчивости. Предварительно, в параметрах Поиска решения необходимо указать, что модель линейная.

Рассмотрим отчет по результатам.

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

В средней таблице – значения изменяемых ячеек в начале (исходное значение) и в конце (результат) – оптимальный план.

В нижней таблице значения левых частей системы ограничений (столбец «Значение»), разница с правыми частями системы ограничений (столбец «Разница») и статус ограничения: «связное» или «не связное», т.е. указываются соответственно дефицитные и недефицитные виды ресурсов, на которые наложены ограничения задачи.

В столбце «Разница» указываются неиспользованные запасы ресурсов. Например, агрегат 1 будет простаивать 400 минут (6 часов 40 минут) в неделю; спрос на изделие В не будет удовлетворен на 20 единиц.

Рассмотрим отчет по устойчивости.

В верхней таблице «Изменяемые ячейки» выводится информация об изменяемых ячейках, т.е. об оптимальном плане:

Результ. значение – оптимальный план.

Нормир. стоимость – значение, на которое уменьшиться целевая функция, если в план принудительно включить производство единицы продукции, отсутствующей в оптимальном плане. Поскольку в данной задаче обе переменные присутствуют в оптимальном плане (≠0), то их нормировочная стоимость равна нулю.

Допустимое увеличение и допустимое уменьшение – интервалы устойчивости для целевого коэффициента, изменение его в этих пределах (при прочих равных) не приведет к изменению оптимального плана. (1Е+30 – символ бесконечности). Например: если бы маржинальная прибыль от изделия А была бы на сколько угодно больше или на 800 рублей меньше (2000-800=1200), то оптимальное значение 100 ед. в плане производства не изменилось бы. Т.е. интервалы устойчивости для коэффициентов целевой функции данной задачи имеют вид:

1200 ≤ с₁≤ ∞

0 < с₂≤ 4000

В нижней таблице «Ограничения» отчета по устойчивости выводятся значения левых частей системы ограничений (столбец «Результ. значение»);

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

,

или .

В данной задаче под запасами ресурсов понимается доступный фонд времени работы всех агрегатов (2400 мин) и величина планируемого спроса на изделия (100 и 50 ед). Эти ограничения выведены здесь в столбце «Ограничение Правая часть»). Например, теневая цена по агрегату 6 равна 80, значит, если бы фонд времени агрегата 6 увеличился бы на 1 минуту, то это бы привело к изменению оптимального плана и принесло дополнительную маржинальную прибыль в 80 рублей.

Теневая цена по спросу на А равна 800 рублей, значит, если бы величина планируемого спроса на изделие А была бы не 100, а 101 единица, то это бы привело к изменению оптимального плана и принесло дополнительную маржинальную прибыль в 800 рублей.

Таким образом, в столбце «Теневые цены» ненулевыми значениями отмечаются, так называемые, «узкие места» как производства, так и отдела сбыта.

Мало того, в двух последних столбцах указаны границы интервалов устойчивости для правых частей системы ограничений, т.е. на сколько можно увеличить или уменьшить запасы ресурса (при прочих равных), от чего его теневая цена не изменится. Например, если фонд времени работы агрегата 6 будет составлять от 2400-900=1300 мин до 2400+600=3000 мин в неделю, то его теневая цена не изменится, т.е. он будет оставаться «узким местом». Чтобы его расширить, нужно фонд времени его работы увеличить как минимум на 601 минуту.

2400-900 ≤ b₆≤ 2400+600.

Пример13. В распоряжении фабрики имеется определенное количество ресурсов: рабочая сила (80 чел./дней), сырье (480 кг), оборудование (130 станко/час). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого вида, и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в табл. 1.

Таблица 1

Ресурсы	Нормы расхода ресурса на единицу изделия	Наличие ресурсов
Ковер «Лужайка»	Ковер «Силуэт»	Ковер «Детский»	Ковер «Дымка»
Труд
Сырье
Оборудование
Доход от реализации ед. изделия (тыс. руб.)

Трубуется:

1. Сформулировать экономико-математическую модель задачи поиска оптимального плана выпуска продукции, при котором доход от ее реализации будет максимальным (условием целочисленности пренебречь).
2. Используя надстройку «Поиск решения» в MS Excel, найти такой план выпуска продукции, при котором доход от ее реализации будет максимальным.
3. Сформулировать экономико-математическую модель двойственной задачи.
4. Используя теоремы двойственности найти оптимальный план двойственной задачи, проверить полученный результат используя отчеты «Поиска решения».
5. Выполнить анализ на чувствительность полученного оптимального решения исходной задачи.
6. Найти интервалы устойчивости для коэффициентов целевой функции и свободных членов системы ограничений.
7. Ответить на следующие вопросы, не прибегая к перерешиванию задачи:

A. Как повлияет на прибыль найм дополнительного рабочего (80 чел/часов)?

B. Как повлияет на прибыль уменьшение запасов сырья на 100 кг?

C. Как повлияет на прибыль введение в производство нового станка, это дополнительно 20 станко/час?

D. Принудительное увеличении выпуска каких видов ковров приведет к снижению прибыли?

E. При каких изменениях показателей дохода от реализации оптимальный план производства ковров будет иным?