Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

,

или, в соответствии с выражением (2.8) для полного резерва времени,

. (3.1)

Теперь рассмотрим, какое может иметь значение полный резерв времени ра­боты, исходящей из события 1 и входящей в событие 2. В соответствии с форму­лой (2.8):

. (3.2)

Из формулы (3.2) видно, что минимально возможное значение полного ре­зерва времени работы, исходящей из события 1 и входящей в событие 2, достига­ется тогда, когда величина достигает своего максимального значения. Из правила определения раннего срока свершения события, задаваемого формулой (2.1), следует, что максимальное значение этой величины может быть равно только раннему сроку свершения события 2, когда ранний срок окончания рассматривае­мой работы самый большой из всех ранних сроков окончания работ, входящих в событие 2. Тогда, минимально возможное значение полного резерва времени ра­боты, исходящей из события 1 и входящей в событие 2 равно:

,

или, исходя из формулы (3.1):

. (3.3)

Поскольку мы предположили от противного, что среди всех исходящих из события 2 работ нет работ с нулевым полным резервом времени, то отсюда сразу вытекает, что и работа, исходящая из события 1 и входящая в событие 2, также не может иметь нулевой полный резерв времени, уж если его минимальное значение заведомо неравно нулю, в соответствии с полученным равенством (3.3). Последнее противоречит условию теоремы. Из этого противоречия следует то, что невоз­можна ситуация, когда при нулевом резерве времени работы, входящей в событие 2, все исходящие из этого события работы имели бы ненулевые резервы времени. Если бы это имело место, то в соответствии с приведённым доказательством, ра­бота, входящая в событие 2 также бы имела ненулевой полный резерв времени. Но ведь это не так по условию теоремы. Тогда для работ, исходящих из события 2 ос­таётся другая возможная ситуация – хотя бы одна из них имеет также нулевой полный резерв времени. Теорема доказана.

Из доказанных выше теорем, непосредственно, следует методика поиска критического пути, приводимая ниже.

Рациональная методика поиска критического пути сетевого графика:

1. Просмотр сетевого графика ведётся от его начального события к конеч­ному;

2. При рассмотрении начального события сетевого графика, в качестве ра­боты, лежащей на критическом пути, выбирается та, которая имеет нулевой пол­ный резерв времени. В соответствии с теоремой 3.1 (утверждение-необходимость), такая работа обязательно будет существовать;

3. При рассмотрении работ, исходящих из события, к которому привила ра­бота с нулевым полным резервом времени, выбирается работа, также имеющая нулевой полный резерв времени. В соответствии с теоремой 3.2, такая работа су­ще­ствует;

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

Реализация указанных правил даёт путь, состоящий только из работ с нуле­выми полными резервами времени. Тогда, на основании теоремы 3.1 (утвержде­ние-достаточность), этот путь и будет являться критическим.

В целях проверки, доказанная методика применена для сетевого графика, представленного на рисунке Error: Reference source not found. Здесь, найденные критические пути, выделены жирными стрелками. Как видно, таких путей два, благодаря тому, что среди работ, исходящих из события 0, есть две работы с нулевыми полными резервами вре­мени. Проверить то, что найденные пути являются критическими легко, просум­мировав длительности принадлежащих им работ. Суммы окажутся: во-первых, равными между собой, а во-вторых, наибольшими среди аналогичных сумм дру­гих возможных путей.

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

Теорема 3.3 – Если произвести расчёт параметров заданного сетевого гра­фика по установленным правилам, но заменяя известные длительности работ на те же значения с отрицательным знаком (длительности всех работ будут меньше нуля), то наикратчайший путь сетевого графика станет подчиняться всем свойст­вам кри­тического пути.

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

Для проверки доказанной теоремы, параметры сетевого графика на рисунке Error: Reference source not foundпересчитаны заново, при отрицательных значениях длительностей работ, и пред­ставлены на рисунке Error: Reference source not found. Как видно, сетевой график на рисунке Error: Reference source not foundсодержит путь, работы которого имеют только нулевые полные резервы времени. Данный путь выделен жирными стрелками. Этот путь, являясь критическим для сетевого гра­фика на рисунке Error: Reference source not found, в тоже время является наикратчайшим путем для сетевого гра­фика на рисунке Error: Reference source not found. Последнее можно проверить простым суммированием дли­тельностей его работ. Полученная сумма должна быть наименьшей по абсо­лют­ному значению, среди аналогичных сумм других путей сетевого графика на ри­сунке Error: Reference source not found.

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

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

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

4.1Представление сетевого графика в машинной форме

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

Наиболее удобный способ представления структуры сетевого графика в ма­шинной форме, основан на понятии матрицы смежностей . Пример данной матрицы для структуры сетевого графика на рисунке Error: Reference source not foundпредставлен на рисунке Error: Reference source not found.

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

Матрица смежностей будет верно отражать структуру сетевого графика, если сетевой график построен по всем, узаконенным стандартом правилам. Здесь, наиболее важны следующие:

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

• Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события, разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. Error: Reference source not found). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответст­вии с первым правилом.

Верно построенная матрица смежностей обладает радом полезных свойств:

• Е
  сли задаться некоторым номером события , то единицы в соответст­вующей строке укажут на номера событий , с которыми событие соединено, исходящими из него работами. Это свойство следует из правила построения мат­рицы смежностей.

• Если задаться некоторым номером события , то единицы в соответст­вующем столбце укажут на номера событий , с которыми событие соеди­нено, входящими в него работами. Это свойство, также, следует из правила по­строения матрицы смежностей.

• Если некоторое событие указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события , то номера этих событий могут быть только больше номера , что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежно­стей могут присутствовать только в верхней диагональной части матрицы (см. рис. Error: Reference source not found).

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

Характеристики

Список файлов реферата