Темы рефератов по методам оптимизации

Обновлено: 19.05.2024

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

в исследовании операций: оптимизация технико-экономических систем, транспортные задачи, управление запасами и т.д.;

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

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

2. Задание на курсовое проектирование:

3. Решение задач безусловной оптимизации

3.1 Анализ задачи
Данная задача является задачей оптимизации без ограничений или задачей безусловной оптимизации. Данная функция является выпуклой на множестве D, так как все угловые миноры матрицы Гессе – матрицы вторых производных положительны при . Для решения данной задачи выбран метод Коши.
3.2 Описание алгоритма и его схема
Метод наискорейшего спуска (метод Коши)

Известный французский математик Коши Огюстен Луи (21.08.1789–23.05.1857) первым использовал аналогичный алгоритм для решения системы линейных уравнений.

В этом широко используемом методе (МК) выбираются так, чтобы минимизировать функцию по :

на множестве значений (одномерная минимизация).

Алгоритм Коши.

Ш. 1 Выбрать начальную точку .

Ш. 2 На -ой итерации, где , найти такое , что

Ш. 3 Проверка критерия останова.

Да: окончание поиска конец. Нет: , Ш. 2.

Определение. Будем говорить, что алгоритм А глобально сходится, если для любой выбранной исходной точки последовательность , порожденная точками , сходится к точке, удовлетворяющей необходимым условиям оптимальности.

Замечание. МК обладает глобальной сходимостью, но это не означает обязательного получения глобального экстремума функции . Если дважды дифференцируема в стационарной точке и гессиан положительно определен, то - локальный минимум ЦФ. И только если является выпуклой функцией, то является точкой глобального минимума .

МК обладает устойчивостью, т.е. при достаточно малом значении обеспечивается выполнение неравенства:

МК позволяет существенно уменьшить значение ЦФ (быстро спуститься на "дно оврага") при движении из точек, расположенных на значительных расстояниях от точки , но в дальнейшем может произойти "зацикливание". Поэтому МК часто используются совместно с другими градиентными методами (например, методом Ньютона) в качестве начальной процедуры.

Недостаток: для некоторых типов функций сходимость может оказаться медленной. В самом деле, если минимизирует функцию

откуда вытекает равенство:

которое доказывает, что последовательные направления ортогональны. В случае ярко выраженной нелинейности ("овражности") ЦФ происходит "зацикливание".

где - соответственно наибольшее и наименьшее собственные значения матрицы Гессе , вычисленные в точке .

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

Ускоренные методы наискорейшего спуска.

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

Метод Ньютона.

Методы сопряженных направлений (относительно метода Флетчера-Ривза).

т.е. последовательность сходится к суперлинейно.

Если удовлетворяет условию Липшица

в окрестности точки , то имеем квадратичную сходимость по n шагам:

Квазиньютоновские методы (применительно к алгоритму ДФП).

Если, кроме того, удовлетворяет условию Липшица в окрестности точки , то сходимость к квадратичная:

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

загрузка памяти пропорциональна ;

объем вычислений пропорционален .

Вычислим компоненты градиента:
;
,
Находим

Критерий останова :
Данные, полученные при проведении дальнейшего поиска приведены в таблице

Рассмотрим общую задачу линейного программирования с m ограничениями и n переменными, записанную в стандартной (канонической) форме:

Как правило, число уравнений задачи меньше числа переменных (т.е. ), поэтому множество ее допустимых решений бесконечно. Следовательно, выбор наилучшего допустимого решения, минимизирующего ЦФ (x), нетривиален.

Известен классический метод решения систем линейных уравнений – метод Гаусса–Жордана. Основная идея этого метода состоит в сведении системы mуравнений с nнеизвестными к каноническому виду при помощи элементарных операций над строками. При использовании первых mпеременных такая система имеет следующий вид:

Или (2) можно переписать следующим образом:

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

Остальные переменных называются небазисными или независимыми переменными.

умножение любого уравнения системы на положительное или отрицательное число;
прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

Например: в системе (2) одно из базисных решений задается как:

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

Допустимое базисное решение является угловой точкой допустимого множества задачи линейного программирования и называется иногда опорным планом.

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

В основе симплекс–метода (СМ) лежит следующая теорема.

Теорема. Если ЗЛП разрешима, то экстремум целевой функции достигается хотя бы в одной из угловых точек допустимого множества этой задачи.

Так как различные базисные решения системы (2) соответствуют различным вариантам выбора из общего числа переменных , то число допустимых базисных решений (угловых точек) не превышает

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

Пример: Если (задача небольшой размерности), то ЭВМ, выполняя 10 5 переборов варианта в 1 секунду, будет искать решение 10 6 лет.

Идея СМ состоит в направленном переборе угловых точек допустимого множества с последовательным уменьшением целевой функции .

СМ разработан Дж. Данцигом.

Наиболее простой метод, используемый для решения ЗЛП, - это симплексный метод Данцига.

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

Описание симплекс–метода

Предположим, что ЗЛП (1) является невырожденной, а базисное решение (4) – допустимым; обозначим его:

Используя соотношение (3), выразим целевую функцию из (1) через свободные переменные :

Справедливы следующие утверждения:

а) если в (6) все коэффициенты , то в угловой точке (5) достигается минимум целевой функции из (1) на допустимом множестве ЗЛП (1) и этот минимум равен ;

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

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

В случаях (а) и (б) процесс решения ЗЛП заканчивается. Рассмотрим подробнее случай (в).

Пусть в (6) коэффициент и в (2) имеются положительные коэффициенты . Найдем номер базисной переменной из условия:

где минимум берется по всем номерам , для которых .

Найдем решение системы ограничений из (1), т. е.:

считая свободными переменные: , т. е. поменяв местами свободную переменную с базисной переменной . Система уравнений (2) в этом случае запишется следующим образом:

Итак, математика – это область человеческого знания, в которой изучаются математические модели.

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

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

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

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

Наилучшие в определенном смысле решения задач принято называть оптимальными. Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

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

Составной частью методов оптимизации является линейное программирование.

Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок; позволяющего минимизировать суммарной километраж, была дана в работе советского экономиста А. Н. Толстого в 1930 году.

Систематические исследования задач линейного программирования и разработка общих методов их решения получили дальнейшее развитие в работах российских математиков Л. В. Канторовича, В. С. Немчинова и других математиков и экономистов. Также методам линейного программирования посвящено много работ зарубежных и прежде всего американских ученых.

Задача линейного программирования состоит в следующем: максимизировать (минимизировать) линейную функцию

Замечание. Неравенства могут быть и противоположного смысла. Умножением соответствующих неравенств на (-1) можно всегда получить систему вида (*).

Если число переменных системы ограничений и целевой функции в математической модели задачи равно 2, то её можно решить графически.

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

Обратимся к одному из неравенств системы ограничений.

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

Замечание 2. Если , то проще взять точку (0;0).

Условия неотрицательности также определяют полуплоскости соответственно с граничными прямыми . Будем считать, что система неравенств совместна, тогда полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты которых являются решением данной системы – это множество допустимых решений. Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, лучом, многоугольником, неограниченной многоугольной областью. Таким образом, задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху (снизу). При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим прямую (где h – некоторая постоянная). Чаще всего берется прямая . Остается выяснить направление движения данной прямой. Это направление определяется градиентом (антиградиентом) целевой функции

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

Эти построения будем продолжать до тех пор, пока прямая не пройдет через последнюю вершину многоугольника решений. Эта точка определяет оптимальное значение.

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

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений.

4. Строят вектор .

5. Строят прямую .

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

7. Определяют координаты точки максимума (минимума) функции и вычисляют значение целевой функции в этой точке.

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

1. Количество перевозимых частей в соединении равно 6, а в –9.

2. Каждая станция может принять определенное количество частей: .

3. На погрузку одной части станции затрачивают различное время (в сутках), которое указано в таблице.

Соединения	Станция погрузки
	3,0 4,5	4,0 6,5	2,5 3,5

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

Решение штабов соединений состоит в распределении частей по станциям погрузки. Обозначим через число частей i - го соединения ( i =1,2) на j - ой станции ( j = 1, 2, 3).

Мы можем записать:

количество частей соединений на станциях погрузки соответственно.

- количество частей соединения на местах погрузки.

Общая сумма затрат времени (в сутках) на погрузку есть

В этой задаче 6 переменных, но мы можем свести к двум.

Целевая функция имеет вид

Итак, надо найти при ограничениях:

которая решается графически

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

Последняя вершина многоугольника решений есть точка С , получаемая пересечением прямых (1) и (4). Решая, получим С (1;5).

Итак, оптимальные значения будут следующими: , а общие затраты времени (суток).

Пусть дана целевая функция .

Для нахождения наибольшего и наименьшего значения функции и (одной) вещественных переменных надо найти критические точки, в которых частные производные (производная) функции f по всем переменным обращается в 0. Кроме того, надо исследовать точки границы, если она принадлежит области определения. Среди них выбрать значения, где f принимает наибольшее и наименьшее значение.

Пример 2. Определить оптимальный по времени маршрут выдвижения танкового подразделения из пункта А в пункт F, если допустимая скорость движения танков до дороги , по дороге , за дорогой . Удаление от дороге пункта А равно , пункта F . Расстояние между точками В и Е равно L = 90 км .

Составим математическую модель, то есть найдем функцию цели. Нас интересует время. Время выдвижения из пункта А в пункт F.

ВС = х км ; DE = y км ; АС =

Составим функцию цели, которая зависит от двух переменных

Найдем критические точки

При данных условиях

Найдем значение t при полученных x и y

При вычислении значения t на границе, значения получаются больше, чем 4,24 часа. Следовательно, оптимальное решение будет при

х = 6,9 км , у = 24 км , .

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

1. Тихонов А. Н., Костомаров Л. П. Вводные лекции по прикладной математике. М., Наука, 1984.

2. Кудрявцев Е. Н. Исследования операций в задачах, алгоритмах и программах. М., Наука, 1982.

3. Кузнецов Ю. Н., Кузубов В. И., Волощеноко А. В. Математическое программирование. М., Высшая школа, 1980.

4. Ильин В. А., Позняк Э. Г. Основы математического анализа. М., Наука, 1979.

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

50 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Кафедра математического анализа Дипломная работа по математике студентка 5 курса математического факультета

Зав. кафедрой математического анализа _________________________

Глава I. Задача отыскания экстремума функций многихпеременных….

§1. Функция многих переменных………………………………………….

1.1 Необходимые условия экстремума…………………………….

1.2 Необходимые условия второго порядка. Достаточные условия……………………………………………………………….

§2. Относительный экстремум. Метод множителей Лагранжа…………

2.2 Метод множителей Лагранжа………………………………….

2.3 Седловая точка функции Лагранжа……………………………..

Глава II. Численные методы отыскания безусловного экстремума…….

§1. Методы первого порядка (градиентные методы)……………………..

1.1 Метод градиентного спуска с постоянным шагом……………

1.2 Метод наискорейшего градиентного спуска………………….

1.3 Метод покоординатного спуска……………………………….

§2. Методы второго порядка………………………………………………

2.2 Метод Ньютона-Рафсона……………………………………….

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить

Темы рефератов по методам оптимизации

Описание симплекс–метода

Похожие работы