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

Автор работы: Пользователь скрыл имя, 06 Июня 2010 в 19:37, Не определен

Описание работы

Дискретное программирование

Файлы: 1 файл

Венгер РГЗ 1.doc

— 92.00 Кб (Скачать файл)

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

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

 
 
 
 
 
 
 
 
 

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

Расчетно-графическое  задание №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
 
  1. Вычислить информационные параметры сетевой  модели:
    1. все полные пути Li и их продолжительности Ti ;
    1. критический путь Lкр , Tкр и подкритические пути;
    2. раннее tip и позднее tin время наступления событий;
    3. резервы времени событий Ri ;
    4. полные резервы времени каждой работы
    5. свободный резерв времени каждой работы
  1. Оптимизировать параметры сетевой модели за счет перераспределения резервов работ с целью минимизации критического времени Tкр.
  1. Составить линейные графики Ганта для исходной оптимизированной моделей.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  1. Вычислим  кратчайшие маршруты от V1 до смежных вершин. Расстояние (dij) между двумя вершинами, равно длине кратчайшего маршрута.

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

    

    

    

    

    

      

      
 
 

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

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

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

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

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