|
|
| Курсовая: Сетевые графики |
Таблица результатов работы алгоритма.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | РНАЧ(v) | 0 | 0 | 5 | 8 | 18 | 5 | 12 | 12 | 19 | 24 | 29 | | РВЫП(v) | 0 | 5 | 8 | 18 | 23 | 12 | 19 | 24 | 24 | 29 | 29 |
Получили, что минимальное время, требуемое для выполнения проекта равно
Т=РВЫП(11), Т=29. Теперь найдем посредством алгоритма 2 значение времени
наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде
последовательности выполняемых шагов.
| Шаг n | Действия выполняемые шагом | | 1 | Объявление значений ПВЫП(v), vÎV равным Т. Текущая вершина vk=11. | | 2 | ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 29}. | | 3 | ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 29} ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 29}. | | 4 | Текущая вершина vk=10. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 24}. | | 3 | ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(10)}{ПВЫП(8) стало равным 24} | | 4 | Текущая вершина vk=9. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 24}. | | 3 | ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(9)}{ПВЫП(7) стало равным 24}. | | 4 | Текущая вершина vk=8. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 12}. | | 3 | ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(8)}{ПВЫП(6) стало равным 12}. | | 4 | Текущая вершина vk=7. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 17}. | | 3 | ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 12}. | | 4 | Текущая вершина vk=6. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 5}. | | 3 | ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(6)}{ПВЫП(2) стало равным 5}. | | 4 | Текущая вершина vk=5. | | 5 | Переход в шаг 2. | | 2 | ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 24}. | | 3 | ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(5)}{ПВЫП(4) стало равным 24}. | | 4 | Текущая вершина vk=4. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 14}. | | 3 | ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 14}. | | 4 | Текущая вершина vk=3. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 11}. | | 3 | ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5}. | | 4 | Текущая вершина vk=2. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}. | | 3 | ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}. | | 4 | Текущая вершина vk=1. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}. | | 3 | Переход в Шаг 4. | | 4 | Переход в Шаг 6. | | 6 | Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ. |
Дадим таблицу результатов работы алгоритма с результатами предыдущего
алгоритма и сосчитаем резерв времени для каждой работы по формуле
PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
| Работы | РНАЧ | РВЫП | ПНАЧ | ПВЫП | Резерв | | 1 | 0 | 0 | 0 | 0 | 0 | | 2 | 0 | 5 | 0 | 5 | 0 | | 3 | 5 | 8 | 11 | 14 | 3 | | 4 | 8 | 18 | 14 | 24 | 10 | | 5 | 18 | 23 | 24 | 29 | 5 | | 6 | 5 | 12 | 5 | 12 | 0 | | 7 | 12 | 19 | 17 | 24 | 7 | | 8 | 12 | 24 | 12 | 24 | 0 | | 9 | 19 | 24 | 24 | 29 | 5 | | 10 | 24 | 29 | 24 | 29 | 0 | | 11 | 29 | 29 | 29 | 29 | 0 |
Из таблиы видно, что критическими работами являются 1, 2, 6, 8, 10, 11,
которые и образуют в сети G критический путь. Расчеты выполнены при Т=29.
Пример 3: Проект водоснабжения и наружной канализации при застройки квартала
по ул. Токарей-Синяева в г. Екатеринбурге.
| n | Наименование работы | Предшеству-ющие работы | Время вы-полнения t(vk) | | 1. | Начало проекта (фиктивн. Работа) | Нет | 0 | | 2. | Разработка грунта экскаваторами с ковшом 0.5 м3 с погрузкой на автомобили-самосвалы. | 1 | 16 | | 3. | Зачистка дна и стенок с выкидкой грунта. | 2 | 10 | | 4. | Монтаж водопроводных колодцев | 1 | 32 | | 5. | Монтаж плит перекрытий из легкого бетона. | 3 | 21 | | 6. | Пробивка в бетонных стенах и полах отверстий. | 5 | 5 | | 7. | Оклейка плит рубероидом и гидроизолом на нефтебитуме в 1 слой. | 4,5 | 14 | | 8. | Заделка сальников при проходе труб через фундаменты или стены подвалов. | 5 | 10 | | 9. | Монтаж скоб. | 6 | 7 | | 10. | Устройство стяжек цементных. | 9 | 5 | | 11. | Конец проекта. (фиктивн. Работа) | 7,8,10 | 0 |
Рис 3. Проект водоснабжения и наружной канализации при застройки квартала по
ул. Токарей-Синяева в г. Екатеринбурге.
Найдем значения наиболее раннего начала и выполнения работ проекта
посредством алгоритма 1. Работу алгоритма изложим в виде последовательности
выполняемых шагов.
| Шаг n | Действия выполняемые шагом | | 1 | Объявление значений РНАЧ(v) и РВЫП(v), vÎV равным нулю. Текущая вершина vk=1. | | 2 | Вершин предшествующей первой нет. Значение РНАЧ(1)=РВЫП(1)+t(1). | | 3 | Текущая вершина vk=2. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)}{РНАЧ(2) стало равным 0} РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 16}. | | 3 | Текущая вершина vk=3. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)}{РНАЧ(2) стало равным 16} РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 26}. | | 3 | Текущая вершина vk=4. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(4)=МАКС{РВЫП(1),РНАЧ(4)}{РНАЧ(4) стало равным 0} РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 32}. | | 3 | Текущая вершина vk=5. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 26} РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}. | | 3 | Текущая вершина vk=6. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(6)=МАКС{РВЫП(5),РНАЧ(6)}{РНАЧ(6) стало равным 47} РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 52}. | | 3 | Текущая вершина vk=7. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47 РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 61}. | | 3 | Текущая вершина vk=8. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(8)=МАКС{РВЫП(5),РНАЧ(8)}{РНАЧ(8) стало равным 47} РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 57}. | | 3 | Текущая вершина vk=9. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(9)=МАКС{РВЫП(6),РНАЧ(9)}{РНАЧ(9) стало равным 52} РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным }. | | 3 | Текущая вершина vk=10. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(10)=МАКС{РВЫП(9),РНАЧ(10)}{РНАЧ(10) стало равным 59} РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 64}. | | 3 | Текущая вершина vk=11. | | 4 | Переход в Шаг 2. | | 2 | РНАЧ(11)=МАКС{РВЫП(7),РНАЧ(11)}{РНАЧ(11) стало равным 61} РНАЧ(11)=МАКС{РВЫП(8),РНАЧ(11)}{РНАЧ(11) стало рвным 61} РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 64} РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 64}. | | 3 | Переход в Шаг 5. | | 5 | Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ. |
Таблица результатов работы алгоритма.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | РНАЧ(v) | 0 | 0 | 16 | 0 | 26 | 47 | 47 | 47 | 52 | 59 | 64 | | РВЫП(v) | 0 | 16 | 26 | 32 | 47 | 52 | 61 | 57 | 59 | 64 | 64 |
Получили, что минимальное время, требуемое для выполнения проекта равно
Т=РВЫП(11), Т=64. Теперь найдем посредством алгоритма 2 значение времени
наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде
последовательности выполняемых шагов.
| Шаг n | Действия выполняемые шагом | | 1 | Объявление значений ПВЫП(v), vÎV равным Т. Текущая вершина vk=11. | | 2 | ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 64}. | | 3 | ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(11)}{ПВЫП(7) стало равным 64} ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(11)}{ПВЫП(8) стало равным 64} ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(10)}{ПВЫП(9) стало равным 64}. | | 4 | Текущая вершина vk=10. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 59}. | | 3 | ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(10)} {ПВЫП(9) стало равным 59}. | | 4 | Текущая вершина vk=9. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало ранвым 52}. | | 3 | ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(9)}{ПВЫП(6) стало равным 52}. | | 4 | Текущая вершина vk=8. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 54}. | | 3 | ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(8)}{ПВЫП(5) стало равным 54}. | | 4 | Текущая вершина vk=7. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 50}. | | 3 | ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 50} ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(7)}{ПВЫП(4) стало равным 50}. | | 4 | Текущая вершина vk=6. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 47}. | | 3 | ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(6)}{ПВЫП(5) стало равным 47}. | | 4 | Текущая вершина vk=5. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 26}. | | 3 | ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 26}. | | 4 | Текущая вершина vk=4. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 18}. | | 3 | ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(4)}{ПВЫП(1) стало равным 18}. | | 4 | Текущая вершина vk=3. | | 5 | Переходв Шаг 2. | | 2 | ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 16}. | | 3 | ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 16}. | | 4 | Текущая вершина vk=2. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}. | | 3 | ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}. | | 4 | Текущая вершина vk=1. | | 5 | Переход в Шаг 2. | | 2 | ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}. | | 3 | Переход в Шаг 4. | | 4 | Переход в Шаг 6. | | 6 | Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ. |
Дадим таблицу результатов работы алгоритма с результатами предыдущего
алгоритма и сосчитаем резерв времени для каждой работы по формуле
PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
| Работы | РНАЧ | РВЫП | ПНАЧ | ПВЫП | Резерв | | 1 | 0 | 0 | 0 | 0 | 0 | | 2 | 0 | 16 | 0 | 16 | 0 | | 3 | 16 | 26 | 16 | 26 | 0 | | 4 | 0 | 32 | 18 | 50 | 32 | | 5 | 26 | 47 | 26 | 47 | 0 | | 6 | 47 | 52 | 47 | 52 | 0 | | 7 | 47 | 61 | 50 | 64 | 3 | | 8 | 47 | 57 | 54 | 64 | 10 | | 9 | 52 | 59 | 52 | 59 | 0 | | 10 | 59 | 64 | 59 | 64 | 0 | | 11 | 59 | 64 | 64 | 64 | 0 |
Из таблицы видно, что критическими работами являются 1, 2, 3, 5, 6, 9, 10,
11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=64.
Литература:
1. Асанов М. О. «Дискретная оптимизация», УралНАУКА, Екатеринбург 1998.
Страницы: 1, 2, 3
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
