341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 56
Текст из файла (страница 56)
т.с, определение очередного приближения х(»тО из (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) (ь) (ы (ь) непусто, то компоненты е. вектора е ' представляются в виде е. з 1 (ь)-ь (ю= е — е н находятся из решения следующей задачи линейного з программирования с переменными ов, е, е, 1 = 1, ..., и: (ь)+ (ю- 1ь = — оь -) пнп, п дх 1=1 П (/) Е (е — е )+ос<0, (б1а, дд,(х ) (ь)+ дх 3 и (е() +е() )<1, (50) у=с оь,е,е, )О, (ь)+ (ь)- е() е() =О, 1=1,...,п. Замечание. Для ускорения сходимости метода возможных направлений множество индексов (49) иногда определяют не по точному, а приближенному равенству д;(х(")) = 0 со все возрастающей точностью еа, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
