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

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

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

 
 
 
 
 
 
 
 
 

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

Расчетно-графическое  задание №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 дней.

Уменьшились все резервы работ и изменился критический путь.