Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 42
Текст из файла (страница 42)
Здесь Х~О, таккак 0 е .)ь"', дтсюда и"из теоремы 7' при о'=О следует утверждение теоремы 8, причем в качестве искомой точки Л* = (Л,*, Л,") можно взять любую точку Л* е Л, Попутно отметим, что здесь тЬ(Л) = 0 = тгг'=,7„= 7'(0) < 7(*) при всех ш е Х, Л е Л, Л =Л, а равенство (30) вытекает йз принадлежности точки Л* множеству Л.
Теорема 8 доказана. С) Другие теоремы двойственности для задач линейного программирования, их обобщения на случай нелинейных экстремальных задач будут приведены ниже в $4.9, там же будет установлена связь между двоиственными переменными и множителями Лагранжа, объяснены некоторые тайны происхождения двойственных задач. Различные методы решения задач линеиного программирования, основанные на теории двойственности, экономические и игровые интерпретации этой теории, ее приложения к теории линейных неоавенств изложены, например, в [48; 49; 52; 76; 116; 203; 216; 231; 232; 259; 295; 297-299; 330; 356; 373; 470; 586; 612; 620; 670; 719; 746; 747; 750-752; 775; 776).
Упражнения 1. Напишите двойственные задачи к задачам из упражнения 1-4 к 6 6 3, 4 и решите их симплекс-методам, преобразовав их при необходимости к каноническому виду. 2. Напишите двойственные задачи для канонической и основной задач (1,15) и (1.21). Сформулируйте для них аналоги теорем 2-6. 3. Приведите примеры взаимодвойственных задач линейного программирования, в которых множества решений Х„, Л* непусты и, кроме того, 1) оба эти множества состоят из единственной точки; 2) оба содержат более одной точки и ограничены; 3) оба неограничены; 4) одно из ннх состоит из единственной точки, другое ограничено и содержит более одной точки; 5) одно из них состоит из единственной точки, другое неограничено; 6) оба множества содержат более одной точки, но одно из ннх ограничено, другое неограничено. 4.
Приведите примеры взаимодвойственных задач линейного программирования, в которых реализуются случаи, описанные в утверждениях а)-г) теоремы 6. 5. В теореме 4 утверждается, что любые точки х, с Х, Л' е Л' удовлетворяют условию дополняющей нежесткости, т. е. в каждом иэ, произведений (21) хотя бы один из сомножителей (возможно и оба) равны нулю.
Доказать, что можно подобрать такие х„е Х„Л* е Л*, когда в каждом нз произведений (21) лишь один сомножитель обращается в нуль (условие строгой дополняющей нежесткости) (см, [6701), 6. Пусть в задаче (1), (2) Ьг = О, Ьз — — О, и пусть эта задача разрешима. Доказать, что тогда 7(0) = Г, =ф'=О. Указание'. йаписать двойственную задачу и заметить, что гр(Л) жО ЧЛ еЛ, 06 Х.
7. Доказать, что задача (1), (2) разрешима при любых а= (со с ), с, е Бж, г е нач тогда и только тогда, когда множество (2) ограничено. 8. Пусть множества Х, Л определены согласно (2), (12), пусть Х ф ЕГ. Доказать, что тогда совместна одна и только одна из систем; х е Х, 7(х) < а или Л е Л, ф(Л) ) а. Убедиться, что это утверждение равносильно теореме Фаркаша.
У к а з а н и е: пользуясь неравенст. вом (17) и теоремой 7, показать, что зтн системы не могут быть одновременно совместными и одновременно несовместными. 9. Доказать, что совместна одна и только одна из следующих систем: А ~а < О, Азх = О, (с х) < 0 или А ~ Л ~ + АзтЛз+ с = О, Л ~ ) 0 (обозначениЯ см. в теоРеме 8). УбедитьсЯ, что это утверждение равносильйо теореме 8. 10. Донаэать, чта непустое мноэкество (2) неограничено тогда и только тогда, когда существует вектор с е Вгч + 'т, для кото]юго 1п1 (с,х) = -аа. хех 11. Доказать, что множество Х, определенное согласно (2), непусто тогда и только тогда, Ка Где (Ь О Л, ) + ( ЬЗ, Л З) > 0 дЛя ВСЕХ Л Е Л = ( Л = (Л И Л З ); Л ~ Е и аь, Л З Е и "Ч, Л, > О, А ~~ Л ~ + + Аз~~ Лз > О, А~~зЛ, + АзтзЛз — — О).
У к а з а н и е: дла задачи д(Л) = (Ьо Л ~) + (Ьз, Лз) ч 1п(, Л ел написать двойственную задачу и воспользоваться теоремой 7. 12. Пусть множества Х,Л взяты из упражнения 11. Доказать, что тогда совместна одна и только одна из двух систем: х Е Х или Л с Л, (Ьо Л,) -1- (Ьз, Лз) < О. Убедиться, что это утверждение равносильно утверждению из упражнения 11. В следующих упражнениях приведены формулировки ряда важных теорем теории линейных неравенств. Доказательства этих и других важных теорем из упомянутой теории читатель наидет, например, в [48; 54; 752], !3.
Пусть А — матрица размера т х и, Ь е Вх. Доказать, чта совместна одна н только одна иэ двух систем: 1) Ах < Ь или (Ь, Л) < О, А Л = О, Л ) 0 (теорема Александрова — Фана [54, стр. 75]); 2) Ах = Ь нлн АТЛ = О, (Ь, Л) < 0 [54, стр. 55, 74]; 3) Ах=Ь, х>0 или А Л>0, (Ь, Л)<0 (теорема Минковского — Фаркаша, [54, стр. 55, 74]). 14. Пусть А; — матрица размера тз х и, 6; е В, 1 = 1, 2,3; пусть система А~х < Ьп Азх = Ьз совместна.
Доказать, что тогда совместна одна и только одна иэ систем: А~к < 6ы Азх= бе, Азх < Ьз или А~ Л~+ Аз Ля+ Аз Лэ —— 0> (Ь| Л~)+ (Ьз, Лз)+(Ьз Лз) ) О, Л~ )лО Лз >0 ЛзгтО (теорема Мацкина, [54, стр. 78]). 15. Пусть А — матрица размера т х и. Доказать, что совместна одна и только одна из двух систем [54, стр. 79]: 1) Ах =О, х > О, х фО или АТЛ >0 (теорема Гордана); ' 2) Ах = О, х > 0 или А Л )х О, АТЛ ~ 0 (теорема Штимке); 3) Ах<0, х>0, х,~О или А Л >О, Л >0(теорема Вилла); 4) Ах<0, х>ОилиАТЛ)0, АтЛФО, Л>0. 6 1.
ВЫПУКЛЫЕ гАНСОКЕСТВА 149 ГЛАВА 4 Элементы выпуклого анализа 9 1. Выпуклые множества 6 Прежде чем переходить к изложению численных методов решения задач, более сложных, чем задачи линейного программирования, остановимся на элементах выпуклого аналива— области математики, в которой изучаются свойства выпуклых множеств и выпуклых функций, и которая играет фундаментальную роль в теории и методах решения экстремальных задач [5; 14; 15; 34; 48; 49; 54; 61; 83; 84; 106; !33; !86; 191; 204; 209; 225; 233; 264; 265; 278; 286, 295; 297; 314; 3!51 358; 364; 366; 374; 446; 4491 471; 472; 499; 511; 5431 584; 587; 603-605; 613; 6!7; 636; 670; 683; 689; 735; 747; 767; 774; 785; 795; 798; 814].
1. Начнем с рассмотрения конкретных примеров выпуклых множеств. Сначала напомним Определение 1, Множество Х называется аыпуклььн, если для любых и, иЕХ точка и =и+се(и — и)=он+(1 — сг)и принадлежит Х при всех ст, О < гт < 1. Иначе говоря, множество Х выпукло, если отрезок [и, и)=(и: и =исг(и — и), О<от <1), соединягощий любые две точки и, и из Х целиком лежит в Х (рис. 4.1).
Все пространство Е", очевидно, образует выпуклое множество. Пустое множество и множество, состоя- Рис. 4.1 щее из одной точки, удобно считать выпуклыми. Тогда из определения 1 непосредственно следует, что пересечение любого числа выпуклых множеств является выпуклым множеством. Приведем другие примеры выпуклых множеств. Пример 1. Шар Я(ио, гь) = (и; и Е Е", [и — ив[ ( хь) (1) радиуса А > О с центром в точке и является выпуклым множеством. В самом деле, если и, и Е Я(тго, В), то, пользуясь неравенством треугольника, имеем [он+ (1 — п)и — и [= [гх(и — и ) +(1 — сг)(и — и )[< < от[и — и [+(1 — гт)[и — и [< стВ+(1 — гт)Л = В, т.
е. и = сги + (1 — гт )и Е Я(ио, В) для всех сг Е [О, 1[. П р и м е р 2. Напомним, что гиперплоскостью в Е" называется множество Г = Г(с, у) = (ип и Е Е", (с, и) = ~), (2) где с =(с„..., с ) фΠ— вектор из Е", -7 — действительное число. Это множество всегда непусто: если, например, с! ~ О, то точка и с координатами иг =.7/сг, ит =О (7 =1,..., и, у ф ь) удовлетворяет равенству (с, и ) = у, т. е.
и Е Г. Если ио — какая-либо точка из Г, т. е. (с,ио) = 7, то гиперплоскость Г можно представить в виде Г = Г(с, ио) = (и: и Е Е", (с, и — и ) = О). Напоминаем, что два вектора а, 5 е Е" называются оргпогона еьными, если (а, 5) =О. Предыдущее представление для Г означает, что гиперплоскость состоит из тех и только тех точек и, для которых вектор и- и ортогонален вектору с. Вектор с называют нормальным вектором гиперплоскости Г. Возьмем произвольные точки и, и Е Г, т.
е, (с, и) = (с, и) = у. Тогда (с, сти+ + (1 — гг)и) = гт(с, и) + (1 — гт)(с, и) = у при всех гх Е [О, 1]. Следовательно, à — выпуклое множество. П р и м е р 3. Пусть Г = (и: (с, и) = у) — некоторая гиперплоскость, Тогда множества Ге = (ия (с, и) > 7), Г = 1тм! (с, и) < 7) называются олткрьстыми полупространствами, а множества Г = (и: (с, и) > ~), Г = (ьн! (с, и) < 7) называются замкнутыми полупространствами. Нетрудно видеть, что Г+, Г, Г, à — выпуклые множества.
Например, если и, и Е Г+, то (с, сти+ + (1 — гх)и) = ст (с, и) + (1 — а)(с, и) > гт 7+ (1 — а) у = у для всех ст Е [О, 1). П р и м е р 4. Прямая и луч в Е" (см. определение в $2,1) — выпуклые множества. П р и м е р 5. Важным примером выпуклого множества явля!отея аффинные множества (или линейные многообразия), О п р е д е л е н и е 2.
Множество М из Е" называется аффинным, если оы+(1 — гт)и ЕМ при всех и, и ЕМ, гт ЕВ, т. е. прямая, проходящая через любые две точки и, и Е М, целиком лежит в М. Все пространство Е" является аффинным множеством. Пустое множество и множество, состоящее из одной точки, удобно считать аффинными. Любое подпространство пространства Е" представляет собой аффинное множество. Множество М = Ь + и, получаемое сдвигом подпространства Ь на произвольный фиксированный вектор и, также является аффинным, Верно и обратное: всякое аффинное множество М может быть получено сдвигом некоторого подпространства Ь на некоторый вектор и .
В самом деле, возьмем произвольную точку и ЕМ и положим Ь = М-и . Ясно, что Ь вЂ” аффинное множество, причем О Е Ь. Тогда для каждого и Е Ь имеем ом = сти+(1 — ст) ОЕ Ь при всех сг Е В. Кроме того, если и,и Е Ь, то (и+и)/2= и/2+(1 — 1/2)и Е Ь и, следовательно, и+и =2((и+ и)/2) Е Ь. Таким образом, сумма двух векторов из Ь и произведение вектора из Ь на любое число принадлежат Ь, т. е. Ь вЂ” подпространство. Убедимся, что подпространство Ь = М вЂ” и не зависит от выбора точки и Е М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
