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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.10.2024

Просмотров: 48

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§ 4. ОПРЕДЕЛЕН ИЕ ДОВЕРИТЕЛЬНОГО МНОЖЕСТВА НЕРАЗРЕШ ИМОСТИ ЗАДАЧИ

Пусть в некоторой левой окрестности точки а функция

1(Ц порождается тем же базисом, что и в точке >-=а. Пост­ роим функцию /(Х) = /(Х) (определенную в этой окрестности),

которая в общем случае имеет вид*

т

—+ 2 Tiг -)'ii—■

Теорема 4.1. Любой вектор k (с целочисленными ком­ понентами), принадлежащий множеству

 

т

Д Т.

е )

 

 

{

 

 

(4Л)

 

 

 

 

является (г, а )—доверительным

вектором неразрешимости

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

задачи, где

_

_____

ТП

TV) =

Y2D t Ф_1(?г ),

П

 

 

 

 

г-i

Р/ > у ,

2, . . ., т.

 

 

 

Доказательство этой теоремы аналогично доказательст­ ву теоремы ЗЛ и отличается лишь некоторыми технически­ ми деталями, поэтому приводить ее здесь не будем.

Отметим, что оценки, полученные из (4.1), являются грубыми. Для получения более точных оценок нужно ре­ шить задачу нелинейного программирования, а именно:

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

т

W ' - . } ) = 2 Q't — '-г ) 2

г-i

при условиях

/ ( Г ) - 7 ( 1 ) = е,

7 —>i > о,

h , h

€ К . «г ],

/=1, 2,

. . ., т.

* Предполагается, что

оптимальный план л-задачи

при Х = а невы­

рожденный.

23

Если Z —максимальное значение целевой функции ука занной задачи, то справедливо следующее утверждение.

Теорема 4.2. Любой вектор к из множества

М 0=

N\ ki

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

Доказательство этой теоремы аналогично доказатель­ ству теоремы 3.2.

Ниже дана графическая иллюстрация на плоскости множеств М , М и М 0, М 0.

Множество Мг(Ма), которое состоит из векторов k, не принадлежащих ни одному из множеств М и М (М0 и М 0),

является неопределенным. Это значит, что если взять лю­ бой вектор k £ £ М2), то нельзя заранее сказать, будет ли стохастическая задача разрешима в требуемом смысле. Очевидно, M2C M V

§ 5. ЗАДАЧА ПОЛУЧЕНИЯ ОПТИМАЛЬНЫХ ОЦЕНОК

Из теоремы 3.1 следует, что (е, а)—доверительных век­ торов разрешимости исходной задачи бесчисленное множест­ во.

24

Поэтому, если для получения одной реализации случай­

ной величины bi требуются

затраты с;, то естественно пос­

тавить задачу определения

такого

вектора k

из множества

М, при котором затраты были бы минимальными.

Для решения этого вопроса,

очевидно,

нужно решить

следующую задачу выпуклого

целочисленного программиро­

вания.

 

 

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

 

 

т

 

(5.1)

cPl(^)==,2

^

1-1

 

 

при условиях

 

 

<=iT< 7 k t

 

(5.2)

 

2

ki (/==1, 2 , . . т) —целые

неотрицательные числа. (5.2')

Чтобы получить более точную оценку, необходимо решить следующую задачу.

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

т

<?■>(&)=2 с‘ h i - 1

при условиях-

К

IN II

к

(5.3)

(5.4)

ki {i —1, 2, . . .,

т )—целые неотрицательные числа, (5.4')

где

Z —минимальное значение

линейной

формы задачи

(3.9)

—(3.11).

 

 

 

Пусть k \k)

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

(5.1) —(5.2')

((5.3) — (5.4'))

без условия целочисленности. Тогда, если в качестве „опти­

мального" плана взять

вектор k * ( k * ),

где компоненты

век­

тора k *

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

из условия k*. =

)ki [

(£*=]&; [),

не­

трудно

убедиться, что k* ^ M (k* ^ М °),

и,

кроме того,

ре-

 

 

 

т

•

 

шение по функционалу не превышает 2 с‘

 

25

Аналогично могут быть определены „оптимальные* за­ траты (грубые и точные), при которых стохастическая за­ дача неразрешима в требуемом смысле. Для этого доста­ точно решить следующие задачи целочисленного нелиней­ ного программирования:

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

ТзС*)

 

т-,

 

 

1 ki

при условиях

 

 

 

2 l i

л^_

Yki

 

2 ’

1=1

 

ki ( г = 1 , 2, . . m) —целые

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

и

 

 

 

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

 

 

 

 

т

 

Ci ki

?i(k) = 2

 

 

i=1

 

при условиях

(5.5)

(5.6)

(5.6')

(5.7)

ki ( t =l ,

2, .

. .,

m) — целые неотрицательные

числа. (5.7')

Если

®",

f?2 '

Тз и ?4 — оптимальные значения

целевых

функций

соответственно задач (5.1)—(5.2'),

(5.3)—(5.4'),

(5 .5 )-(5 .6 '),

(5.7)—(5.8'), то <p?<<p°<<pg<

 

 

Наконец,

отметим, что большой интерес представляет

определение

априорных оценок для более общего

случая,

а именно для задачи: максимизировать

f { X ) = % M ( C j ) X j

при условиях

2

M (iiij)xj^ M (bi

),

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

 

X j > о,

у = 1, 2, . . ., п,

где cj, a ij,

b(—случайные

величины.

26

 

 

 

§ 6. ПРЯМЫЕ МЕТОДЫ РЕШ ЕНИЯ ЗАДАЧ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

При решении стохастических задач, в соответствии с классификацией, введенной в работе [34], можно различать прямые и непрямые методы. К непрямым методам относи­ лись методы, которые сводили стохастическую задачу к: обычной нелинейной задаче математического программиро­ вания. Однако, как было сказано ранее, такой подход име ет свои существенные недостатки. В связи с этим в указан­

ной работе ставился вопрос о

разработке

прямых

методов

решения стохастической

задачи.

Процесс

решения

стохас­

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

прямым

методом

можно представить в ви­

де следующей цепочки:

 

 

 

 

 

 

 

наблюдение— решение—наблюдение— решение —. . .

—наблюдение —решение . . .

 

 

 

 

 

Отметим, что впервые прямые методы,

 

основанные на

методе стохастической аппроксимации, предлагались

в [46]

и [63]. Для решения более широкого

класса

задач

прямые

методы, основанные на понятиях

обобщенного градиента,

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

квазиградиента

 

и доверительного интерва­

ла, предлагались

в работах [33],

[54]

и [62].

 

 

Г . Понятия,

определения

и

примеры.

В дальнейшем

часто будет-использован следующий результат, полученный

В [12].

 

 

Если

яг (*'=1,

 

2, .

. ., п)—незави­

Предположение 6.1.

 

симые случайные величины с соответствующими М(щ )

( i=

1, 2, . .

.,

я), и для каждого М (щ )

найден

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

интервал

с

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

о

1

I

 

— а

вероятность

ф =

1 ------------,

то

 

 

 

 

 

п

 

 

 

 

одновременного накрытия

этих

интервалов,

соответствую­

щих /И(я,- ), не меньше чем а.

 

 

 

 

 

 

Определение 6.1. Два случайных множества R и

на­

зовем я-доверительными множествами

для

/?, если выпол­

няется соотношение

 

 

 

 

 

 

 

P {R < R < R \ > o ..

Для примера рассмотрим множество

27

$=\xl2iM (aj)Xj^:M (aail),

xy>0,

7 = 1 ,

2,

. .

n\

 

j= i

 

 

 

 

 

 

 

 

 

 

{предполагается,

что величины ay

(/— 1,

2, .

.

л) незави­

симы).

Используя

формулы (2.4)

и

(2.5),

по

некоторому

числу

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

для М{аЛ

 

 

 

 

 

 

|

^

 

 

 

с

вероятностью ?7—

1 ----------- .

 

 

 

Построим

множества

 

 

л + 1

 

 

 

 

 

 

 

 

 

 

 

/?=(Х|2

ауХу<а/г+1,

Х > 0 )

 

 

 

 

 

и

 

 

1

 

~

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Я Н * 1 2

аЛ -<««+1,

* > 0 ) .

 

 

 

 

 

 

 

У»1

-

 

 

 

 

 

 

 

Нетрудно видеть,

что с учетом предположения

6.1, множест­

ва R и R

являются a-доверительными

множествами

для

7?, где а=^П £/ . у-i

Пусть /—решение некоторой задачи стохастического

программирования (задача Л), а / и /—решения стохасти­

ческих задач Л и Л.

Определение 6.2. Задачи Л и Л назовем а-доверитель-

ными задачами для Л, если выполняется неравенство

Р(_/</<7|>а.

Для ясности рассмотрим задачу максимизации функции

f ( X ) = i с, X J j^l

при условиях

2 M (a J )-*/ ^ Щ а п+1),

j ” 1

Ху > 0 , / — 1, 2, . . ., л,

28

Смотрите также файлы