Галеев Э.М. - Оптимизация (теория, примеры, задачи)

Э. М.ГалеевОПТИМИЗАЦИЯтеорияадпримерызадачиаКнигарекомендованаСоветомнаучно-методическимпоматематикеиУМОмеханикеуниверситетовФедерацииРоссийскойМосква•200222.318ББК22.18я73,МихайловичЭльфатГалеевОптимизация:базефакультететеория,УРСС,2002.I&ВN5-354-00204-4КнигапосвященапреподаванияМГУ.ВважнейшимосновеикурсыследующихэтихисчисленияВанализа.примерырешенияконтрольныхиуправления.частирешениядляДаетсяизу-функциональноготеоретическойзадачизаданий.Дляэкстремума.элементыпослепредлагаютсядомашнихзадач:оптимальногодаютсяпараграфекаждомзадач,дляиусловияобъемеГалеевым.экстремальныхпрограммирова-достаточныеинеобходимомвразделоввыпуклоготеорииматематическоготакМ.Э.прочитанныеразделоввариационногонеобходимые,какнапостроенафакуль-спецкурсы,иОнаоптимизации.механико-математическомнапрограммирования,программирования, классическогоПриводятсяприводятсялежатеевыпуклогоиизученияпроблемамоптамизациифрагментылинейногоЕдиториалМ.:—с.теорииРассматриваютсяпособие.Учебноезадачи:примеры,304-наобщихобзорпривосеминарах,методовтеорииэкстремума.Длястудентоввузоваматематика»,такжеИздательствоN5175ФорматОтпечатаноотТиражв960ОООтипографиипреподавателей117312,г.г.ПодписаноПеч.экз.«Рохос».л.иМосква,19.117312,60-летия02.09.2002пр-тпечатик№Зак.г.«Прикладнаяработников.научныхОктября,9.г.49.Москва,60-летияпр-тОктября,9.IБИБЛИОТЕКА"ИЗДАТЕЛЬСТВОНАУЧНОЙИ УЧЕБНОЙигез@игез.гиКаталогизданий1пЫтвкТел./факс:Тел./факс:"ш15В14шЛИТЕРАТУРЫЕ-тай:в«Математика»,специальностямУРСС».25.06.2001«ЕциториалИД60x90/16.Лицензия1поаспирантов,для№р:/ иг$з.ги7 @95)7 @95)135-44-23>Э.135-42-46>ЕдиториалМ.1Галеев,2002УРСС,БИБЛИОТЕКА2002IПредисловиеЗадачиявляютсянанаибольшихотысканиеактуальнымиОсобенноенаиболееважностьбогатств,людскихресурсов,приводитэтооптимальноеПервыекакивека,включаявНьютон,Лейбниц,Эйлер,иполноценноеНейман,фонмыслитьневозможновремябезобразованиематематическоеФерма,какПуанкаре,нашедней,нашихтакихЛагранж,Вдругих.началевдоматематиков,ре-зарождаласьвплотькрупнейшихисоздаватьсяначалазадачразвиваласьБернулли,говорят,поставленытолькоматематикаактивноПонтрягинбылиминимумикогдаорбитусвоюКанторович,себемаксимумонаили,каквопроса.экстремальныхзатемВсесредств.наилучшее,иногодревности,Теориянаука.XVIIназадачиглубокойвилитогоприродныхфинансовыхивоз-когдавремя,использованияотыскиватьрешениерешенынастоящеевматериальныхнеобходимостикчеловечества.развитияисторииприобретаютэффективногоонизначениевозрастаетявляют-величиннаименьшихивсейпротяжениинаэлементовтеорииэкстремума.МонографияпереизданиемпятиТихомировВ.2000.Книгаметодампо«Оптимизация:состоитизиМ.—управление».М.курсВ.С.лекцийнекоторыхбылинсти-разработанмеханико-математическогоэтапеТихомирова,втакжесформировалсяусилиямиПриФомина.написаниикнигиопубликованныхранеесодержащийсяСВ.«ОптимальноеФоминВ.М.,В.М.,ТихомировВ.

М.,ГалеевАлексеевМ.:1979;Наука,[АГТ]В. М.поМ.:задачоптимизации».Наука,«СборникВ. М.Э. М.,ГалеевтеориикурсТихомиров«КраткийМ.:является1989.КнигаИзд-возадач».МГУ,расширеннымЭ. М.пособияпоГалеевалекцийвариационному«КурсиМ.:мехматаИзд-воМГУ,оптимальномууправлению».в—экстремальныхвариантомисчислениюпредназначеналюбогочертежикнигах:Алексеев—Тихомировэкстремумапрофессоровматериал,[АТФ]Всеаначальномуслови-пофакультетекурснаспецкурсатакжеуниверситета,В.Алексеева,амеханико-математическомДанныйпрофиля.ипреподавателейМГУ,использовалсяОнапорядкалекцийкурсаоптимальномугосударственногорядомфакультетаматериалМ.,УРСС,М.:задачи».содержатЭ.Галеевкнигипрограммированию,наестественнонаучногоцелым[ГТ]глав.исчислению,второгопереизда-расширеннымпримеры,теория,ОнилинейномувариационномуэкстремумаМосковскогоВ.5оптимизации,управлениюиТанеевым,написанныхглав,М.условияминститутахпереработаннымявляетсяпервыхдляиуровнявЬАТЕХ'еэлементывключающихкурсов,приспособлена2еквыполненытеориидействующимТанеевойнынеАльфирой.экстрему-программам.Э.М.,1984;экстреисчи-1996.4ПредисловиеРассматриваютсяследующиебеззадачиограничений,линейноенеравенств,иоптимальноеПриданныхизучениииэкстрему-условиячитателитребуетсяалгебры,сэлементарными(умножением,остальныедифференциработынавыкамикурсевсма-обратной).нахождениемтранспонированием,используемыекурсахдифференцированияпростейшиеэлементарнымисдвухПредполагается,решатьумеютзнакомыматематиче-первыхприемамифункций,уравнения,науниверситетов.вузов,знакомыосновзнаниеизучаемыхпедагогическихинтегрированияматрицамиВсеисчисление,достаточныеиразделовлинейнойитехническихдифференциальныезадач:равенствтипаисчислении.анализачтоэкстремальныхвариационноенеобходимыевариационномматематическоготеорииограничениямисзадачипрограммирование,управление,экстремума виразделыгладкиематематическиеподробнопонятияопределяются.Впервойтипасоответствующихнормаляхозадачглавнымизэлементыуровнявнормированныхпространствах,Внормированныхпостановкирешенияобоснованиенорми-вкпрограммированияОсновнаяметодамизадачрешенияэтихобоснованияметодов.подобныхрешениясоздатьпокрайнейметодизадачамвдальнейшемирешенияболеебылообоснование.егоглубокорешенийпонятьме-обо-чтобыобразом,такимсуществованияназначении.проведениеивозможнопровестиоимеющимисяспроводитсяприлинейногозадачпрограммированияОбоснованиетеоремыпозволяющиенавыкитипамстудентовлинейногозатемметодоврядПолученныеточки.задачамзадачдоказательстваприводят-двойственности,даетсяознакомление—вна-правилосимплекс-методу,известнымтранспортнымэтомприцельнейпрограммирования,понятиенаиболеенекоторым—Впрограммированию.симплекс-метода,первоначальнойнахожденияприменяютсядвойственности,элементынекоторыеисчисленияВводитсяпримеры.строгоеприведеныдаютсяформеканоническойрешениямисамостоятельноглавелинейногозадачвзадачпроводитсядляжелинейномупосвященаглавадаютсяснормировандоказываетсяидифференциальногоирассматриватьсяпространствах.ВтораяприводятсяможетсубдифференциалаэтойанализазависимостивлинейныхвиДают-задачам.анализчитателяпонятиеКуна—Таккера.функциональногоформывыпуклымвыпуклыйтаквводитсятеоремаквадратичнойуделяетсяпространствах,за-экстремальныхприведенииподготовкиконечномерныхзадачастариннаятеориипричемсоответ-решенияявляетсяоанализа,математическойотвначалеалгебрывниманиевыпуклогокакпримеровприводятсяне-инормированныхвиМетодамикурсаБольшоеосям.Даютсяизэллипсу.кзадачарешаетсязадачОднимпримеров.Аполлониятипазадачиравенствтипапеременныхпкаждогоограничений,ограничениямифункцийДляпространствах.беззадачисравенств,числовыхдлянеравенствкрассматриваютсяглавеограничениямисданныйбысамосто-Впособииитеоремыкурс.5ПредисловиеВ третьейклассическогоглавеприводятсяпростейшаяВсезадача.изопериметрическаяболееобшейэтирассматриваютсясзадачазадача,являютсязадачиКакЛагранжа.задачиэлементарныеследующиеисчисления:вариационногоподвижнымикласси-Больца,случаемчастнымслучайчастныйзадачизадачаиконцамиЛагранжазадачисозадачастаршимипроизводными.ВчетвертойПонтрягинасоглавеПриводитсяуправления.общемвсвободнымВпятойРешаютсяиглавепростейшейБольца.рядпринципадоказательствозадачнеобходимыезадачидлязадачаобыстродействии,управления.оптимальногоусловиядостаточныеиклассическогомаксимумамаксимумапринципатакжепростейшаядругихданызадачеваслучае,концом.Ньютоназадачаиуправле-оптимальногозадачирассматриваютсяформулировкаэкстремумаисчислениявариационногоиГалеевАвторВ.благодаритрешениюзадачкурсовоптимизации.наэкстремумМ.Тихомирова,икоторыйувнескоторогоогромныйучилсявкладЭ.итеориивзадачеразработкуМ.ре-ВведениеТеориюназадачтеориейназываютСловотах1титкакзадачиЗаписьзадачина}(х)ПоэтомувЗадачизадачинадолжнырешитьнаминимум,}(х)гдезадачдлятеорембудем-}(х),=ограничиватьсяформулируются,которойвкакАвозникают.ониДлячтобытого,необходимосредствами,математическогоязыкзадачеиногдаанализа.этимиктш,изначальноминимумиматематическогосредствамивоспользоваться-+мыобласти,тойязыкенаправило,мыминимум.намаксимумначтоформулировкикогдаразличны,задачирассмотрением}(х)случаях,техмаксимумиминимумсвестиможнозадачейтах-+означает,максимум.навсегдамаксимумнаех1г—+задачуизадачунаоборот./(х)видевминимум,Задачузаменивихтеориейназываютзадач.задачунаввелизучаюткоторомвминимум,и«экстремум»,«минимум»,ианализа,разделмаксимумнаСлово«максимум»Ныне—«экстремум»словом«крайнее»).понятиятШтитсловообъединяютсяозначающегоДюбуа-Реймон.экстремальныхивеличин«наибольшее»,означаетпонятияобъединяющийтермин,употреблениеразнообразныевилатыниэтихех(гетит,латинскогонаименьшихизадач.поОба«наименьшее».(отнаибольшихотысканиеэкстремальныхбыломожноформулировкуперевестиТакойанализа.исследуютназываетсяпереводформализацией.В общемэкстремумопределеннойнаКраткоформализованнаявиденайтиXфункциих€илибытьможетргоЫет—Бсосовпадаетзадачейбез=X).Xвключения,видеатакже(обозначение)Множество=уравненийвиде(отанглийскогоэлементовмножество(БвзадачидопустимыхЕслиДр.линей-Ограничениепространством.нумерацияилинесколькихбытьможетX),то(Р)задачевдопустимыхэлементов(Р)задачуназываемограничений.(Р)задачи}(х)в—функциидляслучаяхтопологическимпространствомвсемРешением^(ОСТ>€х(Р)К,=общихзаписано(Р)задача).-О(-Р)неравенств.словаXболееВилиобозначаем/(ж)К".=нормированнымТ)К,—+Х&Б.ех1г;-*переменнойоднойXпеременныхлинейным,X/:ограниченииприобразом:опреде-следующимфункциитак:/(х)Дляминимум)илипространственекоторомзаписываемвыглядитзадача{максимумщывсехнаточекявляетсяминимумх€О{Р).точкаВэтомчтотакая,хслучаемыпишем7ВведениеаЪзтшР.€хТакойглобальным.(аЪяпахР).глобальностьподчеркнутьрешениймыдолжны}{хп)Пристремитсязадачиэкстремумыточкойявляетсях/(х)тоВсвязиссуществуетусловиялиВдолжноЛв/(х)17).(Р)хмаксимумеолюбойдляАналогичнозадачеточких1остшР),€х^Ъ6хV(пишемчтотакая,илиминимуме,илимножествоПоэтомудалеенадоэкстремум(и какой)илиизважнейшихОднимиприменимостиприменитьбезобоснования,выделитьрешение.менеесограничениямиНижезадач.Иногдаширока.можетпривестибудетонтиповэтотэкс-условий.достаточныхзадачоднакотеорему,неПоонадоставляетпомощьюдостаточноимеющуюсятемвозможно,конкретныхЛагранжаназываемэкстремумов.ограничений.снятиято-(мыточекэкстремальными),решениянекоторыхдляпринципаможносделаетсяэтимножестворазобраться,принциповдоказанВыписываязадачи.локальныхдажеточкойЭточисленно.илинеобходимыемножествоилиитакойнет.явнонекотороеЭтока-условия,разработанынаходимусловиям.Яагранжапринципсформулированрешениерешениекритическими,абсолютныхкаждойсвопросы:достаточныенаиболеемыэтимчемнайтикакэкстремума,стационарными,возникаюткаковыудовлетворятьусловияшире,которых}(х)чтоидетзадачудовлетворяющеепримененныйтакая,(пишеммаксимумазадачи,которымзадачехзадачейэкстремальныхнеобходимыеявляетсязадачеэкстремума,решениетеорииусловия,их(Р)вэкстремальнойкаждойнеобходимыеточек,(глоТочкаэкстремумы.(VречьзначениеабсолютныетолькоокрестностьЕсликоторойна1осехггР.пишемкаковыкВ€хнелокальногосуществуетП Л.Множестводостигается,нех„,чтобы5тах.иокрестноститочкойеслиV5аЬ8тах)-локальныеиточкиэтойизхявляется1остахР),^ /(&)€минимумаVокрестностьточкиточканолокальногосуществуетдопустимойилиэкстремумотыскатьследуетзадачи,чи-(иногда,Если5т}„величинамназывается5тахточеккрешении(глобальные)задачи,5тщ5аь5ттАг§Р.задачевилипоследовательностьуказатьфункцииеслиобозначаетсягло-илимаксимумрешение—экстремума,(Р)задачихгдеобозначаетсяиабсолютным,ещеабсолютный/(ж),задачизначениемтоназываетсяопределяетсяВеличиначисленнымхминимумАналогичнонельзяприме-принцип,ксфорСфераточкам,средиГлава1Экстремальные§ 1.ВКонечномерные1.1.ПостановкаПусть/:йразК"К-+функция—х,мыбез€ограниченийзадачирешенииГладкойназываетсянайтинадо(минимумыэкстре-задача:следующаяех!г.-+не(глобальные)абсолютныетолькомаксимумы)иопределен-/ дифференцируемаконечномернойфункцияБк(х)./(х)понимаеммыЕсли/пишемобла-переменных,гладкостьюфункции.задачейПридействительныхпПодгладкостью.экстремумыусловиязадачиточкеэкстремальнойдостаточныеипеременных.несколькихидифференцируемостьвограниченийнеобходимыедаютсяоднойнекоторойобладающаябеззадачипараграфефункцийэтомэкстремумаопределеннуюзадачифункции,инолокальныеэкс-экстремумы.ТочкафункциичтоПри/,хесли}(х)мыпишемилимаксимуме,1.2.Необходимые1.2.1.ФункцииТеорема1действительногои<}{х))х€однойО{&)хх€1остах/),€1осех1г/.достаточные<е}функ-этойизахточкитакая,окрестности.еслиречьидетэкстремумаусловияпеременной(Ферма).€х\точки(хпишем| \х—{х=любой1остш/тоПустьЕсли/для(максимума)минимумаЛеипеременного./локальногоокрестность(}(х)}(х)^этомминимумефункцииточкойявляетсясуществуетхдифференцируема€/:1осех1г/КК-+—вточкеодногофункциялокальноготочка—х,тодействиэкстремумао§1.КонечномерныеПоДоказательство.}(х)}'(х)к+Если}'(х)+/'(х)быо(\)+Самоф О,кможеттакменьше,большеи/Геометрическидифференцируемой2.Необходимыелокальногоусловияпри/ее^?2(^)€бытькак/(х)—0^/.вчток0.-+отрицательныеможет1остах€жк/(х+к)чтоутверждает,■экстремуматочкеграфикугоризонтальна.дваждыдифференцируема/,//DА)+/D)=Необходимость.необходимомуПустьФерматеоремедостаточно/Dкустремимк)+Л.малых—хТейлоравлюбогое/Dг^силу> 0гусловияк)+.-/D)Следовательно,=о(к2)==^/"D)Л2хтополучим,0,/"D)\г(к)\«•Лмалыхдостаточнопри(к)0,>к1-+€1оспгт/.о(к2).=-гпеременнойЛ)—/(х)-0>приТейлора(г(А)0о(к2))=>Лна/"D)что^необходи-пооднойнеравенствапоследнего/'D)ПустьДостаточность.^г(А)во-первых,}(хг(А)+частиПоскольку/.г(А),Тогда,функцийформулы\Г\х)к2обе+во-вторых,силув=0,функциидля0,—/D)->1осгшп/.€ПоэтомуРазделимнулю.к/'(х)к.малых/"D)\}"{*)П2I порядка—> 0.Тейлора+х/"(х)минимума/'D)А+экстремумаусловию0,=формулеПоДоказательство.локаль-точка—еслилокальноготочка—0,=экстремума:условия1ос1шп€/1осгшп€хтоГ{х)хеслиэкстремума:функцииминимумаДостаточныепри0^функция/'D)при/D)—тому,касательнаяПустьк)+иприх.точкето/(хФермафункциитакположительные,/(х)-теоремаТеоремавк)+-+=величинанулю,0коA)к)+Значит,к.малыхблизкихпосколькуразностьЭтопротиворечит/(хипридостаточнокакнуля./(жо(\)к=/'(х),принимать1остшехприкпризнакСледовательно,значения.о(к)—тобыимелаже(к)г9ограниченийдифференцируемостиопределению(к),гбеззадачи0.еЛ2устре-0.^Тогда=>•иформулепог(к)^е)к2 >-еЛ2дляимеем:г(А)^(^-0■10Длялокального}"(х)вид:В^0отом,одномерномнавопросилинет.3.(А)п=в(тах)1осгшп€хфункции{Bт~1\х).