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

л

__

,

/ =

1,

2,

. . .,

/и,

^O ijX j ^ a i , п+1

)-1

* j >

0,

у '=

1 , 2 ............я;

г)

если

Z(i+1) — /(4'+‘)<2s

(/<л+1> и

—решения задач

_

_

/й+D -j-Z^+D

д(^+п и

Л'4+1)),

то

/('ч1) =

---------- ^

--------

— решение

ис­

ходной задачи (в противном случае

переходим к пункту

а).

Прежде

чем

перейти

к

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

сходимости

предложенного

алгоритма,

отметим,

что если на

некотором

s-ом шаге /(*)—

2е, то в качестве приближенного плана

исходной задачи

можно

взять

оптимальный

план

=

* 2S)> • • ••

задачи

Л<5>.

(Как

будет

видно

из

Пусть {/<*>} —случайная последовательность,

полученная

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

Теорема 6.2. Каковы бы

ни были заданные положи­

тельные

числа е и

а (0 < а < 1 ),

всегда найдется такой номер

N(e,

а),

что для всех s!>ZV(e,

а) выполняется неравенство

Р(|/—

Доказательство. Вначале покажем, что на любом s-ou

шаге

задачи AR> и

относительно исходной

являются а-

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

Обозначим через R{s) и R(s)—множества, определяемые

соответственно ограничениями задач A^s) и

и покажем,

что они являются

а'—доверительными множествами относи­

33

тельно

R, где

R —множество

тех

точек

X ,

которые удов-

летворяют ограничениям

исходной

задачи, а а' =

т л+1

П П $„а.

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

возьмем

произвольную

точку

Р - 1

x £ R < sK Тог­

да, так как а% '^М (ард)

и х ^ О ,

то

v

п<)Ъс/>2 M (ai j )x'f,

i=

1,

2,

.

. .,

т

i - i

i - i

или

П

П

,„+1>

/=1,

2,

. . .,

/и,

v U i j X j < y

y-1

/“>

t . e.

/?.

Отсюда следует, что R (S)CZR-

Аналогично можно

показать,

что если x £ R t то x£R<s).

Учитывая

предложение 6.1, получим:

P \ R ^ R ^ R ^ } > a ' .

Далее,

в силу

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

легко

заметить,

что

max

п

п

)х,- sSmax

п

«т-п,;

•*/.

2

ая,+1,у-*/=£тах ^ М (а т+и

2

x £ R (s)J~ l

j " 1

7 - 1

задачи

и

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

исходной являются а-дове-

рительными задачами, где а =

mil

п -fl

П

П fW

Р™1 9 -1

Очевидно, что на любом s-ом шаге выполняется нера­

венство

Р [ | / _ / < * ) [ < / ( * ) _

/(*))

> < х .

С другой

стороны,

так как для всех р и q limja^—а<^>|==0,

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

{ /(4)—

также

стремится к нулю с

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

же вероятностью стремится

к нулю

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

\1— №\, что и требовалось

доказать

4°. Алгоритм решения задачи Минца и Финкельштей-

иа. В работе [45] была поставлена

следующая

задача сто­

хастического программирования:

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

величины

с =

П

a m+i, fXj

ш1п 2

i -1

при условиях

п

< Й

1 , и + ь

*

=

1 ,

2

.....................т ,

j - 1

X j> 0,

у =

1,

2,

.

.

га,

где

Qpq—независимая

случайная

величина.

Для решения

этой

задачи в

случае,

когда

а у

и

2, . .

/га;

у '= 1 , 2, . .

га)—известные

величины,

a

a m+i,/= a(n[]t.u

-t-

+ ш т+1 ; ’ где '-—случайная переменная,

был предложен не­

прямой метод, идея которого заключается

в следующем.

„Игнорируя" вероятностную природу случайной

вели­

чины X, вместо исходной

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

следующая одно­

параметрическая задача линейного программирования.

Найти

П

^m+l,y

== У('■)

mill ^

j -

1

при условиях

У-1

ssaj»

, f

a & V -

* e

l . 2’

• • -

от-

•Ху > 0 ,

У = 1 ,

2 , . .

. , га.

Далее, предполагая, что известен отрезок

[ X, X]

изме­

нения величины X, с

помощью

методов

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

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

разбивают

ее

на такие конеч­

ные подмножества [Xr, Xr+1] ( r

=

1 ,

2 , . .

. ,

S;

\ = = к ,

Х2=Х),

на которых функция /(Х) = /Г(Х) порождается одним

и

тем

же базисом.

Зная плотность распределения <р(Х) случайной величины

X, вычисляем

значение

интеграла

Найти

min ^

am+i1);-*y =C (i+1)

)-1

при условиях

VaSj+1»x; ^ fl(;+ 1',

i = l ,

2,

.

. .,

т.

/- I

х,

35 0,

j =

1,

2,

.

. .,

«;

в) по (s—f—1) реализациям величины

с

строим довери­

тельный интервал (<3i+1>, с(Л+1)) для М (с)

с

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

не меньше, чем <*;

_

2е, то

_

c(s+1)-|-c(s+l>

г) если с('+1) — сЫ+1) ^

^5+1)= ------ —=------- —ре­

шение задачи в требуемом

смысле;в

противном случае пе­

реходим к пункту а).

раммировании.

I. Пусть D —некоторое замкнутое

множество

из /?и, а

C (D )—его

выпуклая оболочка.

Определение 7.1. Случайную последовательность |уса(*й)|,

А = 0, 1, .

. . назовем случайной

фейеровской последова­

тельностью

относительно множества

D,

если

М{ II у—х к ' 1 II *jx°,

х ' , ........... **}«£

II

у—x k \\\ k =

0. 1, . . .

для произвольного

y£D и

|л:° | const < о о .