Алексеев В.М., Галеев Э.М., Тихомиров В.М. - Сборник задач по оптимизации (теория, примеры, задачи)

519.6УДК22.18ББКА 47АлексеевВ.позадачизд.Вконечномерногооптимальногоиуправленияфункциональногоэлементыс.700Учеб.назадачСборник2-е—отысканиеэкстремумовдляисчисления,вариационноговыпуклогоСодержатсяпрограммирования.дифференциальногоанализа,М.пособие.5-9221-0590-6.ISBN-классическогозадачдляВ.ТихомировЗадачи:256-примернослучая,М.,Примеры.2005.собранокнигеЭ.леевТеория.ФИЗМАТЛИТ,М.:-ГаМ.,оптимизации.исчисленияэлеивыпуклогоанализа.ВОсновуЧастькнигеприведенызадачзадач,сбольшоеиспользованыкачествевизадач,Ос-примеры.восходящийпринцип,Имеетсярешениями.бытьмогутрешениядляединыйсоставляетзадачприведенакоторыенеобходимаятеория,всехрешениякЛагранжу.количествотрудныхикурсовыхдипломныхработ.ДлястудентовISBN5-9221повузоваматематика»,также-0590-6В.дляаспирантов«Математика»специальностямииработников.научных©ФИЗМАТЛИТ,©В.М.М.2005Алексеев,Тихомиров,Э.М.2005Галеев,«ПрикладнаяОГЛАВЛЕНИЕПредисловиеВведениеЛАГРАНЖАПРИНЦИП0.1.Основные0.2.ПринципЗАДАЧсвязанныепонятия,ЛагранжаA8).Упражненияс1.ЭлементысзадачограничениямиIПРЕДВАРИТЕЛЬНЫЕИСВЕДЕНИЯС(9).A2).задачамиэкстремальнымиисследованияГлава§ТЕОРИИВЭКСТРЕМАЛЬНЫХЗАДАЧИОГРАНИЧЕНИЯМИфункциональногоанализадифференциальногои20исчисления1.1.УпражненияанализаНормированные1.2.B1).B3).банаховыиНекоторыеУпражненияB6).УпражненияпроизводныхдифференциальногопространстваизтеоремыB4).исчисленияв1.3.геометрииЛеммыB8).1.5.иB5).B0).Упражнефункционального1.4.ОпределенияОсновныенормированныхдифB8).теоремыпространствах32Задачи§2.Гладкие2.1.с35задачиЭлементарныеравенствами2.5.условияи(общийD6).ПримерыГладкая2.3.О2.4.равенст-D0).Примерыусло-D7).НьютонаметодесзадачаДостаточныепорядков.2.7.задачаконечномернаяГладкаяC9).высшихусловия2.6.2.2.C7).случай)равенствнеравенствамиНеобходимыеD2).C5).задачитипаограничениямиЗадачи§3.47Элементы3.1.выпуклогоЗадачиОсновныепонятияанализа52анализавыпуклогоE3).E2).Упражнения3.2.ОсновныетеоремыиформулыE8).58Оглавление§4.Выпуклые60задачи4.1.Принцип4.2.Теорияпрограммирование F5).ЛагранжаввыпукломF2).двойственности4.4.ВыпуклыйанализиF0).программированииЛинейное4.3.теорияпрограммирова-F5).задачэкстремальных72ЗадачиIГлаваКЛАССИЧЕСКОЕ§5.Элементарные5.1.классическогозадачиЗадачавариационногоисчисленияконцамиподвижными5.4.(80).Примеры5.5.НеобходимыеЗадачивысшихусловия5.7.(90).5.6.(88).ПримерыБоголюбоваТеоремаусловия.Гамильтона-ЯкобиУравнениеполя.классическогозадача5.3.G7).достаточныеипорядковПростейшая(84).73исчислениявариационного5.2.G3).БольцасТеорияИСЧИСЛЕНИЕВАРИАЦИОННОЕТео-(95).97Задачи§6.Изопериметрические105задачи6.1.ПринципЛагранжа6.2.НеобходимыевысшихA05).задачизопериметрическихдляусловияипорядковдостаточныеусло-A09).условия113Задачи§7.Задачисо7.1.старшимиНеобходимоеусловиевысшихусловия115производнымипервогоA15).порядкадостаточныеипорядков7.2.НеобходимыеA18).условия121ЗадачиIIГлаваЛАГРАНЖАЗАДАЧА§8.ЗадачаИОПТИМАЛЬНОЕУПРАВЛЕНИЕ124Лагранжа8.1.ПринципЛагранжаA24).Лагранжазадачидля130Задачи§9.Ляпуновские9.1.Принцип132задачиЭлементарнаяЛагранжаоптимальногозадачадляA32).управлениязадачляпуновских9.2.Прин-A33).135Задачи§10.Задачи10.1.максимумавариационномклассическомЗадачиоптимальногоПринципи137управленияусловияA51).исчислениивариационномA37).Понтрягинамаксимуманеобходимыеминимума10.3.10.2.вДостаточныеисчисленииПринципмакси-классическомусловиявариациминимумавA57).167Оглавление5ГлаваСВОДНЫЙ§11.§Сводный12.12.1.наилучшегоПРИЛОЖЕНИЯ170180задачиНекоторыеA84).ГеометрическиеприближенияуказанияСписоклитературыСписокобозначений12.3.неравенстваA91).и194решения252253указательанализатеоремынеравенстваОтветы,ПредметныйИотделРазныеНекоторые12.4.ОТДЕЛIV254иНеравенстваA89).A80).алгебрыдля12.5.производныхПолиномы12.2.Некото-A87).наилучше-КОПРЕДИСЛОВИЕПриэтогоподготовкеВизменения.ВТОРОМУбылиизданияосновноммыИЗДАНИЮвнесеныминимальныелишьлишьограничилисьзамечен-исправлениемопечаток.замеченныхАвторыПРЕДИСЛОВИЕРольиоптимизацииметодовсамойматематикеобразованиеТеориябезнемыслимоееразделовдисциплиныЗавыпуклый—оптимальноеивтузовтеорииэтойкнигиоп-местовэтихкакнекоторыхспособствовать—высшейкурсахдисциплиндолжно,традиционныхчастейразделовклассическогочтобытому,достойноезанялизадачэкстремальныхиместовметодытеорииматема-современномобразовании.математическомМынарассчитываемтехническихобычныхивНамэтойразделы§§5-7оптимальноеатакжеЭтиэтойкниги.темТакимонидаютобразом,важ-ввкромевозможностьосновдлясвоегоматематическогобольшуюрешатьосновнуюзадачнике.параг-требуютнеопти-—названныхрешения»них,10§основнымиврешатьэлементовпрограммирование,«Правилознаний,специальныхсобычкурсомлюбомпридляисчисление,разобранныевпредставленыматематическоеявляютсяизадачи»никакихВместе—местозадачникепараграфыпримеры,пониманияанализа.2нашемвариационноеуправление.«ПостановкаПунктыпараграфов,§втеории:классическое—Виуглубленнымчтопредставляется,найтисьдолжнозадач.использовансвузахматематикиэкстремальныхважныебудетзадачниктехническихвуниверситетах.преподаваниятеориичтото,ивузах,математики,уровнезадачсвоепреподаваниеидисципли-программирование,находяттаквариа-анализа.Цельввзадач,экстремальныхновыеСозданиеновоефункциональногосформировалисьонилишьипеременныхнелинейноеиуниверситетов.внестисомнения,касалисьмногихгодыНынеуправление.математикибезэтилинейноеанализ,Всегоразвития.математикикурсахфункцийэкстремумов—бурногопериодвматематическоевремяоптимизации.теорииназадестествознаниитехнике,нашевэлементовтомуисчисления.вариационногоэкономике,переживаетвекачетвертьдвухвИЗДАНИЮПоэтомуогромна.оптимизациилишьПЕРВОМУКмассузадаччастьможно,Предисловиеинтегральногодифференциальногокурсиинтеграль-исчисления.ВуглубленнымсвузахиспользованыразделыусловиямиспользуютсяЭтотэкстремума.местомыиспользу-классическогозанимаютстаралисьдоказательствахфактыважнейшеекоторыхиспользо-относящиесяматериалПриметодически.основополагающиелишьбытьмогутпараграфов,перечисленныхотработатьтщательноматематикиизучениемтеоретическиенеобходимымкизданиюпервомуминимальныйналишьопираяськанализа,обтеоремысредиобратнойнеявнойифункции.Всеостальноетеориивыпуклыйанализ.выпуклогоанализ১§89.4,аженихиспользовать3.§задачРольраскрываетсяспециальныхвклассическогозадачеосновываетсяпосвященэкстремальныхможнотеоремамважней-доказываютсяНаанализатеориипрепо-икурсах.исчисле-вариационногоЛагранжа.задаче12§Материалтеориипонятиямкоторыхвыпуклогонарассчитанозадач.материалобщей—помощьюобщейвЭтоткнигибазовымэкстремальныхОсновампосвященисчислениясанализа,теоремывчасти1 посвящен§университетах.функциональноговажнейшиетеоретическойввпреподаваниетакжевкакпоказать,призванвзадачэкстремальныхможноисследованияхразличныхиспользоватьалгебры,курсахэлементыанализа,геометрии,итеоретическогоприкладногохарактера.НесколькообсловособенностьсостоитвосновывающейсяОсвоивСводныйприступатьособенностьважнаяобычно,ИвниманиетеорииЧастьПризадачнаписанииВ.М.г.).1979болееНо,вширокуюРаботасилотличиеМ.преподаванияипособия,этогокурсовПоэтомуЗадачникМГУ.СВ.написан-(Наука,Фоминымзадачникнарассчитанважнейшихвчастяхизложениепособия.упомянутогоедваВ.вы-снабженыониуправление»,Тихомировымототскончалсявсе«ОптимальноеВ.задачникоманализа,факультетеаудиторию.надподчеркиватьопытотражениепособиюнезависимоматериаластаралисьвыпуклогорешениями.механико-математическомкучебномуАлексеевым,примыкаетнаписанномубольшее,управления.снашелдатьстремилисьзадачникеПрактическизадач.приведенакнигинаоптимизации—оптимального700околозадачникеответами.методикиусловиям.возможно,методовимывдостаточнымпрограммированияВчтотом,Поэтомуэтогдевсюду,новыхвыпуклогораздела.такойдлявзадач.уделеномынаконец,плодотворностьтворческихсостоитисследованиеисчерпывающеечемлюбогозадачрешениювведении.задач.экстремальныхВтораяквоприспособлениразза-экстремальныхизлагаетсяпринципсразукакметодологии,исследованияСамособен-ееединойнапринципе(§11)Главнаякниги.построенаЛагранжу.можноотделрешенияонаобщемкего,этойчтонавосходящемзадач,особенностяхтом,лишьМ.Алексеев,вкогданачалась,оченьмногосвоихрасцветесилотдавшийПредисловиеразработкеипостановкеилекционныхнаикурсовеепланявилисьбольшаядоляПриизВ.поиМырадыпроблемВ.иаспирантамА.Аюнцу,Е.Ильяеву,МыВ.Б.П.ПекарюбудемоченькввиА.А.Б.студентамспособствовав-——Зунгу,Ю.А.Александрову,Г.Лудереру,Г.Магарил-Петросяну.запланутакжебывшимочередьДиньБуслаеву,М.—благодарныипервуючастности,кафедрыфакультетаИ.

Зеликину,сотрудникамМыИразделеизданияуниверситетов.настоящим—признательнызамыслу,вавторами,особенноФурсикову.книги.улучшениюА.относящиесяА.иихпомощь,кафедрыфран-учебниковмеханико-математическогоразностороннююКонягинуспособствовавшимнамзадач,дляротапринтныеЯрославскогоблагодарностьсвою100излитературыиуправленияиспискенекоторыеприсланныевыразитьбольшуюС.иуправТихо-В.М.инекоторыхвприведеныКиевскогоМ.материалыпособия»)Казахского,общихчтотех,любезнооптимизации,пособияС.(изучебныезадачников«Учебникипособия,материалыоптимальномуКушниренког.), сборникТихомировым1980В.иучебногоизданияфранцузскогопоГ.МГУ,АлексеевымМ.задачиспользовалимыА.изданиеВ.яви-разделыподбореизадачГалеевым,(ротапринтноекнигиГалееву.«СборникЭ.М.подготовленныйтеоретические«Задачи»Алексеева,М.М.разделомнаписанныйТихомировымиЭ.надлек-этойзамыселсоставлениивтруда,принадлежитархивауправлению»,Тихомирову,совместногоработефакультетеОбщийзанятий.В.М.нашегоизданиюпервомумеханико-математическомсеминарскихпринадлежатплодомкилюбыезамечанияипредложения,книги.содержаниюЭ.М.Галеев,В.М.ТихомировобзаВведениеЛАГРАНЖАПРИНЦИПТЕОРИИВОсновные0.1.Сзадачами.ЭКСТРЕМАЛЬНЫХсвязанныепонятия,назадачамиРассмотримЗадача1.расстоянийимаксимумдвепримераНайтидляотнееЗАДАЧэкстремальнымиещепрямойтакуюбылаточек2.Задача2).ПерваяСлово1задачаОбапонятияотзадачиилиизадач,управления.предполагаетсясвязь1Задачивозникающиеиупотреблении2последнегопрактическимисформулированыестественныхэкстремальныхоптимальногообычнотерминапредпола-приложениями.безсловесно,внаиболь-отысканиетеориейтеориейиногдаза-экстремальныенаилиилиупотребляютнаилучший,означаетэто—задачназываютоптимизации,сзадач2иТеориювеличинтеориейПричто1(отэкстремумИногдаoptimus,задачи—наиболь-минимум,термином«крайнее»).оптимизации.наименьшихилииединымлатинскогообразом,максимум.minimumсловомаксимумобъединяютсяна—«наибольшее»,—площадивтораяминимум,означающегоТакимзадачи,задачи,этиоптимальный,совершенный.наозначает—наибольшейпрямоугольникзадачаextremum,словокруглатынинаименьшееилатинскогонаибольшихэто—«наименьшее».наибольшеевпо1).2Рис.Вписатьmaximumсумма(рис.у,,B(d,b)(рис.чтобыточку,минимальнаУ^Рис.школе.взадачи.заданныхдвухзадача-сталкиваемсяпланиметрическиеданнойнадосмыминимумнаукахЭкстремальныеформул.илинапрактике,обычно10Введениеставятсяименнообласти,гдетакданнаяпереводбытьформализованасильнозависитнеобходим1).рис.ПустьСФормализуемх2уравнением+хGу2=точекAw0).2.ПустьНаправимлежащейу)fo(x,НетрудноАху=X,определенияY;множествевXрасширенную—xgCЗадачузаменивf(x)на—>—f(x).—>наоборот,Сподмножествоисо-+ооFимеетизXобластьлежитвоотображенийдляэкстремаль-X/,элементыС.изапись(sup);infе.т.прямая,хX.Стермины:значениямиупотребляетсяхеС.(з)СЕслиможновсегдаf(x)И,ееобласть—X,=тона-задачаограничений.максимумзадачу=описатьсвключа-(XR—>обозначениядопустимыми.беззадачейназываетсяОнаXзадачазадачеупотребляемформализоватьобразом,задачиназываютсяиизлишни,отображениекаждоготочноО,эквивалентнаэлементаТакимf(x)0^г2дополненнаямыR.формализованнойТочки/:чтодлязначитплощадьмаксимум>х=(вещественная)«функционал»этоу=здесьозначает,F(x)прямуюэкстремальную задачуДляYТогданайтит.е.чисел,—>словоу2ограничение,действительнаяaпряпрямо-аналогично.встретившиесяF:0,^+устроенадействительныхзапись2).рис.у)функционалирасширеннаяуравнени->0.хзадачанекоторыевсехоо;b);задаче:сторонамзадачу:/2(ж,х2условиифункционала)совокупность—(см.(d,=вершины(см.=уусловияприэлементы:следующиеПояснимиАВследующейкоординатыО,=у)чтоАхуу)такуюу2-г2формализованнаяэто@, а)иНапра-условиях+убедиться,определения—точкупараллельноквадрантеприу)=х2максимумR1.задачичерезописываетсяПолучаем/з(ж,себя=кОуи(х,первомАху.равна/i(ж,вАокружностьчерезвпрямоугольникавключаетсприходимОхосиобозначимпрямоугольника,неравенствами.ЛюбаяНачнемпроведемтаковы:мызачастую=задачуг2.инайтиВТогдарешенияформализована.2.иможетзадачаR.прямоугольникафункциипростотаОуосьжефункцииминимумвсема(х,=/0*0попрямой,координатыточкикоординатанайти1задачзаданнойпоязык.таионаудачноформализацииОхосьинасколькотого,восполь-математическийнаОднаспособами,разнымиоттойтерминахбыломожнозадачпереводформализацией.называетсяОсуществимНаправимсодержательныхЧтобывозникла.задачатеорией,воспользоватьсяЭтотвсловесно,—sup,хзадачуесвестиС,задачейнаминимумкназадачеf(x)—>можноinf,минимум,xаналогичнымeС,гдеПринципобразомсвестикиминимумПриведембудемнеобходимоf(x)а2уздесь—2задачи—>Ci){(х,у)игдеточкаС1(х,острыеу/(а=+В(попробуйтеуbJг/лД,взадаче(locmaxнеравенство(locmaxabsminзадачиЭтувели-точ-[СВ]чтотем,геометрии,сОх,осьюзначениерав-S3{задачи=(попробуй-квадратсоответствуетхрешениюбудемэкстремумовихстрогое(з)локальныйз),еслиг/л/2,=х,\х(f(x)^f(x)).то(absИнымисуществуетmaxокрестностьзх)/(ж)->inf(sup);вчто—х\\5,что%задачеxeCnf.(зх)знеравенстеслиточкиminлюбойдлявыполняетсясловами,locехпишут(з)задачедоставляетхтакое,<вточкаи5>0существуеткоторойдляПусть(максимум),илокаль-рассматриватьГоворят,минимумJgCтакжеопределение.пространство.зхf(x),ВеличинаискомуюизС).Еминимумзадачи).иf(x)>х=2r2.Дадимз),Абсолютныйзадачи.являетсяэтоговорятзначением[АС]ра-f(x)любогодляотражения»);углувидеещееслиопределяющийх,прямоугольникомточкиf(x)^f(x)f(x)известноотрезкаминормированное—^значениекакгеометрически);S32допустимойGискомымэкстремумы.XS'min('S'max)минимумглобальныхКромелокальныеd2.2этодоказать=простоИЛИравен+задаче(иличисленнымговоримобразованныевравенства.(з),задачерешениемназываетсяограничениемтипавназыватьS3падения0},с—задаваемымабсолютнымхарактеризуется,углы,(«уголравныC2)f(x)абсолютный0),г2.Cg)=(absmax3).будемформализация:ограничениемназываетсязадачи,задаче=с—0.C2)^другая?/ ^=R2):?/задача0,>жxGabsmin3решениесокращенияОбозначатьу2+С=inf.Ci)0,выше,ж2г2,(X1Задача->>ж(максимумом)пишеммыдляг2,(соответственнобудемВписатьобозначаемаясказано(з^)хxgC(иногдабудемто2.ихJ(d-ограничений,задачазадачивеличинуЪ2 +=sup;=минимумом—/уу2+—>у2+неравенств,этомхточку| х21задач+былобеззадачалюбогоПри(максимум)назадачидлязадачи,плоскость,х2sup;какR2еДопустимаяглобальным)дляслуча-задачахтолькоихобедвумернаяимеется,—х2+Ахуравенстввыписыватьзаписи=(X2Задачавэкстремумаисследоватьтехвопределенностиусловийразные,Аху=Длямаксимум.формализованныеЗадачаСзадач11экстремальныхнеобходимыхR):/ДлятеорииxeC.extr;->=назадачемаксимумЕслиминимум.f(x)вформулировкикогдаслучаях,наЛагранжаххтакая,?locчтоminзж?12ВведениеТеориязадачэкстремальныхВзадач.экстремальныхподмножествонекотороекритическим,локальныхнадоПослеизвыделитьНайдемнихсодержатьсяназываемкритичес-абсолютныхмножествовсехнахожденияидажеточеккритическихлокальныеточки,абсолютныеивэкстремумызадаче.3.Задачаf(x)х3(х2=1)-(зз)-1extr;->3).(рис.Абсолютныйвэкстремумможетзадачевнутреннейвоилиотрезкавнутреннейтоточке,этойвточкенадостигатьсяЕслиточке.концахводостигаетсяэкстремум3Рис.т.должнорешения.критическиеследующейчемвыделяютправиламыкотороешире,экстремумов.этикоторыхточек,нескольковозможно,средимножестворешенийнахожденияправиласвоемточек,Этозадачи.решениедаетбольшинстведолжнапроизводнаяравнятьсянулю,е.f(x)ТакимХо,=0=образом,О,Х\locminд/3/5,=G0.2.33;Изк—примереограничений.ИЗmaxбезФункция(п./вх\ТОЧКИ33;состоитвредукциипростойструктурыд/З/5,—ЯВЛЯЮТСЯчтовидно,absGх^с=Х\3)minзадачх%Х%,рис.absGх\1,—Х2,(см./=х\,max33.ограничениями.сзадач(вбольшинствеограничений).к0.1),точек:33;болеепереходить1{-ехисследованиязадачрядузадачамзадачи^^КОТОрЫХЛагранжачем0ОфункцииlocGх$ЛагранжакПрежде2,=графикаХ2,принципаограничениямислучаев=5 критических#5ПринципСущностьЗх2-имеемстационарными.х\5х4ЪхА^^какформализацииописаниюэтогоследуетCi)сизпокажемпринципа,поступатьп.0.1задачинабеззадачами1дифферен-огра-ПринципИзцируема.Ферма,дифференцируемой0.втеориидифференциальногоесликоторой,функциикурсасогласноэкстремум=Лагранжазадач13экстремальныхточках/,тоисчисленияизвестнадоставляетлокальныйвыполненотеоремаэкстре-f'(x)соотношение=Имеем(d-xJf'(x)Уравнениевыполненоираз(см.0=имеетединственноерешениесоотношение«уголприх,паденияравенкаккоторомотражения»углу1):рис.хdx—1-хJИзсуществует,сказанноготолокальнымисслучаев,помощьюобразом,Ci)безнеобходимыевсерешениеточках)Принципилиточексостоитпринциптипа(х\,=задающие)>•какчтосограниче-наПокажем,задачи.примереиссле-иэлементарнойIТ*1,=I 17"—и»—га}..