,
или, исходя из формулы(3.1):
.(3.3)
Поскольку мы предположили от противного, что среди всех исходящих из события 2 работ нет работ с нулевым полным резервом времени, то отсюда сразу вытекает, что и работа, исходящая из события 1 и входящая в событие 2, также не может иметь нулевой полный резерв времени, уж если его минимальное значение заведомо неравно нулю, в соответствии с полученным равенством(3.3). Последнее противоречит условию теоремы. Из этого противоречия следует то, что невозможна ситуация, когда при нулевом резерве времени работы, входящей в событие 2, все исходящие из этого события работы имели бы ненулевые резервы времени. Если бы это имело место, то в соответствии с приведённым доказательством, работа, входящая в событие 2 также бы имела ненулевой полный резерв времени. Но ведь это не так по условию теоремы. Тогда для работ, исходящих из события 2 остаётся другая возможная ситуация – хотя бы одна из них имеет также нулевой полный резерв времени. Теорема доказана.
Из доказанных выше теорем, непосредственно, следует методика поиска критического пути, приводимая ниже. Рациональная методика поиска критического пути сетевого графика:
1 Просмотр сетевого графика ведётся от его начального события к конечному;
2 При рассмотрении начального события сетевого графика, в качестве работы, лежащей на критическом пути, выбирается та, которая имеет нулевой полный резерв времени. В соответствии с теоремой 3.1 (утверждение-необходимость), такая работа обязательно будет существовать;
3 При рассмотрении работ, исходящих из события, к которому привила работа с нулевым полным резервом времени, выбирается работа, также имеющая нулевой полный резерв времени. В соответствии с теоремой 3.2, такая работа существует;
4 Если, среди исходящих из некоторого события работ, есть несколько работ с нулевыми полными резервами времени, то выбирается любая. При этом, согласно теореме 3.2, процесс построения критического пути в тупик зайти не может, и рано или поздно дойдет до завершающего события сетевого графика.
Реализация указанных правил даёт путь, состоящий только из работ с нулевыми полными резервами времени. Тогда, на основании теоремы 3.1 (утверждение-достаточность), этот путь и будет являться критическим.
В целях проверки, доказанная методика применена для сетевого графика, представленного на рисунке 2.1 . Здесь, найденные критические пути, выделены жирными стрелками. Как видно, таких путей два, благодаря тому, что среди работ, исходящих из события 0, есть две работы с нулевыми полными резервами времени. Проверить то, что найденные пути являются критическими легко, просуммировав длительности принадлежащих им работ. Суммы окажутся: во-первых, равными между собой, а во-вторых, наибольшими среди аналогичных сумм других возможных путей.
Теперь рассмотрим вопрос поиска наикратчайшего пути сетевого графика. Оказывается, для его поиска можно применять, методику поиска критического пути, если использовать идею, высказываемую в следующей теореме. Теорема 3.3 – Если произвести расчёт параметров заданного сетевого графика по установленным правилам, но заменяя известные длительности работ на те же значения с отрицательным знаком (длительности всех работ будут меньше нуля), то наикратчайший путь сетевого графика станет подчиняться всем свойствам критического пути.
Эту теорему легко доказать, используя правило сравнения отрицательных чисел. Данное правило заключается в том, что одно отрицательное число считается большим другого, если абсолютное значение первого меньше абсолютного значения второго. Поскольку длительность наикратчайшего пути, по абсолютному значению наименьшая, среди длительностей всех других путей сетевого графика, то, на основании указанного правила, отрицательная длительность наикратчайшего пути будет наибольшей среди отрицательных длительностей остальных путей. Тогда, наикратчайший путь, состоящий из работ с отрицательными длительностями, будет критическим, при условии, что все остальные пути, также состоят из работ с отрицательными длительностями. Теорема доказана.
Для проверки доказанной теоремы, параметры сетевого графика на рисунке 2.1 пересчитаны заново, при отрицательных значениях длительностей работ, и представлены на рисунке 3.2 . Как видно, сетевой график на рисунке 3.2 содержит путь, работы которого имеют только нулевые полные резервы времени. Данный путь выделен жирными стрелками. Этот путь, являясь критическим для сетевого графика на рисунке 3.2 , в тоже время является наикратчайшим путем для сетевого графика на рисунке 2.1 . Последнее можно проверить простым суммированием длительностей его работ. Полученная сумма должна быть наименьшей по абсолютному значению, среди аналогичных сумм других путей сетевого графика на рисунке 2.1 .
Вообще говоря, для нахождения продолжительности наикратчайшего пути, необходимой при анализе оптимальности сетевого графика по критерию(1.1), не обязательно суммировать длительности всех, принадлежащих ему работ. Она уже известна из рассчитанных, при отрицательных длительностях работ, параметров сетевого графика, и равна, как и для любого критического пути, сроку свершения завершающего события. Естественно, что данный срок свершения имеет отрицательное значение, и поэтому, для нахождения фактической длительности наикратчайшего пути, требуется менять это значение на противоположное.
Необходимо сказать, что можно поставить и решить общую задачу поиска пути заданной продолжительности. Но данная задача принципиальной важности, при анализе сетевого графика, не несёт. Для анализа оптимальности сетевого графика и осуществления его оптимизации, достаточно знать лишь, как проходят особые пути, и какова их продолжительность. Ответы на эти вопросы и дают рациональные методики поиска особых путей, доказанные в этом разделе.
4 Автоматизация анализа оптимальности сетевых графиков на ЭВМ 1.1 Представление сетевого графика в машинной форме
Любая ЭВМ нуждается в преобразовании различных абстрактных понятий, ясных для человека, в удобную для неё форму. Сетевой график, как графическое изображение упорядоченных кружков и стрелок само по себе для ЭВМ нечего не значить. Для того, чтобы ЭВМ могла понимать структуру сетевого графика и, главное, обрабатывать её, необходимо представить эту структуру в эквивалентной машинной форме.
Наиболее удобный способ представления структуры сетевого графика в машинной форме, основан на понятии матрицы смежностей
. Пример данной матрицы для структуры сетевого графика на рисунке 2.1 представлен на рисунке 4.1 .
Матрица смежностей квадратная и имеет размерность
, где
– число событий сетевого графика. Номера строк матрицы задаются номерами событий
, из которых работы сетевого графика исходят, номера столбцов матрицы задаются номерами событий
, в которые работы сетевого графика входят. На пересечении строки и столбца
, в матрице смежностей, может быть только одно из двух значений: 0 или 1. Если
, то это означает, что на сетевом графике существует работа, исходящая из события с номером
и входящая в событие с номером
. Если
, то такой работы на сетевом графике нет.
Матрица смежностей будет верно отражать структуру сетевого графика, если сетевой график построен по всем, узаконенным стандартом правилам. Здесь, наиболее важны следующие:
Событиям присваиваются номера с таким расчётом, что старший номер соответствует более позднему по времени событию. То есть, если рассмотреть некоторое событие и все входящие в него работы, то номер этого события должен быть больше номеров всех событий, из которых эти работы исходят. В этом случае первая строка и первый столбец матрицы смежностей соответствует начальному событию сетевого графика
, а последние строка и столбец – завершающему событию сетевого графика
, где
– число всех событий в сетевом графике.
Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события, разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. 4.2 ). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответствии с первым правилом.
Верно построенная матрица смежностей обладает радом полезных свойств:
Если задаться некоторым номером события
, то единицы в соответствующей строке укажут на номера событий
, с которыми событие
соединено, исходящими из него работами. Это свойство следует из правила построения матрицы смежностей.
Если задаться некоторым номером события
, то единицы в соответствующем столбце укажут на номера событий
, с которыми событие
соединено, входящими в него работами. Это свойство, также, следует из правила построения матрицы смежностей.
Если некоторое событие
указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события
, то номера этих событий
могут быть только больше номера
, что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежностей могут присутствовать только в верхней диагональной части матрицы (см. рис. 4.1 ).
Любопытно заметить, что если последнее из перечисленных свойств не выполняется, то в сетевом графике есть петли, то есть, работы, концы которых являются началами других работ, предшествующих первым по времени, при условии, что все события занумерованы, верно. Из этого следует возможность легкой автоматизации на ЭВМ процесса проверки правильности построения сетевого графика. Данный процесс проверки, алгоритмически, представляется в виде блок-схемы4.1.
Суть алгоритма проверки заключается в определении содержимого элементов нижней диагональной части матрицы смежностей. Если там встретится хотя бы одна единица, то это будет означать, что сетевой график построен неправильно – либо в нем есть петли, либо события занумерованы не верно.
1.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исходными данными для расчёта, идёт следующая стадия, – непосредственно, сам расчёт параметров сетевого графика. Данная стадия выполняется в три этапа. На первом этапе осуществляется расчёт сетевого графика в порядке – от начального события до завершающего, и определяются ранние сроки свершения событий, ранние начала и окончания работ. На втором этапе осуществляется расчёт сетевого графика в обратном порядке – от завершающего события до начального, и определяются поздние сроки свершения событий, поздние начала и окончания работ. На третьем этапе осуществляется расчёт резервов времени событий и работ, в произвольном порядке.
Рассмотрим расчёт параметров сетевого графика на первом этапе.
Ясно, что в общем случае, при попытке определить ранний срок свершения некоторого события, как максимальный из ранних окончаний всех работ, входящих в это событие, может быть неудача, так как к этому моменту не все ранние сроки окончаний работ могут быть известны. Тогда, встает задача найти такой порядок расчёта сетевого графика, при котором, переходя от события к событию, всегда удаётся находить их ранние сроки свершения. Оказывается, для всех сетевых графиков, с правильно занумерованными событиями этот порядок один и тот же, и основывается на следующей теореме. Теорема 4.1 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт ранних сроков свершения событий в порядке: 0-е событие, 1-е, 2-е, и так далее, до завершающего события, в тупик зайти не может, при условии, что рассчитывая ранний срок свершения очередного события, сразу же определяются ранние окончания всех, исходящих из него работ.
Докажем эту теорему методом математической индукции.
Зададимся нулевым сроком свершения 0-го события, и рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 1-е событие. В него могут входить только работы, исходящие из событий с меньшими номерами – в данном случае только из 0-го события, при этом ранние окончания этих работ уже известны. Тогда можно рассчитать ранний срок свершения 1-го события. Рассчитав ранний срок свершения 1-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 2-е событие. В него могут входить работы, только из 0-го и 1-го события, и ранние окончания которых уже известны. Тогда можем рассчитать ранний срок свершения 2-го события. Рассчитав ранний срок свершения 2-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 3-е событие. В него могут входить работы, только из 0-го, 1-го и 2-го события, и ранние окончания которых уже известны. Тогда можем рассчитать ранний срок свершения 3-го события….
Продолжая данные рассуждения, по индукции, рано или поздно дойдём до завершающего события сетевого графика, ранний срок которого окажется возможным рассчитать, так как к этому времени, уже будут известны ранние окончания всех работ сетевого графика. Теорема доказана.
Из данной теоремы, непосредственно, вырисовывается алгоритм расчёта параметров сетевого графика на первом этапе. Данный алгоритм представлен в виде блок-схемы4.3, и основан на том, что после выполнения алгоритма4.2, в таблице исходных данных и результатов
уже находятся коды работ сетевого графика и их длительности.
Блок-схема4.3 – Алгоритм расчета ранних сроков свершения событий сетевого графика
Рассмотрим расчёт параметров сетевого графика на втором этапе.
В общем случае, при попытке определить поздний срок свершения некоторого события, как минимальный из поздних начал всех работ, исходящих из этого события, может быть неудача, так как к этому моменту не все поздние сроки начал работ могут быть известны. Тогда, встает задача найти такой порядок расчёта сетевого графика, при котором, переходя от события к событию, всегда удаётся находить их поздние сроки свершения. Оказывается, для всех сетевых графиков, с правильно занумерованными событиями этот порядок, опять, один и тот же, и основывается на следующей теореме. Теорема 4.2 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт поздних сроков свершения событий в порядке: последнее событие, предпоследние событие, предшествующее предпоследнему событию, и так далее, до начального (0-го) события, в тупик зайти не может, при условии, что рассчитывая поздний срок свершения очередного события, сразу же определяются поздние начала всех, входящих в него работ.
Докажем эту теорему методом математической индукции.
Зададимся поздним сроком свершения последнего события, равным его раннему сроку свершения, и рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим предпоследнее событие. Из него могут исходит только работы, входящие в события с большими номерами – в данном случае только в последнее событие, при этом поздние начала этих работ уже известны. Тогда можно рассчитать поздний срок свершения предпоследнего события. Рассчитав поздний срок свершения предпоследнего события, сразу же рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим событие, предшествующее предпоследнему. Из него могут исходить работы, только в предпоследнее и в последнее событие, и поздние начала которых уже известны. Тогда можем рассчитать поздний срок свершения события, предшествующего предпоследнему….
Продолжая данные рассуждения, по индукции, рано или поздно дойдём до начального события сетевого графика, поздний срок которого окажется возможным рассчитать, так как к этому времени, уже будут известны поздние начала всех работ сетевого графика. Теорема доказана.
Из данной теоремы, непосредственно, следует алгоритм расчёта параметров сетевого графика на втором этапе. Данный алгоритм представлен в виде блок-схемы4.4, и основан на том, что после выполнения алгоритма4.3, в таблице исходных данных и результатов
уже рассчитаны все ранние сроки свершения событий.
Блок-схема4.4 – Алгоритм расчёта поздних сроков свершения событий сетевого графика
Рассмотрим расчёт параметров сетевого графика на третьем этапе.
Если, сначала выполнить алгоритм расчёта ранних сроков свершения событий4.3, а затем алгоритм расчёта поздних сроков свершения4.4, то в таблице исходных данных и результатов останутся не заполненными только три последних столбца, с номерами: 11, 12 и 13. Данные столбцы, как видно из таблицы4.1, отведены под расчёт резервов времени сетевого графика. Расчёт резервов времени сетевого графика можно осуществить в любом порядке строк таблицы исходных данных и результатов, например, подряд – с 0-й строки по последнюю. Такой порядок расчёта представлен ниже, в виде блок-схемы4.5. Данный алгоритм является завершающим для процесса расчёта параметров сетевого графика, после выполнения которого, все ячейки таблицы исходных данных и результатов4.1, будут заполнены значениями соответствующих параметров.
Блок-схема4.5 – Алгоритм расчёта резервов времени сетевого графика
1.3 Автоматизация процесса поиска особых путей сетевого графика
Как уже известно, найти особые пути сетевого графика представляется возможным только, если будут рассчитаны полные резервы времени всех, входящих в него работ. Тогда, перед поиском особых путей, необходимо выполнять, описанные в предыдущем подразделе алгоритмы по расчёту параметров сетевого графика.
Из раздела3ясно, что для поиска, и критического пути и наикратчайшего, возможно использовать одну и туже методику. Данная методика заключается в последовательном выборе, от 0-го события до завершающего, тех работ, которые имеют нулевые полные резервы времени. В случае, если параметры сетевого графика рассчитывались для положительных длительностей, входящих в него работ, то указанная методика даёт критический путь сетевого графика. Если же параметры рассчитывались при отрицательных длительностях работ, то методика даст наикратчайший путь сетевого графика.
Алгоритм, реализующий методику поиска особого пути сетевого графика, представлен в виде блок-схемы4.6, и основан на том, что таблица исходных данных и результатов
уже полностью рассчитана, либо при положительных, либо при отрицательных длительностях работ.
Имея в арсенале, все рассмотренные в данном разделе алгоритмы, любому программисту не составит труда объединить их в одну, общую программу анализа оптимальности сетевого графика по критерию оптимальности, подробно описанному в разделе1. Проверка данного критерия, с целью выявления оптимальности сетевого графика, на столько проста в алгоритмической реализации, что специального рассмотрения не требует.
Блок-схема4.6 – Алгоритм поиска особого пути сетевого графика
Заключение
В данном курсовом проекте были предложены и обоснованы рациональные методики поиска особых путей сетевых графиков. Рациональность данных методик заключается в том, что они позволяют найти критический и наикротчайший пути сетевого графика без перебора всех возможных вариантов. Последнее, позволяет в короткие сроки осуществить решение двух основных задач сетевого планирования: задачу анализа оптимальности уже готового сетевого графика и задачу его оптимизации по длительности, в случае, если сетевой график оказывается не оптимальным.
Кроме того, в курсовом проекте были рассмотрены вопросы автоматизации на ЭВМ рациональных методик поиска особых путей сетевого графика. В результате – разработаны блок схемы алгоритмов расчёта параметров сетевых графиков и поиска их особых путей, которые предполагается использовать при создании конкретной программы анализа оптимальности сетевых графиков на любом из известных языках программирования.
Значимость проделанной работы заключается в том, что применение предложенных методик, во-первых – позволяет точно судить об оптимальности сетевых графиков любой сложности, а во-вторых – сокращает затраты на сетевое планирование в целом, прежде всего, за счёт сокращения длительности разработки оптимальных сетевых графиков.
Список использованных источников
Технико-экономическое обоснование дипломных проектов проектов: Учеб. Пособие для втузов / Л. А. Астреина, В. В. Балдесов, В. К. Беклешов и др.; Под ред. В. К. Беклешова. – М.: Высш. Шк., 1991. – 176 c.: ил.
