Сетевой граф


Рубрика: Прочее

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

Сетевой граф Решение: Исходный граф содержит замкнутый контур – работы 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 дней будет выполнен. Скачать прилагающиеся файлы

Оставьте комментарий!

grin LOL cheese smile wink smirk rolleyes confused surprised big surprise tongue laugh tongue rolleye tongue wink raspberry blank stare long face ohh grrr gulp oh oh downer red face sick shut eye hmmm mad angry zipper kiss shock cool smile cool smirk cool grin cool hmm cool mad cool cheese vampire snake excaim question

Комментарий будет опубликован после проверки

Вы можете войти под своим логином или зарегистрироваться на сайте.

(обязательно)