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

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

ОГЛАВЛЕНИЕ

Следующая >>

3 4 7
0 13 19 20
6
14

Рис. 9.




5
6

1 4 2 3 6
1 2 3 4 5

7
4
12
1
8
2 5
0 7 11
3
9
6
10

2 1 4
20
16 17 18
5
15
3 4
13 19
6
14

Рис. 10


33
Число вершин сети увеличилось почти в три раза. Зато теперь мы
можем применить алгоритм решения задачи, описанный в параграфе 3,
который особенно эффективен для случая правильной нумерации сети.
Рассмотрим еще один пример.
Пример 4. Рассмотрим сеть, приведенную на рис. 11.




2 3

0 5 6

1 4



Рис. 11.


Действуя согласно описанному алгоритму, мы рассматриваем две
подсети. Одна начинается с дуги (0,1), а другая – с дуги (0,2).
Рассмотрим дугу (0,1), помечая вершину 1 номером 1. Исключая
вершину 1, помечаем вершину 2 номером 2. В оставшейся сети нет ни одной
вершины без заходящих дуг. Исключая вершину 3 получаем сеть без
контуров. Наконец, рассматривая дугу (0,2)и исключая вершину 2, а затем 3,
мы получаем требуемую сеть без контуров, показанную на рис.12.
Заметим, что в данном случае подсеть с дугой (0,2) можно было бы
исключить, проведя дугу (0,2) в подсети с начальной дугой (0,1) (эта дуга
показана пунктиром на рис. 12). При этом мы получаем преобразованную
сеть с тем же числом вершин. Однако, если бы в исходной сети была дуга
(1,6) (показанная пунктиром на рис. 11), то такое преобразование уже не
допустимо.




34
1 3
1 3

2 5
2 4
0
4
5 6
10
2 3
6 7

5
8

4
9

Рис. 12.


Вообще, проблема построения сети без контуров, эквивалентной
исходной и имеющей минимальное число вершин является гораздо более
сложной.




35
5. Оптимизация обменных схем по доходу

Выше мы рассмотрели задачу определения обменной схемы по
критерию маргинальной прибыли.
Довольно часто в качестве критерия оптимальности выступает не
маргинальная прибыль, а доход, получаемый оператором при реализации
обменной схемы, то есть величина Д = K(µ)?x(µ). Например, если фирма
оператор получила за свою продукцию или услуги от заказчика не деньги, а
какую-либо продукцию, векселя или зачеты, то ее основная задача –
реализовать уже полученный ресурс с максимальным доходом. Опишем
алгоритм построения обменной схемы, оптимальной по критерию дохода.
Предполагаем, что вершины преобразованной сети ВО имеют правильную
нумерацию.
0 шаг. Присваиваем входной вершине индекс u0 = a0.
q-й шаг. Присваиваем вершине k индекс

u q = min ?a q ; max u jk jq ? (5.1)
? ?
? ?
j<q


(максимум, очевидно, берется по тем j, для которых существует дуга (j,q)).
Индекс вершины n будет равен максимальному доходу оператора.
Для обоснования алгоритма покажем, что индекс вершины j ? n равен
максимальному количеству ресурса, который можно получить от j-го
элемента. Докажем этот факт по индукции.
Для выходной вершины j = 0 это очевидно. Пусть этот факт имеет
место для всех вершин j < q. Докажем, что это справедливо и для вершины q.
Действительно, величина kjquj определяет максимальное количество ресурса,
которое отдает элемент q, получив от элемента j ресурс в количестве uj, а
значит выражение (5.1) определяет максимальное количество ресурса,
которое может отдать элемент q, то есть существует обменная схема, в
которой элемент q отдает uq единиц ресурса, и не существует обменной


36
схемы, в которой элемент q отдает ресурса больше, чем uq. Теперь очевидно,
что максимальный доход оператора будет равен
max u jk jn = u n .
j


Пример 5. Рассмотрим сеть ВО, показанную на рисунке 13.

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

Индексы вершин указаны в квадратных скобках. Максимальный доход
равен 48. Для того, чтобы определить оптимальную обменную схему,
модифицируем алгоритм обратного хода, описанный в параграфе 2 для
задачи определения пути с максимальным усилением. А именно, начиная с
вершины n определяем дугу (i,n), такую что
un = uikin.
Далее находим дугу (i2,i1), такую что
max u i k ii1 = u i2 k i2i1
i<i1


и т.д., пока на очередном шаге k мы не получим дугу (0,ik). Путь
(0,ik,ik-1, … ,i2,i1,n) и определит искомую оптимальную обменную схему. В
нашем примере
u5 = u4k45 = 48
max u i k i 4 = u1k14 = 32 .
i< 4


Следовательно, искомый оптимальный путь µ0 = (0,1,4,5), поток по этому
пути x0 = x01 = 3.

37
6. Учет риска

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

38
Наконец, допустимо включение в обменную схему операции с высоким
риском, если такая схема имеет высокую эффективность. Безусловно, в этом
случае высокорисковая операция особо контролируется, и обязательно
прорабатывается система компенсационных мер.
Рассмотрим методы определения оптимальных обменных схем в
случае, если допускаются среднерисковые и высокорисковые операции (не
более одной). Если число таких операций (со средним или высоким риском)
мало, то проще всего задачу решить методом перебора. А именно, включаем
в сеть ВО операцию повышенного риска (среднего или высокого) и
определяем оптимальную обменную схему. Затем исключаем эту операцию,
включаем другую и т.д., пока не рассмотрим все операции повышенного
риска. Сравнивая полученные схемы по критерию маргинальной прибыли
или дохода, определяем оптимальную схему.
При большом числе операций повышенного риска метод перебора
становится достаточно трудоемким. В этом случае целесообразно
разработать алгоритмы, не требующие перебора всех операций с
повышенным риском. Опишем один такой алгоритм для задачи выбора
оптимальной обменной схемы по критерию дохода.

Алгоритм двойной индексации
Обозначим Uq – множество (возможно, пустое) дуг, соответствующих
операциям с низким риском, заходящих в вершину q; Vq – множество
(возможно, пустое) операций с повышенным риском, заходящих в вершину
q.
0 шаг. Присваиваем входной вершине индекс u0 = v0 = a0.
1 шаг. Если дуга (0,1) ? U1 (операция с низким риском), то
присваиваем вершине 1 индексы
u1 = min(a1; a0k01) и v1 = 0.



39
Если дуга (0,1) ? V1 (операция повышенного риска), то присваиваем
вершине 1 индексы
u1 = 0 и v1 = min(a0; a0k01).
q-й шаг. Пусть получены индексы ui, vi, i < q.Присваиваем вершине q
индексы

u q = min ?a q ; max u i k iq ? , (6.1)
? ( i ,q )?Uq ?
? ?
? ?
v q = min ?a q ; max ? max v i k iq ; max u i k iq ?? .
? ( i ,q )?U ? (6.2)

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

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

ОГЛАВЛЕНИЕ

Следующая >>