КУРСОВАЯ РАБОТА
попредмету: «Математические методы»
на тему:«Основные временные параметры сетевых графиков и их расчеты»
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)-
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) =
Р (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 рекомендуется провести расчеты обоимиспособами.
Списоклитературы:
1. Математика икибернетика в экономике. Словарь-справочник. Изд. 2-е, перераб. и доп. М.,«Экономика», 1975. 700с.
2. Хруцкий Е.АЭкономико-математические методы в планировании материально-техническогоснабжения. М., «Экономика», 1976. 287с.