Проектирование и оптимизация сетевой модели

Министерство образования и науки Украины

Одесский национальный морской университет

Оптимальные маршруты транспортной сети

Расчетно-графическое задание №1

«Проектирование и оптимизация сетевой модели»

Выполнила:

студентка 5к.4гр.

Венгер А.А.

Проверил:

Ширшков А.К.

Личикаки Н.К.

Одесса – 2010

1. Составить содержательную постановку задачи и построить сетевую информационно-динамическую модель на основе заданных продолжительностей выполнения работ tij
:

Индекс работы i→j	Продолжи-тельность работы tij	Индекс работы i→j	Продолжи-тельность работы tij	Индекс работы i→j	Продолжи-тельность работы tij
1 – 2	10	4 – 6	16	6 – 9	7
1 – 3	7	4 – 7	19	7 – 8	5
2 – 4	2	5 – 7	5	7 – 10	10
2 – 5	9	5 – 8	11	8 – 10	14
3 – 4	6	6 – 7	4	9 – 10	5

2. Вычислить информационные параметры сетевой модели:

1) все полные пути Li
и их продолжительности Ti
;

2) критический путь L
кр
, T
кр
и подкритические пути;

3) раннее ti
p
и позднее ti
n
время наступления событий;

4) резервы времени событий Ri
;

5) полные резервы времени каждой работы

6) свободный резерв времени каждой работы

3. Оптимизировать параметры сетевой модели за счет перераспределения резервов работ с целью минимизации критического времени T
кр
.

4. Составить линейные графики Ганта для исходной оптимизированной моделей.

1. Вычислим кратчайшие маршруты от V1
до смежных вершин. Расстояние (dij
) между двумя вершинами, равно длине кратчайшего маршрута.

Построим ориентированный граф расстояний от V1
до V9
и траекторию кратчайшего маршрута.

2. Определим все полные пути.

L1
= (1, 2, 5, 8, 10) = 10+8+20+12 = 50
дн.

L2
= (1, 2, 5, 9, 10) = 10+8+12+16 = 46 дн.

L3
= (1, 5, 9, 10) = 14+12+16 = 42 дн.

L4
= (1, 5, 8, 10) = 14+20+12 = 46 дн.

L5
= (1, 5, 7, 10) = 14+16+15 = 45 дн.

L6
= (1, 3, 5, 9, 10) = 7+9+12+16 = 44 дн.

L7
= (1, 3, 5, 8, 10) = 7+9+20+12 = 48 дн.

L8
= (1, 3, 5, 7, 10) = 7+9+16+15 = 48 дн.

L9
= (1, 3, 4, 7, 10) = 7+13+11+15 = 46 дн.

L10
= (1, 3, 6, 9, 10) = 7+17+9+16 = 49 дн.

Полный путь

– последовательность событий и работ от начального события до конечного.

Критический путь

– максимальный по продолжительности полный путь.

Lкр
= max {li
} = 50 дней = tкр

Подкритический путь

– полный путь, продолжительность которого близка к критическому.

Характеристики события:

ti
p
– раннее время наступления события.

ti
n
– позднее время наступления события.

Ri
– резерв времени события.

Ri
= ti
n
– ti
p

Раннее
время событий вычисляется прямым ходом, т. е.

двигаясь от начального события к конечному.

t1
= 0

t2
= 10

t3
= 7

t4
= 7+13=20

10+8=18

t5
= 0+14=14 =18

7+9=16

t6
= 7+17=24

t7
= 20+11=31 =34

18+16=34

t8
= 18+20=38

t9
= 18+12=30 =33

24+9=33

38+12=50

t10
= 34+15=49 =50

33+16=49

Позднее
время событий вычисляется обратным ходом, двигаясь от конечного события к начальному.

t10
= 50

t9
= 50-16=34

t8
= 50-12=38

t7
= 50-15=35

t6
= 4-9=25

34-12=22

t5
= 38-20=18 =18

35-16=19

t4
= 35-11=24

25-17=8

t3
= 24-13=11 =8

18-9=9

t2
= 18-8=10

10-10=0

t1
= 18-14=4 =0

8-7=1

События имеющие «0» резервов образуют критический путь.

3. Оптимизация параметров сетевой модели состоит в том, что перераспределяя резервы работ мы минимизируем Tкр
, С работы имеющей резерв Rij
>0, снимаем часть ресурсов в пределах резерва, при этом продолжительность этой работы увеличивается.

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

Примечание:
Если у сетевой модели есть несколько критических путей, то переброска резервов должна осуществляться на все параллельные участки критических путей.

Выбираем работу, имеющую максимальный резерв.

В результате первой переброски у нас появилось 2 критических пути, что позволяет нам сделать еще 2 переброски.

Переброска резерва с работы Т → на работу критического пути Т → в объеме 3 дней позволило уменьшить Ткр
с 52 дней до 51 дней.