И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 37
Текст из файла (страница 37)
Положить й = й + 1 и перейти к шагу 1Ч. «вт Теорема 1. Пусть выполняются предположения 1 и существует конспшнлш а ( оо такая, что (1о) — при х 11 3, и для всех у ~ ~ 3 выполняется неравенство (ч„<р (х, у), х) ) О; (о) при у ч ч Зе и для всех х с 3, выполняется неравенство шах (Чгф(х, у), у)(О; (Че<р(к,уЦ (ог) '1»Р(Х, У)(((Р,(оо, ЧХЧЯ„УСЗЕ. Если шаговые множители р и р» в алгоритме 1 удовлетворяют условиям р»-»+О, р»-~-+ О, р'lр»-»О при к-» оо; Ф О Е р»=~> 2:р;=~ ь-о »-0 и начальное приближение (х', уа) принадлежит множеству Я,х х 8„, то есе предельные точки последовательности (у"), порожденной алгоритмом 1, принадлежат проекции на В множества седловых точек функции ~р (х, у), т.
е. множеству У». Замечание 1. Пусть в дополнение к условиям теоремы 1 множество седловых точек Х'х У» функции гр (х, у) устойчиво лишь по х (т. е. при у* ~ у'» минимум функции 1р (х, у») достигается лишь на точках множества Х*). Тогда алгоритм 1 сходится по переменным х н у к множеству седловых точек Х'х 1'*.
Библиографические упанаиил. Параграф написан на основании работы (2731. 3.17. Квазнградиентвые методы решения дискретных минимаксных задач стохастического программирования 1. Мнннмнаацнн фуннцнн В„ваах ф; (м, еа) сну 3 а д а ч а 1. Найти агд ппп Еи шах 1р,(х, са) для заданных функ»ааа 1а.т ций ~р, 1В" Х И-» В», 1С 'а' и заданного множества индексов Г.
Предположения 1. (1) — функции ~ро 1 Е О непрерывно дифференцируемы по х, причем градиенты по х функции що (с О удовлетворяют при каждом а» локальному условию Липшица 6рг<рю(х, ь») — Чд,(у, ат))(уг(а»)((х — уЦ, (ЕО, с интегрируемой константой Липшица уг (ео), удовлетворяющей условию Еуг (а») ('оо для х, у, принадлежащих замкнутому ограниченному множеству Я; (й) — при каждом а» имеется возможность вычислять значения функций ф, (х, ат), 1 С д и их производных по хг 7»~Р, (х, га), (С а.
183 В алгоритме 1 на й-й итерации за вектор, определяющия направление движения к следующему приближению х»+' (ь»), выбирается тр„ц,» (х" (е), ь»»), где индекс 1» б И удовлетворяет условию <р~ (х", го») = шахтер»(х", ь»»). 1» У Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо~ Е» 11. Выбрать константу 6 ) О такую, чтобы выполнялось неравенство ~п( Е шах ~р, (х, ь») ) Е шах»р, (х, ь») при 9 х 5 ( б ц>ь с»у !еу П1. Положить й = О.
Ос н о в н о й ц и к'л. 1Н. Вычислить ь»» — реализацию случайного элемента ь». Ч. Вычислить индекс 1„, удовлетворяющий условию »р~ (х' (ь»), ь»») = шахтер,(х»(ь»), ь»»). »ЕУ 'ч'1. Вычислить Чг„Н»~ (х» (ь»), ь»»). ЧП. Найти шаговый множитель р,, удовлетворяющий условиям теоремы 1. ЧП1. Если ) х" (е) ) ) 6, то положить х»+' (ь») = х» (ь») и перейти к шагу Х; иначе перейти к шагу 1Х. 1Х. Вычислить х»+~ (О») = х»(ь») — р„тя; (х»(ь»), ь»»). Х. Положить й = й + 1 и перейти к шагу 17. Теорема 1. Если выполнены предполозсения 1 и (И») — Е шах у, х мя Х (х, ь») -». оо при (х1-з-оо; (ро) — фунгщия Е ппп»р; (х, ь») приним,к мает на множестве решений Х» задачи 1 не более чем счетное число значений; (о) — последовательность шаговых множителей (р»)~ ь удовлетворяет условиям р,-»о, й=о, 1, ..., ~',р,=, ~р,~ » ь»-о р»+»1р»-» 1 при й-ь оо, то почти для всех ь» предельные точки последовательности (х» (ь»))» о, порожденной алгоритмом 1, принадлежат множеству решений Х* задачи 1.
189 2. Мюппаязачяа фтвицаи шах К««р~ (о, а) соо 3 а да ч а 2. Найти агд пйп шах Е~р, (х, а) для заданных функ«ея«ЫЯ ций а,: Л" Х И вЂ” ~ В', (Е О и заданного множества индексов О. Предположения 2. Функции ф, (х, а), 1~ О и распределение в таковы, что выполняются следующие условия: (1) — существует константа 6 ( оо такая, что (Ч1, (х), х) ) О для ) х1 ) 6, где ~, (х) ЬЕ«р, (х, в); (й) — градиенты функций ~, (х), рсР, удовлетворяют локальному условию Липшица 1Ч~;( ) — Чр;(РНАЯ<У,!! — И Уг< для всех х, у, принадлежащих произвольному замкнутому ограниченному множеству Я; ((и) — при каждом а имеется возможность вычислять значение функций ф, (х, в), 1 ~ О и их производных по х — Ч«<р, (х, в), (ЕЙ.
В алгоритме 2 на й-й итерации за вектор, определяющий направление движения к следующему приближению х"+' (в), выбираетси Ч,~Р~г (х" (в), в'), где индекс 1, Е Р УдовлетвоРЯет Условию = шах г~ (здесь при каждом 1 Е У вспомогательная последова« агу тельность чисел (г1)«. о обладает свойством г; — 1, (х" (в)) -«О при я -«оо), Алгоритм 2 Н а ч а л о. 1.
Выбрать константу 6 ) О, удовлетворяющую условию (1) предположения 2. 11. Выбрать произвольное приближение х' ~ В", удовлетворяющее условию ~! х' ) ( 6. 111. Выбрать произвольные числа гг, (Е У. 1Ч. Положить й = О. Ос но в н о й ц и к л. Ч. Вычислить индекс 1„Е О из условия г~с, (в) = шах гс (а). КУ' Ч1. Вычислить в" — реализацию случайного элемента в. ЧП. Вычислить 7«<р;„(х«(в), а"). Ч111. Найти шаговый множитель р, и параметр ов удовлетворяющие условиям теоремы 2. 1Х. Вычислить следующее приближение х', если 1х«(в) ) ) 26; (а) = х'(а) — р«Ч,фс,(х'(в), в'), если ~1х" (а)(!(26. Х. Вычислить значения величин г,"+' (в) = г«(в) + оь(~р;(х«(в),' в«) — г~(а)), (ЧУ.
Х1. Положить й = й+ 1 и перейти к шагу Ч. Теорема 2. Если выполнены предположения2 и (ю) — Е!~р, х зс (х, го)/а( оо, Е"1Ч,гр,(х, го)1а(оо, (ЕО; (о) — последовательности шалавых множителей (рь)ь о и параметров (оь)а"=о удовлетворягот условиям ра>О, (г=О, 1, ..., О(оь(1, й=О, 1, ...~ 60 ОФ ~.' от< рь(оа- 0 при (г-» оо, рь+1!рг-» 1 при я — » оо; (ог) — Функция шах Е~р, (х, то) принимает на множестве решений Сея Х» задачи 2 не более чем счетное число значений, то почти для всех го предельные точки последовательности (хь (го) ) а=о, порожденной алгоритмом 2, принадлежат множеству решений Ха задачи 2.
Библиогри4~ичгокиг уаиония. при иаппсапиа параграфа испольаоаались работы (1бз, 2721. Часть 11 МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИ Глава 4 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача линейного программирования является задачей условной оптимизации, в которой целевая функция и функции ограничений линейны: найти агд щах 2, с,х, при ограничениях л д ! ад,х, + а„хв + + аглхл = авд; а,~хд+а Лхв+ ° ° ° + а,лхл = ал; о алч+дихд + алч+гдхд + ' ' + алч+ьлхл < алч+д~ (4.1) а ~хд + алах, + ° ° ° + а лхл < а', т,(т; х1~0, /=1,2, ...,и;, и(и, (4.2) хл,~О; х"„+,~0; х„,ч ~ = х'„+, — х"„+„х„'+, в О, хл,+2 = хл+д — хл+дл хл+в ~ О~ хл = х'„— хл, х„' ~д О, х"„~ О, то общая задача линейного программирования сведется к эквива- лентной канонической задаче: найти ага гпах (с,х, + ° ° ° + с,,х,, + слд.ы (хл+, — х„+,) + ° ° ° + сл (х„' — хл)) 192 для заданных с = (сд, св, ..., сл); аи, д = 1, 2, ..., т, 1 = 1, 2, ...
..., и; а' = (аль ась ..., а~). Ограничения (4.1), заданные в виде равенств и неравенств, называют общими; ограничения (4.2) — прямыми. Задача линейного программирования называется канонической, если в (4.1) т, = т и в (4.2) и, = и,т.е. если общие ограничения состоят из равенств, а требование неотрицательности распространяется на все переменные хь / = 1, ..., и. Если ввести дополнительные переменные х +д, ..., х„+ щ н сделать замену при ограничениях а х + ° ° ° +аьчх„, + аь„,+~(х„'+, — х"„+,)+ °" +аь (х„' — х„) =по,; а пх, + ° + а„,„,х„, + а о„,+~ (х'„+, — х'„'+,) + ° ° ° + а„,,„(х„— х„") ° ао; а~, 1 ь1хо + ' ' + ав,+ьл,хл, + аи,+ьл,+1 (х„+~ х„+1) + ° ° ° + а,+1,„(Х'„— Х"„) + Хп.1 ~ а~ +,', а пх, + "° +а„„„х„,+ а„,,ч+1(х'„+, — х"„+,)+ " ° + а„(х„' — х"„) + х„+, ао„.
Каноническая форма задачи линейного программирования является наиболее простой и удобной при построении вычислительных алгоритмов. Большинство приводимых в этой главе методов относится к канонической задаче линейного программирования. Те случаи, когда решение задачи с естественной формой записи сокращает трудоемкость численного анализа, будут рассмотрены вместе с соответствующими модификациями алгоритмов. 4.1. Симплекс-метод и его варианты 3 а да ч а О.
Найти агн шах (с, х) для заданного вектора с = кех = (с„..., с„) и заданного множества Х~(х1Ах=по, х~О, хЕВ"), здесь А — матрица размера по х и: аи аго,, аы А аоо и ''' ~ оо (по по по) а ~ а„о...а Столбцы матрицы А обозначаются через а', ао, ..., а". Предположения О. (о) — ранг матрицы А равен гп; (И) — и ) по; (ооо) — множество Х непусто.
Определение 1. Допустимое решение х (т. е. вектор х Е Х) называется опорным решением задачи О, если система векторов а/, соответствующая его положительным компонентам (х1 ) О), линейно-независима. Определение 2. Базисом опорного решения х называют систему т линейно-независимых векторов, которая включает все векторы а1, отвечающие положительным составляющим опорного решения х. 193 7 о-зо ГОпределение 8.
Опорное решение х называется невырожденным, если число его положительных компонент равно хч (если оно мень- ше и, то опорное решение называется вырожденным). . Определение 4. Каноническая задача линейного программирова- ния называется невырожденной, если все ее.опорные решения не- вырождены. Определение 5. Компоненты опорного решения, отвечающие век- торам его базиса, называются базисными, а остальные — небазис- ными. В' дальнейшем базисные векторы будем обозначать через а ', а ', ..., а с с сап[1'и) й 1, ..., пс. Базисные векторы а'а характеризуются номером с, и позицией й, которую он занимает в базисе.
Матрица В, составленная из векто- ров а', а", ..., а'м, называется базисной (ис, и'„,) В симплекс-методе решение задачи 0 начинается о известного опорного решения и его базиса. На каждой итерации алгоритма проводится проверка опорного решения на оптимальность. Если опорное решение не оптимально, то указывается способ, позволя- ющий по данному опорному построить другое опорное решение, более близкое к оптимальному.
Через конечное число итераций ли- бо находится решение задачи О, либо устанавливается неограничен- ность целевой функции задачи 0 на множестве Х, 1. Симплекс-метод ретпеккк иеиыромдепкой иаковикеекой аадаии ливейвого программироаавви Алгоритм 1 Н а ч ало. 1. Найти опорное решениех' (хс, ..., х„') задачиО, базис ас, ас*, ..., ас этого опорного решения и вычислить матрицу В ', обратную к исходной базисной матрице В, состоящей из столб- Обычно на'практике находят опорное. решение, которому соответствует единичный базис а' = (1, О, ..., 0)г, ..., а' = (О, О, ..., 1) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
