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

23.Формирование количества кодов в массиве L ". Орга­ низация цикла для массивов L " и К.

24.Просмотр очередного кода ( ± 000, 000, U) в массиве

Ки анализ его на знак. При знаке «плюс» выполняется опе­ ратор 26, в противном случае — оператор 25.

25.Константа переадресации из индексной ячейки для

массива К записывается в рабочей ячейке Д + 0 . Эта кон­ станта покажет начало очередного полного контура в мас­ сиве К. Далее выполняется оператор 26.

26. В ячейку (/+£*) рабочего массива F приформировывается константа из Д-j-O. В результате всем вершинам одно­ го полного контура в ячейках (/+£*) массива F будет соот­ ветствовать одна и та же константа. Далее переходим к опе­ ратору 27.

27.Анализ на конец массива К. При полном просмотре кодов в К коды массива D*** будут зафиксированы в ячей­ ках массива F. В этом случае выполняется оператор 28.

28.Запись на МЛ кодов массива Z)*** из F.

29.Просмотр очередного кода (i*, j*, dj*) из массива L. Анализ на знак содержимого ячейки (/+7) из F. При знаке «плюс »выполняется оператор 30, в противном случае — опе­ ратор 31.

* С/с — система счисления.

30. Анализ на конец массива L. Если все коды в L про­ смотрены, то это свидетельствует о том, что коды массива L' сформированы. В данном случае выполняется оператор 32, в противном случае — оператор 29.

31. Массив L " дополняется новыми кодами вида г*, у*,

Hdjk, где jk— вершины одного полного контура. Номера у*

Jk

154

отыскиваются в массиве К. Этот поиск осуществляется с по­ мощью вершины j*, соответствующей номеру ( /+ 7*)-й ячей­ ки, анализируемой в операторе 29. Если вершина j * входит в состав некоторого полного контура, то все коды (i*, J*,

2djk) формируются из вершин j k этого контура. Далее вы- / ft

полняется оператор 30.

32.Запись массива V

7777 7777 7777 — программы находится в ячейке 1345. Распределение памяти МОЗУ дано в таблице 6.1, а рас­

положение массивов на магнитной ленте ( р = 2, q = 2)— в таблице 6.2.

Инструкция по использованию программы «Ввод, контроль, компоновка»

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

1. Массив L с кодами

вается в десятичной системе счисления и вводится в МОЗУ с ячейки 1350.

155

3. Все параметры задаются в десятичной системе счис ления в следующих ячейках:

Информация пробивается одним массивом в указанных ячейках между двумя границами и записывается в МОЗУ пе­ ред началом работы программы.

Инструкция работы за пультом

1.Подготовить к вводу исходные данные, поставить маг­ нитную ленту 2— 2, включить БПМ (узкая печать).

2.Ввести программу, контрольная сумма — 7777 7777

7777.

3.Ввести исходные данные.

4.Пуск 0100.

5.Останов 0752 — конец работы программы «Ввод, контроль, компоновка».

Таблица остановов.

Входе работы программы на БПМ выдается следующая информация:

1.3 --------------------------г. Знак «минус» означает пробелы.

Висходной информации пропущена вершина с номером L

2.1 ------- . . . — i.

156

Висходной информации кроме миноранты го есть вер­ шина с номером г, в которую не входит ни одна дуга.

3.2 ■. . — г.

Висходной информации кроме мажоранты гм имеется вершина с номером г, из которой не выходит ни одна дуга.

4.г!->-г2->-.. .->гi свидетельствует о наличии контура. Для того, чтобы выявить его на исходном графе, необходимо каж­ дый полный контур «сжать» в узел, т. е. рассматривать как одну вершину. Узлу-вершине присваивается новый номер, равный номеру вершины, стоящей в массиве К со знаком «минус». Это следует сделать только в том случае, если одна из вершин напечатанного контура входит в состав полного контура.

§5. АЛГОРИТМ СИНТЕЗА ОПТИМАЛЬНОГО СЕТЕВОГО ГРАФА ПРИ ОГРАНИЧЕННОМ ОБЪЕМЕ СКЛАДИРУЕМЫХ РЕСУРСОВ

Метод распределения складируемых ресурсов на сете­ вом графе с полными контурами рассматривался нами в четвертой главе. Для реализации изложенного метода на ЭВМ «Минск-22» разработан машинный алгоритм и состав­ лена стандартная программа.

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

1.Ввод информации, перевод исходных данных в деся­ тичную систему счисления.

2.Формирование рабочих и промежуточных массивов,

запись их на МЛ.

3.Блок проверки правильности построения исходного

графа.

4.Анализ наличия на графе контуров, отличных от пол­

ных.

5.Формирование массива полных контуров.

6.Упорядочение вершин на графе — присвоение верши­ нам графа новых порядковых номеров.

7.Запись на МЛ четырех рабочих массивов, рассортиро­

ванных по увеличению номеров вершин i и j и уменьшению индексов i и j.

8. Формирование расширенного массива L", используе­ мого при расчете максимальных путей L * от г-й вершины графа до мажоранты.

9.Запись на МЛ параметров и констант.

10.Чтение с МЛ массива констант и рабочих массивов

сисходными данными. Вычисление верхней границы потреб­

157

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

Z ( 0 > = 2 bi— aiDt. t

р

*

158

12.Останов.

13.Перезапись на МЛ расширенного массива L " и мас­ сивов L, рассортированных по увеличению г, уменьшению и увеличению j.

14.Печать номера очередной итерации. Определение ранних начал t?-H для работ L Вычисление для вершин k»

входящих в состав полного контура, максимального пути от миноранты го до k и от k-й вершины до мажоранты г n (алго­ ритм В).

15.Упорядочение работ в каждом полном контуре (ал­ горитм А), пересчет ранних начал для всех работ графа, по­ лученного в результате синтеза.

16.Печать промежуточных значений Ткр и подсчет сум­ марного объема расходуемых ресурсов Z (k).

17.Печать Z(k). Проверка неравенства

При соблюдении (6.7) работает блок 18, в противном слу­ чае — блок 20.

18.Печать полученного решения.

19.Останов — решение найдено.

20.Вызов с МЛ промежуточных рабочих массивов; вы­ числение позднего окончания работ и полных резервов вре­ мени.

21.Анализ: все ли резервы времени использованы. Да — работает блок 26, нет — блок 22.

22.Увеличение продолжительности работ на величину резерва времени; определение нового значения Z(k)\ ана­ лиз на конец решения:

( 6. 8)

При выполнении неравенства (6.8) работает блок 25, в противном случае — блок 23.

23.Вычисление резервов времени работ сетевого графа.

24.Переход к блоку вычисления ранних начал и позд­ них окончаний работ. Пересчет резервов времени работ.

25.Корректировка временных оценок работ на резерн

15J