Сетевой граф

Задание: Упорядочить исходный сетевой граф и определить временные характеристики

Решение: Исходный граф содержит замкнутый контур – работы 4, 6, 7. Путем введения фиктивной работы 11 получают следующий сетевой граф без замкнутого контура:

Упорядочивание сетевого графа производится путем размещения всех событий по слоям: слева направо. Исходное событие 1 размещают на первом слое. Далее вычеркиваются из графа все исходящие работы из исходного события. На втором слое размещаются события без входящих работ 2, 4. Далее вновь вычеркиваются работы из события второго слоя. Аналогично размещаются события на следующих слоях. В результате получается следующий граф:

Все работы в сетевом графе должны быть направленными от события с меньшим номером к событию с большим. Поэтому необходимо произвести перенумерацию событий:.

Определим параметры сетевых графов.

Если событие j имеет несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:

Задержка свершения события I по отношению к своему раннему сроку не отразится на сроке свершения завершающего события (а значит на сроке выполнения комплекса работ) до тех пор, пока сумма срока свершения этого события и продолжительности (длины) максимального из последующих за ним путей не превысит длины критического пути. Если событие i имеет несколько последующих событий j, то поздний срок свершения события I удобно находить по формуле:

Аналогично определены остальные поздние сроки Резерв времени R(i) i-го события определяется как разность между поздним и ранним сроками его свершения:

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

 

Lкр={0,2,4,6,7,10,11} Lкр= 45

Определим параметры работ.

Проведем оптимизацию сетевого графа. Граничные значения продолжительностей работ a(i,j) и b(i,j), их стоимости с(i,j), коэффициенты затрат на ускорение работ h(i,j) приведены в таблице. Ранний срок tрн(i,j) начала работы (i,j) совпадает с ранним сроком наступления начального (предшествующего) события i, то есть:

Тогда ранний срок tро(i,j) окончания работы (i,j) определяется по формуле:

Ни одна работа не может окончиться позже допустимого позднего срока своего конечного события i. Поэтому поздний срок tпо(i,j) окончания работы (i,j) определяется соотношением:

а поздний срок tпн(i,j) начала этой работы – соотношением:

Полный резерв времени Rп(i,j) работы (i,j) показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв времени Rп(i,j) определяется по формуле:

Резерв времени первого рода R1 работы (i,j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. Этим резервов можно располагать при выполнении данной работы в предположении, то ее начальное и конечное события свершатся в свои самые поздние сроки.

 

Резерв времени второго рода, или свободный резерв времени Rc работы (i,j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Этим резервов можно располагать при выполнении данной работы в предположении, то ее начальное и конечное события свершатся в свои самые ранние сроки.

Независимый резерв времени Rн работы (i,j) – часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки:

После вычислений была получена следующая таблица:

 

 

Оптимизация стоимости выполнения работ. Проведем оптимизацию сетевого графа по схеме «время-стоимость». Оптимизация сетевого графа представляет процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения. При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа (i,j) характеризуется продолжительностью t(i,j), которая может находиться в пределах где – минимально возможная (экстренная) продолжительность работы (i,j), которую только можно осуществить в условиях разработки (исходная величина); –максимальная продолжительность выполнения работы (i,j) (исходная величина) Величина равная тангенсу угла a наклона аппроксимирующей прямой, показывает затраты на ускорение работы (i,j) (по сравнению с нормальной продолжительность) на единицу времени: Стоимость работы (i,j) заключена в границах от (при нормальной продолжительности работы) до (при экстренной продолжительности работы). Допустимый размер увеличения продолжительности данной работы: Оптимальное время продолжительности работы Теперь можно найти изменение стоимости работы Dс(i,j) при сокращении ее продолжительности на величину При этом стоимость проекта после оптимизации можно найти по формуле: В результате всех вычислений получаем следующую таблицу:

Оптимальная стоимость работ равна Сопт=502,7 руб., то есть стоимость всех работ уменьшилась на величину:

руб.

dt(i,j) – размер увеличения продолжительности работы; h(i,j) - коэффициент затрат на ускорение работ; tопт - оптимальная продолжительность работы; dC – изменение стоимости работы; В результате такой оптимизации сетевого графа мы не меняем продолжительность выполнения всего проекта, а за счет увеличения продолжительности некоторых работ, имеющих свободный резерв времени, уменьшаем стоимость выполнения работ.

В результате получаем, что в критической зоне(>0.8) находятся работы (0,2) (2,4) (4,6) (6,7) (6,9) (7,10) (7,11) (9,11) (10,11). В подкритической зоне(<0.8) находятся работы (0,1) (0,3) (1,2) (3,4). В резервной зоне(<0.6) находятся работы (1,5) (2,6) (3,5) (3,7) (4,10) (5,8) (5,11) (5,7) (8,9) (8,11).

 

Сетевое планирование в условиях неопределенности При определении временных параметров сетевого графика до сих пор предполагалось, что время выполнения каждой работы точно известно. Но чаще всего продолжительность работы по сетевому графику не известна и может принимать лишь одно из возможных значений. Другими словами, продолжительность работы t(i, j) является случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми характеристиками – средним значением (математическим ожиданием) (i, j) и дисперсией (i, j). Закон распределения обладает следующими свойствами:

• непрерывность;
• унимодальность, т. е. наличие единственного максимума у кривой распределения;
• положительная асимметрия, т. е. максимум кривой смещен влево относительно медианы.

Этими свойствами обладает ?-распределение. Предположим, что даны 3 оценки продолжительности выполняемых работ:

• Оптимистическая оценка tо(i, j) , т. е. продолжительность работы (i,j) при самых благоприятных условиях:
• Пессимистическая оценка tп(i, j) , т. е. продолжительность работы (i,j) при самых неблагоприятных условиях:
• Наиболее вероятная оценка tнв(i, j) , т. е. продолжительность работы (i,j) при самых нормальных условиях:

На основе этих 3 величин можно выделить для ?-распределение среднее значение продолжительности работ по формуле:

Дисперсия находится по формуле:

Следует отметить, что обычно специалистам сложно оценить наиболее вероятное время выполнения работы (i, j) . Поэтому в проектах используется упрощенная оценка средней продолжительности работы (i,j) на основании лишь двух задаваемых временных оценок (i, j) и (i, j):

Кроме характеристик работ необходимо найти характеристики пути, для ?-распределения можно воспользоваться центральной предельной теоремой Ляпунова на основании которой можно утверждать, что продолжительность пути L имеет нормальный закон распределения (НЗР), тогда средняя продолжительность работ принадлежит этому пути и вычисляется как сумма средних значений:

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

Если P( ? T) мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер. Если P( ? T) значительна (более 0,8), то очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок. В некоторых случаях представляет интерес и решение обратной задачи: определение максимального срока выполнения проекта Т, который возможен с заданной надежностью (вероятностью) ?. В этом случае:

где, Z? - нормированное отклонение случайной величины, определяемое с помощью функции Лапласа Ф(z? ) = ?. Рассмотрим сетевой граф в условиях неопределенности. Найдем для данного сетевого графика средние значения и дисперсии работ. При этом оценим вероятность выполнения проекта в срок Т = 50 суткам.

Вероятность того, что работы будут выполнены в срок . Обратная задача – задача распределения максимального срока выполнения проекта Т с надежностью

,

То есть с надежностью 0,95 срок выполнения проекта не превысит 52 дня.

То есть с надежностью 0,93 проекта в течении 52 дней будет выполнен. Скачать прилагающиеся файлы