Многомерные задачи оптимизации (стр. 1 из 6)
3. Многомерные задачи оптимизации. 13
3.1 Минимум функции нескольких переменных. 13
3.2 Метод покоординатного спуска. 14
3.3 Метод градиентного спуска. 14
4.1 Линейное Программирование. 16
Список Литературы
1.1 Визначення.
Під оптимізацією розуміють процесвибору найкращого варіантуз усіх можливих. З точки зору інженерних розрахунківметоди оптимізації дозволяють найкращий варіант конструкції, найкращий розподіл ресурсів та інше.
В процесі розв’язку задачі оптимізації,як звичай,необхідно знайти оптимальне значеннядеяких параметрів,які визначають дану задачу.При розвязку інженерних задачїх прийнято називати проектними параметрами, а в задачах економікиїх называютьпараметрами плана. В якості проектних параметрів можуть бути,зокрема,значення лінійних розмірів обєкта, маси, температурий інше число n проектних параметрів x1,x2,…,xn які характеризують розмірність ( й степінь складності) задачі оптимізації.
Вибір оптимального рішення абопорівняння двох альтернативних розв’язків проводиться за допомогою деякої залежної величини (функції),обумовленої проектними параметрами.Ця велечина називаєтьсяцвілевою функцією(абокритерієм якості).В процесі розв’язку задачі оптимізації повинні бути знайдені такі значення проектних параметрів, при яких цілева функціямає мінімум (або максимум). Таким чином, цілева функція – це глобальний критерій оптимальності в математичих моделях, за допомогою яких описуються инженерніабо экономичні задачі.
Цілеву функцію можно записатиу вигляді:
U=F(x1, x2,…,xn). (1.1)
Прикладами цвілевої функції,які зустрічаються у інженерних та економічних розрахунках,є міцність й маса конструкції,потужність установки, обєм випуску продукції,вартість перевезеньвантажута шнше.
У випадку одного проектного параметра
цілева функція (1.1) є функцією однієї змінної,аїї графік - деяка крива на площині.При 
цілевафункціяє функцією двохзмінних, її графік — поверхня у тривимірному просторі.Слід зазначит, що цілева функціяне завжди може бутипредставленау вигляді формули.Іноді вона може прийматитільки деякі значення,задаватися у вигляді таблиціта інше.В усіх випадках вона повинна бути однозначною функцією проектних параметрів.
Цілевих функцій може бути декілька.Наприклад,при проектуванні виробівмашино- будівництваодночасно потребується забезпечитимаксимальну надійність, мінімальну матеріалоємкість,максимальний корисний об’єм (або вантажопідємність).Деякі цілеві функціїможуть здатися несумісними.В таких випадкахнеобхідно вводитипріоритет тієї чи іншої цвілевої функції.
1.2 Задачі оптимізації.
Можно виділити два типи задач оптимізації — безумовні та умовні. Безумовна задача оптимізаціїскладаєтьсяу відшуканні максимумуабо мінімумудійсної функції (1.1) при дійсних зміннихйвизначеннізначеньаргументів на деякіймножиніσ n-мірногопростору. Звичайно розглядаютьсязадачі мінімізації, що до них легкозводятьсяі задачінапошукмаксимумушляхомзамінизнакацільовоїфункціїнапротилежний. Условные задачи оптимизации, или задачи с ограничениями, это такие, при формулировке которых задаются некоторые условия (ограничения) на множестве
. Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих уравнениям или неравенствам.Ограничения-равенства выражают зависимость между, проектными параметрами, которая должна учитываться при нахождении решения. Эти ограничения отражают законы природы, наличие ресурсов т. п.
в результате ограничений область проектирования
, определяемая всеми проектными параметрами, может быть существенно уменьшена в соответствии с физической сущностью задачи.При наличие ограничений оптимальное решение может соответствовать либо локальному экстремуму в нутрии области проектирования, либо значению целевой функции на границе области. Если ограничения отсутствуют то ищется оптимальное решение на всей области проектирования, то есть глобальный экстремум.
2.1 Задачи па экстремум.
Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=х, заданной на множестве σ, и определить значение проектного параметра х Є σ, при котором целевая функция принимает экстремальное значение. Существование решения поставленной задачи вытекает из следующей теоремы.
Методы поиска экстремума функции f (x) (одномерной оптимизации)
К числу наиболее популярных численных методов одномерной оптимизации относятся: метод Больцано (деления интервала пополам), метод «золотого сечения» и пошаговый метод. Первые два метода ориентированы на поиск ext f (x) внутри фиксированного интервала (а,b) оси х, последний - на поиск ext f (x) в окрестности заданной точки х0.
Метод Больцано при поиске минимума функции f (x) предусматривает следующие действия:1) определяется средняя точка интервала (а,b): с = (a+b)/2;
2) выбирается число 0<d< (b-a)/2 (наиболее популярная рекомендация: d=(b-a)/4) и определяются точки: x1=c-d и x2=c+d;
3) вычисляются значения функции в этих точках: f (x1) и f (x2);
4) если f (x1)<f (x2), то интервал (а,b) стягивается в свою левую половину: b=c, в противном случае - в правую: а=с.
Для нового интервала (а,b) вновь выполняются действия п.п. 1)-4). Процесс деления интервала продолжается до тех пор, пока его длина не станет меньше заданной точности: b-а<e. При завершении процесса поиска за точку минимума f (x) принимается середина последнего отрезка: x*=(а+b)/2.
Достаточные условия сходимости алгоритма метода Больцано:
а) функция f (x) непрерывна внутри интервала;
б) f (x) унимодальна на интервале (а,b), т.е. имеет внутри него единственный экстремум;
в) в некоторой окрестности искомой точки х*f (x) является монотонной
(с одной стороны возрастает, с другой - убывает).
При тех же условиях сходится алгоритм метода «золотого сечения».
Определение: «золотым сечением» отрезка называется его деление на две части таким образом, что отношение длины отрезка к его большей части равно отношению большей части к меньшей.
Следовательно, для отрезка единичной длины: 1/t = t/(1-t) ®t2+t-1=0 ®
Пошаговый метод применяется в тех случаях, когда интервал (а,b) оси х, содержащий точку экстремума функции f (x) неизвестен, но известно, что экстремум находится в окрестности экспериментально найденной точки х0. Этот метод применяется на практике значительно чаще методов Больцано и «золотого сечения», т.к. условие сходимости его алгоритма намного проще: для этого достаточно, чтобы функция f (x) была непрерывна в окрестности т. х0.При поиске минимума функции метод заключается в
следующем:
1) выполняется пробный шаг от точки х0 с целью выбора направления поиска:
x = x0 + x (x ~ 0.5×e) и вычисляются значения f (х0), f (х);
2) если f (х) < f (х0), то величина основного шага, с которым осуществляется движение в направлении убывания функции, положительна (h > 0), в противном случае - отрицательна (h < 0);
3) движение в выбранном направлении с шагом h: xk+1= xk+h, k=0,1,2 ...
осуществляется до тех пор, пока f (xk+1) < f (xk);
4) если f (xk+1) ≥ f (xk), то при выполнении условия h < ε процесс поиска заканчивается, а если h³ε, то шаг дробится: h=|h|/p, p > 1 и осуществляется возврат
к п. 1) с начальной точкой х0 = xk.
В качестве коэффициента дробления шага p используют 2, 3, 5, но чаще всего p = e = 2.71828. По завершении процесса поиска за точку экстремума принимается значение x* =(xk+1 + xk)/2.
2.2 Методы поиска.
Численные методы поиска экстремальных значений функции рассмотрим на примере нахождения минимума функции
на отрезке [а., b]. Будем предполагать, что целевая функция унимодальна, т.е. на данном отрезке она имеет только один минимум. Отметим, что в инженерной практике обычно встречаются именно такие целевые функции.Погрешность приближенного решения задачи определяется разностью между оптимальным значением x проектного параметра и приближение к нему х. Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимого значения а: