Курсовая работа: Основные временные параметры сетевых графиков и их расчеты

Теория графов – область дискретной математики, которая занимается исследованием и решением разнообразных проблем, связанных с объектом, называемым графом. Граф определяется заданием двух множеств. Первое – X – множество вершин графа. Элементы этого графа можно изобразить в виде точек плоскости или пространства. Второе – U – множество пар элементов из Х. Каждый элемент множества U указывает пару вершин, между которыми существует связь; она может изображаться линией, соединяющей соответствующие вершины графа. При таком изображении требуется, чтобы линия проходила только через вершины, которые она соединяет, и чтобы разные линии могли пересекаться только в вершинах. Иногда в парах составляющих множество U, указывается, какая вершина является первой. В этом случае элементы множества U называются дугами графа (X, U), а сам граф – ориентированным. Если ориентация не указана, то элементы U называются ребрами, а граф (X, U) – неориентированным графом или про сто графом. Элемент U, указывающий на связь вершины с ней самой , называется петлей.

Граф (X, U) называется конечным, если множества X и U состоят из конечного числа элементов. В противном случае граф (X, U) называется бесконечным.

Основные временные параметры сетевых графиков и их расчеты

Важнейшим параметром сетевого графика является критический путь. Путем в сетевом графике называется любая последовательность работ(стрелок), связывающая какие-либо два события. При этом пути, связывающие исходные и завершающие события сети, считается полными, а все другие пути – неполными. Каждый путь характеризуется своей продолжительностью, которая равна сумме продолжительностей составляющих его работ.

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

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

Для каждого события, включенного в сетевой график, рассчитываются следующие показатели:

Ранний срок наступления события, характеризующий наиболее ранний из возможных сроков совершения того или иного события;

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

Резерв времени наступления событий, который определяется как разность между поздним и ранним сроками наступления события.

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

Расчет основных временных параметров производится по соответствующим формулам.

Ранний срок наступления любого последующего события (j-го) определяется величиной пути максимальной продолжительности, ведущего к нему от исходного события. Выбор этой продолжительности может быть осу­ществлен по следующей формуле:

Производя расчеты, удобно принимать, что ранний срок наступления исходного (1-го) события равен нулю, т.е. Тогда

Поскольку к событию 2 идет только один путь от события 1, то выбирать максимальные продолжительности путей не приходится: . Сказанное только что относится и к данному расчету. Поиному обстоит дело, когда мы подошли к событию 4. К нему ведут два пути: прямой от события 1 и опосредствованный событием 2. Здесь надо использовать во всей полноте нижеприведенную формулу:

Имеем:

Значит, 4-е событие сможет наступить на 14-й день от общего начала работ (но не через 7 дней, как это может показаться вначале).

Продолжаем расчеты. Очередным является событие 5. К нему ведут два пути: от события 4 и от события 3. Применяем формулу

Аналогично поступаем и с расчетами ранних сроков наступления событий 6 и 7:

Затем рассчитываем . К событию 8 ведут четыре пути, поэтому придется иметь дело с выбором макси­мальной величины из четырех слагаемых.

Следовательно, завершающее (8-е) событие может наступить лишь на 36-й день от начала выполнения всего комплекса работ.

Поздний срок наступления любого предыдущего (i-го) события определяется величиной пути минимальной продолжительности, ведущего к нему от завершающего события. Выбор этой продолжительности может быть осуществлен по формуле

--> ЧИТАТЬ ПОЛНОСТЬЮ <--