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

Допустимое решение задачи (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