3 часть (1081356), страница 57
Текст из файла (страница 57)
Для достаточно малых оь > 0 точка х("+') из (22) принадлежит множеству (у (т.е. е(ь) задает возльожиае направление). 2. Для достаточно малых аь > 0 выполняется неравенство г'(х("+') ) < < г'(х(ь)) (т.е. ейй определяет иаправлекие убсчеакил )'(х)). Первое условие означает, в частности, что для граничных точек х(") допустимого множества Гг вектор е(ь) направлен внутрь У. Величина пь > 0 в (22) выбирается из условия наибольшего убывания целевой функции в направлении е( ') с учетом требования х(ь+') Е (ь'. Рассмотрим сначала метод возможных направлений решения задачи минимизации выпуклой дифференцируемой нелинейной функции у(х) на допустимом множестве ГГ, заданном линейными ограничениями 2 4. Нелинейное программирование 395 1.
Пусть в точке хрб все неравенства (24) и (25) выполняются как строгио. Это означает, что х(») — внутренняя точка допустимого множества У. Тогда е( ) = — Г'(х( )), (26) и 1» = г(~~ аых ) =Ь;,,4=(Ях ' =0). (27) у=1 Представим поьипоненты е, вектора е(») для у ф 1» в виде (») (») (») )' (») а\ е, = е — е, ), (28) где е, если с, > О, (»] (») (») О, если е <0; (») О, если еу > О, (») (») (») — е, если е. < О. Очевидно, е,, е, > О, и е ед = 0 лля всех 1 ф,У». (»)-(- (») — (»)-(.
(»)— ) Такое представление ллп е( , 1 ф з», позволяет находить вектор е(») как (») решение задачи линейного программирования, содержащей условие неотрицательности перел»сивых, несмотря на то, что его компоненты могут быть отрицательными. Лля 1 Е з» представление (28) не используетсв, так как у вевтора е( ), опрсде(») (м лающего воаможное направление, вомпонснты е с номерами 1 Е,У» нс могут быть отрицательными. т.с, определение очередного приближения х(»тО из (22) совпадает с итерацией градиентного метода (см. 2 2). 2. Пусть хотя бы одно из неравенств (24), (25) в точке х(») обращается в равенство, т, с.
х(") является граничной точной допустимого множества У. Тогда выбор е(») в соответствии с (26), вообще говоря, невозможен, так как может оказаться, что точка х(»+О из (22) при любом а» > 0 не принадлежит множеству У (е(») из (26) нс является возможным в точке х(») направлснием). Опишем, как определять возможное направление убывания еОО в этом случае. Обозначим через 1» и .1» множества индексов, соответствующих ограничениям (24) и (25), которые в точке х60 обращаются в равенства, т. е. Гл. 17.
Методы оптимизации 396 Вектор ейй = (е,;...; е„) из (22) ищется как решение следующей задачи линейного программирования: ть(е<">) = (т"'(х<">), е< '>) = уедь у<<А, (а<'>, е<ь>) = ~~~ аже<. > + ~~~ аО(ет< >~ — е< > ) < О, 1 Е 1ь, (30) уеоь УвЛ. к <е< >> = ~~~ е. >+ ~ ~(е<. >~+е< > ) < 1, (31) т=г уедь Заешь е. 3 О, У' Е,У<м <ь> (32) (ЗЗ) е< > е< > = О, у р,уь т), (34) где а ' = (ои, ..., асо).
<О Поясним смысл соотношений (29)-(33). 1. Минимуму целевой функции уь(е<ь>) из (29) соответствует минимально возможный с учетом ограничений (30)-(34) угол между искомым вектороги е<ь> и антиградиентом — 1'(х<">), определяющим направление скорейшего убывания <(х) в точке х<ь>. 2. Ограничение (30) для каждого 1 Е 1ь означает, что вектор ейй составляет угол со; > — с вектором а<'>, нормальным к граничной гик перплоскости ~~ абх, = б, допустимого множества с< и направленным 1=1 вне У. г) Для учета дополнительного условия (34) при решении задачи (29)-(ЗЗ) симплекс-методам следует не включать переменные е и е с одинаковым у о номером У в число базисных одновременно.
3 4. Нелинейное программирование 397 1(х~ ~+оье~ ~) = шш /(х~ ~+ае®), и>о, о>-~-ао)еп т. е. оь = пнп(аы, ..., оь, аы, ..., аь„, а„'), (35) где аы и агу — максимальные перемещения, при которых для точки х~"+О из (22) выполняются соответственно 1-е ограничение (24) и у-е ограничение (25), т. е. +со, если (а~0, ейб) (О, ои = (36) (Ь, — (аб), хрй)]/(а~о, ейй), если (а~0,е~~)) ) 0; +со, если еу О, ОО ) — х~ /е~ ~, если е~ ~ <0 э 1 (37) а оь находится из условия наискорейшего спуска вдоль направления вектора е~ь~ без учета ограничений (24), (25), т. е.
Фь(а'„) = ппп Фв(о), где Фь(а) = /(хрй + аейй). (38) а>о Приведем описание к-го шага решения задачи (23) — (25) методом возможных направлений. 1. Подставить хйй в неравенства (24) и (25) и определить множества индексов 1ь, 1ь по формулам (27). Так как точка хйй принадлежит этой гиперплоскости, то условие (30) для любого г б 1ь гарантирует, что направление ейй является возможным по отношению к 1-му ограничению (24) исходной задачи.
Рис. 36 пояс- хч а" няет смысл ограничений (30) в двумерном случае. Ф, а чл1~а г 3. Условие (31) является ограниче- хи' ю нием на длину вектора е~ "~ и обеспечивает ограниченность снизу целевой о' функции /ь(ерй) из (29). 4. Неравенство (32) для каждого у Е б 1ь гарантирует, что направление иско- «! мого вектора е(ь) является возможным по отношению к у'-му ограничению (25) ис- Рис.
36 ходной задачи. 5. Соотношения (33) и (34) следуют из представления (28) компонент е~"~, у ф,уы вектора е~"'>. Опишем теперь, как определить величину перемещения оь вдоль направления е® из (22). Для найденного вектора ерй она находится из условия Гл.
17. Методы оптимизации 398 /(х) = (хг — 4) + (хг — 2) -+ гшп, хг+хг <3 хг+2хг < 4, хм хг >О. а В качестве начального приближения выберем, например, точку х>о> = (0,4; 1,4)' (убедитесь, что х~о> Е У). Шаг 1. 1. Ограничения (24) и (25) в точке х~о> выполняютсп как строгие неравенства (проверьте!), т.е.
х~~> — внутренняи точка множества У, т е !о = .уо = й>. 2. В соответствии с (26) находим е>о> / (х(о>) (7 2 1 2) (39) 3. Из формул (36), (37) получаем ао~ —— 1/7, аког = 1/12, Йо~ = = ног = +со. Определим ао в соответствии с (38), используя условие минимума Фо(о) = 0: Фо(о) =/(х>о>+ос>о>) (04+о 72 4)г+(14+о 12 2)г Фо(а) = 107,04а — 53,52 = О, откуда ао — — 1/2.
Из (35) окончательно находим оо = ппп (1/7, 1/12, 1/2, +сю) = 1/12. 4. Используя равенства (22), (39) и (40), получим (40) хО> = (0,4; 1,4) + — (7,2; 1,2) = (1; 1,5). 12 (41) 2. Если 1ь =,Уь = й>, найти вектор е1в> из (26), в противном случае определить е~ь> из решении задачи линейного программирования (29)— (33) с помощью формулы (28). 3. Длп найденного вектора е'ь> определить оь из формул (34)-(37). 4. Найти очередное приближение х>ь ы> по формуле (22). При выполнсниг> хоти бы одного из условий >>Г(х>ь>)>> < с или >>х>~ '> — х®)( < с, где с > 0 — число, определяющее точность решения задачи, вычисления завершают, полагая х* е х>ь>, /' е /(х<ь>).
Любое из равенств >>/'(х>ь>>> = О, >>х>ь '> — х>ь>! = 0 означает, что точка минимума х' функции /(х) на многкестве У найдена точно: х' = х<ь>. Пример 2. Решг>ть следующую задачу нелинейного программированин с линейными ограничениями методом возможных направлений, завершал вычисления при >)г'(х~~>)>> < 0,01 или >>х>" '> — х~~>(! < 0,01.
3 4. Нелинейное программирование 399 Шаг 2. 1. В точке х('> из (41) второе из ограничений задачи выполняется как равенство, поэтолгу х('> — граничная точка множества (у, причем 11 = (2),,71 = О. 2. Задача (29)-(33) для определения е(') принимает вид /1(е(1)) = — бе, ++бе, ) — е( )++ег ) -) шгп, е( )+ — е( ) + 2е( )+ — 2е( ) < О, е( ) + е( ) + е( ) + е( ) < 1 Е, Е, Ег Ег (,>, (це (ц (це (1>, /2 1 ),3 3 (42) 3. По формулам (36), (37) находим а11 — — 3/2, а12 —— 9/2, = ом = +ос, (11 = 156/85, поэтому в соответствии с (38) 1'3 9 156 '~ 3 а1 = ППП ~ —, —, —, +СО! = —. 1,2' 2' 85 ' / 2 (43) 4.
Очередное приближение х(2> находим до формуле (22) с учетом (41), (42) и (43): (г) 3 3 2 1 ц (44) Шаг 3. Как и на втором шаге, для определения е(2> получаем задачу линейного программирования /2(е(2>) = — 4е( >~+ 4е( ) — 2е( ) + 2ег() -) шгп, (')+ (2)- + (2)+ (2) — < О ег е( >~ — е( > + 2е(~>~ — 2е( ) < О, Е1 1 2 2 (2)+ (2)- (2)+ (г) — < 1 Е, + Е, Ег + Ег е(г)+, е(2) ) О е( >~ е( = О, у = 1, 2, 1 Записав эту задачу в каноническом виде с помощью дополнительных переменных и выбрав эти переменные в качестве базисных, в результате (1)+ (1)- (1)- двух шагов симплекс-метода получим е, = 2/3, ег — — 1/3, е( (1)"; = е = О, т. е.
Гл. 17. Методы оптимизации 400 решив которую, получим (45) Как и на предыпушем шаге, находим ам —— слтт —— азл —— +со) сг22 = оз = 1, т. е ат — — пцп (1, +со) = 1. (46) Из формул (22), (44) — (46) получаем х(з)=(2,1)+1. 1, = 5 Шаг 4. Находя е(з) по общему правилу, получим е(з) = О, т.
е. х(4) = х(з), и ((х(~) — х(~)!) = О. Это означает, что точка минимума х' найдена точно: х* = х(") = (5/2; 1/2), /' = /(х(з)) = 9/2. Рис. 37 дает геометрическую иллюстрацию хода решения задачи. На нем штриховыми линиями показаны линии уровня /(х) (окружности с центром в точке (4, 2)). ~> /(ха') = (3,32 хд /(х)о) О 2 3 4х, Рис, 37 Решить задачи нелинейного программирования с линейными ограничениями 17.281-17.290 методом возможных направлений, завершая вычисления при ((Г'(х(~))(( < 0,01 или Ох(~ ') — х(")(( < < 0,01: 17.281.
/(х) = х~~ + 2хз ~— 16х1 — 20хз — л ппп, 2х1 + 5хз < 40, 2х~ + хз < 16, х1) хз ) О. Гл. 17. Методы оптимизации 402 Метод возмо,"кных направлений используется также для решения задачи нелинейного программирования более общего, чем (23)-(25), вида, а именно 1(х) — ) ппп, (47) д,(х)<0, (=1,...,т, (48) где 1(х), д,(х) — выпуклые дифференцируемые в д„функции. Опишем один нз вариантов определения необходимого для решения атой задачи вектора е(в) из (22) методом возможных направлений, а также укажем критерий окончания вычислений. 1.
Выбор вектора е(ь). Если х(в) — внутренняя точка допустимого множества У, т.е. д;(х(~)) < О, ( = 1, ..., т, то вектор е(в) определяется так же, как в рассмотренном выше случае линейных ограничений (24), (25), т.е. е(а) = — 1'(х(ь)). Если же х( ) — граничная тачка множества У, т.е. множество инм) дексов 1ь = (г)д;(х(~)) = О) (49) (ь) (ы (ь) непусто, то компоненты е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
