Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

Одновременно по первому адресу ячейки (/+ ;) вычитаем единицу из т и присваиваем знак «минус» независимо от первоначального знака. Поскольку массив L рассортирован по возрастанию номеров i, то коды с одинаковыми значени­ ями i располагаются рядом. После анализа всех кодов с i=

— k ячейке (f-\-k) из F присваиваем знак «плюс» и продол­ жаем дальнейший просмотр кодов в F, т. е. повторяем шаг 4.

6. Этот блок выполняется только в том случае, когда в шаге 4 проанализированы все ячейки массива F. Основные действия этого шага сводятся к следующему. В массиве F выбираем те ячейки, у которых т= 0 и которым присвоен знак «минус», а второй адрес А г = 0. Эти ячейки соответст­ вуют вершинам, у которых вычеркнуты все входящие в них дуги, но новый порядковый номер еще не присвоен. Подоб­ ным ячейкам в порядке их просмотра приформировываем по

4-0)<2V4-l (N — количество вершин на графе) продолжаем просмотр кодов из F, по окончании которого опять повторя­ ем шаги 4, 5, 6. В случае (Л 4-0)=Л 7-|-1 присвоение новых номеров считаем законченным и переходим к следующему шагу.

8. Массив L просматриваем один раз и прежние номера вершин i и j в кодах из L заменяем на новые: г* и зафик­ сированные соответственно в ячейках (/-j—г) и (/-f-j). Все даль­ нейшие рассуждения проводим для графа с новыми упоря­ доченными номерами вершин.

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

порядок следования, который отвечает требованию упоря­ дочения всех вершин на графе.

Основные шаги алгоритма упорядочения полных конту­ ров на графе:

1. Исходный граф с полными контурами, преобразуем сетевой, на котором все полные контуры «сжаты» в один узел — вершину; код ее в массиве К имеет знак «ми­

136

нус». Для проведения указанного преобразования можно воспользоваться алгоритмом упорядочения вершин на гра­ фе [3].В результате будут внесены определенные изменения

вмассив L — часть кодов из L удалится.

2.К вновь полученному массиву L применяем алго­ ритм [3]. Тогда у каждой вершины графа будет новый по­ рядковый номер. Все новые номера фиксируем по второму адресу ячеек массива F.

3. Анализируем отрицательные коды — 000 000 i в массиве полных контуров К. Затем по номеру г-й контурной вершины из (/+£)'й ячейки массива F выделяем новый по­ рядковый номер 77, который приформировываем к кодовой части всех кодов рассматриваемого полного контура из мас­ сива К. В результате всем вершинам одного полного контура присваиваем свой номер 77, который указывает порядок сле­ дования полных контуров.

4.Этот шаг выполняем для того, чтобы контурным вер­ шинам, входящим в массив К, были присвоены новые но­ мера, соответствующие единой системе упорядочения вер­ шин сетевого графа с полными контурами. Поэтому, преж­ де чем установить порядок следования полных контуров, необходимо предварительно упорядочить все вершины ис­ ходного графа. Это можно сделать с помощью алгоритма [3], после реализации которого в массиве F будут зафикси­ рованы новые номера.

5.Первоначальные номера i контурных вершин в кодах (d=77, 000, i) массива К заменяем на новые: ±77, 000, i*.

6.Массив К сортируем в порядке возрастания значений 77 и г*. В результате все коды из К располагаются в искомом порядке следования полных контуров. При этом все контур­ ные вершины имеют другие (отличные от исходных) номе­ ра, соответствующие общей системе упорядочения номеров вершин исходного графа.

§2. ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПУТИ НА ГРАФЕ С ПОЛНЫМИ КОНТУРАМИ

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

Предлагаемый алгоритм предназначен для определения

137

величины максимального пути на сетевом графе с полными контурами, построенном на языке «работа — связь». Метод включает небольшое количество операций и прост для реа­ лизации на ЭВМ

Постановка задачи. Дан граф G(X, U) с полными конту­ рами, где X — {дгг } — множество вершин, и = { и ц } — мно­ жество дуг. Обозначим множество полных контуров через тогда I i = { x k] — один полный контур, a Xk — вер­ шина этого контура. Необходимо найти на графе с полны­

ми контурами путь максимальной длины от любой верши­ ны х i до мажоранты x N.

Метод решения поставленной* задачи предназначен для реализации на ЭВМ, поэтому изложение начнем с задания исходной информации. Представим все связи — дуги графа Uij — в виде упорядоченного массива L с кодами -f-г, j, tit где i, j — номера работ (вершин), £г — продолжительность работы x t.

Полные контуры / г условимся представлять в ЭВМ в ви­ де массива с набором кодов ±000, 000, х^ где x k— верши­ ны одного контура (k = l, 2, . . .). Знак «минус» свидетельст­ вует о начале очередного полного контура Ii.

В качестве рабочего массива F фиксируем набор из N рабочих ячеек (/Ч-д^), (г= 1 , 2, . .. , iV), где N — количество вершин (работ) графа G(X, U). Множество X = { x t } упоря­ дочено.

Действие алгоритма основано на следующем очевидном свойстве. Если максимальный путь от любой вершины х-г графа до мажоранты идет через вершину xk полного конту­ ра 7/, то он будет проходить через все остальные вершины X j^ li контура и продолжением его будет максимальный

из путей, связывающих вершины этого контура с мажоран­ той.

Рассмотрим действие алгоритма по шагам.

Шаг 1. Коды массива L -f-г, j, ti просматриваем в произ­ вольном порядке. Значения £* заносим в рабочую ячейку (/-f-г) массива F. За один просмотр кодов массива L в ячей­ ках (/-{-г) зафиксируем все временные оценки tt для вершин графа xt.

Шаг 2. Коды массива L просматриваем вторично. Из яче­ ек (/+ ;) массива F величину tj заносим в код i, j, t t на ме­

сто прежнего значения £*. В кодах массива L параметр tj бу­ дет теперь соответствовать индексу j: -f-г, j, tj.

Шаг 3. Массив L сортируем в порядке уменьшения ин­ дексов г.

Шаг 4. Анализируем коды ±000, 000, Xk массива пол­ ных контуров К. Для каждого полного контура Ii опреде-

138

ляем сумму временных оценок 7* вершин Найден­ ную величину 27* со знаком «минус» заносим во все ячей­ ки (/+ * * ) массива F.

Шаг 5. В массиве L из очередного кода + г, j, t} выделя­ ем индекс j и анализируем знак ячейки (/-f-j) из F. При зна­

Одновременно массив L дополняем новыми кодами г, J*, 2 7*» где ik— номера вершин Xk^-h (при условии, что ко-

Шаг 6. Определение максимального пути L**. Искомые значения L * фиксируем в ячейках массива F. Полагаем зна­ чение Ь*=п для мажоранты iN равным нулю. Коды (i, j, tj) расширенного массива Lpac анализируем в порядке их сле­ дования. Пересчет L * осуществляем по формуле

где L j * — путь максимальной длины от j-й вершины до мажо­ ранты x N. Эту величину берем из ячейки (/-f-у) массива F. Величина L /* из ячейки (/+ i) есть искомый максимальный путь Li*, вычисленный к данному моменту по формуле (6.1).

Вновь найденное значение L * заносим в ячейку (/+ г) массива F и просмотр кодов расширенного массива Lpac продолжаем.

Действие алгоритма закончится, как только будут про­ анализированы все коды из L и проведены вычисления по формуле (6.1). Все искомые величины максимальных путей L *от вершин i до мажоранты iN будут зафиксированы в со­ ответствующих ячейках рабочего массива F.

§ 3. АВТОМАТИЗАЦИЯ ПРОЦЕССА ВЫЧИСЛЕНИЯ ОСНОВНЫХ ПАРАМЕТРОВ СЕТЕВОГО ГРАФА

Здесь описываются алгоритмы вычисления основных параметров, используемых при анализе сетевого графа. Та­ кими параметрами являются: продолжительность критиче­ ского пути Ткр, ранние начала работ 7Р*Н, поздние окончания

работ 7"-°, резервы времени работ и др.

Алгоритм определения максимального пути от миноран­

139