Метод Хука-Дживса в принятии решений

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

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

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

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

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

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

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

2016



Содержание

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

Введение

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

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

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

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

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

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

Заключение

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



Введение

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

P₁ =b₁ +2(b₂ -b₁ ).

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

P_i =b_i +2(b_i+1 -b_i ).

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

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

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



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

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

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



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

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

Задача:

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

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

Решение:

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

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

Итерация №0.

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

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

x₁=1 + 1 = 2

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

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

x₂=21 + 1 = 22

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

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

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

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

x²=x¹+2(x¹-x⁰) = [1;23]

f(x²)=-4422.9

Далее проводится исследующий поиск вокруг точки x².

Итерация №1.

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

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

x₁=1 + 1 = 2

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

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

x₂=23 + 1 = 24

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

x^k-1 = [1;23]

x^k = [1;24]

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

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

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

x³=x¹+2(x¹-x⁰) = [1;25]

f(x³)=-5680.0

Далее проводится исследующий поиск вокруг точки x³.

Итерация №2.

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

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

x₁=1 + 1 = 2

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

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

x₂=25 + 1 = 26

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

x^k-1 = [1;25]

x^k = [1;26]

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

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

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

x⁴=x¹+2(x¹-x⁰) = [1;27]

f(x⁴)=-7155.1

Далее проводится исследующий поиск вокруг точки x⁴.

Итерация №3.

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

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

x₁=1 + 1 = 2

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

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

x₂=27 + 1 = 28

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

x^k-1 = [1;27]

x^k = [1;28]

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

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

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

x⁵=x¹+2(x¹-x⁰) = [1;29]

f(x⁵)=-8865.8

Далее проводится исследующий поиск вокруг точки x⁵.

Итерация №4.

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

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

x₁=1 + 1 = 2

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

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

x₂=29 + 1 = 30

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

x^k-1 = [1;29]

x^k = [1;30]

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

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

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

x⁶=x¹+2(x¹-x⁰) = [1;31]

f(x⁶)=-10830.

Далее проводится исследующий поиск вокруг точки x⁶.

Итерация №5.

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

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

x₁=1 + 1 = 2

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

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

x₂=31 + 1 = 32

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

x^k-1 = [1;31]

x^k = [1;32]

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

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

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

x⁷=x¹+2(x¹-x⁰) = [1;33]

f(x⁷)=-13064.

Далее проводится исследующий поиск вокруг точки x⁷.

Итерация №6.

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

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

x₁=1 + 1 = 2

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

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

x₂=33 + 1 = 34

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

x^k-1 = [1;33]

x^k = [1;34]

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

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

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

x⁸=x¹+2(x¹-x⁰) = [1;35]

f(x⁸)=-15586.

Далее проводится исследующий поиск вокруг точки x⁸.

Итерация №7.

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

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

x₁=1 + 1 = 2

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

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

x₂=35 + 1 = 36

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

x^k-1 = [1;35]

x^k = [1;36]

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

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

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

x⁹=x¹+2(x¹-x⁰) = [1;37]

f(x⁹)=-18413.

Далее проводится исследующий поиск вокруг точки x⁹.

Итерация №8.

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

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

x₁=1 + 1 = 2

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

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

x₂=37 + 1 = 38

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

x^k-1 = [1;37]

x^k = [1;38]

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

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

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

x¹⁰=x¹+2(x¹-x⁰) = [1;39]

f(x¹⁰)=-21563.

Далее проводится исследующий поиск вокруг точки x¹⁰.

Итерация №9.

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

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

x₁=1 + 1 = 2

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

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

x₂=39 + 1 = 40

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

x^k-1 = [1;39]

x^k = [1;40]

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

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

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

x¹¹=x¹+2(x¹-x⁰) = [1;41]

f(x¹¹)=-25054.

Далее проводится исследующий поиск вокруг точки x¹¹.

Ответ:

x(1;41)

f(x)=-25054.



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

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

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

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

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

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

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

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

С_T = 1,5410⁹

µ = 4,4

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

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

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

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

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

? ^* = (С_T/ C)^1/(µ-1)

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

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

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

C_R= C₁[1 - P(t_рез)] + С₂, где

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

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

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

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

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

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

T? (?) ? = l_рез

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

Решение:

T? = С_T / ? ^µ = 1,5410⁹ / 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