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

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





Оптимальные маршруты транспортной сети                           
Расчетно-графическое задание №1
«Проектирование и оптимизация сетевой модели»
Выполнила:

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

Венгер А.А.

Проверил:

Ширшков А.К.

Личикаки Н.К.
Одесса – 2010

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





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

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

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

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

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

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

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

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

4.     Составить линейные графики Ганта для исходной оптимизированной моделей.
1.     Вычислим кратчайшие маршруты от V₁ до смежных вершин. Расстояние (d_ij) между двумя вершинами, равно длине кратчайшего маршрута.

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




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

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

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

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

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

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

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

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

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

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

L₁₀ = (1, 3, 6, 9, 10) = 7+17+9+16 = 49 дн.
Полный путь – последовательность событий и работ от начального события до конечного.

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

L_кр = max {l_i} = 50 дней = t_кр
Подкритический путь – полный путь, продолжительность которого близка к критическому.
Характеристики события:

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

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

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

R_i = t_iⁿ – t_i^p





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

t₁= 0

t₂= 10

t₃= 7

t₄= 7+13=20

         10+8=18

t₅=    0+14=14      =18

         7+9=16

t₆= 7+17=24

t₇ =    20+11=31   =34

         18+16=34

t₈ = 18+20=38

t₉ =    18+12=30   =33

          24+9=33 

          38+12=50

t₁₀ =   34+15=49     =50

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

t₁₀= 50

t₉= 50-16=34

t₈= 50-12=38

t₇= 50-15=35

t₆= 4-9=25

         34-12=22

t₅=    38-20=18      =18

         35-16=19

t₄=  35-11=24

          25-17=8

t₃=     24-13=11     =8

          18-9=9  

t₂ =  18-8=10

          10-10=0

t₁=     18-14=4      =0

          8-7=1
События имеющие «0» резервов образуют критический путь.
3.       Оптимизация параметров сетевой модели состоит в том, что перераспределяя резервы работ мы минимизируем T_кр, С работы имеющей резерв R_ij >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 вычислено.
Диаграмма Ганта