Методы направленного поиска в задачах оптимизации реферат

Обновлено: 04.07.2024

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

Содержание работы

Введение
1. Формулировка математической задачи оптимизации.
2. Численные методы решения задач одномерной оптимизации.
Метод перебора, метод деления пополам.
3. Методы безусловной минимизации функций многих переменных.
3.1. Многомерный поиск без использования производных
Метод циклического покоординатного спуска, метод Хука и Дживса.
3.2. Многомерный поиск, использующий производные
Метод наискорейшего спуска
3.3. Методы, использующие сопряженные направления
Метод Дэвидона-Флетчера-Пауэлла
Заключение
Литература

Файлы: 1 файл

реферат.docx

1. Формулировка математической задачи оптимизации.

2. Численные методы решения задач одномерной оптимизации.

Метод перебора , метод деления пополам.

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

3.1. Многомерный поиск без использования производных

Метод циклического покоординатного спуска, метод Хука и Дживса.

3.2. Многомерный поиск, использующий производные

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

3.3. Методы, использующие сопряженные направления

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

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

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

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

Конечно, и во втором примере при выборе решения можно действовать интуитивно, опираясь на опыт и здравый смысл. Но решения окажутся гораздо более разумными, если они будут подкреплены количественными, математическими расчетами. Эти предварительные расчеты помогут избежать длительного и дорогостоящего поиска правильного решения "на ощупь".

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

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

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

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

1.ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ.

В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом:

Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Под минимизацией (максимизацией) функции n переменных f(x)=f(x1. ,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).

При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f(x) -> min (max),x принадлежит U, где f(x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные.

2.ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси: f(x) -> min , x принадлежит [a, b].

Максимизация целевой функции эквивалента минимизации ( f(x) -> max ) эквивалентна минимизации противоположной величины ( -f(x) -> min ), поэтому, не умаляя общности можно рассматривать только задачи минимизации.

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

Для решения задачи минимизации функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b].

Некоторые из них: метод перебора , метод поразрядного поиска , метод деления попалам , метод золотого сечения.

Разобьем отрезок [a,b] на n равных частей точками деления:

Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n.

Метод деления пополам

Рассмотрим функцию F, которую требуется минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции , которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии eps>0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой к теоретическому значению (b1-a1)/2, и в то же время такое, чтобы значение функции в этих двух точках были различимы.

Алгоритм дихотомического поиска.
Алгоритм дихотомического метода для минимизации строго квазивыпуклой фунции на интервале [a1,b1].

Начальный этап. Выбрать константу различимости 2еps > 0 и допустимую конечную длину интервала неопределенности l > 0. Пусть [a1,b1] - начальный интервал неопределенности. Положить k=1 и перейти к основному этапу.

Шаг 1. Если bk-ak

3.МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

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

3.1.Многомерный поиск без использования производных.

Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. Важно отметить, что для применения этих методов не требуется не только дифференцируемости целевой функции, но даже аналитического задания. Нужно лишь иметь возможность вычислять или измерять значения f в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации. В основном все описанные методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f(x+lym*d) при условии, что lym принадлежит L, где L обычно задается в форме L=E1, L== 0> или L=

lym. Некоторые из них: метод циклического покоординатного спуска, метод Хука и Дживса , метод Розенброка , метод минимизации по правильному симплексу , метод минимизации по деформируемому симплексу .

Метод циклического покоординатного спуска.

В этом методе в качестве направлений поиска используются координатные векторы. Метод циклического покоординатного спуска осуществляет поиск вдоль направлений d1, . dn, где dj - вектор, все компоненты которого, за исключением j-ого, равны нулю.

Таким образом, при поиске по направлению dj меняется только переменная xj, в то время как все остальные переменные остаются зафиксированными.

Алгоритм циклического покоординатного спуска

Начальный этап. Выбрать eps >0, которое будет использоваться для остановки алгоритма, и взять в качестве d1, . dn координатные направления. Выбрать начальную точку x1, положить y1 = x1, k=j=1 и перейти к основному этапу.

Шаг 1. Положить lymj равным оптимальному решению задачи минимизации f(yj+lym*dj) при условии, что lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j

Шаг 2. Положить x[k+1] = y[n+1]. Если || x[k+1] - xk ||

Метод Хука и Дживса.

Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке.

1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.

При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2 . Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.

Алгоритм Хука и Дживса с использованием одномерной минимизации.

Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1. dn и направлений поиска по образцу.

Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.

Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j

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

1. Основы теории оптимизации

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

Рассматривая некоторую произвольную систему, описываемую т уравнениями с n неизвестными, можно выделить три основных типа задач. Если т= n, задачу называют алгебраической. Такая задача обычно имеет одно решение. Если т> n, то задача переопределена и, как правило, не имеет решения. Наконец, при т min, xÎR n

x 0 -начальное приближение (массив [1: n])

Будем считать, что нам известна функция

minf (j (q)), которая вычисляется qmin : j (qmin ) =minj (q)

r: =f (x 0 ); r1: =r+2*e; x: =x 0 ;

пока abs (r1-r) >= e

Для i от 1 до n

4. Метод исключения областей

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

Одним из методов исключения является метод сеточного поиска, разработанный Мишке и дающий неплохие результаты. В этом случае суженная область неопределенности представляет собой гиперкуб - многомерный аналог квадрата или куба, - размеры которого можно определить заранее. Благодаря этому метод Мишке является одним из немногих методов многомерного поиска, эффективность которого поддается измерению. Чтобы лучше понять сущность этого метода, рассмотрим его для случая пространства проектирования, определяемого двумя переменными. Исходную область неопределенности в зависимости от размерности пространства отобразим на единичный квадрат, куб или гиперкуб. Это позволит вести поиск в нормированной области со стороной, равной единице. В гиперкубе построим сетку, образованную попарно симметричными взаимно ортогональными плоскостями, параллельными координатным направлениям, вдоль которых изменяются проектные параметры. Эти плоскости пересекаются по прямым, которые в свою очередь пересекаются в точках, называемых в дальнейшем узлами. Вычислим значения целевой функции в узлах и в центре куба. В случае М проектных параметров получим 2 значений целевой функции, из которых выберем наибольшее. Примем соответствующий узел за центр гиперкуба меньших размеров и продолжим исследование. Процесс продолжается до тех пор, пока не будет достигнута требуемая степень сужения интервала неопределенности. Если в области допустимых значений обозначить степень сужения вдоль какой-либо оси координат через r, то линейное сужение для b-мерного гиперкуба будет равно f=r, а число вычисленных значений целевой функции N= b (2) +1.

Мишке рекомендует выбирать r в интервале значений 2/3 min, xÎR n

x 0 -начальное приближение (массив [1: n])

Будем считать, что нам известна функция

minf (j (q)), которая вычисляется qmin : j (qmin ) =minj (q)

r: =f (x 0 ); r1: =r+2*e; x: =x 0 ;

пока abs (r1-r) >= e

Для i от 1 до n

6. Градиентные методы

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

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

Позднее мы включим их в схему поиска.

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

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

Вектор градиента произвольной целевой функции F (x,x,x,…,x) имеет вид:

(¶F/¶x) e+ (¶F/¶x) e+…. + (¶F/ ¶x) e,

где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде ve+ve+ve+…+ve, где

v=.

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



Здесь D - небольшое смещение в направлении x. Эту формулу часто называют "приближением секущей". Полученную информацию о направлении градиента можно использовать различным образом для построения алгоритма поиска.

Один из возможных примеров алгоритмов.

f (x) - > min, xÎR n

x 0 -начальное приближение (массив [1: n])

Будем считать, что нам известна функция

minf (j (q)), которая вычисляется qmin : j (qmin ) =minj (q)

r: =f (x 0 ); r1: =r+2*e; x: =x 0 ;

Пока abs (r-r1) >= e

Для i от 1 до n

Для i от 1 до n

6.1 Ступенчатый наискорейший подъем

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

Наискорейший подъем с использованием одномерного поиска

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

x=x+Sv,

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


Найти прямую наилучшим образом аппроксимирующую совокупность экспериментальных точек. Уравнение прямой y=m*x+b. Суммарная ошибка в случае точек определяется выражением SUM=

Необходимо найти минимум, SUM, оптимальные значения m,b. Экспериментальные точки заданы.

Емкость бака для жидких отходов должна составитьV л. Изготовляется бак из железобетона толщинойt см. Определить геометрические параметры бака, при которых на его изготовление пойдет минимальное количество бетона.

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

Изготовитель контейнеров проектирует открытый контейнер из листового материала. Заготовка вырезается из листа, сгибается по пунктирным линиям и сваривается четырьмя швами. Каковы должны быть размеры контейнера небольшого объема, если площадь его дна не должна превышать 1 м 2 и ни один из линейных размеров a,b,c не должны быть больше другого более чем в 3 раза?


Сравнительно простая с математической точки зрения целевая функция Розенброка y=100 (x2 -x) 2 + (1+x1 ) 2 описывает поверхность с впадиной.

Минимальное значение целевой функции соответствует точке с координатами M (x,y). Если взять начальную точку во втором квадранте, то не всегда удается обеспечить сходимость. Выбрав исходную точку попытаться решить эту задачу оптимизации:

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

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

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

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

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

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

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

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

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

ВЫСШЕЕ ВОЗДУШНО-ДЕСАНТНОЕ КОМАНДНОЕ

ДВАЖДЫ КРАСНОЗНАМЕННОЕ УЧИЛИЩЕ

ИМЕНИ ГЕНЕРАЛА АРМИИ МАРГЕЛОВА В.Ф.

Кафедра высшей математики и теоретической механики

Выполнил курсант: Валуйкин Александр Владимирович

4 взвода 8 роты

Руководитель работы: Щукина Наталья Васильевна

§1. ПОСТАНОВКА ЗАДАЧ ОПТИМИЗАЦИИ 5

§2 ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 7

§3 АНАЛИТИЧЕСКИЙ МЕТОД ОПТИМИЗАЦИИ 13

Введение

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

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

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

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

§1. ПОСТАНОВКА ЗАДАЧ ОПТИМИЗАЦИИ

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

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

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

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

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

Читайте также: