Двойственные задачи

С каждой задачей ЛП тесным образом связана, строящаяся определенным образом задача, называемая двойственной по отношению к исходной. Прямая и двойственная к ней задачи удовлетворяют следующим условиям:

· число переменных двойственной задачи равно числу условий ограничений прямой задачи (не считая условий неотрицательности переменных) и наоборот число условий ограничений двойственной задачи равно числу переменных исходной задачи;

· коэффициентами целевой функции двойственной задачи служат свободные члены системы ограничений прямой задачи, а свободными членами системы ограничений двойственной задачи – коэффициенты целевой функции исходной задачи;

· матрицей коэффициентов при переменных двойственной задачи будет транспонированная матрица из коэффициентов при переменных системы ограничений исходной задачи;

· если исходная задача решается на max и ее неравенства приведены к виду ≤ то двойственная к ней задача решается на min и ее неравенства в системе ограничений должны быть вида ≥ (целевая установка);

· каждому i-ому ограничению-неравенству прямой задачи соответствует в двойственной задачи условие неотрицательности i-ой переменной (yi ≥ 0), а ограничению-равенству соответствует переменная без ограничений. И наоборот, неотрицательной переменной прямой задачи соответствует в двойственной задачи k-ое ограничение-неравенство, а произвольной переменной – ограничение-равенство.

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

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

Исх. задача: составить план выпуска продукции, обеспечить ее max выпуск в стоимостном выражении.

Двойственная: какова должна быть цена единицы каждого из ресурсов для минимизации общей стоимости затрат.

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

Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.

Лемма 1. Если Х – некоторый план исходной задачи (43) – (45), a Y – произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е. F(x)≤F*(Y) или j=1Σn CjXj ≤ i=1Σm biyi.

Лемма 2. Если для некоторых планов X* и Y* задач (43) – (45) и (46), (47), то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.

22-23. Симметричные и несимметричные двойственные задачи. Нахождение оптимального решения. Пример.

Пары двойственных задач делятся на симметричные и несимметричные. Если в системе ограничений нет ограничений вида равенства и в обеих задачах нет произвольных переменных, то такая пара задач называется симметричной. В противном случае задачи несимметричны.

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

Z = c₁x₁ + c₂x₂ + … + c_nx_n (max)

x₁x₁ + … + a_nx_n £ b₁

…

a_nx₁ + … + a_mnx_n £ b_m

"x_j ³ 0; j=1,n

a_n … a_m b₁ a_n … am₁ c₁

… …

A am₁…a_mn b_m A^T a_m … a_mn c_n

c₁ … c_n Zmax b₁ … b_m Zmax

T + biyi + … + amiyn (min)

a_ny_i + … a_mj ³ c₁

…

a_iny_i + … + a_mny_n ³ c_n

"y_i ³ 0; i=1,m

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

Далее решают задачу симплекс-методом.

Далее находят решение двойственной задачи по решению исходной.

Если задачи симметричны, то решение двойственной находят по строке D последней симплекс-таблице решенной задачи.

исходные балансовые

x1 x2 x3 x4 x5 x6

y4 y5 y6 y1 y2 y3

D1 D2 D3 D4 D5 D5

Если задачи несимметричны, то решение находят по формуле Y_опт = Сб ´ Вб^-1 где Сб – матрица-строка (вектор) коэффициентов при базовых переменных целевой функции в оптимальном решении исходной задачи, Вб^-1 – обратная матрица матрицы коэффициентов базовых переменных уравнений системы ограничений исходной задачи в оптимальном решении.

24. Теоремы двойственности. Основное неравенство двойственности.

Основное неравенство двойственности.

Пусть имеется пара двойственных задач. Скажем, что для любых допустимых решений X(x₁,…,x_n) и Y(y₁,…,y_n) исходной и двойственной задач справедливо неравенство: Z(x) £ T(y) или

n m

Sc_jx_j £ Sb_iy_i

j=1 i=1

Доказательство:

Умножим обе части неравенств системы ограничений исходной задачи соответственно на переменные и сложив левые и правые части получим неравенство

m n m

Sy_i ´ Sa_ijx_j £Sb_iy_i

i=1 j=1 i=1

Аналогично преобразовав систему ограничений двойственной задачи путем умножения обеих частей неравенства на (x₁,…,x_n) и последующего сложения, получим неравенство

n m n

Sx_j ´ Sa_ijy_i ³ Sc_jx_j

j=1 i=1 j=1

Так как левые части этих неравенств представляют собой одно и то же выражение D, то получаем:

n m

Sc_ijx_i £ D £ Sb_ijy_i

j=1 i=1

Отсюда из свойства транзитивности имеем неравенство

n m

Sc_jx_j £ Sb_iy_i

j=1 i=1

что и требовалось доказать.

Поиск по сайту: