Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.)), страница 6

Решаемая задача условной оптимизации функции 1(Х) при ограннченвях типа неравенств имеет следующий вид: в векторной форме Соотношение между т и и может быть любым. Если условие задано в ввде ~~ (Х) > О, то, умножая обе части данного неравенства на -1, переходим я неравенству типа (2.б) со знаком «<г< — цг (Х) < О.

При решенви задачи нелинейного программированвя з общем случае повск глобального экстремума затруднен, тан как задача нелинейного программирования может иметь несколько локальных экстремумов, Это справедливо каи для задачв безусловной оптвмнзации, так и для зэдачв условной оптимизации, з том числе при ограничениях типа неравенств, даже в случае, когда оптимизируемая фунвцвя без учета ограничений имеет только один экстремум.

Проиллюстрвруем это на рис. 2.3, где изображены линии постоянного уровня фуввции Г(хз,х2)= с„(о= 1,3, причем сз> с2> сэ) и заштрихованная область Х1) допустямых значений Х, задаваемая системой трех ограниченвй типа неравенств (Х)> О (1= 1,3). Функция 1(Х) имеет безусловный миии« мум в точке ХЗ н два локальных минимума Х~ и Х2 в качестве решения задачи условной оптимизации функции 1(Х) при заданных ограничениях типа неравенств. В случае нескольких локальных экстремумов среди них выбирается глобальный минимум и/влв максимум на основе сравнения значений функции а локальных экстремумах. Рассмотрим методы нахождения локальных экстремумов.

1. Классический метод решения задач условной оптимизации при ограничениях типа неравенств Алгоритм решения задачи условной оптимвзацин функции 1(Х) при ограничениях типа неравенств согласно классическому методу состоит в следующем. 1. Определяем безусловный экстремум функции 1(Х), необходимым условием которого является равенство нулю всех частных ау производных первого порядка (Х)= О ()= 1,п ). При этом а,. получаем стационарные точки. 2.

Среди стационарных находим точки, првачдлев«аа«ие области Х1). Среди них ищем точки экстремума. Условием минимума ( аи снмума) функции 1(Х) в точке будет положительная (соответственно отрицательная) определенность матрицы Гессе з этой точке. 3. Если все стационарные точки не принадлежат области Х1) или являются точками перегиба„то точки экстремума ищем на границе этой области (где Ч' (Х) = О). Среди граничных точек выбираем те (нли ту) точки, в которых функция 1(Х) принвмает наименьшее н1нлн наибольшее значение.

Эти точки и будут локальными условными экстремумами. 4. Конец алгорвтма. Точка называется граничной точкой множества„если любая ее е-окрестность содержат как точки, принадлежащие этому множеству, так и не принадлежащие ему. Геометрическая интерпретация классического метода решения задач условной оптимизации функции г'(Х) при ограничениях типа неравенств представлена на рис. 2.4, а и б. Изображены ликии постоянного уровня функции ~(х1, х х) = с „(о = 1, 3, причем е1> сз> сз )' и две различные заштрихованные области Хс) и Хб~ допустимых значений Х, задаваемые системой трех ограничений типа неравенств.

На рис. 2.4, а условный минимум Х„функция,у(Х) совпадает с безусловным Хэ. На рис. 2.4, б а) безусловный минимум Хе функцви У(Х) не првкадлежвт области Х01, поэтому задача условной оптимизации имеет решение в точке Х„х Хе. Этот условный экстремум Х лежит на границе области Х1)1, и в нем достигается наименьшее значение функции У(Х) в этой области. Классический метод основав на следующих двух теоремах. Т е о р е и а 1 (Вейерштрасса). Если функция )'(Х) непрерывна и определена на непустом, замкнутом и ограниченном множестве Х(), то функция в атой области принимает по кравней мерв один раз наибольшее и наименьшее значение. Т е о р е и а 2.

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

2. Метод, основанный на теореме Куна — Такера Кроме приведенного выше алгоритма для поиска локальных экстремумов, можно также использовать теорему Куна — Такера, которая дает необходимое, ко ве достаточное условне экстремума функции Г(Х) прв решении задачи (2.5) — (2.6) условной оптимизации функции при ограничениях типа неравенств. Рнс.

2.4 40 41 при Х, в которых Ч' (Х) < О, в противном случае. О ,'> а у. (Х) оз(Х) = (2.7) , 1= 1,п), (2.8) (2.9) (2ЛО) Раа 2.6 д. Метод пгтрау1ных функЧий 4. Методы случайного по сна '?(Х) = У(Х)+ ю(Х), Т е о р е м а К у н а — Т а к е р а. Необходимое условие мнннмума функции 1(Х) прн ограничениях Ч' (Х)ь О имеет ввд: ~а- (Х)+ Х А. — (Х) = 0 а ч'. ахг ' дх, 7=1 Х.ц~.(Х)= О (у'= 1,т), чг . (Х ) < 0 (,1 = 1, т ), Х.> 0 (1= 1,т~.

Необходимое условве максимума функцив ~(Х) прн ограничениях Ч' (Х) < 0 выест ввд: (2.7) — (2.9) и йу< 0 ()= 1,т~. (2Л1) Решая систему (2.7) — (2ЛО) уравнений н неравенств, получаем стационарные точки, среди которых могут быть локальные миянмумы, Напомним, что точка Х называется локальным минимумом функции 7'(Х), если существует такая е-окрестность атой точки, что для любой точки Х данной окрестности выполняется условие У(Х)а У(Х'). Для локального максимума У(Х) ь ~(Х"). Решеянем системы (2.7) — (2.9) и (2.11) уравнений и неравенств являются стационарные точки, среди которых могут быть локальные максимумы.

Данный метод обладает недостаточно хорошей сходимостью в используется в основном для нахожденвя первоначального приближения Х( ). Согласно методу штрафных функций задача (о) (2.5) — (2,6) условной оптимизацвв функцви У(Х) 'при ограничениях тапа неравенств сводится к задаче безусловной оптвмизацвн вспомогательной функции где ю(Х) — штрафная функция, нмеюгцая вид: 42 Константы а. ( ) = 1, т ~ выбираются положительными при поиске мннимума функции ~(Х) (отрицательными прв максимуме) и достаточно большвми с тем, чтобы штрафная функция быстро возрастала при невыполнении ограничений. Геометрвче~чая интерпретация метода штрафных функций прн п = 1 и т= 1 ~ч е.

прв решеннв задачи тягл ~(х) ) приведег ч (.т) я о на иа рис. 2.6. Минвмум '7(ь), а, значит, н У(х) при чг(х)< О, досткгается в точке х Для решения задачн (2 5) — (2ч) условной оптимизации функция 7'(Х) при ограничениях типа нер'-.- -- используются описанные ранее (в первой лаборатоРной Р" " - енвн задач аботе пт. безусловнои оптимизации) все мргоды сяучанного чо только с некоторым отличвем: суазу "ос"е з после нахождения Х в 1.

() а Х(~ ~ согласно зтнм методам леал горвтмов определения я ред п.З вычисляем Ч'(Х) и проверяем выполнение условия Ч'(Х) < О, Если оно выполняется, т.е. Хв ХВ, то переходим к 43 п. 3 указанных выше алгоритмов. Если же Ч~ (Х)> О хотя бы при одном ?, то полученное Х отбрасываем и переходим к и. 1 алгоритмов. Задачи еыпуклоео проераммироеания и их решение Задача нелинейного программирования в общем случае может иметь иесколько локальных экстремумов с различными зпачениями функции в пих. Поэтому в общем случае найти глобальный экстремум затруднительно, так как для этого вначале надо найти все локальные экстремумы.

Но в частном случае, когда задача яелииейиого программирования является задачей выпуклого программирования, ее любой локальный экстремум одковремепио будет и глобальным, а зачастую и едииствепкым. Задача выпуклого программироваяия представляет собой задачу нахождения ш)п ?(Х) или шах г(Х) при условии, что Хе Х?? Хе Хд ?(Х) — выпуклая функция прв поиске ее минимума и вогнутая функция при максимуме, а допустимое множество Х(? является замкнутым и выпуклым. Множество Х1? пазывается выпуклым, если вместе с любыми принадлежащими ему двумя точками Х и Х этому множеству г прииадлежит и соедикяющвй их отрезок 2= ~Х, Х1, т,е.

любая точка ~сгХ+ (1 — сг) Х )е Х??, где О < а~ 1. Пример выпуклого множества при и= 2 представлеи ка рис. 2.7, а, а иевыпуклого множества — ка рис. 2,7, б. К выпуклым множествам, в частности, относятся отрезок, прямая, круг, треугольник, прямоугольник, плоскость, полуплоскость, эвклидово пространство.