Пример. Решение задачи сетевого планирования

1.

Решение задачи сетевого планирования.

Задача.

При разработке проекта водонасосных станций было выделено 8 станций (событий) и 15 связывающих их путей (работ) с указанием их продолжительности, т.е. пропускной способности.

t(0,1)=3 t(2,5)=1

t(0,2)=4 t(3,5)=3

t(0,3)=2 t(4,6)=2

t(1,2)=1 t(4,7)=4

t(1,4)=3 t(5,6)=2

t(2,3)=3 t(5,7)=3

t(2,4)=1 t(6,7)=2

t(2,6)=2

Каждой дуге поставлено в соответствие число

c(i,j) – пропускная способность.

ƒ(i,j) – поток по этой дуге.

ƒ (i,j) ≤ c(i,j)

Требуется:

1. Построить график сетевых потоков.

2. Найти несколько полных путей.

3. Построить линейную диаграмму сетевого графика и определить по нему критический путь и протяженность α_кр, т.е. max возможный поток воды.

Решение.

α₁=(0->1->4->7)

α₂=(0->3->5->7) и т.д.

2. Построить линейную диаграмму.

§28 Аналитический способ определения α_кр и t_кр

О₁

Ранний срок свершения события равен величине наиболее длинного

отрезка путей от исходного события до рассматриваемого.

реккурентное соотношение для

определения раннего срока

совершения события

О₂

Последний срок свершения события i характеризует самый поздний

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

при этом срока начального события.

Аналитически определить t_р(j).

i=0 t_р(0)=0

i=1 t_р(1)=max {t_р(0)+t(0;1)}=0+3=3

i=2 t_р(2)=max { t_р(0)+t(0;2); t_р(1)+ t(1;2)}= max {0+3;3+1}=4

i=3 t_р(3)=max { t_р(0)+t(0;3); t_р(2)+ t(2;3)}= max {0+2;4+3}=7

i=4 t_р(4)=max { t_р(1)+t(1;4); t_р(2)+ t(2;4)}= max {3+3;4+1}=6

i=5 t_р(5)=max { t_р(2)+t(2;5); t_р(3)+ t(3;5)}= max {4+1;7+3}=10

i=6 t_р(6)=max { t_р(2)+t(2;6); t_р(4)+ t(4;6); t_р(5)+ t(5;6)}= max {4+2;6+2;10+2}=12

i=7 t_р(7)=max { t_р(5)+t(5;7); t_р(6)+ t(6;7); t_р(4)+ t(4;7)}= max {6+4;10+3;12+2}=14

t_кр =14 усл. ед.вр.

α_kp.(6;7)→ (5;6)→ (3;5)→ (2;3)→ (1;2)→ (0;1)

Дата добавления: 2014-11-08