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

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

Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 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.