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

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

ОГЛАВЛЕНИЕ

Следующая >>

в дугах будем считать поток, выходящий из начальной вершины). Имеем

25
ai
x (µ 0 ) = min .
Фi
i? n


Пусть минимум достигается в вершине q0. Эту вершину будем называть
насыщенной. Тогда имеет место:
Теорема 2. Путь µ0 определяет оптимальную схему обмена по
критерию маргинальной прибыли среди всех путей, проходящих через
насыщенную вершину.
Доказательство. Для всех путей, проходящих через вершину q0, поток
из вершины q0 не превышает a q 0 . Поскольку Фq0 равно максимальному

усилению среди всех путей, соединяющих начальную вершину с вершиной
q0, то минимальное количество ресурса, отдаваемое оператором не менее
a q0
x (µ 0 ) = .
Фq0

Далее, так как Ф n Ф q0 равно максимальному усилению среди всех путей,

соединяющих вершину q с конечной вершиной n, то оператор не может
получить доход больше, чем
Фn
? a q0 .
Фq0

Окончательно получаем, что маргинальная прибыль оператора составляет
a q0
(Ф n ? 1),
МП(µ 0 ) = Ф n ? x (µ 0 ) ? x (µ 0 ) =
Ф q0

и эта прибыль максимальна на множестве обменных схем, включающих
элемент q0. Теорема доказана.
Исключим вершину q0 и определим путь с максимальным усилением
для оставшейся сети. Пусть это путь µ1, его усиление K(µ1) и насыщенная
вершина q1. Соответствующая маргинальная прибыль равна
a q1
(K(µ1 ) ? 1)
МП1 =
Ф q1


26
и она максимальна среди всех путей, проходящих через вершину q1 и не
проходящих через вершину q0. Удаляем вершину q1 и снова определяем путь
с максимальным усилением в оставшейся сети, и т.д. Процедура
заканчивается, если насыщенной окажется вершина 0 или когда после
удаления очередной вершины qm в сети не останется ни одного пути,
соединяющего вход с выходом. Оптимальный путь по критерию
маргинальной прибыли это путь µl, такой что
аqj
а ql
(K(µ ) ? 1) .
(K (µ l ) ? 1) = max j
Фq l Фq j
0? j? m



Пример 2. Рассмотрим сеть, изображенную на рис. 3 (числа у дуг
равны обменным коэффициентам, числа внизу в вершинах равны количеству
ресурса, имеющегося у соответствующего элемента).

[2] 1
6
5
1,5 2 1
/2
[12]
[1]
4 1 2
0 2 3 5
3 20 10
[4] [4]
1
3 /4
3 1
4
4 [12]
Рис. 8
3.


1 шаг. Определяем путь с максимальным усилением. Индексы вершин
указаны в квадратных скобках, путь с максимальным усилением выделен
жирными дугами. Это путь µ0 = (0,2,4,5) с усилением K0 = 12. Определим
допустимый поток по этому пути
x0(µ0) = x02 = min (3; 20/4; 24/12) = 2.
Насыщенная вершина q0 = 4. Величина маргинальной прибыли составит


27
МП0 = 2(12 – 1) = 22.
2 шаг. Удаляем насыщенную вершину 4 и определяем путь с
максимальным усилением в оставшейся сети (рис.4).


[2] 1
6
5
1,5 2 1
/2
[10]
[4] [4]
[1]
4 1 2
0 2 3 5
3 20 10

Рис. 4.


Это путь µ1 = (0,2,3,1,5) с усилением K1 = 10. Определяем допустимый
поток по этому пути
x(µ1) = x02 = min (3; 20/4; 10/4; 6/2) = 2,5.
Насыщенная вершина q1 = 3, величина маргинальной прибыли
МП1 = (10 – 1)2,5 = 22,5.
3 шаг. Удаляем насыщенную вершину 3 и определяем путь с
максимальным усилением в оставшейся сети (рис.5).


[1,5] 1
6
5
1,5 2
[7,5]
[4]
[1]
4
0 2 5
3 20

Рис. 5.


Это путь µ2 = (0,1,5) с усилением K2 = 7,5. Определяем допустимый
поток по этому пути
x(µ2) = x01 = min (3; 6/1,5) = 3.
28
Насыщенная вершина q2 = 0, величина маргинальной прибыли
МП2 = 3(7,5 – 1) = 19,5.
Так как насыщенной оказалась входная вершина, процедура закончена.
Сравнивая МП0, МП1 и МП2 видим, что оптимальным по критерию
маргинальной прибыли является путь µ1 = (0,2,3,1,5) с величиной
маргинальной прибыли МП1 = 22,5.




29
4. Преобразование произвольной
сети к сети без контуров


Для того, чтобы применить описанный выше алгоритм к произвольной
сети, необходимо преобразовать ее к сети без контуров с усилением больше
Однако, это достаточно сложная задача. В этом параграфе
1.
рассматривается более простая задача построения сети без контуров, такой
что любому простому пути исходной сети соответствует один или несколько
путей в преобразованной сети и наоборот, любому пути преобразованной
сети соответствует один и только один простой путь исходной сети.
В основе алгоритма лежит процедура правильной нумерации вершин
графа без контуров. Дадим описание этой процедуры.
1 шаг. Исключаем вершину 0 и все исходящие из нее дуги.
2 шаг. В полученной сети ищем вершину без заходящих дуг и
исключаем ее вместе с исходящими дугами. Эта вершина получает номер 1.
Далее процедура повторяется, то есть мы снова находим вершину без
заходящих дуг, присваиваем ей очередной номер, исключаем и т.д.
Очевидно, что если в сети имеются контуры, то на каком-либо шаге
процедуры мы не найдем ни одной вершины без заходящих дуг. В этом
случае находим все вершины из множества оставшихся, в которые заходят
дуги, исходящие из уже исключенных вершин. Рассматриваем каждую из
этих вершин. Пусть, например, это вершина j. Тогда исключаем все дуги,
заходящие в вершину j, и продолжаем процедуру правильной нумерации для
оставшейся сети и т.д.
Пример 3. На рис. 6 приведена сеть ВО, состоящая из восьми вершин.
Если исключить вершину 0 вместе с дугами (0,1), (0,2), (0,3), то легко
убедиться, что в оставшейся сети нет ни одной вершины без заходящих дуг.
Поэтому рассматриваем три варианта: удаление вершины 1, вершины 2 и
вершины 3, поскольку в каждую из них идет дуга из вершины 0.
30
1 4




0 2 5 7




3 6

Рис. 6.


1. Исключаем вершину 1 со всеми инцидентными ей дугами.
Оставшаяся сеть также не имеет ни одной вершины без заходящих дуг.
Рассматриваем вершину 4 (это единственная вершина, в которую заходит
дуга из исключенных вершин).
Исключаем вершину 4 с инцидентными дугами. Оставшаяся сеть опять
не имеет вершин без заходящих дуг. Рассматриваем вершины 2 и 7. Вершина
7 является конечной, и поэтому для нее процедура закончена. Исключаем
вершину 2 со всеми инцидентными дугами. Оставшаяся сеть не имеет
контуров.
Окончательно ветвь с дугой (0,1) имеет вид, изображенный на рис. 7
(числа внизу указывают правильную нумерацию вершин).

5
6

1 4 2 3 6
0 7
1 2 3 4 5


Рис. 7.



31
2. Исключаем вершину 2 с инцидентными дугами. Получили сеть без
контуров, допускающую правильную нумерацию, изображенную на рис. 8
(правильная нумерация вершины 2 равна 7, так как последний номер вершин
сети на рис. 7 равен 6).


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

Рис. 8.


3. Удаляем вершину 3 с инцидентными дугами, помечая ее номером
13. Вершина 6 оставшейся сети не имеет заходящих дуг. Помечаем ее
номером 14 и исключаем вместе с исходящими дугами. Теперь вершина 5 не
имеет заходящих дуг. Помечаем ее номером 15 и исключаем вместе с
исходящими дугами. В оставшейся сети нет ни одной вершины без
заходящих дуг. Рассматриваем две вершины, в которые заходят дуги из
исключенных вершин. Это вершины 2 и 4. Рассматриваем вершину 2.
Помечаем вершину 2 номером 16 и исключаем вместе с инцидентными
дугами. Оставшаяся сеть не имеет контуров. Помечаем вершины 1 и 4
соответственно номерами 17 и 18.
Рассматриваем вершину 4, помечая ее номером 19. Поскольку из
вершины 4 в оставшейся сети в вершину 7 идет только один путь (точнее
дуга (4,7)), то процедура закончена. Помечаем вершину 7 номером 20. Эта
сеть приведена на рис. 9.
Окончательный вид преобразованной сети приведен на рис. 10.

32
2 1 4
16 17 18
5
15

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

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

ОГЛАВЛЕНИЕ

Следующая >>