- •Е.В. Сорокина дискретная МатЕматика
- •1. Множества и основные операции над ними
- •1.1. Множества, способы их задания Вопросы для повторения
- •1.2. Основные операции над множествами Вопросы для повторения
- •Тестовые задания
- •2. Основные понятия комбинаторики
- •2.1. Перестановки, размещения и сочетания Вопросы для повторения
- •2.2. Бином Ньютона Вопросы для повторения
- •Тестовые задания
- •3. Алгебра логики
- •3.1. Логика высказываний и предикатов
- •Вопросы для повторения
- •3.1.1. Определения и свойства логических операций. Сложные высказывания
- •3.1.2. Таблицы истинности
- •3.2. Булевы функции
- •Вопросы для повторения
- •3.2.1. Определения и свойства логических операций. Сложные высказывания
- •3.2.2. Минимизация булевых функций с помощью карт Карно
- •3.2.3. Анализ и синтез комбинационных устройств в заданном базисе
- •Тестовые задания
- •4. Элементы теории графов
- •4.1. Основные понятия теории графов Вопросы для повторения
- •4.2. Сетевое планирование Вопросы для повторения
- •5. Теория алгоритмов и конечные автоматы
- •5.1. Алгоритмы Вопросы для повторения
- •5.2. Построение конечных автоматов Вопросы для повторения
- •Список рекомендуемой литературы
- •Оглавление
- •Дискретная математика
4.2. Сетевое планирование Вопросы для повторения
1. Перечислите этапы сетевого планирования.
2. Сформулируйте правила построения сетевой модели.
3. Поясните порядок расчета сроков начала и окончания работ.
4. Что такое критический путь?
5. Поясните порядок выбора критического пути.
4.5 Перечень работ указан в табл. 4.1.
Таблица 4.1.
Перечень работ к задаче 4.5
Работа |
Предшествующие работы |
А1 |
- |
А2 |
- |
А3 |
А1 |
А4 |
А1 |
А5 |
А2 |
А6 |
А2 |
А7 |
А2, А3 |
А8 |
А4, А5 |
Построить сетевую модель в соответствии с этой таблицей.
Решение
Построим сетевую модель в соответствии с табл. 4.1 (рис. 4.3).
Рис. 4.3. Сетевая модель к задаче 4.5
Фиктивная операция Д1 введена, чтобы отобразить отношения следования.
Конечным результатом выполняемых на сетевой модели расчетов является календарный график. Этот график легко «привязать» к реальной шкале времени, удобной для выполнения программ.
4.6. Дан перечень выполняемых работ (табл.4.2).
Таблица 4.2.
Перечень работ к задаче 4.6
Работа |
Предшествующие работы |
Продолжительность, ч |
А1 |
- |
10 |
А2 |
- |
30 |
А3 |
А1 |
10 |
А4 |
А1 |
15 |
А5 |
А2 |
15 |
А6 |
А2 |
25 |
А7 |
А2, А3 |
20 |
А8 |
А4, А5 |
15 |
А9 |
А6 |
30 |
А10 |
А8 |
15 |
А11 |
А8, А9 |
15 |
А12 |
А7, А8 |
10 |
А13 |
А11 |
5 |
Построить сетевой граф, календарный график.
Решение
Построим сетевую модель в соответствии с табл. 4.2 (рис. 4.4).
Рис. 4.4. Сетевая модель к задаче 4.6
Вычислим сроки работ при прямом и обратном проходе по формулам ); а также полный и свободный резервы времени по формулам PПi,j = tnj - tpi - ti,j, PСi,j = tpj - tpi - ti,j. Результаты расчетов занесем в табл.4.3.
Таблица 4.3
Результаты расчетов к задаче 4.6
Операция |
Ветвь графа |
Резерв |
Потребн. |
|||||
Обозначение Аi |
Продол- жит. ti,j,ч |
Наименован. Ui,j |
Начал о tpi |
Окончание tpj tnj |
полный РПi,j |
свободн. PCi,j |
в раб. силе чел. |
|
А1 |
10 |
U0,1 |
0 |
10 |
55 |
45 |
0 |
1 |
А2* |
30 |
U0,2 |
0 |
30 |
30 |
0 |
0 |
3 |
A3 |
10 |
U1,3 |
10 |
30 |
75 |
55 |
10 |
1 |
A4 |
15 |
U1,4 |
10 |
45 |
0 |
45 |
20 |
2 |
A5 |
15 |
U2,4 |
30 |
45 |
0 |
25 |
0 |
2 |
A6* |
25 |
U2,5 |
30 |
55 |
55 |
0 |
0 |
3 |
A7 |
20 |
U3,6 |
30 |
60 |
95 |
45 |
10 |
2 |
A8 |
15 |
U4,7 |
45 |
60 |
85 |
25 |
0 |
2 |
A9* |
30 |
U5,8 |
55 |
85 |
85 |
0 |
0 |
3 |
A10 |
15 |
U7,10 |
60 |
105 |
105 |
30 |
30 |
1 |
A11* |
15 |
U8,9 |
85 |
100 |
100 |
0 |
0 |
2 |
A12 |
10 |
U6,10 |
60 |
105 |
105 |
35 |
35 |
2 |
A13* |
5 |
U9,10 |
100 |
105 |
105 |
0 |
0 |
1 |
Построить календарный график.
Построить графики потребности в рабочей силе при раннем и позднем сроках начала работ.
Тестовые задания
Задан граф:
1. Указать элемент матрицы смежности (3,2)
Ответы:
1. 0 2.+2 3. +1
2. Указать элемент матрицы инцидентности (3,1)
Ответы:
1. 0 2.+1 3. -1