Файл: Говар В.М. Математическое программирование учеб. пособие.pdf

-

19

-

Теорема

I .

Множество всех

решений

(планов)

задачи линейного програм­

мирования

является выпуклым.

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

•Множество всех

решений

системы ограничений

АХ = В обозначим

через

W

. Из этого

множества

решений выберем любые

X p X g , . . Д ^

(2.6),

где X . É W J

Х~2 £ Ѵ У , , . . . | X n é w

•

Составим из значений

(2.6)

выпуклую линейную

комбинацию (2.7)

(2.7)

L ^ j + J ^ 2 Х2 + . . .

+ f L X

L +

lo

Х П

= Х '

где

все

0

<•= .^- é

I

и

Z

Ь

- 1 .

и докажем,

что оначтакже принадлежит множеству W •

Действительно,

значения

Хр

Xg,

,

являясь

решени­

ями

системы АХ = В,

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

ему и,

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

это можно

записать

в виде (2.8).

(2.8)

A Xj- = В,

А%2 = В,

. . . ,

AXn =

В

Покажем, что выпуклая линейная комбинация

(2.7)

также удов­

летворяет

решению системы АХ = В. Для этого, подставляя

выраже­

ние

л из

(2.7) в

(2 . 2 1 ),

получим (2.9)

АХ = A (J...X + І - 2 Х 2 + ' - '

+U

X n

)

=,L( A 1г

+JL2 .AX2 + . . .

+ ^ А Х П

= J . . B +^2-В

+і-п-&>

= (.L+.J-2 +

) ß

= ß

Тем

самым теорема

доказана.

Так как выпуклое множество задачи

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

определяется конечной системой

линейных ограничений

(2.2) и

(2.3),

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

или выпуклой

много­

гранной

областью,

уходящей в бесконечность, или пустым

множеством,

то

есть

множеством,

не имеющим решения. В первом случае

задача

ства допустимых решений ( 2 . 2 ' ) ;

при

этом при решении на максимум

выпуклое множество

долине

быть

ограничено сверху, а при решении

на минимум - снизу.

Если

функция дели принимает экстремальные

значения более, чем в одной угловой

течке, то она достигает та­

кого же значения на всем

множестве,

являющейся выпуклей линейной

комбинацией этих угловых

точек.

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

Для определенности

рассмотрим

случаи максимизации функции

"Н". Пусть Хр Z^,

. . . s

-

совокупность всех

угловых

точек вы­

пуклого множества

допустимых решений

( 2 . 2 ' ) .

Обозначим через Х0

точку, в которой функция цели принимает максимальное значение в

данном мноЕествѳ \ у • Тогда

[_ (

% ; -

M и для всех

XÊW

име­

ет место следующее

неравенство

[_

(.jQ)

^ U ( X . ) :

Приступим к доказательству

первой

части теоремы от против-

- ного,

то есть допустим,

что

функция

цели достигает

своего макси­

мума

не в угловой

точке.

При таком допущении точку

Х0

можно

пред­

ыого ыноаества

У/ ,

ю- есть

(2.10)

х 0

= <Ц. х х

+ hzh•+

••• * J ^ L X " L *

•••

+ < Ц Х ? '

где

• Ь

^

0 .и

S

<Ы

=

I .

Тогда'значение

функции

цели в точке Хв

будет

( 2 Л і )

L с ѵ

= Ь ч і - А

*JLi 2h *

•••

+ < Ц Х г

)

(2.12) L e V

=„_,-_. о - )

+j_/2- L о у

+ - + й

і

а г

) .

Если

функция цели

L (X)

принимает

в точке

XQ

максимальное

значение,

то,

считая L (Х',<)

наибольшим

значением

среди

і_ ( X' L )«

где 1=1;

2,

Z .

а к £ і,

. находим •>

(2.1 3) L ( J Ç > ^ j - , * L ( Хк ) + J_г* L. ( Х!к ) •+ . . . + j L r

Ц £ К ) =

= a , + J L , 2 +

+

J-? > L ( ) C K ) -

L ( X K ) .

то

есть

(2.14)

L ( X 0 )

- е | _ ( Х * )

или

(2.1b)

L ( X K )

^

U -

Мы пришли к противоречию. Следовательно,

точка

Х 0

монет

быть только лишь угловой точкой

выпуклого множества

решений W ,

то

есть

(2.16)

L

( Х ^ )

= L ( X K > = M <

Таким

образом

существует

по крайней

мере

одна угловая

точ­

ка y._Y . й

которой

функция

цели достигает

своего

максимума.

Докаяем

теперь вторую часть

теоремы.

Пусть

функция цели

L

( X

)

достигает

максимума

в точках

Хт_, Х^, ••• xj>

•* r i

- e

l - é z

"и пусть

(2.17)

L

( X ,

)

=

L O Ç )

= •••= L

CX.)

=М

Составим выпуклую линейную комбинацию этих угловых точек

(2.18) X =<цх, + і . - 2*^2 +

••• +

і-е

х е .

гдеЬ

à О И

_

"-I

тогда

L-I

L

(2.19)

L ( . x ) = і - с ц - х ; +

J - 2

X 2 + - - -

+

JUgXe

)

=

= ( J - i

+ i , 2 +

••• + i - e

>

* M

« м ~

Теорема для случая максимизации функции целя доказана.Анало­

гично

можно провести

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

и для случая минимизации функ­

ции

цели.

- 22 -

Согласно этой теореме нахождение оптимального решения

(плана)

можно ограничить перео'ором лишь конечного числа угловых

точек (вершин) выпуклого

многогранника

допускаемых решении.

(

Теорема

3.

Для

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

X = ( х р Х 2 ,

. . . ,х-,. , . 0 , 0 , . . . ,0) . ,

( 2 . 2 0 )

Xj

*

ï j

+ х 2 * l u

+ ...

+ х.:

*

I z

= в

и

( 2 . 2 1 )

х-.

*

0 ,

где

г

= 1

, 2 ,

,

с

)

Из этои теоремы вытекает, что число базисных решений (опор­

ных планов)

задачи

линейного

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

равно числу вершин

вует

и такая, в которой функция

цели достигает своего

оптимального

значения (или максимального, или минимального).

Длн получения оптимума нужно исследовать значения функции

цели лишь в вершинах выпуклого многогранника решений,

тоесть

только те опорные .планы, каждый

из которых определяется

системой

£

линейно-независимых лекторов.

В рассматриваемой системе

( 2 . 2 "

) из И векторов

содержится

не более С^ систем,каждая из которых

состоит

из ^ линейно-незави­

симых векгоров,го есть число опорных

планов не превышает G

В практических задачах значения

П и Z

таковые,что

яв­