Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Верно построенная матрица смежностей обладает радом полезных свойств:
Если задаться некоторым номером события [pic], то единицы в соответствующей строке укажут на номера событий [pic], с которыми событие [pic] соединено, исходящими из него работами. Это свойство следует из правила построения матрицы смежностей.
Если задаться некоторым номером события [pic], то единицы в соответствующем столбце укажут на номера событий [pic], с которыми событие [pic] соединено, входящими в него работами. Это свойство, также, следует из правила построения матрицы смежностей.
Если некоторое событие [pic] указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события [pic], то номера этих событий [pic] могут быть только больше номера [pic], что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежностей могут присутствовать только в верхней диагональной части матрицы (см. рис. 4.1 ).

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

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

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

2 Автоматизация расчёта параметров сетевого графика

Анализ оптимальности сетевого графика возможно провести, только после расчёта всех, присущих ему параметров. Исходными данными для расчёта являются длительности всех, входящих в сетевой график работ. Результатами расчёта являются значения, описанных в разделе 2, параметров. И первое и второе, можно объединить в одной таблице исходных данных и результатов 4.1
.

Данная таблица – есть двумерная матрица с пронумерованными строками и столбцами. Номера строк изменяются от 0 до [pic] (см. таб. 4.1 ), где [pic]
– число работ в сетевом графике, которое можно найти, подсчитав все единицы в матрице смежностей. Номера столбцов изменяются от 0 до 13, где каждый номер соответствует своему параметру сетевого графика. Нумерация строк и столбцов необходима для представления таблицы исходных данных и результатов в машинной форме.

Столбцы под номерами 0,1 и 2 определяют часть таблицы 4.1 , отведённую под хранение исходных данных, к которым относятся коды работ и длительности работ. Как видно, коды работ задаются ячейками двух столбцов под номерами 0 и 1. Здесь индекс [pic] (столбец 0) определяет номер события, из которого работа исходит, а индекс [pic] (столбец 1) определяет номер события, в которое она входит. Найти все возможные коды работ сетевого графика легко по матрице смежностей [pic], если, просматривая её строки, номера которых соответствуют индексу [pic], выбирать в качестве индекса [pic] номера тех столбцов, для которых будут отыскиваться единицы.

Алгоритм заполнения таблицы 4.1 исходными данными представлен в виде блок-схемы 4.2 , где ячейки самой таблицы обозначены символом [pic]. Для данного обозначения: [pic] – номер строки таблицы исходных данных и результатов, [pic] – номер столбца той же таблицы. Алгоритм предполагает, что таблица исходных данных и результатов [pic] уже зарезервирована и имеет размерность [pic], [pic] – число работ в сетевом графике.

Блок-схема 4.2 – Алгоритм заполнения исходными данными таблицы исходных данных и результатов

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

Рассмотрим расчёт параметров сетевого графика на первом этапе.

Ясно, что в общем случае, при попытке определить ранний срок свершения некоторого события, как максимальный из ранних окончаний всех работ, входящих в это событие, может быть неудача, так как к этому моменту не все ранние сроки окончаний работ могут быть известны. Тогда, встает задача найти такой порядок расчёта сетевого графика, при котором, переходя от события к событию, всегда удаётся находить их ранние сроки свершения.
Оказывается, для всех сетевых графиков, с правильно занумерованными событиями этот порядок один и тот же, и основывается на следующей теореме.

Теорема 4.1 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт ранних сроков свершения событий в порядке: 0-е событие, 1-е, 2-е, и так далее, до завершающего события, в тупик зайти не может, при условии, что рассчитывая ранний срок свершения очередного события, сразу же определяются ранние окончания всех, исходящих из него работ.

Докажем эту теорему методом математической индукции.

Зададимся нулевым сроком свершения 0-го события, и рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 1-е событие. В него могут входить только работы, исходящие из событий с меньшими номерами
– в данном случае только из 0-го события, при этом ранние окончания этих работ уже известны. Тогда можно рассчитать ранний срок свершения 1-го события. Рассчитав ранний срок свершения 1-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 2-е событие. В него могут входить работы, только из 0-го и 1-го события, и ранние окончания которых уже известны. Тогда можем рассчитать ранний срок свершения 2-го события. Рассчитав ранний срок свершения 2-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее.
Рассмотрим 3-е событие. В него могут входить работы, только из 0-го, 1-го и
2-го события, и ранние окончания которых уже известны. Тогда можем рассчитать ранний срок свершения 3-го события….

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

Из данной теоремы, непосредственно, вырисовывается алгоритм расчёта параметров сетевого графика на первом этапе. Данный алгоритм представлен в виде блок-схемы 4.3 , и основан на том, что после выполнения алгоритма 4.2
, в таблице исходных данных и результатов [pic] уже находятся коды работ сетевого графика и их длительности.
Блок-схема 4.3 – Алгоритм расчета ранних сроков свершения событий сетевого графика

Рассмотрим расчёт параметров сетевого графика на втором этапе.

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

Теорема 4.2 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт поздних сроков свершения событий в порядке: последнее событие, предпоследние событие, предшествующее предпоследнему событию, и так далее, до начального (0-го) события, в тупик зайти не может, при условии, что рассчитывая поздний срок свершения очередного события, сразу же определяются поздние начала всех, входящих в него работ.

Докажем эту теорему методом математической индукции.

Зададимся поздним сроком свершения последнего события, равным его раннему сроку свершения, и рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим предпоследнее событие. Из него могут исходит только работы, входящие в события с большими номерами – в данном случае только в последнее событие, при этом поздние начала этих работ уже известны. Тогда можно рассчитать поздний срок свершения предпоследнего события. Рассчитав поздний срок свершения предпоследнего события, сразу же рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим событие, предшествующее предпоследнему. Из него могут исходить работы, только в предпоследнее и в последнее событие, и поздние начала которых уже известны. Тогда можем рассчитать поздний срок свершения события, предшествующего предпоследнему….

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

Из данной теоремы, непосредственно, следует алгоритм расчёта параметров сетевого графика на втором этапе. Данный алгоритм представлен в виде блок-схемы 4.4 , и основан на том, что после выполнения алгоритма 4.3
, в таблице исходных данных и результатов [pic] уже рассчитаны все ранние сроки свершения событий.

Рекомендуем скачать другие рефераты по теме: мировая экономика, новые сочинения.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата