4771

Нелинейное программирование. Ограничения на допустимое множество.

Конспект

Информатика, кибернетика и программирование

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

Русский

2012-11-25

468.5 KB

80 чел.

Нелинейное программирование

1 Общая постановка задачи нелинейного программирования

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

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

Пусть f(x1, х2, …, хn), g1(x1,x2,…,xn), g2(x1,x2,…,xn),…gm(x1,x2,…,xn) – нелинейные функции. Основная задача нелинейного программирования может быть сформирована следующим образом: требуется найти n–мерный  вектор (x1, x2,…,xn), удовлетворяющий условиям

                                             xj³0, j=1, 2,…,n;                                          (1)

                                             gi() R 0, i=1, 2,…,m     

и  доставляющий   глобальный   максимум   (минимум) целевой  функции  f(x), то есть                                        

                                                    f(x)® extr                                               (2)

Здесь R – отношения вида (³, £, =).

Определение 1. Множество точек , удовлетворяющих ограничениям (1) называется допустимым множеством задачи или допустимым планом.

Определение 2. Допустимая точка , в которой целевая функция (2) достигает максимума или минимума, называется оптимальным решением или оптимальным планом.

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

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

2 Ограничения на допустимое множество. Выпуклые множества

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

                                                     x1 x2 >1

                                                     x12+x22 1

будут называться несовместимыми.

                                                   x2

                                                    х1х2>1

                                                         x1

                                                    x12+x221

               Рис. 1. Пустое множество

Рассмотренные далее методы оптимизации применимы в том случае, если допустимое множество является выпуклым.

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

Определение 4.  Отрезком, соединяющим две точки  и , называется множество точек  , удовлетворяющих уравнению =t+(1-t), где 0<t<1.

Теорема 1. Пересечение выпуклых множеств есть выпуклое множество.

На рис. 2. показаны примеры выпуклого (рис. 2а) и невыпуклого (рис. 2б) множеств.

                                         х1222£1                                                   х12221    

               x2          х1х2³1                                             x2        x1x2<1

                                                

                      0                             x1                                0                           x1

                       а)                                                                          б)

                       Рис. 2. Множества: выпуклое а); невыпуклое б).

3 Экстремумы функции и стационарные точки

Определение 5. Функция f() имеет в точке 0 локальный максимум или минимум, если найдется такая окрестность этой точки, что для всех  из этой окрестности будет выполнятся неравенство

 f()£(0) для максимума

и f()³f(0) для минимума  (3).

Экстремум называется сильным, если неравенства (3) выполняются как строгие, и слабым, если неравенства (3) выполняются как нестрогие. Из определения вытекает, что точки локального экстремума должны быть обязательно внутренними точками области.

Определение 6. Функция f() имеет в заданной области G глобальный экстремум, если неравенства (3) выполняются для любой точки области (G).

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

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

Теорема 2. Непрерывная функция f(), определенная на непустом замкнутом ограниченном множестве достигает глобального максимума (минимума) по крайней мере, в одной из точек этого множества.  

Для обеспечения замкнутости все ограничения (1) задаются как нестрогие: ³ или £. При этом знаки <, > определяют внутренние, а знаки = граничные точки допустимого множества. Данная теорема дает достаточные условия экстремума. Однако задачи, в которых условия теоремы не выполняются, также могут иметь решения.

Теорема 3. Необходимым условием локального экстремума дифференцируемой функции f() в точке 0 является равенство нулю всех частных производных первого порядка в этой точке:

                                                        ,  j=1,2,…, n                                (4)

Определение 6. Точки, в которых выполняются равенства (4) называются стационарными. Стационарные точки должны быть подвергнуты дополнительным исследованиям с помощью достаточных условий, для того чтобы установить, действительно ли в них достигается локальный экстремум и какой именно.

Так на рис. 3. в точке х4 условия (4) выполняются, но эта точка не является точкой экстремума.

4 Выпуклая (вогнутая) функция

Задача оптимизации значительно усложняется, если целевая функция f() может иметь в допустимой области G не один, а несколько максимумов или минимумов. В этом случае глобальный экстремум может достигаться на границе области и не совпадать с локальным экстремумом. Если заранее известно существование глобального экстремума у функции f() (например, на основании  Теоремы 2.), то достаточно найти все стационарные точки и сравнить значения функции f() в этих точках с экстремальными значениями на границе области. Наибольшее значение будет соответствовать глобальному максимуму. Решение такой задачи может оказаться очень трудоемким, ввиду большого числа ограничений вида (1) в практических задачах.

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

Пусть f() целевая функция, заданная на выпуклом множестве G; 1, 2 – две произвольные точки из G,  0£t –произвольная точка отрезка, соединяющего 1, 2. Рассмотрим отрезок  соединяющий значения f(1) и f(2) функции f()

Определение 7. Функцию f() называют выпуклой, если она целиком лежит выше (не ниже) отрезка, соединяющего две ее произвольные точки, т. е., для любых 1, 2, и   будет выполняться неравенство:

                                                              (5)

Определение 8. Функцию f() называют вогнутой, если она целиком лежит ниже (не выше) отрезка, соединяющего две ее произвольные точки, т. е., если

                                                                 (6)

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

               f      max                            f                                      f

                                 f                       

                                                          z                                            z

                 z                                          f                                                  f

                                                                     min

                                         X                                       X                                                       X

                x1      xopt       x2                                x1      xopt            x2                     x1  x3  xopt  x4   xopt=x2

                               а)                               б)                                  в)

    Рис. 3 Функции: выпуклая а); вогнутая б); общего вида в).

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

Теорема 4. Любой локальный максимум выпуклой или локальный минимум вогнутой функции являются одновременно глобальным.

Теорема 5. Сильный глобальный минимум выпуклой или максимум вогнутой функций, заданных в выпуклой области может достигаться (а в закрытой ограниченной области – достигается) только на границе области.  

Приведенные теоремы позволяют выделить некоторые приемы, упрощающие нахождение глобального экстремума:

  1.  Если функция выпуклая (вогнутая) и из уравнений (4) получена стационарная точка, то в ней достигается глобальный максимум (минимум).
  2.  Для отыскания глобального минимума выпуклой или глобального максимума вогнутой функции достаточно исследование экстремумов  функции только на границе области.

И, наконец, стоит отметить, что сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая).

Рассмотрим некоторые важные виды выпуклых и вогнутых функций.

Линейная функция f()= является выпуклой (и вогнутой) на всем пространстве R(n). Однако она не является ни строго выпуклой, ни строго вогнутой. Квадратичная функция:

f()=      (7)

является выпуклой на всем пространстве R(n), если она отрицательно (не положительно) определенная, то есть, если f()£0 при любом , кроме =0. Квадратичная функция является вогнутой на всем пространстве R(n), если она положительно (не отрицательно) определенная, то есть, если f()>0 при любом , кроме =0.

Указанные свойства квадратичной функции можно установить в общем случае по знакам корней lI  характеристического уравнения матрицы C=, имеющего вид:

                                                                                             (8)

Здесь, диагональные элементы cij являются коэффициентами при хi2, а недиагональные элементы cij=cji равны половине коэффициента при xixj в формуле (7).

Теорема 6.  Для того чтобы квадратичная функция (7) была положительно (отрицательно) определенной, необходимо и достаточно, чтобы все корни уравнения (8) были положительными (отрицательными).

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

5 Функция Лагранжа. Условия Куна – Таккера

С каждой задачей нелинейного программирования связывается так называемая функция Лагранжа

                                       L()                                (9)

рассматриваемая на множестве пар векторов =(х1, х2,…, хn) и =(l1, l2, …lm).

Здесь i  - множители Лагранжа.

Классическая задача оптимизации состоит в нахождении min (max) целевой функции f(), где  – точка в пространстве R(n) при наличии ограничений типа равенств:

                                                          gi()=0                                         (10)

В этом случае задача на условный max (min) целевой функции f() при наличии ограничений типа равенств сводится к задаче определения стационарных точек функции Лагранжа L().

                                                                                          (11)

Решая систему (11), состоящую из n+m уравнений, определяем стационарную точку  в которой может достигаться условный экстремум.

В задачах НЛП имеют место ограничения более общего вида:

                                                                                           (12)

Cформируем необходимые условия того, что в точке  достигается оптимальное решение задачи НЛП, например минимизируется функция f() при ограничениях (12). Рассмотрим случай, когда i=, то есть gi()=0. Пусть  – точка, соответствующая оптимальному решению. Она может быть или внутренней, или граничной, то есть каждая из ее компонентов xj будет удовлетворять условию xj>0, либо условию xj=0.

Если хj находится внутри области, то отклонение от точки х возможны как в сторону увеличения, так и в сторону уменьшения хj. Но поскольку х – оптимальная точка, то должно быть

                                                                       .

Если хj лежит на границе допустимой области (хj=0), то отклонение от оптимальной точки возможны только в сторону увеличения хj, при этом f() должна увеличиваться, так что

                                                                         .

Таким образом, для этого случая необходимые условия примут вид:

                                                                                   (13)

                                                     

Рассмотрим случай gi()0, . Заменим ограничения типа неравенства на ограничения типа равенства путем введения дополнительных неотрицательных переменных ui. При этом ограничения

                                                                                               (14)

Причем

                                                                                    (15)

Функция Лагранжа для этого случая будет иметь вид:

                                                                                   (16)

Условия, которым должны удовлетворять значения ui, xi, li в точке оптимального решения будут выражаться соотношениями (13) применительно к функции Лагранжа (16)

                                                                         (17)

                                                                      (18)

                                                                       (19)

Условие (19) получено с учетом соотношения (15).

Соотношение (17) вводит ограничения на множители Лагранжа li. Из него следует, что в функцию L() (16) ограничения типа равенств исходить не будут, так как для них li=0, а ограничения типа равенств, соответствующие ui=0 будут входить с li>0. Поэтому функция Лагранжа            фактически совпадает с функцией Лагранжа , определяемой соотношением (19).

Принимая во внимание соотношение (17) запишем соотношение (19) в виде:

                                                                          (20)

Условия (18) и (20) называют условием Куна-Таккера. Условие Куна-Таккера можно записать в ином виде:

                                                                                 (21)

Рассмотрим случай gi()³0, i=. Ограничения типа равенств будут иметь вид

                                               gi()-ui =0                                       (22)

Причем

                                                                                                 (23)

Функция Лагранжа для этого случая будет иметь вид:

                                                                   (24)

Условия, которым должны удовлетворять ui, xi, li в стационарной точке применительно к функции Лагранжа (24) будут:

                                                                      (25)

                                                                    (26)

                                                    (27)

Учитывая ограничения (25) на множители Лагранжа условия Куна-Таккера запишем в виде:

                                                                       (28)

                                                              (29)

Или в ином виде:

                                                              (30)

Аналогично могут быть получены необходимые условия и для случая максимизации целевой функции f().

Необходимые условия Куна-Таккера являются также достаточными, если целевая функция и область допустимых решений обладают определенными свойствами, связанными с выпуклостью и вогнутостью (табл. 1.)

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

                                                                                               Таблица 1.

Тип оптимизации

Требуемые свойства

Целевая функция

Область допустимых решений

Максимизация

Выпуклая

Выпуклое множество

Минимизация

Вогнутая

Выпуклое множество

Для метода Лагранжа условия Куна-Таккера сведены в табл.2.

                                                                                                    Таблица 2.

Тип оптими-зации

Тип ограничений

Требования

gi(x)

f(x)

xj

li

xj

max

gi(x)=0, i=1,r

Ли-ней-ная

Вы-пук-лая

³0

Нет огра-нич.

£0

=0

=0

=0

gi(x)<0, i=r+1,k

Вог-ну-тая

£0

£0

£0

gi(x)>0, i=k+1,m

Вы-пук-лая

³0

£0

³0

min

gi(x)=0, i=1,r

Ли-ней-ная

Во-гну-тая

³0

Нет огра-нич.

³0

=0

=0

=0

gi(x)£0, i=r+1,k

Вогнутая

³0

³0

£0

gi(x)³0, i=k+1,m

Вы-пук-лая

£0

³0

³0

В таблице 2 L – функция Лагранжа общего вида

                               (31)

где ui0 – дополнительные переменные.

Другая интерпретация условия Куна-Таккера связана с понятием седловой точки функции Лагранжа L().

Определение 9. Седловой точкой функции L() называют такую точку в которой функция L() достигает минимума по  и максимума по  для задачи минимизации, и максимума по , но минимума по  для задачи максимизации, то есть точку (0,, 0), удовлетворяющую условиям:

                                                                                         (32)

                                                                            (33)

Когда целевая функция f() и ограничения gi() являются функциями одной переменной, условия (32) и (33) могут быть проиллюстрированы графически (рис. 4.).

                                             L

                                                             Седловая точка

                                                                 λo,(x0)

                                  x0, (l0)                                                                               

                                                        

                       x,(l)                             λ>0,x>0,        

                Рис. 4. Функция Лагранжа в окрестности седловой точки.

Таким образом, с каждой задачей нелинейного выпуклого программирования связывается функция Лагранжа L(), рассматриваемая на множестве пар векторов , . Нетрудно доказать следующее утверждение (теорема Куна-Таккера).

Теорема 7. Если пара векторов  и 0 является седловой точкой для функции Лагранжа, -оптимальный вектор в соответствующей задаче нелинейного программирования.

Если необходимые и достаточные условия Куна-Таккера выполняются, то могут быть найдены эффективные вычислительные методы решения задач НЛП, например, задачи квадратичного программирования.

6 Метод решения задач квадратичного программирования

Задачей квадратичного программирования называют задачу НЛП, в которой находиться экстремум суммы линейной и квадратичных форм при ограничениях типа линейных неравенств и неотрицательности переменных. Эта задача имеет вид:

                                                                                           (34)

                                                                                             (35)

                                                       

Здесь R – отношение вида

Методика решения задачи квадратичного программирования заключается в следующем:

  1.  Функция f() проверяется на выпуклость или на вогнутость в зависимости от постановки задачи на максимум или на минимум.
    1.  Записывается функция Лагранжа

                      

  1.  Вычисляются частные производные  и

                            

                                                               

  1.  Записываются необходимые условия существования седловой точки в

соответствии с типом ограничений (табл. 2.). Например, для задачи на      максимум и ограничениях типа  условия Куна-Таккера≤0, ≥0,                           xj=0, ,i=0, xi≥0, i≥0.

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

5. Условия Куна-Таккера записываются в виде равенств путем введения дополнительных переменных.

                                                                                        (36)

                                                       

                                                        (37)

6.   Находим координаты седловой точки используя симплекс-метод.

Система (36) содержит  линейных уравнений с  переменными из которых  являются свободными и равны нулю. Остальные переменные образуют при этом допустимое базисное решение, если выполняется условие (37).

Если в исходной системе (36) можно выделить начальное допустимое базисное решение, то его улучшение производят на основании симплекс-метода, аналогичного рассмотренному в задаче линейного программирования. Отличие здесь заключается в том, что при выборе новой базисной переменной каждый раз должны проверяться условия  которые означают, что если в базисе имеются или то в него не могут быть введены переменные  и  соответственно.

Если в системе (36) нельзя сразу выделить начальное допустимое базисное решение, то оно может быть получено введением в систему фиктивных переменных .

+uj=0,

                                                           - vi +zi=0                                        (38)

В этом случае для улучшения начального допустимого баланса решения используют М-метод (подробнее алгоритм М-метода см. в п.3.5). То есть решают задачу максимизации функции F=при ограничениях (37) и (38). Здесь М – сколь угодно большое положительное число. Оптимальное решение может быть получено, если фиктивные переменные перейдут в разряд свободных, то есть будут выведены из базиса в процессе улучшения начального допустимого базисного решения.


Пример
1  Требуется максимизировать

                                                               (39)

при  условиях:

                                                                                      (40)

Функция f представляет собой сумму линейной функции 4x1+10x2+x3, которую можно рассматривать как выпуклую и квадратичной x12-4x22-4x33. Последняя является отрицательно определенной, следовательно также выпуклой.  

В соответствии с типом оптимизации (39) и видом ограничений (40), ограничения, накладываемые  на переменные  - табличные. Поэтому условия (40) должны быть записаны в виде:

                                                       

                                                                                                                         (41)

для которых .

3.  Функция Лагранжа

            

и условие Куна-Таккера (таблица 2):

                                   

4.  Частные производные от функции Лагранжа по переменным  и

                                                                =

                                                                =

                                                                 =

                                                                 =

                                                                 =

5. Условия Куна-Таккера

                                                                              (42)

6. Условия (42) приводим к каноническому виду (ограничения равенства) путем введения дополнительных переменных u10, u20, u30, v10, v20.

                                               

                                                                               (43)

                                                   

7.  Формируем исходный базис путем введения фиктивных переменных  в ограничения (43):

                                                                 

                                                               

                                                               

                                                                                                    (44)

                                                                 

                                                                 

                                                                 

и решаем задачу максимизации функции  при ограничениях (44) симплекс-методом (решение в виде последовательности симплекс-таблиц представлено ниже).

БП

Cб

В

0

0

0

0

0

0

0

0

0

0

X1

X2

X3

l1

l2

U1

U2

U3

V1

V2

Z1

Z2

Z3

Z1

-м

4

2

0

0

1

1

-1

0

0

0

0

1

0

0

Z2

-м

10

0

8

0

1

1

0

-1

0

0

0

0

1

0

Z3

-м

1

0

0

8

3

1

0

0

-1

0

0

0

0

1

V1

0

16

1

2

3

0

0

0

0

0

1

0

0

0

0

V2

0

30

1

1

1

0

0

0

0

0

0

1

0

0

0

-15м

2м

8м

8м

5м

3м

-м

-м

-м

0

0

0

0

0

БП

В

0

0

0

0

0

0

0

0

0

0

X1

X2

X3

l1

l2

U1

U2

U3

V1

V2

Z1

Z2

Z3

Z1

-м

4

2

0

0

1

1

-1

0

0

0

0

1

0

X2

0

1.25

0

1

0

0.125

0.125

0

-0.125

0

0

0

0

0

Z3

-м

1

0

0

3

3

1

0

0

0,12

0

0

0

1

V1

0

13.5

1

0

3

-0.25

-0.25

0

0.25

0

1

0

0

0

V2

0

28.75

1

0

1

-0.125

-0.125

0

0.125

0

0

1

0

0

-5м

2м

0

8м

4м

2м

-м

0

-0.12м

0

0

0

0

БП

В

0

0

0

0

0

0

0

0

0

0

X1

X2

X3

l1

l2

U1

U2

U3

V1

V2

Z1

Z2

Z3

Z1

-м

4

2

0

0

1

1

-1

0

0

0

0

1

X2

0

1.25

0

1

0

0.125

0.125

0

-0.125

0

0

0

0

X3

0

0.125

0

0

1

0.375

0.125

0

0

-0.016

0

0

0

V1

0

13.125

1

0

0

-1.375

-0.625

0

0.25

0.047

1

0

0

V2

0

28.625

1

0

0

-0.5

-0.25

0

0.125

0.016

0

1

0

-4м

2m

0

0

m

m

-m

0

0

0

0

0

БП

В

0

0

0

0

0

0

0

0

0

0

X1

X2

X3

l1

l2

U1

U2

U3

V1

V2

Z1

Z2

Z3

X1

0

2

1

0

0

0.5

0.5

-0.5

0

0

0

0.5

X2

0

1.25

0

1

0

0.125

0.125

0

-0.125

0

0

0

X3

0

0.125

0

0

1

0.375

0.125

0

0

-0.016

0

0

V1

0

11.125

0

0

0

-1.875

-1.125

0.5

0.25

0.047

1

0

V2

0

26.625

0

0

0

-1

-0.75

0.5

0.125

0.016

0

1

0

0

0

0

0

0

0

0

0

0

0

Оптимальный план opt= (2; 1.25; 0.125; 0; 0; 0; 0; 0; 11.125; 26.625).

Целевая функция Fmax= 4*2+10*1.25+0.125-22-4*0.1252 = 10.3125

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

7 Метод линеаризации Франка-Вульфа

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

Общая постановка задачи:

                                                                                                       (45) 

                                                                                                              (46)

          

Здесь R – отношения вида .

Суть метода при линейной аппроксимации заключается в том, что:

1. Нелинейная функция (45) заменяется линейной в точке (к), принадлежащей допустимой области G

                                         (47)

2. Решается задача линейного программирования:

                                                                                                                                (48)

                   

                                                                               

Пусть решением этой задачи является точка  (k).

3. Из точки в направлении  смещаемся с некоторым шагом  в точку                                                  (49)

Так как и принадлежат допустимой области G, а область G, определяемая ограничениями (46) выпукла и , то  (k + 1)G.

Шаг  можно выбирать по-разному:

  1.  шаг  - произвольное, достаточно малое число ;
  2.  шаг  выбирается таким, при котором функция принимает наибольшее значение при всех  . Если найденное значение принадлежит концам отрезка [0;1], то необходимо выбрать один из концов этого отрезка.

3. Итерации продолжаются до тех пор, пока

                                                                                                                (50)

где -положительное, малое число.


Пример 2 Требуется максимизировать функцию

                                                                           (51)

                     при условиях                                                           (52)

с точностью 0,1.

В качестве начального допустимого вектора берем  (0) = (0,0). Значение целевой функции в этой точке F (0) = 0. Нелинейную функцию (51) заменяем линейной и F * (0,0) в соответствии с (47)

                                     

Далее решаем задачу: х1 + 8х2  ® mах

                                                      

Здесь ограничения (52) приведены к каноническому виду.

БП

Cб

В

1

8

0

0

X1

X2

X3

X4

X1

1

7

1

8

1

0

X4

0

5

0

0

0

1

7

0

0

-1

0

X1

1

2

1

0

1

-1

X2

8

5

0

1

0

1

42

0

0

-1

-7

Итак, . Вектор находим по формуле (49):  Шаг  найдем из условия максимума f ( (1)) при .

F ( (1)) = - (2) 2 - (5) 2 + 2 + 8*5 = -292 + 42.

( (1)) = -58 + 42 = 0. Откуда = 0,724.

Следовательно  (1) = (1,448; 3,62). Значение целевой функции в этой точке       F (1) = 15,207.

Вторая итерация: F * (1,448; 3,62) = -1,896х1 + 0,76х2; (1) = (0,5);

 (2) = ((1-) 1,448; 5 + (1-) 3,62);  = 0,474;

(2) = (0,762; 4,27); F (2) = 16,108.

Третья итерация: F * (0,762; 4,27) = -0,524х1-0,54х2;  (2) = (0,0);

 (3) = ((1-) 0,762; (1-) 4,27);  = 0,072;

 (3) = (0,707; 3,963); F (3) = 16,206.

| F (3) -F (2) | = | 16,206-16,108 | = 0,098 < 0,1. То есть приближенно можно считать, что Fмax = 16,206; opt = (0,707; 3,963) .Точное решение этой задачи: Fмax = 16,25; opt = (0,5; 4).

8 Градиентные методы

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

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

Общая постановка задачи соответствует (1) и (2). Однако, не теряя общности, она может быть преобразована к виду

                                                                                                      (53)

                                                                                                  (54)

                                                                                                                                  (55)

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

                                                                                                            (56)

Различие градиентных методов состоит в способе определения направления  и параметра .

Выбор направления :

1. Если - внутренняя точка области допустимых решений, то

                                                        (57)

есть градиент функции в точке . Стратегия, выражаемая соотношением (57) определяет движение с переменным шагом, так как значение шага зависит от значения градиента . Поскольку значение градиента уменьшается вблизи оптимума, то на некоторых участках шаги будут мелкими, что удлиняет время поиска. От этого недостатка можно избавиться, если использовать градиентную стратегию с постоянным шагом. В этом случае вектор градиента заменяется на вектор направления градиента:

                                                                                                              (58)

где         

2.  не принадлежит допустимой области. Это может иметь место в случае, если точка, двигаясь в сторону наибольшего возрастания функции нарушила  i-ое ограничение (54). В качестве штрафа за нарушение i-ого ограничения введем множитель Ri и вспомогателную целевую функцию.

L(x) = f()

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

В простейшем случае Ri  выбирается следующим образом:

                                                                                      (59)

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

                                                                                       (60)

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

Данного недостатка можно избежать, если принять что штраф должен быть тем меньше, чем меньшее нарушение может иметь место, то есть целесообразно предположить, что

                                                                                     (61)

Выбор параметра :

  1.  Параметр  число постоянное на всех итерациях. Чем меньше число , тем точнее вычисления. Соответственно увеличивается и время поиска оптимума;
  2.  Параметр  выбирают на каждом шаге из условия min {λ′‚ λ″},  где     λ – значение параметра, при котором луч +λ(k)S(k) пересекает ОДЗ;     λ″ - такое допустимое значение λ , при котором функция f(+λ(k)S(k)) достигает максимума на луче. Данная стратегия позволяет находиться в точке ОДЗ и оптимизировать количество итераций. Однако, при нелинейных ограничениях и нелинейной целевой функции вычисление λ, λ″ может оказаться достаточно трудоемким.

Для иллюстрации градиентного метода выберем следующую стратегию:    λ – число постоянное; величина штрафа пропорциональна величине нарушения ограничения; направление движения точки совпадает с направлением градиента. Это так называемый градиентный метод Эрроу-Гурвица. Если ограничения по знаку (55) отсутствуют, то координаты новой точки можно рассчитать в соответствии с (56), (60) по формуле:

                                                                (62)

С учетом условия неотрицательности (55), выражение (62) будет выглядеть:

                                (63)

В выражениях (62) и (63) функция штрафа  вычисляется по формуле (61).

Пример 3 Требуется максимизировать функцию

                       F(x)= -x12-x22  при условии -(x1-2)2 – (x2-2)2 + 1 0

Пусть λ=0.1; R1(0)=2; x1(0)=3; x2(0)=1.5, то есть мы выбрали начальную точку, заведомо не принадлежащую допустимой области.

Уравнения (62) имеют следующий вид:

                                          

Уравнения (61) имеют следующий вид:

                 

Первая итерация:

                              

Вторая итерация: Точка  находится уже внутри допустимой области, однако, множитель , хотя и меньше , но еще отличен от 0 и граница продолжает «подталкивать» движущуюся точку внутрь допустимой области (эта точка еще находится на «опасном расстоянии» от границы):

                                         

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


Список рекомендованной литературы

  1.  А. В. Кузнецов, И. И. Холод. Математическое программирование. - Минск: «Высшая школа», !984. – 221 с.
  2.  Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч.-метод. Посібник для самост. Вивч. Диск. – к.: КНЕУ, 2001. – 248с.
  3.  Г.Г. Цегелик. Лiнiйне програмування.- Л.: «Свiт», 1995. – 216 с.
  4.  Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.
  5.  И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.
  6.  Индивидуальные задания для выполнения контрольных работ по курсу «Математическое программирование» (Линейное программирование) для студентов экономических специальностей всех форм обучения.// Сост.: Глущевский В.В., ст. преподаватель, Исаенко А.Н., ст. преподаватель, -  Запорожье: ЗГИА, 2002г. – 66с.
  7.  Лекции по теории графов /Под ред. Емеличева В.А. и др. - М.: Наука, 1990.
  8.  Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.
  9.  С. Гасс. Линейное программирование. - М.: «Наука», 1961.-303 с.
  10.  Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
  11.  Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.
  12.  Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.


 

А также другие работы, которые могут Вас заинтересовать

46538. Договор поставки и его особенности 19.45 KB
  Договор поставки обычно включает следующие реквизиты: название документа; порядковый номер документа; дата заказа; название и адрес заказывающей компании; ответственность за заказ указывается контактная информация для выяснения поставщиком всех вопросов связанных с заказом МР; реквизиты поставщика МР; наименование товара; количество и качество товара; спецификация запрашиваемых МР; цена заказываемого товара; условия и срок поставки; условия платежа; характеристика тары и упаковки; порядок приемкисдачи; расчетные счета сторон договора. К...
46539. Методика организации уроков-бесед по изобразительному искусству 19.56 KB
  Ценность урокабеседы заключается в том что взрослый учит ребенка логически мыслить помогает думать. Для учителей и воспитателей важнее всего изучить детей в естественных условиях педагогического процесса; большим подспорьем для них является психологопедагогическая характеристика охватывающая все важнейшие стороны личности ребенка. Хотя данная форма в специальном образовании уже редко практикуется в массовых школах и дошкольных учреждениях она является одной из форм описания психологом учителем воспитателем индивидуального состояния...
46540. Методика освоения декоративной росписи 19.58 KB
  План: цель и задачи методики содержание обучения методике освоения дрметоды и приемы обучения средства обучения Усиление познав активности на уроках по ДР. Структура урока освоения декоративной росписи: орг. Для урока характерны специфические признаки: 1. Структура урока и методика его проведения зависят от дидактических целей и задач которые решаются в процессе обучения.
46541. Художественные способности, задатки и склонность к изо-деятельности. Закономерности проявления творческих способностей школьников на уроках ИЗО 19.6 KB
  Понятие непрерывного образования. Современная общеобразовательная школа как базовое звено непрерывного образования. Главный вопрос связанный с непрерывным образованием задется учеными поразному: образование на всю жизнь или образование через всю жизнь Одной из центральных идей должна стать идея перехода от школы знаний к школе культуры рассмотрение образования как части общей культуры и ее важного фактора и источника. Непрерывность будет обеспечена если при проектировании системы образования будут учтены и рассмотрены условия для...
46542. Система управления охраной труда (СУОТ) в РФ 19.65 KB
  Значение Ксп = А Б А 31 Где А общее количество работающих на момент проверки 1 раз в месяц в подразделении; Б количество работающих с нарушениями правил и инструкций ОТ. n; Тс количество требований БТ соответствующих требованиям стандартов по данному оборудованию или процессу; Тс общее количество требований БТ по данному оборудованию или процессу; n количество единиц оборудования или процессов на участке; Ктбу1 Ктбу2 Ктбуm коэффициент технической безопасности участков 1 2 . m по оборудованию или процессам; m ...
46543. Подходы и методы, используемые для определения рыночной стоимости застроенных земельных участков 19.69 KB
  Методические основы оценки рыночной стоимости земельных участков Рыночную стоимость имеют те земельные участки которые способны удовлетворять потребности пользователя потенциального пользователя в течение определенного времени принцип полезности. Методы оценки Оценщик при проведении оценки обязан использовать или обосновать отказ от использования затратный сравнительный и доходный подходы к оценке. Оценщик вправе самостоятельно определять в рамках каждого из подходов к оценке конкретные методы оценки.
46545. Методика организации уроков по рисованию с натуры 19.74 KB
  Методика организации уроков по рисованию с натуры. План : рисование с натуры в содержании программы по изо под ред Неменского задачи рисования с натуры структура урока рисования с натуры возрастные особенности организации уроков вывод. 1Рисование с натуры рисунок и живопись включает в себя также рисование по памяти и по представлению объектов действительностл карандашом а также акварельными и гуашевыми красками пером и кистью. Задачи: Рисование с натуры активизирует умственную деятельность это не созерцание а пониятие о предмете...
46546. Острая эмпиема плевры. Диагностика. Современные принципы лечения 19.74 KB
  Альвеококкоз печени. Альвеококкоз Альвеококкоз альвеолярный эхинококкоз печени тяжелое длительно протекающее заболевание которое вызывается ленточным гельминтом lveococcus multiloculris. Личинка альвеококка паразитирующая у человека представляет собой множество мелких заполненных жидкостью пузырьков не более 36 мм в диаметре окруженных фиброзной тканью Обычно среди полного здоровья обнаруживается очень плотная увеличенная печень или каменистая опухоль в области печени. Наиболее часто среди них встречается обтурационная желтуха...