Математические основы теории двойственности.

 

Сформулируем правила составления двойственной задачи к стандартной форме записи прямой задачи ЛП.

1. Каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи

 

u₁ ↔ a₁ ₁ x₁ +…+a₁ _jx_j+…+a_1nx_n≤ b₁;

u_i↔ a_i₁ x₁ +…+a_ijx_j+…+a_inx_n≤ b_i

u_m↔ a_m₁ x₁ +…+a_mjx_j+…+a_mnx_n≤ b_m (3.7)

x_j≥ 0; j=1, n

F(x) x=c₁ x₁ +…+c_jx_j+…+c_nx_n→ max

 

 

Каждой переменной исходной задачи ставится в соответствие ограничение двойственной задачи

 

 

x₁ ↔ a₁ ₁ u₁ +…+a_i1u_i+…+a_m₁ u_m ≥ c₁;

x_j↔ a₁ _ju₁ +…+a_iju_i+…+a_mju_m ≥ c_j;

x_n↔ a₁ _nu₁ +…+a_inu_i+…+a_mnu_m ≥ c_n; (3.8)

u_i≥ 0; i=1, m;

Z (u)=b₁ u₁ +…+b_iu_i+…+b_mu_m→ min

2. Левая часть ограничения двойственной задачи (3.8), соответствующая переменной x_j, представляет собой сумму произведений коэффициентов столбца при переменной х_j ограничений прямой задачи (3.7) на соответствующие им двойственные переменные. В качестве правой части этого же ограничения берется коэффициент целевой функции при переменной x _j прямой задачи. Между левой и правой частями ограничения двойственной задачи ставится знак ≥.

3. Граничные условия на переменные двойственной задачи заключается в требовании их не отрицательности u_i≥ 0; i=1, m.

4. Целевая функция двойственной задачи представляет собой сумму произведений правых частей ограничений прямой задачи на соответствующие им двойственные переменные и ориентируется на минимум.

Эти правила можно применить при построении задачи, двойственной к прямой, после ее приведения к нижеприведенной стандартной форме записи задачи линейного программирования.

Найти u=(u₁, …u_i, …, u_m);

-a₁ ₁ u₁ -…-a_i₁ u_i-…-a_m₁ u_m≤ -c₁;

-a₁ _ju₁ -…-a_iju_i-…-a_mju_m≤ -c_j;

-a₁ _nu₁ -…-a_inu_i-…-a_mnu_m≤ -c_n;

u_i≥ 0; i=1, m;

Z (u)’= -b₁ u₁ -…-b_iu_i-…-b_mu_m→ max. (3.9)

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

Это доказывает свойство сопряженности прямой и двойственной задачи, которое заключается в том утверждении, что двойственная задача к двойственной задаче является прямой задачей. В соответствии с этим свойством двойственную задачу можно считать прямой, а прямую задачу - двойственной к ней, т.е. названия «прямая задача» и «двойственная задача» не являются навсегда закрепленными названиями за той или иной задачей линейного программирования. Это оправдывает применяемый в дальнейшем термин «пара взаимодвойственных задач».

Теорема двойственности

Пусть дана пара взаимодвойственных задач линейного программирования (3.7) и (3.8). Относительно этих задач имеет место следующая основная (первая) теорема двойственности.

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

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

F(x) = Z (u).

Следствие основной теоремы двойственности

Допустимое решение задачи (4.2) x*=(x₁ *, …, x_j*, …, x_n*) и допустимое решение задачи (4.2) u*=(u*₁, …, u_i*, …, u_m*) будут оптимальными для своих задач, если выполняется равенство

c₁ x₁ ^*+…+c_jx_j*+…+c_nx_n*= b₁ u₁ *+…+b_iu_i^*+…+b_mu_m*.

Под условиями «дополняющей нежесткости» для задач (3.7) и (3.8) понимаются следующие две группы математических соотношений:

 

u₁ (b₁ -a₁ ₁ x₁ -…-a₁ _jx_j-…-a₁ _nx_n)=0;

u_i(b_i-…a_i₁ x₁ -…-a_ijx_j-…-a_inx_n)=0;

u_m(b_m-…-a_m₁ x₁ -…-a_mjx_j-…-a_mnx_n)=0. (3.10)

x₁ (a₁ ₁ u₁ +…+a_i₁ u_i+…+a_m₁ u_m-c₁ )=0;

x_j(a₁ _ju₁ +…+a_iju_i+-+a_mju_m-c_j)=0

x_n(a₁ _nu₁ +…+a_inu_i+…+a_mnu_m-c_n)=0 (3.11)

Вторая теорема двойственности

Допустимое решение задачи (3.7) x*=(x*₁, …, x_j*, …, x_n*) и допустимое решение задачи (3.8) u*=(u₁ *, …, u_i*, …, u_m*) будут оптимальными для своих задач тогда и только тогда, когда для них выполняются « условия дополняющей нежесткости»(3.10) и (3.11).

Первая группа условий дополняющей нежесткости (3.10) интерпретируется следующим образом.

1а. Если предельная эффективность ресурса под номером i больше нуля, т.е. u_i⁰> 0, то этот ресурс является лимитирующим или, иначе, полностью расходуется по данной оптимальной производственной программе x⁰=(x₁ ⁰, …, x_j⁰, …, x_n⁰), так как должно выполняться равенство

a_i₁ x₁ ⁰+…+a_ijx_j⁰+…+a_inx_n⁰=b

1б. Если ресурс под номером i не является лимитирующим для данной оптимальной производственной программы x⁰=(x₁ ⁰, …, x_j⁰, …, x_n⁰) или иначе, a_i₁ x₁ +…+a_ijx_j⁰+…+a_inx_n⁰< b, то предельная эффективность этого ресурса должна равняться нулю, т.е. u_i⁰=0.

Вторая группа условий дополняющей нежесткости (3.11) интерпретируется следующим образом.

2а. Если продукт под номером j выпускается по оптимальной производственной программе х⁰=(x₁ ⁰,...x_j⁰, …, x_n⁰), т.е. x_j⁰> 0, то суммарная эффективность всех затраченных ресурсов на выпуск единицы этого продукта должна равняться эффективность его реализации (цене продукта)

a₁ u₁ ⁰+…+a_iju_i⁰+…+a_mju_m⁰=c_j

2б. Если суммарная эффективность всех затраченных ресурсов на выпуск единицы продукта под номером j превышает эффективность его реализации, т.е. a₁ u₁+…+a_iju_i⁰+…+a_mju_m⁰> c_j, то продукт по оптимальной программе x⁰=(x₁ ⁰,..., x_j⁰, …x_n⁰) не должен производиться, т.е. x_j⁰=0.

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

 

Составим и найдем решение двойственной задаче к задаче, решенной графическим и симплекс-методом.

Прямая задача:

Найти =(x₁, x₂ ), чтобы

F(x) =16x₁ +14x₂ → max, при

0, 8x₁ +0, 5x₂ ≤ 400

0, 4x₁ +0, 8x₂ ≤ 365

x₁ - x₂ ≤ 100

x₂ ≤ 350

x₁, x₂ ≥ 0

Решение прямой задачи:

x₁ =312, 5кг; x₂ =300кг

F(x) =9200 руб.

При этом первое и втрое ограничение превращается в строгое равенство, а третье и четвертое в строгое неравенство.

 

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

Найти =(u₁, u₂, u₃, u₄ ), чтобы

Z (u) = 400u₁ +365u₂ +100u₃ +350u₄ → min

при 0, 8u₁ +0, 4u₂ +u₃ +0u₄ ≥ 16

0, 5u₁ +0, 8u₂ -u₃ +u₄ ≥ 14

u₁ - u₄ ≥ 0

 

Относительно рассматриваемого варианта задач соответствующие условия “дополняющей нежесткости” первой и второй группы выглядит следующим образом.

 

 

u₁ ↔ (400-0, 8x₁ -0, 5x₂ )=0;

u₂ ↔ (365-0, 4x₁ -0, 8x₂ )=0; (3.12)

u₃↔ (100 - x_{1 +} x₂)= 0;

u₄↔ (350 - x₂ ) =0.

 

x₁ ↔ (0, 8u₁ +0, 4u₂ + u₃ -16)=0; (3.13)

x₂ ↔ (0, 5u₁ +0, 8u₂ -u₃ +u₄ -14)=0;

Из группы условий (3.12), так как 100-312, 5+300=87, 5> 0 и 350-300=50> 0 и на основе интерпретации 1б следует, что ограничения по спросу не лимитируют оптимальную программу, т.е. u₃ =u₄ =0

Из группы условий (3.13) на основе интерпретации 2а следует, что если оба продукта выпускаются по оптимальной программе, т.е. x*₁ =312, 5 и x*₂ =300, то должны выполняться равенства

0, 8u₁ +0, 4u₂ +u₃ =16

0, 5u₁ +0, 8u₂ -u₃ +u₄ =14

Из этих уравнений с учетом u₃ =u₄ =0 перейдем к решению следующей системы

0, 8u₁ +0, 4u₂ =16

0, 5u₁ +0, 8u₂ =14

 

Откуда получаем u ₁ = (16, 36) руб. и u₂ = (7, 27) руб. , при этом

 

Z (u) =400 · +365· =9200 руб. т. е F (x) = Z (u) =9200 руб.

В соответствие с вышесказанным найденное оптимальное решение позволяет уточнить понятие «теневая цена» это не просто цена, по которой мы будем продавать единицу того или иного ресурса. «Теневая цена» - это величина увеличения максимума целевой функции прямой задачи при изменении (увеличение) количества соответствующего ресурса на единицу, т.е.:

u₁ =16, 36 - величина ожидаемого прироста максимума дохода (9200 руб.) от дополнительного вовлечения в производство 1 кг молока к имеющимся 400кг;

u₂ =7, 27 руб.- величина ожидаемого прироста максимума дохода (9200 руб.) от дополнительного вовлечения в производство 1кг наполнителя к имеющимся 365 кг

u₃ =u₄ =0 руб. - величина ожидаемого прироста дохода за счет увеличения спроса (недефицитные) ресурсы.

В связи с этим «теневые цены» (u) в советской и российской литературе называются предельной эффективностью ресурса. Графическое решение двойственной задачи приведено на рис.3.13

 

40 A U2

35

30

25

20

15

10

7.27 B

5 U1

16.36

0 5 10 15 20 25 C30 35 40

Рис. 3.13 Графическое решение двойственной задачи

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

Из первой теоремы двойственности следует, что U = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис

.

 

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

 

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда U = C*A^-1 =

 

Оптимальный план двойственной задачи равен:

u₁ = 16.36

u₂ = 7.27

u₃ = 0

u₄ = 0

Z(U) = 400*16.36+365*7.27+100*0+365*0 = 9200

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: