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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 243

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

136 МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [Гл. 2

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

например, в работах [54, 74, 89, 114, 116, 118, 132— 134, 149, 219; 220, 226, 232, 235, 256, 257]. При изложении симплекс-метода для

задачи

(10)

будем следовать

схеме,

принятой в

работе [134].

3. Выпишем двойственную к (10)

задачу: найти

 

 

 

 

 

min(&, К),

А =

{ Х :К е Е р,

с +

А,Х >

0}

 

 

(13)

и переформулируем теоремы

1— 3 применительно к задачам

(10),

(13).

 

 

 

 

 

 

 

 

 

и *^ Е т была

 

 

 

Т е о р е м а

4.

Для

того чтобы точка

 

решением

задачи

(10),

необходимо

и

 

достаточно

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

точки

Х *^ Е Р, такой, что

 

 

 

 

 

 

 

 

 

 

 

 

« * > 0 ,

Au* = b,

с +

Л * Г > 0,

«*'*{с +

Л‘Г ) ; = 0,

t =

l , . . . , /я.

Задачи (10) и (13) либо обе не имеют решения,

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

решения, причем для того, чтобы точки

 

 

и Я ,*еА

были ре­

шениями соответственно задач (10) и (13), необходимо

и доста­

точно,

чтобы

(с,

и*) = — (b, X*).

 

 

 

 

 

 

 

 

В

задачах

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

важное

значение

имеет понятие угловой

(или крайней)

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

 

 

О п р е д е л е н и е

1. Точка

а множества

А а Е п

называется

угловой (или крайней) точкой этого множества, если

представле­

ние a = a a i + ( l — а ) а 2 при щ,

а2^ А и 0 < а < 1

возможно лишь при

а=а\ — а2. Иначе

говоря,

в Л

не существуют

точек а ь

а2, а\ ф а2,

при которых представление a = a a i + ( l — а ) а 2 возможно для

како­

го-либо а, 0 < а < 1 . Геометрически это означает, что угловая точка

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

Т е о р е м а

5. Всякое

выпуклое замкнутое ограниченное мно­

жество Л с £ „

имеет хотя

бы одну угловую точку, и любая точка

5 &Л может быть представлена в виде выпуклой линейной комби­

нации конечного числа угловых точек

а\, а 2, . . . ,ah множества А,

т. е.

 

 

 

 

 

 

 

 

 

к

 

 

к

 

 

a =

£

a tah аг >

0,

t = l , 2,

. . . , & , £

a t= 1.

(14)

 

f=i

 

 

f=i

 

 

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

проводится

с помощью

индукции

по

размерности

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

Е п, в котором задано

множество

А.

Если-/г=1,

то А есть отрезок и справедливость теоремы очевидна.

§ Щ

Элементы линейного программирования

137

Пусть теорема верна для всех выпуклых замкнутых ограниченных

множеств

в

пространстве Е п^ ( п ^ 2 ) .

Пусть

А — выпуклое

замкнутое

ограниченное множество в Е п.

Возьмем какую-либо

граничную точку а множества А и построим в этой точке

гипер­

плоскость

(с,

а— л )= 0 , с Ф 0, опорную

к множеству

А, т. е.

(с, а ) ^ ( с ,

а ) —а при всех а^.А. Общие

точки

множества А и

этой гиперплоскости обозначим через А0. Очевидно, Ло — выпук­

лое замкнутое ограниченное множество,

и,

кроме того, А0

может

быть помещено в некоторое евклидово

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

Е п- £.

По

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

угловые

точки

a it . . .

,ад

• k

 

 

 

 

к

 

множества А0 и числа а £> 0 , ^

а г =

1,

такие,

что а =

^

а £а£.

i =

i

 

 

 

i =

i

 

Остается лишь показать, что точки а\, а2, . . . ,аи являются угловы­

ми

и

для

множества

А.

Пусть а£ = а а '+ ( 1 — а )а " ,

а',

а" ^ А ,

0 < ’о < 1 .

Покажем,

что такое представление возможно только при

а '= а " = а £. Так как

(с, а ')^ .(с ,

а ), (с, а " ')^ (с , а ), (с, а£) =

(с, а ),

то

 

 

 

 

 

 

 

 

 

 

 

(с, щ) = а (с, а') + (1 — а) (с, а") > (с, а) = (с, а£),

 

что возможно только при

(с,

а') = (с, а".) = (с, а ), т. е.

а',

а " е Л 0.

Но

йг — угловая точка

А0,

поэтому представление

щ = а а 'ф

+ (1— а)а",

а', а " ^ А 0, 0 < а < 1

возможно только при

а£= а /= а " .

Тем

самым

доказано существование угловых точек множества А

и, кроме того, получено представление (14) для любой граничной точки множества А.

Пусть теперь а — внутренняя точка множества А. Через точ­ ку а проведем какую-либо прямую L. Пересечение Ь[)А есть отре­

зок с концами Ъ1, Ь2, принадлежащими границе множества

А,

причем для некоторого а, 0 < а < 1 имеем: а = а & 1+ (1 — а )Ь2.

В

силу доказанного для граничных точек имеет место представле­

ние (14). Поэтому найдутся

угловые точки aiU ai2, . . . ,

мно­

жества А и положительные числа а£1.......... aikl,

такие,

что Ь[ = £ a£/a£/,

i — 1, 2.

Тогда

 

/=i

 

 

 

_

fti

к,

 

a = Y> a a i/aи + £ (! — «) °2ia%-

 

 

/=i

j=i

 

Приведя подобные члены и выбрасывая нулевые слагаемые, при­ дем к представлению (14). ^

138

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

[Гл. 2

Т е о р е м а 6. Если задача (10) имеет решение, то найдется угловая точка множества U, также являющаяся решением •этой задачи.

Д о к а з а т е л ь с т в о . Пусть и* — решение задачи (10). Возьмем множества

 

 

 

т

 

 

 

 

 

 

т

 

 

 

А = | и : « > 0,

£

и‘ < М | и В — |u:u >

0,

^ и 1 = М},

 

 

 

i=l

 

 

 

 

 

 

 

 

где М = 1 -f

ш

 

 

 

множества Ап В непусты, ограни-

w£*]> 0.

Очевидно,

 

i=I

 

 

 

и* € А,

и* £ В . Тогда пересечение

чены, выпуклы, замкнуты, причем

U П А является ограниченным

выпуклым

замкнутым

множеством и

u*(zU[}A . По теореме 5

 

 

 

 

 

 

 

 

к

тогда

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

а £а£,

где

а£— угловые точки

множества

U [\ A,

а £> 0 ( £ = 1 ,

i=i

2.......... k),

k

a ( = 1. Так как a£ 6 U, то

 

 

 

 

 

 

 

 

^

 

 

 

 

 

 

 

 

i=i

 

 

 

 

 

 

 

 

 

 

 

 

 

(с,

а£) > (с,

и*) = inf (с,

и) (£ =

1, 2,

. . .

,

k).

 

 

 

 

 

 

и

 

 

 

 

 

 

 

Умножим эти неравенства на а г> 0

и сложим. Будем иметь

 

(с,

и*) <

к

 

 

к

 

 

(с > «*)>

 

 

£

а £(с,

а£) =

(с, £

а л ) =

 

 

 

 

£=1

 

 

£=1

 

 

 

 

 

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

при (с, и’) = (с,

аг)

(t =

1,

2, . . .

, k). Таким

образом, точки alt a,, . . . , ak также являются решением задачи (10).

Остается показать, что среди этих точек

ах, ■..

, ак хотя бы

одна

является угловой точкой множества U.

 

 

 

Заметим,

что среди точек аь . . . ,ай найдется точка щ £ В ,

ибо

 

 

k

 

 

 

в противном

случае

ы‘ = ^ а ;а £6 5 . Докажем, что такая точка

a,i — угловая

 

£ = 1

пусть

a£= a u i + ( l — a)u 2,

точка U. В самом деле,

ии u2^ U , 0 < a < l .

Покажем, что такое

представление, возможно

лишь при U\ = u2= ai. Для этого возьмем точки w; = а г + у (% — а,-) =

= уи ;+ ( 1 — у )°г(/ = 1,2), принадлежащие U

при всех у,

Так как щ ^е В, т о

можем выбрать у, 0 < у < ;1 столь малым, чтобы

т

 

 

^ w lj< iM . Таким

образом, wu rej2<=UHA.

Кроме того, так как

£=1

a£ = a u i+ ( l — а)ы 2, 0 < а < 1 , то простые выкладки показывают, что a{=aa>i + ( l — а)ш 2, 0 < а < 1 . Однако а£—угловая точка множества

§

I t ]

 

Элементы линейного программирования

139

UflA,

wi, w2eU [}A ,

поэтому последнее представление для щ воз­

можно лишь при a,i=Wi =

w2. А тогда щ = и1= и2. Таким

образом,

flj

—

угловая точка

U и

(с, a t) = inf (с,

и).

 

 

 

 

 

uBCJ

 

 

 

Как видим, угловые .точки в задаче

(10) играют важную роль.

В связи с этим полезно иметь простой алгебраический критерий

для угловой точки множества U задачи (10).

 

 

Т е о р е м а

7. Для того чтобы точка и ф 0, u ^ U была угловой

точкой множества U, необходимо и достаточно,

чтобы:

1) сущест­

вовали невырожденная квадратная матрица

 

 

<*ith

bit

 

 

••• а и к

 

 

 

bi,

.такие,

что для

 

и вектор Ь =

aikh • ■ a ‘kfk

1

Л*’ 1

Ф

и =

и‘ь

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

 

 

 

 

 

В й = Ъ ,

\В\фО,

 

(15)

где

а,, — элементы матрицы

A, b i— координаты

вектора

6;

2)

координаты вектора и, не входящие в

й, заведомо

равны, нулю

(заметим, что если u = 0 ^ U , то

и = 0 —

всегда угловая точка

U).

Столбцы матрицы А, входящие в матрицу В, называются базисом угловой точки и.

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

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

Пусть

и ф 0 —

угловая точка

множества U. Пусть

( A u ) i= b i( i= l,. . . ,р),

ш > 0 (/ = 1, . . .

,/с), из—0

( / = к + 1 , . . . ,т )

(этого

всегда

можно

добиться, перенумеровав при необходимости координаты векторов и и Аи). Обозначим

 

ап , . . . ,

(гы'

 

 

А =

 

 

 

\api> ••■ >

aPk->

 

 

*1£

/

гД

Ai —

(* = 1, 2...........k),

-и — |

• | > 0 .

ик

Смотрите также файлы