книги из ГПНТБ / Васильев Ф.П. Лекции по методам решения экстремальных задач

140

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

Покажем, что векторы \Alt А2, . . .

,

Ак линейно независимы.

Пусть

вопреки утверждению существует

k

кой,

что V z£At= Az — 0.

Возьмем

i=l

€ Ет. Так

как и^> 0,

то

при достаточно малых

е > 0

будем иметь Mi^O, ы2^ 0 , кроме того, Ащ = Ь, Au2 — b, т. е.

р ^ к , и, вычеркнув из матрицы А

р—к строк, линейно выражаю-

щиеся через остальные строки А,

получим искомую квадратную

невырожденную матрицу порядка

к Х к и соответствующий век­

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

Пусть

точка

u £ U

и

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

усло­

вию (15).

Пусть и =

аых + (1 — а)ы 2

при

некоторых их,

u ^ U и

0 < а < < 1 . Покажем,

что

такое

представление

и

возможно

только

при ы = ы1 = ы2. В

самом

деле,

если ]'ф]'г,

r =

1,

2, . . .

,

k,

то из

0 < а < 1 ,

ы{ > 0 ,

и'2 > 0

имеем

0 = и' =

аи[ + (1 — а)

>

0,

что

возможно только при и[ — и!2== 0

(/Ф j r,

г — 1,

2 ..........

k).

Тогда

из Aui = b

следует,

что Вщ = Ь ,

где и,

.

| ( t = l ,

2).

Однако

u’k /

|В |=/=0,

поэтому их =

«а = и> а

тогда

и1 =

ий — и.

Следовательно,

и — угловая точка U. А

где а — £-тая компонента

вектора

ua,k ( £ > р ) .

Так

как

ц > 0 ,

то

найдется

а о> 0 , такое,

что «a,ft > 0

при всех

а, 0 <

а <

а 0.

Кроме

того,

р

_

_

_

Aua,k = ^

Л; (и — аБ-1 Ak)i +

Akа =

В(и-^- аБ -1 ЛА) +

Ака

= Ви =

Ь-

i= 1

при всех

а , поэтому ыа>й £ U при 0 •< а < а 0.

Далее;

(с, иа>к) = (с, и

а Б - 1 Ак) + а ск = (с, и) — а [(с, Б“ >Л*) — c j .

Обозначим

ДА= (с, Б-1 Лй) — ск\ тогда (с, wa.fc) = (с,

и) — аДй (k —

= р +

1,

. . . , /п).

Величины Дй имеют смысл и при £ = 1 , 2 , . . . ,

р,.

при этом

согласно определению

обратной матрицы В-1 ЛА=

ек, и по­

этому

Дй =

(с, Б-> Л*) — ск =

(с,

ёА) — ск = 0 (£ = 1, 2, . . .

, р). В за­

висимости от знаков величин ДА, (Б-1 Ak)t возникают три

возможно­

сти.

I.

Все

величины Д^^О

(к —1, 2, . .. ,т ). В этом

случае,

ока­

зывается,

и* —и является

решением задачи (10). В

самом

деле,,

возьмем К * = — (В~1)*с. Тогда

0 >

Д* = (с, Б - 1Ak) — ск = ((Б -1)' с, Ак) — ок = — (Г ,

Ак) —

— ck( k =

1, ... , т),

что равносильно неравенству c - f

Л 1 * > 0. Далее,

( С , U a ,k ) 1«=о =

(С, И)

=

(С,

А - 1 £ ) =

( ( Б - ' ) * с ,

6 ) =

-

( b ,

Г ) .

Таким

образом, Я*— решение двойственной задачи

(13),

и в- силу

тео­

ремы 4

тогда и" = и — решение задачи

(10).

II.

Найдется такой

номер £ > р ,

что Д * > 0 ,

В - 1 ЛА<

0

(напо­

минаем, что Ак = 0 при£ =

1 . . . . ,

р). Тогда задача (10) не имеет решения.

В самом деле, в этом случае «со->

0,

Аиа,к =

Ь,

т. е.

ua,k(:U

при

всех а > 0 ,

А тогда (с,

иа й) = ( с ,

и) — аДй-> — оо при

a -» -j-o o ,

и-

inf (с, и) =

— оо.

иес/

III. Найдутся

такие

£ > р

и

i^ p , что

Дй> 0 ,

(В~1Ак) ,->0..

В этом случае делается

итерационный шаг — переходят к следую­

щей угловой точке

ыао,

а,

где

a =

a0 =

min JE L Q l

,

4

=

{ i : l < i < p ,

(Б~' Л*)£> 0 }^ =

0 ^

£6/ft(B-1^ )I.

Так как B~l b = u^> 0,

то a 0)> 0 .

Покажем, что «<*„,;•. 6

Посколь­

ку Aua,k =

b при

всех

а,,

то

достаточно установить,

что

О»

§ Щ

Элементы

линейного

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

143

или (и — а 0В-1 Аа)£ > 0 ,

р. Это очевидно для тех

i,

для

которых

<

0.

Пусть

(B~l Аа)£ > 0, т.

е.

i 6 I k- Тогда

Q < a 0 <

{В ,

Ь)‘

= -----r -----.

или и‘ — а 0(В-1 Aft)£ >

0

(Br'Afr

(B~l А&

при всех

i 6 /й. Таким образом,

uaoik 6 U,

Покажем,

что иа„,к— угловая точка U. Пусть минимум

в опре­

делении

а 0

достигается при некотором t = s 6 Д :

(В-16)£

(В -1 6),

^

а

( 16)

(В-1

'

‘

Тогда

Ua0, k = us— а 0 (.В

Ak)s =

(В-1 6), — а 0 (В~' Ak)s = 0.

В

матри­

це В =

( А х ,

А2,

,

Ар)

выбросим столбец A s

и дополним

столбцом

АЙ;Тновую матрицу обозначим через С = (Ах, . . . ,

As_ ь

А*+1, . . .

, Ар,

Afe),

кроме

того,

вектор-столбец с

координатами

ц„,, . . .

,

,

ц ^ 1, . . .

, ы£0, гД, =

а 0

обозначим через иа„,к. Будем иметь

~

р

«оAft —

A;«a0 + ®oA* — В (u — a 0B

,CUa0,k=

A;

+

1 Aa)

i= I,

i=/-s

L=1

Cz =

^

ZjAj +

z* Ak = 0.

Так как

•i=l,

Ak = B(B~'A k) = £

Д ( В - ‘ Аа)£,

Cz —

^

z£A£- f 2fc ^

А£ (В

1Aft)£ —

[z£ -(- (В 1 Ak)t zk] A£ +

t = l , l ^ b s

t = 1

£ = 1 , i * r S

+

zftAs (B~1Aft)s = 0,

Из

линейной независимости

Ax,

A2, . . .

, Ap тогда следует, что

zc +

(B—1 Ak)i Zk — 0 (i =

1,

2,

. . .

,

p,

i

s),

zk (B—1 Aft)s = 0.

По

(B_1Aa)s> 0 по определению

s 6 / fe,

поэтому

zk = 0, а тогда все

z£ = 0

(t =

1,

. . . , p, i=^=s),

t .

e.

z =

0.

Следовательно,

|C|=^0,

>Cua0,fe = й.

В

силу теоремы

7

точка

ыа„,ь

является угловой

для 17.

144

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

[Гл. I

При этом

(с, Ua0ife) =

(с,

и) — а 0ДА<

(с, и) = (с,

и), т.

е. значение

функции (с, и) строго уменьшилось.

Тем самым

описан

один итера*

ционный шаг симплекс-метода.

По условию задача

(10) невырожденная, поэтому число поло­

жительных компонент у вектора иаа,к равно

р. Поскольку т — р ну­

левых координат у вектора

ua„ife

известны:

= иРс£1= . . . = и*~1=

= Ua^"1 =

•••=

Ua„ =

о,

ТО

Все

ОСТЭЛЬНЫе

координаты

иа‘ 0= (и —

— aQB~l Ak){ (i =

1, . . .

, р,

i=/=s),

Uas = a0

будут

положительными.

жет быть равной нулю координата (B~lb )s= u s. Таким

образом, в

вырожденных задачах возможно зацикливание,

когда

значение

функции (с, и) при переходе от одной угловой

точки

к другой

Л = b,

uik =

(В - 1 Ak)h

i =

1, 2,

,

р, k = 0,

1, . . .

,

т\.

_

Р

“о/ = Л/ = (с , В ~1А,) — с,- =

£

Cjiii,

Cj,

/ =

1,

2,

. . . ,

т\

£ = 1

«00 =

(С. «)•

Параметры

щ,

назовем параметрами

итерации

для

угловой

точ­

§ Щ

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

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

14Т

Рассмотрим

такую

вспомогательную

задачу

линейного

про­

граммирования: найти

т ш

y/) ’ 117 =

|® =

^ ^ € £ т +р,

« > 0 ,

п >

0,

Au + v = b ^ .

jrn ( E

w

Ь ^ .О,

(19)

Без ограничения общности можем считать, что

ибо

в

про­

тивном случае соответствующую строчку ограничений

(Au)i = bi

мы бы умножили на

(— 1). Для задачи (19)

можно сразу указать

угловую

точку.

Это

будет точка

(

) (см. теорему 7)

и, следова-

тельно, для решения задачи

(19)

\°/

симплекс-ме­

можно применять

тод

(или его модификации в случае вырожденной задачи) и найти

ее решение.

Т е о р е м а

8.

Пусть

— решение задачи

(19),

пусть

2

- “

(5

: 4

t=i

i=i

Тогда если ф* =

0,

то и* — угловая точка множества U\ если

ф*]> 0„

о U = 0

и задача

(10)

становится тривиальной.

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

Прежде

всего ясно,

что задача

(19)

имеет

W Ф 0

р

г/ > 0

на W. Да-

решение,

так как

и линейная функция

^

лее,

поскольку

эта

задача

решается

i=l

то

симплекс-методом,

Ц 9

\

точка множества

W. В частности,

если ф* =

0, то

ф 1— угловая

и' = 0 и ( о ) — Угловая

точка

Очевидно, тогда

и* — угловая

точка U. Если же

ф *> 0 , то [U — пустое множество. В

самом

деле,

если бы

существовала точка и 6 U, то

^ q j 6 W. Но тогда |

^

решение задачи

(19)

и ф* = 0 — противоречие.

Упражнения. 1. Выяснить геометрический смысл задач линей­

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

взяв в задачах (10) и

(12) т = 2,

т = 3.

2.

На

велосипедном

заводе

выпускают

гоночные и дорожн

3. В

пунктах

А и В расположены

кирпичные

заводы, а в

пунктах

С и Д — карьеры, снабжающие

их

песком. Ежесуточно

заводу А нужно 40 т песка, заводу В — 50 т,

а карьер С ежесуточ­

но добывает

70

т песка, карьер Д — 30

т.

Стоимость перевозки

тонны песка

с карьера

С на завод А равна 2 руб., на завод. В —

6 руб., с

карьера

Д на

завод А — 5 руб.,

на завод

В — 5 руб.

ми

1— 3.

5.

Для

того

чтобы задача

(1)

(и, следовательно, двойствен­

ная

задача

(7))

имела решение, необходимо и достаточно, чтобы

1 ! ф 0

и (с, и) ограничена снизу на

U. Доказать.

6.

Для

того

чтобы задача

(1)

(и, следовательно, задача (7))

имела

решение,

необходимо и

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

11ф ф , А ф ф .

Доказать.

(с,

и) =

и3— u4+ u 5— ы6

7.

Решить задачу min

при условиях

и1ф и 3— 2u4— 3w5+ 4 u 6 = 0,

и2+ 4 и 3— За4— 2u5+ u 6 = 0,

и3+ и4 + и5+

+ и6 + и7 = 1,

0, /=1, 2 . . . , 7 .

Показать, что в этой задаче мож­

ганизовать перебор угловых точек,

соответствующий

перебору

базисных столбцов в следующем порядке:

(А3, Л2, Л7) —>(Л3,

Л4, Л7)

(Л5,

At ,

Л7) —»-(ЛБ, А0,

Л7) —>•

Ав,

Л7) —^(Лх,

Аг,

Л7)

(Л3, Л2, Л7).