Пример построения двойственной задачи

Двойственные задачи линейного программирования

Общие правила построения двойственных задач

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

\\\\\\\\\\\

||\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\