Свойства двойственных задач

Любую задачу максимизации с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b ₁, b ₂, …, b_n между различными потребителями или некоторыми технологическими процессами A ₁, A ₂,.., A_m.

Рассмотрим пример. Завод производит три вида продукции х ₁, х ₂ и x ₃, каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пусть с ₁, с ₂ и c ₃ - прибыль от реализации единицы соответствующего вида продукции. Требуется определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль:

(1)

при ограничениях

(2)

где a _{1 j}, a _{2 j}, a _{3 j} — время, необходимое для обработки единицы j -го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j = 1, 2, 3);

b ₁, b ₂, b ₃ - недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.

Обозначим за y ₁, y ₂, y ₃ цены единицы времени работы на токарном, фрезерном и сверлильном станках. Тогда мож­но трактовать как расходы на изготовление единицы продукции вида j.

Предположим, что цены ресурсов y ₁, y ₂, y ₃ выбраны так, что выполняются следующие соотношения:

(3)

Поскольку b ₁, b ₂, b ₃ - использованные ресурсы машинного времени для каждого из станков, то — суммарные расходы на производство.

Требуется найти такие y ₁, y ₂, y ₃, удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:

min g (y ₁, y ₂, y ₃)= , (4)

y ₁ ³ 0, y ₂ ³ 0, y ₃ ³ 0.

Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.

Запишем теперь прямую и двойственную задачи в общем случае. Прямая задача

(5)

при условиях

(6)

. (7)

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

(8)

при условиях

(9)

. (10)

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

1) если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

2) коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

3) свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

5) если знаки неравенств в ограничениях прямой «£», то в двойственной задаче соответствующие ограничения будут иметь знак «³»;

6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

Переменные двойственной задачи иногда называют «теневыми ценами».

Рекомендации: Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).

Пример 3. Найдем двойственную задачу для задачи

F = 12x₁+3x₂ +4x₃ → max

Приведем все неравенства к одному виду:

Составим матрицу задачи, записав коэффициенты ограничений в виде строк. В последней строке укажем коэффициенты целевой функции F.

Транспонируем эту матрицу (запишем строки в виде столбцов). Получим матрицу двойственной задачи:

В последней строке находятся коэффициенты целевой функции Z. Так как F→ max, Z→ min. . Поэтому 1-е и 3-е ограничения двойственной задачи будут в виде неравенств, а 2-е ограничение двойственной задачи – в виде равенства. 1-е и 2-е ограничения исходной задачи заданы в виде неравенств. Поэтому . Получаем

Для найденной задачи двойственной будет исходная задача.

Задача 4. Найти двойственную задачу для задачи

F = 5x₁+3x₂ -x₃ → max

Задача 5 (модель управления запасами)

Пусть С_h – плата за хранение единицы запаса,

D – годовой спрос на изделие,

С₀ – стоимость подачи заказа (расходы, связанные с реализацией),

q – оптимальный размер заказа (заказывается каждый раз, q = const),

– средний объём хранимого запаса.

Издержки: ТС = подача заказов + хранение = .

Найти минимальное значение ТС.

Задача 6.

Годовой спрос D = 1500 единиц, С₀ = 150 руб./заказ, С_h = 45 руб./год, время доставки – 6 дней, 1 год = 300 раб. дней. Найти оптимальный размер заказа, издержки, уровень повторного заказа.

q * = …

TC (q *) = …

За 300 дней реализуется 1500 единиц, следовательно, за 6 дней будет реализовано … единиц. Каждый раз, когда на складе будет оставаться это число единиц товара, будет подаваться заказ на 100 единиц товара (уровень повторного заказа).

Сколько заказов будет подано за год (число циклов = D / q)? …

Расстояние между циклами (1/(D / q))? …

Задача 7.

Годовой спрос D = 400 единиц, С₀ = 40 руб./заказ, С_h = 250 руб./год, время доставки – 6 дней, 1 год = 250 раб. дней. Найти оптимальный размер заказа, издержки, уровень повторного заказа, число циклов за год и расстояние между циклами.

Статические модели макроэкономики (Описание экономики с помощью межотраслевых балансов - МОБ)