Ермольев Ю.М. Методы стохастического программирования

Подождите немного. Документ загружается.

ТЕОРЕТИКО-ВЕРО~1ТНОСТНbJЕ

понqтия

где

ХА

(ю)

характеристическая

функция

множества

А,

т.

е.

ХА

(ю)

при

ХА

(ю)

= 1

при

А.

Легко

убедиться,

что

ММ

(~!cPc1)

M~;

если

СРС1

или

(ю)

является

-измеримой,

то

(~!c,f')

Пусть

теперь

(ю)

(1]1

(ю),

...

1]г

(ю))

случайный

вектор.

Условное

математическое

ожидание

(~!ч)

вели

чины

относительно

определяется

следующим

образом.

Обозначим

через

f!!!J

борелевские

множества

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

рассмотрим

события

1ю:

(ю)

,~}.

Совокупность

этих

событий

образует

а-подалгебру

cPc1t]

исходной

а-алгебры

wt,

полагают

(~!fJ)

(~/$(Ч.

Можно

показать

(см.,

например,

[6]),

что

при

этом

(~!ч)

есть

измеримая

функция

от

Ч,

т.

е.

значения

(~!ч)

определяются

значением

Ч.

т и

ы.

При

рассмотрении

вопросов

сходи

мости

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

случайных

величин

важным

является

понятие

субмартингала

супермартингала.

Это

своеобразные

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

аналоги

неубывающих

невозрастающих

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

действительных

чисел.

Пусть

(Q, wt,

Р)

вероятностное

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

(ю),

5 =

О,

...

, -

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

случайных

вели

чин;

со.

ПQследовательность

(ю),

5 =

О,

...

называется

суnермарmuнгалом,

если

(s5+111;0,

•••

~5)

~5'

5=0,1,

•••

марmuнгалом,

если

(Ss+1!~o,

...

~5)

Ss,

5=0,1,

...

субмарmuнгалом,

если

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

S5'

5 =

О,

...

является

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

Пример.

Пусть

~5=

~k,

5=0,

...

Если

M(~k/~o,

...

k=O

...

~k-l)

при

k >

О,

т,

е.

величины

центрированные,

то

(~S+l/~t"

...

~5)

(~5

S+l/~o,

...•

~5)

т.

е.

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

образует

мартингал.

Иногда

полезными

являются

более

общие

определения.

Пусть

.••

неубывающая

последова

геЛЬНО':l'Ь

ВСПОМОГАТI!ЛЬНЫI':

СВЕДЕНИЯ

ГГ

а-подалгебр

а-алгебры

Q/t,

т.

е.

шt

D,f'sH'

Последова··

тельность

~s,

s =

О,

...

называется

адаптированной

семейству

Q/f

если

при

каждом

s =

О,

...

величины

Являются

w!,-1Iзмеримыми.

Пусть

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

~s,

s =

О,

адаптирована

семейству

Q.-4"

О,

...

такова,

что

~""

! <

00,

Тог

да

эта

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

называется

супермартингалом

(относнтельно

<2~/s,

$=0,1,

...

если

(~s+l/~S)

~~"

5 =

О,

;

мартингалом,

если

5=0,1,

субмартингалом,

если

~s,

S =

О,

.,.,

является

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

Отметим,

что

из

определения

супермартингала

следует,

что

из

определения

мартин

гала,

что

M~s+1

M~s

...

M~o.

Теорема

Если

{~s,

<2~s,

5=0,1,

...

]

-суnермар

тингал,

то

для

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

вероятностьiо

конечного

предела

~~~

(0)

достаточно,

чтобы

iпf

M~~

> -

00,

~;-

шiп

{О,

~s}'

Отсюда,

частности,

следуег,

что

если

~s,

5 =

0,1,

...

неотрицательный

супермартингал,

то

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

существует

предел

~S'

том

случае,

когда

мар

тингал,

условие

inf

M~s

> -

заменяется

УСЛОВllем

sup

00.

Если

маРТl\нгал

~k'

где

цент-

k=O

рированuые

случайные

величины,

то

M~~

M~k;

;'=0

поэтому

справед~[[шо

следующее

утверждение:

ТЕОРГ:ТИКО-ВЕРОЯТНОСТНЫЕ

ПОНЯТИЯ

с т

е.

Если

2.:

I\J1~;;

со,

то

ряд

2.:

~,'

схо-

k=O k=O

дится

почти

всюду.

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

теоремы

основано

на

применении

следующего

неравенства

Дуба:

м м

Пусть

({),

О,

...

Т,

конечные

числа,

(Т)

число

переходов

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

(О),

...

, r

(Т)

от

значений,

лежащих

слева.

значениям,

лежащим

справа

от

интервала

[а,

Ь],

называемое

числом

пересечений

[а,

Ь]

снизу

вверх.

Тогда

Т-I

(Ь

-а)

(Т)

(а

- r

(1'))++

2.:

l(t)

(r(/+

- r

(1)),

1=0

где

(/)

принимает

значения

или

причем

значение

(/)

полностыо

определяется

по

величинам

(О),

...

, r (/).

r(t)

bf--------I-i\-i'--------'\-----------,fr:--------I1t---e-----p.r+-

СЛ!l'(оul

af-\J----I--------\---f----I------\1/--+-----''rf-'~-

СЛ!llfl1u2

Рис.

с т в

о.

Пусть

первый

момент

вре

мени,

когда

(1)

принимает

значение,

меньшее

а,

12-

перный

после

момент,

когда

r (/) >

Ь,

1з

первый

после

момент,

когда

(1)

а,

т.

д.

Тогда

на

отрезке

времени

Т]

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

(/)

уже

ни

разу

не

пересечет

[а,

Ь]

снизу

вверх,

причем,

как легко

видеть

(рис.

1),

(Ь

а)

(Т)

2.:

(г

(l2i)

- r (/

)).

i=1

Это

можно

записать

так:

'211

(b-а)ll(Т)~L

1(/)(г(/+1)-г(I)),

I=О

ВСПОМОГАТЕЛЬНЫЕ

СВЕДЕНИЯ

rгл

если

определить

функцию

I (t)

так,

чтобы

она

принимала

значение

интервалах

[11'

.••

, [t

, t

значение

О во

всех

остальных

точках

интервала

[О,

Очевидно,

что

функция

I (t)

меняет

значение

на

наоборот

только

точках

ее

значение

1(t)

фик

сированный

момент

времени

t (t =

О,

...

, t

)

полностью

определяется

величинами

(О),

...

(t).

Определим

1 (t)

на

интервале

Т)

следующим

образом:

значение

I (t) =

до

тех

пор,

пока

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

ность

не

принимает

значения,

меньшего

а;

если

найдется

впервые

после

момент

времени

такой, что

+l)

а,

то

I (t) = 1

при

+l,

TJ.

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

если

момента

не

существует,

то пре

дыдущее

неравенство

можно

записать

еще

так:

Т-'

(Ь

а)

(Т)

I (t)

(г

(t +

(t)),

1=0

Т-I

если

существует,

то

I (t)

(г

(t +

(1))

отли-

1=0

'2h

чается

от

(t)(r

(t +

1)-r(t))

на

величину

r(T)-r(t

+l)'

1=0

Если

(Т)

+l)

О,

то

предыдущее

неравенство

сохра

няется,

поэтому

общем

случае

Т-l

(Ь

а)

(Т)

I (t)

(г

(1))

(г

(l2h+l)

(Т))+,

1=0

где

(х)+

шах

{х,

О}.

Учитывая,

наконец,

что

r(l2h+l)

а,

отсюда

получим

нужное

неравенство

Дуба.

Покажем,

как

используется

это

неравенство

при

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

теорем

сходимости

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

Докажем

следующее,

более

общее, чем

теорема

утверждение,

которое

потребуется

дальнейшем:

Пусть

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

1]5

(ш),

S =

О,

...

адаптирована

семейству

в7'!

S =

О,

...

inf

М1];

> -

СО,

ТЕОРЕТИКО-ВЕРОЯТНОСТНЫЕ

ПОНЯТИЯ

где

величина

измерима

относительно

е4

сх:>

<00.

5=0

Тогда

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

существует

конечный

пре

дел

115

( I

Iiт

115

I <

(0)

при

00.

~CX)

Т е

Т В

о.

Поставим

соответствие

слу

чайным

величинам

110

(ш),

111

(ш),

...

11k

(ш)

случайную

вели

чину

h (k,

ш)

случайные

величины

! (k,

ш),

которые

для

краткости

будем

обозначать

через

h (k), ! (k).

Тогда

для

любого

справедливо

неравенство

k-\

(Ь

а)

h (k)

(а

-11k)++

(S)(115+1

-115)'

<=0

Величины

h(k), 1

(k)

определяются

значениями

110""

••.

11,,,

поэтому,

беря

математическое

ожидание

от

левой

правой

части

этого

неравенства,

учетом

свойств

услов

ного

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

ожидания

получим

k-l

(Ь

а)

(k)

(а

-11k)+ +

ММ

(S)(115+1

-115)/А

)

5=0

•

k-l

(а

-11k)+ +

М!

(s)

(М

(115+1/е4'5)

-115)'

5=0

учетом

основного

свойства

115

отсюда

получаем

k-l

(b-а)Мh(k)~М(а-11k)++

•

(1.2)

5=0

Полученное

неравенство

для

среднего

числа

пересечений

снизу

вверх

интервала

а,

Ь]

величинами

110'···'

11k

является

решающим

для

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

теоремы.

Пусть

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

110

(ш),

11]

(ш),

...

не

сходится

почти

при

каждом

(с

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

1).

Тогда.

найдутся

такие

числа

Ь,

что

множество

А",

(;

{ш:

1im

1~.

(ш)

Нт

115

(ш)}

.~~

ВСПОМОГЛТЕЛI,НhlЕ

С!3ЕДЕНJIЯ

rгл

не

пусто,

т. е.

{А

•

ь}

О.

Покажем,

что

этого

не

может

быть,

т.

е.

что

{А

•

ь}

О.

ПослеДС1ватеJIЬНОСТЬ

(1), h (2),

...

не

убывает

и стре

мится

:':;

fJРИ

(,)~

:а,о'

Пу

I:·c·

!:JП/l(~).

Тогда

S-·,:;

Р{Аа.ь}=О.

если

P{/7'~'Y;)=C!

~·rО:У')!·

'jдет

иметь

место

том

случае,

еСЛ;j

IVI!!

С-С.

O~.

'I~.1

:.,'[.

Применяя

лемму

Фату

инеравенство

(1.2),

получим

(с

учетом

монотонности

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

(s))

liт

h (s) = Mh = Iim

(s)

s~ro

~b~a(S~P

(a-Y]5)++,~o

MW5)

=ь~a(-

i~fМ(У]s-а)-+!

5=0

Так

как

по

условиям

теоремы

inf

МУ];-

> -

ОС).

,=0

со.

то из

последнего

неравенства

следует,

что

со

и,

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

{А

•

ь}

О.

Так

как

всагда

можно

предполагать,

что

а.

рацио

нальные

числа,

так

как

множество

всех

Ш,

где

имеет

место

расходимость

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

У]5'

т.

е.

Ш:

1im

Y]s

5-+OJ

< limY]s}.

может

быть

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

как

Аа,ь,

где

5-00

а,

пробегают

счетное

множество

всех

рациональных

чисел,

то

отсюда

следует

утверждение

теоремы.

§ 2.

Выбор

решений

условиях

риска

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

е ч а

я.

Существуют

различные

под

ходы

проблеме

выбора

решений

условиях

риска

неопределенности.

каждый

из

которых

имеет

свои

поло

жительные

отрицательные

стороны.

Цель

этого

пара

графа

состоит

том,

чтобы

на

самых

простых

примерах

проиллюстрировать

это

разнообразие подходов

отметиТ1,

их

недостатки.

Согласно

принлтой

классификации

[44]

задачи

выбора

решений

обычно

различаются

тем,

принимает

решение

УСЛОВИЯ

РИСКА

ИНЕОПРЕДЕЛЕННОСТИ

индивидуум

(индивидуальное

решение)

или

группа

(груп

повое

реи/сние),

тем,

производится

выбор

при

оnредслен

ности,

при

риске

или при

неоnределенности.

При

этом

индивидуумом

считается

человек

или

организация,

име

ющая

единый

интерес,

служащий

мотивом

ее

решения.

Всякое

собрание

таких

индивидуумов,

противоречия

между

которыми

разрешаются

либо

открытым

конфликтом,

либо

компромиссом,

рассматривается

как

группа.

дальнейшем

основном

будут

рассматриваться

только

задачи

выбора

индивидуальных

решений.

Говорят,

что

имеет

место

вblбор

ре/иениU

при

определенности,

если

каждое

действие

неизменно

приводит

однозначному

исходу;

вblбор

решений

при

риске,

если

каждое

действие

приводит

одному

из

множества

возможных

частных

исходов,

каждый

из

которых

имеет

известную

вероятность

появления;

вblбор

реlUений

при

неоnределенности,

если

каждое

действие

приводит

одному

из

множества

частных

исхо

дов,

вероятности

которых

неизвестны

или

даже

не

имеют

смысла.

б о

а.

Выбор

решения

при

опреде

ленности

сводится

следующему:

дано

множество

доnу

стимых

действий

(доnустимых

решений),

требуется

этом

множестве

выбрать

такое

действие

(решение),

которое

дает

минимум

(или

максимум)

некоторого

показателя,

назы

ваемого

функцией

цели.

Примерами

нетривиальных

задач

выбора

решений

при

определенности,

потребовавших

развития

новых

разделов

математики,

являются

задачи

линейного

программирова

ния,

более

сложными

примерами

задачи

нелинейного

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

Сущность

задач

выбора

действия

или

решений

при

риске

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

можно

пояснить

на

следующем

IIРОСТОМ

примере.

Пусть

имеется

множество

действий

или

решений

i =

.,.

возможных

исходов,

однозначно

опреде

ляемых

СОСТОЯН[1ЯМИ

природы

j=l,

" n,

пусть

[i:

-затратbl

(убblток,

потери),

связанные

действием

при

исходе

(состоянии

nрироды)

данном

случае

t/j

есть

фУНКIща

цели.

Числа

tll

можно

представить

виде

матрицы

ВСПОМОГАТЕЛЬНЫЕ

СВЕДЕНИЯ

ГГ

Л.

Истинное

состояние

природы

неизвестно.

Требуется

найти

такое

действие

(т.

е.

выбрать

такую

строку

матрицы

ии}),

которое

некотором

смысле

лучше

других.

Если

известны

вероятности

Рl'

...

Рn

состояний

j =

...

Р!

то

имеет место

задача

выбора

решений

при

риске.

При

этом

часто

выбирается

действие

i =

...

т,

которое

минимизирует

оредние

затраты

f{fPf'

Это-

простейшая

задача

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

nрограммирования.

Насколько

удачным

показателем

являются

средние

затраты,

зависит

от

конкретных

обстоятельств.

Например,

если

есть

два

действия

два

исхода

затратами,

предстаВJJен

ными

матрицей

табл.

нижней

строке

которой

указаны

Таблица

1000000

10000000

Р!

0,000001

0,999999

вероятности

исходов,

то

желание

минимизировать

средний

убыток

приводит

выбору

действия

Преимущества

этого

действия

связано

пребыванием

природы

мало

вероятном

состоянии

Если

же

учесть

то,

что

природа

практически

будет

находиться

СОСТОS'lнии

котором

затраты

действия

больше

затрат

действия

то

более

разумным

кажется

выбор

действия

Такой

выбор

можно

обосновать,

если

вместо

минимизации

средних

затрат

мини

мизировать

вероятность

(i) =

{ll

где

f -

некоторый

уровень

затрат,

например

f =

Однако

заметим,

что

если

f =

то

этот

критерий

приводит

выбору

первого

действия.

УСЛОВИЯ

РИСКА

ИНЕОПРЕДЕЛЕННОСТИ

Менее

тривиальным

примерам

выбора

решения

при

риске

является

задача

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

про

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

связанная

планированием

запасов.

Про

ей

а с

к л

и р

я.

Имеется

пункт

(склад)

вместимостью

единиц,

где

требуется

создать

запас

некоторого

продукта.

моменту

планирования

нет

точной

информации

потребностях

этом

продукте,

но

есть

основание

считать

величину

спроса

случайной

функцией

распределения

(г)

{~<

г}.

Пусть

размер

запаса

составляет

единиц.

Тогда

количество

продукта,

которое

будет

отпущено

со

склада

при

условии,

что

его

запас

х,

спрос

равно

меньшему

из

двух

чисел

Поэтому

ОJКидаемое

потребление

равно

zdH (z) +

(г).

Пусть

доход

от

реализации

единицы

продукта

состав

ляет

единиц,

Тогда

ожидаемый

доход

при

запасе

еди

ниц

равен

F(X)=C[~ZdH(Z)+Xr

dH(Z)]=

=сп

Z dH

(г)

+x(l-

(х))].

Задача

состоит

том,

чтобы

выбр

ать

такое

Х;?;

О.

кото

рое

максимизирует

функцию

(х).

Мы

видим,

что

определение

значения

функции

цели

(дохода)

простейшей

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

задаче

планирова

ния

запаса

связано

вычислением

интеграла,

который

конечном

виде

берется

только

редких

случаях.

Когда

же

планируются

запасы

неоднородных

продуктов,

появляются

(см.

многократные

интегралы,

что

еще

более

услож

няет

задачу

вычисления

функции

цели.

Кроме

того,

функ

ция

(х)

рассмотренного

выше

примера

MOJКeT

оказаться

негладкой,

что

зависит

от

функции

распределения

(г).

Рассмотрим

теперь

некоторые

критерии,

которые

бы

ли

преДЛОJКены

для

решения

задач

выборе

решения

при

неопределенности,

причем

для

простоты

остановимся

пока

только

на

задаче

конечным

числом

действий

i =

...•

т,

ВСПОМОГАТЕЛЬНЫЕ

СВЕДЕНИЯ

ггл

0,9

состояниями

природы

j =

...

, n

матрицей

затрат

(потерь)

f/f'

Более

общие

задачи

рассматриваются

даль

нейшем.

и н и

и т е

р и

Й.

Согласно

этому

принципу

(критерию)

принимающий

решение

пытается

свести

минимуму

максимальный

убыток,

который

он

терпит

от

того,

что

совершает

некоторое

действие.

То

есть

каждое

действие

оценивается

числом

(гарантирован

ным

уровнем)

и)

тах

f/f

«оптимальным»

считается

то

действие,

которому

отвечает

наименьшее

из

чисел

и).

Пример,

представленный

табл.

показывает,

какие

возраже

ния обычно

выдвигаются

про

тив

минимаксного

принципа.

Здесь

согласно

минимакс

ному

принципу

действие

оказывается

предпочтитель

нее,

чем

Между

тем

очевид

но,

что

действие

разумно

только

том

случае,

когда

состояния

j =

...

, n

ко!!т

ролируются

сознательным

противником,

который

может

быть

полностью

осведомлен

действиях

принимающего

ре

шение

матрице убытков

обязательно

выберет

j =

р и й

а.

Этот

критерий

называют

еще

критерием

МUlшмакс/юго

риска.

для

каждого

состоя

ния

природы

отыскивается

min

f/f.

предыдущем

при

I .

мере

minfil=O,

minfi2=0,9.

Условимсяриском

называть

I I

разность

miп

fi/.

Поэтому,

если

природа

находится

состоянии

j =

то

пр!!

выборе

действия

i = 1

нет риска,

но

есть

риск

при

выборе

i =

равный

0,9;

если

истин

ное

состояние

природы

j =

то

нет

риска

при

выборе

действия

i = 2

есть

риск,

равный

1- 0,9,

при

выборе

действия

i =

соответствии

этим

будем

рассматривать

матрицу,

лредставленную

табл.

выбирать

то

действие,

которое

минимизирует

наихудшее,

что

может

предложить

природа

при

данной

матрице

убытков.

То

есть

будем

минимизи-