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

УИ0=

М

\

(3.12)

h

является (г,

я)—доверительным вектором разрешимости сто­

хастической

задачи.

Здесь

т

Ni = / 2 А Ф -н Э, ),

р, >

у ,

/=1,

2,

т, пр, > я.

/-1

Доказательство этой теоремы основывается на следую­

щих двух леммах.

Лемма 3.2. Для пары векторов X

и X,

компоненты ко­

торых

удовлетворяют условиям

x t — х< ^ О ,

Xi , x t £

[яг

,

яi ],

г =

1,

2, .

. ., т,

(3.13)

т

__

__

2 ( ^

- ;* / ) '< Z I

(3.14)

i-l

имеет

место

неравенство

l ( X j -

1 (Х )есв .

(3.15)

Допустим^ противное: для некоторой пары векторов X, X

выполняется

условие

1 (Х )-Ц Х )> * .

Тогда, очевидно, на

отрезке

?Х + (1 — p )Z (0 < )i < П

существует точка Х °=^°Х -г{\ —\>-0)Х такая,

что

l(X j—1{Х) > 1 (Х °)-Ц Х )= в ,

т. е. (Х°, X ) является допустимым

планом

задачи

(3.9) —

<3.11).

~

Х°— внутренняя

С

другой стороны,

точка

отрезка

JQt-f (1—

Поэтому

x°—Xi <^Xi — Xt,

1 =

1,

2,

. . .,

т

или

т

т

__

2

i-l

)<z.

i - 1

2 (aV—Xi )< Z . Полученное

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

указывает на

i~ I

справедливость утверждения -леммы 3.2.

Лемма 3.3. Для пары векторов X и Y, компоненты ко­

торых удовлетворяют условиям

Xi

, уi

,

«/ ]>

i = 1, 2, . . .,

m,

(3.16)

W

_

2 ( * г

“

У-' )2<

Z -

(3-17)

«-1

выполняется

неравенство

|/(Х )-/(П 1< б.

(3.18)

x i — yi>0,

/=1, 2, .

. .,

тъ

(3.19)

Xi — у, < 0 ,

i= m 1-{-1,

. .

.,

От2,

(3.20)

xi — у/ = 0,

i = m2-t-l,

. .

.,

т.

(3.20')

Вначале покажем,

что пара X, Y удовлетворяет неравенству

l ( X ) - l ( Y ) ^ e .

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

1(Ц — монотонно

неубывающая

функция,

поэтому с

учетом

(3.19),

(3.20) и (3.20') имеем:

1{Х) — /(Y) — l(x v .

. ., Хт)

^(Уц • • •> Ут)~^С

^ £ ( X i t •••,

X m i,

У ® , + 1,

. . . ,

У т )

^ ( У 1 > У ш п

•••, Х т ) =

—

((J C j ,

X*,,

. . . ,

A m )

Д а х,

£ m ) .

где

— _f xi

,i = l , 2, . .

Mj,

jc> =

f У; ,

f = l , 2.........

m,,

l yz

,i = /гег-(-1, . .

m,

—

\x-t ,

г=/я,+ 1,...,

m.

/ ( * ) - / ( К) > - 8 .

■Лемма 3.3 доказана.

Теперь перейдем к доказательству теоремы.

Возьмем произвольный вектор k f - M Q и

покажем, что k яв­

ляется (з, а)-доверительным вектором

разрешимости сто­

хастической задачи,

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

P [\ l-l(b (k )\ < z )^ a ..

(3.22)

Действительно, допустим, чтополучено

реализаций

каждой случайной величины bi . Найдем с вероятностью

границы доверительного интервала для М ( Ь ):

bi

(ki

) = b, (ki ) - ± u(k,

),

Т,

(kt

)= b , (k, ) + Д3Дki

)

для

1 , 2 , . . . ,

т.

/ - - = 1 , 2 ,

m.

нетрудно

видеть,

что условия леммы 3.3

при Xi = M (bt )

и

у, = bi

(ki

) выполняются

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

не менее

чем

а„

Поэтому неравенство (3.22) имеет место.

Теорема доказана.

Замечание 3.1.

Из доказательства теоремы

3.1

следует,

что предположение 3.1

может быть заменено предположе­

нием

,

t = 1, 2, . . ., т.

Итак, чтобы определить М ( М 0), которое является мно­

жеством (е, а)-доверительных

иекторов

разрешимости сто­

хастической задачи, нужно:

D(b-, ),

i — 1,

m-r

а)

найти такие

Д

, чтобы Д

>

2,

...,

б)

определить

числа

и оц ,

которые

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

условию

P{bi

(ki

)£

[<xi ,

асi

]} >

для любого ki > 0 ,

i —\,

2,

...,

т,

где

т

> а ;

П

1

/ =

bj

пользуясь методами параметрического программирова-

ния, установить вид функции l(l) = lQ),

определенной в пра­

вой окрестности точки а (решить задачу

(3.5) —(3.11))*;

г)

по (3.1) ((3.12)) определить множество М (М0)

и взять

любой

вектор k с

целочисленными

компонентами

из этого-

множества.

Согласно теореме 3.1 (теореме 3.2),

если

будут полу­

чены ki реализаций

каждой

случайной

величины bi и оп­

ределена статистическая оценка bi (ki ),

то

l(b (k ))

будет

решением

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

задачи

с

требуемой

точностью

е^>0 и

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

не меньше,

чем заданное а.

* Для определения вида функции /(А) достаточно решить

задачу

ли­

нейного программирования в точке

Х = а

с

некоторым видоизменением