Математическая экономика

Подграф исходного графа G = (X , U ) – это граф, в который входит некоторая часть X 0 X вершин графа G вместе с дугами из U , соеди-

няющими эти вершины. Частичным графом по отношению к исходному графу G называют граф, содержащий некоторую часть дуг U0 U вместе

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

Примером пути в графе G на рис. 4.2, а может служить последовательность (u1, u4, u3) .

Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Конечный путь, образованный некоторой последовательностью дуг (u1, u2 ,..., uk ) и проходящий через вершины

(xs , x p , xr , xq ,..., x f , xh , xt ) , называется контуром, если в нем начальная вершина xs совпадает с конечной xt . В графе G на рис. 4.2, а контур об-

разуют дуги (u4 , u3, u5 ) .

Введенным для ориентированных графов понятиям пути и контура в неориентированных графах соответствуют аналогичные понятия цепи и цикла [18].

91

Важной характеристикой графов является связность. В неориентированном графе она означает возможность соединения любых двух вершин некоторой цепью. Если граф не удовлетворяет этому условию (не является связным), то его всегда можно разбить на связные подграфы, называемые компонентами связности. Аналогично определяют связность ориентированного графа, игнорируя при этом направленность дуг. Более жестким является условие так называемой сильной связности ориентированного графа, предполагающее существование пути, идущего от xs и xt для лю-

бых вершин xs , xt X [28].

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

§ 4.2. Задача о кратчайшем пути в графе

Пусть дан некоторый связный ориентированный граф G = (X , U ), каждой дуге uk = (xi , x j ) U которого приписано число (вес) сij ≥ 0 , на-

зываемое обобщенной длиной этой дуги. При этом граф можно характеризовать и задавать матрицей С, в которой на пересечении i-й строки и j-го столбца записывается соответствующее число (длина) сij при наличии ду-

ги, направленной от xi к x j , и записывается ∞ при отсутствии такой дуги.

Пусть в графе заданы две вершины s и t. Рассмотрим некоторый путь из s к t. Длиной этого пути называют число, равное суммарной длине дуг, входящих в этот путь. Путей из s в t может быть несколько. Путь, имеющий наименьшую длину из всех путей, ведущих от s к t, называется кратчайшим путем из s в t , и его длина называется расстоянием от s до t. Отыскание такого пути в заданном графе называется задачей о кратчайшем пу-

ти [18, 21, 29, 36].

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

92

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

Одним из наиболее эффективных методов решения задачи о кратчайшем пути в графе является так называемый метод (алгоритм) Дейкстры [21, 29, 36]. Он состоит в приписывании вершинам графа специальных весов, называемых метками.

Метка l(xi ) произвольной вершины xi представляет собой число,

оценивающее верхнюю границу длины пути от заданной начальной вершины s к вершине xi . Это означает, что истинная длина пути d(s, xi ) не

превышает l(xi ) . Алгоритм состоит в изменении меток вершин на каждой

итерации по определенному правилу. От итерации к итерации метки уменьшаются либо остаются неизменными. На каждой итерации ровно одна метка принимает значение, уменьшить которое нельзя. Она объявляется постоянной и далее уже не меняется. Эта метка дает точную длину кратчайшего пути от s к вершине с этой меткой. Когда все вершины получат постоянные метки, процесс вычислений заканчивается. Полученные метки вершин дают длины кратчайших путей от заданной вершины s до каждой из остальных вершин графа.

Расстановка и преобразование меток осуществляется следующим образом [21].

Шаг 1 (присвоение меткам начальных значений). Начальной вершине s приписывается метка l(s) = 0, и она объявляется постоянной. Всем ос-

тальным вершинам xi ≠ s приписываются временные метки l(xi ) = ∞. Полагаем p = s и переходим к следующему шагу.

Шаг 2 (обновление меток). Для всех вершин xi , связанных дугами ( p, xi ) с вершиной p и метки которых временные, изменяются метки по следующему правилу: вместо метки l(xi ) записывается метка, равная наименьшему из двух чисел: l(xi ) и l( р) +с( р, хi ) . Кратко эту замену метки можно записать следующим образом:

Шаг 3 (превращение метки в постоянную). Среди всех вершин xi с временными метками выбирается такая вершина x*i , для которой l(xi*) = min[l(xi )]. Метка этой вершины становится постоянной, а p = xi*.

93

Шаг 4. Если p совпадает с заданной конечной вершиной t, то полученная постоянная метка этой вершины l(t) дает длину искомого кратчай-

шего пути из s в t. Решение закончено (останов). Если же p ≠ t , то следует

перейти к шагу 2.

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

Шаг 4, а (проверка наличия временных меток). Если все вершины имеют постоянные метки, то эти метки дают длины искомых путей. Решение закончено (останов). Если же имеется хотя бы одна временная метка, то следует перейти к шагу 2.

Как указывалось выше, получаемая постоянная метка каждой вершины xi равна длине кратчайшего пути от s к xi . Сами пути можно найти,

пользуясь соотношением

где xi' – вершина, непосредственно предшествующая вершине xi в крат-

чайшем пути от s к xi , а l(xi' ) и l(xi ) – полученные постоянные метки этих вершин. Полагая сначала xi = t и пользуясь (4.2), можно найти предшест-

вующую t некоторую вершину xi' = p . Затем, положив xi = p и пользуясь

(4.2), аналогично отыскивается предшествующая ей некоторая вершина xi' = q и т.д. до xi' = s .

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

Для решения рассматриваемой задачи с помощью алгоритма Дейкстры, особенно для графов с большим количеством вершин и дуг, целесообразно использовать ЦВМ. Описанные выше операции (шаги 1 – 4) легко программируются на соответствующем алгоритмическом языке. Листинг программы, реализующей данный алгоритм, приведен в [36]. При решении задачи «вручную» описанный итерационный процесс изменения меток удобно свести в таблицу.

94

Пример [21]. Неориентированный граф с девятью вершинами x1, ..., x9 задан матрицей весов, приведенной в табл. 4.1. Необходимо найти

Примечание 1. Заданный граф является неориентированным, поэтому его матрица является симметрической. Учитывая это, в матрицу С можно было записать элементы только верхней треугольной «половины» матрицы весов. Нижняя половина ей симметрична.

Примечание 2. Незаполненные элементы матрицы С указывают на отсутствие ребер между соответствующими вершинами графа. Как отмечалось, эти элементы можно было принять равными ∞.

Решение. По матрице С строим граф (рис. 4.3), записав рядом с каждым ребром его вес (длину).

Рис. 4.3

95

Рассмотрим выполнение операций, предусмотренных алгоритмом Дейкстры, (шагов 1 – 4 а) применительно к данному графу. При этом метки, приписываемые вершинам на каждой итерации, будем записывать в строках табл. 4.2, выделяя постоянные метки прямоугольной рамкой.

Шаг 1. Принимаем l(x1) = 0, l(x2 ) = l(x3 ) =... = l(x9 ) = ∞. Заносим эти метки в начальную строку табл. 4.2. Метку l(x1 ) выделяем рамкой. Полагаем p = x1.

Т а б л и ц а 4.2

Первая итерация

Шаг 2. Рассматриваем вершины, связанные ребрами с p = x1 и имеющие временные метки. Это вершины x2 , x7 , x9 , x8 . Их метки равны ∞. Возьмем для начала x2 . Определим для этой вершины новую мет-

ку по правилу (4.1) , в котором l(xi ) =l(x2) = ∞, l( р) =l(x1) = 0, c( p, xi ) = = c(x1, x2) =10, l(x2) = min[∞,0 +10] =10.

Аналогично получаем: l(x7 ) =3, l(x9) =12, l(x8) = 6.

Заполняем вторую строку табл. 4.2, вписывая в нее найденные новые метки вершин x2 , x7 , x8, x9 и переписывая метки остальных вершин без

изменения.

96

Шаг 3. Из всех временных меток выбираем наименьшую и объявляем ее постоянной. Такой меткой оказывается l(x7 ) =3. Выделяем ее рам-

кой во второй строке табл. 4.2. Полагаем p = x7 .

Шаг 4. Поскольку имеются вершины с временными метками, переходим к шагу 2.

Вторая итерация Шаг 2. Рассматриваем вершины, связанные ребрами с вершиной

p = x7 и имеющие временные метки. Это вершины x2, x9, x6, x4 . Для вершины x2 , имеющей метку lст(x2) =10 , находим новую метку

lнов(x2 ) = min[lст(x2 ); l(x2 ) + c(x1, x2 )] = min(10, 3 + 2) =5.

Аналогично получаем: l(x4 ) = 7; l(x9 ) =12; l(x6 ) =17.

Полученные новые метки записываем в 3-ю строку табл. 4.2, а метки остальных вершин переписываем без изменения.

Шаг 3. Из временных меток этой строки табл. 4.2 выбираем наименьшую и объявляем ее постоянной. Это метка l(x2 ) =5. Отмечаем ее

рамкой в 3-й строке табл. 4.2, полагаем p = x2 .

Шаг 4. Анализируя 3-ю строку табл. 4.2, убеждаемся в наличии временных меток, далее переходим к шагу 2 и выполняем следующую (3-ю) итерацию.

Продолжая этот процесс, будем последовательно заполнять табл. 4.2 новыми строками, отмечая каждый раз по одной новой постоянной метке до тех пор, пока не будет получена строка, все элементы которой отмечены как постоянные метки. Полученные в последней строке табл. 4.2 числа равны длинам кратчайших путей из x1 в соответствующие вершины xi .

Сами пути можно получить, пользуясь соотношением (4.2).

Так, для вершины t = x5 длина кратчайшего пути от s = x1 оказалась равной 12. Этой вершине могут предшествовать вершины x4 , x6 , x8 (см.

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

для каждой из вершин:

l(x4 ) +c(x4 , x5 ) = 7 +5 =12; l(x6 ) +c(x6 , x5 ) =17 +10 = 27; l(x8 ) +c(x8 , x5 ) = 6 + 23 = 29.

Сравнивая полученные результаты с l(x5 ) =12 , видим, что в кратчайшем пути вершине x5 предшествует x4 .

97

Аналогично находим, что x4 предшествует x7 , а x7 предшествует x1 = s . Таким образом, кратчайший путь от x1 к x5 проходит через вершины x7 и x4 .

Оформление решения

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

§ 4.3. Задача о критическом пути в графе

Постановка задачи. Дан ориентированный граф, в котором отсутствуют контуры и каждой дуге ( xi , x j ) приписан вес cij ≥ 0 . Требуется найти

путь от заданной начальной вершины s к заданной конечной вершине t, имеющий наибольшую длину, равную сумме весов дуг, входящих в этот путь. Такой путь называется критическим [21, 25].

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

Совокупность операций, или работ, необходимых для выполнения задания, можно представить в виде ориентированного графа, в котором дуги изображают соответствующие операции с учетом их последовательности, а вершины – события. Говорят, что событие произошло (например, блок № 2 изготовлен), если все операции (например, изготовление и испы-

98

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

завершены. Подобный граф, изображающий отношения предшествования между операциями проекта, называют сетевым графиком [25]. В качестве весовых характеристик cij дуг обычно рассматривают время, необходимое

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

Отметим, что задача о критическом пути сходна с задачей о кратчайшем пути в графе, поэтому ее можно решать, используя рассмотренный выше алгоритм Дейкстры, заменив в нем все операции min на max [21].

Однако специальная структура сетевого графика позволяет находить решение с помощью более простого алгоритма [21, 25]. Его можно представить в виде трех стадий.

Стадия А. Она заключается в специальной нумерации вершин графа, при которой каждая дуга ориентирована от вершины с меньшим номером i к вершине с большим номером j. При этом начальное событие получает номер 1, затем следующий номер присваивается любому неперенумерованному событию, для которого все предшествующие события перенумерованы (такое событие всегда существует благодаря отсутствию контуров). Эта операция повторяется до тех пор, пока все события не будут перенумерованы. При этом конечное событие всегда получит последний (наибольший) номер.

Стадия Б. Она состоит в последовательной расстановке меток перенумерованных вершин по следующему правилу. Вершине x j приписыва-

где максимум ищется по всем вершинам xi , от которых идут дуги в x j . Вслед за x j метка по правилу (4.3) присваивается вершине, номер которой на единицу больше. Процесс расстановки меток начинается с x1 (полагают l(x1) = 0 ), а заканчивается тогда, когда последняя вершина xn =t получит соответствующую метку. Можно показать, что метка l(x j ) любой вершины x j , включая и xn , равна длине самого длинного пути от x1 до x j .

99

Стадия В. Она состоит в отыскании дуг, образующих критический путь. Для этого используется условие, по которому дуга (xi , x j ) входит в

где l(xi ) и l(x j ) – метки, расставленные на стадии Б.

Процесс включения дуг в критический путь начинается с конечной вершины xn и продолжается до тех пор, пока не будет достигнута началь-

ная вершина x1 .

Пример [21]. Для графа, заданного матрицей весов, приведенной в табл. 4.3, нужно найти критический путь от x1 к x13 .

Решение. Строим граф, соответствующий заданной матрице (рис. 4.4, а). Затем меняем нумерацию вершин, при этом во избежание путаницы изменяем обозначения – вместо xk пишем ym . Получаем граф,

приведенный на рис. 4.4, б.

Т а б л и ц а 4.3

правилу (4.3), записывая их рядом с вершинами, например в кружках. Так, для вершины y6 рассматриваем две дуги от y2 и y3 и, используя по-

100