рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Образование
- /
- Орграф без контуров с неотрицательными
Реферат Курсовая Конспект
Орграф без контуров с неотрицательными
Орграф без контуров с неотрицательными - раздел Образование, Календарное (Сетевое) Планирование Сетевая Модел...
Календарное (сетевое) планирование
Сетевая модель:
вершины – события (завершение одних видов работ и начало других видов работ – выходящих из вершин);
дуги – работы
орграф без контуров с неотрицательными
весами вершин или дуг
|  … ð  контур
простой путь
 … ð  цикл
|
Проект –совокупность частично упорядоченных работ, направленных на достижение некоторой цели.
Пример: проект из 6 работ и их длительности.
Найти:
1) Диаграмму Ганта;
2) Правильную нумерацию;
3) Кратчайший срок и кратчайший путь.
| Работа | Предшествование | Длительность |
| A | - | |
| B | - | |
| C | A | |
| D | B,C | |
| E | B | |
| F | E,D |
Диаграмма Ганта
Например, работа D – критическая (её задержка приведёт к задержке всего проекта)
Сеть «работы - дуги»
| S | |||||||
| (is,js)) | (1,2) | (1,6) | (2,3) | (3,4) | (4,5) | (6,4) | (6,3) |
| τs |
Вычисление параметров сети
Опр. Рангом Ri события (вершины) i называется максимальное число дуг в пути из входной 1 в вершину i. Ранги событий находят по рекурсивной формуле: Rk(j)= … k(j) – концевая вершина;Алгоритм Форда
Шаг 1. Последовательностно просматриваем дуги (работы) и пересчитываем ранги их концевых вершин: S = 1 ð (1, 2): R2 = max {R2, R1 +1} = max {0, 0+1} = 1; S = 2 ð (1, 6): R6 = max {R6, R1 +1} = max {0, 0+1} = 1;Был сетевой график
Введём правильную нумерацию:
Ø Входу (вершине нулевого ранга) ð 1;
Ø Вершинам ранга 1 (вершинам 2,6) ð номера 2 и 3 соответственно;
Ø Вершинам ранга 2 (вершине 3) ð номер 4;
Ø Вершинам ранга 3 (вершине 4) ð номер 5;
Ø Вершинам ранга 4 (вершине 5) ð номер 6.
Новый сетевой график
Задача о кратчайшем сроке выполнения проекта Алгоритм ФордаАлгоритм Форда
t’i s = max {tis, tjs+τs}. Шаг 1. 1. S =(1, 2): t’1 = min {t1, t2 - τ1 } = min {19, 19-3} = 16;– Конец работы –
Используемые теги: Орграф, без, контуров, неотрицательными0.074
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Орграф без контуров с неотрицательными
Что будем делать с полученным материалом:
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.13 сек.
Новости и инфо для студентов