RCP101 : Recherche opérationnelle et aide à la décision

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 illimité. Si capacité limitée : les clients supplémentaires sont perdus ou rejoignent une autre file d’attente. Le nombre de clients dans le système est différent du nombre de clients dans la file d’attente
Discipline de service : règle d’ordonnancement des clients au (…)

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 des trois ateliers sont :
– 450 heures par mois pour l’atelier 1.
– 350 heures par mois pour l’atelier 2.
– 200 heures par mois pour l’atelier 3.
Bénéfices unitaires dégagés par l’entreprise sont : :
– 4000 francs pour les voitures de type (…)

Affecter 4 personnes à 4 taches comment faire ?
Soit 4 personnes A, B,C,D
et 4 taches a,b,c,d
La méthode hongroise
tableau représentant les coefficients de préférence des différentes personnes : A B C D E a 9 6 7 3 4 b 2 1 9 1 8 c 4 3 2 2 7 d 9 1 8 8 3 e 1 7 8 9 5
la personne ’a’ veut vraiment aller sur le poste A éventuellement C voir B mais ne veut pas aller en E ou D, etc...
la méthode hongroise est que c’est un algorithme de minimisation donc la première étape est (…)

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 maximale la quantité la plus élevée possible. Ce qui sature une ligne ou une colonne. Reprendre le processus jusqu’à ce que toutes les rangées soient saturées.
Algorithme Dl : différence entre le coût mini et celui immédiatement supérieur sur une (…)

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 complet On fait passer un flot au juger Améliorer le flot jusqu’à ce qu’on ait un flot complet- Flot qui sature suffisamment de relations pour que tout chemin entre source, s et la sortie t comporte au moins un arc saturé. Procédure de marquage Marquer (…)

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 graphe valué par les durées des tâches détermine la date au plus tôt de réalisation du projet. Ce plus long chemin est appelé chemin critique
METHODE PERT (1956- Program evaluation and review technique) Graphe potentiels (…)

Graph Symétrique
– Si pour toute paire de sommets (x,y) 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) U (y,x) U
Graph Anti-Symétrique
– Si pour toute paire de sommets (x,y) C X il n’existe pas autant d’arcs de la forme (x,y) que de la forme (y,x) Le graphe G est dit anti-symétrique
– Cas du 1-graphe G=(X,U) il est anti-symétrique ssi :
(x,y) U

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
Les cycles se représentent aussi sous la forme de matrice. Ici nous avons le cycle µ1=1,2=(1,-1,0,0,0,0,0) Dans cette matrice « 1 » représente l’arc 1 parcouru dans le bon sens, « -1 » représente l’arc 2 parcourus dans le sens inverse. Les autres arcs sont à 0 car ils ne font pas partie du cycle.
Un cycle est une séquence d’arcs Il suffit de suivre les arcs avec un stylo (…)

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 de haut en bas, car ce sont des sens naturels.
On appelle un graphe G(X,U) avec X= ensemble de sommets et U = ensembles d’arcs.
Graphe non orienté Orientation des arcs : pas d ’importance (plan de circulation sans sens interdits) Extrémité initiale et terminale : aucun rôle (…)

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 = 1 1 + 1 = 1
pour les produits : le * correspond au "ET" 0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1 le 0 = Faux le 1 = Vrai
Théorie des graphes : matrice d’un graphe
Matrice d’incidence ou matrice d’incidence sommet-arc ou sommet-arête Si on a un graphe orienté G=(X, (…)