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

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

ОГЛАВЛЕНИЕ

Следующая >>

его длины к числу содержащихся в нем дуг. Для решения этой
задачи используется алгоритм 5:
1. Определяем произвольный контур. Пусть L – длина этого
контура, k – число его дуг. Вычисляем lср = L / k и добавляем (-lср) к
длинам lij всех дуг.
Затем определяем контур отрицательной длины, повторяем
шаг 1, и т.д. до тех пор, пока на очередном шаге таких контуров не
найдется.
Так как на каждом шаге длины всех дуг изменялись на одно и
то же число, то на последнем шаге длина каждой дуги равна lij – ?,
где ? – суммарное изменение длины каждой дуги на всех шагах.
Значение ? равно минимальной средней длине дуг контуров
графа. При этом контуром минимальной средней длины является
контур, определенный на предпоследнем шаге.
Путь максимальной эффективности. Пусть задана сеть, в
которой для каждой дуги (i; j) определены два числа (Эij; Sij), ин-
терпретируемые как эффект при осуществлении соответствующей
операции – Эij и затраты на эту операцию – Sij. Эффективность K(µ)
?
пути µ определяется как отношение его эффекта Э(µ) = Эij к
µ

?s
затратам S(µ) = , то есть K(µ) = Э(µ) / S(µ). Задача заключа-
ij
µ

ется в поиске пути µ* максимальной эффективности: K(µ) > max.
Если решение K* = K(µ*) этой задачи известно, то по опреде-
лению K* выполнено:
(8) Э(µ) – K* S(µ) ? 0 ? µ

13
Следовательно, задача свелась к поиску минимального значе-
ния K*, для которого имеет место (8). Другими словами, необходи-
мо найти минимальное K*, такое, что все пути (длина которых
определяется как lij(K*) = Эij – K* Sij) в сети имеют неположитель-
ную длину (неравенство (8) должно выполняться, в том числе, и
для пути максимальной длины).
Алгоритм 6. 1) Положим K* = 0. Находим путь µ1 максималь-
ной длины. Положим K1 = Э(µ1) / S(µ1) (заметим, что при K = K1
длина пути µ(K1) равна нулю).
2) Находим максимальный путь µ2 при K = K1. Если длина пу-
ти µ2, которую мы обозначим L(K1), равна нулю, то задача решена.
Если L(K1) > 0, то вычисляем K2 = Э(µ2) / S(µ2) и находим макси-
мальный путь µ2 при K = K2 и т.д.
Путь максимальной эффективности с учетом штрафов.
Пусть для каждой дуги (n + 1)-вершинной сети заданы два числа:
эффект Эij и время tij. Каждый путь µ из начальной вершины в
конечную вершину характеризует некоторый процесс (проект).
Под продолжительностью пути будем понимать сумму времен его
дуг. Если продолжительность процесса отличается от заданного
времени T, то налагаются штрафы ?(µ), пропорциональные откло-
? (T ? T ( µ )), T ( µ ) ? T
нению, то есть: ?(µ) = ? , где коэффициенты ?
?
? ? (T ( µ ) ? T ), T ? T ( µ )
и ? могут быть как положительными, так и отрицательными.
Задача заключается в том, чтобы найти путь µ*, максимизи-
рующий разность между эффектом и штрафами, то есть
µ* = arg max [Э(µ) – ?(µ)].
µ

Обозначим lij(?) = Эij – ? tij, где ? – некоторый параметр, T(?) –
продолжительность оптимального пути при параметре ?, то есть
пути, имеющего максимальную длину, измеряемую в lij(?). Легко
показать, что с ростом ? величина T(?) не возрастает.
Обозначим T(?), T(?) – продолжительности оптимального пу-
ти при ? равном ? (соответственно, ?), µ(?), µ(?) – эти пути (для
их нахождения необходимо решить две задачи на поиск пути
максимальной длины). Рассмотрим шесть случаев (исходную
задачу можно разбить на две подзадачи – поиска максимума Э(µ) –
?(µ) при T(µ) ? T и при T(µ) ? T).

14
Пусть ? ? ?, тогда T(?) ? T(?) и:
1) если T(?) ? T(?) ? T, то µ(?) – оптимальное решение;
2) если T ? T(?) ? T(?), то µ(?) – оптимальное решение;
3) если T(?) ? T ? T(?), то, сравнивая µ(?) и µ(?) по длинам
l = Э – ?, выбираем путь, имеющий максимальную длину.
Пусть ? ? ?, тогда T(?) ? T(?) и:
4) если T(?) ? T(?) ? T, то µ(?) – оптимальное решение;
5) если T ? T(?) ? T(?), то µ(?) – оптимальное решение;
6) если T(?) ? T ? T(?), то задача не имеет эффективных мето-
дов решения (возможные подходы описаны в [7]).


3. Псевдопотенциальные графы

Полный, (n+1)-вершинный, симметричный граф называется
псевдопотенциальным, если длина его любого гамильтонова кон-
тура равна одному и тому же числу. Обозначим lij, i , j = 0 ,n –
длины дуг.
Известно [7, 8], что для того, чтобы граф был псевдопотенци-
альным, необходимо и достаточно существование чисел ?i, ?i,
i = 0,n , таких, что lij = ?j – ?i для всех i , j = 0,n ; а также, что
любой подграф псевдопотенциального графа является псевдопо-
тенциальным.

? (? )
j
Будем считать, что ?0 = 0. Обозначим M j ( µ ) = ? ? ik ?1
ik
k =1
– сумма длин первых j дуг гамильтонова контура µ, ?j = ?j – ?j.
Определим M(µ) = max Mj(µ).
1? j ? n

Известно [7, 8], что существует оптимальное решение задачи
(1) M(µ) > min ,
µ

в котором сначала идут вершины с ?i ? 0 в порядке возрастания
величин ?i, а затем вершины с ?i ? 0 в порядке убывания величин
?i.
Для доказательства этого утверждения обозначим
Mmin = min M(µ), а µ = (0, i1, i2, ... , in, 0) – оптимальный гамильто-
µ

15
нов контур (решение задачи (1)). Тогда для него имеет место сле-
дующая система неравенств:
?M min ? ? i1
?
?M min + ? i1 ? ? i2
?
(2) ?M min + ? i1 + ? i2 ? ? i3 .
?
?............................
?M min + ? i +.....+ ? i ? ? i
? n ?1
1

Если для некоторого индекса s ? {1, 2, ..., n} выполнено
? is ?1 ? 0, ? is ? 0, то из (2) следует справедливость соответствую-
щей системы неравенств для гамильтонова контура (0, i1, ..., is-
2, is, is-1, is+1, ..., in). Поэтому всегда существует оптимальное реше-
ние, в котором сначала обходятся вершины с положительными ?, а
затем с отрицательными ? (вершину i с ?i = 0 можно отнести в
любую группу).
Если ? is ?1 ? 0, ? is ? 0 и ? is ?1 > ? is , то из (2) следует справед-
ливость соответствующей системы неравенств для гамильтонова
контура (0, i1, ..., is-1, is, is+1, ..., in).
Наконец, если ? is ?1 ? 0, ? is ? 0 и ? is ?1 > ? is , то из (2) следует
справедливость соответствующей системы неравенств для гамиль-
тонова контура (0, i1, ..., is-1, is, is+1, ..., in). Докажем, например,
последнее утверждение. Из (2) получаем, что
s?2

?? ? ? is ?1 = ? is ?1 – ? is ?1 ,
Mmin + ij
j =1
s?2

?? + ? is ?1 ? ? i s = ? is – ? is .
Mmin + ij
j =1
Но тогда тем более имеет место:
s?2
?? i + ? is ?1 ? ? is , так как ? is ?1 ? 0,
Mmin + j
j =1
s?2
?? i + ? is + ? is ?1 ? ? i s ? ? is ?1 .
Mmin + j
j =1


16
Итак, пусть µ = (0, i1, i2, ... , in, 0) – контур, являющийся реше-
нием задачи (1), то есть
? i j ? 0, j = 1, 2, ..., s, причем ? i1 ? ? i2 ? ... ? ? i s ,
? i j ? 0, j = s + 1, ..., n, причем ? i s+1 ? ? i s +2 ? ... ? ? i n .
Тогда
? ??
? k
= max ? ? i1 , max? ? ik +1 ? ? ? i j ?? .
(3) M min
1? k < n ? ?
? ??
?
? ?
j =1

Частным случаем псевдопотенциального графа является по-
тенциальный граф, у которого длина любого гамильтонова конту-
ра равна нулю1. В частности, потенциальный граф обладает сле-
дующими свойствами:
- у потенциального графа длина любого контура равна нулю;
- для n-вершинного потенциального графа существуют числа
{?i}, такие, что lij = ?j – ?i, i, j = 1, n .
- у потенциального графа для любой вершины сумма длин за-
ходящих дуг по абсолютной величине равна сумме длин исходя-
щих дуг.


4. Задачи о максимальном потоке

Рассмотрим сеть из (n + 1) вершины. Пусть каждой дуге по-
ставлено в соответствие число cij, называемое пропускной способ-
ностью дуги (i; j).
Потоком x в сети называется совокупность чисел {xij}, где xij –
поток по дуге (i; j), удовлетворяющих условиям 0 ? xij ? cij,
? ?
xki , i ? 0, n. Величиной потока x называется
i, j = 0 , n , xij =
j k

?x ?x
?(x) = = .
0i in
i i




1
Потенциальный граф может рассматриваться как модель электрической
сети, а его свойства как теоретико-графовые аналоги законов Кирхгофа.
17
Задача о максимальном потоке заключается в определении
потока максимальной величины1.
Разрезом W в сети называется любое множество вершин, обя-
зательно содержащее выход и не содержащее вход. Пропускной
способностью C(W) разреза W называется сумма пропускных
способностей дуг, заходящих в разрез.
Известно [5, 7, 19], что величина любого потока не превышает
пропускной способности любого разреза (теорема Форда-
Фалкерсона).
Следовательно, если удастся найти поток, величина которого
равна пропускной способности некоторого разреза, то этот поток
максимален, а разрез минимален.
Алгоритм 7 (алгоритм Форда-Фалкерсона). Применение алго-
ритма проиллюстрируем примером сети, приведенной на рисунке
3, в которой пропускные способности всех дуг равны единице.
Шаг 0. Берем произвольный поток (например, поток
x01 = x12 = x25 = 1). Помечаем начальную вершину индексом «0».
Обозначим Z – множество помеченных вершин.
Общий шаг. Первое действие. Помечаем вершину j индексом
+i, если, во-первых, существует дуга (i; j), и, во-вторых, i ? Z,
j ? Z, xij < Cij.
Если в результате этого типа пометок мы пометили выход, то
поток можно увеличить хотя бы на единицу (если cij – целые чис-
ла). Двигаясь обратно, можно найти путь, поток по которому мож-
но увеличить. Однако, как видно из примера, этого недостаточно
для нахождения максимального потока.




1
Наиболее распространенной содержательной интерпретацией является
перевозка грузов из начальной вершины в конечную по дугам графа, где пропуск-
ная способность дуги характеризует максимальное количество груза, которое
по ней можно перевозить в единицу времени.
18
[-2] [+1]
1
1 4
1
1 [+4]
[0] 0
5
5
0
1
1

1 2
3 [+3]

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

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

ОГЛАВЛЕНИЕ

Следующая >>