Любую задачу максимизации с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b 1, b 2,…, bn между различными потребителями или некоторыми технологическими процессами A 1, A 2,.., Am.
Рассмотрим пример. Завод производит три вида продукции х 1, х 2 и x 3, каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пусть с 1, с 2 и c 3 - прибыль от реализации единицы соответствующего вида продукции. Требуется определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль:
(1)
при ограничениях
(2)
где a 1 j, a 2 j, a 3 j — время, необходимое для обработки единицы j -го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j = 1, 2, 3);
b 1, b 2, b 3 - недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.
Обозначим за y 1, y 2, y 3 цены единицы времени работы на токарном, фрезерном и сверлильном станках. Тогда можно трактовать как расходы на изготовление единицы продукции вида j.
Предположим, что цены ресурсов y 1, y 2, y 3 выбраны так, что выполняются следующие соотношения:
(3)
Поскольку b 1, b 2, b 3 - использованные ресурсы машинного времени для каждого из станков, то — суммарные расходы на производство.
Требуется найти такие y 1, y 2, y 3, удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:
min g (y 1, y 2, y 3)= , (4)
y 1 ³ 0, y 2 ³ 0, y 3 ³ 0.
Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.
Запишем теперь прямую и двойственную задачи в общем случае. Прямая задача
(5)
при условиях
(6)
. (7)
Двойственная задача
(8)
при условиях
(9)
. (10)
Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи:
1) если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;
2) коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;
3) свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;
4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;
5) если знаки неравенств в ограничениях прямой «£», то в двойственной задаче соответствующие ограничения будут иметь знак «³»;
6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.
Переменные двойственной задачи иногда называют «теневыми ценами».
Рекомендации: Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).
Пример 3. Найдем двойственную задачу для задачи
F = 12x1+3x2 +4x3 → max
Приведем все неравенства к одному виду:
Составим матрицу задачи, записав коэффициенты ограничений в виде строк. В последней строке укажем коэффициенты целевой функции F.
Транспонируем эту матрицу (запишем строки в виде столбцов). Получим матрицу двойственной задачи:
В последней строке находятся коэффициенты целевой функции Z. Так как F→max, Z→min. . Поэтому 1-е и 3-е ограничения двойственной задачи будут в виде неравенств, а 2-е ограничение двойственной задачи – в виде равенства. 1-е и 2-е ограничения исходной задачи заданы в виде неравенств. Поэтому . Получаем
Для этой задачи двойственной будет исходная задача.
Задача 4. Найти двойственную задачу для задачи
F = 5x1+3x2 -x3 → max