Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





 

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

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

 

u₁↔a₁₁x₁+…+a₁jxj+…+a1nxn≤b1;

ui↔ai₁x₁+…+aijxj+…+ainxn≤bi

um↔am₁x₁+…+amjxj+…+amnxn≤bm (3.7)

xj≥0; j=1, n

F(x) x=c₁x₁+…+cjxj+…+cnxn→max

 

 

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

 

 

x₁↔a₁₁u₁+…+ai1ui+…+am₁um ≥ c₁;

xj↔a₁ju₁+…+aijui+…+amjum ≥ cj;

xn↔a₁nu₁+…+ainui+…+amnum ≥ cn; (3.8)

ui≥0; i=1, m;

Z (u)=b₁u₁+…+biui+…+bmum→min

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

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

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

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

Найти u=(u₁,…ui,…,um);

-a₁₁u₁-…-ai₁ui-…-am₁um≤-c₁;

-a₁ju₁-…-aijui-…-amjum≤-cj;

-a₁nu₁-…-ainui-…-amnum≤-cn;

ui≥0; i=1,m;

Z (u)’= -b₁u₁-…-biui-…-bmum→max. (3.9)

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

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

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

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

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

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

F(x) = Z (u).

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

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

c₁x₁*+…+cjxj*+…+cnxn*= b₁u₁*+…+biui*+…+bmum*.

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

 

 

u₁(b₁-a₁₁x₁-…-a₁jxj-…-a₁nxn)=0;

ui(bi-…ai₁x₁-…-aijxj-…-ainxn)=0;

um(bm-…-am₁x₁-…-amjxj-…-amnxn)=0. (3.10)

x₁(a₁₁u₁+…+ai₁ui+…+am₁um-c₁)=0;

xj(a₁ju₁+…+aijui+-+amjum-cj)=0

xn(a₁nu₁+…+ainui+…+amnum-cn)=0 (3.11)

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

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

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

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

ai₁x₁0+…+aijxj0+…+ainxn0=b

1б. Если ресурс под номером i не является лимитирующим для данной оптимальной производственной программы x0=(x₁0,…,xj0,…,xn0) или иначе, ai₁x₁+…+aijxj0+…+ainxn0<b, то предельная эффективность этого ресурса должна равняться нулю, т.е. ui0=0.

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

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

a₁u₁0+…+aijui0+…+amjum0=cj

2б. Если суммарная эффективность всех затраченных ресурсов на выпуск единицы продукта под номером j превышает эффективность его реализации, т.е. a₁u1+…+aijui0+…+amjum0>cj, то продукт по оптимальной программе x0=(x₁0,...,xj0,…xn0) не должен производиться, т.е. xj0=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)

u3↔(100 - x1 + x2)= 0;

u4↔(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) в советской и российской литературе называются предельной эффективностью ресурса.

 







ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.