I/ Définition Une file d’attente est caractérisée par : – Un flot d’arrivées – Un mécanisme de service – Une file d’attente – Une discipline de service Capacité de la file d’attente: – nombre de places possibles : limité ou…

Méthode graphique Le problème: Entreprise fabrique des voitures de type A et B. Il y a trois ateliers: – Atelier 1 fabrique les moteurs. – Atelier 2 fabrique les carrosseries. – Atelier 3 effectue les assemblages. Les capacités de travail…

Méthode On calcule pour chaque rangée, ligne ou colonne, la différence entre le coût le plus petit avec celui qui lui est immédiatement supérieur. Affecter à la relation de coût le plus petit correspondant à la rangée présentant la différence…

Calcul du flot maximum dans un graph reliant le puits (t) à la source(s). Il faut respecter la loi de kirshoff: l’ensemble flux entrant sur un nœud=l’ensemble des flux sortant du même nœud Algorithme de Ford -Fulkerson Recherche du flot…

METHODE MPM (méthode des potentiels Metra- 1958) Graphe potentiel tâche Graphe orienté sans circuit de valeur positive: sommets: tâches arcs: contraintes d’antériorité entre deux tâches valués avec la durée de la tâche La recherche du plus long chemin sur le…

Graph Symétrique – Si pour toute paire de sommets (x,y) $\in$ X il existe autant d’arcs de la forme (x,y) que de la forme (y,x) – Cas du 1-Graphe G=(X,U), il est symétrique ssi : (x,y) $\in$ U (y,x) $\in$…

Définition : Dans un graphe G=(X,U) un cycle est une séquence d ’arcs :m=(u1,u2,u3,…,uq) telle que : Tout arc uk (1

La théorie des graphes : Un graphe est composé de sommets (on parle aussi de noeuds) et d’arcs qui relient les sommets entre eux. La forme n’a pas d’importance mais en général on le lit de gauche à droite, parfois…

Rappels sur le calcul matriciel et booléen Addition de matrices [0150]+ [1203] = [1353] [1210] [0024] [1234] Multiplication de matrices Calcul booléen le + correspond au « OU » 0 + 0 = 0 1 + 0 = 1 0 + 1…