XIV Аттетков и др. Методы оптимизации (1081420), страница 61
Текст из файла (страница 61)
При этом предположении матрицу Р удобно записать как блочную матрицу о=(; где 0 симметрическая матрица порядка тп — 1, Я блок размера (ш — 1) х 1, а д элемент матрицы Р, расположенный в ее нижнем правом углу. Аналогичным образом запишем и обратную матрицу где Я вЂ” симметрическая матрица порядка т — 1, Л вЂ” блок размера (ш — 1) х 1, о элемент матрицы Р в левом нижнем углу.
При вычеркивании в матрице А последней строки матрица Р = АА преобразуется в матрицу С. Таким образом, задача состоит в том, чтобы, зная блоки матриц Р и Р определить матрицу С В соответствии с правилами перемножения блочных матриц ~ПЦ находим "Можно показать, что если н матрице А переставить строки, то в матрице АА произойдет одновременная перестановка строк и столбцов с теми же номерами и точно так же преобразуется матрица (АА ) 424 8. ЧИСЛЕННЫЕ МЕТОДЫ где О обозначает нулевые блоки соответствующего размера.
В результате получаем систему матричных уравнений Са+ ЛЛ' =1 Сл+ Яд = О, л'а+дл' = 0, Л'Л+дд =1. (8.89) 1 Из второго равенства (8.89) находим Я = — -СЛ, с помощью Д этого соотношения заменяем Я в первом равенстве. В резуль- 1 т тате получаем СЯ вЂ” — СЙЙ = 1, м или д с(а — 1лл ) =1.... Следовательно, С 1=1) — — ЛЛ . 1 д 1 д= д— (8.90) Первое равенство заменой Л = — дл С 1 преобразуется к виду С~1 — для С ' = 1, 1, что позволяет найти матрицу Я: д=а '+да 'ЛЛ С '.
С помощью уравнений (8.89) можно решить и противоположную задачу: пересчитать матрицу Р ' в случае, когда к матрице А добавляется новая строка. В обозначениях, введенных выше, это означает, что необходимо вычислить матрицу Р 1 при известных С, С 1, Я и д. Из второго равенства (8.89) находим Л = — дС 'Я, откуда, т учитывая симметричность матрицы С, заключаем, что Л = — дЯ С 1. Заменяя Л в четвертом равенстве (8.89), получаем дл С Я = дд — 1, что позволяет найти д: 425 Вопросы и зада 1и С помощью найденных выражений для й, 9 и Я можно записать матрицу В С +да ЯЯ а да Я 1, 9 где 9 определено равенством (8.90). Вопросы и задачи 8.1.
Приведите классификацию численных методов нелинейного программирования на примере решения задачи минимизации выпуклой функции, непрерывно дифференцируемой на замкнутом выпуклом множестве й С Кп. укажите достоинства и недостатки каждого метода, целесообразность применения при различных способах задания допустимого множества й: при помощи ограничений типа равенства и (или) неравенства, линейных и нелинейных.
Н чем состоит принципиальное различие метода условного градиента и метода проекции антиградиента? На каких множествах целесообразно применять каждый из указанных методов нелинейного программирования? 8.2. Дайте определение проекции точки на множество. Как найти проекцию точки на замкнутое выпуклое множество? Покажите, что проекцию точки а у= жо на замкнутое множество й = (а Е Б'.": ~,в — то ~ = 1) можно найти с помощью соотношения (8.21). 8.3.
Докажите, что точка, определяемая равенством (8.23), принадлежит полупространству й* (8.24) и при любых я б й* удовлетворяет неравенству (8.19). 8.4. Докажите, что точка, заданная равенством (8.27), принадлежит множеству й из примера 8.5 и при любых я Е й удовлетворяет неравенству (8.19). 8. ЧИСЛЕЕШЫЕ МЕТОДЪ| 8.5.
Используя метод условного градиента, найдите решение задачи квадратичного программирования с целевой функцией з 1хмхз) = 5х1 +2х,— 1хз+5хз ~— 4ъ215х1+хз) — 8 на множестве 0 < х — 1 < 1, 0 < хз < 2, выбирая различные начальные точки: 10, 0), 10, 1), 11, 2). В условии прекращения итераций ~х~ — хь 1~ < е положить с = 10 ~. Проверьте полученный результат, применив метод проекции точки на множество и выбрав начальную точку 10, 0). Результаты расчетов проиллюстрируйте графически. 8.6. Решите задачу на условный экстремум 2х)+ хз — 4х1 — 2хз — ~ т1п; < 3 2 ъ'5х1+ х2 — 5 = О, выбрав начальную точку хе = 10, — Л), с помощью метода проекции точки на множество и метода проекции антиградиента.
Используйте значение параметра точности е = 10 ~. Дайте сравнительный анализ этих алгоритмов по числу шагов итерационного процесса, необходимых для достижения минимума целевой функции с заданной точностью. Покажите различие процессов минимизации этими методами в случае ограничений ~/5х1+ х~ ~— 5 = 0 и ъ 5х~ + х~ ~— 5 ( О. Дайте графическую иллюстрацию полученных результатов.
8.7. Решите задачу нелинейного программирования 4х, + хз + 2х2 -+ ппп:, 2 з х1+хз — 4хз (О, 2 2 — х1+хз — 2 < 0 методом возможных направлений. Полученные результаты проиллюстрируйте графически. 8.8. Используя метод проекции антиградиента и метод возможных направлений, решите задачу квадратичного програм- 427 Вопросы и задачи мирования х~ + 2х2+ Зхз + х1х2 — 2х1хз + хзхз — 4х1 — бх2 -+ ппп; 2 Д х1 + 2х2 + тз К 4, х„х„"з >О, выбрав начальную точку (О, О, 0). 8.9. Методом внутренних штрафных функций решите задачу квадратичного программирования 1х1 '1) + (х2 о) г шЖ х1+х2 ( 3, — х1+2х2 (4, выбрав начальную точку (О, 0). Графически проиллюстрируйте полученный результат. 8.10.
Используя метод внешних штрафных функций, найдите решение задачи нелинейного программирования < 4х~ — 1х1х2+ х2 — 1 1п1п; 2 г,, 2 х,— х2+2(0, х1+х2 — 6(0, х1,2230, выбрав начальную точку (О, 0). Графически проиллюстрируйте полученный результат. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ Учебники и учебные пособия Алексеев В.М., Тихомиров В.М., Фомин С.В. Онтимвльное управление. Мл Наука, 1979. 429 с. Амосов А.А., Дубинский Ю.А., Кенченава Н.В. Вычислительные ыетоды для инженеров: Учеб. пособ. Мл Высш. шк., 1994. 554 с. Велоусвв А.И., 1"алкин С.В., Герман А.Д. и др. Методы оптимизации в инжерных задачах / Под ред. С.В.
Галкина. Мл Изд-во МГТУ им. Н.Э. Баумана, 1991. 160 с. Васильев Ф.П. Численныс методы решения экстремальных задач. Мл Наука, 1988. 552 с. Волков И.К., Заеоруйко ЫА., Фаликова И.Д. Псевдообрвщение и линейные системы: Учеб. пособ. Мл Изд-во МГТУ им. Н.Э. Баумана, 1980. 26 с. Галкин С.В. Методы решения экстремальных задач.
Мл Изд-во МГТУ им. Н.Э. Баумана, 1986. 52 с. Грелиилев А.А. Прикладные задачи математического программирования, Мл Изд-во МГТУ им. Н.Э. Баумана, 1990. 189 с. Дамбраускас А.П., Кощеев В.А., Кошеве Д.В. Алгоритмы и программы симплексного поиска. Красноярск: Изд-во Краснояр. ун-та, 1993. 160 с. Карманов В.Г. Математическое программирование.
Мл Наука, 1975. 272 с. Лесин В.В., Лисевеч Ю.П. Основы методов оптимизации. Мл Изд-во МАИ, 1995. 341 с. Линейное и нелинейное программирование / Под ред. И.Н. Ляшенко. Киев: Вьпца шк., 1975. 372 с. Моисеев Н.Н., Иванилов Ю.П., Сглоллрева В.М. Методы оптимизации. Мл Наука, 1978. 351 с. Сухарев А.Г., Тимехов А.В., Федоров В.В. Курс методов оптимизации. Мл Наука, 1986.
328 с. Феодосьев В.И. Сопротивление материалов,1 Отв. ред. К.С. Колесников. Мл Изд-во МГТУ иъв. Н.Э. Баумана, 1999. 592 с. (Сер. Механика в техническом университете; Т.2). 429 Дополнительная литература Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание: Пер. с англ. Мл Наука, 1977.
224 с. Аоки М. Введение в методы оптимизации. Основы и приложенил нелинейного программирования: Пер. с англ. Мл Наука, 1977. 344 с. Базара М., Шетти К. Нелинейное программирование, Теория и алгоритмы: Пер, с англ. Мл Мир, 1982. 584 с. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. Мл Радио и связь, 1988. 128 с. Батипдев Д.Н. Методы оптимального проектирования. Мл Радио и связь, 1984. 248 с. Бекишев Г.А., Кратко М,Н.
Элементарное, введение в геометрическое программирование. Мл Наука, 1980. 144 с. Бертсекас Д. Условная оптимизация и методы множителеи Лагранжа: Пер. с англ. Мл Радио и связь, 1987. 400 с. Брайспи А., Хп Ю-Ши. Прикладная теория оптимального управления: Пер. с англ. Мл Мир, 1972. 515 с. Васюхаинский Н. Золотая пропорция. Мл Молодая гвардия, 1990. 235 с. Введение в нелинейное программирование / Под ред. К.Х.
Эльствра: Пер. с англ. Мл Наука, 1985. 264 с. Воробьев Н.Н. Числа Фибоначчи. Мл Наука, 1978. 144 с. Галеев Э.М.,Тихомиров В.М. Краткий курс теории экстремыьных задач. Мл Изд-во Ъ|оск. ун-та, 1985. 201 с. Галкин С.В. Целенаправленные системы в физическо-духовном мире (Мир, жизнь, разум). М., 1999. 284 с. Геминтерк В.Н., Казан Б.М. Методы оптимального проектирования. Мл Энергия, 1980. 160 с. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: Пер. с англ.
Мл Мир, 1985. 510 с. Гвльттейн Е.Г. Выпуклое программирование (элементы теории). Мл Наука, 1970. 268 с. Гроссман К., Каплан А.А. Нелинейное программирование на основе безусловной мннимизапии. Новосибирск; Наука. Сиб. отд-ние, 1981. 183 с. Дамбраускас А.П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
