 |
Понятие двойственности для симметричных задач
|
|
|
|
Сформулируем определение двойственной задачи по отношению к симметричной ЗЛП, состоящей в нахождении максимального значения функции
(13)
при условиях
, (14)
(15)
Задача, состоящая в нахождении минимального значения функции
(16)
, (17)
, (18)
называется двойственной по отношению к задаче (13)-(15), а переменные 
– двойственными оценками.
Задачи (13)-(15) и (16)-(18) образуют пару задач, называемую парой взаимно двойственных задач линейного программирования.
Сравнивая пару двойственных задач (13)-(15) и (16)-(18), можно сформулировать правила, по которым составляется двойственная задача:
1) если в прямой задаче требуется найти максимум целевой функции,
то в двойственной задаче –минимум, и наоборот;
2) коэффициенты 
целевой функции прямой задачи являются сво-
бодными членами системы ограничений двойственной задачи;
3) свободные члены 
системы ограничений прямой задачи являются
коэффициентами целевой функции двойственной задачи;
4) матрицы коэффициентов ограничений прямой и двойственной зада-
чи являются транспонированными друг к другу;
5) если прямая задача решается на максимум, и ее система ограниче-
ний состоит из неравенств типа “£”,то двойственная задача решается на минимум, и ее система ограничений состоит из неравенств
типа “³”;
6) число ограничений прямой задачи равно числу переменных двойст-
венной, а число ограничений двойственной–числу переменных
прямой;
7) все переменные в обеих задачах неотрицательны.
Экономическая интерпретация симметричных
Двойственных задач
Рассмотрим экономическую интерпретацию понятия двойственности на примере задачи оптимального использования сырья.
Пусть на предприятии решили рационально использовать отходы основного производства. Пусть на предприятии имеются отходы сырья 
видов в объемах единиц . Из этих отходов можно наладить выпуск 
видов неосновной продукции. Обозначим через 
норму расхода сырья 
-го вида на единицу продукции 
-го типа 
, через – цену реализации единицы -ой продукции. Неизвестные величины задачи: 
– объемы выпуска -ой продукции, обеспечивающие предприятию максимум выручки.
|
|
|
Математическая модель задачи имеет вид (13)-(15).
Пусть с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность продать их некоторой организации. Необходимо установить оценки (цены) на эти отходы. Обозначим цену единицы отходов сырья каждого вида через 
Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы продавца и покупателя:
1) общую стоимость отходов сырья покупатель стремится минимизи-
ровать;
2) предприятие согласно продать отходы только по таким ценам, при
которых оно получит за них выручку, не меньшую той, что могло бы
получить, организовав собственное производство.
Эти требования приводят к следующей математической модели.
Требование 1 покупателя –минимизация стоимости покупки:
Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если
.
Здесь левая часть означает выручку за сырье, идущее на производство единицы продукции первого вида; правая – цену реализации каждой единицы этой продукции.
Аналогичные рассуждения можно провести в отношении выпуска продукции каждого вида. Так мы получим двойственную задачу
(16)-(18).
Пример.
Предприятие может выпускать четыре вида продукции. Сбыт обеспечен. Для изготовления продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объем ресурсов (в расчете на трудовую неделю), расход каждого ресурса на единицу выпускаемой продукции и прибыль, полученная за единицу продукции, приведены в таблице. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить послеоптимизационный анализ решения и параметров модели.
|
|
|
Решение.
Пусть 
- объемы продукции 
, планируемой к выпуску; 
–сумма выручки. Математическая модель прямой задачи.
при ограничениях
| Ресурсы | Выпускаемая продукция | Объем ресурсов | ||||
| П1 | П2 | П3 | П4 | |||
| Р1 | Трудовые ресурсы, чел-час | |||||
| Р2 | Полуфабрикаты, кг | |||||
| Р3 | Станочное оборудование, станко-час | |||||
| Цена единицы продукции, руб |
Пусть 
–оценка стоимости одного человеко-часа, 
–оценка одного килограмма полуфабриката, 
- оценка стоимости одного станко- часа. Тогда математическая модель двойственной задачи имеет вид:
при ограничениях
|
|
|
