Содержание
Введение2
1. Теоретическая часть4
1.1. Содержательное описание4
1.2. Математическая модель4
1.3. Постановка оптимизационной задачи6
1.4. Методы решения задачи коммивояжера6
1.4.1. Метод ветвей и границ6
1.4.2. Алгоритм Литтла9
1.4.3. Генетические алгоритмы11
2. Практическая часть12
2.1. Постановка задачи12
2.2. Решение задачи методом полного перебора13
2.3. Решение задачи методом ветвей и границ25
2.4. Решение задачи методом Литтла27
2.5. Программное решение муравьинным методом36
2.6. Сравнение методов решения задачи коммивояжера46
Заключение47
Литература48
Приложение50
Выдержка из текста работы
Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках. Требуется найти локальный минимум функции на множестве допустимых решений. В теории оптимизации f называется целевой функцией.
Все описываемые градиентные методы основаны на итерационной процедуре, реализуемой в соответствии с формулой
Где — текущее приближение к решению ; — параметр, характеризующий длину шага; — направление поиска управляемых переменных x.Способ определения и на каждой итерации связано с особенностями применяемого метода. Рассмотрим простейшие градиентные методы.
Первый называется методом градиентного спуска с постоянным шагом. Где направление движения на каждом шаге совпадает с антиградиентом функции. А длина шага задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности .
Второй — метод наискорейшего градиентного спуска, где величина шага определяется для каждого значения k из условия:
Есть еще градиентные методы со своими особенностями определения направления поиска и величины шага на каждой итерации.
Более подробно рассмотрим метод Флетчера-Ривса. Относительно невысокий уровень требований к объему памяти ЭВМ делает метод Флетчера-Ривса и его модификации особенно полезным при решении задач большой размерности.
1. Градиентный метод Флетчера-Ривса
Постановка задачи
Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках.
Требуется найти локальный минимум функции f(x) на множестве допустимых решений X=Rn, т.е. найти такую точку , что f(x*)=min f(x).
Стратегия поиска
Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {xk}, k=0,1,…, таких, что f (xk+1)< f (xk), k=0,1,…. Точки последовательности {xk} вычисляются по правилу:
x k + 1 = x k +t d k, k = 0,1,…;
d k = +вk-1 d k -1;
d0 = ;
вk-1 = ;
Точка x0 задается пользователем, величину шага t выбираем постоянной.
Вычисление величины вk -1 обеспечивает для квадратичной формы построение последовательности Н-сопряженных направлений d0, d1,.., dk,… . При этом в точках последовательности {xk} градиенты функции f(x) взаимно перпендикулярны.
Для квадратичных функций f(x) метод Флетчера-Ривса является конечным и сходится за число шагов, не превышающих размерность вектора x.
Алгоритм
Шаг 1. Задать x0, е1>0, е2>0, M — предельное число итераций, t — длина шага. Найти градиент ;
Шаг 2. Положить k = 0;
Шаг 3. Вычислить ;
Шаг 4. Проверить выполнение критерия окончания ;
Шаг 5. Проверить условие :
a) если неравенство выполняется, то расчет окончен и ;
б) если нет, то при k = 0 перейти к шагу 6, а при перейти к шагу 7.
Шаг 6. Определить
Шаг 7. Определить .
Шаг 8. Определить
Шаг 9. Вычислить
Шаг 10. Проверить выполнение условий
, :
а) в случае выполнения обоих условий в двух последовательных итерациях с номерами k и k — 1 расчет окончен, найдена точка ;
б) если не выполняется хотя бы одно из условий, полагаем и переходим к шагу 3.
Тестовый пример
Применим градиентный метод Флетчера-Ривса для нахождения локального минимума функции:
Задаем начальные условия:
Величину шага на каждой итерации определяем из следующего условия:
Текст программы, выполненной в системе Wolfram Mathematica, находится в Приложении.
2. Постановка задачи оптимизации
В механизме, изображенном на рисунке, стержень LC проходит через поворотный ползун в точке А, а в точке В шарнирно закреплен на ползуне, движущемся по прямолинейной вертикальной направляющей MN.
Считать, что
1. Приняв АС, за полярные координаты, определить величину скорости и ускорения точки С.
2. Предполагая, что
Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.
3. Стратегия поиска
Будем решать задачу поиска безусловного минимума с ограничениями. Для этого рассмотрим метод штрафов. Идея метода заключается в сведении задачи на условный минимум к решению задач поиска безусловного минимума вспомогательной функции:
Где — штрафная функция, rk — параметр штрафа, задаваемый на каждой итерации.
Штрафные функции конструируются исходя из условий:
, при выполнении ограничений, , при невыполнении ограничений. Как правило для ограничений типа равенств используется квадратичный штраф, а для ограничений типа неравенств квадрат срезки:
На каждой k-й итерации ищется точка минимума вспомогательной функции при заданном параметре с помощью метода Флетчера-Ривса. Полученная точка используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании последовательность точек стремится к точке условного минимума .
4. Задача на минимум функции скорости и ускорения
1. Приняв АС, за полярные координаты, определить величину скорости и ускорения точки С.
2. Предполагая, что
Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.
AC = AB+BC;
Начальные условия:
Для скорости:
Сравнение полученного результата с результатом команды NMinimize пакета Mathematica функции скорости:
Для ускорения:
Сравнение полученного результата с результатом команды NMinimize пакета Mathematica функции ускорения:
Текст программы, выполненной в системе Wolfram Mathematica, находится в Приложении.
Заключение
В данной работе был рассмотрен градиентный метод решения задач оптимизации в механике и продемонстрировано применение данного метода на примере нахождения минимума скорости и ускорения.
В ходе исследования были выявлены некоторые проблемы в составлении штрафной функции, необходимой для избавления ограничений, и выборе параметра, характеризующего длину шага на каждой итерации, что привело к нахождению приближенного решения задачи.
Приложение
Тестовый пример:
Найти локальный минимум функции .
Задача оптимизации
Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.
Скорость:
Ускорение:
Литература
1. Лутманов С.В. Курс лекций по методам оптимизации — РХД Ижевск, 2001.
2. Рейклетис Г., Рэгсдел К. Оптимизация в технике. М.:Мир, 1986
3. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. М: Высш. шк., 2005
Размещено на
