.RU

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


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

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

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

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

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

opisivaet-mehanizirovannie-sposobi-rezki-metalla-tipovaya-uchebnaya-programma-obshij-kurs-slesarnogo.html
opit-1-opredelenie-aktivnoj-kislotnosti-i-kolloidnaya-himiya.html
opit-4-opredelenie-velichini-rn-rastvorov-elektrolitov-metodicheskie-ukazaniya-k-laboratornim-rabotam-po-kursu-obshej.html
opit-arhangelska-v-nemecko-rossijskih-proektah-v-oblasti-socialnogo-ugolovnogo-pravosudiya.html
opit-ekspluatacii-gelievogo-zavoda-ooo-gazprom-dobicha-orenburg-kak-strategicheskaya-osnova-dlya-perspektivi-proizvodstva-i-realizacii-geliya-v-rossii.html
opit-formirovaniya-fonda-arendnogo-zhilya-v-chuvashskoj-respublike.html
  • knigi.bystrickaya.ru/sem-lyubimih-sds04-ni039.html
  • notebook.bystrickaya.ru/gosudarstvennaya-politika-v-sfere-truda-v-sovremennoj-rossii-stranica-7.html
  • spur.bystrickaya.ru/kultura-domongolskoj-rusi-1.html
  • znaniya.bystrickaya.ru/programma-xiii-nauchno-prakticheskoj-konferencii-posvyashennoj-50-letiyu-poleta-yu-v-gagarina-v-kosmos-sekciya-anglijskogo-yazika-mhk-muziki-istorii-5-6-klass-i-obzh-kab-31-nanotehnologii.html
  • vospitanie.bystrickaya.ru/www-quality-journal-ru-stranica-14.html
  • lecture.bystrickaya.ru/7-obvineniya-kniga-anglijskogo-uchenogo-m-barbsra-posvyashena-odnomu-iz-samih-skandalnih-sobitij-evropejskoj-istorii.html
  • kolledzh.bystrickaya.ru/5-fakticheskoe-resursnoe-obespechenie-oop-bakalavriata-po-napravleniyu-podgotovki-021300-kartografiya-i-geoinformatika-v-buryatskom-gosudarstvennom-universitete.html
  • nauka.bystrickaya.ru/vipusk-ii-novouralskij-gorodskoj-okrug-stranica-22.html
  • student.bystrickaya.ru/109zakupka-u-edinstvennogo-uchastnika-konkurentnoj-zakupki-planirovanie-zakupok-17-2-sposobi-zakupok-18.html
  • tests.bystrickaya.ru/kursovoj-proekt-po-kursu-sistemi-elektrosnabzheniya-elektrosnabzhenie-zavoda-gornoshahtnogo-oborudovaniya.html
  • prepodavatel.bystrickaya.ru/stati-opublikovannie-v-zhurnalah-iz-perechnya-vak-2009-g.html
  • nauka.bystrickaya.ru/voennoe-obrazovanie-ryunoske-akutagava-slova-pigmeya.html
  • upbringing.bystrickaya.ru/kratkij-slovar-ingredientov.html
  • holiday.bystrickaya.ru/metodicheskie-ukazaniya-k-prakticheskim-zanyatiyam-po-discipline-teoriya-veroyatnostej-matematicheskaya-statistika-i-sluchajnie-processi-dlya-studentov-specialnosti-220400.html
  • occupation.bystrickaya.ru/naimenovanie-znamenatelnih-dat-stranica-3.html
  • esse.bystrickaya.ru/programma-proon-gef-ekologicheskogo-ozdorovleniya-bassejna-dnepra-stranica-6.html
  • credit.bystrickaya.ru/otveti-na-voprosi-viktorini-istoriya-kosmonavtiki-nasha-istoriya.html
  • upbringing.bystrickaya.ru/menshikov-memorial-readings-2011-stranica-8.html
  • nauka.bystrickaya.ru/vibracionnaya-tehnologiya-ustrojstva-podzemnoj-gidroizolirovannoj-chasti-maloetazhnih-zdanij-v-vodonasishennih-gruntah.html
  • znanie.bystrickaya.ru/altajskogo-kraya-po-socialnoj-zashite-naseleniya-i-preodoleniyu-posledstvij.html
  • report.bystrickaya.ru/izdatelstvo-gamilton-diletanti-stranica-6.html
  • laboratornaya.bystrickaya.ru/razdel-4-kontrolnie-voprosi-dlya-ocenki-kachestva-osvoeniya-disciplini.html
  • reading.bystrickaya.ru/metod-broadcast-yazik-broadcast-english-i-zvuko-tekstovie-fajli-interneta-dlya-ego-izucheniya.html
  • portfolio.bystrickaya.ru/podgotovitelnie-kursi-6-mes-3-mes-2-mes-1-mes-kratkosrochnie-letnie-kursi-srokom-na-1-mes-2-nedeli-1-nedelya-po-matematike-i-russkomu-yaziku.html
  • apprentice.bystrickaya.ru/vzaimosvyaz-identichnosti-i-povedeniya-v-internete-polzovatelej-yunosheskogo-vozrasta.html
  • textbook.bystrickaya.ru/hogart-i-anglijskaya-graficheskaya-shkola-xviii-veka-problemi-razvitiya-avtorskoj-i-reprodukcionnoj-gravyuri.html
  • lecture.bystrickaya.ru/61-klassifikaciya-vichislitelnih-setej-uchebnoe-posobie-prednaznacheno-dlya-studentov-ochnoj-i-zaochnoj-form-obucheniya.html
  • esse.bystrickaya.ru/rabochaya-programma-disciplina-proektirovanie-i-soprovozhdenie-buhgalterskih-informacionnih-sistem.html
  • otsenki.bystrickaya.ru/sportivnie-igri-forma-racionalno-organizovannoj-dvigatelnoj-deyatelnosti.html
  • urok.bystrickaya.ru/programma-disciplini-leksikologiya-dlya-studentov-napravleniya-031100-lingvistika-stepen-bakalavr-lingvistiki.html
  • notebook.bystrickaya.ru/hronika-poslednih-vremyon-1959-2000-stranica-5.html
  • writing.bystrickaya.ru/2-den-zavtrak-viezd-na-ekskursiyu-podvig-odessi-v-godi-velikoj-otechestvennoj-vojni.html
  • composition.bystrickaya.ru/plan-doklada-annotaciya-obshaya-harakteristika-uchrezhdeniya-sostav-obuchayushihsya-struktura-upravleniya-personalom.html
  • institut.bystrickaya.ru/strazhdushij-messiya-svyashennoe-pisanie.html
  • credit.bystrickaya.ru/osnovnoe-soderzhanie-dissertacii-istoriya-molodezhnogo-poiskovo-kraevedcheskogo-dvizheniya-v-rossii-v-40-e-nachale-90-h.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.