Лекция по дискретной математике

Главная Учебники - Разные Лекции (разные) - часть 51

Лекция по дискретной математике

Контрольная работа по дискретной математике.

Задание 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.

Проект состоит из последовательного выполнения работ u₁ , u₂ , u₃ , u₄ .

Для каждой работы u_i ( ) определена зависимость ее стоимости s_i от времени ее осуществления t_i .

1. Предполагая, что , определить:

a) время осуществления работ , для которых общая стоимость проекта минимальна при условии, что весь проект должен быть закончен не позднее времени T_max . Также найти при этих условиях минимальную стоимость проекта и стоимость осуществления каждой работы .

Значения , T_max для каждого варианта даны в столбцах 2 - 6 таблицы вариантов

б) стоимости работ , для которых общее время осуществления проекта минимально при условии, что общая стоимость проекта не более S_max . Также найти при этих условиях минимальное время осуществления проекта и время осуществления каждой работы .

Значения , S_max для каждого варианта даны в столбцах 2 – 5 и 7 таблицы вариантов.

2. Предполагая, что зависимость s_i от t_i линейная и убывающая, и зная для каждой работы u_i ее минимальное и максимальное время осуществления и , а также минимальную и максимальную стоимость и определить:

a) время осуществления работ , для которых общая стоимость проекта минимальна при условии, что весь проект должен быть закончен не позднее времени T_max . Также найти при этих условиях минимальную стоимость проекта и стоимость осуществления каждой работы .

Значения , , , , T_max для каждого варианта даны в столбцах 8 – 15 и 6 таблицы вариантов.

б) стоимости работ , для которых общее время осуществления проекта минимально при условии, что общая стоимость проекта не более S_max . Также найти при этих условиях минимальное время осуществления проекта и время осуществления каждой работы .

Значения , , , , S_max для каждого варианта даны в столбцах 8 – 15 и 7 таблицы вариантов.

Варианты:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

№

вар-та.

a₁

a₂

a₃

a₄

T_max

S_max

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