Recherche Opérationnelle

Programmation dynamique

Énoncé

On considère un jeu composé de quatre étapes où l'on passe à chaque fois une épreuve :

• A l'étape 1, on passe l'épreuve A.
• A l'étape 2, on passe une épreuve parmi B ou C.
• A l'étape 3, on passe une épreuve parmi D, E, F.
• A l'étape 4, on passe une épreuve parmi G, H.

Si à une certaine étape on réalise l'épreuve X, on a une certaine chance $P\left(Y/X\right)$ de gagner et de se voir attribuer à l'étape suivante l'épreuve Y. L'évènement correspondant à la victoire est noté I. On connait les probabilités dictant le jeu :

• $P(B/A)=\frac{1}{3},P(C/A)=\frac{1}{2}$
• $P\left(D/B\right)=\frac{1}{5},P\left(E/B\right)=\frac{2}{5},P\left(E/C\right)=\frac{1}{4},P\left(F/B\right)=\frac{1}{5},P(F/C)=\frac{1}{3}$
• $P(G/D)=\frac{1}{2},P\left(G/E\right)=\frac{1}{5},P\left(G/F\right)=\frac{1}{2},P\left(H/E\right)=\frac{3}{5},P\left(H/F\right)=\frac{1}{3}$
• $P\left(I/G\right)=\frac{3}{5},P\left(I/H\right)=\frac{2}{3}$

1. Modéliser le problème à l'aide d'un graphe dont les sommets sont les évènements A, B, C, D, E, F, G, H, I.
2. Déterminer la suite menant à la victoire qui a la plus grande probabilité de se produire.

Solution

1. Si pour deux évènements X, Y, la probabilité $P\left(Y/X\right)$ est non nulle, on trace un arc de X à Y de valuation $P\left(Y/X\right)$(en fait garder les arcs de valuation nulle ne change rien au problème, mais surchage le graphe). Le problème revient alors à chercher un chemin de A à I de probabilité optimale. On ne peut toutefois pas appliquer les algorithmes de cheminement optimal vus en cours, puisque la probabilité du chemin n'est ici pas définie comme la somme mais comme le produit des probabilités conditionnelles.
2. En notant $f\left(X\right)$ la plus grande probabilité d'un chemin de A à X et en appliquant la formule d'optimisation séquentielle, on trouve :

   $f\left(B\right)=\frac{1}{3},f\left(C\right)=\frac{1}{2},f\left(D\right)=\frac{1}{15},f\left(E\right)=\frac{2}{15},f\left(F\right)=\frac{1}{6},f\left(G\right)=\frac{1}{12},f\left(H\right)=\frac{2}{25}$ et enfin $f\left(I\right)=\frac{4}{75}$ obtenu pour la suite d'épreuves A, B, E, H, I.

Graphe des Évènements A A B B A->B 1/3 C C A->C 1/2 D D B->D 1/5 E E B->E 2/5 F F B->F 1/5 C->E 1/4 C->F 1/3 G G D->G 1/2 E->G 1/5 H H E->H 3/5 F->G 1/2 F->H 1/3 I I G->I 3/5 H->I 2/3

Cheminement optimal dans les graphes

Exercice 1 : Algorithme de Ford

Dans ce graphe sans circuit, trouver le plus court chemin pour aller de A à J.

Graphe des Évènements A A B B A->B 2 C C A->C 1 F F B->F -1 D D C->D 2 C->F 1 D->F 1 E E G G E->G -4 F->E 3 H H F->H 2 I I F->I -3 G->H 5 J J G->J 2 H->J 1 I->H 3

Exercice 2 : Algorithme Dijkstra

Dans ce graphe à valuation positive, trouver le plus court chemin pour aller de I à VII.

I I II II I->II 2 IV IV I->IV 1 III III II->III 5 VI VI III->VI 1 IV->III 1 IV->VI 7 V V V->II 2 VII VII V->VII 1 VI->V 0 VI->VII 2

Exercice 3 : Algorithme de Bellman-Ford

x1 x1 x2 x2 x1->x2 2 x3 x3 x1->x3 8 x2->x3 5 x4 x4 x2->x4 5 x5 x5 x3->x5 -2 x4->x5 -1 x6 x6 x4->x6 2 x5->x2 -3 x7 x7 x5->x7 5 x6->x7 -1 x8 x8 x6->x8 1 x7->x4 3 x7->x8 1

Dans le graphe G précédent, on considère les cycles ${\mu }_1=(x_1,x_2,x_3),{\mu }_2=(x_1,x_3,x_5),{\mu }_3=(x_2,x_4,x_5),{\mu }_4=(x_4,x_6,x_7),{\mu }_5=(x_4,x_5,x_7),{\mu }_6=(x_6,x_8,x_7)$. On notera respectivement $m,n,p$ le nombre d'arêtes, de sommets et de composantes connexes de G. Pour tout $1\le i\le 6$, $1\le j\le m$ on note ${\mu }_i^j$ la valeur 0, -1, 1 indiquant l'absence ou le sens de parcours de l'arête $j$ dans le cycle ${\mu }_i$.

1. Parmi les ${\mu }_i$, quels sont ceux qui sont des circuits ?
2. Calculer la dimension d'une base de cycle $\nu \left(G\right)$(on rappelle qu'il vaut $m-n+p$).
3. Montrer que les ${\mu }_i$ forment une base de cycle.
4. En déduire que tout circuit $\mu$ de G s'écrit $\sum _{i=2}^5{a}_i{\mu }_i$ avec $a_i\ge 0$.
5. Conclure que l'on peut appliquer l'algorithme de Bellman-Ford.
6. Quel est le chemin de côut minimal de $x_1$ à $x_8$ ?

Exercice 4 : Algorithme de Floyd-Warshall

Déterminer les coût minimaux des chemins entre tout couple de sommets :

a a b b a->b 1 c c a->c 2 d d a->d 3 e e b->e 1 c->b -2 f f c->f -1 d->f 2 e->c 1 e->f -1

Solutions

Exercice 1

Les chemins optimaux sont A, B, F, E, G, J et A, B, F, I, H, J avec une valeur de 2.

Exercice 2

Le tableau des valeurs provisoires est :

I	II	III	IV	V	VI	VII
0	2	∞	1	∞	∞	∞
0	2	2	1	∞	8	∞
0	2	2	1	∞	8	∞
0	2	2	1	∞	3	∞
0	2	2	1	3	3	5
0	2	2	1	3	3	4

Le chemin optimal est donc I, IV, III, VI, V, VII avec un coût de 4.

Exercice 3

1. Tous sont des circuits, sauf ${\mu }_1$ et ${\mu }_6$ qui possèdent un arc parcouru dans le sens inverse. Pour les autres, on a toujours ${\mu }_i^j$ valant 0 ou 1.
2. $\nu \left(G\right)=13-8+1=6$
3. D'après la question 2, il suffit de prouver que les ${\mu }_i$ forment une famille libre, i.e qu'une combinaison linéaire nulle implique des coefficients tous nuls. Or cela est évident car chacun possède une arête qui n'appartient à aucun des autres cycles.
4. D'après la question 3, tout circuit $\mu$ est un cycle dont peut s'écrire $\sum _{i=1}^6{a}_i{\mu }_i$. Mais on peut retirer ${\mu }_1$ et ${\mu }_6$ où sinon un des arcs serait parcouru dans le sens inverse. Soit alors $\mu =\sum _{i=2}^5{a}_i{\mu }_i$. Supposons qu'il existe $i$ tel que $a_i<0$. Soit alors $j$ une arête parcouru uniquement par ${\mu }_i$(une telle arête existe toujours comme on l'a remarqué à la question 3) . On a alors ${\mu }^j=a_i{\mu }_i^j=a_i<0$ ce qui contredit le fait que $\mu$ soit un circuit.
5. On vérifie facilement que les cicuits ${\mu }_i$ pour $2\le i\le 5$ ont tous un coût positif. Tout circuit de G s'écrit comme combinaison linéaire à coefficients positifs de ces circuits élémentaires, donc son coût n'est pas strictement négatif.
6. L'algorithme de Floyd-Warshall donne :

   $x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$x_8$
   0	1	8	∞	∞	∞	∞	∞
   0	1	6	6	4	∞	∞	∞
   0	1	6	6	4	8	9	∞
   0	1	6	6	4	8	7	8
   0	1	6	6	4	8	7	8

   On arrête l'algorithme lorsque l'on tombe sur un état stationnaire. On trouve pour chemin optimal $x_1,x_2,x_4,x_6,x_7,x_8$ de coût 8.

Exercice 4

Les nombres séparés par des virgules correspondent aux différentes valeurs prises au cours de l'algorithme.

/	a	b	c	d	e	f
a	0	1, 0	2	3	∞, 2, 1	∞, 1, 0
b	∞	0	∞, 2	∞	1	∞, 0
c	∞	-2	0	∞	∞, -1	-1, -2
d	∞	∞	∞	0	∞	2
e	∞	∞, -1	1	∞	0	-1, 0
f	∞	∞	∞	∞	∞	0

Ordonnancement

Exercice 1

1. Tracer le graphe de Pert correspondant à l'ordonnancement de tâches suivant :

   Tâche	Durée	Tâches antérieures
   a	1	/
   b	2	/
   c	5	/
   d	3	a, b
   e	1	b, c
   f	5	d
   g	1	e
   h	1	g, d
   i	2	h, f

2. Indiquer les dates au plus tôt et au plus tard.
3. Indiquer le ou les chemins critiques.
4. Idem avec la méthode Potentiel.

Exercice 2

On doit usiner une suite de pièce $p_i$ sur deux machines A puis B, avec les durées précisées dans le tableau suivant :

	A	B
p1	5	7
p2	4	8
p3	6	3
p4	2	4
p5	7	1
p6	4	3
p7	9	7

1. Donner une borne inférieure du temps nécessaire.
2. Donner l'ordonnancement optimal ainsi que la durée de l'usinage correspondant.

Solutions

Exercice 1

Le chemin critique est en rouge, les valeurs entre parenthèses sont les dates au plus tôt et au plus tard.

Graphe de Pert D Debut(0, 0) 1 (2, 2) D->1 a 2 (2, 2) D->2 b 3 (5, 6) D->3 c 4 (4, 4) 1->4 d 2->1 0 2->3 0 5 (6, 7) 3->5 e 6 (7, 8) 4->6 0 7 (9, 9) 4->7 f 5->6 g 6->7 h F Fin(11, 11) 7->F i

Graphe Potentiel D Début(0, 0) a a(0, 1) D->a 0 b b(0, 0) D->b 0 c c(0, 1) D->c 0 d d(2, 2) a->d 1 b->d 2 e e(5, 6) b->e 2 c->e 5 f f(4, 4) d->f 2 h h(7, 8) d->h 2 g g(6, 7) e->g 1 i i(9, 9) f->i 5 g->h 1 h->i 1 F Fin(11, 11) i->F 2

Exercice 2

1. Une borne inférieure est $2+(7+8+3+4+1+3+7)=35$
2. p4, p2, p1, p7, p3, p6, p5 avec une durée de 38.

Flots dans les graphes

Énoncé

1. Appliquer l'algorithme de Ford Fulkerson au graphe ci-dessous (les valeurs sur les arcs correspondent à flot / capacité) pour trouver un flot maximal entre s et t.
2. En déduire une coupe de capacité minimale.

Un graphe de flot s s A A s->A 8/10 C C s->C 3/5 B B A->B 7/15 D D A->D 1/5 B->s 5/10 B->D 1/5 E E B->E 6/15 C->B 5/5 G G D->G 2/5 F F E->F 4/10 E->G 2/5 F->C 2/5 H H F->H 2/5 G->H 5/10 t t H->t 7/10 t->s 6/∞ t->G 1/5

Solution

1. On trouve un flot de 10.
2. Une coupe de capacité minimale après application de l'algorithme est donnée par $(X\backslash \left\{t\right\},\left\{t\right\})$et on vérifie que sa capacité est de 10.

• • Accueil
  • Actualité
  • A propos
  • Infos Logo
  • Infos techniques
  • Proposer article
  • Plan du site
  • Ouvrages
  • Mailing List
  • Imprimer
• • Algèbre
  • Analyse
  • Ensembles
  • Geometrie
  • Graphes
  • Logique
  • Probabilités
  • Recherche Opérationnelle
  • Statistiques

Cette page respecte les recommandations du W3C. Son contenu est sous licence Creative Commons.