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

где Cj — заданные

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

числа (предполагается^

что множество R,

определяемое

ограничениями исходной

рому числу

реализаций

определим доверительный интер­

вал [a.j , a,j ]

для M(tij )

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

Тогда легко заметить, что если

П

/ = т а х 2

c i х )

J -

1

при

2

fly xi

a n+i,

j -

1

-

X}

>

0 ,

j — 1, 2 , . .

ft,

а

l =

т а х 2

Cj Xj

при

2

^

Xj ss

Л ; >

0 ,

/ =

1

, 2 .................ft,

j -1 M ( CJ ) * j

(6 .1 )

Р & а и ^ ) х 1^ Ь 1{ш)\ = 1,

i = 1 ,2 ..........

/га,

(6.2>

*/ > 0,

У =1, 2,

. . ., ra,

(6.3>

Пусть ац(ш) и

—независимые

величины с извест­

ными областями значений

Ац и В /,

т.

е.

а,-£А ц и b ^ B i с

вероятностью, равной единице.

Тогда ограничения (6.2) означают, что при всевозмож­

ных реализациях

пц ^ А ц ,

b i Q B u

2

4 j < b u

i=

1,

2, . .

., n.

(6.4)

'Т»

Нетрудно

видеть,

что

(6.1)—(6.3)

равносильна

следу­

ющей задаче.

Максимизировать

(6.1)

при ограничениях

П

i = 1, 2, . .

.,

m,

(6.5)

H a / j ^ b i ,

/=1-

Xj^>0,

У =

1, 2, .

.

.,

я,

(6.6)

a,y=mln ац,

a

bi—max bi

aij € -4 ij

h $Bt

(предполагается, что а/

и bi существуют).

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

пусть Х * = (х1,

л;*,..., •**)—решение зада­

чи (6.1), (6.3),

(6.4),

а Х=^(хг, х2,

. .

.,

х п)—решение

зада­

чи (6.1), (6.5), (6.6). Так как

X *, в

частности,

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

ограничениям (6.5), тоS*2

2 Л1(о)-*/®£2 M(cj)Xj.

j - 1

1

i - 1

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

X

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

ограничениям

(6.4).

Поэтому

S М (Cj)x*. >

У М (Cj)xj.

1

; - i

Из последних неравенств следует,

что Х * = Х. Таким обра­

зом, предварительный

анализ рассматриваемой

задачи

поз­

воляет вероятностные ограничения заменить обычными.

Теперь

приведем

прямой метод решения

этой

задачи

(с требуемой

точностью

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

не

меньшей, чем

ли

получены

реализаций случайной

величины Cj.

Тогда

а)

получаем

реализаций

величины Cj, где

1</г <sH'><0 0 ;

б)

по числу

реализаций д у +1) =

+

k ^ +1),

исполь­

зуя

формулы (2.4),

(2.5), с

вероятностью Р/= 1 —- —

п

находим

доверительный

интервал

[cj,

Cj\

для М(С])-,

в)

одним из конечных

методов

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

рования решаем следующие «-доверительные задачи

(пред­

полагается, что они разрешимы

и

максимальные значения

их линейных форм ограничены сверху):

найти

П

ci x J

шах 2

(6.7)

xeR

] - i

-

шах 2

ci x h

(6-8)

x e R

т- i

где

R —множество,

определяемое

ограничениями (6.5),

(6.6)

г)

если

— /(4+>)^2£ (/<i+1)

и

—

решения

задач (6.7) и (6.8)),

то

/(*+1) = --------------------требуемое ре­

Пусть (Л*)}— случайная

последовательность, получен­

ная вышеописанным алгоритмом.

Теорема 6.1. Каковы бы ни были заданные положитель­

ные

числа е и «(0<J*<C1)>

всегда найдется

такой номер

Л/(е,

а), что для всех

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

неравенство

водить не будем.

3°.

Теперь предложим метод решения следующей за­

дачи.

Максимизировать

2

j )jcj

при

j -1

2 M (aij)X jS^M (ai,„+i ),

/ = 1,2 , . .

m,

J - 1

0,

i = 1, 2, . .

n.

Схема алгоритма. Пусть на s-ом шаге были получены

реализаций случайных

величин apq (/7=1,2, . .

т -j-1,

<7 = 1 , 2,

. . ., « + 1 , а т+], я+ 1 = 0 ) ,

и задача не была

реше­

на с точностью г>0 и вероятностью,

не меньшей,

чем задан­

ное число а (предполагается,

что

задача

разрешима,

и ее

линейная форма ограничена сверху). Тогда:

а)

получаем k^+1^ реализаций

величины apq,

где

1 <

< А<м+1)< ° ° ;

К^+1)== К ${

б) по числу реализаций

+

с

вероят­

1—а

(?т-rl. п +1

1)

находим

довери­

ностью §pq=\

тп-\-т+п

тельный интервал [Opq, apq]

для

M (apq);

в)

одним из конечных

методов линейного

програ

рования решаем следующие а-доверительные задачи

(пред­

полагается, что они разрешимы, и

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

значения

их линейных форм ограничены сверху).

Задача ■A(,s+'1) . Найти

П

а т+1. jX j

шах 2

7-1

при условиях

п

i =

1,

2,

.

.

., т,

2 aijX j^ ai, п+х ,

7= 1

Х ]>0,

j =

1,

2,

.

.

.,

п.