Метод прямого поиска

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

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

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

F(x, y) – заданная целевая функция – должна быть описана отдельно.

Входные данные: Х0, ХN, Y0, YN – граничные значения переменных x и y;

Eps – заданная точность вычислений;

Результаты: Xmin, Ymin - приближение к искомым значениям координат точки минимума;

Fmin – значение целевой функции в точке минимума.

 

Начало

Ввод X0, XN, Y0, YN, Eps

N = round ((XN – X0)/Eps)

M = round ((YN – Y0)/Eps)

Xmin = X0

Ymin = Y0

Fmin = F(X0, Y0)

i = 0.. N

j = 0.. M

x = X0 + i* Eps

y = Y0 + j* Eps

Fx = F(x, y)

-

Fmin > Fx

		+

Xmin = x

Ymin = y

Fmin = Fх

Вывод Xmin, Ymin, Fmin

end

 

Рисунок 3.10 - Блок-схема алгоритма метода оптимального пассивного поиска для функции двух переменных

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

 

 

1. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров: Учеб. пособие. - М.: Высшая школа, 1994. - 544 с.

2. Гловацкая А.П. Методы и алгоритмы вычислительной математики. Учеб. пособие. –М.: Радио и связь, 1999.- 408 с.

3. Демидович Б.П., Марон И.А., Основы вычислительной математики. - М.: Физматгиз, 1963.-660 с.

4. Демидович Б.П., Марон И.А., Шувалова Э.З., Численные методы анализа. - М.: Физматгиз, 1963.-400 с.: ил.

5. Дюк В. Обработка данных на ПК в примерах. – С.-Петербург: Питер – 240 с.: ил.

6. Калиткин Н.Н. Численные методы. - М.: Наука, 1978. - 512 с.

7. Мак-Кракен Д., Дорн У. Численные методы и программирование.-М.: Мир, 1977. - 583 с.: ил.

8. Плис А.И., Сливина Н.А. Лабораторный практикум по высшей математике: Учеб. пособие для втузов. - М.: Высшая школа, 1983. - 208 с.: ил.

9. Турчак Л.И. Основы численных методов.- М.:Наука, 1987.- 320 с.

10. Тюрин Ю.Н., Макаров А.А. Статистический анализ данных на компьютере / Под ред. В.Э. Фигурнова – М.: ИНФРА –М, 1998. – 528 с.: ил.

11. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. Пер. англ. -М.: Мир, 1980. -280с.

12. Шуп Т. Решение инженерных задач на ЭВМ: Практическое руководство. Пер. с англ. - М.: Мир, 1982. - 238 с.: ил.

 

 

 

УДК 681.3.06

 

МиМ – 2.3. - - 05

 

 

Автор: Орлова Ирина Викторовна

 

РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

 

Методическое пособие по курсам “Информатика”, “Решение инженерных задач на ЭВМ”, “Вычислительные методы в инженерных расчётах” для специальностей 120100, 200400, 210100 (дневная форма обучения)