Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

m in J{u ),

U =

{ u :u e U 1,g ( u ) ^ 0 ,g ( u )

=

0},

(1)

н6£/

где g =

(g i ,

g s), g =

(g , ,

g p). Условия g(u) = 0

называют огра­

ничениями типа равенств, условия g ( u ) ^ 0

— ограничениями типа

неравенств. Разумеется, условие «e£/i, возможно,

представимо

посредством

ограничений

указанных

типов,

однако

нам

будет

удобнее сохранить это условие именно в таком виде.

Введем переменные X =

(р, р),

р =

(р ^ . ■■, ps),

р =

(plt

•••, рД

и составим функцию:

L.(u, X) = J(u) +

(р, g(u)) + (р, g (и)),

называе­

мую функцией Лагранжа задачи (1).

О п р е д е л е н и е ! .

Точку

(и*, X*), и*

X' =

(р*, р*),

р* > 0

называют

седловой

точкой

функции

Лагранжа

L (и, X)

в

области

Ux X Alt

где A j = {X = (р, р ): р 6 Es, р >

0,

р 6 £р},

если

L (и*, X) <

L (и*, X*) <

L {и, X*) при всех

и 6 Ux,

А/6 Лх.

(2)

Т е о р е м а

1. Для того чтобы точка

и *^ 1 ),

была точкой

ми­

нимума функции /'(и) на

U,

достаточно

существования

точки

Я *еЛ ],

такой, чтобы пара

(а*,

X*) была седловой

точкой

Ь(и, 'Х)

в области б^ХЛ].

(и*,

.X*) eC /.XA i —

Д о к а з а т е л ь с т в о. По условию точка

седловая точка L(u, X), т. е.

J

(а*) +

(р, g (и*)) -г (Р, g {и)) < J

(и*)

+

(j?,

g (и*)) -f

-i- О1*, ё (“*)) < и .( и) +

ОЛ ё

(«))

-г (р\

ё («))

(3)

при всех

u(zU1 и X6 Аг.

Покажем,

что тогда и' £ U. Из

левого

не­

равенства

(3)

при р =

р*

имеем (р* — р, £ («'))

> 0 при любых р в Ер,

что возможно только

при g (u *)— 0. Далее,

при р =

р*

левое

нера­

венство

(3) дает

(р* — р, g (« *))> 0

при

всех р > 0 ,

что

возможно,

только

при g (и‘) <

0.

В

самом

деле,

если

здесь

взять

р =

(р*, .. .

. . . ,р£_ь

рг, p*+ i,

••■, р*),

то будем

иметь (р- — р]) g t (и’) > 0

при

всех р£ >

0,

откуда

g t (и*) < 0

(i =

1,

2,

. . . , s).

Таким

образом,

й* 6 U. Заметим,

что если g L(и*) <

0,

то обязательно р* = 0,

и поэтому

Pigi («*) = 0,

i = l , 2 ,

•••, s.

(4)

Отаода и из g (и*) =

0 следует

(р*>£(“*)) = о, ОЛ*(«’)) = о.

(5)

§ Ю]

Теорема Куна —

Таккера

123

Так

как

р * >

0,

то с учетом равенств

(5) из

правого

неравенства (3)

при любом u £ U будем иметь J (и*) <

J (и) +

(р*, g (и)) +

(р*, g (и)) <

< / ( « ),

т. е.

J

(и*) — inf J { u ) . ±

/ (и)

Теорема

1

доказана без каких-либо ограничений

на функцию

и

множества U,, U. Обратное

утверждение,

к

сожалению,

J ( u ) = — и, Ui = {и : и ^ О } ,

g (u ) — uz.

Здесь множество U

состоит

из одной точки и = 0 и

m in J (и) =

/(0) = 0 , и* =

0, но

функция

/.(»,

X) = —и + Хи2 при ы^О,

Х^О вообще не имеет

седловых точек

типа

(2). Однако теорему

1

можно

обратить, если

функция / (и)

О п р е д е л е н и е 2.

Множество. U = {и : u ^ U u g (u )^ .0}, где

U1

— выпуклое

множество в E m>

gi(u) — выпуклые функции на

U i( i= l, 2

s),

назовем регулярным,

если для любого Л = р ^ 0 ,

Х=£0 существует точка n et/ i,

такая, что

(X, g (v))< C 0.

Для регулярности множества

U

достаточно

существования

точки а е У i,

для которой g (o )< 0

(условие Слейтера). Множество

U

будет

регулярным

и

_тогда,

когда

существуют

точки

щ ^ и (,t = l,

. . ,

s), такие, что g i{u i)< 0 ,

i.= 1,

.. , s. В этом случае

точка

удовлетворяет

неравенству g(v}<^0.

Т е о р е м а

2

(теорема Куна

— Таккера). Пусть множество

U = {u :u ^ .U I, £( н)=^0}, где U: выпукло,

gi(u) — выпуклые функ­

ции

на U \{i=l,

2,.-., s ),

удовлетворяет

условию

регулярности,

и

J (и) является выпуклой

на

U\.

Тогда,

для

того

чтобы

в

точке

u *^ U 1 достигался

минимум функции J (и)

на множестве

U,

необ­

ходимо и достаточно существования точки X* ^ 0 ,

такой, что _пар а

(и*, X*) образует

седловую точку функцииТ(цД) = J(u )-\ -(X ,g(u ))

в области f/iXAi, где А\ = {X :X ^ E S, Х ^ 0 }.

Д о к а з а т е л ь с т в о .

Достаточность

доказана в теореме

1.

Докажем необходимость. Пусть и*

— точка минимума J (и)

на

U.

Покажем, что тогда функция L(u,

X)

в области П1Х Л 1 имеет сед­

ловую точку

(и*, Я*). Для этого в s +

1-мерном пространстве пере­

менных а = {1 о, £) = (!о, £1, . . ,

Is)

введем

два

множества

А

и

В

следующим образом:

§ Щ

Теорема Куна — Танкера

125

В частности, при

и = и"

отсюда следует, что 0 <

(A,*, g (и")).

Но

А .*>0, g («*)_< О,

поэтому

возможно лишь равенство

(A,*, g (и*)) =

0.

L (и, А,*) = У(и) + (Г , g («)) >

J («*) = J (и*) + (Г , g (и')) =

= L(u\ Г ) > J («*) +

(к, g («*)) =

L{u\ к)

при всех u^U lt А, > 0 . ^

На примере простой задачи

min (— и),

U = { u :u ^ s 0, «2.^ 0 }

£-i — (cil>

' 1■* ^im)

1 j 2, •■■ ,p)

Пусть П — множество

всех

тех

векторов 1 =

1т) ^ Е т, ко­

торые удовлетворяют условиям

т

(С;,/) =

£

С^

=

0

(г =

1,

2, . . .

, р),

/=1

т

(°t, 1) ■=

£

cijlj < 0

(t =

1,

2, . . .

, п ).

i=i

Тогда для того, чтобы

некоторый

вектор

у — (у\,. . . , ут) удовле­

творял неравенству

т

(у, 0 =

£

yili ^

0

при всех

(8)

£=1

р

п _____

( 9 )