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

132

МИНИМИЗАЦИЯ

ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

[Гл. V

здесь сохранены обозначения из задачи

(10.10).

Из

(2),

(3)

сле­

дуют равенства

(р*, Ли* — Ь) = 0, (р*, Ли* — Ь) = 0, (и*, с + Л*р* + Л V ) = 0.

(4).

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

Составим

функцию

Лагранжа

задачи

( 1) :

L(u,

X) — (с,

и) + (р,

Аи — b) -f (р,

Аи — Ь) =

= (с + Л*р Аг Л*р, и) — {Ь, р) — (£ 'р ).

Согласно теореме 10.4 точка и*

будет решением задачи

(1) тогда'

и только

тогда,

когда

функция

L(u,

Х)_

на

множестве

t/iXAj,

Ux— {и : u,'^ 0 ( i e / ) } >A i= {^ = (p .,

р)

: р ^ О }

имеет седло­

вую точку (и*, Я*), т. е.

(с, ы*) +

(ц,

Ли* — 6) +

(р,

Ли* — Ь)<[(с, и*) +

(р*,

Аи' — Ь) +

+ у , Ли* - Ъ) = (с + Л*р* + А 'у, и*) - (Ь, р*) - (Ь, р‘) <

<

(с +

Л*р* +

Л* р*.

и) -

(Ь,

р*) -

(5,

р*),

и 6 C/lt

Я 6 Ах

или в равносильном

виде:

для

некоторого X* =

(р*,

р*) £ Ль

(р — р*,

Ли’ — Ь) +

(р — р*,

Ли* — Ь) <

0

при всех

(р,

р) £ А1г

а для некоторого и* 6 U

(5>

(с + Л*р* + Л’ р’,

и — и*) >

0

при всех

ц £ t/1#

(6)

Нетрудно видеть, что соотношения

(5), (6) эквивалентны соотно­

шениям (2), (3). В самом деле, если верны

соотношения

(2), (3), то

из них, очевидно, [вытекают (5),

(6). Покажем обратное.

Пусть

име­

ют место соотношения

(5),

(6).

Тогда из

(5)

при р =

р*

получим

(р — р\

Ли* — 6 ) < 0 д л я

любого

р £ Ер,

что возможно

только

при

Ли* =_&. Далее,

при р =

р*

из

(5)

следует

(pj— р*. Ли* — Ь) < 0

при

всех р > 0,

что

возможно

тольно_при

Ли* < Ь-

В

самом

деле,

если

здесь^

взять р = (pi, - - ■,

pit—i,

pf,_

Рн-i , . . .

,

Ps), _то

получим

(рг — p‘) (Ли* — b )i< 0

при

всех

p( >

0,

откуда

(Ли* — 6); < 0,

i_— 1, 2 , . . . , [s. _ B ^частности, если

(Ли* — b)t <

0,

то

обязательно

р{ = 0,

поэтому

р[ (Ли* — b)i =

0

при всех

t =

1,2,

. . .

, s. Соотноше­

ния (2)

получены.

§ Щ

Элементы линейного

программирования

133

Аналогично условие

(6)

(с +

+

A* р*. и -

и*) =

£

(с +

А У + Л* p*)i («' -

иП +

ie/

+

£

(с + л V

+ л V

) £ (U1-

«'■') > о,

выполняющееся

при

всех

0

(ie / )

и

произвольных и1’(/’§£/),

приводит к соотношениям

(3).

Таким образом, существование сед­

ловой

точки функции

L (u t

X)

на

U1Х Л 1 эквивалентно

соотноше­

ниям

(2),

(3).

Отсюда

и из теоремы

10.4

следует справедливость

теоремы 1.

А

Оказывается,

задача (1) тесно связана со следующей задачей:

найти

min

[(6, р) +

(b,

р)],

Л =

{А< = (jx, р ): р >

0,

(й, ц)ел

(с

А*р + А" |л)(

0 (i 6 I ) ,

(с + А'р +

А* р)( = 0

(t ^ /)},

(7)

Т е о р е м а

2.

Задачи

(1) и (7) либо обе не имеют решения,

либо обе имеют,

решения, причем в последнем случае

(с,

u') =

- ( b ,

i o ,

(8)

где ц* — решение задачи

(1),

V = (р", р’) — решение, задачи (7).

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

Составим функцию Лагранжа для двой­

ственной задачи

Lx (X,

и) =

(Ь, р) +

(67 Й — J ]

(с + Л*р +

А* р)г —

щ/

—

£

u‘ (c +

А'р + А* р)г =

(b, р) +

(b,

р) —

‘ ф }

•***

— (и, с +

А*р + А*р) =

— L(u,

X),

чи лишь знаком. Согласно теореме 10.4 двойственная

задача (7)

имеет решение А,*— (р*,

р *)& А

тогда и только тогда,

когда функ­

ция Ь](Х, и) на A iX U i

имеет

седловую точку (X*, u *)^ A iX .U i:

Li(X *,u) s^.Li(X*, u*)^LLi(X, и*) при всех А,еЛь

Так как

134

МИНИМИЗАЦИЯ ФУНКЦИЯ МНОГИХ ПЕРЕМЕННЫХ

[Гл. 2

L(u,

Х) = — L\(X, и),

то из последних неравенств следует, что если

(А*,

и*) — седловая

точка

функции Li(X, а) на A iXf/i, то

(и*,

X*)

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

на U1Х Л 1 и наоборот. Таким обра­

зом,

функции L(u, X) и L\{X,

и) одновременно имеют седловую

точку или ее не имеют. Согласно теореме 10.4 это означает,

что

будут решениями' задач (1) и (7) соответственно тогда

и только

тогда, если выполняются соотношения

(2),

(3). Для

получения

равенства

(8)

теперь

достаточно

воспользоваться равенствами

(4). А

Т е о р е м а

3. Для того чтобы точки

и А *= (р *,

(х *)е Л

были решениями задач (1) и (7) соответственно, необходимо

и

достаточно, чтобы

Ф, u*) = - ( 6 ,

р*).

(8)

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

Необходимость

доказана

в

теореме

2.

Остается

доказать

достаточность.

Пусть для

некоторых

u *^ U

и

Я ,*= (р *,

р * ) е Л имеет место равенство

(8).

Тогда из условий, оп­

ределяющих U и Л,

имеем

(с, и) > — (Л*р + А* р, и) = — (Аи, р) — (Аи, р) >

>

— (6,

р) — (6,

р)

при всех

и в U,

X — (р,

р) £ Л.

(9)

В

частности, при X = X* — (р*,

р*)

с учетом

условия

(8)

отсюда

бу­

дем иметь

(с, и) > — (6,

р*) — (6,

р*) =

(с,

и’)

при всех

и 6 U, т.

е.

(с,

u*)s=m in(c,

и).

Аналогично

при

и =

и*

из (9)

и

(8)

следует

—

_

_

(ь ,

р) + (Ъ, р) >

— (с, и") =

(6,

р*) +

(6, _р*)

при всех

X=

(р, р) £ Л,

т.

е. (6, р’) -г Ф, Р”) =

min [(6,

р)

-f

ф,

р)]. А

ХбЛ

2.

Ниже будем рассматривать так называемую

каноническу

задачу линейного программирования: найти

min (с, и),

t/ =

{ « > 0 ,

Аи = 6},

(10)

ибУ

получающуюся

из

общей

задачи

(1)

при I

=

{ i : 1 <

i <

in},

А =

0,

6 = 0, s =

0. Заметим, что общая задача (1)

введением дополнитель­

ных переменных может быть сведена к канонической задаче. В

са­

мом деле,

положим v =

b —Аи,

и‘ =

х&f — wl, где £§Ё1/, wl =

max {0;

и‘} > 0 , wl — max (0; — и‘} > 0 ,

и

в

пространстве

переменных

v,

u‘ (i(zl), we,

w‘ ( i £ I )

рассмотрим задачу:

найти

§ Щ

Элементы

линейного

программирования

135

min ^

с;«' -г V

с, (w‘ — w1) )

£е/

lU l

при условиях

V> О, ие >

0 (i 6 I),

w1'> О, w* > О

( i £ I ) ,

^

AiU1

£

At (w!— а;1) = Ь,

iei

igi

^

ALu* +

^ Ai(w‘ — w‘~) + v =

b

записать в виде (10).

Остается заметить, что точка

v*, м‘’ (£6/),

w‘ , w£

(i& zl)

будет

решением задачи (11)

тогда и только тогда,

когда

точка

и* с координатами ие* (i 6 /)

и и * == w * — wl* (i £ I)

будет решением задачи (1), так что задачи

(1) и (11)

эквивалент­

ны.

min (с,

и); U = {u\u^> 0,

(12)

u£U

Исходная задача (1)

легко сводится к виду

(12), если ограниче­