Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 13
Текст из файла (страница 13)
Одна из задач не имеет ни одного допустимого решения, а другая имеет по крайней мере одно допустимое решение, но не имеет оптим льного решения(целевая функция на множестпве допустимых решений неограниченна). 3. Ни одна из пары задач не имеет допустимых решений. Доклзлтвльство. Во-первых, отметим, что утверждения 1, 2, 3 взаимно исключают друг друга. Остается показать, что для любой пары двойственных задач одно из утверждений выполняется. Рассмотрим произвольную пару двойственных задач в форме (с) и построим по ним соответствующую систему неравенств (1), (2), (3). По лемме 3.2 для этой системы имеется по крайней мере одно решение уг )~ О, хг > О, сг > О, для которого выполняются усло- виЯ (4), (5), (6). Есть Две взаимоисключагоЩие возмогкности: 8г > 0 и гв = О.
Рассмотрим каждую из них отдельно. гл, з, двонствкнность 74 т. е. хч и у* — допустимые решения пары двойственных задач. По лемме 3.1 любые допустимые решения прямой и двойственной задач удовлетворяют условию сх > уЬ. Отсюда в силу сх* (у*Ь получаем, что х* и у* являются соответствующими оптимальными решениями прямой и двойственной задач, т. е.
сх* = аип сх = = шах уЬ = у*Ь. Итак, в случае 1з ) 0 каждая из двойственных задач имеет оптимальное решение, и оптимальные значения целевых функций равны. Случай 2а. 4 = — О. После подстановки решения х„ у„ 1, в неравенства (1) и (2) получаем Ахо -=- "0 уо ~) О, (1') (2') уаА- О, хо>0. Предположим, что существуют допустимые решения х и у пары двойственных задач (с), т. е.
Ах>Ь, х>0; уА(с, у.- О. (7) (8) Из условий (1') и (8) имеем Ах, > О, у ) О. Следовательно, уАх,>0. Умножив неравенство уА(с иа х,)0, получим схз> >уАхм Таким ебразои, схо > уАхо) О (9) Из условий Ах>Ь и уз>0 следует, что уеАх > узЪ. Умножая неравенство узА(0 па х>0, имеем узАх(0, откуда 0'= узАх>усЬ. (10) Из условий (9) и (10) следует, что сх, > уеЬ. (11) Случай 2б. 1, = О. Допустим одна из задач двойственной пары имеет допустимое решение, а другая нет. Пусть х — допустимое решение первой задачи из (с), т. е. Ах Ь, х>0.
(12) Но при 1, = 0 условие (6) имеет вид уеЬ вЂ” сх, > О, что противо- речит условию (11). Таким образом, если 1, = О, обе задачи из (с) одновременно но могут иметь допустимых решений, т. е. при т = 0 хотя бы одна из пкх не имеет допустимого решения. Зл. дополняющяя нкжесткость 75 Тогда для любого Л>~0, х+Лх, танке будет допустимым решением, поскольку А (х-)-Лхо) = Ах+ ЛАхо) Ь, где Ахз' з0 в силу (1'). Используя условия (2'), Ах)Ь н уз>0, х)0, получаем 0 ~уоАх.-~у,Ь. (13) 3.2. Дополняющая нежесткость (Данциг и Орден 144]) В этом параграфе будут изучены еще некоторые соотношения между решениями пары двойственных задач линейного программирования. Следующие две теоремы, называемые обычно теоремами о дополняющей нежесткости, устанавливают зти соотношения между прямой и двойственной задачами. Двойственная задача шах уЬ уА(с у)0 Прямая задача пип сх Ах)Ь х)0 Из условий (13) и (б) следует, что О - "уеАх) у,Ь) схю т.
е. сх, отрицательно. Поскольку схе — отрицательная величина, а Л вЂ” любое положительное число, значение с (х + Лх,) = ех + + Лсхз может быть как угодно большим по абсолютной величине отрицательным числом. Поскольку х + Лх, — допустимое решение прямой задачи, целевая функция з пе ограничена снизу.
Подобным лге образом, если допустить существование у, удовлотворяющего уА ( с, можно доказать, что и не ограничена сверху. Итак, если ге = 0 и одна из пары двойственных задач имеет допустимое решение, то утверждение 2 теоремы доказано. Случай 2в. В п. 2а было показано, что при 1з — — 0 хотя бы одна нз задач двойственной пары не имеет решения. Для завершения доказательства теоремы осталось показать, что возможен случай, когда каждая из пары двойственных задач пе имеет допустимых решений. Предоставляем читателю возможность самому построить пример такой пары задач.
° Доказательство теоремы двойственности было приведено для задачи в стандартном виде. Однако, используя преобразования, указанные в гл. 1, можно от стандартного вида перейти к каноническому, и наоборот. гл. г. Двойствкнность Ткогкмл о славой дополняющки нкжксткостн'). Пусть задана пара двойственных задач линейного прогр ммирования в стандартном виде. Для того чтобы допустимые решения х и у прямой и двойственной задач были оптимальными, необходимо и достаточно, чтобы выполнялись следующие соотношения: у[Ах — Ь[=0, [е — уА[х=О. Докдздткльство.
Так как х и у — допустимые решения, то а = у [Ах — Ь[~0, р = [с — уА[ х) О, где а и р суть произведения неотрицательных сомножителей. Более того, а+ р = — уЬ+ ех )О. По теореме двойственности, для того чтобы х и у были оптимальными решениями прямой и двойственной задач, необходимо и достаточно, чтобы — УЬ+ сх = О.гг~ Следовательно, а + р = О, и так как а ) О, [3 ) О, то а = 0 и [) = О.
Теорема доказана. ° Слкдствик о дополняющки нкжксткостн, Дана пара двойственных задач в стандартном виде. Для того чтобы х и у были решениями прямой и двойственной задач, необходимо и достаточно выполнение соотношений (1), (2), (3) и (4), приводимых ниже. Перепишем матричное соотношение у [Ах — Ь[ = 0 в следующей зквивалентной форме: у~[а;х — Ь;[ = 0 (1=1, ..., т), или, что то же самое, если у~)0, то а;х=Ь» и (2) если а~х)Ь» то у;=О. Подобным же образом условие [с — уА[х=О равносильно следующим: если с, ~ уа» то х; = О, (4) если хе~О, то с,=уат» г) Иногда говорят: слабая форма теоремы е дополняющей нежесткостн.— Прим.
ред. З.О. ОРТОГОНАЛЬНОСТЪ РЕШЕНИЙ Соотноше1щя ([) — (4) должны быть справедливыми для любой пары оптимальных решений. Может случиться так, что у; = О и а;х == Ь, одновременно. Следующая теорема подчеркивает, что всегда существует по крайней мере одна пара оптимальных реопений, для которых соотношения у~ —— — О и а;х =- Ь; не могут выполняться одновременно. ТеОРИМА О сильнОЙ дОНОлняющеи нежесткости Пусть для прямой и двойственной задач существуют допустимые решения.
Уезда найдется по крайней мере одна пара оптимальных решений х и у, удовлетвортощоя соотношениям (Ах — Ь) — , 'у"- О, (с — уА)+хт о О. (5) (6) Доклзлтельство. Если обе задачи обладают допустимыми решениями, то параметр о„фигурирующий в утверждении леммы 3.2, положителен, Со ) О.
Разделив неравенства (4), (5) и (6) из утверокдения леммы 3.2 на со и положив х = —" и у =- — ' хо уо оо ~о получим [Ах — Ь! + ут О и [с — уА] -]- хт О. Запишем первое неравенство более подробно: если а;х — Ь;=О„то уо)О; если у; =О, то а;х — Ь;)О. Аналогично для второго неравонства: если с, = уа, то х; ) О; если хе=О, то с, уа,. Эти соотношения должны выполняться по крайней мере для одной нары онтимальньох решений. хо =- ао1х1 + аозхо + .+ ао„хо (то = — з) 3.3.
Ортогональность решений (Танкер [[93]) Запишем стандартный вид прямой и двойствонной задач несколько иным способом. Пусть прямой задачей является следующая: найти максимум гл. г. дВОЙстВеннОсть 78 при условиях х,г =ого +анхо -1-... —;— агпхп)0, хп+ — — а„,+а„,х,+... +а„„х„пО, хг Э:О х„- О. Тогда двойственной задачей будет такая: максимизировать (Уо = нг) уо = — агоуп.н —... — а,упо при условиях У.,„~О, — уг =аог + анупо,+... + атгуп+тк-01 — у„= аоп+ап у ог+ + а~ уп+ч (О Такую форму записи можно представить таблицей, подобной табл. 3.1, где а„= — сн аго — — — Ь| (см.
табл. 3.2). В табл. 3.2 Таблица 2.2 аи *г — хи+ г ап+г Уп+1 Уппо Уп+пг Уо Уг на все переменные х и у, кроме х, и у„наложено требование неотрицательности. Пусть А=(ам) (о=О, 1, У =(г~ Уп+ь Уп-пг~ ° ° ° г у'"'"=(у, у, ", уп), ..., Вг; у = О, 4, ..., Н), Уп+и) ~ 3.3. ОРТОГОНАЛЪНОСТЬ РЕШЕПИЙ (хо| хп»-1> ' 1 хп.нп) (т»-1) х<и+'>=(1, х(, ..., х„), У =(1 Уп+11 ° °, Уп+т, Уо~ У! ° ° ~ Уп), (и»- п+ 2) — » Х (т -<-и+ 2) = (хо хи+1 ° 1 хп+т~ 1» х!1 ° ° ° т хп) ° Отсюда следует, что Ах(и+О = х(т» !>, (1) (2) у<тО()А у<и+!> У< " >Х( " > = ХО+ Х„+1У„+! -1-... + Хп.Нпуи.Нп+ т+и +УО+Х(у<+ ° —,.Х Уп =ХО+ УО+ Х Х<»уо= 3=! т+и = — 2+в)+ ~ хпу3=0.
3=1 (4) если у<т+и+2> и х< +и+2) — допустимые решения, то у„)0 (<3=1, ..., и+т) и хд)0 (к=1, ..., пи.и). Поскольку сумма произведений неотрицательных величин есть величина пеотрицаи+т тельная, ~, хоуо)0. Отсюда, используя (4), получаем 3=1 т+и 2 — и= 2 хоуо)0 или 2)н), и=.! что является утверждением леммы 3.1. ПуетЬ тЕПЕръ у<т+иП2> И Х< Оп+2> — ОПтИМаЛЬНЫЕ рЕШЕНИя. ПЕ- обходимым и достаточным условием етого является по теореме у(т+ИП 2)Х(т+И+2) — у<т+!)Х(т+ 0 ' у(И+ !)Х<п+ !) = у<т+'>Ах<и"> — у<т+!>Ах<и»-!> = О.
(3) Любой вектор х' пи'3» представляет собой ре)пение прямой задачи, если только компоненты удовлетворяют условию (1); если, кроме того, все его компоненты, за исключением, быть МОжЕт, Х„НЕОтрнцатЕЛЬНЫ, тО Х< +и+2> яВЛяЕтСя дОПуСтИМЫМ решением. Подобным же образом, у<т+и+2> представляет собой решенно двойственной задачи, если только его компоненты удовлетворя!от условию (2); зто решение является допустимым, если все компоненты, кроме уо„неотрицательны.
Условие (3) показывает, что каждый вектор х'и+и+", представляющий собой решение (допустимое или нет) прямой задачи, ортогокалеп любому вектору у<т+и+2>, яВЛяЮщомуСя РЕШЕНИЕМ (дОПуСтИМЫМ ИЛИ НЕт) дВОйотВЕН- ной задачи. Распишем условие (3) более подробно: Гл. 3. двойствкнность ДВОйСтВЕННОСтИ РаВЕНСтВО 2= Пг, ИЛИ, УЧИтмзаЯ (4), о!+и х 2 — пг = ~„хдрд = О. д=! Но в силу того, что х! ) О, у; ) О, это условно равносильно следующему: если уд ) О, то хд == 0; если хд ) О, то уд = О, что представляет собой теорему о слабой дополняющей пежесткости. Рассмотрим следую!дай пример: найти максимУм хо (минимУм 2) хо = — х! — х2 — хз (2 = х! + х2 + хз) пря условиях хг = — 1 — х, — хз+ хз)О, хз = — 7+ х! + Хз+ Зхз) О; найти максимум уо (максимум ю) уо = уг + 7уг (пг = уг + 7уо) при условиях — У = — — 1 — у +Уз<0, — у,= — 1+у,+У,~О, — уз = — (+ уг+ Зуд~~О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
