Симметричные двойственные задачи

Каждой ЗЛП можно поставить в соответствие задачу, называемую двойственной к исходной задаче.
Рассмотрим задачу об использовании ресурсов. Предположим, что предприятие А производит n видов продукции, величина выпуска которых определяется переменными x1, x2,…,xn. В производстве используются m различных видов ресурсов, объем которых ограничен величинами b1, b2,…bn. Известны нормы затрат каждого ресурса на единицу каждого вида продукции, образующие матрицу

,
а также стоимость единицы продукции каждого вида c1, c2,…cn. Требуется организовать производство так, чтобы предприятию А была обеспечена максимальная прибыль. Задача сводится к нахождению неотрицательных переменных x1, x2,…,xn, при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигнет максимума. В математической форме задача записывается следующем виде:

L = c1x1 + c2x2 +…+cnxn → max (1)

при условиях (2)
По этим же исходным данным может быть сформулирована другая задача. Предположим, что предприятие В решило закупить все ресурсы, которыми располагает предприятие А. В этом случае предприятию В необходимо установить оптимальные цены на эти ресурсы, исходя из следующих условий:
– общая стоимость ресурсов для предприятия В должна быть минимальной;
– за каждый вид ресурса предприятию А надо уплатить не менее той суммы, которую это предприятие может получить при переработке данного вида ресурса в готовую продукцию.
Если обозначить через y1, y2,…,yn цены, по которым предприятие В покупает ресурсы у предприятия А, то задача сводится к следующему: найти такие значения переменных y1, y2,…,ym, при которых стоимость ресурсов, расходуемых на единицу любого вида продукции не меньше прибыли (цены) за эту единицу продукции, а общая стоимость ресурсов достигает минимума. В математической форме задача записывается в виде:

(3)

при условии (4)
Задачи (1) – (3) и (3) – (4) образуют пару взаимодвойственных задач, любая из которых может рассматриваться как исходная. Решение одной задачи дает оптимальный план производства продукции., решение другой – оптимальную систему оценок сырья, используемого для производства этой продукции.

В матричном виде пара двойственных задач записывается следующим образом:

максимизировать сTx при условиях:
Ax≤b;
x≥0;

минимизировать bTy при условиях:
ATy≥c;
y≥0.

Переменные y1,y2,…,ym двойственной задачи иногда называют теневыми ценами.

Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).

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

  • число переменных одной задачи равно числу ограничений другой задачи;
  • в одной задаче ищется максимум целевой функции, в другой – минимум;
  • коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи;
  • в каждой задаче система ограничений задается в виде неравенств, причем, в задаче на отыскание максимум, все неравенства вида «≤», а в задаче на отыскание минимума, все неравенства вида «≥»;
  • матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;
  • условия неотрицательности переменных сохраняются в обеих задачах.

Пример. По исходной задаче требуется построить двойственную.
Исходная задача: L = 10x1 + 6x2 – 4x3 →min


Приведем все неравенства системы ограничений исходной задачи к одному знаку:


Двойственная задача.


Замечание. В линейном программировании кроме симметричных двойственных пар существуют несимметричные двойственные пары. Эти задачи отличаются от симметричной пары двумя особенностями:
– ограничения задачи выражены уравнениями вместо неравенств;
– в двойственной задаче отсутствуют условия неотрицательности переменных

Решение симметричных двойственных задач

Первая теорема двойственности. Если одна из двойственных задач имеет оптимальное решение, то оптимальное решение имеет и другая задача, при этом значения целевых функций задач равны между собой. Если целевая функция одной из задач не ограничена, то другая задача вообще не имеет решения.
Метод одновременного решения пары двойственных задач.Двойственную пару задач (1) – (2) и (3) – (4) приведем к каноническому виду.
Исходная задача: L = c1x1 + c2x2 +…+ cnxn →min


Двойственная задача:


Число переменных в задачах одинаково и равно m + n. В исходной задаче базисными переменными являются вспомогательные неотрицательные переменные xn+1, xn+2,…,xn+m, а в двойственной задаче – вспомогательные неотрицательные переменные ym+1. ym+2,…, ym+n. Можно показать, что базисным переменным одной задачи соответствуют свободные переменные другой задачи, и наоборот, то есть:


Установив соответствие между переменными пары двойственных задач, и решив одну из них табличным симплексным методом, можно получить решение другой задачи. Значения базисных переменных исходной задачи определяются строкой оптимальной симплексной таблицы двойственной задачи, и, наоборот, значения базисных переменных двойственной задачи определяются строкой оптимальной симплексной таблицы исходной задачи.
Пример 1. Найти решение пары двойственных задач.
Исходная задача: Двойственная задача:
L = 4x1 + 6x2 → max

Решив исходную задачу табличным симплексным методом и учитывая соответствие между базисными и свободными переменными, получим оптимальное решение исходной и двойственной задач.

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x2

2

5

1

0

0

1

x4

3

1

0

1

0

2

x5

-1

2

0

0

1

3

L

-4

-6

0

0

0

0

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x1

1

2,5

0,5

0

0

0,5

x4

0

-6,5

-1,5

1

0

0,5

x5

0

4,5

0,5

0

1

3,5

L

0

4

2

0

0

2


Решение исходной задачи: .
Решение двойственной задачи: .

Пример 2. Для исходной задачи составить двойственную и найти решение пары двойственных задач.

L = 3x1 – x2 + x3 + 9 → max

Приведем данную задачу линейного программирования к виду, допускающему применение симплексного метода. Для этого, используя метод Жордана-Гаусса, приведем ЗЛП к единичному базису.

Баз.

x1

x2

x3

x4

x5

Cвоб.
члены

4

-3

-1

1

1

6

1

4

1

0

1

15

2

-4

-1

-1

0

-3

L

-3

1

-1

0

0

9

Баз.

х1

х2

х3

х4

х5

Cвоб. члены

х5

4

-3

-1

1

1

6

3

-7

-2

1

0

-9

2

-4

-1

1

0

-3

L

-3

1

-1

0

0

9

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x5

1

4

1

0

1

15

x4

3

-7

-2

1

0

-9

-1

3

1

0

0

6

L

-3

1

-1

0

0

9

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x5

2

1

0

0

1

9

x4

1

-1

0

1

0

3

x3

-1

3

1

0

0

6

L

-4

4

0

0

0

15


После преобразований методом Жордана-Гаусса ЗЛП можно записать в виде: L = 4x1 – 4x2 + 15 → max

или

L = 4x1 – 4x2 + 15 → max

Для данной исходной задачи линейного программирования двой­ственная будет иметь вид:


Установим связь между переменными прямой и двойственной задачами


Решим исходную задачу линейного программирования табличным симплексным методом и найдем решение обеих задач. Результирующая таблица Жордана-Гаусса совпадает с исходной симплексной таблицей, определяющей первое допустимое решение Это решение не является оптимальным, поскольку в строке L имеется отрицательная оценка. Используя алгоритм симплексного метода, улучшим данное решение.

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x5

2

1

0

0

1

9

x4

1

-1

0

1

0

3

x3

-1

3

1

0

0

6

L

-4

4

0

0

0

15

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x5

0

1

0

-2

1

3

x1

1

-1

0

1

0

3

x3

0

2

1

1

0

9

L

0

0

0

4

0

27


Результирующая симплексная таблица определяет оптимальное решение, так как в строке L нет отрицательных оценок. Итак, Используя соответствие между переменными прямой и двойственной задачами, найдем решение двойственной задачи
Пример 3.

Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.

L = x1 + x2 → min

В случае нахождения минимума целевой функции система ограничений должна иметь знак «≥». Исходная ЗЛП примет вид:

L = x1 + x2 → min


Соответствующая ей двойственная задача запишется в виде:

Исходную ЗЛП решим двойственным симплексным методом и графическим методом, а двойственную ЗЛП решим табличным симплексным методом и сравним решения.
Для решения исходной задачи двойственным симплексным методом
приведем ее к виду: L – x1 – x2 = 0

Используя алгоритм двойственного симплексного метода, найдем решение исходной ЗЛП.

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x3

1

1

1

0

0

8

x4

-1

1

0

1

0

-4

x5

-1

-2

0

0

1

-6

L

-1

-1

0

0

0

0

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x3

1/2

0

1

0

1/2

5

x4

-3/2

0

0

1

1/2

-7

x2

1/2

1

0

0

-1/2

3

L

-1/2

0

0

0

-1/2

3

Баз.

x1

x2

x3

x4

x5

Cвоб. члены

x3

0

0

1

1/3

2/3

8/3

x1

1

0

0

-2/3

-1/3

14/3

x2

0

1

0

1/3

-1/3

2/3

L

0

0

0

-1/3

-2/3

16/3


Результирующая таблица определяет допустимое оптимальное решение исходной ЗЛП:
Решение двойственной задачи получим из строки L результирующей таблицы с учетом соответствия между переменными исходной и двойственной задач:
Для решения двойственной ЗЛП табличным симплексным методом, приведем ее к виду:


Используя алгоритм табличного симплексного метода, получим решение двойственной задачи.

Баз.

y1

y2

y3

y4

y5

Cвоб. члены

y4

-1

1

1

1

0

1

y5

-1

-1

2

0

1

1

8

-4

-6

0

0

0

Баз.

y1

y2

y3

y4

y5

Cвоб. члены

y2

-1

1

1

1

0

1

y5

-2

0

3

1

1

2

4

0

-2

4

0

4

Баз.

y1

y2

y3

y4

y5

Cвоб. члены

y2

-1/3

1

0

2/3

-1/3

1/3

y3

-2/3

0

1

1/3

1/3

2/3

8/3

0

0

14/3

2/3

16/3


Получили оптимальное решение двойственной ЗЛП: Из последней симплексной таблицы из строки получим решение исходной ЗЛП:
Исходную ЗЛП решим графическим методом.


Найдем координаты точки Amin, решив систему уравнений
Итак, Amin = (14/3; 2/3), L = 16/3.

загрузка...