Рациональные методики поиска оптимальных путей сетевых графиков и их автоматизация на ЭВМ

эти вопросы и дают рациональные методики поиска особых путей, доказанные в этом разделе. 4 Автоматизация анализа оптимальности сетевых графиков на ЭВМ 4.1 Представление сетевого графика в машинной форме Любая ЭВМ нуждается в преобразовании различных абстрактных понятий, ясных для человека, в удобную для неё форму. Сетевой график, как графическое изображение упорядоченных кружков и стрелок само по себе для ЭВМ нечего не значить. Для того, чтобы ЭВМ могла понимать структуру сетевого графика и, главное, обрабатывать её, необходимо представить эту структуру в эквивалентной машинной форме. Наиболее удобный способ представления структуры сетевого графика в машинной форме, основан на понятии матрицы смежностей . Пример данной матрицы для структуры сетевого графика на рисунке 2.1 представлен на рисунке 4.1 . Матрица смежностей квадратная и имеет размерность , где число событий сетевого графика. Номера строк матрицы задаются номерами событий , из которых работы сетевого графика исходят, номера столбцов матрицы задаются номерами событий , в которые работы сетевого графика входят. На пересечении строки и столбца , в матрице смежностей, может быть только одно из двух значений: 0 или 1. Если , то это означает, что на сетевом графике существует работа, исходящая из события с номером и входящая в событие с номером . Если , то такой работы на сетевом графике нет. Матрица смежностей будет верно отражать структуру сетевого графика, если сетевой график построен по всем, узаконенным стандартом правилам. Здесь, наиболее важны следующие: ? Событиям присваиваются номера с таким расчётом, что старший номер соответствует более позднему по времени событию. То есть, если рассмотреть некоторое событие и все входящие в него работы, то номер этого события должен быть больше номеров всех событий, из которых эти работы исходят. В этом случае первая строка и первый столбец матрицы смежностей соответствует начальному событию сетевого графика , а последние строка и столбец завершающему событию сетевого графика , где число всех событий в сетевом графике. ? Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события, разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. 4.2 ). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответствии с первым правилом. Верно построенная матрица смежностей обладает радом полезных свойств: ? Если задаться некоторым номером события , то единицы в соответствующей строке укажут на номера событий , с которыми событие соединено, исходящими из него работами. Это свойство следует из правила построения матрицы смежностей. ? Если задаться некоторым номером события , то единицы в соответствующем столбце укажут на номера событий , с которыми событие соединено, входящими в него работами. Это свойство, также, следует из правила построения матрицы смежностей. ? Если некоторое событие указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события , то номера этих событий могут быть только больше номера , что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежностей могут присутствовать только в верхней диагональной части матрицы (см. рис. 4.1 ). Любопытно заметить, что если последнее из перечисленных свойств не выполняется, то в сетевом графике есть петли, то есть, работы, концы которых являются началами других работ, предшествующих первым по времени, при условии, что все события занумерованы, верно. Из этого следует возможность легкой автоматизации на ЭВМ процесса проверки правильности построения сетевого графика. Данный процесс проверки, алгоритмически, представляется в виде блок-схемы 4.1 . Суть алгоритма проверки заключается в определении содержимого элементов нижней диагональной части матрицы смежностей. Если там встретится хотя бы одна единица, то это будет означать, что сетевой график построен неправильно либо в нем есть петли, либо события занумерованы не верно.

Блок-схема 4.1 Алгоритм тестирования матрицы смежностей

4.2 Автоматизация расчёта параметров сетевого графика Анализ оптимальности сетевого графика возможно провести, только после расчёта всех, присущих ему параметров. Исходными данными для расчёта являются длительности всех, входящих в сетевой график работ. Результатами расчёта являются значения, описанных в разделе 2, параметров. И первое и второе, можно объединить в одной таблице исходных данных и результатов 4.1 . Данная таблица есть двумерная матрица с пронумерованными строками и столбцами. Номера строк изменяются от 0 до (см. таб. 4.1 ), где число работ в сетевом графике, которое можно найти, подсчитав все единицы в матрице смежностей. Номера столбцов изменяются от 0 до 13, где каждый номер соответствует своему параметру сетевого графика. Нумерация строк и столбцов необходима для представления таблицы исходных данных и результатов в машинной форме. Столбцы под номерами 0,1 и 2 определяют часть таблицы 4.1 , отведённую под хранение исходных данных, к которым относятся коды работ и длительности работ. Как видно, коды работ задаются ячейками двух столбцов под номерами 0 и 1. Здесь индекс (столбец 0) определяет номер события, из которого работа исходит, а индекс (столбец 1) определяет номер события, в которое она входит. Найти все возможные коды работ сетевого графика легко по матрице смежностей , если, просматривая её строки, номера которых соответствуют индексу , выбирать в качестве индекса номера тех столбцов, для которых будут отыскиваться единицы. Алгоритм заполнения таблицы 4.1 исходными данными представлен в виде блок-схемы 4.2 , где ячейки самой таблицы обозначены символом . Для данного обозначения: номер строки таблицы исходных данных и результатов, номер столбца той же таблицы. Алгоритм предполагает, что таблица исходных данных и результатов уже зарезервирована и имеет размерность , число работ в сетевом графике.

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