Силаева Т.А. - Методы решения задач оптимального проектирования ВС (774567), страница 7
Текст из файла (страница 7)
Фуякция ?(Х) называется выпуклой па выпуклом множестве Х1?, если для любых двух точек Х и Х этого множества и для любого числа а (О ь а< 1) выполняется соотпошепие ?(аХ+ (1 — а) Х )< аУ( Х)+ (1 — а)У( Х). (2.12) Функция 7'(Х) — строго выпукла, если неравенство (2.12) — строгое при О< а< 1, Хх Х. Функция У(Х) — вогнутая, если функция — ДХ) — выпуклая, Функция ? (Х) — строго вогнутая, если — ДХ) — строго выпуклая функция.
Пример строго выпуклой функция ?'(х) при и= 1 и при любом х приведен на рис. 2.8, а, строго вогнутой — на рис. 2.8, б, пример выпуклой функции для х< х и строго выпуклой для х> х — иа рис. 2.8, е. л .гл Лзс. 2.8 прк условии, что ~(Х) ВАРИАНТЫ ЗАДАНИЯ т, Раа. 9.9 47 Выпуклая функция на замкнутом и выпуклом множестве ХР обладает следующим свойством: ее любой локальный минимум одновременно является и ее глобальным минимумом, а для строго выпуклой функции — и единственным. Любой локальный максимум вогнутой функции на замкнутом и выпуклом множестве ХР является одновременно н ее глобальным максимумом, а для строго вогнутой функции — и единственным. Справедлива т е о р е м а . Для того, чтобы непустое множество ХР= (Х( Ф(Х)< 0~ было выпукло,.достаточно, чтобы все Ч/ (Х) (7'= 1,т) были выпуклыми функциями.
На рис. 2.9, а представлен пример выпуклои функции у (Х) при и= 2. При у (Х) ь 0 получаем, что ХР— выпуклое множество (см. у рнс. 2.9, б). Учитывая данную теорему и определение задачи выпуклого программирования, получаем два вида задачи выпуклого программирования; 1) шш,)'(Х), Ха ХП ХР= (Х! Ч (Х)< О~ при условии, что г(Х) и все у (Х) () = 1, т ) — выпуклые функции; 2) шах у(Х), Ха ХП ХР = ( Х ~ Ч (Х) О 1 — вогнутая функция, а все у (Х) 7 ()'= 1, и 1 — выпуклые функции. Чтобь( определить, является ли функция строго выпуклой или вогнутой, удобно использовать следующяя критерий строгой выпуклости н вогнутости: функция 7"(Х) строго вогнута, если выполняется условие отрицательной определенности ее матрицза Гессе, н строго выпукла при положительной определенности. Остановимся на решении задачи выпуклого программирования, При рассмотрении методов решения задач условной оптимизации функции при ограничениях типа неравенств было сформулировано необходимое условие экстремума функции в виде теоремы Куна — Такера с приведенной в ней системои уравнений и неравенств.
В случае задачи выпуклого программирования данное необходимое условие является также и достаточным. Локальный экстремум (ои же глобальный) определяется в результате решения системы уравнений н неравенств (2.7) — (2.10), если задача выпуклого программирования состоит в нахождении минимума функции 7'(Х), или системы (2.7) — (2.9) и (2,11) при задаче выпуклого программирования на максимум.
Для каждого номера варианта )т'= 1, 20 в табл. 2.1 заданы дле задачи условнои оптимизации. Таблияа 3.1 Окончание табл. 2.1 Продолжение табл. 2.1 ! Номер варианта У Номер варианта )у Первая задача Вторая задача Вторая задача Первая задача ехгг ((х, — 1) + (хг- 1)г), х (.т, — 1)г+ (х г- 2)г= 4 ехгг(х,+ (х + 1) ), х х,+4хг<4,х,>О,х >О. ехгг ((х, — 3)'+ х'г), х х,+ 2хг> 6. (х, — 2) + (х г — 2) ) ( ехгг 4 ) х (х — 2) + (х — 3) = 4 г 15 16 ехгг ((х, е 2) е (х — 2)г), х ( + 3)гл (, 2)г= 4 ехгг ((х, + 3)г+ (х,— 1)'), х х,+х > 1.
2)г+ (х 2)г ) х,>О,х >О. ехгг ((х, — 1)г+ (хе+ 1)г), х (х 3)г+ (х г 1)г 9 ехСг ( (х, — 2)'+ (х + 1)') хг+ хг< 2, хс> О, хгн О. ( г г) хс+ хг> 4. 17 , ( х,+ (хг+ 1)'= 4. ехСг ( (х, — 2)г + (х г 3)г ) 18 ~ х ехгг ((х, + 2)г+ х г ) х 2х,+х >4. ехгг ((х 1)г+ хгг) х х,— хги 3, хсн О, хг> О.
ехгг ((х, + 2) + (х г — 2) х (х, + 2) + (х г- 1) = 4. х ', + (х, — 3)г = 9 ох Сг ( (х 1 — 1) + (х г — 1) ), х (Х1 1) + хг= 4. ехгг ((х, — 3) + (х, + 1)г ), х х,+ хг< 1, х,а О, хг> О ехгг (хг+ (х + 1) ), х ехгг ((х, — 1) е (х г — 1) ), (х 2)г + (х 1)г — 4 х,+ хги 5 ехгг ((х, + 1) + (х — 2) ), х 1 г 3)г ехсг(х',+ хг), х,+ 2хг< 4, х,> О,хг> О. ехгг (х, + (х г л 1) ), х ,+ хг~ 5, х,> О, хг~ О. 2О ехгг (х, + хг ), г гх х 2х~+ хг> 4.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ Для Вашего варианта задания необходимо: 1. Найти решение первой задачи условной оптимизации функции прн ограничениях типа равенств с помощью метода множителей Лагранжа. 2. Изобразить геометрическую интерпретацию применения метода к решению данной задачи условной оптимизации. 3. Найти решение второй задачи условной оптимизации функции прн ограничениях типа неравенств согласно методу, основанному на теореме Куна — Такера, н изобразить геометрическую интерпретацию применения метода к решению данной задачи.
4. Проанализировать результаты н показать их преподавателю. 5. Выполнить на ЭВМ решение каждой из двух заданных задач условной оптимизации функции с помощью различных методов, в том числе итерационных. ехгг (х ~ л 2) + (х г — 2) ) ехгг ((х, + х 2х1+ хг< 4, х (х, + 2) + (х г — 3) = 4 .
ехгг ((х ~ — 1) + (х г — 1) ), х х'+ (х, — 1)г= 4. ехгг ( (х, — 1) х 12 13 х,+ 2х ехгг (х ге хгг), х,+ хг< 4, х,> О, хг> О. ехСг ((х, — 1) + (х г+ 1) ), х (Х1 ) г ехгг ((х, — 2)г+ (х г — 3) ), х (х, — 1)г + (х г — 3)' = 9 . схгг ( (х, + 1)г л х г ), 2хг+ хг> 4. 14 6. Провести сравнительный анализ результатов решения задач условной оптимизации функции разнымв методами и сформулировать выводы. ПРйМЕР Пусть номер варианта задания Л'= 20, Тогда заданы следую- щие две задачи условной оптимизации: 1) ех(г ((х,+ 1) + (,— 2) ), 2 2~ Х (х 1+ 1) + (х 2 — 3) = 4; 2 2 2) ет)г (х 2+ х2), 2 2Ь х хе+ 2хгь 4, Х1> 0 хг~ О. Найдем решение первой задачи по методу множителей Лаг- ранжа.
Данная задача условной оптимизации функции Г(Х) = (х1+ 1) + (х 2 — 2) при ограничении у(Х)= (Х1+ 1) + (х2 — 3) — 4= 0 сводится к 2 2 задаче безусловной оптимизации функции Лагранжа )'(х 1 х 2 А) = (х 1 + 1) + (х 2 — 2) + л( (х 2 + 1) + (х 2 — 3) — 4 ). / Согласно необходимому условию экстремум а функции Ь(хт,х2, Х) получим систему нз трех уравнений: (х1хзр))=2(х1+1)+ 21~ Х1+1 1= 0 ах 1 дЬ вЂ” (х 2, х 2,'ь)= 2(х2- 2)+ 2Х(х2 — 3)= О, д1 — (х,,х2,). ~= ~х,+ 1) + (х2- 3) 2 Ь2 Из первого уравнения системы имеем 2(х ~+ 1)(1+ ь)= О, откуда получаем х~ — — — 1 нли Х= — 1.
Подстановка ь= — 1 во второе уравнение системы приведет к ве имеющему решение уравнению 2 = О, поэтому 2.= — 1 не является решением свстемы. Из второго уравнения системы имеем х 2 — — (Зь + 2 ~/( 1+ ь). Подставив х1 — — — 1 и выражение для х2 в третье уравнение системы, получим квадратное уравненне относительно ),: 4ь + Зь+ 3= 0 2 50 с двумя решениями: 2,= — 0,5 и Х= — 1,5. Подставив их в выражение для Х2, получим два значения х2'. 1 и 5.
В результате имеем две стационарные точки: Х1= (- 1;1) при 2.= — 0,5 и Х2= (- 1; 5) при 2,= — 1,5, Проверим в них выполнение достаточного условия ех1г Ь(Х, Х). Х Для этого находим д21 д 2 (Х ) ) 6(Х, 2д= а,ах, (Х ~) 2+2ь 0 Тогда определители второго и первого порядков будут иметь вид: — О у РР ~=(2 2Х) 2 2) О 2 Ь1 = 2+ 2).. В точке Хт= (- 1;1) имеем 2.= Х(Х )= — 0,5, й = 1> 0 52= 1> О. Поэтому соблюдается положительяая определеяность части б(Х1, ь(Х1) ) матрицы Гессе, соответствующей частным производным второго порядка по Х, т.е. Х~ = Х1 — точна минимума, Г(Х 1) = 1 . В точке Х2 — — (- 1; 5).
имеем ) = А(Х2)= — 1,5, Л1 — — — 1< О, 22-— 1> О. Имеется чередование знаков с отрицательного на положительный, что свидетельствует об отрицательной определенности о(Х2,) (Х2) ), поэтому Х2= Х2 — точка максимума, .Г(Х2)= 9. Рассмотрим геометрическую интерпретацию метода множителей Лагранжа для данного примера, На рис. 2.10 изобраэнм кривую ограничения <р (Х) = (х 1+ 1) + (т 2 — 3) — 4 = О, которой является ок- 2 ружность с центром в точке ( — 1; 3) и радиусом г= 'Г4'= 2. Проведем также дзе касающиесл данной крввой ограничения линна постоянно- | х1> О, х2> О, х1+ 2л2 » 4 'т' 2 (Х ) = — х 2 < О, Ч2(Х) =х1+ 2х2 — 4< О, 2х1 — 2,1-ь )с в = О, 2х2 — ) 2+ 2Хз— - О, -7 х =О, 1 (2,13) (2.14) (2.15) (2 16) ) 2з2= О, ).2( х1+ 2хг 4)= Π— х1< О, — х2< О, (2.17) (2.18) (2 19) х +2 — 4<О, Ъ)» О ~7-1,3) (2.20) Рис.
2.10 Рис. 2Л1 52 ГО УРОВНЯ ФУНКЦИИ У(Х)= (х1+ 1) + (х2 —,2) = 1 и ((Х)= 9. 2 2 Ими будут две окружности с центром в точке (-1; 2) и радиусами г1 — — 1 и ге= Ж= 3. Отметим точки Х1 — — (- 1; 1) и Х2— - ( — 1; 5) касания двух указанных ливий постоянного уровня функции /(Х) с кривой ограничения ср(Х) = О. Двигаясь из Х1 в обоих направлениях вдоль кривой ограничения, получаем, что значение функции г"(Х) будет возрастать по сравнению со значением функции в точке Х1, поэтому Х1 — точка локального минимума.
Точка же Х2 является локальным максимумом, т.к. при движении от нее вдоль ср(Х) = О в обоих направлениях значение функции ('(Х) будет убывать по сравнению с У(Х2). Точки Х' и Х2 являются одновременно н глобальными экстремумами (соответственно минимумом и максимумом) функции 1(Х) при заданяом ограничении 1р(Х) = О, т.к. ((Х1) <,1(Х) и г(Х2) > г(Х) для всех х, припадлежап1их кривой ограничения ез(х) = О. Найдем теперь решение второй задачи условной оптимязацин функции,((Х) = х1+ х 2 при ограничениях типа неравенств 2 2 согласно методу, основанному на теореме Куна — Такера. Приведем ограпнчення к аиду Ч'(Х) < О, умножив на — 1 обе части каждого иэ первых двух неравенств: р (Х)= — х <О, Вначале определим локальный минимум фуякции ~(Х).
Для этого согласно теореме Куна — Такера найдем необходимое условие минимума((Х): Решим данную систему уравнений н неравенств. Пусть 2,2= О, тогда выполняется (2.17). Из (2.13)— (2.18) следует в 1 — 2 1 = х 2 = = 2. 2 = О . Поэтому Х1 = (О; О), = (О; О; О), У(Х1 ) = О: На рис.
2.11 представлена область Х1) допустимых значений Х, задаваемая системой трех ограничений у (Х) ь 0 ()'= 1,3). Исследуя принадлежащую ) ХО е-окрестность точки Х1, получаем, что для любой точки Х данной окрестности выполняется условие У(Х) >)(Х~), поэтому Х~ — — Х~ является локальным минимумом функции ((Х), Других точек, удовлетворяющих системе уравнений и неравенств (2ЛЗ)— (2.20), не существует, следовательно, Х4 — также глобальный минимум функции )'(Х). Для определения локальных максимумов ыо теореме Куыа— Такера находим необходимое условие максимума функции ~(Х), которое нмеет вид: (2ЛЗ) — (2ЛО) и г,,~ о ~)= 1,3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
