Задача о максимальном пути и сетевые графики.

Задача о максимальном пути формулируется следующим об­разом: в заданной сети G=(V,E,c) с выделенным узлом s, для ка­ждого узла v V найти s-v-путь, имеющий максимальную длину среди всех возможных s-v-путей в сети G.

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

Впрочем, задачу о максимальном пути в общем случае можно решать и непосредственно, заменяя в алгоритме Форда-Беллмана строку 6 на строку

6' forw V doD[v] := max(D[v], D[w]+A[w,v]);

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

Важный частный случай сети с неотрицательными весами дуг в предположении отсутствия контуров положительной длины сводится к случаю отсутствия контуров в сети. Следовательно, задача о максимальном пути в частном случае может быть реше­на алгоритмом 6.6, в котором +∞ заменяется на

-∞ (строка 3), а min на шах (строка 6). Несложное доказательство корректности исправленного таким образом алгоритма 6.6 мы предоставляем читателю.

Отметим, что замена всех минимумов в алгоритме Дейкстры (строки 7 и 10) на максимумы не позволяет получить алгоритм решения задачи о максимальном пути. Для примера достаточно рассмотреть сеть, изображенную на рис.6.5. Здесь модификация алгоритма Дейкстры, при которой все минимумы заменены на максимумы неправильно определит путь максимальной длины от узла s до узла 2.

Итак, алгоритм Форда-Беллмана и алгоритм 6.6 легко могут быть модифицированы для вычисления длин максимальных

s-v- *1 путей. Сами же пути с помощью вычисленных Задача о максимальном пути в бесконтурной сети имеет большое практическое значение. Она является важнейшим зве­ном в методах сетевого планирования работ по осуществлению некоторого проекта.

Многие крупные проекты, такие как строительство дома, из­готовление станка, разработка автоматизированной системы бух­галтерского учета и т.д., можно разбить на большое количество различных операций (работ). Некоторые из этих операций могут выполняться одновременно, другие — только последовательно: одна операция после окончания другой. Например, при строи­тельстве дома можно совместить во времени внутренние отде­лочные работы и работы по благоустройству территории, однако возводить стены можно только после того, как будет готов фун­дамент.

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

Здесь мы разберем основные моменты одного из методов се­тевого планирования, называемого методом критического пути (МКП).

Метод был разработан в конце пятидесятых годов Дюпоном и Ремингтоном Рандом для управления работой химических заво­дов фирмы "Дюпон де Немур" (США).

Пусть некоторый проект W состоит из работ v₁...,v_n. для каж­дой работы v_k известно, или может быть достаточно точно оценено время ее выполнения t(v_k). Кроме того, для каждой работы v_k известен, возможно пустой, список ПРЕДШ(v_к) работ, непо­средственно предшествующих выполнению работы v_k. Иначе го­воря, работа v_k может начать выполняться только после заверше­ния всех работ, входящих в список ПРЕДШ(v_к).

Для удобства, в список работ проекта W добавим две фиктив­ные работы s и t, где работа s обозначает начало всего проекта W, а работа t — завершение работ по проекту W. При этом будем считать, что работа s предшествует всем тем работам v W, для которых список ПРЕДШ(v) пуст, иначе говоря, для всех таких работ v W положим ПРЕДШ(v)={s}. Положим далее ПРЕДШ(s) = Ø, ПРЕДШ(t)={v W : v не входит ни в один список ПРЕДШ(w)}, то есть считаем, что работе t предшествуют все те работы, которые могут выполняться самыми последними. Время выполнения работ s и t естественно положить равными нулю; t(s)=t(t)=0.

Весь проект W теперь удобно представить в виде сети G=(V,E,c), где сеть G=(V,E,c) определим по правилам:

1. V=W, то есть множеством узлов объявим множе­ство работ;

2. E={(v,w) : v ПРЕДШ(w)}, то есть отношение предшествования задает дуги в сети;

3. c(v,w)=t(w).

Так построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Легко видеть, что списки смеж­ностей этой сети ПРЕДШ[v] совпадают с заданными для проекта списками предшествующих работ ПРЕДШ(v).

Понятно, что сетевой график любого проекта не может содер­жать контуров. Действительно, пусть узлы v_kl,v_k2,...,v_kr=v_k1 обра­зуют контур в сети G. Это означает, что работа v_k2 не может на­чаться раньше, чем будет завершена работа v_k1 работа v_k3 — раньше, чем завершится работа v_k2, и т.д., и, наконец, v_kr = v_k| -— раньше, чем будет завершена работа v_kr-1. Но тогда никакая из работ v_k1...,v_kr никогда не сможет быть выполнена. А каждый ре­альный проект должен допускать возможность его завершения. Следовательно, в сетевом графике нет контуров.

Отсутствие контуров в сети G позволяет пронумеровать рабо­ты проекта W таким образом, чтобы для каждой дуги (v_i, v_j) сети G выполнялось условие i<j (лемма 6.3). Напомним, что осущест­вить такую нумерацию узлов сети G можно с помощью алгорит­ма 6.5 ТОПСОРТ. Поэтому в дальнейшем будем считать, что уз­лы в сети G топологически отсортированы.

Рис 6.6 Проект строительства дома и его сетевой график

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

Обозначим через РВЫП(v) (соответственно PHAЧ(v)) наибо­лее ранний возможный срок выполнения работы v (соответственно наиболее ранний возможный срок начала рабо­ты v). Удобно считать, что РВЫП(s)=PHAЧ(s)=0. Поскольку на­чать выполнять работу v можно только после того, как будут вы­полнены все работы, предшествующие данной работе v, то полу­чим следующие формулы для расчета значений PHAЧ(v) и РВЫП(v):

PHAЧ(v) = max{ РВЫП(w): w ПРЕДШ(v)},

РВЫП(v) = PHAЧ(v) + t(v).

Легко видеть, что значение РВЫП(v) равно длине максималь­ного s-v-пути в сети G. Поэтому, для вычисления значений РВЫП(v) можно использовать алгоритм 6.6 вычисления длин минимальных путей в бесконтурной сети, в котором все миниму­мы заменены на максимумы. При этом значение РВЫП(t) дает наиболее ранний возможный срок завершения всего проекта в целом.

Ради полноты приведем здесь формальную запись алгоритма, непосредственно вычисляющего характеристики РНАЧ и РВЫП.

АЛГОРИТМ 6.7.

(* расчет наиболее ранних возможных сроков начала и выполне­ния работ *)

Данные: Сетевой график G работ V, заданный списками ПРЕДШ(v), v V.

Результаты: Наиболее ранние возможные сроки начала и выпол­нения работ PHAЧ[v], РВЫП[v], v V.

Здесь, в алгоритме 6.7, узлы сетевого графика s и t обозначены соответственно через v₀ и v_n+1.

Значения РВЫП(v) и PHAЧ(v) для сетевого графика, изобра­женного ранее на рис.6.6, приведены на рис. 6.7. Из найденных значений следует, что этот проект не может быть завершен ранее чем через 20 единиц времени.

Пусть Т — плановый срок выполнения проекта W. Ясно, что Т должно удовлетворять неравенству Т ≥ PBЫП(v_n+1).

Через ПВЫП(v) (соответственно ПНАЧ(у)) обозначим наибо­лее поздний допустимый срок выполнения (начала) работы v, то есть такой срок, который не увеличивает срок Т реализации всего проекта. Например, для работы 3 сетевого графика из рис. 6.6 имеем РНАЧ(3)=12, РВЫП(3)=14, но ясно, что начать работу 3 можно на единицу времени позже, поскольку это не повлияет на срок выполнения всего проекта, а вот задержка в реализации этой же работы на 2 единицы приведет к увеличению срока выполне­ния всего проекта на 1 единицу времени.

АЛГОРИТМ 6.8.

(* Расчет наиболее поздних сроков начала и окончания работ *) Данные: Сетевой график G работ V, заданный списками ПРЕДШ[v], v V, плановый срок окончания проекта — Т. Результаты: Наиболее поздние допустимые сроки выполнения и начала работ ПВЫП[v] и ПНАЧ[v].

Прямо из определений получаем справедливость равенств ПНАЧ(v_n+1)=ПВЫП(v_n+1)=Т. Поскольку произвольная работа v должна быть завершена до начала всех наиболее поздних допус­тимых сроков тех работ w, которым предшествует работа v, то получаем следующие формулы:

ПВЫП(v)=min{ПНАЧ(w): по всем w таким, что ПРЕДШ(w) v},

ПНАЧ(v)=ПВЫП(v)-t(v).

Вычислять значения ПВЫП(v) и ПНАЧ(v) можно, двигаясь по узлам сети G от v_n+1 к v₀. Все детали вычисления названных ха­рактеристик приведены выше в алгоритме 6.8.

Найденные значения возможных и допустимых сроков выпол­нения работ позволяют определить резервы времени для выпол­нения той или иной работы. В сетевом планировании рассматри­вают несколько различных и по-своему важных видов резерва работ. Мы здесь ограничимся лишь полным резервом (иногда его называют суммарным) времени выполнения работ. Он определя­ется по формуле:

PE3EPB(v)=ПНАЧ(v)-PHAЧ(v).

Значение PE3EPB(v) равно максимальной задержке в выпол­нении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство

РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).

Рис 6.7. Численные характеристики сетевого графика

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

Численные значения введенных характеристик сетевых гра­фиков для проекта из рис.6.6 даны на рис. 6.7. Расчеты выполне­ны при Т=20. Критическими работами этого проекта являются работы с номерами 0,1,2,4,6,8, которые и образуют в сети G кри­тический путь.

Исследование сетевых графиков на этом мы завершим. Отме­тим только, что помимо рассмотренных нами характеристик, час­то рассматривают и большое число других, связанных, например, с неопределенностью во времени выполнения работ, с управле­нием ресурсами и т.д. Достаточно обширный и содержательный материал по этому поводу можно найти в книге [8].

Задача о maxmin пути.

Пусть G=(V,E,c) — сеть, s,v V и р: s=v₀,v₁,…,v_k⁼v — s-v-путь в G. Весом пути р назовем число

m(p) = min{c(v_i-1, v_i): i=l,2,...,k}.

Задача о maxmin пути формулируется следующим образом: среди всех s-v-путей в сети G найти путь максимального веса.

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

Рассмотрим дорожную сеть, включающую мосты. Будем счи­тать, что превышение грузоподъемности некоторого моста при перевозке груза приводит к разрушению данного моста. Допус­тим, что мы хотим определить максимальный вес груза, который может быть транспортирован в рассматриваемой дорожной сети из пункта s в пункт v без превышения грузоподъемности находя­щихся на пути движения транспорта мостов.

Для решения этой задачи построим сеть G=(V,E,c), множест­вом узлов которой объявим пункты s и v, а также все перекрестки дорожной сети. Будем говорить, что дорога х, соединяющая пе­рекрестки w и u, непосредственно их соединяет, если х не прохо­дит через другие перекрестки. Для дороги х положим с(х) рав­ным минимальной из грузоподъемностей мостов, находящихся на дороге х; если дорога х мостов не содержит, то считаем, что с(х)=+∞. Будем считать, что два какие-нибудь узла w и и сети G соединены дугами (w,u) и (u,w), если есть хоть одна дорога х, непосредственно соединяющая перекрестки w и u. Положим c(u,w)=c(w,u)=max{c(x) : х непосредственно соединяет w и u}. Аналогично определяются дуги, инцидентные пунктам s и v. правда будем считать, что из s дуги только исходят (то есть ис­ключим дуги вида (w,s), w V), а в v дуги только входят.

На рис.6.8.а дан пример дорожной сети, соединяющей пункты s и v: цифрами обозначены перекрестки, буквами — мосты, а числа в скобках означают грузоподъемность соответствующего моста. Соответствующая сетевая модель приведена на рис.6.8.б, где каждое неориентированное ребро вида {i,j} соответствует двум дугам (i,j) и (j,i). Обращаем внимание читателя на вес дуги (3,v), который равен 80, ибо пункты 3 и v соединяют две дороги х и х' для которых с(х)=80, и с(х')=60. Поэтому c(3,v)=80.

Рис.6.9. Пример интерпретации задачи о maxmin пути.

Для решения задачи о maxmin пути в произвольной сети G=(V,E,c) с необязательно неотрицательными весами мы лишь немного модифицируем изложенный ранее в параграфе 6.2 алго­ритм Дейкстры. Принцип «жадности» в вычислении maxmin рас­стояний выглядит здесь следующим образом: вычисляем после­довательно каждый раз maxmin расстояние до наиболее далекого узла от s среди всех тех узлов, до которых maxmin расстояние еще не вычислено.

Более точно наши рассуждения здесь таковы. Обозначим че­рез dm(v) максимальный вес среди всех s-v-путей, то есть maxmin расстояние от s до v.

Положим S={s} и dm(s)=+∞.

Будем теперь добавлять к S по одному узлу так, что множест­во S состоит на каждом шаге из тех узлов v, для которых dm(v) вычислено, и для всех v S и w V\S справедливы неравенства dm(v) ≥ dm(w). Для каждого w V\S положим

D(w)= max{min{dm(v), c(v,w)} : v S}.

Понятно, что в этой формуле появляется максимум вместо мини­мума в аналогичной формуле (1) из параграфа 6.2, ибо нас инте­ресует путь максимального веса.

Очередной узел w*, который следует добавить к S, выбирается под условием:

D(w*)=max{D(w): w V\S}.

Обоснование корректности такой модификации алгоритма Дейкстры проводится аналогично доказательству корректности самого алгоритма Дейкстры.

Формально можно сказать, что вся модификация заключается в том, что все знаки суммы заменяются на минимумы, а все ми­нимумы в алгоритме Дейкстры — на максимумы. Поэтому мы не будем приводить здесь исправленный указанным способом алго­ритм 6.3.

Рис 6.9. Работа модифицированного алгоритма Дейкстры

На рисунке 6.9 каждое неориентированное ребро {v,w} пред­ставляет собой две ориентированные дуги (v,w) и (w,v). Читателя не должен смущать тот факт, что веса дуг (1,2) и (2,3) равны +∞. Это обстоятельство следует понимать как то, что, во-первых, дуги (1,2) и (2,3) имеются в сети, и, во-вторых, они имеют беско­нечно большой вес. Бесконечно большой вес некоторых дуг мо­делирует ситуацию, встречающуюся в задаче о самом надежном пути перевозки груза по дорожной сети. Естественно считать, что дорога, по которой может быть транспортирован груз любого веса, соответствует дуге бесконечно большого веса.

При рассмотрении maxmin задачи веса несуществующих дуг естественно считать равными -∞.

Сами пути легко строятся с помощью меток ОТЕЦ. Отметим только, что такая модификация алгоритма Дейкстры не гаранти­рует построения минимального по числу дуг наилучшего в смыс­ле maxmin-расстояния пути. Например, в сети из рис 6.9 до узла 5 будет найден путь 1-2-3-5, в то время как путь 1-3-5 имеет тот же вес.

Отметим, что задача о minmax пути может быть сформулиро­вана и решена аналогично задаче о maxmin пути.

Не нашли, что искали? Воспользуйтесь поиском по сайту: