 |
Понятие двойственности для симметричных задач линейного программирования
|
|
|
|
Рассмотрим понятие двойственности на примере задачи о рациональном использовании сырья.
Пусть на некотором предприятии решили рационально использовать отходы основного производства. В плановый период появились отходы m-видов в объемах 
единиц (
. Из этих отходов, учитывая специфику предприятия, можно наладить производство n-видов неосновной продукции.
Обозначим через 
норму расходов сырья i-вида на единицу j-ой продукции. 
- цена единицы j- продукции. Неизвестные величины задачи: 
- объемы выпуска j-продукции, обеспечивающие предприятию максимальную выручку.
Математическая модель задачи:
, (1)
при ограничениях
(
),
, (
).
Предположим с самого начала, при изучении вопроса об использовании отходов основного производства на предприятии, появилась возможность реализации их некоторой организации. Необходимо установить цены на эти отходы. Обозначим цены через 
. Цены должны быть установлены исходя из двух основных условий: 1) общую стоимость сырья покупающая сторона стремится минимизировать; 2) предприятие согласно уступить свою продукции только по таким ценам, при которых оно получит за них выручку не меньшую той, что оно могло бы получить организовав собственное производство.
Математическая модель полученной задачи:
(2)
Переменные 
называются двойственными оценками (теневые цены).
Задачи (1) и (2) называются парой взаимодвойственных задач. Так как они написаны в симметричной форме их называют парой взаимодвойственных симметричных задач.
 ,
при
 ( ),
 ( )
| 
при
 ( )
 ()
|
Сравнивая прямую и двойственную задачи можно установить следующие взаимосвязи:
1. Если прямая задача на максимум, то двойственная на минимум.
|
|
|
2. Коэффициенты 
целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3. Свободные члены 
ограничений прямой задачи, являются коэффициентами целевой функции двойственной задачи.
4. Матрицы ограничений прямой и двойственной задачи являются транспонируемыми друг к другу.
5. Если прямая задача на максимум то ее система ограничений представляется в неравенства типа 
. Двойственная задача решается на минимум и знак ³.
6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной равно числу переменных прямой.
7. Все переменные в обоих задачах не отрицательны.
Пример: Составить симметричную двойственную задачу:
при
Решение:
Исходная задача на максимум, значит двойственная – на минимум. Свободные члены системы ограничений исходной задачи равны 2 и 5. Значит коэффициенты в целевой функции двойственной задачи будут 2 и 5. Коэффициенты в целевой функции прямой задачи – 27, 10, 15, 28. Следовательно эти значения будут свободными членами в системе ограничений двойственной задачи. Таким образом, транспонируя матрицу А, получим:
при
Блок 3
|
|
|
E) тело, размерами которого можно пренебречь в условиях данной задачи
I Приклади розв’язання задач
I ЭТАП. Постановка задачи
I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
I. Цели и задачи учебной дисциплины
I. Цель задачи дисциплины «История государства и права зарубежных стран»
II Анализ задачного материала
II Раздаточный материал из сборника задач по технологии горячей и холодной прокатки стали и сплавов. Протасов А.А. Изд-во «Металлургия» М.1972, 320 с.
II. Задачи работы с классом
II. Типовые задачи.
