Файл: Экономикоматематические методы и модели.pdf

107
Шаг k: помечаем вершину k индексом λ
k
= min (λ
i
+ l
ik
) при i < k .
Индекс выхода λ
n
будет равен длине кратчайшего пути. На рис. 6.2 пока- зан пример применения алгоритма для определения кратчайшего пути (чис- ла у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).
Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь μ = (0; i
1
; i
2
; ...; i
n-1
; n), такой, что
l
i
n-1
n
= λ
n
– λ
n
-1
и т.д.
Рис. 6.2. Поиск кратчайшего пути
Следующий алгоритм дает возможность определять кратчайший путь в общем случае (то есть при произвольной нумерации вершин).
Алгоритм 2 (алгоритм Форда)
Шаг 0: помечаем нулевую вершину индексом l
0
= 0, все остальные вер- шины индексами l
i
= + ∞, i = 1,…, n;
Шаг k: рассматриваем все дуги. Для дуги (i; j), если λ
j
– λ
i
>l
ij
, то вычис- ляем новое значение 'λ
j
= λ
i
+ l
ij
Индексы устанавливаются за конечное число шагов. Обозначим {λ
i
*
} – установившиеся значения индексов, которые обладают следующим свой- ством: величина λ
i
*
равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется мето- дом обратного хода.
Если длины всех дуг не отрицательны, то для поиска кратчайшего пути применим следующий алгоритм.
Алгоритм 3
Шаг 0: помечаем нулевую вершину индексом λ
0
= 0;
Шаг k: пусть уже помечено некоторое множество вершин. Обозначим Q множество непомеченных вершин, смежных с помеченными. Для каждой вершины k є Q вычисляем величину ξ
k
= min (λ
k
+ l
ki
), где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину
k, для которой величина ξ
k
минимальна, индексом λ
k
= ξ
k
Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n. Длина кратчайшего пути равна λ
n
, а сам кратчайший путь опреде- ляется так, как это было описано выше.
Электронный архив УГЛТУ

108
Запишем задачу о кратчайшем пути как задачу линейного программиро- вания (ЛП). Пусть x
ij
= 0, если дуга (i; j) входит в путь
3
μ, x
ij
= 0, если дуга (i;
j) не входит в путь μ, i, j = 0,…,n .
Задачу о минимальном пути можно записать в виде:
( ) ∑
; (6.1)
∑
∑
(6.2)
∑
∑
̅̅̅̅̅̅̅̅̅̅
(6.3)
Любое решение системы (6.2) - (6.3) определяет путь в сети без контуров
(но не в сети с контурами). Пусть все контуры имеют строго положительную длину, т. е. нет контуров отрицательной и нулевой длины. Тогда решение задачи (6.1) - (6.3) определяет путь кратчайшей длины.
Ограничение (6.2) отражает требование того, что в искомом пути из входа выходит одна дуга и в выход заходит одна дуга. Ограничение (6.3) обеспечивает равенство числа заходящих и выходящих в любую промежуточную вершину дуг.
Сформулируем задачу ЛП, двойственную задаче (6.1) - (6.3), поставив в соответствие ограничениям (6.2) двойственные переменные λ
0
и λ
n
, а ограни- чениям (6.3) – двойственные переменные {λ
i
}, i = 1,…, n – 1:
λ
n
– λ
0
→ max (6.4)
λ
j
– λ
i
≤ l
ij
, i, j = 0,…, n . (6.5)
По теореме двойственности линейного программирования [13], для оп- тимальных решений задач (6.1) - (6.3) и (6.4) - (6.5) значения целевых функ- ций совпадают.
Задача (6.4) - (6.5) называется задачей о потенциалах вершин графа.
Общая ее формулировка такова: найти потенциалы вершин {λ
i
}, удовлетво- ряющие системе неравенств (6.5) и максимизирующие некоторую функцию
F(λ), где λ = (λ
0
, λ
1
, ..., λ
n
). Примером является задача о ближайших потенциа- лах, в которой F(λ) = ∑
|
|
где
{
} могут интерпретироваться как же- лательные потенциалы.
Аналогично задаче о кратчайшем пути формулируется и решается зада- ча о максимальном пути – достаточно изменить знаки дуг на противополож- ные и решить задачу о кратчайшем пути. Для существования решения задачи
3
Будем считать, что имеются две дуги между каждой парой вершин, так как, если их нет в исходном графе, то, положив их длину равной бесконечности, мы заведомо исключим их из решения.
Электронный архив УГЛТУ

109 о максимальном пути необходимо и достаточно отсутствия контуров поло- жительной длины.
В задаче поиска пути максимальной надежности длины дуг интерпрети- руются, например, как вероятности того, что существует связь между соот- ветствующими двумя пунктами. При замене длины дуг их логарифмами, взя- тыми с обратными знаками, получается, что путь максимальной надежности в исходном графе будет соответствовать кратчайшему пути в новом графе.
К таким же сложным задачам относятся и задачи поиска кратчайших или длиннейших путей или контуров, проходящих через все вершины графа
(элементарный путь (контур), проходящий через все вершины графа, называ- ется гамильтоновым путем (контуром)). Классическим примером задачи по- иска гамильтонова контура является задача коммивояжера, заключающаяся в следующем. Коммивояжер (бродячий торговец) должен посетить n городов, побывав в каждом ровно один раз, и вернуться в исходный пункт своего пу- тешествия. Заданы неотрицательные длины дуг, интерпретируемые как рас- стояние между городами или стоимость проезда. Требуется найти гамильто- нов контур минимальной длины (в графе из n вершин существует n! (число перестановок) гамильтоновых контуров).
Алгоритмы решения задачи о кратчайшем пути позволяют решать ши- рокий класс задач дискретной оптимизации. В качестве примера приведем задачу целочисленного линейного программирования – задачу о ранце (о рюкзаке), к которой сводятся многие практически важные задачи определе- ния оптимальной комбинации факторов при ограничениях на общий вес, площадь, объем, финансирование и т.д.
Задача о ранце. Пусть имеется n предметов, которые могут быть полез- ны в походе. Полезность i-го предмета оценивается числом a
i
, вес предмета
(или его объем) – b
i
. Суммарный вес, который может нести турист (объем рюкзака), ограничен величиной R. Требуется найти набор предметов, обла- дающий максимальной суммарной полезностью и удовлетворяющий ограни- чению.
Обозначим x
i
– переменную, принимающую значение ноль (если i-й предмет не кладется в ранец) или единица (если i-й предмет кладется в ра- нец). Тогда задача о ранце имеет вид:
∑
(6.6)
∑
(6.7)
Верхняя оценка числа возможных комбинаций – 2
n
. Однако для решения задачи о ранце существует эффективный алгоритм – метод динамического
программирования. При его использовании строится сеть (см. примеры в
[12]) по следующим правилам. По оси абсцисс будем последовательно от- кладывать номера предметов, по оси ординат – их вес. Из каждой точки
Электронный архив УГЛТУ

110
(начиная с точки (0; 0)) выходят две дуги – горизонтальная (соответствующая альтернативе «не брать предмет») и наклонная (соответствующая альтерна- тиве «взять предмет»), вертикальная проекция которой равна весу предмета.
Длины наклонных дуг положим равными ценности предметов, длины гори- зонтальных дуг – нулю. Полученная сеть (конечная вершина является фик- тивной и вес любой дуги, соединяющей ее с другими вершинами, равен ну- лю) обладает следующими свойствами: любому решению задачи (6.6) - (6.7) соответствует некоторый путь в этой сети; любому пути соответствует неко- торое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины.
Задача поиска контура минимальной длины решается следующим обра- зом. Если известно, что искомый контур содержит некоторую вершину, то нужно определить кратчайший путь от этой вершины до нее же, применяя описанные выше алгоритмы. Так как в общем случае контур минимальной длины может проходить через любую вершину графа, то находятся контуры минимальной длины, проходящие через каждую вершину, и среди них выби- рается кратчайший.
Более простым является алгоритм 4: берется первая вершина (в произ- вольном их упорядочении) графа и рассматривается сеть, в которой эта вер- шина является одновременно конечной и начальной вершиной. Для этой сети
(применением описанного выше алгоритма) ищется путь μ
1
минимальной длины L (μ
1
). Затем первая вершина отбрасывается, и минимальный путь μ
2
ищется для сети, в которой начальной и конечной вершиной является вторая вершина. Затем отбрасывается вторая вершина и т.д. для всех вершин исход- ного графа, для которых существует контур, проходящий через них и через вершины с большими номерами. Контуром минимальной длины будет контур μ
min
, длина которого равна L (μ
min
) = = min {L(μ
1
), L(μ
2
), ,..., L(μ
n
)}.
Задача поиска контура минимальной средней длины заключается в по- иске контура, для которого минимально отношение его длины к числу со- держащихся в нем дуг.
Для решения этой задачи используется алгоритм 5:
1. Определяем произвольный контур. Пусть L – длина этого контура, k – число его дуг. Вычисляем l
ср
= L / k и добавляем (-l
ср
) к длинам l
ij
всех дуг.
Затем определяем контур отрицательной длины, повторяем шаг 1, и т.д. до тех пор, пока на очередном шаге таких контуров не найдется.
Так как на каждом шаге длины всех дуг изменялись на одно и то же чис- ло, то на последнем шаге длина каждой дуги равна l
ij
– h, где h – суммарное изменение длины каждой дуги на всех шагах.
Значение h равно минимальной средней длине дуг контуров графа. При этом контуром минимальной средней длины является контур, определенный на предпоследнем шаге.
Электронный архив УГЛТУ

111
Путь максимальной эффективности. Пусть задана сеть, в которой для каждой дуги (i; j) определены два числа (Э
ij
; S
ij
), интерпретируемые как эф- фект при осуществлении соответствующей операции – Э
ij
и затраты на эту операцию – S
ij
. Эффективность K(μ)пути μ определяется как отношение его эффекта Э(μ) = ∑
к затратам S(μ) = ∑
, то есть K(μ) = = Э(μ) / S(μ).
Задача заключается в поиске пути μ
*
максимальной эффективности:
K(μ)→max.
Если решение K
*
= K(μ
*
) этой задачи известно, то по определению K
*
выполнено:
Э(μ) – K
*
S(μ) ≤ 0
μ . (6.8)
Следовательно, задача свелась к поиску минимального значения K
*
, для которого имеет место (6.8). Другими словами, необходимо найти минималь- ное K
*
, такое, что все пути (длина которых определяется как l
ij
(K
*
) = Э
ij
–
K
*
S
ij
) в сети имеют неположительную длину (неравенство (6.8) должно вы- полняться, в том числе, и для пути максимальной длины).
Алгоритм 6
1. Положим K
*
= 0. Находим путь μ
1
максимальной длины. Положим K
1
=
Э(μ
1
) / S(μ
1
) (заметим, что при K = K
1
длина пути μ(K
1
) равна нулю).
2. Находим максимальный путь μ
2
при K = K
1
. Если длина пути μ
2
, кото- рую мы обозначим L(K
1
), равна нулю, то задача решена.
Если L(K
1
) > 0, то вычисляем K
2
= Э(μ
2
) / S(μ
2
) и находим максимальный путь μ
2
при K = K
2
и т.д.
Путь максимальной эффективности с учетом штрафов. Пусть для каждой дуги (n + 1) – вершинной сети заданы два числа: эффект Э
ij
и время
t
ij
. Каждый путь μ из начальной вершины в конечную вершину характеризует некоторый процесс (проект). Под продолжительностью пути будем понимать сумму времен его дуг. Если продолжительность процесса отличается от за- данного времени T, то налагаются штрафы χ(μ), пропорциональные отклоне- нию, т. е. χ (μ) равно:
{
( ( ) ( )
( ( ) ( )
(6.9) где коэффициенты α и β могут быть как положительными, так и отрицатель- ными.
Задача заключается в том, чтобы найти путь μ
*
, максимизирующий раз- ность между эффектом и штрафами, то есть μ
*
= arg max [Э(μ) – χ(μ)].
Обозначим l
ij
(λ) = Э
ij
– λt
ij
, где λ – некоторый параметр, T(λ) –
продолжительность оптимального пути при параметре λ, т. е. пути, имеюще- го максимальную длину, измеряемую в l
ij
(λ). Легко показать, что с ростом λ
величина T(λ) не возрастает.
Обозначим T(α), T(β) – продолжительности оптимального пути λ при β
равном α (соответственно, β), μ(α), μ(β) – эти пути (для их нахождения необхо-
Электронный архив УГЛТУ

112 димо решить две задачи на поиск пути максимальной длины). Рассмотрим шесть случаев (исходную задачу можно разбить на две подзадачи – поиска мак- симума Э(μ) –χ(μ) при T(μ)

T и при T(μ)

T).
Пусть α
β, тогда T(β)

T(α) и:
1) если T(β)

T(α)

T, то μ(β) – оптимальное решение;
2) если T

T(β)

T(α), то μ(α) – оптимальное решение;
3) если T(β)

T

T(α), то, сравнивая μ(α) и μ(β) по длинам l = Э – χ, вы- бираем путь, имеющий максимальную длину.
Пусть α

β, тогда T(β)

T(α) и:
4) если T(α)

T(β)

T, то μ(β) – оптимальное решение;
5) если T

T(a)

T(β), то μ(α) – оптимальное решение;
6) если T(α)

T

T(β), то задача не имеет эффективных методов реше- ния (возможные подходы описаны в работе [7]).
6.3. Задачи о максимальном потоке
Рассмотрим сеть из (n + 1) вершин. Пусть каждой дуге поставлено в со- ответствие число c
ij
, называемое пропускной способностью дуги (i; j).
Потоком x в сетиназывается совокупность чисел {x
ij
}, где x
ij
– поток по дуге (i; j), удовлетворяющий условиям 0

x
ij

c
ij
,i, j = 0,…, n. Величиной по- тока x называется F(x) = ∑
∑
Задача о максимальном потоке заключается в определении потока мак- симальной величины.
Разрезом W в сети называется любое множество вершин, обязательно содержащее выход и несодержащее вход. Пропускной способностью C(W) разреза W называется сумма пропускных способностей дуг, заходящих в раз- рез.
Известно [18], что величина любого потока не превышает пропускной способности любого разреза (теорема Форда-Фалкерсона).
Следовательно, если удастся найти поток, величина которого равна про- пускной способности некоторого разреза, то этот поток максимален, а разрез минимален.