Автор работы: Пользователь скрыл имя, 30 Января 2015 в 00:17, контрольная работа
Значительная часть задач, с методами решения которых мы будем знакомиться при изучении курса, связана с построением и использованием математических моделей оптимизации. Как научное направление, теория оптимизации возникла лишь в эпоху ЭВМ, так как реализация алгоритмов отыскания экстремумов чрезвычайно трудоемка, но основные методы и подходы, использующиеся в теории оптимизации, были разработаны крупнейшими математиками прошлого - Ньютоном, Эйлером, Лагранжем.
Введение3
Классическая постановка задачи оптимизации4
Стандартные формы задач оптимизации5
Методы решения задач оптимизации6
Численные методы оптимизации8
Области применения моделей оптимизации13
Список литературы14
Министерство культуры Российской Федерации
ФГБОУ ВПО «Кемеровский государственный университет культуры и искусств»
Институт информационных и библиотечных технологий
Кафедра технологии автоматизированной обработки информации
Контрольная работа
по курсу «Моделирование информационных ресурсов»
тема: «Оптимизационные математические модели»
Выполнил:
студент группы ПИ-122 ЗФО
Свобода А.А.______________
Проверил:
Доцент кафедры ТАОИ
Огнева Э.Н._______________
« »____________ 2015 г.
Кемерово 2015
Содержание
Математические модели оптимизации широко применяются практически во всех сферах жизнедеятельности, будь то завод, транспортная компания, сферы здравоохранения.
Значительная часть задач, с методами решения которых мы будем знакомиться при изучении курса, связана с построением и использованием математических моделей оптимизации. Как научное направление, теория оптимизации возникла лишь в эпоху ЭВМ, так как реализация алгоритмов отыскания экстремумов чрезвычайно трудоемка, но основные методы и подходы, использующиеся в теории оптимизации, были разработаны крупнейшими математиками прошлого - Ньютоном, Эйлером, Лагранжем.
Обычная постановка задачи оптимизации (которую мы будем называть классической) состоит в следующем. В некотором -мерном пространстве тем или иным способом выделяется некоторое непустое множество точек этого пространства , называемое допустимым множеством. Далее фиксируется некоторая вещественная функция , заданная во всех точках допустимого множества. Задача оптимизации состоит в том, чтобы найти точку во множестве , для которой функция (целевая функция) принимает экстремальное - минимальное или максимальное значение. Под точкой пространства понимается -мерный вектор и, соответственно, является функцией -мерного векторного аргумента. Особо следует отметить, что при представлении о системе в форме понятие допустимого множества совпадает с понятием области допустимых траекторий или области существования системы.
Задачу оптимизации мы будем записывать следующим образом
или . (1)
При перемене знака целевой функции все точки ее максимума превращаются, очевидно, в точки минимума и наоборот. Поэтому в теории достаточно рассматривать лишь какой-нибудь один из видов оптимума (максимум или минимум). В современной теории оптимизации чаще всего останавливаются на нахождении минимума. Все результаты этой задачи очевидным образом переходят на задачу максимизации.
Заметим, что термин "оптимизация функции" не вполне точно отражает существо процесса оптимизации в форме (1). В таком процессе сама функция остается неизменной. Речь идет об оптимизации ее значения (путем выбора соответствующей точки в допустимом -мерном допустимом множестве значений ее аргумента ). Помимо такой задачи (задачи оптимизации функций) возможна постановка оптимизационной задачи, при которой в качестве допустимого множества выступает некоторое множество вещественных функций , а целевая функция есть некоторый функционал , сопоставляющей каждой функции некоторое вещественное число . Такую задачу мы будем называть задачей оптимизации функционалов или вариационной задачей.
В стандартных формах задач объектом оптимизации является непрерывная функция вещественных переменных , допустимая область задается конечной системой равенств и неравенств с непрерывными левыми частями и . Если при этом область ограничена, то в ней обязательно существует по крайней мере одна точка абсолютного максимума и одна точка абсолютного минимума функции . Поскольку перемена знака у левых частей неравенств и меняет знаки этих неравенств на противоположные, можно ограничиться одним из двух типов неравенств. Обычно при максимизации используются неравенства вида , а при минимизации - неравенства вида . Таким образом, возникают две стандартные формы постановки задач оптимизации.
; . (2)
Ограничения типа неравенств легко заменить ограничениями типа равенств и простыми координатными неравенствами, вводя дополнительные (вещественные) переменные . При этом ограничения вида заменятся парой ограничений , , а ограничения - парой ограничений , . Этот прием будет в дальнейшем именоваться приемом элиминации нетривиальных неравенств. Его особенно удобно применять в тех случаях, когда по смыслу задачи все точки допустимой области имеют неотрицательные координаты. В результате его применения в таких условиях возникает третья стандартная форма постановки задачи оптимизации:
. (3)
Во всех перечисленных постановках может присутствовать дополнительное требование о том, чтобы все координаты точки оптимума были целыми числами (или числами некоторого заданного ряда). Это требование превращает задачу непрерывной оптимизации в задачу целочисленной оптимизации. В случае, когда допустимая область ограничена, в ней может находиться лишь конечное множество точек с целочисленными координатами. Поэтому задача целочисленной оптимизации в ограниченной области в принципе может быть решена методом перебора, то есть путем вычисления значения целевой функции во всех допустимых точках и выбора из них точки (или точек) с оптимальными значениями критерия.
В случае, когда функция и функции , задающие ограничения, являются дифференцируемыми (гладкими) для решения задач оптимизации может быть использовано понятие градиента. Поле градиента обычно определяется как векторное поле, которое характеризует скалярное поле в направлении его наискорейшего возрастания.
Определение 1
Для любой дифференцируемой функции ее градиентом в точке называется вектор
. (4)
Отметим некоторые особенности, связанные с применением аналитических методов оптимизации:
Аналитические методы применимы лишь для оптимизации дифференцируемых (гладких) функций, то есть функций, имеющих частные производные по крайней мере до второго порядка включительно.
Необходимые условия экстремума первого порядка позволяют выделить лишь стационарные точки функции. Для определения точек экстремума требуется использование необходимых и достаточных условий второго порядка, что значительно увеличивает вычислительную сложность задачи.
Аналитические методы, основанные на непосредственном использовании необходимых и достаточных условий экстремума, позволяют выделить лишь точки экстремума, лежащие внутри допустимой области и не позволяют выделить экстремальные точки на границе . Для поиска точек экстремума, лежащих на границе , необходимо использовать метод множителей Лагранжа.
Алгоритм аналитической оптимизации функций на основании необходимых и достаточных условий экстремума состоит из следующих четырех шагов.
1. Свести задачу к стандартной форме постановки оптимизационных задач.
2. Используя необходимое условие экстремума первого порядка , определить стационарные точки.
3. Используя достаточные условия экстремума второго порядка, определить, являются ли стационарные точки экстремальными. Если стационарные точки являются экстремальными, определить характер экстремума (максимум или минимум).
Вычислить значения целевой функции в найденных точках локального экстремума нужного вида.
Помимо аналитических методов оптимизации, в практике широко применяются численные методы оптимизации, причем при численной оптимизации дифференцируемых функций во многих случаях также используется понятие градиента.
Рассмотрим некоторые из методов численной оптимизации. Для простоты изложения будем полагать, что модель оптимизации, представленная в форме (2), не содержит ограничений. Тогда мы можем говорить, что непрерывная дифференцируемая функция задана во всех точках пространства . Для произвольной точки , в которой , вектор градиента задает направление наискорейшего роста функции , а обратное ему направление - , называемое антиградиентом, - направление наискорейшего убывания этой функции. Это значит, что движение (на очень малый шаг) в направлении градиента функции обеспечивает наибольший рост, а в направлении антиградиента - наибольшее уменьшение этой функции. Из сказанного вытекает общая идея градиентного спуска (подъема): отправляясь из заданной точки , строим последовательность точек , так, что перемещение от каждой точки к точке , производится в направлении антиградиента (градиента) в точке .
Определение 2
Метод градиентного спуска - это метод численной оптимизации гладких функций многих переменных, при котором приближение к экстремуму производится так, что
, (5)
где - вектор единичной длины, имеющий то же направление, что и .
Существуют различные модификации метода градиентного спуска в зависимости от того, каким образом выбирается величина множителя , которая должна уменьшаться по мере приближения к точке экстремума. Наиболее простым способом обеспечения требуемого уменьшения шага является выбор длины шага , пропорциональной длине вектора градиента в точке .
Определение 3
Пропорционально-градиентный метод - один из видов метода градиентного спуска, при котором длина шага на (i+1) - м приближении определяется из условия
, , . (6)
При использовании полношагового градиентного метода (метода наискорейшего спуска) каждый шаг градиентного спуска делается на максимально возможную длину, обеспечивающую требуемое направление изменения значения функции. Таким образом, на полупрямой, исходящей из очередной точки в направлении антиградиента (при спуске) ищется точка абсолютного минимума, которая и выбирается в качестве очередной точки .
Определение 4
Метод наискорейшего спуска - один из градиентных методов оптимизации, при котором положение точки в (i+1) - м приближении определяется из условия
, где . (7)
На рисунке 0. 1. изображена геометрическая иллюстрация этого метода для случая минимизации функции двух переменных. Из начальной точки перпендикулярно линии уровня в направлении - спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча значение функции. В найденной точке этот луч касается линии уровня . Затем из точки проводят спуск в направлении, перпендикулярном линии уровня, до достижения и т.д. Следует отметить, что чрезвычайно большое значение при использовании численных методов имеет выбор начальной точки . Так, для случая, приведенного на рисунке, выбор в качестве начальной точки приведет к тому, что каждая итерация будет приближать решение к седловой точке , а не к точке минимума .
Рис1. Геометрическая интерпретация метода наискорейшего спуска при минимизации функции двух переменных
В качестве критерия окончания итераций при использовании численных методов оптимизации, как правило, используют следующие условия
, (8)
, (9)
, (10)
где , , - заданные положительные числа. Нередко используются различные сочетания критериев (8) - (10) или критерии, основанные на понятии относительной погрешности. Надежные и универсальные критерии окончания счета, которые были бы применимы к широкому классу задач и гарантировали бы достижение требуемой точности, в настоящее время неизвестны.
Помимо рассмотренных нами методов численной оптимизации широко применяются методы сопряженных градиентов, покоординатного спуска, метод Ньютона, методы выпуклой оптимизации и т.д.
Рис.2. Графики функций двух переменных, для максимизации которых градиентные методы неприменимы
Кроме численных методов, основанных на применении понятия градиента, существуют так называемые "методы прямого поиска", при использовании которых вычисление производных не требуется. Методы прямого поиска основаны на сравнении значений целевой функции в последовательно вычисляемых пробных точках. Обычно методы этой группы применяются тогда, когда в окрестности точки локального экстремума функция не является гладкой и не может быть продифференцирована. Примеры графиков таких функций приведены на рисункеОшибка! Закладка не определена.. Методы прямого поиска гораздо менее эффективны, чем градиентные методы, но в ряде случаев их использование неизбежно.
Рассмотренные нами методы численной оптимизации применяются обычно для решения задач без ограничений. В то же время математическая модель оптимизации в форме (2) в общем виде содержит ограничения - равенства и неравенства. Задачи вида (2) удается сводить к случаю безусловной оптимизации за счет изменения целевой функции. Такой подход реализуется в методах штрафных функций и барьеров.
При использовании метода штрафных функций в задаче максимизации целевая функция заменяется семейством функцией вида
, =1,2,., (11)
где - штрафная функция, которая внутри допустимой области принимает нулевое значение, а вне ее - отрицательна, а - -й элемент последовательности положительных чисел, сходящейся к нулю.
В методе барьеров при решении задачи максимизации в форме (2) целевая функция заменяется семейством функций
, =1,2,. (12)
где - барьерная функция, которая характеризуется свойством стремиться к - при приближении к границам допустимой области изнутри, а определяется аналогично (11). При решении любым из численных методов задачи безусловной оптимизации (11) или (12) при =1,2,., может быть получена последовательность экстремальных точек , сходящаяся к экстремальной точке исходной задачи (2). Переход от задачи максимизации к задаче минимизации при использовании метода штрафных функций и метода барьеров осуществляется изменением знака штрафной или барьерной функции.
оптимизационное моделирование функция алгоритм
Математические модели оптимизации широко применяются практически во всех сферах жизнедеятельности, будь то завод, транспортная компания, сферы здравоохранения. Так же в качестве примера можно рассмотреть исследование процессов резания, проектировании металлорежущего инструмента и технологических операций обработки. Достаточно часто в практике встречаются задачи оптимизации суммарного периода стойкости инструмента и задачи оптимизации режимов резания, которые могут быть решены с использованием рассмотренных нами методов. Особый класс задач составляют задачи определения конструкции (величин геометрических параметров) инструмента из условия максимизации стойкости инструмента или оптимизации физических параметров процесса обработки резанием.