Главная » Просмотр файлов » И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации

И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 80

Файл №1121207 И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации) 80 страницаИ.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207) страница 802019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 80)

Если для всех 1~ (1, ..., и)',Я выполняется неравенство (а~, и)+ (дс, Я~у — с)~ О, то вычислить оптимальное решение х'= (хь ..., х„) задачи 5 /уи если 1сп, (О, если 1Я О, и прекратить вычисления; иначе положить| = Г1 и перейти к шс» гу 1Ч. 1Ч. Найти индекс й Е (1, ..., п)~~ й', для которого выполняется неравенство (а~, и)+(д», ~ту — с) О. Ч. Положить О = й [[ (й).

Ч1. Найти вектор у, координаты которого ур 1 ~ Р, вычисляются по правилу у; = у, при всех 1Ев'; д,=о и перейти к шагу Х1. ЧП. Вычислить максимальное значение Х ~ [О, 1), при котором )д+(1 — Л)д>О, и положить г~ —— Ху;+(1 — Цуи 1ед. ЧШ. Положить И = Э. 1Х. Найти множество Ф, состоящее из тех индексов й е 0', для которых г, = О и положить И = В" й. Х.

Вычислить вектор у, координаты которого находятся по правилу У! = хи 1 с и > и перейти к шагу Х1. Х1. В соответствии с множеством а составить подматрицу Вд матрицы А и подматрицу Ят матрицы 6. ХП. Найти решение (у, и) системы линейных уравнений В,д=Ь; В~и+ Я~~9ту = Я~с и перейти к шагу П. /1~ найти агдш(п ( — Ь)А)~ ) о,х) х (5.116) при ограничениях 1=1, (1, х)~0, (6.117) Если выполняется неравенство ( — Ь1А) ~ О, то задача 5 не имеет допустимого решения; если ( — Ь1А) „= О, то х* удовлетворяет условиям х'~ 0 и Ахь= Ь.

$ Если х"рь О, то множество столбцов аг, для которых х) ) О линейно-независимо и вместе с соответствующими столбцами д1 образует начальную матрицу 11л ) алгоритма 5. ~ь| Отметим, что для решения задачи (5.116) — (5.117) можно использовать алгоритм 5 с начальной матрицей ~~ /, равной! Ь).

Замечание б'. Для решения систем линейных уравнений (5.114) и (5.115) в [524) предлагается следующий способ. Пусть ~ ) имеет размер (т + 1) х г. Тогда у и и определяются 437 Теорема б. Пусть существует множество индексов Р с= (1, ... (В '1 ..., и) та е, что матрица ~ ) имеет полный столбцовый ранг ~ь1 и система (5.1И) имеет решение (у, и), для которого у ) О, и пусть каждая матрица Вт, получающаяся в результате применения алгоритма, имеет полный строчный ранг.

Тогда за конечное число итераций алгоритма б вычисляется оптимальное решение х* задачи б. )'в ') Замечание б. Для получения начальной матрицы ~, ~,опнсан~ь,) ной на шаге 1 алгоритма 5, необходимо предварительно получить решение (1Р, х") следующей задачи квадратичного программирования: с помощью решения треугольных линейных систем о(Ь вЂ” и)=й; [ту=г[ для (ь — и) и у, где с[ = Русто -[- Уй й = ~ ть — ~тРУото; [[ув = л5; л — т х т-матрица с ортогональными столбцами и о— т (В ~ верхняя треугольная невырожденная т Х т.матрица, ~О~[ =йр[т, йт— у/ — (т + 1) К т-матрица с ортогональными столбцами, [т — верхняя г 1ув1 треугольная невырожденная т Х т-матрица, йт = 1[у ), йтв — имеет т строк, [[70 — имеет [ строк.

Библиоера»»ические ркаюиия. Прн написании параграфа использовались ра. боты [209, 320, 523, 5241. Дополнительные сведения о методах решения задач квадратичного программирования можно найти в работах [35, 310, 311, 437, 461, 467, 473, 507, 5461. Глава 6 СПЕЦИАЛЬНЬШ МЕТОДЫ РЕШЕНИЯ МИНИМАКСНЫХ ЗАДАЧ И МЕТОДЫ ОТЫСКАНИЯ СЕДЛОЕЫХ ТОЧЕК 6.1.

Методы последовательных приближений решении дискретных минимаксных задач 1. Микимаксиаа аадача с ограничениями простой структурм Зада ч а 1. Найти зги ппп гпах гр; (х) для заданных функ«ех гау ций ~р,: В" — В', 1~ й, заданного множества индексов й и заданного множества ограничений Х ~ В". Предположения 1.

(4) — функции фо 1 ~ й — непрерывно дифференцируемы; (й) — множество Х вЂ” выпукло и замкнуто. Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение х' ц Х. П. Выбрать константы а, ) О и ае ) О. П1. Положить й О. О с н о в н о й ц и к л. [Ч. Найти множество точек Х» = (х [$ х — х» ~[, ( 1, х Е Х), где [[у[[, = шах [уг[. гтн:«1 Ч. Вычислить множество индексов Оье(х") = (1)<р,(х») = шахтер;(х»), Рь,й).

геу 433 Ч1. Вычислить »Р(х») = пйп шах (Ч«о, (х»), х — х»). «в» ~вас«~» ~ ЧП. Если ф(х») = О, то положить х»= х» и прекратить вычисления, если ф (х') ( О, то перейти к шагу ЧШ. ЧП1. Положить 1' = О. 1Х. Положить з = е/. Х. Вычислить множество индексов Я» (х") = (1) шах ф; (х») — »р, (х») ~( е, ! Е О). сет Х1. Вычислить ф«(х») = ш)п шах (Чф;(х»), х — х»). «сх»»ея »<«»> ХП. Если выполняется неравенство ф, (х») ( — а»е/е„то перейти к шагу ХШ; иначе положить е/~.~ = ег/2, 1 = /+ 1 и перейти к шагу 1Х.

(выход из цикла, определяемого шагами 1Х вЂ” ХП, будет осуществляться за конечное число итераций при каждом й = О, 1, ...). ХП1. Вычислить точку у', удовлетворяющую условию ф«(х») = шах (Ч~й (х»), у» — х»). ~еуге<«»ъ Х1Ч. Вычислить шаговый множитель р» из условия гпах»р, (х»+ р»(у» — х»)) = ш)п шах»р, (х»+ р(у» — х»)) »е.у »ааи»е~ ХЧ. Вычислить следующее приближение х»+' = х» + р» (у» — х»). ХЧ1.

Положить й = й + 1 и перейти к шагу 1Ч. Теорема 1. Если выполнены предполт»гения 1 и начальное приблиаеение х' в алгоритме 1 таково, что множеппво Х(х') = (х) шахтер,(х)(шах»р,(х»), хРХ) %.т»иу' ограничено, то любая предельная точка х* бесконечной последовательности (х»)» о, порожденной алгоритмом 1. является стационарной точкой функции шах ~р, (х) на множеспые Х. «еу Замечание 1. Основная трудность в применении алгоритма 1 связана с вычислением значения»р, (х") на шаге Х1. В П271 показано, что если Х» — строго выпуклое множество и начало координат не принадлежит выпуклой оболочке 1., (х»), натянутой на векторы Чф; (х»), 1 ~ Ж, (х»), то задача вычисления ф» (х») сводится к более простой задаче максимизации на /.» (х») непрерывно дифференцнруемой функции О(г) Ьпп1п(г, о — х»), »сх градиент которой 70(г) = о(г) — х", где о (г) Е Х" удовлетворяет условию 0 (г) = (г, о (г) — хл).

2. Первый метод последовательных приалимеввй решении мивпмаиеной еадачи е отравпчевввмв типа веравевета 3 а д а ч а 2. Найти агн ппп гпах фг (х) для заданных функций тях гое ~рг: В -~ лгг, г ~ И, заданного множества индексов гг и множества ХЬ(х!Рг(х)~(О, (бды хбгг ! Предположения 2. (1) — функции гро (ŠΠ— непрерывно дифференцируемы; (й) — функции!и ! ~ О,— выпуклы и непрерывно дифференцируемы; ((м) — выполняется условие Слейтера 1п1 гпах !, (х) ( О. *зн" 'Ж В пунктах 2 — 4 приводятся методы последовательных приближений для нахождения стационарных точек х* функции игах ~р, (х) гця на множестве Х.

Точка х' Е Х называется стационарной точкой функции игах гр, (х) на множестве Х, если многогранник Е (х') содержит нагну чало координат (здесь Е(хе) = са Н (х*), Н" (хе) = Н (х") () Н, (хе); Н(х*) = (7гр,(х'), гЕЯе(х*)); Н,(х') = (7Р,(х*), !6Яе(хе)); Яе(хе)= ((/пгах<р,(хе) = <р,(хе), (ЕО); кет Яе (х') = (! ! Рг ( ') = О, ! Е гг,)). Если игах гр, (х) выпукла на Х, то стационарная точка х' является гне точкой минимума. Алгоривтле 2 Н а ч а л о. 1.

Выбрать начальное приближение х' б Х. 11. Выбрать константы е,) О, р,) О, ае) О. П1. Положить й = О. Основ но й ци кл. 17. Найти множества индексов оьо(х") = (1!гпах~р,(х') =<рг(х"), ЕЕИ)1 з.т Яе (х') = (! ! Рг (х') = О, ! Е О,!. Ч. Вычислить множество векторов Н,(х') = Н,(х') () Но(х'), где Но(х') = (7<р, (х'), ! Е Жо(х")); Нз(х') = (7/~(х'), /ЕД,(х')). Ч1. Используя алгоритм !' (см. з 3.!2), определить, принадлежит ли начало координат многограннику /.00 (»"), который является выпуклой оболочкой, натянутой на множество векторов Н„(»»). Если начало координат принадлежит многограннику 1.„(»»), то положить х" = х» и прекратить вычисления; иначе перейти к шагу ЧП.

Ч!1. Положить з = О. ЧП1. Положить е = в„р = р„а = а,. 1Х. Найти множества индексов Я. (х') = (! ! шах ср, (х') — ~р, (х') ( з, ! Е г/); азу ! !в (х ) = (!! — р ~ (/! (х") (~ О, ! Е пд). Х. Вычислить множество векторов Й „= Н, (хь) (! Ня (хз), где множества Н,(х») = (Чц,(хз), !ЕЯ,(хь)); Н„(х") = (ЧР!(х ), !'Ей(х')), Х1. Используя алгоритм 1" (см. % 3.12), вычислить точку г, ближайшую к началу координат точку многогранника /., (х»), который янляется выпуклой оболочкой, натянутой на множество векторов Неа (» ) ° ХП.

Если выполняется неравенство ~!г„, ~! в и, то перейти к шагу Х1П; иначе положить з,.!.~ = е,/2, р,+~ = р,/2, а,.!~ = = я,/2, з = з+ ! и перейти к шагу Ч(П. ХП1. Вычислить вектор Ьц, (х") — направление (е, р)-квазина- искорейшего спуска функции шах ~р,(х) в точке х~ по формуле сну Лая(х ) = (!4!зея1!)зер. Х1Ч. Вычислить шаговый множитель р», удовлетворяющий условиям так ~р! (х" + р„йэя (х»)) = пип шах <р, (х" + рй.а (х')); ге,т р>0 ~ну + Радея (хь) Е Х. ХЧ. Вычислить следующее приближение хе+' = х" + р,п„в(х"). ХЧ1. Положить й = й + 1 и перейти к шагу 1Ч.

Творема2. Если выполнены предположения 2 и начальное приближение хе б Х таково, что множество Хеьь(хашах ф,(х)(шахф,(х'), хЕХ) ьту 16у ограничено, то любая предельная точка бесконечной последовапыльности (хе)е с, порожденной алгоритмом 2, ягляется стационарной точкой функции гпах ф, (х) на множестве Х. 'еу 3. Второй метод иоследовательиьтл ираблвмеввй решевиа минамансной вадачн с отравачевалми тина неравенств Алгоритм Я Н а ч а л о. 1.

Выбрать начальное приближение хс Е Х. П. Выбрать константы е) О, р, ) О П1. Положить й = О. Основной ц и к л. !Ч. Найти множества индексов нее (хе) = (1 ~ |пах ф, (хе) — ф; (хе) ( е, 1 Р О); 'ВУ Яе (х") = (1'! р ~ ~Ру (х ) » <О 1 Е ~ь). Ч. Вычислить множество векторов Осв = Ос(» ) () ~(а(х )ю где множества Не(хе) = (Чр,(х'), (6 Же(х')); Н„(хе) =~Ч1!(х"). 169с(х')). Ч1. Используя алгоритм 1' (см.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6499
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее