9904

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

Реферат

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

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

Русский

2013-03-18

47 KB

45 чел.

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

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

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

Сколько изделий и какой конструкции 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, то есть определять границы изменения этих коэффициентов при изменении условий (например, стоимости, запасов ресурсов и т.п.), то есть заранее знать, изменится или нет оптимальное решение, нужен ли дополнительный анализ, понадобится ли еще раз принимать решение.

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


 

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

16107. Адміністративна діяльність: Навчальний посібник 167 KB
  Забезпечення належного громадського порядку в країні, який відповідав би вимогам сучасного періоду, є однією з важливих функцій держави. У здійсненні цієї функції беруть участь всі державні органи, посадові особи та громадяни. Важлива роль у забезпеченні виконання цієї функції відводиться органам внутрішніх справ, для яких, згідно з їх правовим положенням, громадський порядок в країні - є головне завдання
16108. Кримінальне право України 2.01 MB
  Як самостійна галузь права кримінальне право являє собою сукупність юридично закріплених норм, що визначають загальні принципи, умови і підставу кримінальної відповідальності й покарання, а також встановлюють, які суспільно небезпечні діяння є злочинними і які види та межі покарань застосовуються до осіб, що їх вчинили
16109. Основи адміністративного менеджменту 3.21 MB
  Подано матеріал з основ управлінської діяльності і, зокрема, про особливості адміністративно-державного управління. Розглянуто основні функції управління, питання прийняття стратегічних рішень. Висвітлено систему та сучасний досвід адміністративно-державного управління у країнах з федеральною (Німеччина, США) та унітарною (Франція, Великобританія) формою державного устрою. Розглянуто перспективи формування української школи державного адміністрування.
16110. Комерційне право 2.84 MB
  Книга загострює увагу на найбільш актуальних проблемах підприємництва, спрямована на поєднання в процесі навчання теорії і практики. Практикум містить методичні вказівки для підготовки та проведення занять з курсу «Комерційне право», практичні поради, ситуаційні завдання, основою яких є реальні судові прецеденти...
16111. ОСНОВИ КРИМІНАЛЬНО-ПРАВОВОЇ КВАЛІФІКАЦІЇ 2.72 MB
  Аналізуються загальні положення кримінально-правової кваліфікації - її поняття, підстави та принципи, а також питання кваліфікації окремих типів діянь, передбачених Кримінальним кодексом України - кваліфікації злочинів, з урахуванням стадії їх вчинення, вчинених у співучасті, множинності злочинів тощо.
16112. Історія держави і права зарубіжних країн 1.63 MB
  Держава і право Стародавнього Єгипту. Держава і право Стародавньої Греції. Виникнення і розвиток буржуазної держави і права в Англії. Виникнення і розвиток буржуазної держави і права у Німеччині. Держава і право США.
16113. Житлове право України 1.2 MB
  Мічурін Є.О. Сліпченко С.О. Соболев О.В. Житлове право України Науковопрактичний посібник. Харків: Еспада 2004. С.318. У посібнику розглядаються питання житлового права України характеризуються основні засоби здійснення права на житло що передбачені Конституцією Ук
16114. Господарське законодавство 2.72 MB
  Нормативне регулювання господарських відносин ґрунтується на встановлених Конституцією України основних засадах правопорядку у сфері господарювання, про що згадується в Преамбулі Господарського кодексу України, а в ст. 5 Господарського кодексу цьому питанню приділяється спеціальна увага. Зокрема
16115. Державне управління. Навчальний посібник 1.54 MB
  Навчальний посібник «Державне управління» зорієнтований на освітньо-професійні програми підготовки магістрів державної служби та магістрів за спеціальністю «Адміністративний менеджмент». У посібнику розглядаються основи теорії державного управління, система органів державної влади в Україні, їхні функції та повноваження, напрямки реформування організаційних структур державного управління за Концепцією адміністративної реформи в Україні, основи внутрішньої організації та менеджменту державних органів.