- •1. Методы одномерной оптимизации
- •1.2.2. Метод золотого сечения
- •2. Методы безусловной оптимизации
- •2.1.1. Поиск по правильному симплексу
- •2.2.1. Метод циклического покоординатного спуска
- •2.2.2. Метод Зейделя
- •2.2.3. Метод Хука - Дживса
- •2.2.4. Метод Пауэлла
- •2.2.5. Типовые примеры
- •2.3.1. Метод градиентного спуска
- •2.3.2. Метод наискорейшего спуска
- •2.3.3. Типовой пример
- •3.1.1. Метод штрафных функций
- •3.1.2. Метод барьерных функций
- •3.1.3. Комбинированный метод штрафных функций
- •3.1.4. Типовой пример
- •3.2.2. Описание метода возможных направлений
- •3.2.3. Построение начального приближения
- •3.2.4. Выбор наилучшего подходящего направления
- •3.2.5. Определение длины шага
- •3.2.6. Типовой пример
- •3.3.3. Алгоритм статистичекого градиента
- •3.3.2. Алгоритм наилучшей пробы
- •4.2.2. Алгоритм метода
3.2.2. Описание метода возможных направлений
Идея метода возможных направлений (МВН) заключается в том что в каждой очередной точке выбирается подходящее направление и производится исчерпывающий спуск в этом направлении.
Направление 5в точке XeR называется возможным, если достаточно малое перемещение из точки X в этом направлении не выводит точку за пределы дополнительной области R, т.е. если За > 0: X + aS е Л,то S - возможное направление в точке Хе R.
Возможное направление S в точке XeR называется подходящим, если перемещение из точки Хъ этом направлении ведет к
уменьшению значения функции /0 (X), т.е. если у о [X),Sj<0.
Если в некоторой точке X"eR не существует подходящих направлений, то точка X' является точкой минимума функции
/0(Л")в области R.
Метод возможных направлений осуществляется следующим образом:
1. Точка начального приближения выбирается в допустимой
области, т.е. Х° е R.
2. Последовательность точек Х\ X2,..., Хк, принадлежащих R, строится так, чтобы выполнялись неравенства/о tO </.(*"),' = 1,2,...,*.
При этом, строя точку А-*41 £ Л так, чтобы выполнялись неравенства /0 (Xм)</,(*'), обнаруживаем, что либо/0(А0 не ограничена, либо такой точки не существует, т.е. Хк - оптимальнаяточка. В обоих случаях процесс решения задачи прекращается.Задача решена. F
'а построения точки А'*1 6Д состоит из двух
а) " Т°ЧКе * «"Р^ляется подходящее направление 5*;
б) определяется длина шага ак > О: х" + а 5* е R
3.2.3. Построение начального приближения
Шаг 1. Строим точку Z°: 0 < Z° < С
Шаг_1 Располагая точкой Х°, вычисляем значение функ-
ций
ШагЗ. Если значение функции у,\Х ) > 0 , то точка Х° удовлетворяет г-му линейному ограничению задачи (3.10), т.е. выпол-
/ ~о\
няется неравенство Ы,Х ) < Ь,. Если же значение j/. (х"\ < о, то в
точке X не выполняется условие /4,АМ<^ и, следовательно,
—о точка X не удовлетворяет линейным ограничениям задачи (3.10).
Шаг 4. Введем в рассмотрение неотрицательные числа р., положив р.=0 для тех индексов;, для которых у АХ I > 0 , и поло-
/~о\
жив р. > 0 для тех индексов, для которых у,А X I < 0 .
Шаг 5. Введем дополнительную переменную £, > 0, увеличивая тем самым размерность вектора неизвестных на единицу, и в
(п+1)-мерном пространстве (а,,х2,...,хя,^поставим следующую задачу:
(3.14)
Получили таким образом в (п+1)-мерном пространстве задачу минимизации линейной функции на множестве, задаваемом линейными ограничениями, т.е. задачу линейного программирования, которая решается за конечное число шагов симплекс-методом. При этом в качестве начального опорного плана можно выбрать точку.-
49
р,
> О
В качестве значений р. > 0 можно взять р, =
Решая вспомогательную задачу (3.14) симплекс-методом, за конечное число шагов получим оптимальный план, в котором 4 = 0. Тогда первые п компонентов этого опорного плана определят точку X , которая будет удовлетворять всем линейным ограничениям исходной задачи (3.10), т.е.
Ь„ ieI2,0<X° <С.
I—о\ /—о\
Шаг 6. Вычислим уАХ \ = b,-fAX |,ге/,. Зададим неотрицательные числа р., полагая р.= 0 для тех индексов /, для ко-
торых у АХ 1>0, и р,. > 0 для тех индексов, для которых
ния ЗВП (3.15) на каком-то шаге получим л = 0, т.е. вектор (х,0,^,...,^ 0), то соответствующий вектор(х,0,*",...,^) опреде. лит точку А-0, удовлетворяющую всем ограничениям задачи (3 10) которая будет являться начальной точкой исходной задачи
Вместо того, чтобы последовательно удовлетворять сначала линейным, а затем нелинейным ограничениям, можно, избегая шага 5 и шага 6 и имея точку Х°: 0 < х° <CJ e / , сразу сформулировать и решить только одну задачу:
где р > 0 для тех индексов г, для которых у\х < 0.
ли-
Задача (3.16) является ЗВП, для которой за нулевое приб можно взять точк
жение можно взять точку
ftFU Ц,Г)-ь,
р,.>0
X ,%„ =тах
Р,
Шаг 7. Введем дополнительную переменную х\ > 0 и сформулируем еще одну вспомогательную задачу, следующим образом:
mm{r\\fi(X)-plT\<bnieI];(Ai,X)<bnieI2;O<X<C;r\>O}. (3.15)
Это есть ЗВП, для которой известна начальная точка с координатами
У\Х
Р,
|р,>0 .
х, = х°1,х2=х°2,...,хп =
Если в качестве значений р. > 0 выбрать величину р, = у,
X , 1 . Очевидно, если в ходе реше-50
Однако решение задачи (3.16) является более сложным, чем решение задач, которые рассматривались в шаге 5 и шаге 6.