Файл: Математическое программирование и производственные задачи..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