![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Македонов Р.А.
Классификация оптимизационных задач и способов их решения.( не дай бог кому попадётся!!!) Задача одномерной оптимизации Рассмотрим задачу поиска минимума одномерной функции f( Постановка задачи Если функция f( Методы решения а) Классический метод. Достоинства: простота. Недостатки: 1) имеет ограниченное применение при решении практических задач (практически не имеет применения!); 2) сложность решения уравнения Все остальные методы накладывают ограничения применимости! б) Прямые методы (не требуют вычисления производных функции). Достоинства этих методов – функция может быть не задана в аналитическом виде, не требуется вычислять производные функции. Условия применения – функция должна быть унимодальной. Унимодальной называется функция, имеющая на заданном отрезке [a,b] один максимум или минимум. Основные представители: метод перебора, метод дихотомии (деления отрезка пополам), метод золотого сечения Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем. Разобьем отрезок [a,b] на n равных частей точками деления: xi=a+i(b-a)/n, i=0,...n Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что F(xm) = min F(xi) для всех i от 0 до n. Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n. Деление пополам. Рассмотрим функцию F, которую требуется минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции , которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии eps>0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой к теоретическому значению (b1-a1)/2, и в то же время такое, чтобы значение функции в этих двух точках были различимы.
Алгоритм дихотомического метода для минимизации строго квазивыпуклой фунции на интервале [a1,b1].
Шаг 1. Если bk-ak < l, то остановиться; точка минимума принадлежит интервалу [ak,bk]. В противном случае вычислить pk=(ak+bk)/2-eps qk=(ak+bk)/2+eps и перейти к шагу 2.
|