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

между работами i и j покажет, что ;-я работа сможет выпол­

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

ri—bi—a{tb

выражающей зависимость времени и ресурсов.

Известно также общее количество потребляемых ресур­ сов R q, выделенных для осуществления всего проекта. Ис­ ходную информацию о графе представим двумя массивами: L и К. В массиве L в произвольном порядке в десятичной системе счисления записываем информацию о дугах графа, не принадлежащих полным контурам. Для дуг, входящих в состав полного контура, информация в массиве L не зада­ ется. При формировании массива L следует учитывать, что каждая вершина полного контура должна быть связана вхо­ дящей и выходящей дугами с внешними вершинами, не от­ носящимися к рассматриваемому полному контуру.

Зная параметры г-й вершины dif Лг, aif можно запи­ сать информацию о каждой дуге, выходящей из вершины i и входящей в j-ю, двумя 37-разрядными ячейками:

а) “N> h dh

a + l) + O if bif а*.

Каждый из параметров i, j, Dh bit db at может принимать десятичные значения от 0 до 999. Нумерация вершин графа г осуществляется подряд от 0 до 999 в произвольном поряд­ ке.

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

130

«минус». Номер контурной вершины фиксируется в млад­ ших разрядах ячейки. Например, для графа, содержащего два полных контура, информация массива запишется так:

к) — 000 000 и

й+1)+000 000 z2

fe+2) — 000 000 U

fe+3)+000 000 и

k + 4)+000 000 г5

k+ 5) — 000 000 000.

Здесь вершины с номерами ц и гг входят в первый полный контур, вершины U, U, h составляют второй полный контур, а отрицательный ноль в ячейке к-\-Ъ свидетельствует об окончании массива полных контуров.

Порядок следования контуров в массиве К произволь­ ный.

Кроме массивов L и К для графа задаются дополнитель­ но следующие параметры:

I — количество связей в массиве L без учета контурных связей;

N — общее количество вершин на графе;

k — количество вершин, принадлежащих полным конту­ рам;

io— номер фиктивной миноранты; iN— номер фиктивной мажоранты;

Ro— общее количество ресурсов, выделенных на осущест­ вление проекта;

h — шаг изменения величин в пределах [<2*, Z)f]. Фиктивные миноранта io и мажоранта iN вводятся на

графе независимо от того, входит ли в исходный граф одна или несколько начальных (конечных) вершин. При наличии одной входящей (выходящей) вершины фиктивная верши­ на io (i n) соединяется с ней дугой. Если на графе несколько входящих (выходящих) вершин, то все они соединяются ду­ гами с фиктивной вершиной. Параметры dit Dit ait bt вновь введенных фиктивных вершин io и iN берутся равными нулю.

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

а)+го i \ 000

а + 1 )+ 0 0 0 000 000

131

a-\-K) -j-/* iV ООО

a + t f + l ) - f ООО ООО ООО.

Параметры I и N задаются с учетом введенных вершин io, In и дуг, соединяющих эти вершины с вершинами графа.

Контроль правильности задания исходной информации

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

Алгоритм выявления на сетевом графе висячих вершин.

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

Для выполнения указанного контроля отводится в МОЗУ N рабочих ячеек (N — количество вершин на графе). Сово­ купность этих ячеек составляет некоторое множество F. Каждой ячейке в F соответствует одна вершина графа.

Контроль можно осуществить выполнением следующих шагов:

1.Массив ячеек F очищаем нулями.

2.В массиве L просматриваем ячейки с кодами i, j, dt. При этом для i-й вершины в ячейку (/+ г) из F заносим еди­ ницу по первому адресу, а для j-й вершины в ячейку ( /+ ;) — единицу по второму адресу. За один просмотр массива L в массиве F будут зафиксированы все входы и выходы из вер­ шин графа.

3.Анализируем все ячейки /+*' массива F. При этом мо­

гут быть такие варианты:

а) первый и второй адреса рассматриваемой ячейки (/-Н ) отличны от нуля (это говорит о том, что для i-й вер­ шины графа существуют входящие и выходящие из нее ду­ ги);

б) содержимое ячейки ( /+ 0 равно нулю (это свидетель­

132

ствует о том, что в массиве L вершина с номером 0 <Ci<iN пропущена и ее следует ввести в исходную информацию);

в) первый адрес ячейки (/+£) равен нулю, т. е. выхода из i-й вершины нет (если 1ф1н,то это говорит о том, что на графе имеется новая мажоранта с номером i и ее необходи­ мо соединить фиктивной дугой с г#);

г) второй адрес ячейки ( /+ 0 равен нулю (если Ьфц, то на графе есть новая миноранта с номером i, которую следу­ ет соединить с io).

При анализе ячеек массива F все выявленные ошибки выдаются на печать. Перед началом вычислений, согласно сделанным распечаткам, в массив L необходимо внести со­ ответствующие исправления.

Алгоритм поиска на графе контуров, отличных от пол­ ных. Сущность этого алгоритма заключается в том, что граф с полными контурами преобразуется в обычный сетевой путем «сжатия» полных контуров в узел (одну вершину). На полученном в результате этого графе все обычные контуры устанавливаются с помощью метода Форда. Найденные кон­ туры необходимо исключить, т. е. внести соответствующие изменения в массив L.

Основные шаги вычислительного алгоритма:

1.В массиве L анализируем последовательно коды типа (i, j, d{). Считаем, что массив L рассортирован в порядке воз­ растания номеров вершин i и j. Для сортировки можно вос­ пользоваться методом Шелла [51].

2.Массив F из N рабочих ячеек очищаем нулями.

3.Просматриваем коды в массиве полных контуров К

ианализируем их знаки «плюс» и «минус» (000 000 гА). При

в рабочей ячейке R-j-1. Далее выполняется блок 5.

5. Содержимое R-f-1 заносим в ячейку (/+£&) массива F, где ik взято из кода, анализируемого на знак в шаге 3. Далее переходим к шагу 3. В результате действия пяти ша­ гов за один просмотр кодов всем вершинам каждого полного контура будет присвоен один и тот же номер i, находящий­ ся в массиве К со знаком «минус». Новые номера контур­ ных вершин необходимо затем зафиксировать в массиве L, т. е. выполнять шаги 6 и 7.

6. Коды i, j, dt из массива L просматриваем один раз. При этом анализируем в F содержимое ячеек (/+£) и (/+ j), в которых зафиксированы новые номера £* и j*.

7. Если содержимое ячеек (/+ г) и (/+ ;) отлично от ну­ ля, то i и j в коде из L заменяем на г*, j* из F.

Шаги 6 и 7 повторяем до полного просмотра кодов мас­

133

сива L. После замены старых номеров на новые в массиве L могут появиться одинаковые коды: ik, j k, dk и ц, Ju dih где

ik=zii* Jk Jh dk dii.

Одинаковые коды из массива L необходимо удалить. Для этого массив L сортируем по возрастанию номеров i и j, а за­ тем выполняем шаг 8.

8. Коды массива L просматриваем один раз и сравнива­ ем. Из-за рассортированности одинаковые коды в L стоят рядом. При совпадении рядом стоящих кодов первый из них удаляется. Тогда оставшаяся часть кодов массива L будет представлять информацию, характеризующую обычный се­ тевой граф, в котором каждый полный контур «сжат» в узел, т. е. представлен как вершина. В полученном сете­ вом графе необходимо выявить контуры, отличные от пол­ ных. Этот процесс поиска осуществляется на шагах 9— 14.

9. Веса всех дуг нового графа условно принимаем рав­ ными единице. Очищаем нулями ячейки массива F и пять

При соблюдении этого неравенства анализируется следую­

(а^+1) в ходе просмотра записываем в рабочей ячейке -R-f- + 3 , а номер ячейки (/+ ;), где достигается этот максимум (т. е. номер вершины ;'),— в ячейке (R+ 4).

12. Проверяем неравенство N ^ a j, где N — максималь­

ный номер вершины графа, а значение а бер ется из (Л+3)-й ячейки. При N ^ a j переходим к повторению шага 10, в про­ тивном случае при aj ^>N выполняются шаги 13 и 14. Не­ равенство aj^>N свидетельствует о наличии на графе кон­ тура, который отыскивается на шаге 13.

13. Номер вершины ;ft, входящей в контур, находится в

тем в ячейке (/-J-j*—i) отмечаем контурную вершину jk — 2, и процесс повторяем до тех пор, пока не придем вновь к вершине jk> В этом случае контур j k-^ jk -i- к . --+ik будет найден. По результатам, выданным на печать, необходимо в массив L внести соответствующие исправления, т. е. удалить коды полученного контура.

134

14. Этот шаг выполняем в том случае, если за один пол­ ный просмотр кодов массива L не будет соблюдено неравен­ ство N '> a j. Затем анализируем содержимое ячейки (Д +1),

и если оно отлично от нуля, то вновь повторяем шаги 10— 13, а ячейку (/2+1) очищаем. Наличие нуля в (/2+1) гово­ рит об отсутствии на графе контуров. На этом действия ал­ горитма заканчиваются.

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

Основные шаги алгоритма:

1.На графе удаляем контурные связи, т. е. дуги, соот­ ветствующие каждому полному контуру. Для полученного графа массив L сортируем методом Шелла [51] по возраста­ нию номеров вершин i и j. Ячейки рабочего массива F очи­ щаем нулями.

2.Просматриваем коды (i, j, d{) массива L. При этом в ячейку (/+ ;) по первому адресу добавляем единицу. В ре­ зультате за один просмотр кодов из L в (/+ ;)-й ячейке мас­ сива F накопится число тп, равное количеству дуг, входящих

ввершину ;.

3.В рабочей ячейке /2+0 фиксируем порядковый номер для присвоения его очередной вершине графа. Нумерацию вершин начинаем с единицы. Присвоение номеров осущест­

вляем с миноранты го» т. е. с вершины, у которой нет входя­ щих дуг и 7?г=0. В массиве F в ячейке (/+го) по второму ад­ ресу добавляем единицу — новый номер миноранты и затем присваиваем знак «минус»— признак вычеркивания входя­ щих дуг. В ячейку (/2+0) по второму адресу А 2 заносим число 2 — порядковый номер для очередной вершины графа.

4. Ячейки (/+& ) массива F просматриваем одну за дру­ гой и запоминаем номер к, т. е. первоначальный номер вер­ шины исходного графа, у которой вычеркнуты все входя­ щие дуги (т = 0, знак «минус») и присвоен новый номер (вто­ рой адрес А 2 ФО). Первоначально это будет ячейка, соответ­ ствующая миноранте + При выборе номера к выполняется шаг 5.

5. В массиве L находятся все коды (г, j, dt ), у которых но­

135