Corrigé de l’examen de Février 2002

Exercice 1   :

1. M =

2. Le graphe est convexe. Cherchons les composantes fortement connexes : 1 2 3 4 5 6 pred. 1 préd. 31 X X 02 X X 13 X X X X 1 04 X

5 X X X 2 16 X X 1

succ. 1 0 1 1succ. 3 1 1 0 1 1 2

t(1) = {1, 2, 6} {1, 2, 3, 5, 6} = {1, 2, 6}La composante fortement connexe de 1 comprend les éléments 1, 2 et 6.

t(3)= {1, 2, 3, 4, 5, 6} {3, 5} = {3, 5}La composante fortement connexe de 3 comprend les éléments 3 et 5.La composante fortement connexe de 4 est composée du singleton 4.

D’où trois classes : {1, 2, 6} = classe récurrente, non périodique{3, 5}= classe transitoire{4} = classe récurrente.

3. Etudions la sous-chaîne {1, 2, 6}

Posons . Cherchons * = (a, b, c), la matrice des probabilités de l’état stationnaire (a=

proba d’avoir 1, b d’avoir 2, c d’avoir 6)

On doit avoir * P’ = * d’où

On cherche N =

Exercice 2   : PERT :

A :4

E :30

0 0

1

3 3

2

2 3

3

7 7

5

9 9

4

6 7

610 10

7

12 12

8

14 16

9

16 16

I :2 B :1 D :2

F :3

G :2

C :3 H :41

2 3

4

Tâches critiques : E A I C H.

Exercice 3   :

1.

Les arcs double et en bleu sont saturés, les arcs en pointillés et rouges sont nuls.La solution est optimale : méthode de marquage qui permet de marquer seulement les sommets : déb., A1, A2 et A4. Le flux maximal est donc de 57.

2. On aurait pu faire entrer en A1 19 milliers de m3/j de plus et sortir de B (8+12+6=) 26 unités. Essayons de faire passer 30 unités sur A1B.On aurait pu faire entrer en F 12 unités de plus et sortir de Q3 17 unités supplémentaires. Essayons de faire passer 18 unités sur FQ1.

Nouveau flot optimal   : 71 En modifiant d’abord A1B :

Nouveau flot optimal : 59 unités

C

Q1

Q2

Q3

A1

A2

87/8

B

11

8

A3

15

8/11

8

A4

15D

6

11/23

23

23

6/11

E

F

6/11

45

15

6

déb.fin

4/23

15

23

15/25

21/23

30

6/23

+

+

-

7/8

A28

A3

15

8/11

A4

15

déb.

18/23

15

23

15/25

A1

8

B

25/30

8

D

2/6

23

23

23

6/11

E

F

8/11

Q1

Q2

Q3

45

15

18

23

30 fin

18/23

Q1

Q2

Q3

A1

A2

87/8

B

13/30

8

A3

15

8/11

8

A4

15D

6

13/23

23

23

10/11

E

F

10/11

45

13/15

6

déb.fin

6/23

15

23

15/25

23

30

6/23

C

+

+

+ +

+

+

+

-

-

-

--

-

C

--

+

+

++

+

+

+

+

+-

En modifiant d’abord FQ3 :

Nouveau flot optimal : 57 unités.Il vaut mieux améliorer d’abord A1B puis FQ3.

Exercice 4   : Recherche d’une solution initiale par la méthode de Balas-Hammer :

180 10 Cette solution coûte 25130 21 21 42 28 14110 260 Calculons les regrets : -7 7 63 7 35

160 180 21 0 49 42 210 7 28 -28

Comme un des regrets est négatif, la solution n’est pas optimale.Nouvelle répartition :

180 10 Prenons x= 110. 21 21 42 35 14x 110-x 260 La nouvelle solution coûte : 28 14 63 7 28

160-x 180+x 24360 21 0 49 49 21Calculons les regrets : 0 7 28 -35

Cette solution est optimale. Elle n’est pas unique (il y a un regret nul).

Bilan : les deux solutions optimales sont : 180 10 190

110 260 110 26050 290 50 180 110

Pour un coût total de 24360.

Q1

Q2

Q3

A1

A2

87/8

B

11

8

A3

15

8/11

8

A4

15D

6

11/23

23

23

11

E

F

11

39/45

9/15

18

déb.fin

4/23

15

23

15/25

9/23

30

18/23

+

+

+

-