Пример построения двойственной задачи
Двойственные задачи линейного программирования
Общие правила построения двойственных задач
1. число неизвестных одной задачи равно числу ограничений другой задачи;
2. матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;
3. неравенства в системах ограничений имеют противоположный смысл;
4. свободные члены системы ограничений одной из задач становятся коэффициентами целевой функции другой задачи, коэффициенты целевой функции превращаются в свободные члены ограничений;
5. целевые функции в задачах имеют противоположный смысл: в первой – max, во второй – min.
6. в исходной задаче ограничения неравенства следует записывать со знаком больше или равно, если целевая функция стремиться к минимуму, и со знаком меньше или равно, если целевая функция стремится к максимуму;
7. каждому ограничению неравенства исходной задачи соответствует в двойственной задаче условие неотрицательности переменных yi>=0;
8. каждому условию равенства соответствует переменная yi без ограничения на знак, и наоборот: неотрицательным переменным xk из основной задачи в двойственной задаче соответствуют ограничения неравенства, а неограниченным по знаку переменным соответствуют равенства.
Для любых двойственных задач справедлива следующая теорема (первая теорема двойственности):
Если одна из двойственных задач имеет оптимальное решение, то и другая его имеет. Причем экстремальные значения целевых функций совпадают. Если же в одной задаче целевая функция не ограничена, то двойственная ей задача противоречива.
Пример построения двойственной задачи
Рассмотрим построение взаимодвойственных задач на примере задачи об использовании ресурсов.
Пусть предприятие №1 производит n видов продукции и использует m видов сырья. Известна прибыль получаемая с единицы продукции Cj (в руб.), j =1,n. Известны коэффициенты aij (кг), которые показывают какое количество сырья i-го вида требуется для производства j-го вида продукции (j = 1,n; i = 1,m). Известны запасы сырья (запасы ресурсов) каждого вида - аi (кг). Известны цены каждого вида ресурса (сырья) - ui (руб.)
Запишем в общем виде экономико-математическую модель задачи об использовании ресурсов. Для этого введем переменные xj, j=1,n, которые будут обозначать количество продукции j-го вида.
Тогда целевая функция, определяющая максимум прибыли имеет вид:
Zmax = c1x1 + c2x2 + ...+ cnxn 
xj>=0, j=1,n 
, 
Ограничения на сырье запишутся в следующем виде:
a11x1 + a12x2 + ... +a1nxn <=a1 
a21x1 + a22x2 + ... +a2nxn <=a2 
.
.
.
am1x1 + am2x2 + ... +amnxn <=am 
По этим исходным данным сформулируем задачу предприятию №2.
Допустим, что предприятие №2 решило закупить все ресурсы, которыми располагает предприятие №1. В этом случае предприятию №2 необходимо установить оптимальные цены на эти ресурсы, исходя из следующих условий:
1. общая стоимость ресурсов для предприятия №2 должна быть минимальной;
2. за каждый вид ресурса предприятию №1 надо уплатить не менее той суммы, которое это предприятие может получать при переработке этого ресурса в готовую продукцию.
Обозначим цены, по которым предприятие №2 покупает ресурсы у предприятия №1, через ui, i=1,m.
Запишем экономико-математическую модель для предприятия №2 с учетом сформулированных выше условий:
Lmin = a1u1 + a2u2 + ... + amum 
a11u1 + a21u2 + ... + am1um >=c1 
a12u1 + a22u2 + ... + am2um >=c2 
….
….
….
a1nu1 + a2nu2 + ... + amnum >=cn 
Сравним две построенные математические модели задач:
1. число неизвестных одной задачи равно числу ограничений другой задачи;
2. матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;
3. неравенства в системах ограничений имеют противоположный смысл;
4. свободные члены системы ограничений одной из задач становятся коэффициентами целевой функции другой задачи, коэффициенты целевой функции превращаются в свободные члены ограничений;
5. целевые функции в задачах имеют противоположный смысл: в первой – max, во второй – min.
Задачи линейного программирования, обладающие такими пятью признаками, называются симметричными. Одна из них называется основной, а другая двойственной.
В линейном программировании кроме симметричных двойственных пар существуют не симметричные двойственные пары, которые отличаются от симметричной пары двумя особенностями:
1. ограничения задачи (основной) выражены уравнениями вместо неравенств;
2. в задаче двойственной отсутствуют условия неотрицательности переменных yi, i = 1,m
\\\\\\\\\\\
||\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\