Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

Оптимизационных задач

Поисковые (численные) методы решения однофакторных

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

Для получения решения:

а) задаем способ вычисления целевой функции: y = f (x) → min.

б) все поисковые методы – приближённые, поэтому перед началом решения задаётся интересующая нас точность решения .

в) выбирается интервал допустимых значений: a≤x≤b.

 

1. Метод перебора (сплошного поиска).

 

Разбиваем ось аргументов на конечное число шагов решения, которое определяется интересующей нас точностью: . При точности 1% от интервала изменения фактора это будет соответствовать разбиению интервала на 100 шагов, при точности 5% потребуется разбить интервал на 20 шагов и т.д.

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

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

2. Метод дихотомии (половинного деления).

Исходно требуется то же, что и в предыдущем методе. Разбиваем интервал значений аргумента пополам:

 

. Строим две дополнительные узловые точки с координатами:

 

и вычисляем значения целевой функции в этих точках.

 

y1 = f (x1)

y2 = f (x2).

 

Представим, что функция имеет один минимум на отрезке от a до b. Ординаты у1 и у2 вычислены в точках, лежащих достаточно близко друг к другу, на расстоянии удвоенной точности решения. Если у21, поиск минимума на левой половине интервала теряет смысл, и ее можно отбросить. На этом первая итерация решения заканчивается, и после сокращения интервала вдвое задача вновь возвращается к исходной.

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

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

Поскольку сокращение интервала на каждой итерации происходит вдвое, то совершив 7 итераций, например, мы уменьшим первоначальный интервал в 128 раз, достигнув точности решения менее 1% от первоначального интервала.

Поскольку на каждой итерации целевая функция вычисляется дважды, общее количество ее вычислений будет равно 14. При этом нет необходимости запоминать результаты вычислений, в отличие от метода сплошного поиска. К тому же, решая задачу по методу сплошного поиска с точностью 1%, мы были бы вынуждены выполнить 100 вычислений целевой функции, и при этом все результаты вычислений надо было бы сохранить. При повышении точности решения различия методов становятся еще больше: при точности 0.5% метод дихотомии требует 16 вычислений функции, а метод сплошного поиска – 200 вычислений, при точности 0.1% - 20 и 1000 вычислений соответственно!

 

 

1

 

7 шагов

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

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

 

Дата публикации:2014-01-23

Просмотров:405

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







 

2012-2018 lekcion.ru. За поставленную ссылку спасибо.