<< Предыдущая

стр. 6
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

? ??
? ( i ,q )?Vq
q



n-й шаг. Присваиваем вершине n индекс

u n = max ? max u i k in ; max u i k in ; max v i k in ; ? . (6.3)
?( i,q )?Un ?
? ?
( i ,q )?Vn ( i ,q )?U n


Если какое-либо множество является пустым, то соответствующий максимум
в (6.1) – (6.3) равен 0 по определению.
Докажем, что индекс un определяет максимальный доход фирмы-
оператора среди всех обменных схем, включающих не более одной операции
с повышенным риском. Как и ранее, доказательство проведем по индукции.
Предварительно введем определение i-части обменной схемы.
Определение. i-частью обменной схемы, включающей элемент i,
называется начальная часть схемы, которой соответствует путь в сети ВО,
соединяющий вход 0 с вершиной i.
Заметим, что для любой допустимой обменной схемы, включающей
элемент i, ее i-часть может либо не иметь ни одной операции повышенного
риска, либо иметь только одну такую операцию. Соответственно, i-часть, не
имеющую операций повышенного риска, будем называть i-частью низкого
риска, а имеющую – повышенного риска.
Докажем сначала, что индекс ui > 0 (i ? n) равен количеству ресурса,
такому что участвуя в любой схеме с i-частью низкого риска элемент i отдает
не более ui единиц ресурса, и существует i-часть низкого риска, в которой

40
элемент i отдает ровно ui единиц ресурса. Соответственно, индекс vi > 0
(i ? n) равен количеству ресурса, такому что, участвуя в любой схеме с i-
частью повышенного риска, элемент i отдает не более vi единиц ресурса, и
существует i-часть повышенного риска, участвуя в которой элемент i отдает
ровно vi единиц ресурса.
Для вершины i = 0 это очевидно (u0 = v0 = a0). Предположим, что этот
факт имеет место для всех j < q. Докажем его для вершины q ? n. Очевидно,
что все q-части низкого риска должны заканчиваться дугами (i,q) ? Uq. Но
тогда выражение (6.1) определяет максимальное количество ресурса (не
более), которое отдает элемент q, участвуя в обменных схемах с q-частью
низкого риска. Очевидно, что, если uq > 0, то существует q-часть низкого
риска, участвуя в которой элемент q отдает ровно uq единиц ресурса. Далее,
все q-части повышенного риска состоят либо из i-части низкого риска и дуги
(i,q) ? Vq, либо из i-части повышенного риска и дуги (i,q) ? Uq.В обоих
случаях выражение (6.2) определяет количество ресурса, не более которого
отдает элемент q, участвуя в обменных схемах с q-частями повышенного
риска. Столь же очевидно, что существует q-часть повышенного риска,
участвуя в которой элемент q согласен отдать ровно vq единиц ресурса. Если
теперь проанализировать выражение (6.3), то по аналогии с предыдущим
анализом нетрудно показать, что любая обменная схема может состоять либо
из i-части низкого риска и операции (i,n) низкого риска (первое выражение в
квадратных скобках), либо из i-части низкого риска и операции (i,n)
повышенного риска (второе выражение в квадратных скобках), либо из i-
части повышенного риска и операции (i,n) низкого риска (третье выражение
в квадратных скобках). Следовательно, un определяет максимальный доход
оператора. Для определения оптимальной обменной схемы применяем
алгоритм обратного хода по аналогии с алгоритмом из параграфа 5.




41
Пример 6. Рассмотрим сеть из примера 5, в которой все операции с
обменными коэффициентами выше 2 и операция (4,5)имеют повышенный
риск (эти операции изображены на рис. 14 жирными дугами).

1 [8,0]
10
4 5
2 2
[10,10]
4
0 2 2
3
[4] 5
24
4 10 1,5
[15,24]
3 1
6 2
3
18 [0,18]
Рис. 14.


0 шаг. u0 = 4.
1 шаг. u1 = min (10, u0k01) = 8;
v1 = 0.
2 шаг. u2 = min (10, u1k12) = 10;
v1 = min (10, u0k02) = 10.
3 шаг. u3 = 0;
v3 = min (18, u0k03; u2k23) = 18.
4 шаг. u4 = min (24, u2k24) = 15;
v4 = min (24, max (u1k14, v3k34)) = 24.
5 шаг. u5 = max (u1k15, u4k45, v3k35) = 40.
Оптимальный путь, очевидно,
µ0 = (0, 1, 5).
Заметим, что описанный алгоритм можно обобщить на случаи, когда
допускается более одной операции повышенного риска. Достаточно ввести
не 2 индекса в вершине, а (m+1), где m – число операций повышенного
риска, которое допускается в обменной схеме.


42
7. Управление риском

Выше уже отмечалось, что риск операций можно уменьшить, применяя
различные компенсационные меры, то есть риском можно управлять.
Безусловно, снижение риска требует затрат, уменьшающих доход от
обменной схемы. Рассмотрим задачу выбора оптимальной обменной схемы
(по критерию дохода) с учетом затрат на снижение риска до требуемого
(приемлемого) уровня.
Обозначим через rij затраты на снижение риска операции (i,j) до
приемлемого уровня. Тогда доход оператора от реализации обменной схемы
µ будет равен
Д = K(µ)?x(µ) - R(µ),

? r - суммарные затраты на снижение риска. Ограничим число
где R(µ) = ij
()
i , j ?µ


операций повышенного риска (выше, чем приемлемый риск) в обменной
схеме. Обозначим это число через m. Для случая m = 1 опишем алгоритм
множественной индексации, обобщающий алгоритм двойной индексации,
описанный в параграфе 6. Идею алгоритма поясняет рис.15.

1
[u1; v11(s11); v12(s12)]
a1
k14

k24 4
2
[u2; v21(s21)] a4
a2
k34
3
[u3; v31(s31)]
a3
Рис. 15.

Индекс ui определяет максимальное количество ресурса, которое
может отдать элемент i, участвуя в обменных схемах с i-частью низкого
риска. Индексы vij(sij) определяют максимальное количество ресурса,
43
которое может отдать элемент i, участвуя в обменных схемах с i-частью
повышенного риска с затратами на снижение риска равными sij. При этом vi1
> vi2 > vi3 и, соответственно, si1 > si2 > si3.
Зная индексы вершин 1, 2, 3 можно определить индекс вершины 4.
Действительно,
u4 = min[a4; max(u1k14; u3k34)],
v41 = min[a4; max(u2k24; v11k14; v31k34)].
Предположим, что v41 = v11k14. Тогда s41 = s11. Далее определяем
v42 = min[a4; max(u2k24; v12k14; v31k34)].
Предположим, что v42 = u2k24 < v41. Тогда, если r24 < s11, то помечаем вершину
4 вторым индексом v42, s42 = r24. Действуем таким образом, пока не проверим
все допустимые комбинации индексов вершин 1, 2, 3.
Пример 7. Рассмотрим сеть ВО из примера 6. Затраты на снижение
риска до приемлемого уровня для операций с повышенным риском указаны
в круглых скобках у соответствующих дуг (см. рис. 16).

1 [8]
10
5(8)
2 2 4(3)

2 [10]
0 3(3) 4 2(2)
5
24
4 10 1,5
[15,24(3),18(2)]
3(2) 1
6(7)
2
3
[0,18(2)] 18
Рис. 16.

0 шаг. u0 = 4.
1 шаг. u1 = min (10, 4?2) = 8;
2 шаг. u2 = min (10, 8?12) = 10;
v21 = min (10, 4?3) = 10.
Так как v21 = u2, то индекс v21 не присваиваем.

44
3 шаг. u3 = 0;
v3 = min (18, max (4?6; 10?3)) = 18, s31 = 2.
В данном случае s31 = 2, так как обе 3-части (0,1,2,3) и (0,3) обеспечивают
количество ресурса больше 18. Поэтому выбираем 3-часть с меньшими
затратами на снижение риска.
4 шаг. u4 = min (24, 10?1,5) = 15;
v41 = min (24, max (8?4, 18?1)) = 24.
В данном случае s41 = r14 = 3, так как 4-часть (0, 1, 2, 3, 4) не обеспечивает
количество ресурса 24, хотя и имеет меньшие затраты на снижение риска.
v42 = min (24, 18?1) = 18, s42 = 2.
5 шаг. Окончательно имеем:
u5 = max (8?5-8, 15?2-2, 18?2-2) = 34.
Этот максимум обеспечивает обменная схема (0, 1, 2, 3, 5).
Этот алгоритм можно обобщить и на случай m > 1. Однако система
множественной индексации становится при этом излишне громоздкой.
Рассмотрим метод ветвей и границ для решения задачи управления
риском. Обозначим через Q множество операций с повышенным риском и
определим s = min rij . Примем, что затраты на снижение риска равны s для
(i , j )?Q

всех операций множества Q и решим задачу выбора оптимальной по
критерию дохода обменной схемы для этого случая. При одинаковых
затратах на снижение риска задача решается методом множественной
индексации, описанным в параграфе 6 (при небольшой его модификации,
учитывающей затраты s при индексации конечной вершины n). Очевидно,
что полученное решение дает оценку сверху для исходной задачи.
Определяем в полученной обменной схеме операцию с повышенным риском
и максимальными затратами на его снижение и рассматриваем два
подмножества обменных схем. В первом подмножестве эта операция
присутствует в сети ВО, а во втором – нет. Сравнивая оценки сверху для

45
обоих подмножеств, выбираем подмножество с большей оценкой и т.д.,
согласно схеме ветвей и границ. Дадим иллюстрацию метода ветвей и
границ на сети ВО из примера 7.
Пример 8. Определяем s = min rij = 2.
(i , j )?Q

1 шаг. Решаем задачу алгоритмом двойной индексации, рис. 17.


1 [8,0]
10
4 5
2 2
[38]
[10,10]
4
0 2 2
3
[4] 5
24
4 10 1,5
[15,24]
3 1
6 2
3
18 [0,18]

Рис. 17.

Поясним получение индекса u5 = 38. В алгоритме двойной индексации
этот индекс был равен 40. Вычитая затраты s = 2 на снижение риска
операции (1,5), получаем 38. Фактические затраты на снижение риска
операции (1,5) равны 8. Поэтому фактический доход равен 32.
2 шаг. Рассматриваем сеть ВО без операции (1,5) (рис. 18).

1 [8,0]
10
4
2 2
[34]
[10,10]
4
0 2 2
3
[4] 5
24
4 10 1,5

<< Предыдущая

стр. 6
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>