И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 56
Текст из файла (страница 56)
Положить й = О. Основной ци к л. 111. Вычислить вектор в' (реализа- цию в в й-й итерации). 1Ч. Вычислить вектор х»+' = пх х' — р, (А) Ч„Р,(х", в") + ~ с, (гй) Ч,Р/ (х», а") ,/ / «/ ° где с/ (г/) — коэффициенты, определяемые согласно (5.34). Ч. Вычислить вектор г»+ йг(г + р»(Й)(Р(х г а ) г ))г где Р = (Р„..., Р„), Я сх  — выпуклый компакт, содержащий векторы ((/»(х), ..., 1 (х)), хсХ*) (здесь Х» — множество реше- ний задачи 1). Ч1.
Найти значения щаговых множителей р, (й + 1) и р» (Й + + 1), удовлетворяющие условиям теоремы 1. 296 ЧП. Положить й й + 1 и перейти к шагу 1П. Теорема 1. Пусть выполнены предположения 1 и, кроме того, имеют меето условия рг(й)~0, р,(й)~0 при й= О, 1, ...; В С М-О Е р,(й) ьь, Е рг(й) = ьь, -~~-~-.~--~-0 при й-~-ьь; г-о Рг !в) М Х е(р',(й)+4И))с г о Тогда каждая предельная точка последовательности (хь)ь ь, порожУгнной алгоритмом 1, принадлежит множеству решений задачи 1', а при достаточно большом значении а принадлежит множеству решений задачи 1. В более общем случае етохастический метод штрафов имеет следующий вид.
Алгоритм 1' Н а ч а л о. 1. Выбрать: произвольные начальные приближения х' ~ 11" и гь ~ Л"; начальные значения шатовых множителей р, (0) и р, (0), удовлетворяющие условиям теоремы 1'; достаточно большое число сс ) О. П. Положить й = О. Ое нов н ой пи кл.
П1, Вычислить реализации $~ (/г), 1 О, 1, ..., т, олучайных векторов $/, / О, 1, ..., т„условное математическое ожидание которых Е($'/(х", г'), ..., (х", г"))=71,(х")+о/(/г), 1=0, 1, ..., т, где Ь' (й), 1 = О, 1, ..., т,— векторы, измеримые относительно о-подалгебры, индуцированной случайными величинами (х', гь), ... ..., (х", г"). 1Ч. Вычиолить вектор х"+' = их х" — р, (й) Р (й) + ~„ 'с, (г,') У (й) ( ! где вг (г/) — числа, определяемые при заданном г~~ согласно (5.34).
Ч. Вычислить реализацию Ь (й) случайного вектора й, условное математическое ожидание которого К(!/(хь, гь), ..., (х', г')) =/(х"), где/= (/м - /). Ч1. Вычиолить вектор ге+~ = яг /(г" + рг (/г) (ь (я) — гг)). ЧП. Вычиолить значения щаговых множителей р, (й + 1), р, (й+ 1), удовлетворяющие условиям теоремы 1'. ЧП1, Положить й й+ 1 и перейти к шагу П1. Теорема 1'. Пусть выполняются все условия теоремы 1 и, кроме того, имеет место неравенство Рь (й) 1[ Ье (Я) + ~ с! (г[ь) Ь! (й) ( оо п. н. ь-з /=! Тогда каждая предельном точка последовательности [х")ь з, порожденной алгоритмом 1', принадлежит множеству решений задачи 1', а при достаточно большом значении а — множеству решений исходной задачи 1. Бибеааерафанеекае указания. При написании параграфа использовались работы [15Ц !531. 5.7. Методы возможных направлений Вектор [ть называют возможным направлением в точке х" (являющейся, например, я-м приближением к решению задачи отыскания агд ш[п 1е (х)), если существует такое число р ) О, что для всех крХ Л Е (О, р) точка х'+ И«является допустимой, т.
е. х" + Цге Е Х и, кРоме того, УдовлетвоРЯет неРавенствУ 1е (х" + [ьйь) (1е (х"). В методах возможных направлений улучшенное (й + 1)-е приближение х'+' к агу ппп 1е (х) вычисляют по формуле «сх х~+! = х« + рь[гь. Различные варианты методов возможных направлений отличакл ся способами выбора щаговых множителей р„и возможных направлений йз.
1. Методы зозмоисвыи вапраалеиий реьтевва задач мвввмвзаввв с ограввчеивлми типа неравенств 3 ада ча 1. Найти атаги!п~з(х) для заданной функции «ях 1е; В"-ь В' и множества Х ~ [х [ 7! (Х) ( О, 1 Е [1 ! т), х Е В"), определенного о помощью заданных функций [! ! В" ~ В', 1'Е Е П: гп). Предположения 1. (1) — функции 1п 1 = О, 1, ..., т, непрерывно дифференцнруемы; (й) — множество Х имеет внутренность нли относительную внутренность (т. е. множество Х может содержаться в линейном многообразии и иметь внутренность по отношению к этому многообразию). Алгоритпм 1 Н а ч а л о. 1. Вычислить начальное приближение хе ~ Х, удовлетворяющее условиям теоремы 1. П.
Положить |г = О. Оановной цикл. П1. Положить х=х». 1У. Найти решение а а, (х), И й" (х) задачи линейного программирования в (и + 1)-м пространстве векторов (а, й): ппп а (ам прн ограничениях (71»(х), й) (а; 1,(х)+(71~(х), И)(а, 1=1, ..., пн ~й,~(1, 1=1, ..., и. У. Если а» (х) О, то положить х» = х» и прекратить вычисле- ния; иначе перейти к шагу У1. У1. Вычислить наименьшее положительное число р», удовле- творяющее условию 1,(х+ р„й»(х)) = пнп. 1»(х+ рй" (х)). »ьо «+Ф(жх УП.
Вычислить следующее приближение х»+' = х+ р,И" (х). УП1. Положить й = й + 1 и перейти к шагу П1. георема 1. Если вьтолнены предположения 1 и начальное прибли- жение х» Е Х таково, что множество Х»1',1(х~1»(х) — 1»(х»)~(0, 1~(х)(0, 1 1, ..., т, хрВ") компактно и имеетвнутренность, топоследовотельность х», х», ... ..., порожденная алгоритмом 1, либо конечна и ее последний влемент х» удовлетворяет условию а» (х") = О, либо бесконечна и каждая ев предельная точка х удовлетворяет условию а» (х) = О. Если х' — оптимальное решение задачи 1, то а (х') = О. Основной недостаток алгоритма 1 состоит в том, что на каждой итерации требуется решать задачу линейного программирования, которая может иметь большую размерность (может включать все функции ограничений 1й 1 = 1, ..., т).
В приводимом ниже алгоритме те из ограничений задачи линей- ного программирования 1г(х)+(Ч11(х), й)» а, 1=1, ..., т, для которых значения 1~ (х) отрицательны и имеют достаточно боль- шую абсолютную величину, могут оказаться несущественными и их исключают из задачи линейного программирования, на й-й ите- рации. Алгоритм 1' Н а ч а л о.
1. Вычислить начальное приближение х' р Х, удов- летворяющее условиям теоремы 1. П. Выбрать константы з' О, з" р (О, а') и р р (О, 1) (рекомен- дуется р = '/,). 1П. Положить й = О. 1У. Положить е = з'. 298 Основной цикл. Ч. Положитьх х». Ч1. Найти з-активное множество индексов г(л(х)](Л (О) [] (1) 1](х) лл — е, /Е [1:(и]). ЧП. Найти решение и * ал (х), Ь = Ь, 'задачи линейного программирования в (и + 1)-мерном пространстве векторов (а, Ь): ш[п а при ограничениях (а,») (Ц](х), Ь) <а, !ЕИ»(х)[ ] Ь( ) л(~ 1, 1 Е [1 [ и].
ЧП1. Если (лл (х) ~ — а, то положить Ь» Ьл и перейти к шагу КП1; иначе перейти к шагу 1Х. 1Х. Если а ~ е', то перейти к шагу Х[ иначе положить е = ра ы перейти к шагу Ч[. Х. Найти множество индексов и, (х) ~ (О) [] (1)(,(х) > О, 1 [[[1: лл]). Х1. Найти решение а ал (х), Ь Ь» задачи линейного программирования в (и + 1)-мерном пространстве векторов (и, Ь): ппп сс при ограничениях (%7,(х), Ь) а~а, И г(л(х); )Ь])<1, И[1(п] ХП. Если ил (х) О, то положить хл х и пр(й(ратить вычисления; иначе положить а рз и перейти к шагу Ч1. Х1П. Вычислить число р(х) шах (р]1](х+ ЛЬ») »-,0, ЛЕ [О, р], ) ~ [1:и]). Х1Ч. Вычислить наименьшее значение р» ~ [О, р (х)], удовлетворяющее условию [л (х+ р»Ь») ш1п 1» (х+ рЬ»). ре[О,Ъ(п ХЧ. Вычислить следующее приближение х».(.( х+ р»Ь'. ХЧ1. Положить Ь Ь + 1 и перейти к шагу Ч.
Для алгоритма 1' имеет место теорема, ~щалогичная теореме 1. В [285] рекомендуется заменить шагр Х1Ц Х1У алгоритма 1' практически реализуемыми шагами ХП1' и Х]Ч' для вычисления шагового множителя р». ХП1'. Вычислить наименьшее из целых чисел з в О, для которых выполняются неравенства 1»(х+ ~'6Ь») — ~л(х) — ]]'6р(7~»(х), Ь')~0; [((х+ ~~6Ь»)(0, )6[1 (л(] (здесь 6) 0 и р Е (О, 1) — наперед заданные константы). Х1Ч'. Положить р» = ]!'6. Ниже приводится модификация алгоритма 1', в которой на каждой итерации необходимо решать более простую задачу линейного программирования. Алгоритм 1" Н а ч а л о.
1. Вычислить начальное приближение хо Р Х, удовлетворяюшее условиям теоремы !'. !1, Выбрать константы е' ) О, е" Е (О, е') и ]3 Е (О, !) (рекомендуется й = '/е). П1. Положить Ь = О. Основной цикл. 1Ч. Положить х= хе. Ч'. Положить е, = е'. Ч1.
Положить з = О. ЧП. Вычислить е, — активное множество индексов В'е (х) ~ [1] ~! (х) ~ — е„ / Р [1: т]]. ЧП1. Найти решение Ь = Ь, задачи линейного программирования вл-мерном пространстве векторов Ь: найти агд ш!и (7 го (х), Ь) при ограничениях (7~! (х), Ь) ) е„1 ~ де (х) ! [Ь,]< 1, !Е[1: ].
1Х. Вычислить значение ие (х) = (Ч1о(х)~ Ье ). Х. Если а, (х) ( — е„то положить Ье = Ье и перейти к шагу ХЧ1; иначе перейти к шагу Х1. Х!. Если е,( е", то перейти к шагу ХП; иначе положить е,+~ — — ра„з = з + 1 и перейти к шагу ЧП. ХП. Вычислить множество индексов Ууо (х) Ь [1 ] ~! (х) ~ О, ! Е [1: т]]. ХШ. Найти решение Ь = Ьо езадачи линейного программирования в и-мерном пространстве векторов Ь: найти агп ш!п (71о(х), Ь) при ограничениях (Ч$!(х), Ь)~~еО, 1Епо(х); ]Ьс](1, !Е[! ел]. ЫЧ.
Вычислить значение ао (х), ио (х) = (ЧРо (т), Ьо) ХЧ. Если сео (х) = О, то положить х'= хе и прекратить вычисления; иначе положить е,+~ = йе„з = з+ 1, и перейти, к шагу Ч!1. ХЧ1. Вычислить число р (х) ) 0: р(х) = шах [р]!!(х+ ХЬе) (О, ХЕ[0, р], [Е[1: ле]). зоо ХЧП. Вычислить наименьшее число р„е [О, р (х)], удовлетворяющее условию 1»(х+ р„й') = ппп 1е(х+ рй'). ояо,ылв ХЧШ. Вычислить следующее приближение х"+» = х+ р„й".
Х1Х. Положить й = й + 1 и перейти к шагу 1Ч. Теорема 1'. Если выполнены все предположения теоремы 1 и, кроме того, для любой точки х Р Х существует такой вектор й Е ЕВ", что (Ч/~(х), й)(0, 1сое(х), где Ре (х) — множество, определяемое соотнои»гнием Оо (х) 1'.» (1 ( ~~ (х) ~) О, 1 Р [1: т]), то последовательность хе, к', ..., порожденная алгоритмом 1", либо конечна и ее последний элемент х" удовлетворяет условию а, (хе) = О, либо бесконечна и каждая ее предельная точка х удовлетворяет условию а, (х) = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
