Реферат: Задачи оптимизации и методы их решения. Обзор

1<m:mathPr> <m:mathFont m:val=«Cambria Math»/> <m:brkBin m:val=«before»/> <m:brkBinSub m:val="--"/> <m:smallFrac m:val=«off»/> <m:dispDef/> <m:lMargin m:val=«0»/> <m:rMargin m:val=«0»/> <m:defJc m:val=«centerGroup»/> <m:wrapIndent m:val=«1440»/> <m:intLim m:val=«subSup»/> <m:naryLim m:val=«undOvr»/> </m:mathPr>Содержание:

 TOC o «1-2» h z u Введение. PAGEREF _Toc154915412 h 3

1.Основные понятия. 4

1.1Определения. 4

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

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

2.1Задачи па экстремум. 6

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

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

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

3.Многомерные задачи оптимизации. 13

3.1Минимум функции нескольких переменных. 13

3.2  Метод покоординатного спуска. 14

3.3  Метод градиентного спуска. 14

4.Задачи с ограничениями. 16

4.1Линейное Программирование. 16

4.2Геометрический метод. 17

4.3  Задача о ресурсах. 19

5.Практическая часть. 23

Списоклитературы. 27

Введение

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

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

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

 

1. Основныепонятия1.1 Определения.

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

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

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

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

U=F(x1, x2,…,xn).                              (1.1)

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

            В случае одногопроектного параметра <img src="/cache/referats/26211/image002.gif" v:shapes="_x0000_i1025"> целевая функция (1.1)является функцией одной переменной, и се график — некоторая кривая наплоскости. При <img src="/cache/referats/26211/image004.gif" v:shapes="_x0000_i1026"> целевая функцияявляется функцией двух переменных, и ее график — поверхность в трехмерномпространстве.

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

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

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

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

Условные задачи оптимизации, или задачи сограничениями, это такие, при  формулировке которых задаются некоторые условия(ограничения) на множестве <img src="/cache/referats/26211/image006.gif" v:shapes="_x0000_i1027">

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

в результате ограниченийобласть проектирования <img src="/cache/referats/26211/image006.gif" v:shapes="_x0000_i1028">, определяемая всеми проектными параметрами,может быть существенно уменьшена в соответствии с физической сущностью задачи.

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

 2. Одномернаяоптимизация2.1 Задачи па экстремум.

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

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

                                             <img src="/cache/referats/26211/image009.gif" v:shapes="_x0000_i1029"> 

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

Будемрассматривать методы оптимизации для разных классов целевых функций. Простейшимиз них является случай дифференцируемой функции F(х) на отрезке [а, b], причем функция задана в виде аналитическойзависимости у = F(х), иможет быть найдено явное выражение для ее производной ‚<img src="/cache/referats/26211/image011.gif" v:shapes="_x0000_i1030"> экстремумов таких функций можно проводитьизвестными из курса высшей математики методами дифференциального исчисления. Напомнимвкратце этот путь.

Функция‚<img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1031"> может достигать своегонаименьшего и наибольшего значений либо в граничных точках отрезка [а, b], либо в точках минимума и максимума.Последние точки обязательно должны быть критическими, т. е. производная <img src="/cache/referats/26211/image011.gif" v:shapes="_x0000_i1032"> в этих точкахобращается в нуль, — это необходимое условие экстремума. Следовательно, дляопределения наименьшего или наибольшего значений функции ‚<img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1033"> на отрезке [а, b] нужно вычислить еезначения во всех критических точках данного отрезка и в его граничных точках исравнить полученные значения; наименьшее или наибольшее из них и будет искомымзначением.

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

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

Численныеметоды поиска экстремальных значений функции рассмотрим на примере нахожденияминимума функции <img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1034"> на отрезке [а., b]. Будем предполагать, чтоцелевая функция унимодальна, т.е. наданном отрезке она имеет только один минимум. Отметим, что в инженернойпрактике обычно встречаются именно такие целевые функции.

Погрешность приближенногорешения задачи определяется разностью между оптимальным значением x проектногопараметра и приближение к  нему х.Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимогозначения а:

<img src="/cache/referats/26211/image018.gif" v:shapes="_x0000_i1035">                  (2.1)

Процессрешения задачи методом поиска состоит в последовательном сужении интервалаизменения проектного параметра, называемого интерваломнеопределенности. В начале процесса оптимизации его длина равна <img src="/cache/referats/26211/image020.gif" v:shapes="_x0000_i1036"><img src="/cache/referats/26211/image022.gif" v:shapes="_x0000_i1037"><img src="/cache/referats/26211/image024.gif" v:shapes="_x0000_i1038"><img src="/cache/referats/26211/image026.gif" v:shapes="_x0000_i1039"><img src="/cache/referats/26211/image028.gif" v:shapes="_x0000_i1040">

Наиболеепростым способом сужения интервала является деление его на некоторое число равныхчастей с последующим вычислением значений целевой функции в точках разбиения. Пусть- число элементарных отрезков, <img src="/cache/referats/26211/image030.gif" v:shapes="_x0000_i1041"> - шаг разбиения. Вычислим значения целевой функции <img src="/cache/referats/26211/image032.gif" v:shapes="_x0000_i1042"> в узлах <img src="/cache/referats/26211/image034.gif" v:shapes="_x0000_i1043"><img src="/cache/referats/26211/image036.gif" v:shapes="_x0000_i1044"><img src="/cache/referats/26211/image038.gif" v:shapes="_x0000_i1045"><img src="/cache/referats/26211/image040.gif" v:shapes="_x0000_i1046">

Число <img src="/cache/referats/26211/image042.gif" v:shapes="_x0000_i1047"><img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1048"> на отрезке <img src="/cache/referats/26211/image045.gif" v:shapes="_x0000_i1049"><img src="/cache/referats/26211/image047.gif" v:shapes="_x0000_i1050"><img src="/cache/referats/26211/image049.gif" v:shapes="_x0000_i1051"> зависит от числаточек, и для непрерывной функции <img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1052">

<img src="/cache/referats/26211/image052.gif" v:shapes="_x0000_i1053">

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

Вданном методе, который можно назвать методом перебора, главная трудностьсостоит в выборе <img src="/cache/referats/26211/image054.gif" v:shapes="_x0000_i1054"> и оценке погрешности. Можно,например, провести оптимизацию с разными шагами и исследовать сходимость такогоитерационного процесса. Но это трудоемкий путь.

Болееэкономичным способом уточнения оптимального параметра является использованиесвойства унимодальности целевой функции, это позволяет построить процесс суженияинтервала неопределенности. Пусть, как и ранее, среди всех значенийунимодальной функции <img src="/cache/referats/26211/image056.gif" v:shapes="_x0000_i1055"><img src="/cache/referats/26211/image058.gif" v:shapes="_x0000_i1056"><img src="/cache/referats/26211/image060.gif" v:shapes="_x0000_i1057"><img src="/cache/referats/26211/image062.gif" v:shapes="_x0000_i1058"><img src="/cache/referats/26211/image064.gif" v:shapes="_x0000_i1059">

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

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

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

Припостроении процесса оптимизации стараются сократить объем вычислений и времяпоиска. Этого достигают обычно путем сокращения количества вычислений (илиизмерений — при проведении эксперимента) значений целевой функции <img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1060"><img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1061">  достигается наилучшаяточность, является метод золотого сечения.Он состоит в построении последовательности отрезков <img src="/cache/referats/26211/image068.gif" v:shapes="_x0000_i1062"><img src="/cache/referats/26211/image070.gif" v:shapes="_x0000_i1063"><img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1064"><img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1065"> проводится лишь водной точке. Эта точка, называемая золотымсечением, выбирается специальным образом.

Пояснимсначала идею метода геометрически, а затем выведем необходимые соотношения. Папервом шаге процесса оптимизации внутри отрезка <img src="/cache/referats/26211/image068.gif" v:shapes="_x0000_i1066"> выбираем некоторыевнутренние точки <img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1067"> и <img src="/cache/referats/26211/image077.gif" v:shapes="_x0000_i1068"><img src="/cache/referats/26211/image079.gif" v:shapes="_x0000_i1069"> и<img src="/cache/referats/26211/image081.gif" v:shapes="_x0000_i1070"><img src="/cache/referats/26211/image083.gif" v:shapes="_x0000_i1071"><img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1072"> отрезков: <img src="/cache/referats/26211/image086.gif" v:shapes="_x0000_i1073"> или <img src="/cache/referats/26211/image088.gif" v:shapes="_x0000_i1074"><img src="/cache/referats/26211/image090.gif" v:shapes="_x0000_i1075"> можно отбросить, сузивтем самым первоначальный интервал неопределенности.

Второйшаг проводим на отрезке<img src="/cache/referats/26211/image070.gif" v:shapes="_x0000_i1076"><img src="/cache/referats/26211/image093.gif" v:shapes="_x0000_i1077"><img src="/cache/referats/26211/image095.gif" v:shapes="_x0000_i1078"> осталась изпредыдущего шага, поэтому достаточно выбрать лишь одну точку <img src="/cache/referats/26211/image097.gif" v:shapes="_x0000_i1079"><img src="/cache/referats/26211/image099.gif" v:shapes="_x0000_i1080"> и провести сравнение.Поскольку здесь <img src="/cache/referats/26211/image101.gif" v:shapes="_x0000_i1081"><img src="/cache/referats/26211/image103.gif" v:shapes="_x0000_i1082"><img src="/cache/referats/26211/image105.gif" v:shapes="_x0000_i1083"><img src="/cache/referats/26211/image107.gif" v:shapes="_x0000_i1084"> не станет меньшезаданной величины <img src="/cache/referats/26211/image022.gif" v:shapes="_x0000_i1085">

Теперьрассмотрим способ размещения внутренних точек на каждом отрезке <img src="/cache/referats/26211/image107.gif" v:shapes="_x0000_i1086">l, а точка деления разбиваетего на части <img src="/cache/referats/26211/image111.gif" v:shapes="_x0000_i1087">

<img src="/cache/referats/26211/image113.gif" v:shapes="_x0000_i1088">                         (2.2)

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

<img src="/cache/referats/26211/image115.gif" v:shapes="_x0000_i1089">

Преобразуем,выражение (2.2) и найдем значения <img src="/cache/referats/26211/image117.gif" v:shapes="_x0000_i1090"><img src="/cache/referats/26211/image119.gif" v:shapes="_x0000_i1091">

<img src="/cache/referats/26211/image121.gif" v:shapes="_x0000_i1092">

Посколькупас интересует только положительное решение, то

<img src="/cache/referats/26211/image123.gif" v:shapes="_x0000_i1093">

Очевидно,что интервал неопределенности можно разделить в соотношении золотого сечениядвояко: в пропорциях <img src="/cache/referats/26211/image125.gif" v:shapes="_x0000_i1094"> и <img src="/cache/referats/26211/image127.gif" v:shapes="_x0000_i1095"><img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1096"> и <img src="/cache/referats/26211/image077.gif" v:shapes="_x0000_i1097"> выбираются с учетомэтих пропорций. В данном случае имеем

<img src="/cache/referats/26211/image131.gif" v:shapes="_x0000_i1098">     (2.3)

Аналогично,

<img src="/cache/referats/26211/image133.gif" v:shapes="_x0000_i1099">                (2.4)

Начальнаядлина интервала неопределенности составляет <img src="/cache/referats/26211/image135.gif" v:shapes="_x0000_i1100"><img src="/cache/referats/26211/image070.gif" v:shapes="_x0000_i1101">

<img src="/cache/referats/26211/image138.gif" v:shapes="_x0000_i1102">

На  втором шаге отрезок <img src="/cache/referats/26211/image140.gif" v:shapes="_x0000_i1103"> также делится всоотношении золотого сечения. При этом одной из точек деления будет точка <img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1104">

<img src="/cache/referats/26211/image143.gif" v:shapes="_x0000_i1105">

Последнееравенство следует из соотношения <img src="/cache/referats/26211/image145.gif" v:shapes="_x0000_i1106">

Втораяточка деления <img src="/cache/referats/26211/image097.gif" v:shapes="_x0000_i1107"> выбирается так же, каквыбирается точка <img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1108"> при деления отрезка <img src="/cache/referats/26211/image068.gif" v:shapes="_x0000_i1109"><img src="/cache/referats/26211/image150.gif" v:shapes="_x0000_i1110">

<img src="/cache/referats/26211/image152.gif" v:shapes="_x0000_i1111">

Поаналогии с соотношениями (2.3), (2.4) можно записать координаты точек деления <img src="/cache/referats/26211/image154.gif" v:shapes="_x0000_i1112"> и <img src="/cache/referats/26211/image156.gif" v:shapes="_x0000_i1113"><img src="/cache/referats/26211/image158.gif" v:shapes="_x0000_i1114"> на k-м шаге оптимизация <img src="/cache/referats/26211/image160.gif" v:shapes="_x0000_i1115">

<img src="/cache/referats/26211/image162.gif" v:shapes="_x0000_i1116">

Вычислению,естественно, подлежит только одна из координат <img src="/cache/referats/26211/image164.gif" v:shapes="_x0000_i1117">

<img src="/cache/referats/26211/image166.gif" v:shapes="_x0000_i1118">           (2.5)

Как я вобщем случае метода поиска, процесс оптимизации заканчивается при выполненииусловия <img src="/cache/referats/26211/image168.gif" v:shapes="_x0000_i1119"><img src="/cache/referats/26211/image170.gif" v:shapes="_x0000_i1120"><img src="/cache/referats/26211/image172.gif" v:shapes="_x0000_i1121"> или <img src="/cache/referats/26211/image174.gif" v:shapes="_x0000_i1122"><img src="/cache/referats/26211/image176.gif" v:shapes="_x0000_i1123">

<img src="/cache/referats/26211/image178.gif" v:shapes="_x0000_i1124">                         (2.6)

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

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

Какбыло отмечено в п. 2.1, задача одномерной оптимизации дифференцируемой функции <img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1125"> сводится к нахождениюкритических точек этой функции, определяемых уравнением

<img src="/cache/referats/26211/image181.gif" v:shapes="_x0000_i1126">                    (2.7)

Когдауравнение (2.7) нельзя решить аналитически, для его решения можно применитьчисленные методы, например метод Ньютона. В этом случае говорят о методе Ньютона решения задачи оптимизации.

Пусть <img src="/cache/referats/26211/image183.gif" v:shapes="_x0000_i1127"> - решение уравнения(2.7), а <img src="/cache/referats/26211/image185.gif" v:shapes="_x0000_i1128"> некоторое начальное

приближение к <img src="/cache/referats/26211/image187.gif" v:shapes="_x0000_i1129"><img src="/cache/referats/26211/image189.gif" v:shapes="_x0000_i1130"><img src="/cache/referats/26211/image191.gif" v:shapes="_x0000_i1131"><img src="/cache/referats/26211/image193.gif" v:shapes="_x0000_i1132">

<img src="/cache/referats/26211/image195.gif" v:shapes="_x0000_i1133">

подставим вместо <img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1134"> производную <img src="/cache/referats/26211/image011.gif" v:shapes="_x0000_i1135"> и получим тем самым формулудля   <img src="/cache/referats/26211/image193.gif" v:shapes="_x0000_i1136">

<img src="/cache/referats/26211/image199.gif" v:shapes="_x0000_i1137">             (2.8)

для использования этойформулы необходимо, чтобы <img src="/cache/referats/26211/image201.gif" v:shapes="_x0000_i1138">   качестве критерияокончания итерационного процесса можно применить условия близости двухпоследовательных приближений

<img src="/cache/referats/26211/image203.gif" v:shapes="_x0000_i1139">

или близости значений целевойфункции на этих приближениях

<img src="/cache/referats/26211/image205.gif" v:shapes="_x0000_i1140">

Достаточноеусловие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующаятеорема.

Теорема.  Пусть <img src="/cache/referats/26211/image183.gif" v:shapes="_x0000_i1141"><img src="/cache/referats/26211/image208.gif" v:shapes="_x0000_i1142">  <img src="/cache/referats/26211/image210.gif" v:shapes="_x0000_i1143"> и<img src="/cache/referats/26211/image212.gif" v:shapes="_x0000_i1144"> непрерывна. Тогдасуществуют окрестность корня <img src="/cache/referats/26211/image214.gif" v:shapes="_x0000_i1145"> такая, что еслиначальное приближение <img src="/cache/referats/26211/image185.gif" v:shapes="_x0000_i1146"> принадлежит этойокрестности, то для метода Ньютона (2.8) последовательность значений <img src="/cache/referats/26211/image217.gif" v:shapes="_x0000_i1147">  сходится к <img src="/cache/referats/26211/image187.gif" v:shapes="_x0000_i1148"> при <img src="/cache/referats/26211/image220.gif" v:shapes="_x0000_i1149">

Заметим,что точка <img src="/cache/referats/26211/image183.gif" v:shapes="_x0000_i1150">  может являться как точкой минимума, так и точкоймаксимума, а может (при <img src="/cache/referats/26211/image222.gif" v:shapes="_x0000_i1151"><img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1152"> имеет как минимумы,так и максимум то она может сходиться и к точкам минимума, и к точкам максимумав зависимости от того, из окрестности какой критической точки взято начальноеприближение. При этом, в отличие от других методов оптимизации, формула дляпоиска максимума функции совпадает с формулой для поиска минимума.

Формулуметода Ньютона решения задачи оптимизации можно получить и из другихсоображений. Разложим функцию <img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1153"> в ряд Тейлора вокрестности точки <img src="/cache/referats/26211/image224.gif" v:shapes="_x0000_i1154"><img src="/cache/referats/26211/image226.gif" v:shapes="_x0000_i1155">

<img src="/cache/referats/26211/image228.gif" v:shapes="_x0000_i1156"><img src="/cache/referats/26211/image230.gif" v:shapes="_x0000_i1157"> (2.9)

Вкачестве следующего приближения <img src="/cache/referats/26211/image232.gif" v:shapes="_x0000_i1158"> к оптимальномузначению проектного параметра <img src="/cache/referats/26211/image234.gif" v:shapes="_x0000_i1159"> возьмем точкуэкстремума функции <img src="/cache/referats/26211/image236.gif" v:shapes="_x0000_i1160">

<img src="/cache/referats/26211/image238.gif" v:shapes="_x0000_i1161">

 что совпадает с (2.8). Разложение (2.9) вокрестности точки <img src="/cache/referats/26211/image185.gif" v:shapes="_x0000_i1162"><img src="/cache/referats/26211/image013.gif" v:shapes="_x0000_i1163"> заменяется параболой графикомфункции <img src="/cache/referats/26211/image236.gif" v:shapes="_x0000_i1164">

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

3. Многомерныезадачи оптимизации3.1 Минимум функции нескольких переменных.

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

Минимумдифференцируемой функции многих переменных <img src="/cache/referats/26211/image243.gif" v:shapes="_x0000_i1165"> можно найти, исследуяее значения в критических точках, которые определяются из решения системыдифференциальных уравнений

<img src="/cache/referats/26211/image245.gif" v:shapes="_x0000_i1166">             (3.1)

Рассмотренныйметод можно использовать лишь для дифференцируемой целевой функции. Но и в этомслучае могут возникнуть серьезные трудности при решении систем нелинейныхуравнений (3.1).

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

Длярешения подобной задачи в области проектирования, <img src="/cache/referats/26211/image247.gif" v:shapes="_x0000_i1167"> в которой ищетсяминимум целевой функции <img src="/cache/referats/26211/image243.gif" v:shapes="_x0000_i1168"><img src="/cache/referats/26211/image250.gif" v:shapes="_x0000_i1169"> на части с шагам <img src="/cache/referats/26211/image252.gif" v:shapes="_x0000_i1170">

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

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

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

Пустьтребуется найти наименьшее значение целевой функции <img src="/cache/referats/26211/image243.gif" v:shapes="_x0000_i1171"> в <img src="/cache/referats/26211/image255.gif" v:shapes="_x0000_i1172"><img src="/cache/referats/26211/image257.gif" v:shapes="_x0000_i1173"> <img src="/cache/referats/26211/image259.gif" v:shapes="_x0000_i1174"><img src="/cache/referats/26211/image261.gif" v:shapes="_x0000_i1175"> фукция однойпеременной <img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1176"><img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1177"> в направлении убыванияфункции <img src="/cache/referats/26211/image265.gif" v:shapes="_x0000_i1178"> от точки  <img src="/cache/referats/26211/image267.gif" v:shapes="_x0000_i1179"> до некоторой точки <img src="/cache/referats/26211/image269.gif" v:shapes="_x0000_i1180"><img src="/cache/referats/26211/image271.gif" v:shapes="_x0000_i1181"> дифференцируемая, тозначение <img src="/cache/referats/26211/image273.gif" v:shapes="_x0000_i1182"> может быть найдено  

<img src="/cache/referats/26211/image275.gif" v:shapes="_x0000_i1183">                            (3.2)

            Зафиксируемтеперь все координаты кроме <img src="/cache/referats/26211/image077.gif" v:shapes="_x0000_i1184"><img src="/cache/referats/26211/image278.gif" v:shapes="_x0000_i1185"><img src="/cache/referats/26211/image077.gif" v:shapes="_x0000_i1186"><img src="/cache/referats/26211/image280.gif" v:shapes="_x0000_i1187"> от точки <img src="/cache/referats/26211/image282.gif" v:shapes="_x0000_i1188"> до точки <img src="/cache/referats/26211/image284.gif" v:shapes="_x0000_i1189"><img src="/cache/referats/26211/image286.gif" v:shapes="_x0000_i1190"> можно найти

<img src="/cache/referats/26211/image288.gif" v:shapes="_x0000_i1191">

Аналогичнопроводится спуск по координатам <img src="/cache/referats/26211/image290.gif" v:shapes="_x0000_i1192"><img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1193"> до <img src="/cache/referats/26211/image292.gif" v:shapes="_x0000_i1194"><img src="/cache/referats/26211/image294.gif" v:shapes="_x0000_i1195"><img src="/cache/referats/26211/image296.gif" v:shapes="_x0000_i1196">

Налюбом k-том шаге этотпроцесс можно прервать. И значение функции в точке k принимается вкачестве наименьшего значения целевой функции в рассматриваемой области.

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

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

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

Переходяна математический язык, заключаем, что направление наискорейшего спускасоответствует направлению наибольшего убывания функции. Из курса математикиизвестно, что направление наибольшего возрастания функции двух переменных <img src="/cache/referats/26211/image298.gif" v:shapes="_x0000_i1197">  характеризуется ее градиентом

<img src="/cache/referats/26211/image300.gif" v:shapes="_x0000_i1198">

Где <img src="/cache/referats/26211/image302.gif" v:shapes="_x0000_i1199"> единичные векторы(орты) в направлении координатных осей. Следовательно, направление, противоположноеградиентному, укажет направление наибольшего убывания функции. Методы,основанные на выборе пути оптимизации с помощью градиента, называются градиентными. Идея метода градиентногоспуска состоит в следующем. Выбираем некоторую начальную точку <img src="/cache/referats/26211/image304.gif" v:shapes="_x0000_i1200">

<img src="/cache/referats/26211/image306.gif" v:shapes="_x0000_i1201">

Врезультате приходим в точку <img src="/cache/referats/26211/image308.gif" v:shapes="_x0000_i1202"><img src="/cache/referats/26211/image310.gif" v:shapes="_x0000_i1203"><img src="/cache/referats/26211/image312.gif" v:shapes="_x0000_i1204">

<img src="/cache/referats/26211/image314.gif" v:shapes="_x0000_i1205">

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

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

<img src="/cache/referats/26211/image316.gif" v:shapes="_x0000_i1206">

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

<img src="/cache/referats/26211/image318.gif" v:shapes="_x0000_i1207">

Дляминимизации <img src="/cache/referats/26211/image320.gif" v:shapes="_x0000_i1208"> можно использоватьодин из методов одномерной оптимизации. Можно и просто двигаться в направлении,противоположном градиенту, делая при этом не один шаг, а несколько шагов до техпор, пока целевая функция не перестанет убывать. В найденной новой точке сноваопределяют направление спуска (с помощью градиента) и ищут новую точку минимумацелевой функции и т. д. В этом методе спуск происходит гораздо более крупнымишагами, и градиент функции вычисляется в меньшем числе точек.

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

4. Задачи сограничениями4.1 Линейное Программирование.

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

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

1)     

<img src="/cache/referats/26211/image322.gif" v:shapes="_x0000_i1209">                 (4.1)

      2)  являются неотрицательными, т. е.

<img src="/cache/referats/26211/image324.gif" v:shapes="_x0000_i1210">              (4.2)

      3)  обеспечивают наименьшее значение линейнойцелевой функции

<img src="/cache/referats/26211/image326.gif" v:shapes="_x0000_i1211">          (4.3)

Всякоерешение системы уравнений (4.1), удовлетворяющее системе неравенств (4.2),называется допустимым решением. Допустимоерешение, которое минимизирует целевую функцию (4.3), называется оптимальным  решением.

4.2 Геометрический метод.

Областьюрешения линейного неравенства с двумя переменными

<img src="/cache/referats/26211/image328.gif" v:shapes="_x0000_i1212">                  (4.4)

является полуплоскость.Для того чтобы определить, какая из двух полуплоскостей соответствует этомунеравенству, нужно привести его к виду <img src="/cache/referats/26211/image330.gif" v:shapes="_x0000_i1213"> или <img src="/cache/referats/26211/image332.gif" v:shapes="_x0000_i1214"><img src="/cache/referats/26211/image334.gif" v:shapes="_x0000_i1215"><img src="/cache/referats/26211/image336.gif" v:shapes="_x0000_i1216">  (4.4)имеет вид <img src="/cache/referats/26211/image338.gif" v:shapes="_x0000_i1217"><img src="/cache/referats/26211/image340.gif" v:shapes="_x0000_i1218"><img src="/cache/referats/26211/image342.gif" v:shapes="_x0000_i1219"> - левую полуплоскость.

            Областью решений системы являетсяпересечение конечного числа полуплоскостей, описываемых каждым отдельнымнеравенством вида (4.4). Это пересечение представляет собой многоугольную область<img src="/cache/referats/26211/image247.gif" v:shapes="_x0000_i1220">

Областьрешений <img src="/cache/referats/26211/image247.gif" v:shapes="_x0000_i1221"> обладает важнымсвойством выпуклости. Область  называетсявыпуклой, если произвольные две ееточки можно соединить отрезком, целиком принадлежащим данной области.

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

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

Основываясьна введенных понятиях, рассмотрим геометрическийметод решения задачи линейного программирования. Пусть заданы линейная целеваяфункция <img src="/cache/referats/26211/image346.gif" v:shapes="_x0000_i1222"> двух независимых переменных,а также некоторая совместная система линейных неравенств, описывающих областьрешений <img src="/cache/referats/26211/image247.gif" v:shapes="_x0000_i1223"><img src="/cache/referats/26211/image348.gif" v:shapes="_x0000_i1224"> найти такое, прикотором линейная целевая функция <img src="/cache/referats/26211/image271.gif" v:shapes="_x0000_i1225"> принимает наименьшеезначение.

Положимфункцию <img src="/cache/referats/26211/image271.gif" v:shapes="_x0000_i1226"> равной некоторомупостоянному значению <img src="/cache/referats/26211/image352.gif" v:shapes="_x0000_i1227">

<img src="/cache/referats/26211/image354.gif" v:shapes="_x0000_i1228">              (4.5)

Припараллельном переносе этой прямой в положительном направлении вектора нормали <img src="/cache/referats/26211/image356.gif" v:shapes="_x0000_i1229"> линейная функция <img src="/cache/referats/26211/image271.gif" v:shapes="_x0000_i1230"> будет возрастать, апри переносе прямой в противоположном направлении — убывать.

Действительно,пусть при параллельном переносе точка <img src="/cache/referats/26211/image358.gif" v:shapes="_x0000_i1231"><img src="/cache/referats/26211/image360.gif" v:shapes="_x0000_i1232"><img src="/cache/referats/26211/image362.gif" v:shapes="_x0000_i1233">

<img src="/cache/referats/26211/image364.gif" v:shapes="_x0000_i1234">

Поскольку

<img src="/cache/referats/26211/image366.gif" v:shapes="_x0000_i1235">

Есливектор <img src="/cache/referats/26211/image368.gif" v:shapes="_x0000_i1236"> сонаправлен с вектором<img src="/cache/referats/26211/image054.gif" v:shapes="_x0000_i1237"><img src="/cache/referats/26211/image371.gif" v:shapes="_x0000_i1238"> и <img src="/cache/referats/26211/image373.gif" v:shapes="_x0000_i1239"><img src="/cache/referats/26211/image375.gif" v:shapes="_x0000_i1240">

Предположим,что прямая, записанная в виде (4.5), при параллельном переносе в положительномнаправлении вектора  первый развстретится с областью допустимых решений <img src="/cache/referats/26211/image247.gif" v:shapes="_x0000_i1241"> в некоторой еевершине, при этом значение целевой функции равно <img src="/cache/referats/26211/image378.gif" v:shapes="_x0000_i1242"><img src="/cache/referats/26211/image378.gif" v:shapes="_x0000_i1243"> будет минимальным,поскольку дальнейшее движение прямой в том же направлении приведет к увеличениюзначения <img src="/cache/referats/26211/image271.gif" v:shapes="_x0000_i1244">

Если взадаче оптимизации нас интересует максимальное значение целевой функции, топараллельный перенос прямой (4.5) осуществляется в направлении, противоположном<img src="/cache/referats/26211/image054.gif" v:shapes="_x0000_i1245"><img src="/cache/referats/26211/image271.gif" v:shapes="_x0000_i1246">

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

4.3  Задача оресурсах.

Враспоряжении бригады имеются следующие ресурсы: <st1:metricconverter ProductID=«300 кг» w:st=«on»>300 кг</st1:metricconverter> металла, <st1:metricconverter ProductID=«100 м2» w:st=«on»>100 м2</st1:metricconverter> стекла,160 чел.-ч. (человеко-часов) рабочего времени. Бригаде поручено изготовить два наименованияизделий: А и Б. Цена одного изделия А -1 тыс. р., для его изготовлениянеобходимо <st1:metricconverter ProductID=«4 кг» w:st=«on»>4 кг</st1:metricconverter>металла, <st1:metricconverter ProductID=«2 м2» w:st=«on»>2 м2</st1:metricconverter>стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1,2 тыс. для егоизготовления необходимо <st1:metricconverter ProductID=«5 кг» w:st=«on»>5 кг</st1:metricconverter>металла, <st1:metricconverter ProductID=«1 м2» w:st=«on»>1 м2</st1:metricconverter>стекла и 3 чел.-ч. рабочего времени. Требуется  так спланировать  объем выпуска продукции, чтобы ее стоимостьбыла максимальной.

Сначаласформулируем задачу математически. Обозначим через <img src="/cache/referats/26211/image075.gif" v:shapes="_x0000_i1247"> и <img src="/cache/referats/26211/image077.gif" v:shapes="_x0000_i1248"> количество изделий А иБ, которое необходимо запланировать (т.е. это искомые величины). Имеющиеся ресурсысырья и рабочего времени  зададим в видеограничений-неравенств:

<img src="/cache/referats/26211/imag

еще рефераты
Еще работы по математике