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

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

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





















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



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



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





















Выполнила:

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

Венгер А.А.

Проверил:

Ширшков А.К.

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





















Одесса – 2010

Составить содержательную постановку задачи и построить сетевую информационно-динамическую модель на основе заданных продолжительностей выполнения работ 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



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

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

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

раннее tip и позднее tin время наступления событий;

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

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

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

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

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







































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

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





























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

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кр



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



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

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

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

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

Ri = tin – tip















































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

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» резервов образуют критический путь.











	Оптимизация параметров сетевой модели состоит в том, что перераспределяя резервы работ мы минимизируем 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 вычислено.

	

	

	

	Диаграмма Ганта