9904

Двойственность в линейном программировании

Реферат

Информатика, кибернетика и программирование

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

Русский

2013-03-18

47 KB

46 чел.

Двойственность в линейном программировании

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

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

Сколько изделий и какой конструкции xj (j = 1, …, n) необходимо произвести, чтобы при заданных стоимостях                    cj (j = 1, …, n) единицы продукции и размерах имеющихся ресурсов bi (i = 1, …, m) максимизировать выпуск продукции в стоимостном выражении?

z = c1x1 + c2x2 + … + cnxn  max

xj  0, j = 1, …, n

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

Какие цены yi на единицу каждого из ресурсов нужно назначить при заданных количествах ресурсов bi и величинах стоимости продукции cj, чтобы продать ресурсы было бы не менее выгодно, чем производить продукцию?

f = b1y1 + b2y2  + … + bmym  min

yi  0, i = 1, …, m,


  

Пары двойственных задач

А. Несимметричные

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

                 

              

Б. Симметричные

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

                 

               


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

Теорема 1 (основное неравенство двойственности).

Для любых допустимых планов X прямой и Y двойственной задач их целевые функции z(X) и f(Y) связаны между собой неравенствами:

при минимизации   z(X) z(X)  f(Y),

при максимизации  z(X) z(X)  f(Y),

и не существенно, какая задача прямая, а какая - двойственная.

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

При максимизации z(X):

При минимизации z(X) необходимо записать задачи в соответствующем виде и доказать по аналогии с приведенным доказательством (самостоятельно!).


Теорема 2 (
критерий оптимальности Канторовича).

Если на допустимых планах прямой и двойственной задач ЛП значения целевых функций совпадают, то эти планы являются оптимальными и наоборот, если планы прямой и двойственной задач оптимальны, то значения целевых функций на них совпадают.

Доказательство. (Докажем прямое утверждение)

Пусть X – допустимый план прямой задачи, а Y – допустимый план двойственной задачи и z(X) = f(Y).

Пусть X' – произвольный допустимый план прямой задачи. Тогда по основному неравенству двойственности

z(X')  f(Y), т.е. z(X')  f(Y) = z(X),

т.е. значение целевой функции прямой задачи в точке X является максимальным (т.к. это неравенство выполняется для любого допустимого плана).

Пусть Y' – произвольный допустимый план двойственной задачи. Тогда по основному неравенству двойственности

f(Y')  z(X) = f(Y),

т.е. значение целевой функции двойственной задачи в точке Y является минимальным.

Теорема 3. Для существования оптимального решения как прямой, так и двойственной задачи ЛП необходимо и достаточно существования какого-либо допустимого плана для каждой из них.

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

Необходимость. Оптимальные решения являются допустимыми по определению. Если существуют оптимальные планы, то с очевидностью существуют и допустимые.

Достаточность. Если Y – допустимый план двойственной задачи, то по основному неравенству двойственности для любого допустимого плана X' прямой задачи выполняется z(X')  f(Y).

Т.о., последовательность значений целевой функции прямой задачи z(X1), z(X2), … на различных ее допустимых планах X1, X2, …, полученных симплекс-методом, является неубывающей и ограниченной сверху. Поэтому на допустимых планах X1, X2, … можно выбрать такой план X, для которого z(X')  z(X) при любом X', что доказывает условие достаточности для максимума.

Теорема 4. Если прямая (двойственная) задача имеет оптимальное решение, то и двойственная (прямая) задача имеет оптимальное решение.

Теорема 5. Если прямая (двойственная) задача не имеет решения из-за неограниченности целевой функции на множестве допустимых решений, то система ограничений двойственной (прямой) задачи противоречива.

Теорема 6 (о дополняющей нежесткости)

Необходимым и достаточным условиями оптимальности допустимых планов прямой X и двойственной Y задач является выполнение условий дополняющей нежесткости


Использование двойственности при решении задач ЛП

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

Теория двойственности позволяет также проводить анализ устойчивости решения при изменении коэффициентов cj и bj, то есть определять границы изменения этих коэффициентов при изменении условий (например, стоимости, запасов ресурсов и т.п.), то есть заранее знать, изменится или нет оптимальное решение, нужен ли дополнительный анализ, понадобится ли еще раз принимать решение.

Теория двойственности создана Дж. Фон Нейманом и Л.В. Канторовичем.


 

А также другие работы, которые могут Вас заинтересовать

37468. ФИЛОСОФСКИЕ СКАЗКИ ДЛЯ ОБДУМЫВАЮЩИХ ЖИТЬЕ или Веселая книга о свободе и нравственности 683 KB
  Как называется Истинная правда или Учебник для психолога по жизни . Про Клуб Синтон то есть тоже про жизнь и про психологов то есть про отношение к жизни. Она для повседневности для живого и чувствующего человека с утра до вечера его дня и жизни в привычном окружении близких и далеких для работы и праздников болезней и телевизора. Клуб этот мир созданный мною двенадцать лет назад попрежнему занимает в моей душе и жизни большое место: он много требует но и много дает.
37470. Новый этап в развитии физики рентгеновских лучей 54.26 KB
  Первое что бросается в глаза это следующее. фантастическое увеличение потока информации и все возрастающая узкая специализация приводят к тому что большинство книг представляет собой сборники а не монографии в прямом смысле этого слова. Из них 28 это сборники обзоров такого же типа что и рецензируемая книга. Разумеется в том что такая книга будет неровной будет содержать повторения.
37471. Классики мировой философии о политику, государстве и праве 26.46 KB
  Противопоставление Гераклитом аристократического права и государства справедливым законам за которые люди должны биться как за стены родного города. Четыре свойства государства: мудрость мужество рассудительность справедливость. Структура государства. Разработал теорию возникновения и существования государства ради достижения благой жизни.
37472. Психологическая защита в социуме 968 KB
  Ключникова посвящена теме психологической защиты человека живущего в бурном потоке современного социума. В ней описываются психологические механизмы и законы защищенности человека помогающие человеку стать защищенным и успешным мастером жизни. Книга богато иллюстрированная историями из обширной консультативной практики автора содержит многочисленные советы приемы и методы вдумчивое применение которых сделает человека значительно более уверенным и успешным.Автор развивает и конкретизирует подход суть которого состоит в разумном сочетании...
37473. Гісторыя Беларусі (у кантэксце сусветнай гісторыі) 8.25 MB
  Мандрык Гісторыя Беларусі у кантэксце сусветнай гісторыі Віцебск 2008 УДК 947. 4 Беи 73 Г 46 Друкуецца па рашэнні навуковаметадычнага савета Віцебскага філіяла Установы адукацыі Федэрацыі прафсаюзаў Беларусі âМіжнародны інстытут працоўных і сацыяльных адносінâ. Гісторыя Беларусі у кантэксце сусветнай гісторыі. 4 Беи 73 Г 46 Віцебскі філіял Установы адукацыі Федэрацыі прафсаюзаў Беларусі âМіжнародны інстытут працоўных і сацыяльных адносінâ.