Любая помощь студенту и школьнику!


Жми! Коллекция готовых работ

Главная | Мой профиль | Выход | RSS

Поиск

Мини-чат

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0

Форма входа

Логин:
Пароль:

Курсовая работа по основам алгоритмизации и программирования на тему: «Методы одномерной оптимизации

Курсовая работа по основам алгоритмизации и программирования на тему: «Методы одномерной оптимизации» (500 руб.)

Оглавление

Оглавление. 3

Введение. 4

Задачи оптимизации. 5

Одномерная оптимизация. 5

Методы поиска. 6

Метод золотого сечения. 7

Блок-схема метода золотого сечения. 9

Метод перебора. 9

Блок-схема метода перебора. 11

Блок-схема программы. 12

Руководство пользователя. 13

Демонстрация интерфейса программы. 14

Сравнение аналитического решения с результатами работы программы. 16

Описание используемых функций. 18

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

Список используемой литературы. 20

Приложение. Листинг программы.. 21

 

 

Введение.

Целью моего проекта является создание программы в математическом пакете MatLab на тему «Методы одномерной оптимизации». Для достижения данной цели ставились следующие задачи:

1.    Выполнить литературный обзор по данной теме

2.    Программно реализовать алгоритм

3.    Создать интерфейс пользователя

4.    Разработать руководство по эксплуатации программы

5.    Подробно разобрать 2 метода одномерной оптимизации: метод перебора и метод золотого сечения.

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

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

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

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

Целевую функцию можно записать в виде

)

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

В случае одного проектного параметра (n=1) целе­вая функция является функцией одной переменной, и ее график — некоторая кривая на плоскости. При п = 2 целевая функция является функцией двух переменных, и ее графиком является поверхность.

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

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

Задачи оптимизации.

 

Можно выделить два типа за­дач оптимизации — безусловные и условные. Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции от п действи­тельных переменных и определении соответствующих зна­чений аргументов на некотором множестве  n-мерного пространства. Обычно рассматриваются задачи минимиза­ции; к ним легко сводятся и задачи на поиск максимума путем замены знака целевой функции на противопо­ложный.

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

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

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

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

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

 

Одномерная оптимизация

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

 

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

 

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

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

Функция f(х) может достигать своего наименьшего и наибольшего значений либо в граничных точках отрезка [а, b], либо в точках минимума и максимума. Последние точки обязательно должны быть критическими, т. е. про­изводная  в этих точках обращается в нуль, — это необходимое условие экстремума. Следовательно, для определения наименьшего или наибольшего значений функции f(х) на отрезке [а, b] нужно вычислить ее зна­чения во всех критических точках данного отрезка и в его граничных точках и сравнить полученные значения; наименьшее или наибольшее из них и будет искомым значением.

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

Методы поиска.

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

Процесс решения задачи методом поиска состоит в последовательном сужении интервала изменения проект­ного параметра, называемого интервалом неопределенности. В начале процесса оптимизации его длина равна b-а, а к концу oнa должна стать менее заданного допу­стимого значения , т. е. оптимальное значение проектно­го параметра должно находиться в интервале неопреде­ленности — отрезке [хn, xn+1] , причем хn+1- хn< .

Наиболее простым способом сужения интервала не­определенности является деление его на некоторое число равных частей с последующим вычислением значений це­левой функции в точках разбиения. Пусть п — число элементарных отрезков, h= (b- а)/п — шаг разбиения. Вы­числим значения целевой функции   в узлах = а + kh

(k = 0, 1, ..., п). Сравнивая полученные зна­чения , найдем среди них наименьшее .

Число  можно приближенно принять за наи­меньшее значение целевой функции  на отрезке [а, b]. Очевидно, что близость  к минимуму т зависит от чис­ла точек, и для непрерывной функции

 

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

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

 

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

 

Метод деления отрезка пополам.

 

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

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

 

Метод деления на три равных отрезка.

 

1. Дан отрезок [a;b] на котором определена функция f(x) и точность e. Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек x1=a и x4=b. И вычислим Z=1/3.

2. Делим отрезок на три равные части и определяем точку x2=x1+Z(x4-x1) и точку x3=x4-Z(x4-x1). Вычисляем значения функции в этих точках F2=f(x2) F3=f(x3).

3. Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как x1=x1, а x4=x3, иначе x1=x2, а x4=x4.

4. Проверяем условие окончания итерационного процесса | x4-x1 | <= 2e. Если оно выполняется, то определим решение, как x=(x4+x1)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 2.

 

Метод золотого сечения.

 

  Далее я бы хотел остановиться на методе золотого сечения.

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

На первом шаге процесса оптимизации внутри отрезка [] (рис. 1, а) выбираем две внутренние точки х1 и х2 и вычисляем зна­чения целевой функция   и . Поскольку в дан­ном случае   < . очевидно, что минимум располо­жен на одном из  прилегающих к   , отрезков: [] или []. Поэтому отрезок [] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке [] (рис. 1, б), где  = , =. Нужно снова выбрать две внутренние точки, но одна из них () осталась из предыдущего ша­га, поэтому достаточно выбрать лишь одну точку , вы­числить значение  и провести сравнение. Поскольку здесь   >  ясно, что минимум находится на от­резке []. Обозначим этот отрезок [] снова выбе­рем одну внутреннюю точку и повторим процедуру суже­ния  интервала неопределенности. Процесс оптимизации повторяется до тех нор, пока длина очередного отрезка [] не станет меньше задаyной величины .

 

Пропорция золотого сечения равна

Таким образом

Метод золотого сечения относится к тем немногочисленным методам, для которых можно гарантировать, что требуемая точность достигнута.

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

 

Блок-схема метода золотого сечения.

Метод перебора 

В своей  работе я также уделю особое внимание методу перебора.

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

  Суть данного метода состоит в том, заданный интервал разбивается равные отрезки, длина каждого из которых -  N. Также длины этих отрезков можно назвать  шагом разбиения.

Затем вычисляются значения целевой функции  в узлах = а + kN          (k = 0, 1, ..., п). По мере продвижения по интервалу сравниваются значение в данной точке и значения двух соседних узлов. Если значения функции в этих узлах одновременно меньше (или больше),  чем в данной точке, то данная точка является максимумом (или минимумом соответственно).

 

  Хочется отметить, что точность вычислений напрямую зависит от шага разбиения. То есть чем меньше шаг, тем меньше погрешность и соответственно больше точность.


Нужен полный текст этой работы? Напиши заявку cendomzn@yandex.ru

Календарь

«  Сентябрь 2020  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
282930

Рекомендуем:

  • Центральный Дом Знаний
  • Биржа нового фриланса