Реферат: по дискретной математике
Контрольная работа по дискретной математике.
Задание 1.
На рисунке изображен граф. Его дуги обозначены буквами a – p. Обозначить произвольным образом вершины графа. Взяв из таблицы вариантов данные о длине его дуг, определить:
1. Кратчайший путь из начальной вершины в конечную, и длину кратчайшего пути.
2. Критический путь из начальной вершины в конечную, и длину критического пути.
3. Считая этот граф сетевым графиком некоторого процесса, а длины дуг – временем осуществления работ, определить:
— для каждой вершины-события ранний и поздний срок его свершения и его резерв времени,
— для каждой дуги-работы независимый резерв времени.
Варианты:
№ | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p |
1 | 4 | 5 | 3 | 5 | 6 | 4 | 2 | 7 | 4 | 8 | 2 | 8 | 6 | 2 | 1 | 4 |
2 | 3 | 3 | 4 | 2 | 5 | 7 | 4 | 3 | 3 | 5 | 8 | 2 | 2 | 6 | 7 | 3 |
3 | 3 | 4 | 4 | 3 | 2 | 1 | 3 | 5 | 5 | 4 | 3 | 4 | 7 | 1 | 2 | 2 |
4 | 3 | 4 | 4 | 4 | 4 | 4 | 6 | 6 | 7 | 3 | 8 | 5 | 1 | 4 | 1 | 3 |
5 | 3 | 2 | 1 | 4 | 6 | 3 | 1 | 1 | 5 | 3 | 6 | 7 | 8 | 4 | 2 | 6 |
6 | 3 | 2 | 2 | 4 | 5 | 2 | 6 | 9 | 4 | 5 | 2 | 3 | 4 | 2 | 6 | 7 |
7 | 3 | 5 | 5 | 4 | 6 | 7 | 2 | 3 | 4 | 5 | 6 | 3 | 6 | 3 | 2 | 5 |
8 | 3 | 4 | 4 | 4 | 2 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 3 | 1 | 3 | 3 |
9 | 3 | 6 | 4 | 3 | 5 | 6 | 2 | 5 | 2 | 5 | 6 | 2 | 5 | 3 | 4 | 3 |
10 | 3 | 4 | 1 | 7 | 4 | 7 | 3 | 4 | 2 | 5 | 2 | 5 | 1 | 3 | 7 | 5 |
11 | 3 | 4 | 3 | 5 | 6 | 4 | 2 | 7 | 4 | 8 | 2 | 8 | 6 | 2 | 1 | 4 |
12 | 5 | 3 | 5 | 2 | 5 | 7 | 4 | 3 | 3 | 5 | 8 | 2 | 2 | 6 | 7 | 3 |
13 | 5 | 4 | 4 | 2 | 2 | 1 | 3 | 5 | 5 | 4 | 3 | 4 | 7 | 1 | 2 | 2 |
14 | 4 | 4 | 4 | 4 | 1 | 4 | 6 | 6 | 7 | 3 | 8 | 5 | 1 | 4 | 1 | 3 |
15 | 4 | 2 | 1 | 4 | 6 | 6 | 1 | 1 | 5 | 3 | 6 | 7 | 8 | 4 | 2 | 6 |
16 | 6 | 2 | 2 | 4 | 5 | 2 | 7 | 9 | 4 | 5 | 2 | 3 | 4 | 2 | 6 | 3 |
17 | 5 | 5 | 5 | 4 | 6 | 7 | 2 | 8 | 4 | 5 | 6 | 3 | 6 | 3 | 7 | 5 |
18 | 4 | 4 | 4 | 4 | 2 | 2 | 3 | 1 | 4 | 3 | 4 | 2 | 3 | 6 | 3 | 3 |
19 | 6 | 6 | 4 | 3 | 5 | 6 | 2 | 5 | 2 | 8 | 6 | 2 | 4 | 3 | 4 | 3 |
20 | 7 | 4 | 1 | 7 | 4 | 7 | 3 | 4 | 2 | 5 | 1 | 6 | 1 | 3 | 7 | 5 |
21 | 8 | 5 | 3 | 5 | 6 | 4 | 2 | 7 | 4 | 8 | 2 | 8 | 6 | 2 | 1 | 4 |
22 | 6 | 3 | 4 | 2 | 5 | 7 | 4 | 3 | 3 | 5 | 8 | 2 | 2 | 6 | 7 | 3 |
23 | 7 | 4 | 4 | 3 | 2 | 1 | 3 | 5 | 5 | 4 | 3 | 4 | 7 | 1 | 2 | 2 |
24 | 6 | 4 | 4 | 4 | 4 | 4 | 6 | 6 | 7 | 3 | 8 | 5 | 1 | 4 | 1 | 3 |
25 | 6 | 2 | 1 | 4 | 6 | 3 | 1 | 1 | 5 | 3 | 6 | 7 | 8 | 4 | 2 | 6 |
26 | 6 | 2 | 2 | 4 | 5 | 2 | 6 | 9 | 4 | 5 | 2 | 3 | 4 | 2 | 6 | 7 |
27 | 7 | 5 | 5 | 4 | 6 | 7 | 2 | 3 | 4 | 5 | 6 | 3 | 6 | 3 | 2 | 5 |
28 | 8 | 4 | 4 | 4 | 2 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 3 | 1 | 3 | 3 |
Задание 2.
Проект состоит из последовательного выполнения работ u1, u2, u3, u4 .
Для каждой работы ui () определена зависимость ее стоимости si от времени ее осуществления ti.
1. Предполагая, что , определить:
a) время осуществления работ , для которых общая стоимость проекта минимальна при условии, что весь проект должен быть закончен не позднее времени Tmax. Также найти при этих условиях минимальную стоимость проекта и стоимость осуществления каждой работы .
Значения , Tmax для каждого варианта даны в столбцах 2 — 6 таблицы вариантов
б) стоимости работ , для которых общее время осуществления проекта минимально при условии, что общая стоимость проекта не более Smax. Также найти при этих условиях минимальное время осуществления проекта и время осуществления каждой работы .
Значения , Smax для каждого варианта даны в столбцах 2 – 5 и 7 таблицы вариантов.
2. Предполагая, что зависимость si от ti линейная и убывающая, и зная для каждой работы ui ее минимальное и максимальное время осуществления и , а также минимальную и максимальную стоимость и определить:
a) время осуществления работ , для которых общая стоимость проекта минимальна при условии, что весь проект должен быть закончен не позднее времени Tmax. Также найти при этих условиях минимальную стоимость проекта и стоимость осуществления каждой работы .
Значения , , , , Tmax для каждого варианта даны в столбцах 8 – 15 и 6 таблицы вариантов.
б) стоимости работ , для которых общее время осуществления проекта минимально при условии, что общая стоимость проекта не более Smax. Также найти при этих условиях минимальное время осуществления проекта и время осуществления каждой работы .
Значения , , , , Smax для каждого варианта даны в столбцах 8 – 15 и 7 таблицы вариантов.
Варианты:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
№ вар-та. | a1 | a2 | a3 | a4 | Tmax | Smax |
|
|
|
|
|
|
|
|
1 | 6 | 5 | 3 | 1 | 10 | 40 |
|
|
|
|
|
|
|
|
2 | 2 | 3 | 4 | 2 | 15 | 70 |
|
|
|
|
|
|
|
|
3 | 3 | 6 | 4 | 2 | 10 | 10 |
|
|
|
|
|
|
|
|
4 | 3 | 4 | 1 | 7 | 10 | 40 |
|
|
|
|
|
|
|
|
5 | 3 | 2 | 1 | 4 | 10 | 30 |
|
|
|
|
|
|
|
|
6 | 3 | 2 | 5 | 4 | 15 | 20 |
|
|
|
|
|
|
|
|
7 | 3 | 5 | 9 | 4 | 20 | 70 |
|
|
|
|
|
|
|
|
8 | 3 | 4 | 2 | 1 | 25 | 20 |
|
|
|
|
|
|
|
|
9 | 3 | 6 | 4 | 1 | 10 | 60 |
|
|
|
|
|
|
|
|
10 | 3 | 4 | 1 | 7 | 10 | 70 |
|
|
|
|
|
|
|
|
11 | 3 | 4 | 8 | 5 | 10 | 40 |
|
|
|
|
|
|
|
|
12 | 5 | 3 | 7 | 2 | 15 | 70 |
|
|
|
|
|
|
|
|
13 | 5 | 4 | 3 | 2 | 20 | 10 |
|
|
|
|
|
|
|
|
14 | 4 | 2 | 1 | 3 | 10 | 40 |
|
|
|
|
|
|
|
|
15 | 4 | 2 | 1 | 3 | 20 | 60 |
|
|
|
|
|
|
|
|
16 | 6 | 1 | 2 | 4 | 25 | 20 |
|
|
|
|
|
|
|
|
17 | 5 | 3 | 2 | 4 | 25 | 70 |
|
|
|
|
|
|
|
|
18 | 4 | 2 | 1 | 5 | 20 | 20 |
|
|
|
|
|
|
|
|
19 | 6 | 2 | 4 | 3 | 10 | 60 |
|
|
|
|
|
|
|
|
20 | 7 | 4 | 1 | 3 | 15 | 70 |
|
|
|
|
|
|
|
|
21 | 8 | 5 | 3 | 9 | 10 | 40 |
|
|
|
|
|
|
|
|
22 | 6 | 3 | 4 | 2 | 20 | 70 |
|
|
|
|
|
|
|
|
23 | 7 | 4 | 9 | 3 | 25 | 10 |
|
|
|
|
|
|
|
|
24 | 6 | 7 | 9 | 5 | 20 | 40 |
|
|
|
|
|
|
|
|
25 | 6 | 2 | 1 | 4 | 20 | 30 |
|
|
|
|
|
|
|
|
26 | 6 | 2 | 3 | 4 | 15 | 20 |
|
|
|
|
|
|
|
|
27 | 7 | 5 | 6 | 4 | 20 | 70 |
|
|
|
|
|
|
|
|
28 | 8 | 1 | 3 | 4 | 20 | 20 |
|
|
|
|
|
|
|
|