Модели нелинейного программирования

       

     Условие (1.12) означает равенство нулю скалярного произведения градиентов функции f точках x^(q+1) и x^(q). Геометрически оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на рис. 1.2. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке x^(q+1) вектор f(x^(q+1)), будучи градиентом, перпендикулярен линии уровня, проходящей через данную точку. Стало быть, вектор f(x^(q)) является касательным к этой линии. Итак, движение в направлении градиента f(x^(q)) следует продолжать до тех пор, пока он пересекает линии уровня оптимизируемой функции.

     После того как точка x^(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора Δf(x^(q)) должны быть близки к нулю.

     Метод дробления шага

     Для нахождения шага λ в методе наискорейшего спуска требуется решить уравнение (1.12), которое может оказаться достаточно сложным. Поэтому часто ограничиваются «подбором» такого значения λ, что φ(λ) > φ(0). Для этого задаются некоторым начальным значением λ₁, (например, λ₁=l) и проверяют условие φ(λ₁) >φ(0). Если оно не выполняется, то полагают 

     λ₂ = 1/2 λ₁ 

     и т. д. до тех пор, пока не удается найти  подходящий шаг, с которым переходят к следующей точке x^(q+1). Критерий завершения алгоритма, очевидно, будет таким же, как и в методе наискорейшего спуска.

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

       

     в случае градиентных методов, может  быть осуществлен за счет подбора  соответствующих начальных приближений х⁽⁰⁾.

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

     F Функция f(x) = f (x₁, x₂, …, x_n) называется выпуклой в области D, если для любых двух точек х⁽¹⁾, х⁽²⁾ Î D и любого λ Î [0,1] выполняется неравенство

       

если  же

     

     

 

     то  функция называется вогнутой. 

     Геометрический  смысл понятий выпуклости и вогнутости для случая функции одной переменной представлен на рис.1.3. Из него, в частности, видно, что график выпуклой функции лежит ниже отрезка, соединяющего точки (х⁽¹⁾, f(x(¹⁾)) и (х⁽²⁾, f(x⁽²⁾)), а график вогнутой — выше. 

       

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

 

     Метод допустимых направлений. Данный метод также называется методом возможных направлений или же по имени автора—методом Зойтендейка. Его основную идею будет удобно продемонстрировать на примере ЗНП с ограничениями в форме неравенств: 

    

     В указанном методе так же, как и  в градиентных методах, находится последовательность точек х⁽⁰⁾ х⁽¹⁾,..., х^(q)..., таких, что f(х^(q+1)) ≥ f(x^(q)) . При этом переход от точки x^(q))  к точке х^(q+1)) происходит по некоторому выбранному направлению s^(q) с шаговым множителем λ_q:

     

     По  отношению к векторам, задающим направления  перемещения, вводятся два фундаментальных понятия.

     F Направление s называется допустимым (возможным) в точке x^(q) Î D, если существует такое  λ > 0, что x^(q+1) = x^(q) + λs Î D.

     F Направление s называется прогрессивным в точке x^(q) Î D, если существует такое λ >0, что   f(x^(q) + λs)> > f(x^(q)) для задачи максимизации и f(x^(q) + λs) < f(x^(q)) для задачи минимизации.

     На  основе данных определений достаточно просто сформулировать критерий проверки оптимальности точки (так называемый критерий оптимальности в терминах допустимых и прогрессивных направлений):

     F точка х* является оптимальным планом задачи, если в ней ни одно допустимое направление не является прогрессивным.

     В алгоритме метода допустимых направлений  правила выбора точки х^(q+1), к которой происходит очередной переход, различаются в зависимости от того, где находится текущая точка х^(q). Принципиально возможны две ситуации.

     1°.  Точка х^(q)  лежит внутри области D, т. е. для всех i Î 1: m g_i(х^(q)) < 0 (см. рис. 1.4). Очевидно, что для внутренней точки любое направление будет допустимым (при выборе достаточно малого шага), поэтому естественным представляется движение в сторону «гарантированного» возрастания значения функции, а именно в направлении градиента. Значит, для внутренней точки х^(q) целесообразно выбрать s^(q) = f(х^(q)).

     Шаговый множитель λ_q выбирается так, чтобы, с одной стороны, новая точка х^(q+1) принадлежала D, а с другой — значение целевой функции в ней f(х^(q+1)) было как можно большим. 

       

     С этой целью сначала найдем промежуток [0, ] из условия для чего необходимо решить систему неравенств: 

       

     Зная  промежуток [0, ], определяем значение шагового множителя λ_q из условия максимизации значения функции в направлении s^(q): 

       

      Вновь найденная точка x^(q+1) может находиться или внутри области D, или на ее границе. В первом случае (на рис. 1.4 ему соответствует точка ^(q+1) переходим к началу данного пункта и повторяем вышеописанные действия, а во втором (точка ^(q+1)  на рис. 1.4) — действуем по рассматриваемой далее схеме.

     2°.  Точка x^(q) находится на границе области (см. рис. 1.5). Это означает, что одно или несколько неравенств из системы ограничений задачи (1.15) выполняются как строгие равенства: g_i(x^(q)) = 0. Например, на рис.1.5 и g₁(x^(q)) = 0 и g₃(x^(q)) = 0.

     Ограничение, которое в текущей точке выполняется  как равенство, называют активным. Множество номеров активных ограничений в точке x^(q) будем обозначать как I(x^(q)). В примере, изображенном на рис. 1.5, I(x^(q)) = {1, 3}. Также из рисунка видно, что все допустимые направления, исходящие из точки x^(q), должны образовывать тупые углы с векторами градиентов функций, задающих активные ограничения в данной точке. Последнее условие может быть выражено через задание ограничений на значения скалярных произведений вектора направления s на градиенты функции ограничений: 

       

     где I_л — множество номеров индексов линейных ограничений, I_н — множество номеров индексов нелинейных ограничений. Соответственно, I(x^(q))◠I_л —номера линейных активных ограничений, а I(x^(q))◠I_н — номера нелинейных активных ограничений. Отличие условий (1.19) от условий (1.20) заключается в том, что в случае линейного ограничения направление, образующее прямой угол с градиентом ограничивающей функции (т. е. их скалярное произведение равно нулю), будет заведомо допустимым, а в случае нелинейного ограничения — возможно, нет.

     Все возможные направления в точке  x^(q) образуют так называемый конус допустимых направлений, и из них для следующего перехода, очевидно, нужно выбрать прогрессивное. Если такового не существует, то согласно сформулированному выше критерию точка x^(q) является оптимальной! Для ускорения максимизации функции желательно, чтобы угол между искомым допустимым прогрессивным направлением s^(q) и градиентом целевой функции ∇f(x^(q)) был как можно меньше или, что то же самое, как можно большей была бы проекция s на ∇f(x^(q)) (при условиях нормировки вектора s^(q)). Иными словами, желательно, чтобы неравенство s^(q)∇f(x^(q))+σ≥0 выполнялось при минимально возможном σ ∈ R. Тогда задачу отыскания наилучшего допустимого прогрессивного направления s^(q) можно свести к задаче минимизации параметра σ: 

       

     при условиях

       

     где s₁² +s₂² +...+s_n², ≤ l —условие нормировки, обеспечивающее ограниченность решения;

             τ — некоторое достаточно малое число, характеризующее «строгость» выполнения неравенств.  

     В отличие от всех остальных, последнее условие в системе (1.22) является нелинейным, что существенно усложняет процесс решения задачи (1.21)-(1.22). Поэтому на практике для определения направления s^(q) (возможно, не лучшего) переходят от данной задачи к задаче линейного программирования путем замены указанных выше условий нормировки на ограничения вида –l ≤ s_j, ≤ 1: 

    

     После того как прогрессивное направление  s^(q) найдено, шаговый множитель определяется по методу, описанному в п. 1°.

     В заключение отметим, что при практических расчетах алгоритм завершается при достижении такой точки х*, в которой |∇f(x*)|<ε, где ε —достаточно малое число. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Практическая  часть.

  Задача №2.2

      Решить симплексным методом следующие  задания, сравнив полученные решения с решениями, найденными геометрически:

    А).                                          Б).

          при ограничениях:                                             при ограничениях:

                                                                  

Решение:

А)

при ограничениях:   

              (1)

Запишем систему ограничений в каноническом виде:

Решаем  симплекс- методом: