- •1. ВВЕДЕНИЕ
- •1.1. Постановка задач оптимизации
- •1.2. Математическая постановка задач оптимизации
- •1.2.1. Виды ограничений
- •1.2.2. Критерии оптимальности
- •1.2.3. Классификация задач
- •2. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ
- •2.1. Методы сужения интервала неопределенности
- •2.1.1. Общий поиск
- •2.1.2. Унимодальные функции
- •2.1.3. Метод деления интервала пополам
- •2.1.4. Метод золотого сечения
- •2.1.5. Установление первоначального интервала неопределенности
- •2.2. Ньютоновские методы
- •3. МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ
- •3.1. Рельеф функции
- •3.2. Метод покоординатного спуска (Метод Гаусса)
- •3.3. Метод оврагов
- •4. МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОДНЫХ
- •4.1. Градиентные методы
- •4.2. Метод Нюьтона
- •4.3. Метод Марквардта
- •5. УСЛОВНАЯ ОПТИМИЗАЦИЯ
- •5.1. Задачи с ограничениями в виде равенств
- •5.1.1. Множители Лагранжа
- •5.2. Задачи с ограничениями в виде неравенств
- •5.2. Методы штрафных функций
- •5.3. Метод факторов
- •6. Случайный поиск
- •6.1. Простой случайный поиск
- •6.2. Ненаправленный случайный поиск
- •6.3. Направленный случайный поиск
- •6.3.1. Алгоритм парной пробы
- •6.3.2. Алгоритм наилучшей пробы
- •6.3.3. Метод статистического градиента
- •6.3.4. Алгоритм наилучшей пробы с направляющим гиперквадратом
- •6.4. Алгоритмы глобального поиска
- •7. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- •7.1. Примеры задач линейного программирования
- •7.1.1. Задача об использовании сырья
- •7.1.2. Задача об использовании мощностей оборудования
- •7.1.3. Транспортная задача
- •7.1.4. Задача о питании
- •7.2. Основная задача линейного программирования
- •7.3. Основная задача линейного программирования с ограничениями-неравенствами
- •7.4. Геометрическое толкование задач линейного программирования
- •7. СИМПЛЕКС МЕТОД ИЛИ МЕТОД ПОСЛЕДОВАТЕЛЬНОГО УТОЧНЕНИЯ ОЦЕНОК
- •7.1. Алгоритм симплекс метода
- •7.2. Вырожденность в задачах линейного программирования
- •7.3. Двойственность задачи линейного программирования
- •Теоремы двойственности
- •7.4. Метод последовательного уточнения оценок
- •7.5. Методы решения транспортной задачи
- •7.5.1. Метод северо-западного угла
- •7.5.2. Метод минимального элемента
- •7.5.3. Метод потенциалов
- •СПИСОК ЛИТЕРАТУРЫ
- •СОДЕРЖАНИЕ
6. Случайный поиск
Регулярные, или детерминированные методы спуска, рассмотренные нами выше, не полноценны на неупорядоченном рельефе. Если экстремумов много, то спуск из одного начального приближения может сойтись только к одному из локальных минимумов, не обязательно абсолютному. Кроме того, с ростом размерности задач резко снижается эффективность регулярных методов поиска, которые требуют очень больших вычислительных ресурсов. Поэтому иногда для исследования таких сложных задач применяют случайный поиск.
6.1. Простой случайный поиск
Предполагают, что искомый минимум лежит в некотором n-мерном параллелепипеде. В этом параллелепипеде по равномерному закону выбирают случайным образом N пробных точек и вычисляют в них целевую функцию. Точку, в которой функция имеет минимальное значение, берут в качестве решения задачи. Однако даже при очень большом числе пробных точек вероятность того, что хотя бы одна точка попадает в небольшую окрестность локального минимума, ничтожно мала. Действительно, пусть N=106 и диаметр котловины около минимума составляет 10% от пределов изменения каждой координаты. Тогда объем этой котловины составляет 0.1n часть объема n-мерного параллелепипеда. Уже при числе переменных n>6 практически ни одна точка в котловину не попадет.
Поэтому берут небольшое число точек N = (5 ) n и каждую точку
рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска быстро укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью. Сравнивая окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов и сопоставить их величины. После этого можно отобрать нужные по смыслу задачи минимумы и провести в них дополнительные спуски для получения координат точек минимума с более высокой точностью.
При решении экстремальных задач на областях со сложной геометрией обычно эту область вписывают в n-мерный гиперпараллелепипед, в котором генерируют случайные точки по равномерному закону, оставляя только те, которые попадают в допустимую область (рис. 24).
44