Математические методы

                                                                      (7)

Понятно, что решение вспомогательной задачи зависит от значения параметра барьера. Покажем влияние  на результат минимизации .

Пример 1: f(x) = x → min; (x)=3 – x  0.

Барьерную функцию строим согласно (7). Тогда вспомогательная функция имеет вид Находим точку минимума : Отсюда

Следовательно, с уменьшением  точки минимума вспомогательной функции приближаются к минимуму исходной задачи. Геометрическая иллюстрация решения приведена на Рисунок 7.

Как хорошо видно на Рисунок 7, при оптимуме исходной задачи на границе допустимого множества последовательность точек минимума  с уменьшением  приближается к оптимальному решению изнутри допустимой области. По этой причине метод барьеров называют методом внутренних штрафов.

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

Алгоритм:

1. Выбрать начальную точку x0 так, чтобы i(x0)<0; задать точность , начальное значение 0 и число   (0, 1).

2. Минимизировать (x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.

4. Положить , за начальную точку принять и вернуться к шагу 2.

Значение 0 можно брать из интервала [2, 10]. Важное замечание касается пункта 2 алгоритма: в процессе поиска минимума вблизи границы из-за дискретности шагов возможен выход за допустимую область, где барьерная функция становится отрицательной, что повлечет расхождение поиска. Поэтому необходима явная проверка на допустимость точек на каждом шаге при минимизации .

Пример 2: f(x) = (x1–2)4+( x1–2x2)2 min; (x)=x2 0.

Решение находим, используя вспомогательную функцию

=(x1–2)4+(x1–2 x2)2 – 

За начальную точку возьмем допустимую точку (0;1), значения  и  принимаем равными 10. Результаты поиска алгоритмом барьерных функций представлены в табл. 2 и на Рисунок 8.

Таблица 2

Результаты поиска алгоритмом барьерных функций

Как и следовало ожидать, с уменьшением  значение B стремится к нулю.

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

(x) = f(x) + B(x) +

где барьерная функция B(x) применяется к неравенствам, а штрафная функция Н(х) – к ограничениям-равенствам. Последовательность задач минимизации  решается с уменьшающимися значениями параметра .

Глава 3. Другие методы условной оптимизации

Если все ограничения задачи заданы в виде неравенств, то для поиска условного минимума могут применяться модификации некоторых методов безусловной оптимизации. Так в методах случайного поиска модификация заключается в изменении условия успешности шага или направления. Шаг считается успешным, если он приводит в точку, в которой улучшается значение целевой функции и выполняются все ограничения. С этой целью добавляется проверка каждой точки на принадлежность допустимому множеству. В остальном алгоритмы остаются без изменений.

Аналогичное дополнение алгоритма Хука-Дживса делает его пригодным для поиска условного минимума. Генетические алгоритмы также могут использоваться для условной оптимизации. Для этого в них вводится детерминированный оператор жизнеспособности: если особь не удовлетворяет условиям «жизни», она погибает. Такой оператор должен применяться к каждой особи.

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

Несмотря на интенсивные исследования проблемы глобальной оптимизации сегодня нет эффективных методов, построенных на идее глобального поведения функции. Практическое применение находят в основном подходы, использующие локальный спуск из многих начальных точек с последующим выбором лучшего из найденных решений. Многократный спуск иногда называют мультистартом. Ему присущи такие недостатки как возможность неоднократного спуска в одну и ту же точку и отсутствие гарантии попадания в область притяжения глобального минимума. Эффективность мультистарта повышают за счет обеспечения выхода из «мелких» минимумов, исключения повторных спусков в найденные минимумы и т.п. С этой целью процессу спуска придают инерцию, которая позволяет проскакивать «неглубокие» минимумы (метод тяжелого шарика), изменяют целевую функцию для придания ей «туннельного эффекта», обеспечивающего переход из найденного в более глубокий минимум, используют редукцию задачи и другие идеи.

3.1 Пример решения

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию переменная x6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δk = CбXk — ck

Где:

­                      Cб = (с1, с2, ... , сm ) — вектор коэффициентов целевой функции при базисных переменных;

­                      Xk = (x1k, x2k, ... , xmk ) — вектор разложения соответствующего вектора Ак по базису опорного решения;

­                      Ск — коэффициент целевой функции при переменной хк.

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

              Таблица 3

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

В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле:

Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ1 = — 6*(- 2) = 12, и третьего вектора ΔZ3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5).

(таблица 4)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = - 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 5).

Таблица 5