Лекция: МЕТОДЫ ПОИСКА

Применим методов безуслов оптимизации. Задача обслуж на 1 приборе.

Основные понятия. Классификация

Одну и ту же задачу оптимизации можно решить различными методами. Их может быть несколько десятков, поэтому их разбивают на классы. Методы делятся на прямые и непрямые.

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

Пусть дана задача:

(1)

и пусть задано начальное приближение .

В прямых методах строится последовательность:

(2)

в которой – направление итерации, – шаг в этом направлении. Шаг и направление выбирают, чтобы выполнялось неравенство:

.

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

1 2 3

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

Методы делятся на детерминированные и стохастические. Если и вычисляются по определённым формулам, то метод называется детерминированным, а если для их построения используются механизмы теории вероятности, то метод называется стохастическим.

Метод называется методом -го порядка, если для вычисления направления и шага итерации используются производные от параметров задачи до -ой включительно. Если =0, то такой метод называется методом поиска или перебора.

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

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

Методы также различают по использованию ресурсов ЭВМ, объёму памяти, быстроте нахождения решения и так далее.

МЕТОДЫ ПОИСКА

Обычно методами поиска решаются задачи:

(1)

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

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

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