АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. D – элементы
  2. I. МЕХАНИКА И ЭЛЕМЕНТЫ СПЕЦИАЛЬНОЙ ТЕОРИИ ОТНОСИТЕЛЬНОСТИ
  3. III. Несущие элементы покрытия.
  4. S-элементы I и II групп периодической системы Д.И.Менделеева.
  5. V. ЭЛЕМЕНТЫ ФИЗИКИ АТОМА
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. А. Понятие и элементы договора возмездного оказания услуг
  8. А. Понятие и элементы комиссии
  9. А. Понятие и элементы простого товарищества
  10. Актеры и элементы Use Case
  11. Архитектурная композиция и ее элементы
  12. Архитектурно-конструктивные элементы стен

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

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

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

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

1. Установления границ интервала;

2. Уменьшения интервала.

Пусть функция f(х) унимодальна на замкнутом интервале a £ x £ b, а ее минимум достигается в точке х* (рис. 7.1).

 

Рис. 7.1

 

Рассмотрим точки х(1) и х(2), для которых а < х(1) < х(2) < b.

1. Если f(x(1)) > f(x(2)), то x*Î (x1, b);

2. Если f(x1) < f(x2), то x*Î (a, x2);

3. Если f(x1) = f(x2), то x*Î (х1, x2).

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

 

x(k+1)= x(k)+2k·D , k=0,1,2...

 

где D - подбираемая величина шага.

Знак D подбирается путем сравнения значений f(x(0)), f(x(0)+½D½) и f(x(0) – ½D½).

Если f(x(0)–½D½) ³ f(x(0)) ³ f(x(0)+½D½)то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х(0) и величина D выбирается положительной.

Если f(x(0)–½D½) £ f(x(0)) £ f(x(0)+½D½), то D выбирается отрицательной.

Если f(x(0)–½D½) ³ f(x(0)) £ f(x(0)+½D½), то точка минимума лежит между x(0) – ½D½ и x(0)+½D½и поиск граничных точек завершен.



Алгоритм метода Свенна.

Шаг 1. Выбрать произвольную начальную точку х(0) и D – начальный положительный шаг (подбираемая величина).

Шаг 2. Вычислить f(x(0)), f(x(0)+ D)

Шаг 3. Сравнить f(x(0)), f(x(0)+ D):

а) если f(x(0)) > f(x(0)+ D) то, согласно предположению об унимодальности функции, точка минимума должна лежать правее, чем точка х(0). Положить а = х(0), х(1) = х(0) + D, f(x(1)) = f(x(0)+ D), k = 2 и перейти на шаг 5.

б) если f(x(0)) ≤ f(x(0)+ D), то вычислить f(x(0)- D).

Шаг 4. Сравнить f(x(0) - D), f(x(0)):

а) если f(x(0) - D) ≥ f(x(0)), то точка минимума лежит между точками x(0) - D и x(0) + D, которые и образуют границы начального отрезка локализации минимума. Положить а = х(0) - D, b = x(0) + D и завершить поиск.

б) если f(x(0) - D) < f(x(0)) то, согласно предположению об унимодальности функции, точка минимума должна лежать левее, чем точка х(0).

Положить b = x(0), x(1) = x(0) - D, f(x(1)) = f(x(0) - D), D = - D, k=2 и перейти на шаг 5.

Шаг 5. Вычислить х(k) = х(0) + 2(k-1)· D, f(x(k))..

Шаг 6. Сравнить f(x(k)), f(x(k-1)):

а) если f(x(k-1)) ≤ f(x(k)), то

при D > 0 положить b = x(k),

при D < 0 положить а = x(k)

и завершить поиск.

б) если f(x(k-1)) > f(x(k)), то

при D > 0 положить а = x(k-1)

при D < 0 положить b = x(k-1),

положить k = k+1 и перейти на шаг 5.

 

Выполнение работы в среде MS EXCEL

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

Определение знака D.

Для этого необходимо подсчитать значения функции в точках х(0), х(0) + |D|, х(0) ‑ |D|, затем сравнить эти значения. Для сравнения значений функции и выбора в зависимости от этого знака D необходимо использовать логическую функцию MS EXCEL ЕСЛИ(). Аргумент этой функции имеет следующую размерность: ЕСЛИ (логическое выражение; значение, если истина; значение, если ложь). Для записи условий сравнения значений функции в этих точках используется также логическая функция И(), имеющая размерность И (логическое выражение 1; логическое выражение 2). Данная функция возвращает значение ИСТИНА, если хотя бы одно логическое выражение ИСТИНА, или ЛОЖЬ, если оба логических выражения ЛОЖЬ. Любая функция EXCEL может быть использована в качестве аргумента другой функции. В этом случае она называется вложенной. В MS EXCEL может быть использовано до 9 уровней вложения функций.

‡агрузка...

Для задачи функция должна быть записана таким образом:

 

=ЕСЛИ(И(f(х(0)) <= f(х(0) -|D|);f(х(0)) >= f(х(0) +|D|));D;

 

(ЕСЛИ(И(f(х(0))>=f(х(0) -|D|);f(х(0))<=f(х(0) +|D|));‑D;

 

«Поиск границ завершен»)).

 

Данная функция возвращает значение D или ‑ D в зависимости от значений функции в точках х(0), х(0) +|D|, х(0) ‑ |D|, либо признает точки х(0) +|D|, х(0) ‑ |D| границами интервала. В последнем случае, кроме того, что границы интервала найдены, необходимо вывести их в виде а = х(0) ‑ |D|, b= х(0) +|D|. Для этого необходимо составить новую функцию, которая не возвращает ничего, если

 

f(х(0) ‑ |D|) >= f(х(0)) >= f(х(0) +|D|, f(х(0) -|D|) <= f(х(0)) <= f(х(0) +|D|,

 

и возвращает в одной ячейке значение «а=», в смежной с ней – значение х(0) - |D|, еще в одной ячейке – «b=» и в смежной с ней ‑ х(0) + |D|, если

f(х(0) -|D|) >= f(х(0)) <= f(х(0) +|D|.

 

Данная функция составляется аналогично предыдущей с использованием функций ЕСЛИ() и И().

Таким образом, если границы интервала не найдены при выполнении I этапа работы, определился, как минимум, знак D. Теперь можно приступить к определению границ интервала.

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

Вывести на экран результаты сравнения значений функции в пробных точках. Предлагается выводить эти результаты в двух графах. В левой графе выводится текст «x>» или «x<» в зависимости от значения функции в пробной точке и знака D, а в правой графе выводятся значение х в пробной точке. Если f(x(k+1)) < f(x(k)), то выводится «x>», если f(x(k+1)) > f(x(k)) – «x<» для D положительной. Для D отрицательной наоборот – «x<», если f(x(k+1)) < f(x(k)) и «x>», если f(x(k+1)) > f(x(k)). Для этого в левой графе составляется следующее выражение: =ЕСЛИ (f(x(k+1)) < f(x(k));ЕСЛИ(D > 0; «x>»; «x<»);ЕСЛИ(D > 0; «x<»; «x>»)). Для копирования выражения во все ячейки левой графы следует не забыть присвоить ячейке, содержащей D, абсолютный адрес.

Для вывода необходимых значений х в правой графе также составляются логические функции. Границами интервала поиска будут значения x, соответствующие последнему «x>» – а, и первому «x<» – b для D > 0, и наоборот, последнему «x<» – а и первому «x>» – b для D<0.


Пример 7. Определение интервала поиска минимума функции.

 

Исходные данные
f(x) х(0) D
(100-x)2

Определение знака D

х(0) -D f(х(0) - D) D=5
х(0) f(х(0))
х(0) +D f(х(0) + D)

 

x Индекс х f(x) Границы интервала
 
x>30
x>35
x>45
x>65
x<185
x<345

 

 

Выводы:для D = 5 границами интервала поиска минимума функции y = (100 - x)2 являются 65 < x < 185.


Контрольные вопросы

1. К каким одномерным функциям могут быть применены методы исключения интервала?

2. На какие этапы можно разбить процедуру поиска минимума функции методами исключения интервала?

3. Как влияет величина шага на результаты поиска границ интервала?

4. Каким образом осуществляется поиск граничных точек?

5. Опишите метод определения пробной точки по Свену.

6. Каким способом подбирается знак D величины шага?

7. От чего зависит эффективность поиска граничных точек? Как влияет

8. Что является исходными данными при решении задачи определения границ интервала поиска оптимума одномерной функции в среде MS EXCEL?

9. Какую логическую функцию используют в среде MS EXCEL для определения знака D при решении задачи определения границ интервала поиска оптимума одномерной функции?

10. Какая функция MS EXCEL может быть использована в качестве аргумента другой функции при решении задачи определения границ интервала поиска оптимума одномерной функции и как она называется?

11. Для чего используется индекс «х» в расчетном блоке при решении задачи определения границ интервала поиска оптимума одномерной функции в среде MS EXCEL?

12. Что является границами интервала поиска оптимума одномерной функции в среде MS EXCEL?

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |


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