Методы решения задач нелинейного программирования. Тема №9

1.

Тема лекции 9. Методы решения задач нелинейного программирования.
Цель лекции: Понятия модели нелинейного программирования. Рассмотреть
Методы решения задач нелинейного программирования.
Конспект лекции: Модели нелинейного программирования
В общем виде, задача нелинейного программирования состоит в определении
максимального (минимального) значения функции
f (x1,x2,...,xn ),
(9.1)
при условии, что ее переменные удовлетворяют соотношениям
g i ( x 1 , x 2 , . .. , xn )≤bi
g i ( x 1 , x 2 , . .. , xn )=bi
{
i =1, . .. , k
i =k +1, .. . ,m
(9.2)
где f и gi - некоторые известные функции n переменных, а bi - заданные
числа.
Здесь имеется в виду, что в результате решения задачи будет определена
точка Х =(x 1,x 2,...,x n), координаты которой удовлетворяют соотношениям
(9.2) и такая, что для всякой другой точки Х=(x1,x2,...,xn), удовлетворяющей
условиям (9.2), выполняется неравенство
f (x 1,x 2,...,x n) f ( x1,x2 ,...,xn ),
(9.3)
[ f (x 1,x 2,...,x n ) f (x1,x2,...,xn )] .
(9.4)
Если f и gi - линейные функции, то задача (9.1) , (9.2) является
задачей линейного программирования. Соотношения
(9.2) образуют
систему ограничений и включают в себя условия неотрицательности
переменных, если такие условия имеются. Условия неотрицательности
переменных могут быть заданы и непосредственно.
Метод множителей Лангранжа
Рассмотрим
частный
случай
общей
задачи
нелинейного
программирования (9.1), (9.2), предполагая, что система ограничений (9.2)
содержит только уравнения, отсутствуют условия неотрицательности
переменных и
f (x1,x2,...,xn ) и gi(x1,x2,...,xn )- функции, непрерывные вместе со своими
частными производными
f(x1, x2,..., xn ) max (min) ;
(9.4)
g i(x1,x2,...,xn ) = bi ( i = 1,...,m ) .
(9 .5 )
В курсе математического анализа задачу (9.5), (9.6) называют задачей на
условный экстремум или классической задачей оптимизации.Чтобы найти
решение этой задачи, вводят набор переменных 1, 2,..., m, называемых
множителями Лагранжа, составляют функцию Лагранжа

2.

n
∑ λi
F( x1,x2,...,xn, 1, 2,..., m )=f (x1,x2,...,xn )+ i=1
(9.7)
∂F
∂xj
находят частные производные
(j = 1,...,n) и
рассматривают систему n + m уравнений
{
[b - g i (x1,x2,..., xn)],
∂F
∂ λi
(i = 1,...,m) и
m
∂ gi
∂F ∂f
=
− ∑ λi
=0
∂ x j ∂ x j i=1 ∂ x j
∂F
=b i−gi ( x1 , x 2 , .. . xn )=0
∂ λi
j=1 . .. n
( i=1 . .. m)
(9.8)
c n +m неизвестными x1,x2,...,xn, 1, 2,..., m . Всякое решение системы
уравнений (9.8) определяет точку Х(xo1, xo2,...,xon,) , в которой может иметь
место экстремум функции f(x1,x2,...,xn). Следовательно, решив систему
уравнений (9.8), получают все точки, в которых функция (9.5) может иметь
экстремальные значения. Дальнейшее исследование найденных точек
проводят так же, как и в случае безусловного экстремума.
Таким образом, определение экстремальных точек задачи (9.5) , (9.6)
методом множителей Лагранжа включает следующие этапы:
1.
Составляют функцию Лагранжа
2.
Находят
частные производные от функции Лагранжа по переменным
и λ i и приравнивают их к нулю.
3. Решая систему уравнений (9.8), находят точки, в которых целевая
функция задачи может иметь экстремум.
4. Среди точек, подозрительных на экстремум, находят такие, в которых
достигается экстремум, и вычисляют значения функции (9.6) в этих точках.
Метод множителей Лагранжа позволяет находить максимум или
минимум функции при ограничениях, имеющих вид равенств. Важность
этого метода обусловливается как его прямым применением при решении
задач (он часто встречается в литературе по экономическим вопросам), так
и тем фактом, что он служит мостом к современным работам по теории и
вычислительным вопросам нелинейных задач программирования.
Идея метода множителей Лагранжа (и тем самым алгорифмов для
решения задач нелинейного программирования) заключается в том, что
вместо задачи максимизации целевой функции, подчиненной ряду
дополнительных условий или ограничений, решается задача максимизации
хотя и несколько более сложной функции (функции Лагранжа), но зато
уже без ограничений. Практически этот метод может быть применен к
задачам следующего вида. Найти
max f ( x1 , x 2 , .. .. , x n )
(9.9)
при условиях

3.

g1 ( x 1 , x 2 ,...., x n)=0,
g2 ( x 1 , x 2 ,...., x n)=0
...............................
gm ( x 1 ,x 2 ,....,x n )=0
где все функции f, g1,g2, …gm дифференцируемы. Необходимо отметить,
что здесь на переменные не налагается условия неотрицательности.
Для того чтобы обосновать и объяснить предлагаемый метод, рассмотрим
следующую задачу
небольших
размеров.
Найти max f(x1,x2)
при условии g(x1,x2) = 0.
(9.10)
Ограничивающее равенство означает, что при поиске значений
переменных x1 и х2, которые максимизируют функцию f, мы
ограничиваемся множеством таких точек (x1,x2), для которых g(x1,x2) = 0.
При переходе от одной точки этого множества к другой значение функции
g не изменяется.
В силу дифференцируемости функции g мы можем охарактеризовать
это соотношение между x1 и х2 как
dx 2
dg
=g x1 + g x2
=0
dx 1
dx 1
(9.11)
dg
gx , gx
1
2
где dx 1 — полная производная функция g по x1 a
— частные
производные функции g. Тот факт, что для всех значений переменных x1 и
х2 должно обязательно выполняться условие g(x1,x2) = 0, определяет
переменную х2 как функцию от x1. Таким образом, полная производная
выражает скорость изменения величины g в зависимости от изменений
dx 2
переменной x1; при этом производная dx 1 означает, что переменная х2
одновременно
изменяется
в
такой
степени, чтобы обязательно
dx 2
dx 1 иногда называют (особенно
выполнялось условие g(x1,x2) = 0. Член
в литературе по экономике) «маргинальной скоростью изменения х2 по
x1». Из формулы (9.11) его можно выразить следующим образом:
gx
dx 2
=− 1
dx 1
gx
2
(9.12)
0 0
Предположим теперь, что мы нашли некоторую точку ( x1 , x 2 )∈ K , где
K= {( x 1 , x2 ) : g ( x 1 , x 2 )=0 }
в которой функция достигает максимума
(относительного или абсолютного) в области K. В этом случае не должно

4.

быть допустимых изменений переменной x1 или x2, увеличивающих
0 0
значение f, т. е. в точке ( x1 , x 2 ) должно выполняться равенство
dx 2
df
=f x1 + f x2
=0
dx 1
dx 1
(9.13)
Так как в точке
0
0
( x1 , x 2 )
выполняется равенство g(x1,x2) = 0 для нее
dx 2
справедливо (9.12). Подставляя выражение для dx 1 из (9.12) в формулу
(9.13), мы получаем
2
1
(9.14)
или
fx
1
g x1
=
g x1
( )
f x +f x −
gx
=0
2
f x2
g x2
(9.15)
Таким образом, в максимизирующей точке частные производные функций
f и g по x1 и х2 должны быть пропорциональны. Обозначив коэффициент
пропорциональности через — λ , мы из формулы (9.15) получим
f x + λgx =0 и f x + λgx =0
2
2
2
1
(9.16)
( x10 , x 02 ) , если она удовлетворяет
Эти условия означают, что точка
первоначальному ограничению, является максимизирующей. Поэтому они
являются необходимыми условиями в задаче максимизации при
ограничениях, имеющих форму равенств. Введем теперь функцию
L( x1 , x 2 , λ )=f ( x 1 , x 2 )+ λg( x 1 , x 2 ) .
(9.17)
Мы видим, что, приравнивая нулю частные производные функции L по
переменным x1, х2 и λ , мы как раз получим выражения (9.16) и
первоначальное ограничение. Эта функция называется функцией Лагранжа
для задачи (9.10), а переменная λ — множителем Лагранжа.
Введением функции Лагранжа мы свели задачу максимизации при
ограничивающем равенстве к обычной задаче максимизации без
ограничений. Подобным же образом можно преобразовать и более
сложную многомерную задачу с несколькими ограничивающими
равенствами. В результате будет иметь место следующая теорема.
Теорема НП10. Пусть функцией Лагранжа для задачи (9.9) является
функция
m
L( x1 ,. .. . .. . , x n , λ 1 ,. . .. .. , λm )=f ( x1 ,. .. . .. .. . , x n )+ ∑ λ i g i ( x 1 ,. . .. .. . x n ).
i =1

5.

Тогда
необходимыми
условиями
того, что точка
представляет решение задачи (9.9), будут равенства
Lx ( x 01 ,. .. . .. , x0n ; λ 1 , .. . .. .. , λm )=0 , i=1, . .. .. . , n
i
0
0
0
( x1 ,. . .. .. . , x n )
0
L λ ( x 1 ,. .. . .. , x n ; λ 1 , .. . .. .. , λ m )=0 , j=1 ,. .. . .. , m.
j
Обсуждение достаточных условий в терминах лагранжевой формы задачи
увело бы нас слишком далеко. И действительно, найти где-либо в
литературе обсуждение достаточных условий не так просто, за
исключением задачи двух переменных с одним ограничением. Для этого
последнего случая справедлива следующая теорема.
0 0
( x1 , x 2 ) , удовлетворяющей необходимым
Теорема НП11.В точке
Lx =0 , Lx =0 , L λ =0
2
1
условиям
,
достигается
максимум,
если
положительным является следующий определитель [частные производные
0 0
второго порядка вычислены в точке ( x1 , x 2 ) ]:
L x1 x 1
| Lx x
Lx 1 x 2
L x1 λ
f x 1 x 2 + λg x 1 x 1
f x1 x2 + λ
g x1 x2 g x1
2 1
Lx 2 x 2
L x2 λ |= f x 2 x 2 + λg x 2 x 1
f x x +λ
gx x gx
Lλx 1
Lλx 2
L λλ
g x2
0
(
g x1
2 2
2 2
2
)
Замечательно то, что задачу нахождения условного максимума можно
решить путем добавления новых переменных в форме множителей
Лагранжа. Эти новые переменные могут быть интерпретированы как
двойственные
переменные
к
нашей
нелинейной
задаче
с
ограничивающими равенствами. Каждому ограничению ставится в
соответствие одна переменная λ j , а значение каждой переменной λ j ,
0
0
( x1 ,. . .. .. . , x n ) и является
соответствующее максимизирующей точке
скоростью, с которой может возрасти целевая функция f, если несколько
ослабить j-е ограничение. Неотрицательности от переменных λ j не
требуется.
Пример 1. Некоторая энергетическая компания обладает двумя
гидроэлектростанциями, стоящими на одной и той же реке. Отводная
плотина регулирует общий поток воды таким образом, что возможно
любое его распределение между этими двумя станциями. Мощности
станций могут быть выражены следующими функциями:
x1
−
t2
2
−
t2
2
P1 ( x 1 )=∫ e
0
x
2
P2 ( x 2 )=∫ e
dt ,
dt
0
где переменные x1 и х2 — величины потоков воды, направляемых
соответственно на первую и вторую плотины. Предполагая, что речной

6.

поток с направляется на станции полностью, мы получим следующее
ограничение:
с — x1 — х2 = 0.
Функцией Лагранжа для этой задачи будет функция
x1
−
L( x1 , x 2 , λ )=∫ e
0
t2
2
x2
2
−
dt +∫ e
t
2
dt + λ(c−x 1 −x 2 )
0
Взяв частные производные, как указано в теореме НП10, мы получим
2
−
Lx =e
1
2
x1
2
− λ=0 ;
−
L x =e
2
x2
2
−λ= 0 ,
L λ = c−x 1−x 2 =0 .
Из первых двух условий легко получить, что
x 01= x02 =
−
e
x 21
2
−
=e
x 22
2
, так что
c
2 . После проверки условий
возможным решением будет
теоремы НП11 о производных второго порядка видно, что эта точка
доставляет максимум. Необходимо отметить, что в данной задаче все
нужные шаги можно проделать и без непосредственного вычисления
множителя К. Однако из написанных выше уравнений видно, что
0
−
λ =e
x21
2
−
c2
8
Согласно нашей интерпретации множителей Лагранжа как
двойственных переменных, или теневых цен, значение Х° должно
представлять скорость, с которой возрастает общая мощность при
небольшом изменении правой части ограничения.
Контрольные вопросы:
1. Привести математическую модель задачи нелинейного программирования
2. Перечислите методы решения задачи нелинейного программирования
3. Перечислите этапы метода множителя Лагранжа.
4. В чем суть метода Лагранжа
Литература:
1. Акулич И.Л. Математическое программирование в примерах и задачах,
Изд. "Высшая школа" 1986.
2. Бурков В.Н., Кулжабаев Н.М. Активные системы и деловые игры–
Алматы:2000.
3. Бурков В.Н. Основы математической теории активных систем. М.: Наука,
1977.
4.Вентцель Е.С. Исследование операций. Задачи, принципы, методология –
Москва: Наука, 1988
5.Зуховицкий С.И. Авдеева Л.И. Линейное и выпуклое программирование,
Изд. "Наука". Москва 1967.
6.Кулжабаев Н.М. Исследование операции. Учебное пособие. –Алматы:РИК
КАО имени И.Алтынсарина,1999.
7.Кулжабаев Н.М. Муханова Г.С. Системный анализ и исследование
операции.
=e