Модели и методы решения задач минимизации. Алгоритм метода деформируемого многогранника. Классификация задач и методов. Задача поиска условного экстремума. Правило построения последовательности. Методы нулевого порядка. Метод деформируемого многогранника.
Аннотация к работе
НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВОСТОЧНАЯ ЭКОНОМИКО-ЭРИДИЧЕСКАЯ ГУМАНИТАРНАЯ АКАДЕМИЯ (Академия ВЭГУ)Процессы принятия решений лежат в основе любой целенаправленной деятельности. В научных исследованиях - позволяют выделить важнейшие научные проблемы, найти способы их изучения, предопределяют развитие экспериментальной базы и теоретического аппарата. При создании новой техники - составляют важный этап в проектировании машин, устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере - используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими процессами. Оптимальные (эффективные) решения позволяют достигать цели при минимальных затратах трудовых, материальных и сырьевых ресурсов. В классической математике методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании.Требуется исследовать функцию f(x) на экстремум, т.е. определить точки ее локальных минимумов и максимумов на : Находятся точки локальных экстремумов с помощью необходимых условий первого и второго порядка (порядок условий определяется порядком используемых производных), а также достаточных условий безусловного локального экстремума. , где , m и р-числа; f(x)-целевая функция, ,j=1,..,p - функции, задающие ограничения (условия). Существуют различные методы аналитического решения таких задач, но применение необходимых и достаточных условий безусловного экстремума эффективно для решения ограниченного числа задач. Возможны случаи, когда о целевой функции известно лишь то, что ее значение может быть вычислено с нужной точностью, а сама функция задана неявно. Общее правило построения последовательности {xk } имеет вид xk 1 = xk tk dk, k = 0, 1,… (1.3) где точка x0-начальная точка поиска; dk-приемлемое направление перехода из точки xk в точку xk 1, обеспечивающее выполнение условия (1.2) и называемое направлением спуска; tk - величина шага.В основу метода деформируемого многогранника (метода Нелдера - Мида [J.A.Nelder , R.Mead ]) положено построение последовательности систем n 1 точек ci (k), i = 1, . . Точки системы ci (k 1 ), i=1,…, n 1 на k 1 интерации совпадают с точками системы c I = (k ), i=1 , … , n 1 ,кроме i= h , где точка c h (k ) - наихудшая в системе ci (k ) , i=1, … , n 1 , то есть ¦(ch(k)) = max ¦(ci(k)).Точка ch(k) заменяется на другую точку по специальным правилам , описанные ниже . В результате многогранники деформируются в зависимости от структуры линий уровня целевой функции , вытягиваясь вдоль длинных наклонных плоскостей , изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума . Построение последовательности многогранников заканчивается , когда значение функции в вершинах текущего многогранника отличаются от значения функции в центре тяжести системы CI (k ) ,i= 1, … , n 1; i? h не более чем на e > 0 . Найти вершины нового многогранника: - если ¦ (xn 4) <¦ (x1), то вершина xh заменяется на xn 4 (при n = 2 многогранник будет содержать вершины x1, x3, x6).Поиск методов позволяющих наиболее быстро и с наименьшими потерями времени и труда решать типовые задачи поиска минимума (максимума) является актуальной проблемой, особенно с известным фактом применения этих задач в коммерческих расчетах, для получения большей прибыли.
План
Содержание
Введение
§1. Постановка задач минимизации
1.1 Классификация задач и методов
1.2 Методы нулевого порядка. Постановка задачи и стратегии поиска метода одномерной минимизации