Реферат: Проектирование и оптимизация сетевой модели
Название: Проектирование и оптимизация сетевой модели Раздел: Рефераты по информатике Тип: реферат | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Министерство образования и науки Украины Одесский национальный морской университет
Оптимальные маршруты транспортной сети Расчетно-графическое задание №1 «Проектирование и оптимизация сетевой модели» Выполнила: студентка 5к.4гр. Венгер А.А. Проверил: Ширшков А.К. Личикаки Н.К. Одесса – 2010 1. Составить содержательную постановку задачи и построить сетевую информационно-динамическую модель на основе заданных продолжительностей выполнения работ tij :
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
t5 = 0+14=14 =18 7+9=16 t6 = 7+17=24
18+16=34
t9 = 18+12=30 =33 24+9=33
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
t5 = 38-20=18 =18 35-16=19 t4 = 35-11=24
t3 = 24-13=11 =8 18-9=9 t2 = 18-8=10
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 вычислено. Диаграмма Ганта |