Реферат: Сравнительный анализ методов оптимизации

Министерствообразования и науки Республики Казахстан

КарагандинскийГосударственный Технический Университет

Кафедра САПР

ПОЯСНИТЕЛЬНАЯЗАПИСКА

к курсовойработе

по дисциплине«Теория принятия решений»

Тема:«Сравнительный анализ методов оптимизации»

Караганда2009

Введение

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

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

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

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

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

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

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

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

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

f(xi) ®min (max), хiÎ U

гдеf(xi) – целевая функция, а U – допустимоемножество, заданное ограничениями на управляемые переменные. Значениепараметров f(xi) ®min (max) при которых достигается min(max), называется оптимальным решением.

2. Численные методы одномернойбезусловной оптимизации

Числох* Î U называется точкой глобального (абсолютного)минимума функции f (x) на множестве U, если f (x*) £ f (x) для всех хÎ U.

Значениеf * = f (x*) = /> называютглобальным (абсолютным) минимумом или просто минимумом функции f (x) намножестве U.

Множествовсех точек минимума f (x) на U будем в дальнейшем обозначать через U*.

Число/> ÎU называется точкой локального минимума функции f (x), если />для всех xÎU, достаточно близких к />, т.е. если существует e > 0 такое, что это неравенство выполняется для любого/>/>.

Глобальныйминимум f (x) является и локальным минимумом, а обратное, неверно.

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

Функцияf(x) называется унимодальнойна отрезке [а; b], если она непрерывна на [а; b] и существуютчисла a и b, />,такие, что:

1)если а < a, то на отрезке [a; a] функция f(x) монотонноубывает;

2)если b < b, то на отрезке [b; b] функция f(x) монотонновозрастает;

3)при х Î [a; b] f(x) =f* = />.

Возможновырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезковмонотонности и постоянства унимодальной функции показаны на.

Основныесвойства унимодальных функций:

1.Любая из точек локального минимума унимодальной функции является и точкой ееглобального минимума на отрезке [а; b].

2.Функция, унимодальная на отрезке [а; b], является унимодальной и на любомменьшем отрезке [с; d] /> [а; b].

3.Пусть f (x) />Q[а; b] и />. Тогда:

если/>, то x* /> [a; x2];

если/>, то x* /> [x1; b],

гдех* – одна из точек минимума f (x) на отрезке [a; b].

Изчисленных методов одномерной безусловной оптимизации рассмотрим два:

1. метод дихотомии

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

2.1 Метод дихотомии

Вэтом методе точки x1 и х2располагаются близко к середине очередного отрезка [а; b], т.е:

/> ,

гдеd > 0 – малое число. При этом отношение длиннового и исходного отрезков /> близко к 1/2,этим и объясняется название метода.

Отметим,что для любых точек x1 и х2величина t > 1/2, поэтому указанный выбор пробных точекобъясняется стремлением обеспечить максимально возможное относительноеуменьшение отрезка на каждой итерации поиска х*.

Вконце вычислений по методу дихотомии в качестве приближенного значения х* берутсередину последнего из найденных отрезков [а; b], убедившисьпредварительно, что достигнуто неравенство />.

Опишемалгоритм метода деления отрезка пополам.

Шаг1. Определить x1 и х2по формулам (2.11). Вычислить f(x1) и f(x2).

Шаг2. Сравнить f(x1) и f(x2). Если />, то перейти к отрезку [а; x2], положив b= x2, иначе – котрезку [x1; b], положив а= x1 .

Шаг3. Найти достигнутую точность /> Если />, то перейти к следующейитерации, вернувшись к шагу 1. Если />, то завершитьпоиск х*

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

Рассмотримтакое симметричное расположение точек x1 и х2на отрезке [а; b], при котором одна из них становитсяпробной точкой и на новом отрезке, полученном после исключения части исходногоотрезка. Использование таких точек позволяет на каждой итерации методаисключения отрезков, кроме первой, ограничиться определением только одногозначения f(x), таккак другое значение уже найдено на одной из предыдущих итераций.

Рассмотримсначала отрезок [0; 1] и для определенности предположим, что при его уменьшенииисключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 =1–t (рис.2.2).

Рис. 2.2.-Определение пробных точек вметоде золотого сечения

Пробнаяточка х1 отрезка [0; 1] перейдет в пробную точку х2¢ = 1–t нового отрезка [0; т]. Чтобы точки х2 = t, и х2¢ = 1–t делили отрезки [0; 1] и [0; t] в одном и томже отношении, должно выполняться равенство /> или />, откуда находим положительноезначение />… Таким образом, х1 =1–t = />, />.

Дляпроизвольного отрезка [а; b] выражения дляпробных точек примут вид

/>; />.

1.Точки x1 и х2 обладаютследующим свойством: каждая из них делит отрезок [а; b] на двенеравные части так, что отношение длины всего отрезка к длине его большей частиравно отношению длин большей и меньшей частей отрезка. Точки с таким свойствомназываются точками золотого сечения отрезка [а; b].

2.На каждой итерации исключения отрезков с пробными точками одна из них /> переходит на следующий отрезоки значениеf(x) в этой точкевычислять не следует. Если новым отрезком становится [а; х2],то на него переходит пробная точка/> исходногоотрезка, становясь его второй пробной точкой (х2’=х1) (рис. 2.2). В случае перехода к отрезку [х1;b] пробная точка /> исходногоотрезка становится первой пробной точкой отрезка [х1; b].

3.Легко проверить, что х1=а+b–х2, и x2=а+b–х1. Поэтому накаждой итерации метода золотого сечения недостающую пробную точку нового отрезкаможно найти по перешедшей на него пробной точке с помощью сложения и вычитания.

4.В конце вычислений по методу золотого сечения в качестве приближенного значениях* можно взять середину последнего из полученных отрезков />.

Накаждой итерации отрезок поиска точки минимума уменьшается в одном и том жеотношении />, поэтому в результате питераций его длина становится />. Такимобразом, точность en определенияточки х* после п итераций находятиз равенства/>, а условием окончания поискаточки х* с точностью e служит неравенство en £ e.

2.3 Пример решенияметодами дихотомии и золотого сечения

Данафункция />,где d=2, e=1

Необходимонайти минимум на отрезке [a,b], где />, />, т.е. на отрезке [7.23,8.21]

Составитьпрограмму, которая выдаст число итераций при точности ε=0,001

Решитьдвумя методами: дихотомии и золотого сечения

Решение методом дихотомии:

Шаг 1:

Шаг 2: Так как f1<f2

Шаг 3: Так как f1<f2

Решениеметодом золотого сечения:

Шаг 1:

Шаг 2: Так как f1<f2

Шаг 3: Так как f1<f2

Так как f1<f2

Листингпрограммы реализующей методы дихотомии и золотого сечения представлен вприложении А

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

Рассмотримконкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х)® min, xÎ En, которыеопираются только на вычисление значений функции f (х), т.е. прямые методыминимизации. Важно отметить, что для их применения не требуетсядифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишьиметь возможность вычислять или измерять значения f (х) в произвольных точках.Такие ситуации часто встречаются в практически важных задачах оптимизации.

3.1 Поиск точки minметодом правильного симплекса

Впространстве E2 правильным симплексом является совокупность вершинравностороннего треугольника, в E3 – правильного тетраэдра.

Еслих0– одна из вершин правильного симплекса в En то координатыостальных n вершин х1 ,.., хn можно найти,например, по формулам:

/> (3.1)

гдеd1/>, d2/>, a– длина ребра. Вершину х0симплекса, построенного по формулам (3.1), будем называть бaзовой.

Поизвестному симплексу можно построить новый симплекс отрaжением какой–либовершины, например, хk симметрично относительно центра тяжести хcостальных вершин симплекса.

Пустьзадана функция f(x,y) ® min и начальный базис (x0,y0).

Новаяи старая вершины связаны соотношением:

/>, где xc/>

/>, где уc/>(3.2)

Вычисляемзначение функции в точках f(A), f(B), f(D) (пусть f(A)<f(B)<f(D)) иприсваиваем им номера в порядке возрастания A-1, B-2, D-3.

Вершинус наибольшим номером отражаем относительно центра тяжести стороны 1-2

Координатывершины Е:

/>(3.3)

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

3.2 Поиск точки minметодом деформируемого симплекса

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

/>(3.5)

Таккак величина a Î (0; 1), товыбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствуетотражению, а g > 1 и выбор точки z4 приводит крастяжению симплекса. На практике хорошо зарекомендовал себя следующий наборпараметров a, b и g для выбора пробных точек zi: a = 1/2, b = 1 и g =2.

Рис.3.2. Пробные точки z1,z2,z3,z4 для перехода кновому симплексу

Рис.3.3. Новые симлексы полученные в результате процедур сжатия (а, б); отражения(в); растяжения(г).

Опишемалгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг0 – Шаг 3 Аналогичны методу правильного симплекса.

Шаг4. Найти />и пробные точки zk, k=1, …, 4 пo формулам(3.5). Найти f (z*)= min f (zk). Если f (z*) < f (zn). то положить xn=z* и перейти кшагу 2. Иначе – перейти к шагу 5.

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

Этотметод заключается в последовательной минимизации целевой функции f(x) сначала понаправлению первого базисного вектора е1, затем второго – е2и т.д. После окончания минимизации по направлению последнего базисного вектораеn цикл повторяется.

Опишемэтот алгоритм.

Шаг0. Выбрать х ÎEn, критерийдостижения точности, величину e. Найти f (x), положить j= 1.

Шаг1. Решить задачу одномерной минимизации Ф(a) = f (х + aеj)® min, a Î R, т.е. найти a*. Положить />=х +a*еj, вычислить f (х).

Шаг2. Если j< п, то положить х =/>, j=j+1 и перейти кшагу 1, иначе – перейти к шагу 3.

Шаг3. Проверить условие достижения точности ||х–/>||< e

3.4 Поиск точки minметодом Хука – Дживса

Этоталгоритм содержит две основные процедуры:

а)исследующий покоординатный поиск в окрестности данной точки, предназначенныйдля определения направления убывания f (х);

б)перемещение в направлении убывания.

Опишемалгоритм исследующего покоординатного поиска из заданной точки х с приращениямипо каждой координате Dj, j= 1, …, n

Шаг 1. Положить /> = x, i= 1.

Шаг2. Сделать пробный шаг y=/>– Dje j, где e j–j–й базисныйвектор. Если f (/>) £f(y), то перейти кшагу 3, иначе – к шагу 4.

Шаг3. Сделать пробный шаг y=/>+Dje j. Если f (/>) £f(y), то перейти кшагу 5, иначе – к шагу 4.

Шаг4. Положить />= у.

Шаг5. Положить j= j+ 1. Если j£ n, то перейти кшагу 2. В противном случае исследующий поиск окончен – получена точка /> для которой f(/>) <f(y), если /> ¹ х.

3.5 Пример решенияметодами правильного симплекса, деформируемого симплекса, покоординатногоспуска, Хука – Дживса

Дана функция />, с=7; d=7.

Найти минимумфункции с точностью ε=0,001

Метод правильногосимплекса

Выбираем длину сторонытреугольника l=10ε=0,0001

Вершины треугольниканаходим следующим образом:

A(/>);

B(/>/>);

D(/>/>).

A(1,065;0,918);

B(1,07,0,927);

D(1,075,0,918).

Шаг

F(A)=10,903;F(B)=11,081; F(D)=11,051.

F1<F2<F3:

F1=F(A);F2=F(D); F3=F(B).

Отражаем вершину 3относительно центра тяжести.

F(E)=10,873.

Значение функции внайденной точке меньше, значения функции в точке 1, поэтому принимаем новыйсимплекс (1,2,E).

Шаг 1

F(1)=10,903; F(2)=11,081; F(E)=10,873.

F1<F2<F3:

F1=F(E);F2=F(1); F3=F(2).

Отражаем вершину 3относительно центра тяжести.

F(E)=10,726.

Значение функции внайденной точке меньше, значения функции в точке 1, поэтому принимаем новыйсимплекс (1,2,E).

/>,

/>.

В результате получаем x1=0,125, x2=0,208, f(x1, x2)=-0,41.

Метод деформируемогосимплекса

Выбираем длину сторонытреугольника l=5ε=0,005

Вершины треугольниканаходим следующим образом:

A(/>);

B(/>/>);

D(/>/>).

A(1,065; 0,918);

B(1,07,0,927);

D(1,075,0,918).

Принимаемкоэффициенты выбора пробных точек k1=0,5, k2=1, k3=2.

Шаг

F(A)=10,903;F(B)=11,081; F(D)=11,051.

F1<F2<F3:

F1=F(A); F2=F(D); F3=F(B).

Находим центртяжести вершины 3 относительно вершин 1 и 2:

Выбираем пробные точки:

F(z1)=10,966.

F(z2)=11,018.

F(z3)=11,044.

F(z3)=11,097.

Значение функции в z1 точке меньше, значения функции вточке 3, поэтому принимаем новый симплекс (1,2,z1).

Шаг 1

F(1)= 10,903; F(2)= 11,051; F(z1)=10,966.

F1<F2<F3:

F1=F(1);F2=F(z1); F3=F(2).

Выбираем пробные точки:

F(z1)=10,955.

F(z2)=10,998.

F(z3)=11,019.

F(z3)=11,062.

Значение функции в точке z1 меньше, значения функции в точке 3,поэтому принимаем новый симплекс (1,2,z1).

/>,

/>.

В результате получаем x1=-0,012, x2=0,419, f(x1, x2)=-0,014.

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

(1,065;0,918).

α=5ε=0,005.

Шаг 1

Координату /> закрепляем,

Т.к./>/>,

Следовательно/>

/>/>

Получим x1=0,012, />

Шаг 2

Принимаем /> и закрепляем,

Т.к./>/>,

/>/>

Получим x2=0,199, />

Продолжаем поиск до техпор, пока не будет выполнено условие />

В результате получаем x1=0,117, x2=0,189, f(x1, x2)=-0,411.

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

x0: (1,065; 0,918).

Δ1=5*ε=5*0,001,Δ2=5*ε=5*0,001.

λ=2.

Шаг 1

Принимаемk1=-1, k2=-1 – коэффициенты, определяющие направление поиска.

В данномнаправлении функция убывает.

Шаг 2

Принимаемk1=-1, k2=-1.

В данномнаправлении функция убывает.

Продолжаем поиск до техпор, пока не будет выполнено условие />

В результате получаем x1=0,115, x2=0,198, f(x1, x2)=-0,411.

4.Основы линейного программирования

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

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

Точка оптимальногорешения является крайней точкой пересечения выпуклых множеств,

4.1 Симплекс-методрешения задачи ЛП

Допустим, что естьбазисное решение. Не трудно заметить, что в качестве базисного решения можнопринять:

/>,/>

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

Предполагаем, чтобазисная точка найдена, тогда:

/>,/>

/> – значение функции в базисной точке(базисе).

Тогда значение функции:

/> – симплекс-разность

Тогда в скалярной форме:

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

/>,

Если />, то /> быть не может,следовательно />, т.к. приотрицательном коэффициенте /> можетстать отрицательным.

Это условие необходимое.

Max значение базисной переменной определяется:

/>,/>

где /> – номер столбца, который выводитсяиз базиса.

Если />, то функция может возрастатьнеограниченно.

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

1. по известному базисному решениюстроятся матрицы и находим />;

2. вычисляется симплекс-разности. Из нихвыделяются положительные наибольшие. Соответствующая переменная вводится вбазис;

для выбора выводимойпеременной из базиса вычисляется /> и maxзначение новой базисной переменной />

3. Вычисляются значения новых базисныхпеременных:

4.2 Пример решениязадач ЛП симплекс – методом

Дана функция /> и ограничения

a=3, b=6, c=4, k подобрать таким образом, чтобыобласть была пятиугольной.

Графическое решениезадачи линейного программирования

Чтобы получитьпятиугольную область допустимых значений выберем k=11.2.

Подставив коэффициенты a, b, c, k, получим функцию

Построим областьдопустимых значений

Рисунок 4.1 – Областьдопустимых значений

Чтобы получить максимумцелевой функции будем ее переносить параллельно самой себе до пересечения скрайней точкой области допустимых значений. В данном случае максимум находитсяв точке пересечения функций 6x1+x2=12 и 2x1+4x2=11,2.

Решим систему уравнений:

Получим точку максимумацелевой функции:

Значение функции в этойточке f(x1,x2)=15,927

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

Приведем задачу кстандартной форме записи:

Начальный базис y0(0 0 8 12 11.2).

Процедура поискаоптимальной точки симплекс-методом сведена в таблицу 1.

Таблица 1. Симплекс-таблица

Номер итерации Базисные переменные Значение y1 y2 y3 y4 y5 отношения y3 8 1 3 1 0,125 y4 12 6 1 1 0,5 y5 11,2 2 4 1 0,17857143 -f' 6 3 1 y3 6 2,833333 1 -0,16667 0,4722 y1 2 1 0,166667 0,166667 0,0833 y5 7,2 3,666667 -0,33333 1 0,5093 -f' -12 2 -1 2 y3 0,436363636 1 0,090909 -0,77273 y1 1,672727273 1 0,181818 -0,04545 y2 1,963636364 1 -0,09091 0,272727 -f' -15,92727273 -0,81818 -0,54545

На шаге 2 нетположительных коэффициентов в симплекс разности, значит, решение прекращаем.

Получаем оптимальноезначение целевой функции

5.Определениеоптимальных параметров технического объекта

Рисунок 5.1-Модель сосуда

Параметры сосуда(рис.5.1):

Высота цилиндров – h1

Высота параллелепипеда – h2

Высота усеченного конуса– h3

Длина параллелепипеда – а

Ширина параллелепипеда –а

Радиус нижнего основанияусеченного конуса – R

Радиус верхнего основанияусеченного конуса – r

Соотношения параметров:

2h1 = 2h2 = h3 = H

a = 2R = 4r = x

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

Площадь поверхностицилиндра: />

Площадь поверхностипараллелепипеда: />

Площадь поверхностиусеченного конуса:

Общая площадь боковойповерхности:

При заданной площадиповерхности S=10 м2 выразим H из последнего уравнения

Найдем объем сосуда

Объем цилиндра: />

Объем параллелепипеда: />

Объем усеченного конуса: />

Общий объем сосуда равен:

Рисунок 5.2

Подставив H в последнее уравнение, получимзависимость объема сосуда от одного параметра x. Зависимость и график функции представлен на рисунке 2.Область определения функции 1 четверть, т.к. объем и радиус – положительныевеличины. Для нахождения максимума функции воспользуемся методом золотогосечения.

Таким образом,максимальный объем при площади поверхности равной

10 м2<sup/>равен 1,19 м3

Заключение

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

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

2. проведен анализ методовмногопараметрический безусловной оптимизации;

3. были разобраны основы линейногопрограммирования;

4. был смоделирован и оптимизировантрёхмерный объект;

Список использованнойлитературы

1. ДегтяревЮ.И., «Исследование операций», Москва 1986;

2. ТурчакЛ.И., «Основы численных методов», Москва 1987;

3. МудровА.Е., «Численные методы», Томск 1991;