Министерство образования и науки Украины
Одесский национальный морской университет
Оптимальные маршруты транспортной сети
Расчетно-графическое задание №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 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации.
Переброска резерва с работы Т → на работу критического пути Т 6→9 в объеме 3-х дней позволило изменить Ткр
с 51 дней до 50 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации.
Переброска резерва с работы Т → на работу критического пути Т → в объеме 3-х дней позволило изменить Ткр
с 50 дней до 49 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации.
Переброска резерва с работы Т → на работу критического пути Т → в объеме -х дней позволило изменить Ткр
с 49 дней до 48 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации
Переброска резерва с работы Т 7→ 10 на работу критического пути Т 8→ 10 в объеме 3-х дней позволило изменить Ткр
с 48 дней до 45 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации
Переброска резерва с работы Т → на работу критического пути Т → в объеме -х дней позволило изменить Ткр
с 45 дней до 44 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации
Переброска резерва с работы Т → на работу критического пути Т → в объеме -х дней позволило изменить Ткр
с 44дней до 43 дней.
Уменьшились все резервы работ и изменился критический путь.
Выполним еще одну итерацию по оптимизации
Переброска резерва с работы Т → на работу критического пути Т → в объеме -х дней позволило изменить Ткр
с 43дней до 42 дней.
Резервы сетевой модели исчерпаны, так как только 2 работы имеют резервы и появилось 5 критичных путей.
Ткр
min вычислено.
Диаграмма Ганта
|
