Основные временные параметры сетевых графиков и их расчеты
КУРСОВАЯ РАБОТА
по предмету: «Математические методы»
на тему: «Основные временные параметры сетевых графиков и их расчеты»
2009
Теория графов – область дискретной математики, которая занимается исследованием и решением разнообразных проблем, связанных с объектом, называемым графом. Граф определяется заданием двух множеств. Первое – 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-го) события определяется величиной пути минимальной продолжительности, ведущего к нему от завершающего события. Выбор этой продолжительности может быть осуществлен по формуле
.
Примем самый поздний срок наступления (8-го) события, равный 36 единицам времени, поскольку ранний срок (по предыдущим расчетам) был равен этому числу.
Определим этот показатель для последующих событий:
При расчетах последующих событий 5,4 и т. д., к которым идут несколько путей, необходимо в полной степени использовать вышеприведенную формулу
;
;
В конце рассчитываем
,
к которому ведут три пути, и, как в
предыдущих расчетах, выбираем минимальный
путь
Полученный результат говорит о том, что расчеты произведены правильно.
На основе этих расчетов определяются резервы времени для событий как разность между самым поздним и самым ранним сроками их наступления. Резервы времени для событий показывают, на какой предельно допустимый период времени может задержаться наступление того или иного события, не вызывая при этом опасности срыва наступления завершающего события. Разумеется, события, находящиеся на критическом пути, не имеют резервов времени. Имеем:
;
;
;
;
;
;
;
;
Следовательно, критический путь проходит от 1-го до 8-го события через 2-, 4- и 6-е события, у которых резервы времени равны нулю.
Обратим внимание на тот факт, что если два события, начальное и конечное, для данной работы критические, то это еще не означает, что связывающая их работа находится на критическом пути. На рассматриваемом графике 2-е и 6-е события — критические, а работа (2,6) не лежит на критическом пути. Это обусловлено тем, что указанные события связаны между собой еще одним путем большей продолжительности, в нашем примере работами (2,4) и (4,6). Следует также сказать и о работе (4,8), связывающей два критических события — 4-е и 8-е.
Работы также могут располагать резервами времени для их выполнения. При этом различают следующие разновидности резервов времени.
Полный резерв времени — это максимально возможный запас времени для выполнения данной работы сверх продолжительности самой работы при условии, что в результате такой задержки конечное для данной работы событие наступит не позднее чем в свой поздний срок. Другими словами, это разница между поздним сроком совершения конечного события и суммой раннего срока наступления начального события и продолжительности работы. Следовательно, полные резервы времени для работ можно вычислить по формуле
,
где
—
полный резерв времени для (i,
j)-й
работы.
Например, полный резерв времени для работы (3,5) составит
.
Значит, работа (3,5) может быть выполнена не за семь дней, а за 27 дней (20 + 7) без задержки выполнения всего комплекса работ, предусмотренных сетевым графиком. Конечно, это предельный максимальный срок, ибо задержка в выполнении работы хотя бы на один день грозит срывом срока наступления завершающего (8-го в нашем примере) события.
Свободный резерв времени — это запас времени, которым можно располагать при выполнении данной работы в предположении, что предшествующее и последующее события этой работы наступают в свои самые ранние сроки. Другими словами, это разница между ранними сроками наступления конечного для работы события и суммой раннего срока наступления начального события и продолжительности работы. Формула для расчета свободного резерва времени имеет вид
,
где
—
свободный резерв времени для (i,
j)-й
работы.
Свободный резерв времени для той или иной работы показывает, насколько можно увеличить продолжительность работы без всякой опасности срыва своевременного выполнения всего комплекса работ, поскольку свободный резерв работы не влияет на резервы времени других работ.
Например, свободный резерв времени для работы (3,5) равен
.
Значит, работу (3,5) можно без всякого риска выполнить за 15 дней (8 + 7) или начать на восемь дней позже, если ее выполнение осуществится за семь дней.
Частный резерв времени первого вида — это запас времени, которым можно располагать в предположении, что начальное и конечное события работы совершаются в свои поздние сроки.
Этот резерв времени равен разности между самым поздним допустимым сроком наступления конечного для работы события и суммой позднего срока наступления начального события и продолжительности работы. Для расчета частного резерва времени второго вида предлагается следующая формула:
,
где
—
частный резерв времени первого вида.
Например, для работы (3,5) этот резерв
составит
,
а для работы (5,8) будет
.
Частный резерв времени второго вида — это запас времени, которым можно располагать при выполнении данной работы, имея в виду, что его использование не повлияет на ранний срок наступления конечного события, а также на величину резервов времени всех остальных работ графика. Этот резерв определяется как разность между самым ранним сроком наступления конечного для данной работы события и суммой самого позднего срока наступления начального для работы события и продолжительности данной работы.
Не для каждой работы существует частный резерв второго вида. Чаще всего бывает, что разность между самым ранним сроком наступления конечного события и самым поздним сроком наступления непосредственно предшествующего события не превышает продолжительности работы или оказывается даже меньше ее. В этом случае резерв для работы принимается равным нулю.
Формула для расчета частного резерва времени второго вида имеет вид
,
где
— частный резерв второго вида для
(i,j)-й
работы.
Например, для работы (3,5) частный резерв второго вида равен
Полученный результат означает следующее: не может случиться так, чтобы 5-е событие наступило в ранний срок, в то время как 3-е событие наступит в поздний срок. Включение в фигурные скобки нуля с указанием перед ним знака дает возможность считать, что указанного вида резерва не существует (ведь отрицательным резерв быть не может).
А вот для работы (5,8) частный резерв первого вида существует:
Расчет основных показателей сетевого графика по формулам, приведенным выше, весьма трудоемкий и проводится, как правило, на электронных вычислительных машинах. Если сетевой график небольшой (около 100 событий), то расчеты можно проводить вручную.
При этом удобно пользоваться табличным способом расчета основных показателей сетевого графика.
Для этого составляется квадратная (шахматная) таблица, количество строк и столбцов которой соответствует количеству событий. Приведем эти расчеты на примере сетевого графика, который нами использован выше. Это одновременно позволит нам проверить правильность получаемых результатов по основным показателям сетевого графика.
Составим табл. 1 из 8 строк и 8 столбцов (по количеству событий в сети). Выделим в ней жирным контуром квадраты по главной диагонали, т.е. квадраты, имеющие одинаковые номера строк и столбцов, в которых они находятся. Эти квадраты будем называть «главными», а остальные квадраты — «побочными». Отметим «побочные» квадраты, находящиеся на пересечении строк и столбцов с номерами непосредственно связанных друг с другом событий. Для квадратов, находящихся выше главной диагонали, номер строки будет соответствовать номеру начального события, а номер столбца — номеру конечного для данной работы события. Наоборот, для квадратов, находящихся ниже главной диагонали, начальному событию будет соответствовать номер столбца, а конечному — номер строки.
В числители отмеченных квадратов запишем продолжительности соответствующих работ. Например, в числитель квадрата, находящегося на пересечении 2-й строки и 6-го столбца (т.е. выше главной диагонали), запишем число 8 (продолжительность работы между 2-м и 6-м событиями); в числитель квадрата, находящегося на пересечении 5-й строки и 3-го столбца (т.е. ниже главной диагонали), записываем число 7 (продолжительность работы между 3-м и 5-м событиями).
Вначале проводятся вычисления знаменателей для отмеченных «побочных» квадратов, находящихся выше главной диагонали.
Вычисления выполняются в следующем
порядке. В первый «главный» квадрат
(т.е. квадрат, относящийся к первому
событию) записываем нуль, а в знаменатели
квадратов первой строки, где проставлены
числители, записываем сумму
.
В нашем примере
;
;
.
Переносим знаменатель квадрата
(1,2), равный в нашем примере 4, в числитель
«главного» квадрата 2-го столбца, а в
знаменателе отмеченного квадрата 2-й
строки, где проставлены числители,
записываем сумму 4 + / (2, у); в нашем примере
;
(рис. 2).
Далее переносим знаменатель
квадрата (1,3), равный в нашем примере 2,
в числитель «главного» квадрата 3-го
столбца, а в знаменатели квадратов 3-й
строки записываем сумму
;
.
Затем переносим максимальный из
знаменателей квадратов 4-го столбца
(выше главной диагонали) в числитель
«главного» квадрата этого столбца (в
нашем примере max {12; 14}), а в знаменатели
«побочных» квадратов 4-й строки записываем
сумму
;
;
.
Поступая аналогично, определяем
знаменатели для всех «побочных» квадратов
выше главной диагонали (во всех случаях
в числитель «главных» квадратов
записываем наибольший из знаменателей
«побочных» квадратов, находящихся в
данном столбце выше главной диагонали).
Проведя все эти расчеты, получим определенное число для последнего «главного» квадрата (в нашем примере 36 — наибольший из знаменателей последнего столбца).
Теперь проведем вычисления знаменателей для «побочных» квадратов, находящихся ниже главной диагонали. Расчеты проводим в обратном порядке, начиная с последнего «главного» квадрата. Из числа, записанного в этом квадрате, вычитаем числители в «побочных» квадратах нижней строки и результат записываем в знаменатели. Минимальный из знаменателей данного столбца переносим в «главный» квадрат (знаменатель). Из него опять вычитаем числители в «побочных» квадратах соответствующей строки и получаем знаменатели, наименьший из которых переносим в «главный» квадрат.
Для событий, лежащих на критическом пути, числители и знаменатели «главных» квадратов совпадают, и для первого «главного» квадрата должен получиться нуль. На этом вычисления заканчиваются.
Из табл. 1 получаем показатели сетевого графика:
продолжительность критического пути (число в последнем «главном» квадрате);
ранние сроки наступления событий (величины числителей в «главных» квадратах);
самые поздние сроки наступления событий (величины знаменателей в «главных» квадратах);
резервы времени для событий (разность между знаменателем и числителем в каждом «главном» квадрате). Для событий, находящихся на критическом пути, как известно, резервы времени равны нулю. Это значит, что в квадратах, соответствующих критическим событиям, числители и знаменатели должны быть равны;
самые ранние сроки окончания работ (величины знаменателей в «побочных» квадратах выше главной диагонали); самые поздние сроки начала работ (величины знаменателей в «побочных» квадратах ниже главной диагонали);
полные резервы времени для работ (разность между знаменателем «главного» квадрата и знаменателем «побочного» квадрата для данной работы выше главной диагонали, но в том же столбце); свободные резервы времени для работ (разность между числителем «главного» квадрата и знаменателем «побочного» квадрата для данной работы выше главной диагонали).
Путем простейших арифметических действий можно определить и все остальные показатели сетевого графика. Так, частный резерв времени первого вида для работы (i,j) определяется путем вычитания из знаменателя «главного» квадрата j-го события знаменателя «главного» квадрата i-го события и числителя «побочного» квадрата выше главной диагонали, содержащего продолжительность (i,j)-й работы. Частный резерв второго вида для работы (i,j) определяется путем вычитания из числителя «главного» квадрата j-го события знаменателя квадрата i-го события и числителя «побочного» квадрата, соответствующего (i,j)-й работе и находящегося выше главной диагонали.
Пример. Пусть дан сетевой график (рис. 2).
Ранние сроки наступления событий:
/р(1) = 0;
*р(2) = 7р (1) + /(1, 2) = 0 + 4 = 4;
*р(3) = *р(1) + *.(1,3) = 0 + 2 = 2;
tp (4) = max {tp (1) + t (1, 4); tp (2) + / (2, 4);
/p(3) + /(3, 4)} = max{0 + 7; 4 + 1; 2 + 2} = 7;
fp(5) = fp(4) + f(4,5)=7+3 = 10; i tp (6) = max {*p (2) + t (2, 6); tp (4) + / (4, 6); tp(5) + + /(5,6)} = max (4 +8; 7+12; 10+ 7} =19; /p(7) = max{/p(3) + /(3,7); tp (5) + / (5, 7)} = max (2 + 9; 10 + 2} = 12; tp (8) = max (tp (5) + t (5, 8); tp (6) + / (6, 8); tp(7) + t(7, 8)} = max{10 + 7; 19 + 10; 12 + 5} = 29. Поздние сроки наступления событий: U8) =29;
tn(7) = tn(8)-t(7, 8) = 29-5= 24; 'л(6) = /,(8)-/(6, 8) = 29- 10 = 19; *я (5) - min (tn (8) - / (5, 8); tn (7) -1 (6, 7)} =
= min{29—4; 24 — 2} = 22; *„ (4) = min {/. (5) -1 (4,5); *„ (6) -1 (4, 6)} =
= min {22 — 3; 19 —12} = 7;
\A(3) = min{U7)-<(3, 7);
W*)— /(3,'4)} = min(22-9; 7-2} = 5; /„(2}=min{/n(4)-f(2, 4); tn((>)-t(2, 6)} =
= min (7 — 1; 19 —8} = 6; /я(1) = пнп{*в(2)-*(1,2); ^(3)-/(1,3); ^(4) — /(1,4)} = min{6 -4; 5-2; 7-7} = 0.
Резервы времени для событий:
Р(1) = /л(1)-'р(1) = 0-0 = 0; Р(2)=7л(2)-^(2) = 6-4 = 2; P(3) = <B(3)-/p(3)=i6-2 = 3; Р(4) = /л(4)-^(4) = 7-7-0;
Р (5) =•*„ (5) - tp (5) = 22 - 10 = 12;
Р(6) = гл(6)-М6)=19-19 = 0;
P(7) = ta(7)-tp(7) =24-12= 12;
Р(8) = /„(8) — /р(8) = 29 — 29 = 0.
Расчеты временных параметров системы графика табличным методом рекомендуется учащимся провести самостоятельно (рис. 21). По рис. 22 рекомендуется провести расчеты обоими способами.
Список литературы:
Математика и кибернетика в экономике. Словарь-справочник. Изд. 2-е, перераб. и доп. М., «Экономика», 1975. 700с.
Хруцкий Е.А Экономико-математические методы в планировании материально-технического снабжения. М., «Экономика», 1976. 287с.