p align="left">Таблица результатов работы алгоритма.|
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), vV равным Т. Текущая вершина 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), vV равным нулю. Текущая вершина 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), vV равным Т. Текущая вершина 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
|
