Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 12

ТЕОРЕМЛ 1 (опгпамалъпостпи оля раэложимых фупхаай). ' ппп у(х, у) = пцп Гг (х, пнп ~з(у)), (*,о) и точно так же для шах. Доказательство проведем для случая минимума. (Равенство будет вытекать из пары противоположных неравенств.) По определению минимума пппЛ(х Ь(у)) < Л(х Уа(у )) Ух у и, следовательно, для у вп агбпнпЯУ), х пп агепппгг(х„6(у )) и о что доказывает неравенство "<". Аналогично, в силу неубывання уг по последнему аргументу, уг (х', пппг уз(у)) < уг (х', уз(у')) Ух', у'. Положим Уг:= агдтт уг(х', )з(у)), х':= ага пни(пнп уг(х, Яу))). Поскольку повторный пцп равен двойному, в правой части получили пцпо о у(х, у), чем доказали и неравенство ")".

Плй задачи условной оптимизации теорема оптимальности для разложимых функций переписывается следуюшим образом: пцп ~(х,у) = ппп 1г(х, пйп Яу)), (ол)ай о: у(о)гга оау(о) где У(х) = (у~ (х,у) б й]. Указанная теорема используется для понижения размерности оптимизапионных задач и в методе л(П. Пля начала рассмотрим задачу оптимизации, записанную в виде — пцп ~(х,у), х б Х С Нг', уб У(х) С В". (6) о(о,г)еегсп 59 Здесь Ет называется множеством пзермииальиых соспгояиий системы по ассоциации с динамическими системами управления, для оптимизации которых было'изобретено ПП.

Например, для у = (у) ° ° ° Ут), если ограничения задачи заданы в форме у;(х, у) < 0 Ув = Т, пг, то Ет = К"'. Пусть у разложима (4), а у разделяема: ) Ь( Ь( )) Ь. Н«рз«Ь, На+на Впю тогда введем Ух,у Е = Ь1(х), Е' = Ьг(у, Е) и вычисляем у как у(х, у) = Е'. Функции Ь), Лг называются ггуихциями перехода, векторы Е, Е' — соспгояииями сисглемьь Множество всех возможных состояний системы обозначается Е и формально задается так: 1) Е ) Ь)(Х) = (Л1(х)) х б Х), 2) НЕЕ Е (Ьг(у, Е)/уб У(Х)) С Е (множество в качестве аргумента означает объедянение по всем аргументам нз этого множества). Рассмотрим для (6) семейство задач поиска Ег(Е) = пцп уг(у), г: )«1з,н)ест которые нужно решать УЕ е Е. По теореме оптимальности У' = ппп 11(х, Ег(И)(х))).

В результате задача (6) свелась к последовательности ~)Е')+ 1 оптимизационных задач меньшей размерности. В методе ПП данная процедура применяется рекурсивно к задаче г'" = ппп Дхы...,х„) е(ео...,х )еетсн для сведения к семейству одномерных задач следующим образом. Пусть | последовательно разложима, т.е. Дхы...,х«) = У~(хмЯхг,...,х„)), Уг(хг, ° .,х«) = Ь(хг,Гз(хз, ° °,х )), Д )(х„мх„) = ~«)(х„~,У«(х«)), 60 и все Д монотонно не убывают по 2-му аргументу. Пусть у последовательно разделяема, т.е. ЗЕ С В.'", Э функпни перехода Ь1, Ьз,..., Ь„: Чх Е Х = ЭХ1 У(х) = Ьп(хп Еп-1)> Еп-1 = Ьп-1(хп-1>Еп-2)» ' Ез — Ьз(хз,Е1), Е1 = Ь1(х1) и Е> б Е Чз = 1>п — 1 ° Обозначим Чз = 2,п — 1, ЧЕ б Е через Ь1(х1,х1+1,...,х„,Е) функпию, определяемую рекуррентно равенствамк: Е1 = Ь;(х;, Е), Е~+1 = Ь1+1(х1+1,Е~), .

° °,Е„' = Ьп(хп, Е„>,) =' Ь (х>,хьь1>'''>хп>Е). Заметим, что в случае Е = Е; 11 Ь1(х1, х1+1,..., хп, Е> 1) = у(х) и Е; '= Ез Чу ) з. В сделанных обозначениях справедливо воэвраизное соовзхонзсхае для ограничений Ь (х;,х1+1,...,хп, Е) = Ь1+1(х+1,...,хп, Ь (х;, Е)). (8) Тогда по определению Г* = ппп Л(Х! > У2(Х2» Хп))> *ЕХ> Лз1пз,...,з,Л>1з>11ЕЕт и по теореме оптимальности Г' = пип у1(х1, Рз(Ь1(х1))), з>ЕХ> где ЧЕ1 б Е Рр(Е1) =' ппп Уз(хз,..., х„) = (пз "и ): Лз(пз,—.,з,Л>(п>))Ест (из (8)) = пип,6(хз,Ь(хз> ",х )) = (пз, -,з )> лз(зз,-,п л>1зз,н>))ест — ппп Яхз, Гз(Ь2(хз, Е1))) *зЕХз (последнее равенство следует из (5) с х = хз у = (хз, °, х )), и т.д., полагая минимум по пустому множеству равным +со, имеем 7;(Е) =' ппп Д(х1,х1+г,...,х„) ЧЛ,Е (10) Лз(зьзз+>,...,з„,х)Ест — семейство задач, в которое "погрузили" (1), Г(Е1 1) = ппп Д(х1, 0<+1(Ь1(х1, Е; 1))) ЧЕ>.-1 б Е (11) 61 — еозераньное (фуннчнонааьное) уравнение ДД 'Гь = е, » -Т, Р'„(Е) = ппп ~„(в„).

е„ЕХ„: Ь„(е„,и)ягг (12) Алгорнньм ЛП: 1ЬЕ б Е вычисляем Г„(Е) из (12), последовательно для ь = »- 1,..., 2 определяем Рь(Е) из (11),(10), затем г" из (9). Число шагов алгоритма (решений задач одномерной минимизации) будет порядка»~Е ~. Таким образом метод ДП имеет смысл применять для задач с не очень большим числом состояний Щ малб).

2. Примерами разложимых функций могут служить пцп, шах, сумма, произведение (с неотрицательными коэффициентами) и т.п. Исходно метод ДП использовался для оптимязации динамических систем, что нашло отражение в применяемой терминологии. Так, Е соответствует физическому пространству состояний (возможных координат траектории движения), в; — управлению в момент времени 1» воздейств(ье управления на траекторию определяется функпией перехода в сл ующее состояние, на конечное состояние наложены ограничения п надлежности к Ет, начальное состояние фиксировано; уь(х;, Е) — стоимость управления системой, находящейся в состоянии Е, у' — Ъ(оимость всей траектории Ем..., Е„ Соотношение (11)ь означает минимизацию стоимости "хвоста" траектории в каждый момент времени, что согласуется с принципом оптимальности, сформулированным Р.

Бэллманом: оптимальная политика управления такова, что для любого начального состояния и любых решений (по выбору управления), принятых на начальных шагах, оставшиеся решения образуют оптимальную политику, начинающуюся с состояния, возникшего в результате этих решений. (Отметим, что в случае строгой монотонности у таким образом можно получить любое решение, в случае нестрогой монотонности — хотя бы одно). Проиллюстрируем применение метода ДП на примере решения задач БЛП с неотрицательными коэффициентами (элементами симплекс-таблицы). Итак, вернемся к задаче (3) г" '= шах (с, г) завсе Ае<Ь в предположении а;, Ь;, с б 2+. Обозначим через а.

у-й столбец матрицы А. Рассмотрим семейство задач поиска » Еь(Е) =' шах ~~~ су яу а: »зя(сл1 Уу»ь,...,» » а.яу < Ь вЂ” Е, у=я где Е'Е 8 =' (Е б Е~+] Е. < Ь; % = 1, ш), Ь = 1, и. Очевидно, Е" = Е~(0). Возвратное уравнение в данном случае: Рк(Е) = тзл(7ь~~(Е), сь + Ььь (Е + аь)), »р 1 0 иначе. Находим ЧЕ б 8 Е»(Е) и соответствующие я»(Е), затем для Ь = = в-1,..., 2 определяем Еь(Е) и реализующие их хь(Е) из возвратного уравнения, вычисляем Г~(0), л~(0) и далее хз(Е'),...,х„(Е» ') в зависимости от того, какие состояния Е',..., Е» ' были в конечном счете использованы при вычислении Е~(0), если посмотреть по всем шагам алгоритма.

Число шагов предложенного алгоритма равно и и на п-м шаге рассматривается пнп((Ь| + 1) ° ... (Ь + 1), 2" ') состояний, на (в — 1)-м — минимум из левой части (равной Щ) и 2" з и т.п. Так что при больших Ь метод ПП решает примерно столько же задач, сколько МВГ в худшем случае, однако решаемые задачи здесь проще (проверка ограничений вместо ЛП). Подчеркнем, что процедура ПП не дает способов сокрашения перебора, тогда как удачный выбор стратегии ветвления в МВГ (например, на основе имеющейся у вычислителя дополнительной информации или эвристических соображений) позволяет (хотя и не гарантированно) решать задачи большей размерности. Отметим также отсутствие ограничения неотрицательности коэффициентов для работы МВГ. В принципе, возможно комбинирование обеих схем (см.

[6]). Содержание 51 54 58 Н.М. Новикова Дискретные и непрерывные задачи оптимиэацни (основные сведения по теории и методам решения) Корректура автора Подписано в печать 25.12.95 Формат бумаги 60х84 1/16 Уч.-иод.л. 3,5. Уел.-печ.л. 4 Тираж 200 вко. Закво 3. Цена договорная Отпечатано нв ротапринтах в ВЦ РАН 117333,Москва, ул. Вавилова, 40 1.

ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ 51. Понятие о сложности решения задач $2. НР-полные (универсальные) задачи $3. Классы сложности. Сильная НР-полнота и псевдополиномиальность 15 54. Приближенное решение задач комбинаторной оптимизации 21 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ $5. Понятие о сложности задачи линейного программирования (ЛП) 24 56. Метод зллипсоидов 29 57. Теория двойственности ЛП. Идея метода Кармаркара ЗЗ 3.

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ 58. Обзор идей математического программирования (МП) 38 з9. Двойственность в МП 45 4. СПОСОБЫ РЕШЕНИЯ ПЕРЕБОРНЫХ ЗАДАЧ 510. Глобальная оптимизация. Метод ветвей и границ (МВГ) 511. Целочисленное линейное программирование (ЦЛП) 512. Метод динамического программирования (ДП) .