Сетевые графики

| Категория реферата: Рефераты по математике
| Теги реферата: реферат великая, скачать шпаргалки по истории
| Добавил(а) на сайт: Dovmont.

3. Присвоить значению ПВЫП(v) для всех работ v(ПРЕДШ(v) предшествующих текущей работе vk минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы vk, если таковых нет перейти в Шаг 4.

4. Если имеется предыдущая вершина (работа) к текущей, то объявить её текущей, иначе перейти в Шаг 6.

5. Перейти в Шаг 2.

6. Выдать наиболее поздние допустимые сроки выполнения и начала работ ПВЫП(v) и ПНАЧ(v), конец работы алгоритма.
Проиллюстрируем работу приведенных алгоритмов на следующих примерах:

Пример 1: Проект гаража для стоянки автопогрузчиков.

|n |Наименование работы |Предшеству-ю|Время |
| | |щие работы |вы-полнения |
| | | |t(vk) |
|1 |Начало проекта (фиктивн. работа) |Нет |0 |
|2 |Срезка растительного слоя грунта |1 |5 |
|3 |Монтаж каркаса |2 |30 |
|4 |Обшивка стен профнастилом |3 |15 |
|5 |Кровля из профнастила |3 |12 |
|6 |Заполнение проема воротами |4 |5 |
|7 |Масляная окраска ворот и |5,6 |10 |
| |профнастила | | |
|8 |Щебёночное основание под полы |7 |3 |
|9 |Асфальтовое покрытие |8 |3 |
|10 |Уборка строительного мусора после |7 |3 |
| |строит. | | |
|11 |Конец проекта (фиктивная работа) |9,10 |0 |

[pic]

Рис 1. Проект гаража для стоянки автопогрузчиков.

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

|Шаг n |Действия выполняемые шагом |
|1 |Объявление значений РНАЧ(v) и РВЫП(v), v(V равными нулю. |
| |Текущая вершина vk=1. |
|2 |Вершин предшествующей первой нет. |
| |РВЫП(1)=РНАЧ(1)+t(1). {РНАЧ(1) стало равным 0} |
|3 |Текущая вершина vk=2. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0} |
| |РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 5}. |
|3 |Текущая вершина vk=3. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5} |
| |РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 35}. |
|3 |Текущая вершина vk=4. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)}{РНАЧ(4) стало равным 35} |
| |РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 50}. |
|3 |Текущая вершина vk=5. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 35} |
| |РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}. |
|3 |Текущая вершина vk=6. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(6)=МАКС{РВЫП(4),РНАЧ(6)}{РНАЧ(6) стало равным 50} |
| |РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 55}. |
|3 |Текущая вершина vk=7. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47} |
| |РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)}{РНАЧ(7) стало равным 55} |
| |РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 65}. |
|3 |Текущая вершина vk=8. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(8)=МАКС{РВЫП(7),РНАЧ(8)} {РНАЧ(8) стало равным 65} |
| |РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 68}. |
|3 |Текущая вершина vk=9. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(9)=МАКС{РВЫП(8),РНАЧ(9)}{РНАЧ(9) стало равным 68} |
| |РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 71}. |
|3 |Текущая вершина vk=10. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(10)=МАКС{РВЫП(7),РНАЧ(10)}{РНАЧ(10) стало равным 65} |
|3 |Текущая вершина vk=11. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)}{РНАЧ(11) стало равным 71} |
| |РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 71}|
|3 |Переход в Шаг 5. |
|5 |Конец работы алгоритма, выдача значений наиболее раннего |
| |начала и выполнения работ. |

Таблица результатов работы алгоритма.
|n |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |
|РНАЧ(v) |0 |0 |5 |35 |35 |50 |55 |65 |68 |65 |71 |
|РВЫП(v) |0 |5 |35 |50 |47 |55 |65 |68 |71 |68 |71 |

Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.

|Шаг n |Действия выполняемые шагом |
|1 |Объявление значений ПВЫП(v), v(V равным Т. |
| |Текущая вершина vk=11. |
|2 |ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 71}. |
|3 |ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 71} |
| |ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 71} |
|4 |Текущая вершина vk=10. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 68} |
|3 |ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(10)}{ПВЫП(7) стало равным 68} |
|4 |Текущая вершина vk=9. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 68} |
|3 |ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(9)}{ПВЫП(8) стало равным 68} |
|4 |Текущая вершина vk=8. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 65} |
|3 |ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(8)}{ПВЫП(7) стало равным 65} |
|4 |Текущая вершина vk=7. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 55} |
|3 |ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 55} |
| |ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 55} |
|4 |Текущая вершина vk=6. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 50} |
|3 |ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(6)}{ПВЫП(5) стало равным 50} |
|4 |Текущая вершина vk=5. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 43} |
|3 |ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 43} |
|4 |Текущая вершина vk=4. |
|5 |Переход в Шаг 2. |
|2 |ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 35} |
|3 |ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 35} |
|4 |Текущая вершина vk=3. |
|5 |Переход в шаг 2. |
|2 |ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 5} |
|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)=ПНАЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
|Работы |РНАЧ |РВЫП |ПНАЧ |ПВЫП |Резерв |
|1 |0 |0 |0 |0 |0 |
|2 |0 |5 |0 |5 |0 |
|3 |5 |35 |5 |35 |0 |
|4 |35 |50 |35 |50 |0 |
|5 |35 |47 |43 |55 |8 |
|6 |50 |55 |50 |55 |0 |
|7 |55 |65 |55 |65 |0 |
|8 |65 |68 |65 |68 |0 |
|9 |68 |71 |68 |71 |0 |
|10 |65 |68 |68 |71 |3 |
|11 |71 |71 |71 |71 |0 |

Из таблицы видно, что критическими работами являются 1, 2, 3, 4, 6, 7,
8, 9, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=71.

Пример 2: Проект склада сажи и других материалов в помещение производственного цеха.
|n |Наименование работы |Предшеству-ю|Время |
| | |щие работы |вы-полнения |
| | | |t(vk) |
|1. |Начало проекта (фиктивн. работа) |Нет |0 |
|2. |Монтаж металлоконструкций нижней |1 |5 |
| |обвязки каркаса | | |
|3. |Устройство бетона под стойки |2 |3 |
|4. |Монтаж стоек |3 |10 |
|5. |Монтаж опорных столиков |4 |5 |
|6. |Монтаж балок |2 |7 |
|7. |Монтаж металлоконструкций ворот |6 |7 |
|8. |Обшивка стен и кровли волнистым |6 |12 |
| |листом | | |
|9. |Монтаж козлового крана |7 |5 |
|10.|Устройство асфальтобетонных |8 |5 |
| |покрытий | | |
|11.|Конец проекта (фиктивн. работа) |5,9,10 |0 |

[pic]

Рис 2. Проект склада сажи и других материалов в помещение производственного цеха.

Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 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) стало равным 5}. |
|3 |Текущая вершина vk=3. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5} |
| |РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 8}. |
|3 |Текущая вершина vk=4. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)} {РНАЧ(4) стало равным 8} |
| |РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 18}. |
|3 |Текущая вершина vk=5. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(5)=МАКС{РВЫП(4),РНАЧ(5)} {РНАЧ(5) стало равным 18} |
| |РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 23}. |
|3 |Текущая вершина vk=6. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(6)={РВЫП(2),РНАЧ(6)} {РНАЧ(6) стало равным 5} |
| |РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 12}. |
|3 |Текущая вершина vk=7. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)} {РНАЧ(7) стало равным 12} |
| |РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 19}. |
|3 |Текущая вершина vk=8. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(8)=МАКС{РВЫП(6),РНАЧ(8)} {РНАЧ(8) стало равным 12} |
| |РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 24}. |
|3 |Текущая вершина vk=9. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(9)=МАКС{РВЫП(7),РНАЧ(9)} {РНАЧ(9) стало равным 19} |
| |РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 24}. |
|3 |Текущая вершина vk=10. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(10)=МАКС{РВЫП(8),РНАЧ(10)} {РНАЧ(10) стало равным 24}|
| | |
| |РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 29}. |
|3 |Текущая вершина vk=11. |
|4 |Переход в Шаг 2. |
|2 |РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)} {РНАЧ(11) стало равным 24}|
| | |
| |РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(10)}{РНАЧ(11) стало равным 29}|
| | |
| |РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 29}. |
|3 |Переход в Шаг 5. |
|5 |Конец работы алгоритма, выдача значений наиболее раннего |
| |начала и выполнения работ. |

Таблица результатов работы алгоритма.
|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. |Разработка грунта экскаваторами с |1 |16 |
| |ковшом 0.5 м3 с погрузкой на | | |
| |автомобили-самосвалы. | | |
|3. |Зачистка дна и стенок с выкидкой |2 |10 |
| |грунта. | | |
|4. |Монтаж водопроводных колодцев |1 |32 |
|5. |Монтаж плит перекрытий из легкого |3 |21 |
| |бетона. | | |
|6. |Пробивка в бетонных стенах и полах|5 |5 |
| |отверстий. | | |
|7. |Оклейка плит рубероидом и |4,5 |14 |
| |гидроизолом на нефтебитуме в 1 | | |
| |слой. | | |
|8. |Заделка сальников при проходе труб|5 |10 |
| |через фундаменты или стены | | |
| |подвалов. | | |
|9. |Монтаж скоб. |6 |7 |
|10.|Устройство стяжек цементных. |9 |5 |
|11.|Конец проекта. (фиктивн. Работа) |7,8,10 |0 |

[pic]

Рис 3. Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге.