Xreferat.com » Рефераты по экономико-математическому моделированию » Сравнительный анализ методов оптимизации

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

анализ методов оптимизации" width="93" height="49" align="BOTTOM" border="0" />, где у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).


Шаг 0


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.

Шаг 0


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 значение базисной переменной определяется:

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

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


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

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

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

по известному базисному решению строятся матрицы и находим Сравнительный анализ методов оптимизации;

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

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

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


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


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 отношения
0 y3 8 1 3 1 0 0 0,125

y4 12 6 1 0 1 0 0,5

y5 11,2 2 4 0 0 1 0,17857143

-f' 0 6 3 0 0 0
1 y3 6 0 2,833333 1 -0,16667 0 0,4722

y1 2 1 0,166667 0 0,166667 0 0,0833

y5 7,2 0 3,666667 0 -0,33333 1 0,5093

-f' -12 0 2 0 -1 0
2 y3 0,436363636 0 0 1 0,090909 -0,77273

y1 1,672727273 1 0 0 0,181818 -0,04545

y2 1,963636364 0 1 0 -0,09091 0,272727

-f' -15,92727273 0 0 0 -0,81818 -0,54545

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

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


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


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


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


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


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

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

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

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

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

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

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

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

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


2h1 = 2h2 = h3 = H

a = 2R = 4r = x


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

Площадь поверхности цилиндра: Сравнительный анализ методов оптимизации

Площадь поверхности параллелепипеда: Сравнительный анализ методов
    <div class=

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: