Исследование методов оптимизации (стр. 1 из 8)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ХАРЬКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ»

Факультет информатики и управления

Кафедра экономической кибернетики и маркетингового менеджмента

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

По математическому программированию

Исследование методов оптимизации

Харьков 2009

РЕФЕРАТ

Данная курсовая работа содержит : 41 страницу, 16 таблиц, 6 графиков.

В курсовой работе рассмотрены теоретические основы двух методов оптимизации математического программирования :

- метод Нелдера-Мида ;

- градиентный метод с дроблением шага.

Произведена минимизация исследуемой функции указанными методами. Выявлена зависимость числа итераций от заданной точности. Сопоставлена трудоемкость и эффективность оптимизации заданной функции различными методами (градиентным и методом Нелдера-Мида).

Ключевые термины:

Градиент – вектор первых частных производных функции.

Линии уровня – множества точек, в которых функция

принимает постоянные значения, т.е.

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

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

СОДЕРЖАНИЕ

1. Введение

2. Математическое описание методов оптимизации

2.1 Метод Нелдера-Мида

2.2 Градиентный метод с дроблением шага

3. Решение задачи минимизации для каждого из методов

3.1 Метод Нелдера-Мида

3.2 Градиентный метод с дроблением шага

4. Графическая интерпретация решения задачи

5. Аналитическое исследование методов

6. Заключение

7. Приложение

8. Список литературы

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ

- точка

- длинна шага

- вектор градиент

E - точность

N – количество итераций

Д – матрица координат симплекса

t – длинна ребра симплекса

1. ВВЕДЕНИЕ

Объектом исследования предмета математическое программирование являются задачи оптимизации.

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

Универсальных методов, подходящих для поиска экстремума абсолютно любой функции не существует. Данная курсовая работа ставит себе целью исследовать метод оптимизации нулевого порядка – метод Нелдера-Мида, а также метод оптимизации первого порядка – градиентный метод с дроблением шага на примере конкретной функции. Таким образом, получив практические результаты, можно будет сравнить эффективность рассматриваемых методов, применяемых к исследуемой функции.

ПОСТАНОВКА ЗАДАЧИ ( Вариант задания 1)

Исследовать функцию типа :

Используемые методы минимизации

:

1. Метод: Нелдера-Мида.

2. Метод: Градиентный с дроблением шага.

Необходимо :

1. Решить задачу минимизации

, начав итерации из выбранной начальной точки x0=(1;1) заданными по варианту методами, необходимая точность решения . Привести таблицу результатов расчета типа: Итерация: - точка: значение: критерий: .

2. Рассчитать 3 линии уровня функции и изобразить их на графике.

3. Отобразить на графиках линий уровня для каждого из заданных методов траекторию движения по итерациям (траекторию спуска).

4. Выявить зависимость числа итераций N от заданной точности E, значения точности:

, , , , , . Привести таблицу результатов как в п.1 для каждого значения E.

5. Сравнить эффективность рассмотренных в варианте методов по числу итераций N, построить графики N=F(E).

2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ

2.1 Метод Нелдера-Мида

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

t – некоторое выбранное число.

Если n = 2, то при t = 1 имеем

Расположение симплекса показано на рисунке 2.1

Рисунок 2.1- Начальное расположение симплекса

Легко убедиться в том, что если координаты вершин симплекса задать в соответствии с матрицей Д₀ , то расстояние между двумя любыми вершинами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n .

Действительно, расстояние между любой вершиной x_j , j= 2,3,.., n+1, и вершиной x₁ равно

С другой стороны, расстояние между любой парой вершин

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

Вычислим значения оптимизируемой функции в точках

и переномеруем точки так, чтобы выполнялись неравенства :

.

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

:

Осуществим отражение вершины

относительно центра тяжести. Получим точку

.

Если a=1 , то получим зеркальное отражение. В одномерном случае процедура отражения, обеспечивающая получение точки

, симметричной точке относительно иллюстрируется рис. 2.2

Рисунок 2.2 - Построение точки

Сравним теперь между собой значения

Возможны следующие варианты

а)

. В этом случае выполняется растяжение симплекса и отыскивается точка