Файл: Математическое программирование и производственные задачи..pdf

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

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

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

Добавлен: 30.10.2024

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

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

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

сзойстзам обычных фейеровских последовательностей, отра-

жаются в следующей лемме.

 

 

Лемма 7.1. Если последовательность

{л'^(«>)}

является

случайной фейеровской,

то

 

 

а) множество предельных точек

непусто почти

для каждого «>;

 

 

 

б)

если л-'(о>) и

—какие-либо

предельные точки

(д:*(<о)}

для некоторого

и>, нб'принадлежащие C(D),

то С(О)

лежит э плоскости, являющейся геометрическим местом то­

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

и х"(ш).

 

 

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

Утверждение

этого

пункта непо­

средственно следует из того, что при любом

y£D последо­

вательность { |у—л'* ||2},

согласно [30],

сходится почти для

каждого «>.

 

 

 

!,6) рассмотрим некоторую реализацию {л^(ш)| случай­

ной последовательности (х^); пусть jc'(w) и х"(ш) какие-ли­

бо две предельные точки данной реализации,

не принадле­

жащие C(D ). Так

как { |у—х Л(о>) |2)

сходится

к некоторой

величине, то для

произвольного y£C(D) все

предельные

точки ( x k( о) )

)

будут

лежать на

сфере

с

радиусом1

inf |у—x k(m) (12.

Последнее

возможно тогда, когда

у лежит

в некоторой плоскости, являющейся геометрическим местом точек, равно удаленных от х'(т) и л:"(«).

Лемма

доказана.

последовательность \xk \ является

Следствие 1. Если

случайной фейеровской относительно множества C(D), име­

ющего размерность я, то

|*(0))1

имеет единственную пре­

дельную точку почти для каждого «г

 

Следствие 2. Если предельная точка х"(ш)

последова­

тельности

{*(«))} для некоторого

м принадлежит

C(D), то

х"(ш) является единственной предельной точкой для данно­

го <«.

 

 

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

Случайную последовательность то­

чек (х*|, к — 0 , 1 , . .

. назовем случайной квазифейеров-

ской относительно множества D, если

Щ II У—х^+11|*/х°, х

. . ., х к

|y - x k |*+>*, k = 0 , 1......

где "

 

 

38


 

 

• ^/.A<oo,

y£D.

 

 

 

* - о

 

 

Если

рассмотреть zk = |у - х к |2 + £

>•*, то из послед-

 

 

 

А* —I

 

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

любом

y£D последова­

тельность

{г/;}

является полумартннгалом.

Поэтому почти

для каждого ю

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

{ |у —х к |*) сходится.

Следовательно, для случайных квазифейеровских последова­

тельностей справедливы все перечисленные свойства

фейе-

ровских

последовательностей.

 

 

1°.

Стохастический

аналог

Чебышевской задачи.

Пусть имеется совокупность случайных величин

 

 

П

 

 

 

f t(x, ш ) = 2

ац(ш)Х;

 

 

 

)-•

 

 

зависящих от t и x = (Xj,

д*2, . . .,

х п). Рассмотрим

сле­

дующую задачу.

 

 

 

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

F (x) = M(ma\\ft(x, ш)|)

t

при x^D, где D выпуклое замкнутое множество Еп. Обозначим через к(х) оператор проектирования, определен­ ный на О, такой, что

|у — ч'(л') ||2 <: |у - х ||2

для любого y£D . Пусть ш°, о»1, со3, . . . последовательность независимых испытаний. Определим случайную последова­ тельность (xs| по формуле

 

,х5+1=т(л:* - iv f),

s= 0,

1, . . .

(7.1)

Здесь х°

произвольная точка, &s

величина

шага, а вектор

'fls = (riv

’ll.

• • •.

такой,

что

 

 

i

p i

x j - b t A

U)S) = £

a t s / ( m S ) x j -

=

 

=* I//,(**.

“>s)| = max |/,(**, u>s)|.

 

39



Теорема 7.1. Если

|r f |*^ Л < оо ,

 

 

 

 

 

Ps> 0,

2 Р* <

«»,

 

 

 

 

 

 

 

 

s~-1

 

 

 

 

 

ТО

 

 

 

 

 

 

 

 

 

 

а) последовательность |х4),

полученная по формулам

(7.1),

является квазифейеровской;

 

 

 

 

б) |х4)

сходится с

вероятностью,

равной

единице, к

точке

минимума функции F (x ),

если 2 fo ^ 00-

(7.2)

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

 

 

J—1

 

 

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

точек ми­

нимума функции F (x ).

Очевидно,

что

для любого х *£ М ,

имеем

 

 

 

 

 

 

 

 

 

 

 

 

|х *

х 4+1 |8 =

|х *

x 4-f ps*l4 ||а

 

 

sS

|х *

-Xs |2+2ps(vjs, х*

х 4)+Лр8.

 

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

обеих час­

тей этого неравенства

 

 

 

 

 

 

 

 

М I

|х*

x s+1 ||2/x1, х 8............х 4) <

 

 

II х *

x s ||8 +

2ps(F ^(xs),

х * -х *)А -А &

где F r(xs)=M (ris(x >, . . . Xs)).

Нетрудно

видеть,

что

 

 

 

(/^(х4), х*

X s) со.

 

 

Это следует

из того, что функция

шах|/Дх, ю)|

выпуклая

Вниз при любом о), а вектор -rf

 

t

 

 

 

-внутренняя нормаль опор­

ной гиперплоскости к телу

 

 

 

 

 

 

 

|х:тах|/,(х,

со4)|<тах|/Дх4,

о>®)|}.

 

 

 

t

 

 

 

t

 

 

 

 

Поэтому

 

 

 

 

 

 

 

 

 

М{ || у

х 4+> || 7 х \

. . .,

х 4}

|| х *

х 4 II8 + Лр*.

(7.3)

Из последнего следует, что случайная последовательность является квазифейеровской относительно множества D, по­ этому она сходится с вероятностью, равной единице.

40


Пусть теперь справедливо условие (7.2). Из свойства операции случайного проектирования и неравенства (7.3) имеем:

М |

1 1|2 ^ II * *

||» - Ь v p *(F ,(**)f * * х к) -

 

 

fe-0

+* & } ■

Всилу (7.2) левая часть неравенства равномерно ограниче­ на. Следовательно

 

^ psMiFjAx*), x * —x s)>

оо,

 

 

Г" I

 

 

 

 

 

 

 

/\

 

x s)-*0 при s-+oо.

 

 

 

т. е. M (Fx(x s), х *

 

 

 

 

Поэтому

найдется

 

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

|s/|, 1 =

0, 1 ,...,

 

 

 

ч

 

 

с вероятностью,

для которой при I ->оо (F *(a:s), х * - x si)-*Q

равной единице, т.

е. при любом ш подпоследовательность

(jc*i(w) 1 сходится

к

некоторой

точке

минимума

функции

F(x).

 

 

 

 

 

 

 

Если учесть

следствие 2,

леммы 7.1,

то этим доказа­

тельство

теоремы

заканчивается.

 

 

 

2°.

Задача двухэтапного

стохастического

програм­

мирования. Данная задача применяется тогда, когда требу­ ется составить план на некоторый интервал времени при не полностью определенном будущем. При реализации приня­ того в такой ситуации плана возникают „неувязки*, ликви­ дация которых связана с определенными затратами. Необ­ ходимо найти такой план, стоимость реализации которого с учетом ликвидации неувязок является в среднем минималь­ ной.

Математическая

задача ставится следующим

образом

(см. [36| и [62]).

 

 

 

 

Пусть заданы:

 

 

 

 

1) система линейных неравенств вида

 

Ах +

Dy ^

В(ш),

(7.4)

х

0,

у >

О,

(7.5)

41