Главная » Просмотр файлов » XIV Аттетков и др. Методы оптимизации

XIV Аттетков и др. Методы оптимизации (1081420), страница 15

Файл №1081420 XIV Аттетков и др. Методы оптимизации (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска) 15 страницаXIV Аттетков и др. Методы оптимизации (1081420) страница 152018-01-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Для выпуклой комбинации с к = 2 слагаемыми утверждение теоремы верно (оно равносильно определению выпуклого множества). Пусть утверждение теоремы верно для любой выпуклой комбинации, содержащсй а СЛаГаЕМЫХ. ВЫбЕрЕМ В Е ЭЛЕМЕНТЫ Х1, ..., Хк, Хкт1 и произвольные неотрицательные числа а1, ..., аы а1, у1, сумма которь1х равна единице. Отметим, что если аь+1 = 1, то все остальные числа а,, равны нулю и выпуклая комбинация рассматриваемых элементов совпадает с х~+1, так что утверждение теоремы в этом случае тривиально и его справедливость очевидна. ПУсть аь е1(1. Положим Л = 1 — аеа1 и 11, = — ', г = 1, й. Тогда 11, > О, г = 1, Л, и Поэтому, согласно предположению, у = 191 х1 + ... + ф,хя Е Е.

Отсюда заключаем, что а1Х +... +авХ +а111Х Ь и-~-1 =Л(Д, '1+...+9,.х")+(1 — Л) '" = = Лу+ (1 — Л)х~ +~ е Е. Таким образом, произвольная выпуклая комбинация элементов множества Е, содержащая 1+1 слагаемых, принадлежит Е. Согласно принципу математической индукции, любая выпуклая комбинация элементов множества Е принадлежит Е. ~ Теорема 3.2. Пересечение любого числа выпуклых множеств является выпуклым множеством. 1ОО з. луииимизлция выпуклых функций Пусть А — - некоторое семейство выпуклых множеств в линейном пространстве,С.

Рассмотрим множество Пусть х1 и хз принадлежат Е. Тогда они принадлежат любому множеству Р е А. Поскольку по условию множество Р выпукло, для любого Л е (О, 1) элемент Лх1+ (1 — Л)хэ принадлежит Р. А так как Р Е А выбрано произвольно, то Лх'+ (1 — Л)хэ е ( 1 Р = Е. Значит, множество Е выпукло. > Пример 3.4.

Рассмотрим в К" множество Е элементов х = (хм ..., х„), координаты которых удовлетворяют системе неравенств анх1+и1эхз+... +а1„х„< вм а21Х1 + аэз хэ + .. ° + О2пхи < 62, (3.1) а„нт1+ вп12хв+... + а~~,хв ~ (Ьпг Множество Е является выпуклым. Чтобы доказать это утверждение, изменим представление множества. Введем векторы а, = (а,ы ..., а,„). Тогда с помощью стандартного скалярного произведения в Ы' систему неравенств (3.1) можно записать следующим образом: (х, а,) < б„г' = 1, а. Другими словами, множество Е представляет собой пересечение т полупространств. Поскольку любое полупространство является выпуклым множеством, то и множество Е выпукло.

ф Множество .Е с К', заданное системой неравенств (3.1), а также любое конечное пересечение полупространств в евклидовом пространстве будем называть выпуклым мноеоеранным множеставом. 1О1 3. Ь Выпуклые множества Выпуклую комбинацию ст1ж~ +... + стажа элементов линейного пространства назовем стпрозо выпуклой комбинацией, если все ее коэффициенты положительны. В частности, выпуклая комбинация Лж' + (1 — Л)аз строго выпукла, если Л Е (О, 1).

Элемент ж Е Е называют крайней точкой множества Е С ь". (или его вершиной), если этот элемент не может быть представлен в виде строго выпуклой комбинации двух различных элементов из Е. Иначе говоря, если х = Лж~+ (1 — Л)х~, где жт, язз е Е, Л е (О, .1), то жт =;вз = а. Етжи выпуклое множество не имеет крайних точек, то его называют строго выпуклым мнозтсестпв ом. Пример 3.5. У отрезка ~а~,.в~1 б ь" крайними точками являются элементы х и з, и других крайних точек у отрезка нет. В Кз у выпуклого многоугольника крайними точками являются его вершины.

У круга Е С лс,'-', заданного уравнением хт + хз < 1, множество крайних точек представляет собой 2 2 окРУжность Язт + Яз з— — 1. ф Никакая внутренняя точка множества Е С Н" не может быть крайней точкой этого множества. Действительно, если ао б Š— внутренняя точка Е, то существует окрестность* о" = ~х Е лсв: (х — х~! < е), целиком принадлежащая Е. Значит, множеству Е принадлежат элементы а =-:во+со и и =- а — са, где а .. произвольный вектор, для которого ~а~ < 1. Очевидно, что аб = О,осх' +О,баз.

Все линейное пространство —. выпуклое множество. Но, как следует из доказанного, .в этом множестве нет крайних точек. Крайних точек также не имеет аффинное многообразие. Выпуклой оболочкой произвольного подмножества Е линейного пространства ь". называют пересечение всех выпуклых множеств в ь", которые содержат в себе множество Е. *Здесь н далее ~н~ обозначает стандартную норму в кчк элемента ж. 102 з. л!инимизлция выпуклых функций Теорема 3.3.

Выпуклая оболочка множества Е совпадает с множеством всех выпуклых комбинаций элементов множества Е. ~ Покажем, что множество Е всех выпуклых комбинаций элементов множества Е является выпуклым. Выберем в Е произвольные элементы у' и у и рассмотрим их выпуклую комбинац ю у=ау!+(1 — о)у~., Е [О., Ц. Пос о~~~у у" уз ринадлежат Е, их можно представить как выпуклые комбинации элементов множества Е: ь, у'= ~! !!„хо, и=1.,2, где ь., ро)0, 1=1,2, 1=1,й!, '! !!0=1, 1=1,2. ! =-! Подставим эти представления в выражение у = оу! + (1 — а)уз: /С1 й~ у = ~ ор.

х! +~(1 — а)н хэви. В правой части равенства линейная комбинация элементов хо, г = 1, 2, у' = 1, 1!„принадлежащих множеству Е, является выпуклой комбинацией, так как все коэффициенты линейной комбинации неотрицательны, а их сумма равна единице: а!!! +~ (1 — о)!зз, = !=! !=! ь1 ь! =о~~ р!;+(1 — а)Яузу=о 1+(1 — с!) 1=1. Следовательно, элемент у можно представить в виде выпуклой комбинации элементов множества Е, а потому он будет принадлежать Е.

В силу того что элементы у!, .уз и число о Е (О, 1] выбирались произвольно, множество Е выпукло. 1О3 3.!. Выпуклые множества Выпуклую оболочку конечного множества Е С Б'.", содержащего пу+ 1 различных точек х', называют выпуклым мноеоеранником. Если и1, = п, и элементы х'., !' = 1, и+1,. не принадлежат какой-либо гиперплоскости, то выпуклую оболочку множества Е = 1х, ..., хп 1 ) называют симплексом, а точки х' вершинами симплекса.

Отметим, что условие, согласно которому элементы х', .! = 1, п+1, не принадлежат какой-либо гиперплоскости, равносильно линейной независимости векторов х! — х ", 1 = 2, и+1. Согласно теореме 3.3, любую точку симплекса можно представить в виде выпуклой комбинации его вершин. Отметим, что такое представление единственно.

Действительно, если х, ..., х"" вершины симплекса и имеют место предста- вления х=а!х +озх +...+аье!х 1 2 ь-~-! х = Ах +!ггх +... +Ке1х то, вычитая из первого равенства второе, получаем уух + угх +...+ уьеух =О, 1 2 Ь-~-1 4, ! = 1, п,+1, удовлетворяют ра- где коэффициенты у, = о,— венствам и-!-! и-1- ! ~ у, = ~> о, — ~ У1, = 1 — 1 = О. 1=1 Пусть выпуклое множество Р включает в себя Е. Тогда, согласно условию выпуклости, множество Р содержит любую выпуклую комбинацию своих элементов, в частности элементов множества .Е.

Следовательно, множество Г включает в себя множество Е. Таким образом, множество .Е является подмножеством пересечения всех выпуклых множеств, содержащих в себе Е. Но поскольку множество Е само является выпуклым множеством, содержащим Е, .то оно совпадает с указанным пересечением. ° 1О4 3. 81ИНИМИЗггНИЯ ВЫПУКггЫХ ФУЕ)КЦИЙ Предположим, что один из коэффициентов у„например у„т1, тг отличен от нуля. Тогда 71~.1 —— — ", у, и г=1 1 2 к+1 ъх + 72х + " + зь«1 х = 71(х' — х~"')+...+ у (х" — х~«~) =О. (3.2) Так как уь «1 ~ О, то и один из коэффициентов 7„1 = 1, и, отличен от нуля. Значит, в силу равенства (3.2) элементы Х' — Х"+', 1 = 1, Пг ЛИНЕЙНО ЗаВИСИМЫ. ОтСЮДа ЗаКЛЮЧаЕМ, ЧтО существует вектор а, ортогональный всем этим векторам, т.е.

(а, х' — х""1) =О, 1=1, пг или (а, х') = (а, ха~ ), 1 = 1, о. Положим с= (а, х" «1). ТогДа все элементы х', 1 = 1г в+1г УДовлетворяют уравнению (а, х) = с, а значит, принадлежат одной гиперплоскости. Но это противоречит предположению, согласно которому эти элементы являются вершинами симплекса. Пример 3.6. В Рт« симплексом является отрезок (одномернь1й симплекс), в )и треугольник (двумерный симплекс), в тетраэдр (трехмерный симплекс).

Теорема Зей (тпеорема Каратпеодори*). Любую точку х выпуклой оболочки Й произвольного множества Е С )й можно представить выпуклой комбинацией элементов из Ь', количество слагаемых в которой не превышает п+ 1. ~ Каждую точку х Е 11 можно представить в виде выпуклой комбинации Л1х1+... + )г х~ элементов х' Е Е, 1' = 1, ш. Мы можем считать, что число т, ". это наименьшее число слагаемых в выпуклой комбинации элементов множества Я, равной заданному элементу х.

Если гв < и+1, то утверждение теоремы верно. Поэтому предположим, что га > и+ 1. Тогда векторы х' — х1, 1 = 2, ш, линейно зависимы, поскольку их *К. Каратеодйри (1873 — 1980) немецкий математик. 105 3.1. Выпуклые множества количество превышает размерность линейного пространства. Следовательно, верно равенство ги ,'г р (жг — ш') = 0 г.=.2 (3.3) ги и 1г!гв! = О, ~! 12! = О. (ЗА) г=! Поскольку сумма всех коэффициентов рг равна нулю, а среди них есть коэффициенты, отличные от нуля., то р„, > 0 хотя бы для одного номера 1.

Введем параметр а Е К и с учетом равенств !3.4) запишем т т т т ш = ~ Л,т' = ~~ Л,ж' — о~~ !2,ж' = ~(Л, — а!2,)ж'. 13.5) г=1 г=1 г=-1 г=-1 При этом и и и (Лг — о!2,) = ~~ Л, — с!~~ р, =1 — 0=1. г=1 г=1 г=! Подберем такое значение параметра а, при котором линейная комбинация с коэффициентами Л; — 11р, будет выпуклой, а хотя бы один из коэффициентов будет равен нулю. Для этого достаточно выбрать а равным наименьшему отношения> Л,1111; среди тех, для которых р! > О. Обозначим номер выбранного отношения через аз т.е. полагаем сг = Ла,1!гы Тогда Л; — 1111.; > О, 1 = 1, пь Действительно, если для фиксированного номера ! имеем 1гг ~ (О, то !псле Л; — с1Р; положительно как разность положительного и неположительного чисел.

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

Тип файла
DJVU-файл
Размер
2,13 Mb
Тип материала
Высшее учебное заведение

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

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