Файл: 1. Общие правила комбинаторики правила суммы, произведения и биекции. Булеан конечного множества. Примеры.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 71
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
2°. Расстановка отметок. Пусть сеть правильно занумерована. Для каждой вершины вычисляем отметку по следующим правилам:
– полагаем ;
– просматриваем вершины в порядке их номеров и для -ой вершины вычисляем по формуле
, (1)
где максимум берется по всем вершинам , имеющим дугу , направленную в вершину .
По окончании процесса вычисления отметок величина находится как отметка концевой вершины.
3°. Построение критического пути. Начиная с вершины-конца, последовательно находим дуги , для которых . Эти дуги и образуют критический путь.
Резервом времени работы называется величина .
При практическом применении сетевых графиков более удобными по сравнению с резервами времени являются коэффициенты напряженности работ, определяемые как отношение длины максимального пути из начала в конец, проходящего через данную работу, к длине критического пути:
. (4)
Из формулы (4) следует, что , причем для работ с нулевым резервом (лежащих на критическом пути) , а для работ с большим резервом времени – . На основании этого всю совокупность работ делят на зоны: критическую с , подкритическую с , и резервную.
-
Построение сетевого графика по заданной упорядоченности работ.
Будем считать, что задан перечень работ, в совокупности составляющих некоторый проект: .
(Работы пронумерованы и в дальнейшем ссылаемся на каждую работу по ее порядковому номеру).
Предположим далее, что для каждой работы j (1≤ j ≤ n) указаны ее непосредственные предшественники, то есть множество работ, выполнение которых является необходимым условием для начала работы j.
Процедура построения сетевого графика распадается на несколько этапов.
-
Транзитивное замыкание отношения предшествования. Если работа i предшествует работе j, а работа j предшествует работе k, то, очевидно, работа i должна завершиться до начала работы k. Множество работ называется замкнутым (по транзитивности), если вместе с каждой работой оно содержит и всех ее предшественников.
II. Построение конституент для множеств полных предшественников
. Пусть – совокупность всех работ. Разбиение множества Uна непересекающиеся подмножества
(6)
будем называть разбиением на конституенты, если каждое из множеств (5) полных предшественников можно представить в виде объединения некоторых конституент
Ш. Построение сетевого графика
а) Вершинами сетевого графика служат построенные множества ( ) и , ( .
б) Работа изображается дугой с началом в множестве полных предшественников работы и ведущей в конституенту, содержащую работу . На рис. 1 показан фрагмент сетевого графика, содержащий работу 4.
в) Сетевой график содержит также пустые дуги, помогающие обеспечить требуемую упорядоченность работ. Эти дуги не соответствуют работам (или можно считать, что они изображают работы с нулевым временем выполнения) и называются фиктивными. Фиктивные дуги проводятся следующим образом: для каждого представления множеств в виде суммы :
IV. Упрощение графа. Граф, построенный на предыдущем этапе можно упростить, удаляя из него некоторые фиктивные дуги (иногда все). Для этого применяются следующие два правила.
1°. Если фиктивная дуга соединяет вершины, между которыми есть другой путь, то эту дугу следует удалить.
2°. Если единственная дуга, выходящая из вершины (входящая в вершину) является фиктивной, то эту дугу следует удалить и слить ее концы в одну вершину.
Фактическое построение сетевого графика удобно совмещать с упрощениями 1°, 2°. Покажем как строится сетевой график в рассматриваемом примере. Работы помещаются на сетевой график в порядке их появления в исходной таблице, при этом одновременно производятся упрощения.