Метод хука дживса двумерная функция c. Метод хука-дживса в принятии решений. Выбор и описание тестовых задач

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

x = x+ λ (x – x)

четко устанавливает, что множество отраженных точек описывается. вектором, определяющим некоторое направление в пространстве управляемых переменных. Остальные элементы логической структуры поиска связаны лишь с выбором такой величины шага λ, которая позволяет достигнуть заметного «улучшения» значений целевой функции. Если же главная задача работы с образцом, составленным из пробных точек, состоит в определении направления поиска, то стратегию поиска по симплексу можно усовершенствовать путем непосредственного введения множества векторов, задающих направления поиска. Простейший подход заключается в том, что поиск ведется на основе рекурсивного перебора направлений из произвольно заданного множества. С другой стороны, можно построить стратегию поиска, в рамках которой одно или несколько направлений поиска уточняются на каждой итерации, что позволяет согласовать систему направлений поиска с глобальной топологией целевой функции. Для того чтобы гарантировать возможность проведения поиска по всей рассматриваемой области, в обоих случаях целесообразно наложить требование линейной независимости направлений поиска, которые должны образовывать базис в допустимой области определения f (x ). Например, легко убедиться в том, что нельзя вести поиск оптимума функции трех переменных с использованием двух направлений поиска. Отсюда следует, что все рассматриваемые методы прямого поиска используют по меньшей мере N независимых направлений поиска, где N - размерность вектора х.

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

Конструктивные попытки повышения эффективности этого метода были связаны с тем обстоятельством, что поиск, периодически проводимый в направлении d ( i ) = x ( i ) – x ( i -1) позволяет существенно ускорить сходимость. Это обстоятельство было положено в основу модифицированного метода, разработанного Хуком и Дживсом и являющегося одним из первых алгоритмов, в которых при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. По существу процедура Хука - Дживса представляет собой комбинацию «исследующего» поиска с циклическим изменением переменных и ускоряющегося поиска по образцу с использованием определенных эвристических правил. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направлений вдоль «оврагов». Полученная в результате исследующего поиска информация затем используется в процессе поиска по образцу при движении по «оврагам».

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

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

x
= x + (x – x
). (3.24)

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

x текущая базовая точка,

x
предыдущая базовая точка,

x
точка, построенная при движении по образцу,

x
следующая (новая) базовая точка.

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

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

Шаг 1. Определить:

начальную точку x

приращения ∆,i = l, 2, 3,..., N ,

коэффициент уменьшения шага α > 1,

параметр окончания поиска ε > 0.

Шаг 2. Провести исследующий поиск.

Шаг 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением целевой функции)?

Да: перейти к шагу 5.

Нет: продолжать.

Шаг 4. Проверка на окончание поиска. Выполняется ли неравенство || ∆ x || < ε?

Да: прекратить поиск; текущая точка аппроксимирует точку оптимума х*.

Нет: уменьшить приращения по формуле

∆= ∆/ α, i = 1, 2, 3,…, N ,

Перейти к шагу 2.

Шаг 5. Провести поиск по образцу:

x
= x + (x – x
).

Шаг 6. Провести исследующий поиск, используя x
в качестве базовой точки; пусть x ( k +1) - полученная в результате точка.

Шаг 7. Выполняется ли неравенство f (x ( k +1} )< f (x )?

Да: положить x
= x ( k ) , x ( k ) = x
.

Перейти к шагу 5.

Нет: перейти к шагу 4.

Пример 3.3. Поиск по методу Хука - Дживса

Найти точку минимума функции

f (x ) = 8 x + 4 xx+ 5 x,

используя начальную точку х (0) =[ – 4, – 4] T .

Решение. Для того чтобы применить метод прямого поиска Хука - Дживса, необходимо задать следующие величины:

∆x - векторная величина приращения = ,

α - коэффициент уменьшения шага = 2,

ε - параметр окончания поиска - 10 -4 .

Итерации начинаются с исследующего поиска вокруг точки х (0) , которой соответствует значение функции f (х (0)) = 272. Фиксируя x 2 , дадим приращение переменной x :

x= – 4

x = – 4+1→ f (– 3, – 4) = 200< f (х (0)) → Успех.

Следовательно, необходимо зафиксировать x = – 3 и дать приращение переменной х 2:

x = – 3,

x= – 4+1→ f (– 3, – 3) = 153< 200 → Успех.

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

x = [– 3, – 3] , f (x ) = 153

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

x =x+ ( x– х (0)) = [– 2, – 2],

f (x ) = 68

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

x= [– 1, – 1], f (x) = 17.

Поскольку f (x (2)) < f (x (1)), поиск по образцу следует считать успешным, и х (2) становится новой базовой точкой при следующем проведении поиска по образцу. Итерации продолжаются, пока уменьшение величины шага не укажет на окончание поиска в окрестности точки минимума х * = T . Последовательные шаги реализации метода показаны на рис. 3.7.

Из примера 3.3 следует, что метод Хука - Дживса характеризуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к объему памяти ЭВМ, который оказывается даже ниже, чем в случае использования метода поиска по симплексу. Благодаря этому алгоритм Хука - Дживса находит широкое применение во всех областях инженерной практики; особенно эффективны его варианты с использованием штрафных функций, которые рассматриваются в гл. 6. Однако необходимо отметить, что основанный на циклическом движении по координатам алгоритм в ряде случаев может заканчивать работу преждевременно, а при наличии значительных нелинейных эффектов вырождается в последовательность исследующих поисков без перехода к ускоряющемуся поиску по образцу.

Известен целый ряд подходов к усовершенствованию метода Хука - Дживса. В частности, Бендлер и Мак-Дональд модифицировали процедуру Хука - Дживса путем введения дополнительных правил увеличения и уменьшения приращений переменных, а также правила уменьшения шага по образцу, которое применяется в тех случаях, когда обычный шаг оказывается неудачным. Эксперименты, проведенные авторами данной книги, позволили доработать другую фазу реализации алгоритма, которую иногда называют использованием образца. Если движение по образцу приводит к успеху, имеются определенные основания для того, чтобы полностью использовать возможности поиска вдоль прямой, определяемой образцом, или по крайней мере увеличить длину шага по образцу. Такие действия часто позволяют существенно ускорить сходимость метода. Эмери и О"Хаган изменили фазу исследующего поиска путем введения системы ортогональных направлений поиска, ориентация которой случайным образом меняется на каждой итерации. Розенброк разработал метод, в котором, как и в методе Хука - Дживса, новое направление поиска определяется с учетом информации, полученной на предыдущих итерациях. Однако (в отличие от метода Хука-Дживса) подход, предложенный Розенброком, основан на непрерывном изменении множества векторов, используемых при исследующем поиске, с помощью процедуры ортогонализации. Другой метод, изложенный в работе Свенна и иногда называемый методом поиска Дэвиса, Свенна и Кемпи, опирается на стратегию поиска, подобную стратегии Розенброка. При его реализации поиск ведется не с помощью фиксированных шагов по каждому из выбранных направлений, а вдоль каждой прямой, заданной одним из направлений 1) . Каждый из перечисленных методов прямого поиска обладает рядом преимуществ перед остальными при решении задач определенного типа.

f(x) = 8x + 4xx+ 5x

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

Содержание:

Введение

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

Блок-схема данного метода

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

Текст программы

Распечатка результатов работы программы

Литература

Введение

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

(x 1 * ,x 2 * )

x 2

Рис. 1

C D

A B

x 1

а минимум лежит в точке (x 1 * ,x 2 * ). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и, таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси. Затем, производя поиск из точки В в направлении оси, получаем точку С, производя поиск параллельно оси, получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идую можно применить для функций n-переменных.

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

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

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b 1 и шаг длиной h 1 для каждой переменной x j , j = 1, 2, … , n . В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

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

1. Вычисляется значение функции f (b 1 ) в базисной точке b 1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b 1 +h 1 e 1 ) , где e 1 – единичный вектор в направлении оси x 1 . Если это приводит к уменьшению значения функции, то b 1 заменяется на b 1 +h 1 e 1 . В противном случае вычисляется значение функции f (b 1 -h 1 e 1 ) , и если ее значение уменьшилось, то b 1 заменяем на b 1 -h 1 e 1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1 остается неизменной и рассматриваются изменения в направлении оси х 2 , т. е. находится значение функции f (b 1 +h 2 e 2 ) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2 .

3. Если b 2 =b 1 , т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b 1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b 2 b 1 , то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

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

P 1 =b 1 +2(b 2 -b 1 ) .

В общем случае

P i =b i +2(b i+1 -b i ) .

2. Затем исследование следует продолжать вокруг точки Р 1 (Р i ) .

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b 2 (в общем случае b i+1 ), то получают новую базисную точку b 3 (b i+2 ) , после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b 2 (b i+1 ) , а продолжить исследования в точке b 2 (b i+1 ).

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

Модифицированный метод Хука-Дживса

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

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

В тексте прогаммы модифицированного метода прямого поиска Хука-Дживса сделана попытка реализовать такую процедуру. Рассматриваемая задача формулируется следующим образом:

минимизировать f (x 1 ,x 2 ) = 3x 1 2 +4x 1 x 2 +5x 2 2 ,

при ограничениях x 1 x 2 x 1 +x 2 .

Текст программы

program HuDjMody;

(*** Модифицированный метод Хука-Дживса ***)

(*** (при наличии ограничений) ***)

uses crt;

label 0,1,2,3,4,5,6,7;

var k,h,z,ps,bs,fb,fi:real;

i,j,n,fe:integer;

x,y,b,p:array of real;

(*** Процедура,вычисляющая функцию ***)

procedure calculate;

begin

z:=3*sqr(x)+(4*x*x)+(5*sqr(x));

if (x<0) or (x<0) or ((x+x)<4) then

z:=1.7e+38;

fe:=fe+1; (*** Счетчик ***)

end;

begin

clrscr;

gotoxy(20,2);

writeln(‘Модифицированный метод Хука-Дживса’);

gotoxy(23,3);

writeln(‘(при наличии ограничений)’);

writeln;

writeln(‘Введите число переменных:’);

readln(n);

writeln;

writeln(‘Введите начальную точку x1,x2,…,xN’);

for i:=1 to n do

readln(x[i]);

writeln;

writeln(‘Введите длину шага’);

readln(h);

writeln;

k:=h;

fe:=0;

for i:=1 to n do

begin

y[i]:=x[i];

p[i]:=x[i];

b[i]:=x[i];

end;

calculate;

fi:=z;

writeln(‘Начальное значение функции’, z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

ps:=0;

bs:=1;

(*** Исследование вокруг базисной точки ***)

j:=1;

fb:=fi;

0: x[j]:=y[j]+k;

calculate;

if z

x[j]:=y[j]-k;

calculate;

if z

x[j]:=y[j];

goto 2;

1: y[j]:=x[j];

2: calculate;

fi:=z;

writeln(‘Пробный шаг’,’ ‘, z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

if j=n then goto 3;

j:=j+1;

goto 0;

3: if fi

(*** После оператора 3,если функция не уменьшилась, ***)

(*** произвести поиск по образцу ***)

if (ps=1) and (bs=0) then

goto 4;

(*** Но если исследование производилось вокруг точки ***)

(*** шаблона PT,и уменьшение функции не было достигнуто,***)

(*** то изменить базисную точку в операторе 4: ***)

(*** в противном случае уменьшить длину шага в операторе***)

(*** 5: ***)

goto 5;

4: for i:=1 to n do

begin

p[i]:=b[i];

y[i]:=b[i];

x[i]:=b[i];

end;

calculate;

bs:=1;

ps:=0;

fi:=z;

fb:=z;

writeln(‘Замена базисной точки’,’ ‘,z:2:3);

for i:=1 to n do

writeln(x[i]:1:3);

(*** (следует за последним комментарием) ***)

(*** и провести исследование вокруг новой базисной точки ***)

j:=1;

goto 0;

5: k:=k/10;

writeln(‘Уменьшить длину шага’);

if k<1e-08 then goto 7;

(*** Если поиск незакончен,то произвести новое ***)

(*** исследование вокруг новой базисной точки ***)

j:=1;

goto 0;

(*** Поиск по образцу ***)

6: for i:=1 to n do

begin

p[i]:=2*y[i]-b[i];

b[i]:=y[i];

x[i]:=p[i];

y[i]:=x[i];

end;

calculate;

fb:=fi;

ps:=1;

bs:=0;

fi:=z;

writeln(‘Поиск по образцу’,’ ‘,z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

(*** После этого произвести исследование вокруг ***)

(*** последней точки образца ***)

j:=1;

goto 0;

7: writeln(‘Минимум найден’);

for i:=1 to n do

writeln(‘x(‘,i,’)=’,p[i]:2:3);

writeln;

writeln(‘Минимум функции равен’,’ ‘,fb:2:3);

writeln(‘Количество вычислений функции равно’,’ ‘,fe);

repeat until keypressed;

end.

Приведенная выше программа реализует описанную процедуру. Одной или двух точек бывает недостаточно для определения начальной точки. Первая точка всегда должна выбираться осмотрительно. ЭВМ работает только с ограниченной точностью, и ошибки могут накапливаться в процессе сложных вычислений, особенно если шаг имеет “неудобную” длину. (Обычно мы будем избегать “неудобной” длины, но программа должна быть работоспособна и в таких ситуациях.) Поэтому в строке, где выясняется вопрос об изменении базисной точки, мы избегаем уменьшения длины шага из-за накапливания ошибки введением длины шага, равной . Мы отслеживаем, где производится исследование – в базисной точке (В5 = 1, Р5 = 0) или в точке образца (В5 = 0, Р5 = 1). Как можно убедиться на практике, если не принимаются такие меры предосторожности даже программа с удовлетворительной логикой будет неработоспособна.

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

Процедура calculate вычисляет значение минимизируемой функции , в нашем случае : f (x 1 ,x 2 ) = 3x 1 2 +4x 1 x 2 +5x 2 2 ,

при ограничениях x 1 x 2 x 1 +x 2 .

Минимум, равный 44, достигается в точке (3;1) при ограничении x 1 +x 2 =4.

Для начальной точки (4;3) и при длине шага, равной единице, программой успешно решена задача минимизации.

Ниже приведена распечатка результата работы программы:

Модифицированный метод Хука-Дживса

(при наличииограничений)

Введите число переменных

Введите длину шага

Начальное значение функции 141.000

4.000

3.000

Пробный шаг 108.000

3.000

Пробный шаг 71.000

3.000

2.000

1.000

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Поиск по образцу 1.70000000000001566Е+0038

3.000

0.000

Пробный шаг 48.000

4.000

0.000

Пробный шаг 48.000

4.000

0.000

Замена базисной точки 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Минимум найден

х(1) = 3.000

х(2) = 1.000

Минимум функции равен 44.000

Количество вычислений равно 74

Для начальной точки (3;4) и длины шага, равной единице, программой также успешно решена задача минимизации.

Для начальной точки (5;6) и длины шага, равной единице, задача не решена, т.к. программа остановилась в точке (1;3) , т.е. на активном ограничении, и выдала неверный результат.

Распечатка результата работы программы приведена ниже:

Модифицированный метод Хука-Дживса

(при наличииограничений)

Введите число переменных

Введите начальную точку х1,х2,…,х N

Введите длину шага

Начальное значение функции 375.000

5.000

6.000

Пробный шаг 324.000

4.000

6.000

Пробный шаг 253.000

4.000

5.000

Поиск по образцу 155.000

3.000

4.000

Пробный шаг 124.000

2.000

4.000

Пробный шаг 81.000

2.000

3.000

Поиск по образцу 1.70000000000001566Е+0038

0.000

1.000

0.000

1.000

Пробный шаг 1.70000000000001566Е+0038

0.000

1.000

Замена базисной точки 81.000

2.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Поиск по образцу 1.70000000000001566Е+0038

0.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Замена базисной точки 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Минимум найден

х(1) = 1.000

х(2) = 3.000

Минимум функции равен 60.000

Количество вычислений равно 89

Аналогичные неутешительные результаты были получены для начальной точки (5;6) и длины шага, равной 0.5 .Неверное решение было найдено в точке (1.5;2.5) . Для начальной точки (4;3) и длины шага, равной 0.5 ,программа работала нормально, но было получено неверное решение в точке (2.5;1.5) .

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

Литература:

Б.Банди “Методы оптимизации”

Р.Хук, Т.А.Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с., 1961 .

Лекция 6

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

Этот метод можно рассматривать как модификацию метода Гаусса-

Зейделя.

Рассмотрим простейшую модификацию метода Хука и Дживса на примере функции F = f (x 1, x 2)=(x 1+ x 2) 2 +(x 2-1) 2

Метод вращающихся координат Розенброка

Идея Розенброка - устранить ограничения покоординатного поиска и метода Хука-Дживса на возможные изменения переменных, которые в этих методах могли изменяться только в направлениях, параллельных осям координат. В методе Розенброка шаги поиска могут производиться вдоль направлений координатных осей, которые могут вращаться в пространстве. (т.е.движение может быть и по диагонали).

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

Однако имеется дополнительный недостаток - процедура ортогонализации очень дорого стоит и в смысле количества операций, производимых с системой координат, и в смысле необходимой памяти, которой требуется уже порядка n 2 , а не n , как в методе Хука-Дживса. Это значит, что даже в случае относительно “дешевой” целевой функции вычислительные затраты на ортогонализацию оказываются значительными в сравнении с общими затратами. Кроме того, размерность решаемых задач ограничивается требуемым объемом памяти.

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

Поиск экстремума методом Нелдера-Мида

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

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

Методы первого порядка

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

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

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

где e 1 , e 2 - единичные векторы (орты) в направлении координатных осей. Следовательно, направление, противоположное градиентному, укажет путь, ведущий вниз вдоль наиболее крутой линии. Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными .

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

Формально поиск новой точки приближения к минимальной точке можно представить как

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

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

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

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

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

Проиллюстрирую метод наискорейшего спуска на рисунке для случая функции двух переменных z = f(x,y) и отметим некоторые его геометрические особенности.

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

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

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

Исследование оврагов

Все рассмотренные методы, как прямые, так и методы первого порядка страдают существенным недостатком они слабо применимы при наличии оврага на поверхности.

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

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

Проблема многоэкстремальности

Достаточно часто на практике имеются функции имеющие несколько минимумов.

На рисунке приведены линии уровня функции с двумя локальными минимумами в точках O 1 и O 2 . Такие функции принято называть многоэкстремальными. Сравнивая между собой значения функции в точках O 1 и O 2 f 1 =3 , f 2 =1 , находим, что наименьшее значение функция достигает в точке O 2 .

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

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

Решение задач условной оптимизации методом Лагранжа

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

Решение задач условной оптимизации методом Лагранжа.

Пусть задана задача математического программирования: максимизировать функцию

Z = f (х 1 , х 2 , ..., х n) при ограничениях

g i (х 1 , х 2 , ..., х n ) = 0, i= 1, 2. ..., m

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

С этой целью составим функцию

(2.7)

Где множитель Лагранжа.

Определим частные производные

И приравняем их нулю. В результате получим систему уравнений

Функция (2.7) называется функцией Лагранжа, а числа - множителями Лагранжа . Решая систему находим точки x 1 (0) , x 2 (0) , ..., x n (0) , λ 1 (0) , λ 2 (0) , ..., λ m (0) которые и определяют точки экстремума (в общем случае таких точек может быть несколько). Однако для того чтобы определить какой экстремум (мах или мин) нужно дополнительное исследование связанное с анализом значения функции в найденной точке.

Пример 1. Найти точку условного экстремума функции Z=x 1 x 2 +x 2 x 3 при ограничениях

Решение. Составим функцию Лагранжа

F (х 1 , х 2 , х 3 , λ 1 , λ 2 )= х 1 х 2 + х 2 х 3 + λ 1 (х 1 + х 2 -2)+ λ 2 (х 2 + х 3 -2)

и продифференцируем ее по переменным х 1 , х 2 , х 3 , λ 1 и λ 2 . Приравнивая полученные выражения нулю, получим следующую систему уравнений:

Из первого и третьего уравнения следует, что λ 1 = λ 2 = - х 2 ; тогда

Решая данную систему, получим: х 1 = х 2 = х 3 = 1, Z =2.

Для определения характера экстремума исследуем окрестность точки Z =2. С этой целью дадим приращения h 1, h 2, h 3 для точек х1, х2, х3.

Т.е новые точки имеют координаты 1+ h 1, 1+ h 2, 1+ h 3

Подставим эти значения в ограничения.

1+ h 1+1+ h 2=2

1+ h 2+1+ h 3=2

Т.е.

h 1+ h 2=0

h 2+ h 3=0

Или h 1=- h 2 и h 2=- h 3

Подставим значения новых точек в функцию

Ф=(1+ h 1)*(1+ h 2)+(1+ h 2)*(1+ h 3)

С учетом найденных значений h

Ф=2-2 h 1 2

Т.е окрестность точки экстремума меньше значения функции в этой точке, что свидетельствует, что это максимум.

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное

образовательное учреждение высшего образования

Курсовая работа

по дисциплине

«Теория и методы принятия решений»

оптимизация решение хук дживс

Введение

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

1.3 Блок-схема данного метода

Заключение

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

Введение

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

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

Целью данной работы, является освещения концепций метода Хука-Дживса.

Основными задачами, подлежащими рассмотрению в связи с поставленной целью, являются:

· объяснить в чем состоит суть метода Хука-Дживса;

· показать его отличие от других методов данного типа;

· рассмотреть алгоритм работы метода;

· пояснить этапы выполнения метода;

· уточнить в чем состоит модификация данного метода;

· наглядно продемонстрировать работу метода с помощью блок-схем.

Актуальность данной работы заключается в конкретизации и резюмированию знаний об этом методе.

1. Освоение алгоритма решения типовой задачи оптимизации на учебном примере

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b 1 и шаг длиной h 1 для каждой переменной x j , j = 1, 2,…, n. В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

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

1. Вычисляется значение функции f (b 1) в базисной точке b 1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b 1 +h 1 e 1), где e 1 - единичный вектор в направлении оси x 1 . Если это приводит к уменьшению значения функции, то b 1 заменяется на b 1 +h 1 e 1 . В противном случае вычисляется значение функции f (b 1 -h 1 e 1), и если ее значение уменьшилось, то b 1 заменяем на b 1 -h 1 e 1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1 остается неизменной и рассматриваются изменения в направлении оси х 2 , т. е. находится значение функции f (b 1 +h 2 e 2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2 .

4. Если b 2 b 1 , то производится поиск по образцу.

1. Разумно двигаться из базисной точки b 2 в направлении b 2 -b 1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца:

P 1 =b 1 +2(b 2 -b 1).

В общем случае:

P i =b i +2(b i+1 -b i).

2. Затем исследование следует продолжать вокруг точки Р 1 (Р i).

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b 2 (в общем случае b i+1), то получают новую базисную точку b 3 (b i+2), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b 2 (b i+1), а продолжить исследования в точке b 2 (b i+1).

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

1.2 Модифицированный метод Хука-Дживса

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

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

1.3 Блок-схема данного метода

1.4 Решение конкретной задачи симплексным методом

Задача:

Минимизируйте функцию

при ограничениях:

Решение:

Шаг 1. Задаем начальную точку x 0 =(1,21); приращения (шаги): ?x=(1,1); коэффициент уменьшения шага: б = 2; е=0.1

Вычислим значение функции в т. x 0 =(1,21) T: f(x 0) = -3366.5

Итерация №0 .

Шаг №2. Исследующий поиск.

Фиксируя переменную x 2 = 21, дадим приращение x 1:

f(2;21) = -1980.3 > -3366.5

x 2 =21 + 1 = 22

f(1;22) = -3870.7 < -3366.5

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 1 =(1;22) T . Переходим к поиску по образцу.

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

Итерация №1 .

Фиксируя переменную x 2 = 23, дадим приращение x 1:

f(2;23) = -2601.7 > -4422.9

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =23 + 1 = 24

f(1;24) = -5025.3 < -4422.9

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 2 =(1;24) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №2 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 25, дадим приращение x 1:

f(2;25) = -3341.1 > -5680

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =25 + 1 = 26

f(1;26) = -6389.2 < -5680

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 3 =(1;26) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №3 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 27, дадим приращение x 1:

f(2;27) = -4208.9 > -7155.1

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =27 + 1 = 28

f(1;28) = -7979.9 < -7155.1

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 4 =(1;28) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №4 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 29, дадим приращение x 1:

f(2;29) = -5215.2 > -8865.8

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =29 + 1 = 30

f(1;30) = -9815 < -8865.8

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 5 =(1;30) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №5 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 31, дадим приращение x 1:

f(2;31) = -6370.3 > -10830

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =31 + 1 = 32

f(1;32) = -11912 < -10830

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 6 =(1;32) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №6 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 33, дадим приращение x 1:

f(2;33) = -7684.5 > -13064

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =33 + 1 = 34

f(1;34) = -14288 < -13064

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 7 =(1;34) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №7 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 35, дадим приращение x 1:

f(2;35) = -9168.1 > -15586

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =35 + 1 = 36

f(1;36) = -16960 < -15586

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 8 =(1;36) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №8 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 37, дадим приращение x 1:

f(2;37) = -10831 > -18413

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =37 + 1 = 38

f(1;38) = -19947 < -18413

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 9 =(1;38) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №9 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 39, дадим приращение x 1:

f(2;39) = -12684 > -21563

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =39 + 1 = 40

f(1;40) = -23265 < -21563

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 10 =(1;40) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Ответ:

2. Анализ метода решения реальной задачи оптимизации на основе научной публикации

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

Путь резания / l рез. / составляет 628м. Расчёт средней стойкости инструмента (T?) проводится по тейлоровской зависимости:

T? = С T / ? µ , где

С T - константа, не зависящая от скорости резания

µ - эмпирическая константа

Скорость резания

Даны параметры:

Коэффициент вариации стойкости инструмента? t изменяется от 0,1 до 0,5.

В задаче рассматриваются 2 критерия оптимизации:

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

2) Минимум экономического риска.

Используется численный метод - метод касательных Ньютона:

? * = (С T / C) 1/(µ-1)

Математическое ожидание равно 1.

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

Для второго критерия оптимальности применяют выражение:

C R = C 1 + С 2 , где

C R - среднее значение экономического ущерба из-за возможного отказа инструмента при обработке детали;

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

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

Вероятность безотказной работы инструмента за время резания t.

Для второго критерия оптимальности решение зависит от коэффициентов С 1 и С 2 . С увеличением разброса стойкости усиливается влияние С 1 /С 2 на оптимизацию. Чем больше величина С 1 /С 2 , т.е. чем больше зависимость потерь от брака, тем меньшую скорость обработки следует назначать.

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

T? (?) ? = l рез

В данной задаче? = 75,1 м/мин

Решение:

T? = С T / ? µ = 1,5410 9 / 75,1 4,4 = 2,73783976 Ч 10 ? 7

l рез =T? (?) ? = 2,73783976 Ч 10 ? 7 * (75,1) * 75,1 = 0,00154414436

Оптимальная скорость резания равна 0,00154414436.

Заключение

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

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

В данной работы были освещены концепции метода Хука-Дживса. Основываясь на данной работе и на материалах использованных для ее написания, можно сделать следующие выводы:

Метод Хука-Дживса применим для широкого числа приложений, не смотря на то, что он был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным;

Метод Хука-Дживса использует информацию на основании уже полученных значений функции, это экономит время работы;

Метод Хука-Дживса нетрудно модифицировать для учета ограничений.

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

1.Пушкин Н.М., ИноземцевА.Н., Савушкин В.Н. Оптимизация режимов обработки деталей спортивного и охотничьего оружия путём уменьшения риска потери качества/ Н.М. Пушкин, А.Н. Иноземцев, В.Н. Савушкин / /Автоматизация и современные технологии. 2002. №6. с. 10-13.

2.Бразовская Н.В., Бразовская О.В. Методы оптимизации: Учебное пособие / Алт. Госуд. Технич. Ун-т им. И.И. Ползунова. Барнаул: изд. АлтГТУ, 2006. 127 с.

3.Кулаков С.М., Бондарь Н.Ф. Методические указания к выполнению курсовой работы и практическим работам / С.М. Кулаков, Н.Ф. Бондарь. Новокузнецк: Изд. центр СибГИУ, 2016. 62 с.

4. Б.Банди. Методы оптимизации. М., 1998 г.

5. Р.Хук, Т.А. Дживс. Прямой поиск решения для числовых и статических проблем. 1961 г.

Размещено на Allbest.ru

Подобные документы

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

презентация , добавлен 12.03.2012

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

контрольная работа , добавлен 17.12.2013

Характеристика количественной школы, направления, основные тенденции развития. Практика принятия решений в области ценообразования в ООО "Евроокна". Анализ количественных методов для решения задачи оптимизации процесса принятия управленческих решений.

курсовая работа , добавлен 18.05.2009

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

реферат , добавлен 08.12.2014

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

курсовая работа , добавлен 17.06.2010

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

презентация , добавлен 17.02.2015

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

контрольная работа , добавлен 25.03.2011

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

курсовая работа , добавлен 31.10.2008

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

курсовая работа , добавлен 28.11.2015

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

На начальном этапе задаётся стартовая точка (обозначим её 1) и шаги h i по координатам. Затем замораживаем значения всех координат кроме 1-й, вычисляем значения функции в точках x 0 +h 0 и x 0 -h 0 (где x 0 - первая координата точки, а h 0 - соответственно значение шага по этой координате) и переходим в точку с наименьшим значением функции. В этой точке замораживаем значения всех координат кроме 2-й, вычисляем значения функции в точках x 1 +h 1 и x 1 -h 1 , переходим в точку с наименьшим значением функции и т. д. для всех координат. В случае, если для какой-нибудь координаты значение в исходной точке меньше, чем значения для обоих направлений шага, то шаг по этой координате уменьшается. Когда шаги по всем координатам h i станут меньше соответствующих значений e i , алгоритм завершается, и точка 1 признаётся точкой минимума.

Иллюстрация первого этапа для двух координат:

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

На этапе поиска по образцу откладывается точка 3 в направлении от 1 к 2 на том же расстоянии. Её координаты получаются по формуле Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \overline{x}_3=\overline{x}_1+\lambda(\overline{x}_2-\overline{x}_1) , где x i - точка с номером i, λ - параметр алгоритма, обычно выбирающийся равным 2. Затем в новой точке 3 проводится исследующий поиск, как на 1 фазе алгоритма, за исключением того, что шаг на этой фазе не уменьшается. Если на этой фазе в результате исследующего поиска удалось получить точку 4, отличную от точки 3, то точку 2 переобозначим на 1, а 4 на 2 и повторим поиск по образцу. В случае если не удаётся найти точку 4, отличную от точки 3, то точку 2 переобозначим на точку 1 и повторим 1-ю фазу алгоритма - исследующий поиск.

Иллюстрация второго этапа для двух координат:

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

Напишите отзыв о статье "Метод Хука - Дживса"

Литература

Р. Хук, Т. А. Дживс «Прямой поиск решения для числовых и статических проблем», 212-219 с., 1961.
C. T. Kelley. Iterative methods for optimization, 180 p

Ссылки

http://www.theweman.info/topics/t4r5part1.html
в Интуит.ру .
А.В. Аттетков, С.В. Галкин, В.С. Зарубин. Метод Хука - Дживса // . - М .: Изд-во МГТУ им. Н.Э. Баумана, 2003. - С. 285. - 440 с. - (Математика в техническом университете; Вып. XIV).

Просмотр этого шаблона

Одномерные

Прямые методы

Первого порядка

Второго порядка

Стохастические

Методы линейного программирования

Методы нелинейного программирования

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

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

Отрывок, характеризующий Метод Хука - Дживса

– А как же «этажи»?.. Я ведь никак не могла сама туда попасть?.. Это ведь Стеллина бабушка мне их показала! – всё ещё упорно не сдавалась я.
– Ну, так ведь для того и показала, чтобы сама попробовала, – констатировала «неоспоримый» факт бабушка.
– А разве я могу сама туда пойти?!.. – ошарашено спросила я.
– Ну, конечно же! Это самое простое из того, что ты можешь делать. Ты просто не веришь в себя, потому и не пробуешь...
– Это я не пробую?!.. – аж задохнулась от такой жуткой несправедливости я... – Я только и делаю, что пробую! Только может не то...
Вдруг я вспомнила, как Стелла много, много раз повторяла, что я могу намного больше... Но могу – что?!.. Я понятия не имела, о чём они все говорили, но теперь уже чувствовала, что начинаю понемножку успокаиваться и думать, что в любых трудных обстоятельствах мне всегда помогало. Жизнь вдруг показалась совсем не такой уж несправедливой, и я понемногу стала оживать...
Окрылённая положительными новостями, все последующие дни я, конечно же, «пробовала»... Совершенно себя не жалея, и вдребезги истязая своё, и так уже измождённое, физическое тело, я десятки раз шла на «этажи», пока ещё не показываясь Стелле, так как желала сделать ей приятный сюрприз, но при этом не ударить лицом в грязь, сделав какую-нибудь глупую ошибку.
Но вот, наконец-то, решила – хватит прятаться и решила навестить свою маленькую подружку.
– Ой, это ты?!.. – сразу же зазвучал счастливыми колокольчиками знакомый голосок. – Неужели это правда ты?! А как же ты сюда пришла?.. Ты что – сама пришла?
Вопросы, как всегда, сыпались из неё градом, весёлая мордашка сияла, и для меня было искренним удовольствием видеть эту её светлую, бьющую фонтаном, радость.
– Ну что, пойдём гулять? – улыбаясь, спросила я.
А Стелла всё никак не могла успокоиться от счастья, что я сумела придти сама, и что теперь мы уже сможем встречаться, когда пожелаем и даже без посторонней помощи!
– Вот видишь, я же тебе говорила, что ты можешь больше!.. – счастливо щебетала малышка. – Ну, теперь всё хорошо, теперь уже нам никто не нужен! Ой, а это как раз-то очень хорошо, что ты пришла, я тебе хотела что-то показать и очень тебя ждала. Но для этого нам придётся прогуляться туда, где не очень приятно...
– Ты имеешь в виду «нижний этаж»? – поняв, о чём она говорит, тут же спросила я.
Стелла кивнула.
– А что ты там потеряла?
– О, я не потеряла, я нашла!.. – победоносно воскликнула малышка. – Помнишь, я говорила тебе, что там бывают и хорошие сущности, а ты мне тогда не поверила?
Откровенно говоря, я не очень-то верила и сейчас, но, не желая обижать свою счастливую подружку, согласно кивнула.
– Ну вот, теперь ты поверишь!.. – довольно сказала Стелла. – Пошли?
На этот раз, видимо уже приобретя кое-какой опыт, мы легко «проскользнули» вниз по «этажам», и я снова увидела, очень похожую на виденные раньше, гнетущую картину...