Программирование численных методов: нахождение минимума функции методом деформируемого многогранника

Размещено на http://www.allbest.ru/

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВОСТОЧНАЯ ЭКОНОМИКО-ЭРИДИЧЕСКАЯ ГУМАНИТАРНАЯ

АКАДЕМИЯ (Академия ВЭГУ)

Специальность 230700 Прикладная информатика (в экономике)

Специализация - Информационные системы в бухгалтерском учете и аудите

КУРСОВАЯ РАБОТА

Программирование численных методов: нахождение минимума функции методом деформируемого многогранника

Шафигина Лилия Маратовна

Уфа 2011

Содержание

Введение

§1. Постановка задач минимизации

1.1 Классификация задач и методов

1.2 Методы нулевого порядка. Постановка задачи и стратегии поиска метода одномерной минимизации

§2. Метод деформируемого многогранника

Заключение

Список используемой литературы

Приложение

ВВЕДЕНИЕ

Процессы принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных организаций, обеспечивают их оптимальное функционирование и взаимодействие. В научных исследованиях - позволяют выделить важнейшие научные проблемы, найти способы их изучения, предопределяют развитие экспериментальной базы и теоретического аппарата. При создании новой техники - составляют важный этап в проектировании машин, устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере - используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими процессами. Оптимальные (эффективные) решения позволяют достигать цели при минимальных затратах трудовых, материальных и сырьевых ресурсов.

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

Математическое программирование является одним из разделов исследования операций - прикладного направления кибернетики, используемого для решения практических организационных задач. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий).

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

Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач составляют содержание математического программирования. Задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин, а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ

Целью математического программирования является создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов - создание эффективных вычислительных способов получения приближенного решения.

Целью курсовой работы является изучение и реализация численного метода решения задачи минимизации многомерной функции методом деформируемого многогранника.

Для достижения поставленной цели сформулированы следующие задачи:

· изучить литературу по решению задач минимизации;

· классифицировать модели и методы решения задач минимизации;

· реализовать алгоритм метода деформируемого многогранника численно;

· проверить работу алгоритма на примерах с известным аналитическим решением.

§1. Постановка задач минимизации

1.1 Классификация задач и методов

Постановка задачи поиска безусловного экстремума

Дана дважды непрерывно дифференцируемая функция f(x), определенная на множестве .

Требуется исследовать функцию f(x) на экстремум, т.е. определить точки ее локальных минимумов и максимумов на :

Находятся точки локальных экстремумов с помощью необходимых условий первого и второго порядка (порядок условий определяется порядком используемых производных), а также достаточных условий безусловного локального экстремума. Вычисляются значения функции в найденных точках локальных экстремумов.

Постановка задачи поиска условного экстремума.

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

,

где , m и p-числа; f(x)- целевая функция,

,j=1,..,p - функции, задающие ограничения (условия).

Будем считать функции f(x), , j=1,..,р дважды непрерывно дифференцируемые на множестве .

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

1. Целевая функция (x) может не иметь непрерывных производных до второго порядка включительно.

2. Использование необходимого условия первого порядка связано с решением системы n в общем случае нелинейных алгебраических уравнений, что представляет собой самостоятельную задачу, трудоемкость решения которой сравнима с трудоемкостью численного решения поставленной задачи поиска экстремума.

3. Возможны случаи, когда о целевой функции известно лишь то, что ее значение может быть вычислено с нужной точностью, а сама функция задана неявно.

Подавляющее большинство численных методов оптимизации относится к классу итерационных, т.е. порождающих последовательность точек в соответствии с предписанным набором правил, включающим критерии окончания. При заданной начальной точке x0 методы генерируют последовательность x0, x1, x2. Преобразование точки xk в xk+1 представляет собой итерацию.

Для определенности рассмотрим задачу поиска безусловного локального минимума:

 (1.1)

Численное решение задачи (1.1), как правило, связано с построением последовательности xk точек, обладающих свойством

(xk+1) < (xk) , k = 0,1,… (1.2)

Общее правило построения последовательности xk имеет вид

xk+1 = xk + tk dk, k = 0, 1,… (1.3)

где точка x0- начальная точка поиска; dk -приемлемое направление перехода из точки xk в точку xk+1, обеспечивающее выполнение условия (1.2) и называемое направлением спуска; tk - величина шага.

Начальная точка поиска x0 задается, исходя из физического содержания решаемой задачи и наличия априорной информации о положении точек экстремума.

Приемлемое направление спуска dk должно удовлетворять условию

, k = 0,1, (1.4)

обеспечивающему убывание функции (x).Примером приемлемого направления является направление вектора антиградиента: dk =

Величина шага tk > 0 выбирается либо из условия (1.2), либо из условия минимума функции вдоль направления спуска:

(1.5)

Выбор шага tk из условия (1.5) делает спуск в направлении dk -наискорейшим.

В зависимости от наивысшего порядка частных производных функции f(x), используемых для формирования dk и tk , численные методы решения задачи безусловной минимизации (1.1) принято делить на три группы.

1. Методы нулевого порядка, использующие только информацию о знании функции (x).

2. Методы первого порядка, использующие информацию о первых производных функции (x).

3. Методы второго порядка, требующие для своей реализации знания вторых производных функции (x).

1.2 Методы нулевого порядка

Постановка задачи и стратегии поиска метода одномерной минимизации

Постановка задачи

Требуется найти безусловный минимум функции (x) одной переменной, т.е. такую точку x* R, что f(x*) = min f(x), x R

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

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

Замечания 1.1.

1. Для методов одномерной минимизации типично задание априорной информации о положение точки минимума с помощью начального интервала неопределенности L0 = a0, b0 (рис. 1.1). Предполагается, что точка минимума x* принадлежит интервалу L0, но ее точное знание неизвестно.

2. Большинство известных методов одномерной минимизации применяется для класса унимодальных функций.

Определение 1.1. Функция (x) называется унимодальной на интервале L0 = a0, b0, если она достигает глобального минимума на a0, b0 в единственной точке x*, причем слева от x* эта функция строго убывает, а справа от x* строго возрастает. Если a0 ? y ‹ z ‹ x*,то (y)› (z), а если

x*‹ y ‹ z? b0, то (y) ‹ (z) (рис.1.1,а).

Рис 1.1. Иллюстрация унимодальных функций

Отметим, что непрерывная строго выпуклая функция является унимодальной. Однако, определению 1.1 могут удовлетворять и функции, не являющиеся непрерывными и выпуклыми. (рис. 1.1, б).

3. Методы одновременной минимизации широко применяются в методах первого и второго порядков для нахождения оптимальной величины шага . При этом левая граница начального интервала неопределенности, как правило, совпадает с началом координат, т. е. .

Стратегии поиска

Существует две принципиально различные стратегии выбора точек, в которых производится вычисление значений функций. Если все точки задаются заранее, до начала вычислений, - это пассивная (параллельная) стратегия. Если эти точки выбираются последовательно в процессе поиска с учетом результатов предыдущих вычислений, - это последовательная стратегия. Примером реализации пассивной стратегии является метод равномерного поиска .

Последовательную стратегию можно реализовать следующими способами:

а) применением квадратичной и кубической интерполяции, где по нескольким вычисленным значениям функции строится интерполяционный полином, а его минимум указывает на очередное приближение искомой точки экстремума;

б) построением последовательности вложенных друг в друга интервалов, каждый из которых содержит точку минимума;

Стратегия поиска включает в себя три этапа:

1. Выбор начального интервала неопределенности. Границы 0, 0 интервала должны быть такими, чтобы функция () была унимодальной (см. определение 1.1).

2. Уменьшение интервала неопределенности.

3. Проверку условий окончания. Поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины.

Ответом является множество точек, принадлежащих последнему интервалу неопределенности, среди которых каким-либо образом выбирается решение задачи *.

Замечания 1.2

1. В некоторых методах заранее задается или находится количество вычислений функции. В этом случае продолжительность поиска ограничена.

2. Для эвристического выбора начального интервала неопределенности можно применить алгоритм Свенна Swann W. H.:

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

Пусть точка y и z интервала a,bвычислены значения функции: (y) и (z). Если (y) (z), то x*a,y) и поэтому x*y,b (рис. 1.2, а). ,то x*(z,b и поэтому x*a,z (рис. 1.2, б). иными словами, в качестве нового интервала берется «гарантирующий интервал», наверняка содержащий точку минимума.

Если (y) = (z), в качестве нового интервала можно взять любой из изображенных на рис. 1.2.

Рис. 1.2. Иллюстрация 1итерации одномерных методов нулевого порядка

К методам последовательной стратегии можно отнести метод деления интервала пополам, метод Дихотомии, метод злотого сечения, метод Фиббоначи и др.

Методы нулевого порядка также подразделяются на методы одномерной и многомерной минимизации.

К методам одномерной минимизации относятся тот же метод Дихотомии, метод Фиббоначи, метод квадратичной интерполяции и др.

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

§2. Метод деформируемого многогранника

алгоритм минимизация последовательность экстремум

Постановка задачи

Требуется найти безусловный минимум функции () многих переменных, то есть найти такую точку Rn , что =

Cтратегия поиска

В основу метода деформируемого многогранника (метода Нелдера - Мида [ J.A.Nelder , R.Mead ]) положено построение последовательности систем n + 1 точек i , n , которые являются вершинами выпуклого многогранника. Точки системы i k + 1 , i1,…, n+1 на k+1 интерации совпадают с точками системы I k , i=1 , … , n+1 ,кроме i= h , где точка h k - наихудшая в системе i k , i, … , n , то есть hk max ik.Точка hk заменяется на другую точку по специальным правилам , описанные ниже . В результате многогранники деформируются в зависимости от структуры линий уровня целевой функции , вытягиваясь вдоль длинных наклонных плоскостей , изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума . Построение последовательности многогранников заканчивается , когда значение функции в вершинах текущего многогранника отличаются от значения функции в центре тяжести системы I k ,i , … , n ; i h не более чем на .

Алгоритм

Шаг 1. Задать координаты вершин многогранника 1, . . . , n+1; параметры отражения , сжатия , растяжения ; число для остановки алгоритма. Положить k ( последующие шаги 2-6 соответствуют номеру k системы точек).

Шаг 2. Среди вершин найти «наилучшую» 1 и «наихудшую» h, соответствующие минимальному и максимальному значениям функции:

1 min j ; h = max j ,

j = 1 , . . . , n + 1 j = 1, . . . , n + 1

а также точку s, в которой достигается второе по величине после максимального значения функции s .

Шаг 3. Найти « центр тяжести » всех вершин многогранника за исключением наихудшей h :

Шаг 4. Проверить условие окончания :

а) если , процесс поиска можно завершить и в качестве приближенного решения взять наилучшую точку текущего многогранника:

* 1 ;

б) если , продолжать процесс.

Шаг 5. Выполнить операцию отражения наихудшей вершины через центр тяжести n+2 (рис. 2.3, а) :

xn+3 = xn+2 + б (xn+2 - xh ).

Шаг 6. Проверить выполнение условий:

а) если (xn+3) (x1) , выполнить операцию растяжения (рис. 2.3, б):

xn+4 = xn+2 + г (xn+3 - xn+2 ).

Найти вершины нового многогранника:

- если (xn+4) < (x1), то вершина xh заменяется на xn+4 (при n = 2 многогранник будет содержать вершины x1, x3, x6). Затем следует положить k = k + 1 и перейти к шагу 2;

- если (xn+4) (x1), то вершина xh заменяется на xn+3 (при n = 2 многогранник будет содержать вершины x1, x3, x5). Далее следует положить k = k + 1 и перейти к шагу 2;

Рис. 2.3. Иллюстрация операций над многогранником

б) если (xs) < (xn+3) (xh), то выполнить операцию сжатия (рис. 2.3, в):

xn+5 = xn+2 + (xh - xn+2 ).

Следует заменить вершину xh на xn+5, положить k = k + 1 и перейти к шагу 2

(при n = 2 многогранник будет содержать вершины x1, x3, x7);

в) если (x1) < (xn+3) (xs) , то вершина xh заменяется на xn+3. При этом следует положить k = k + 1 и перейти к шагу 2;

г) если (xn+3) > (xh) , выполнить операцию редукции (рис. 2.3, г). Формируется новый многогранник с уменьшенными вдвое сторонами и вершиной x1:

x = x1 + 0,5 (x- x1), j = 1,…, n + 1.

При этом следует положить k = k + 1 и перейти к шагу 2.

Замечание 2.3. Нелдер и Мид рекомендуют использовать параметры = 1; = 0,5; = 2; Павиани (Д.Paviani) - = 1; 0,4 0,6; 2,8 3; Паркинсон и Хатчинсон (J.M. Parkinson, D.Hutchinson) - = 2; = 0,25; = 2,5. В последнем случае в рамках операции отражения фактически выполняется растяжение.

Рассмотрим решение задачи минимизации на следующем примере:

Найти минимум функции аналитически.

Вычислим градиент нашей функции:

Получаем стационарную точку x*=(5;6) подозрительную на экстремум.

Составляем матрицу Гесса матрицу вторых частных производных:



Далее найдем угловые миноры нашей матрицы:

Наша матрица положительно определена. Функция f(x) - строго выпуклая, а значит она выпукла.

Анализирую угловые миноры мы видим, что у нас выполняются достаточные условия и, следовательно, точка x*=(5;6) - локальный min.

На рис. 2.4 представлено решение данной задачи с помощью программы, написанной на языке Pascal. Необходимо указать координаты начального многогранника (в данной задаче - треугольника), в результате решения сообщаются координаты точки минимума и количество итераций.

Рис. 2.4. Результат работы программы на Pascal

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

Рис. 2.5. Результат работы программы на Delphi

Заключение

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

Высокая сложность алгоритма, может компенсироваться за счет времени расчета, меньшего числа итерации и значительно большей точности.

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

Литература

Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах - ФГПУ «Издательство «Высшая школа», 2005.- 22с., 35с., 107с.,138с.

Мустафина С.А., Гнатенко Ю.А. Методы оптимизации - Уфа РИЦ БашГУ, 2010 - 4с

Васильев Ф.П. Методы оптимизации - Москва Факториал пресс, 2002

Вержбицкий В.М. Численные методы - Москва Высшая школа, 2002

Размещено на Allbest.ru

...