Recherche Opérationnelle pour le Génie Industriel
Master Génie Industriel
Emmanuel Caillaud 2014-2015
Plan du Cours
• Introduction à la recherche opérationnelle • Programmation linéaire • Théorie des graphes
• Nous ne verrons pas : • Simulation • Phénomènes aléatoires
• files d'attente • Fiabilité • Simulation
Bibliographie
• V. Cohen, "La Recherche Opérationnelle", Que sais-je ?, PUF, 1995.
• R. Faure, B. Lemaire, C. Picouleau, "Précis de Recherche Opérationnelle", Dunod, 2000.
• Roseaux, "Exercice et problèmes résolus de Recherche Opérationnelle", Dunod, 2000.
• I. Rasovka, « Recherche Opérationnelle », support de cours, 2014
• J. Lamothe et L. Dupont « Recherche opérationelle », supports de cours, 2014
Objectifs du cours • Principaux objectifs du cours :
• connaître l'existence de quelques uns des modèles de référence (les plus importants),
• comprendre les modèles en connaissant leurs caractéristiques et leurs limites,
• savoir appliquer ces modèles à des problèmes classiques.
• Remarque : • La mise en œuvre des modèles "à la main" n'est pas un
objectif du cours mais un moyen de compréhension des modèles et de leur application sur des exemples numériques.
Introduction à la Recherche Opérationnelle
RO ? • Recherche opérationnelle :
• ensemble d'outils et de méthodes pour formaliser et résoudre des problèmes classiques.
• Outils et méthodes : • théorie des graphes • optimisation par programmation linéaire • Heuristique et métaheuristiques • modélisation des phénomènes aléatoires
Domaines d'application • Aide à la décision • Ordonnancement de projet, de job-shop • Maintenance • Problèmes de transport • …
Exemples de problèmes • Où installer 4 usines de production parmi 20 sites
d'implantation possibles ? • Combien faut-il de personnes au service commercial
pour qu'une personne ait moins de 5 % de chances de devoir attendre plus de 15 minutes ?
• Quel est l’emploi du temps « optimal » pour les étudiants de Master ?
Historique • Terme de "Operational Research" par R. Watson-
Watt (1892-1972), spécialiste de radar. • Pb. : efficacité globale du système de surveillance
Radar et d'intervention aérienne (1937, Blackett, Grande-Bretagne). • Où positionner les radars ? • Comment transmettre les informations ? • Comment être sûr du matériel ? • Comment assurer les différentes tâches ?
Historique (2) • Équipes militaires de recherche opérationnelle ont
été créées dans les différents pays. • Après 1945 : application au secteur civil (économie,
administration, production,…). • Exemples en sidérurgie :
• Succession des qualités d'acier au laminage à froid de manière à favoriser l'expédition directe tout en minimisant les coûts liés aux contraintes techniques
• Simulation du cadencement d'un train de laminage
Historique (3) • Années 50
• Développement rapide malgré les difficultés informatiques. Enseignement de la RO, création de sociétés savantes ORSA, AFCET, EJOR.
• Apparition d'outils de la RO : • PROGRAMMATION DYNAMIQUE (BELLMAN 1954) • FLOTS ET AFFECTATIONS (KüHN 1955, FORD/
FULKERSON 1956) • MÉTHODE SIMPLEXE (DANTZIG à partir de 1947) • "BRANCH AND BOUND" ou PSE (LITTLE 1963) • METHODES A CHEMINS CRITIQUES (PERT 1958, ROY
1960)
Historique (4) • 70-80 : stagnation de la RO
• Depuis 80 : "reprise" • travaux de groupe (gestion de projet) • apparition de nouveaux outils • prise en compte d'objectifs multiples • intégration des facteurs humains • temps réel • aide à la décision
Caractéristiques de la RO • Objectif :
• fournir des éléments de réflexion pour une prise de décision concernant un problème concret.
• Étapes d'une démarche de RO : • identification du problème • modélisation du problème (c'est le plus difficile !) • résolution par des méthodes "classiques" • validation des résultats et interprétation
Modélisation • Délicate car lien entre un problème concret et sa
mise en forme abstraite de manière à permettre sa résolution en veillant à : • être fidèle à la réalité • permettre une résolution efficace • présenter les solutions applicables au problème concret
Modélisation (2) • La forme de modélisation la plus fréquente :
modélisation mathématique • par des équations et des inéquations liant entre eux les
paramètres connus et inconnus de manière à constituer d'une part des contraintes à respecter et d'autres part des mesures de satisfaction à optimiser (maximiser ou minimiser) appelés objectifs ou fonctions objectif ou critères.
• Autres formes de modélisation : • les graphes, les réseaux de Petri, le grafcet, les réseaux de
file d'attente…
Fonctions d'un modèle • Expliquer
• Mettre en évidence les causes
• Prévoir • Passé (extrapoler les résultats d'un échantillon) • Futur proche (extrapolation ou simulation) • Moyen terme (tendances,intervalles de confiance)
• Agir • Variables d'entrée • Paramètres du modèle
Hypothèses du modèle • Indépendance statistique
• Si indépendant : produit des statiques • Sinon fonction de leur dépendance jusqu'à la plus petite
valeur des 2 (> au produit) • Attention à ne pas minorer les risques !
• Stationnarité (indépendance du temps) • Linéarité (proportions) ou convexité
Types de modèles • Graphes • Matrices • Suites • Dérivées de fonctions • Séries et calcul intégral • Variable aléatoire • Chaîne de Markov
Méthodes de résolution • Méthodes analytiques classiques • Algorithmes recherchant des solutions numériques
par des procédures déterministes • Expériences numériques : simulation ou algorithmes
probabilistes (Monte Carlo, Tabou, recuit simulé)
Algorithmes • Succession de pas (dont certains sont réalisés en
boucles) jusqu'à ce qu'un critère d'arrêt soit satisfait. • Algorithmes déterministes
• Analyse numérique : systèmes linéaires, extrema de fonctions
• Optimisation combinatoire : plus courts chemins, flot maximum
Programmation linéaire
Historique • La programmation linéaire fut développée au cours
de la Seconde Guerre mondiale. • L’objectif était d’allouer plus intelligemment les
ressources de l’armée. • Le terme « programmation » est employé avec le
sens de « plan ». • La terminologie est due à G.B. DANTZIG, inventeur
de l’algorithme du Simplexe en 1947
Domaines d’application • La PL peut résoudre un grand nombre de
problèmes : • modèle de transport, • allocation de ressources, • tarifications, …
Modèle PL • Variable de décisions
• Des variables mathématiques représentant des décisions
• Fonction Objectif (fonction à optimiser) • Une équation linéaire qui quantifie un objectif • L’objectif le plus fréquent des entreprises est de maximiser
les profits. • Pour un département, on essaie souvent de minimiser les
coûts.
• Contraintes • Des équations ou inéquations linéaires qui restreignent les
variables de décisions.
Formulation générale Max/min z = c1x1 + c2x2 + ... + cnxn Avec :
a11x1 + a12x2 + ... + a1nxn (≤, =, ≥) b1 a21x1 + a22x2 + ... + a2nxn (≤, =, ≥) b2 : am1x1 + am2x2 + ... + amnxn (≤, =, ≥) bm
xj = variables de décision bi = valeur de la contrainte à satisfaire cj = coefficients de la fonction objectif aij = coefficients des contraintes
Hypothèses • La linéarité des contraintes • Linéarité de la fonction objectif. • L’additivité des effets. • La proportionnalité des gains/coûts • Proportionnalité de la consommation des ressources. • La divisibilité des variables. • La détermination des données.
• Ces hypothèses devront être validées pour chaque cas d’application ! Cette analyse peut mener à choisir un modèle différent (non linéaire, stochastique, ..).
Un exemple • Une usine réalise deux produits : • A nécessite 2 kg de matière première et 4 heures de
fabrication et donne un bénéfice de 30 €. • B nécessite 4 kg de matière première et 2 heures de
fabrication et donne un bénéfice de 10 € . • On dispose de 100 kg de matière première et de
280 h de travail (2 opérateurs x 35h x 4 semaines). • Quelle production de A et de B doit on réaliser pour
obtenir un bénéfice maximal ?
Un exemple • Variable de décision:
• X1 = Production de produit A (X1 ≥ 0) • X2 = Production de produit B (X2 ≥ 0)
• Fonction objectif:
• Z = 30 X1 + 10 X2
• Contraintes
• Produit A utilise 2 kg de matière et 4h de production.
• Produit B utilise 4 kg de matière et 2 heures de production.
• La matière première est limitée à 100 kg.
• 2 X1 + 4 X2 ≤ 100
• Le temps de production est limité à 280 h.
• 4 X1 + 2 X2 ≤ 280
Résolution graphique (1) • Déterminer les variables du problème : formuler le
problème en termes de fonction objectif et de contraintes linéaires.
• Faire un graphique avec une variable de décision sur chaque axe et tracer les droites des contraintes : ces contraintes déterminent la région de solutions admissibles (chacune des contraintes est satisfaite : toutes les solutions sont possibles).
Résolution graphique (2) • Déterminer la pente de la fonction objectif et
l’indiquer dans la zone de faisabilité. • Déplacer la fonction objectif parallèlement à elle-
même jusqu'à ce qu’elle rencontre une limite de la zone de faisabilité.
• Lire directement les valeurs des variables qui constituent la solution du problème sur les axes respectifs.
• La solution optimale sera toujours située à l’intersection de deux droites de contraintes dans la région de faisabilité.
X2
X1
Résolution graphique
X1 ≥ 0 et X2 ≥ 0
25
50
100
125
75
150
25 50 75 100 125 150 175 200 225
X2
X1
Résolution graphique
25
50
100
125
75
150
25 50 75 100 125 150 175 200 225
4 X1 + 2 X2 ≤ 280
X2
X1
Résolution graphique
X1 ≥ 0 et X2 ≥ 0
25
50
100
125
75
150
25 50 75 100 125 150 175 200 225
2 X1 + 4 X2 ≤ 100
X2
X1
Résolution graphique
X1 ≥ 0 et X2 ≥ 0
25
50
100
125
75
150
25 50 75 100 125 150 175 200 225
X2
X1
Résolution graphique
X1 = 50 et X2 = 0
25
50
100
125
75
150
25 50 75 100 125 150 175 200 225
La solution optimale Produit A = 50unités Produit B = 0 unités Profit = 1500 €
Coût marginal
Rôle des points extrêmes… Si un programme linéaire a une solution optimale, alors au moins un point extrême est optimal.
Plusieurs solutions optimales
• Si plusieurs solutions optimales existent alors la fonction objectif doit être parallèle à au moins une des contraintes.
Méthode du simplexe • Quand le nombre de variables est égal à 2, la
résolution graphique est facile • Quand le nombre de variables est égal à 3, il faut
faire une représentation 3D, c’est pas gagné ! • Quand le nombre de variables est > 3, il faut faire
autrement ! Utiliser par exemple la méthode du simplexe
Méthode du simplexe • Méthode du simplexe
• méthode itérative qui consiste à partir d'une solution de base (réalisable mais pas optimale), à l'améliorer à chaque itération afin d'obtenir la solution optimale.
• basée sur la construction de tableaux dont les valeurs seront calculées manuellement
• Lorsque le nombre de variables devient trop important, il est préférable d'utiliser un logiciel qui effectue les différentes itérations et détermine la solution optimale.
L’algorithme du simplexe (Dantzig, 1947)
• Développé juste après la Seconde Guerre mondiale • Utilisé pour planifier le pont aérien de Berlin en
1948. • Principes de l’algorithme :
• Démarrer d’un point extrême • Se déplacer (pivot) vers un point extrême voisin améliorant la
solution • Répéter jusqu’à l’obtention de la solution optimale
Algorithme du simplexe • Modéliser le problème sous la forme d’une fonction
objectif et de contraintes (programme canonique) • Transformer le programme canonique en
programme standard en introduisant des variables d’écart et artificielles pour transformer les inéquations en équations
Tableau 1
Test d’optimalité • La solution courante est optimale si tous les coûts Ci
sont non négatifs. • Dans le cas contraire (si au moins un coût est
négatif), passer à l’étape suivante.
• Détermination de la colonne-pivot et de la ligne-pivot :
• Colonne-pivot : correspond à la colonne contenant le plus petit coût négatif.
• Ligne-pivot : correspond à la ligne qui contient le plus petit qi non négatif.
Nouveau tableau • Le nouveau tableau s’obtient comme suit : • Ligne-pivot : diviser tous les éléments de la ligne-
pivot par l’élément pivot ars. • Colonne-pivot : remplacer l’élément pivot par 1 et
les autres éléments de la colonne-pivot par 0. • Pour toutes les autres lignes et colonnes :
• u : élément quelconque sur la ligne-pivot • w : élément quelconque sur la colonne-pivot • ars : élément-pivot
Itération • On vérifie à nouveau si on est à l’optimum sinon
nouveau tableau.
Exemple
0,075
4000104060002030200400max
≥≥
≤
≤+
≤+
+=
yxx
yxyx
yxz
Forme canonique
Forme canonique : transformation des inéquations en équations par ajout de variables d ’écart
0,0,0,0,075
4000104060002030200400max
321
3
2
1
≥≥≥≥≥
=+
=++
=++
+=
eeeyxex
eyxeyx
yxz
e1 : heures inoccupées sur la machine 1 e2 : heures inoccupées sur la machine 2 e3 : produits p1 qu ’on aurait pu vendre mais qu ’on a pas fabriqués
Résolution graphique
x y e1 e2 e330 20 1 0 0 600040 10 0 1 0 40001 0 0 0 1 75
400 200 0 0 0 0
Matrice initiale : solution point 0
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 1
x y e1 e2 e330 20 1 0 0 6000 x ≤ 6000/30 = 20040 10 0 1 0 40001 0 0 0 1 75
400 200 0 0 0 0
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 1
x y e1 e2 e330 20 1 0 0 6000 20040 10 0 1 0 4000 x ≤ 4000/40 = 1001 0 0 0 1 75
400 200 0 0 0 0
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 1
x y e1 e2 e330 20 1 0 0 6000 20040 10 0 1 0 4000 1001 0 0 0 1 75 x ≤ 75/1 = 75
400 200 0 0 0 0
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 1
x y e1 e2 e330 20 1 0 0 600040 10 0 1 0 40001 0 0 0 1 75400 200 0 0 0 0
x y e1 e2 e30 20 1 0 -30 37500 10 0 1 -40 10001 0 0 0 1 750 200 0 0 -400 -30000
Solution : point D x = 75 e1 = 3750 e2 = 1050 y = 0 e3 = 0
Itération 1
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 2 x y e1 e2 e30 20 1 0 -30 3750 y ≤ 3750/200 10 0 1 -40 10001 0 0 0 1 750 200 0 0 -400 -30000
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 2 x y e1 e2 e30 20 1 0 -30 37500 10 0 1 -40 1000 y ≤ 1000/101 0 0 0 1 750 200 0 0 -400 -30000
0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 2: 40x+10y=4000
Machine 1 : 30x+20y=6000
A
B
D O
Dl
Vente maximale: x =75
C
75
Itération 2 x y e1 e2 e30 20 1 0 -30 3750 375/20 10 0 1 -40 1000 1001 0 0 0 1 75 0y ≤ 750 200 0 0 -400 -30000
x y e1 e2 e30 20 1 0 -30 3750 187,50 10 0 1 -40 1000 1001 0 0 0 1 75 + ∞0 200 0 0 -400 -30000
Solution : point C x = 75 y = 100 e1 = 1750 e2 = 0 e3 = 0
Itération 2
x y e1 e2 e30 0 1 -2 50 17500 1 0 1/10 -4 1001 0 0 0 1 750 0 0 -20 400 -50000
O 0
50
100
150
200
250
300
350
400
y
0 50 100 150 200 x
Machine 1 : 30x+20y=6000
A
B
D
Dl
Vente maximale: x =75
C
75
Itération 3 x y e1 e2 e30 0 1 -2 50 1750 50 e3 ≤ 1750 (e3≤ 35)0 1 0 1/10 -4 100 -4 e3 ≤ 1001 0 0 0 1 75 e3 ≤ 750 0 0 -20 400 -50000
Solution : point B x = 35 y = 240 e3 = 35 e1 = 0 e2 = 0
Itération 3 x y e1 e2 e30 0 1 -2 50 1750 350 1 0 1/10 -4 100 + ∞1 0 0 0 1 75 750 0 0 -20 400 -50000
x y e1 e2 e30 0 2/100 -4/100 1 350 1 8/100 -6/100 0 2401 0 -2/100 4/100 0 400 0 -8 -4 0 -64000
r
2 4 5 7 1 0 0 42
1 1 2 2 0 1 0 17
1 2 3 3 0 0 1 24
7 9 18 17 0 0 0 0
1. Choix de la colonne entrante r si tous les Cj ≤ 0 alors FIN optimum atteint sinon choisir une colonne r avec Cr>0 (ici : Cr = max Cj ) 2. Si tous les Air ≤ 0 alors FIN : solution non bornée Xr = + ∞
s
3. Sinon déterminer la ligne sortante s telle que Asr > 0 et Bs / Asr soit minimum ( Asr est
appelé le pivot )
42/5
17/2
24/3
r
2 4 5 7 1 0 0 42
1 1 2 2 0 1 0 17
1 2 3 3 0 0 1 24
7 9 18 17 0 0 0 0
r
s
4. Diviser la ligne s par le pivot 5. Eliminer des termes de la colonne r en dehors de la ligne s par combinaison linéaire
valeur de -z dans la solution faisable 5. Réitérer
1/3 2/3 0 2 1 0 -5/3 2
1/3 -1/3 0 0 0 1 -2/3 1
1/3 2/3 1 1 0 0 1/3 8
1 -3 0 -1 0 0 -6 -144
Exemple
Construction du 1er tableau • n variables = 6 • m équations = 4 • n-m = 2 variables qui doivent être nulles • On prend x1=0 et x2=0 (hors base) • D’où e1= 200; e2 = 60 ; e3 = 34 ; e4 = 14 (variables
de base)
Tableau initial • Les 4 lignes correspondent aux 4 contraintes. • La colonne coef Z à gauche correpond aux coefficients des
variables de base dans la fonction objectif. • La valeur en bas à droite corespond à la valeur de Z (somme
des produits des valeurs de base par leurs coef dans Z)
Choix de la variable entrante • On cherche le Maximum des Cj-zj si on veut
maximiser • On cherche le minimum des Cj-zj si on veut
minimiser
• Dans notre problème, on veut maximiser. • On fait donc entrer x2 dans la base
Choix de la variable sortante • On calcule bi/aik et on cherche le minimum >0 • 200/5 = 40 • 60/3 = 20 • 34/0 infini ça fait beaucoup qd on cherche le mini • 14/1 = 14 • E4 va sortir de la base (e4 va devenir =0)
Pivotage • La cellule à l’intersection entre la variable entrante
et la variable sortante est le pivot.
• On divise la ligne du pivot par le chiffre du pivot. • Pour l’exemple on divise par 1. • Dans la colonne pivot, toutes les valeurs sont à 0
sauf le pivot. • Pour les autres
Nouveau tableau
• On calcule, les bj, les zj, et Z.
Résolution par le simplex • Les inégalités représentent des plans (en 2D) ou
des hyperplans. • Un ensemble d’inégalités permet de construire un
espace réalisable borné que l’on appelle un polygone convexe (2D) ou polyèdre convexe
• Un rappel sur la convexité : • Soit a et b deux solutions réalisables d’un polyèdre convexe,
alors (a+b)/2 est aussi une solution de ce polyèdre
Bonne nouvelle ! • La propriété des points extrêmes nous dit que si un polyèdre
(P) contient une solution optimale, alors il existe une solution optimale qui est située sur un point extrême.
• La bonne nouvelle : on ne peut que considérer les points extrêmes :-)
• La mauvaise nouvelle : Le nombre de points extrêmes peut-être exponentiellement élevé par rapport au nombre de variables de décision.
• Le prix de consolation : la convexité garantit que les optimums locaux sont des optimaux globaux. • C'est-à-dire qu’un point extrême est optimal si tous ses voisins sont pires
que lui. • Mais attention aux plateaux…
Dualité • A tout problème de maximisation (ou minimisation),
on peut associer un problème de minimisation (ou maximisation) correspondant. En notant par PRIMAL le problème initial ; le problème correspondant s'appellera donc DUAL.
Primal / Dual
Primal : trouver X={X1, X2..Xn} Max C.X
A .X <= B Dual : Trouver Y={Y1, Y2..Ym} Min Y.B
Y.At >=C
PRIMAL DUAL
n variables , m contraintes m variables , n contraintes
Max C.X min Y.B
A X ≤ B Y ≥ 0
X ≥ 0 Y At ≥ c
Forme canonique de la dualité
Passage primal/dual
Primal (Dual) Dual (Primal)
Fonction à maximiser Fonction à minimiser
ième contrainte ≤ ième variable ≥ 0
ième contrainte ≥ ième variable ≤ 0
ième contrainte = ième variable <> 0
jème variable ≥ 0 jème contrainte ≥
jème variable ≤ 0 jème contrainte ≤
jème variable <> 0 jème contrainte =
Problèmes rencontrés en PL.
• La programmation linéaire est un outil de modélisation et de résolution très puissant.
• Par contre, dans certaines situations, on peut rencontrer certaines difficultés… • Solutions optimales multiples • Phénomène de dégénérescence et cyclage • Solution réalisable inexistante • Solution non bornée
Solutions optimales multiples
Solutions réalisables inexistantes
• Soit le programme linéaire suivant:
Max x0 = 4x1 + 3x2
Sujet à:3x1 + 4x2 ≤ 12 (2.11)x1 + x2 ≥ 4 (2.19)
4x1 + 2x2 ≤ 8 (2.13)x1 ≥ 0x2 ≥ 0.
Solutions réalisables inexistantes • Il n’existe pas de point qui
satisfasse toutes les contraintes simultanément.
84
Problème de PL non borné • Soit le programme linéaire suivant:
85
Max z = x1 + x2 (2.21)Sujet à:
−4x1 + x2 ≤ 2 (2.22)x1 + x2 ≥ 3 (2.23)x1 + 2x2 ≥ 4 (2.24)x1 − x2 ≤ 2 (2.25)
x1 ≥ 0x2 ≥ 0.
Problème de PL non borné
86
Pas de solution optimale
Autres algorithmes pour résoudre les PLs
• Il existes d’autres algorithmes pour résoudre des programmes linéaires, en particulier les méthodes de points intérieurs • En théorie ces méthodes converge dans un temps polynomial
( elles devrait donc bcp plus efficaces que le simplexe )
• En pratique elles fonctionnent mieux quand l’espace est plus «lisse» alors que le simplexe semble plus efficace quand les arrêtes sont plus prononcées.
L’analyse de sensibilité • Est-ce que la solution optimale est sensible aux
paramètres du problème ?
• Pourquoi se poser cette question ? • Les paramètres utilisés ne sont que des estimations • Dans un environnement dynamique, ceux-ci peuvent
changer régulièrement. • Une analyse de scénarios (what-if) peut permettre de
proposer des changements aux paramètres.
Analyse de sensibilité (objectif) Intervalle d’optimalité • La solution optimale demeurera inchangée tant
que: • Un coefficient de la fonction objectif demeure dans son
intervalle d’optimalité; • Rien d’autre ne change.
• La valeur de cette solution changera si: • Le coefficient qui a changé multiplie une variable dont la
valeur optimale est non nulle.
Prolongements de la programmation linéaire • Programmation en nombres entiers (dont la
programmation dynamique) • Programmation non-linéaire
Optimisation avec Excel
Logiciels commerciaux • Il existe de nombreux logiciels commerciaux pour
résoudre des problèmes linéaires ou plus généralement d’optimisation.
• Cplex, Lingo, … • Le solveur d’Excel permet de traiter les cas avec
peu de variables et de contraintes…
Optimisation avec Excel (Solver) • Excel intègre un outil qui permet la résolution de
certains problèmes d’optimisation comme programmation linéaire, problème de transport et autres.
• Cet outil n’est pas toujours installé dans l’installation standard
• Menu Outils à macros complémentaires … à cocher Solveur puis OK
• Aller dans Outils (menu Solveur …).
Exemple • Ouvrir une feuille de calcul et enregistrer les
contraintes et la fonction objectif • Aller dans outils / Solveur
Exemple • Aller dans outils / Solveur • Entrer la cellule de la fonction objectif • Entrer les cellules des variables • Entrer les variables • Choisir la méthode
Options • On peut alors
choisir des options
Théorie des Graphes
Pourquoi la théorie des graphes ?
• On aime bien raisonner à partir de dessins • Graphe = formes de dessins génériques qui représentent
des problèmes génériques
• Si on sait modéliser un problème sous forme de graphe, • On saura évaluer à quels types de problèmes génériques il
appartient • On saura évaluer si il est facilement résolvable • On saura identifier quels types d ’algorithmes peuvent aider
• Théorie des graphes = Ensemble des problèmes génériques représentables sous forme de graphe et de leur modes de résolution
Exemple
Qu ’est ce qu ’un graphe • Graphe G(X,U)
• X ensemble fini d ’éléments appelés sommets = {Agen, Auch,…}
• U ensemble de relations entre 2 sommets x et y notée (x,y) =>{Agen-Auch, Agen-Montauban, …} Exemple : représentation du réseau routier en Midi-Pyrénées
Albi
CastresToulouse
MontaubanAgen
Cahors
Tarbes
Auch
Terminologie
• Arc = arête orientée => graphe orienté • Arc ou arête valuée => graphe valué • Boucle = arc (x,x)
<=>55
5
• Arc et arête Si la relation est réversible ((x,y) ∈ U => (y,x) ∈ U), (x,y) = arête Sinon (x,y) = arc x = origine, y = extrémité
Prédécesseurs U-(x) = ens des sommets origines des arcs d ’extrémité xSuccesseurs U+(x) = ens des sommets extrémité des arcs d ’origine x
Exemple d ’un projet : Construction d ’une maison
A/ Faire les fondations + Sécher 15sB/ Monter les murs 3sC/ Poser le toit 4sD/ Monter la menuiserie 4sE/ poser l ’électricité 2sF/ platrer + séchage platres 5s
a b
c
d
e
f
g
h
i
jk
15
33
3
3
3
4
44
4
2
2
5
1
3
2
G/ Carreler, poser moquettes 3sH/ Tapisser et peindre 2sI/ Crépir 1sJ/ Aménager l ’extérieur 3sK/ Fini
Terminologie (2) • Chemin = suite ordonnée d ’arc telle que l ’extrémité de l ’un est
l ’origine du suivant. Ex : chemin ABDFK • Chemin hamiltonien = chemin passant une fois et une seule par
chaque sommet du graphe et contenant tous les sommets • Chemin simple = ne passe pas 2 fois par le même arc • Chemin élémentaire = ne passe pas 2 fois par le même sommet • Circuit = chemin se fermant sur lui même.
Ex : Toulouse, Albi, Castres, Toulouse • Longueur d ’un chemin (ou circuit) = somme du poids des arcs qui
le composent • chaîne (resp cycle) =Chemin (resp circuit) composé d ’arêtes • Graphe (fortement) connexe = graphe non orienté (orienté) tel que
pour tout couple de sommet (x,y) il existe une chaîne (chemin) allant de x à y
• Arbre = graphe non orienté connexe sans cycle • Arborescence d ’un graphe orienté = arbre ayant un sommet
« racine » tel qu ’il existe un chemin allant de la racine à tout autre sommet.
Représentation d ’un graphe a b c d
a 0 1 1 0b 0 0 1 1c 0 0 0 1d 1 0 0 0
a
b
c
d
a b c da 0 1 1 -1b -1 0 1 1c -1 -1 0 1d 1 -1 -1 0
Matrice d ’incidence
Matrice booléenne (successeurs)
Liste de précédentsPrécédents
a db ac a,bd b,c
Recherche faciles prédécesseursPas pour les graphes valués
Recherche difficile prédécesseurs ���Risque beaucoup de 0 (inutile)Valuation à la place des 1
Recherche des arcs difficilePeu de mémoire
Matrice d’adjacence
Problèmes de RO en théorie des graphes • Trouver le plus court chemin (temps, km) pour aller d ’une ville à une
autre • Trouver la plus courte tournée (chemin hamiltonien) passant par toutes
les villes • Trouver le réseau de fibre optique le plus court à poser en parallèle du
réseau routier pour alimenter toute la région = trouver un arbre de longueur minimale dans le graphe
• Trouver la date de début au plus tôt d ’une tâche = plus long chemin ente le nœud de début et le nœud représentant la tâche.
• Quel est l ’effet du retard sur une tâche sur le retard d ’un projet • Trouver la quantité maximale de matière pouvant circuler dans un
réseau : problème de flot max (à coût minimum) • Comment alimenter une série de points de consommation à partir de
points de production à coût de transport minimum. • De combien de camions a t ’on besoin pour réaliser toutes le tournées en
1 jour ? • Quelles antennes poser et où les poser pour avoir une couverture
maximale et répondre aux demandes de consommations locales • Qui va faire quelles tâches et dans quel ordre pour un projet ?
Chemins optimaux
Objectif • Dans un graphe orienté trouver :
• le plus court (ou le plus long) chemin allant d ’un sommet origine à un sommet final
• Les plus courts (plus long) chemins entre 1 sommet et l ’ensemble des autres
• Les plus courts (plus long) chemins entre tous les sommets.
• Circuit absorbant = circuit de longueur négative pour un plus court chemin ou de longueur positive pour un plus long chemin
• Circuit absorbant => pas de solution on peut faire le tour du circuit indéfiniment
ba
cd e
3
33
3
-73
Ex : pas de plus court chemin de a à b,c,d ou e
De nombreux algorithmes
Principe de calcul de plus court chemin
Tout sous chemin d’un chemin optimal est optimal
ab
c
d
e
f4
6
3
-4
4
1
4
24
a,b,d,c,e,f plus court chemin de a à f=> a,b,d,c,e plus court chemin de a à e
Le plus court chemin de a à f se construit à partir ���du plus court chemin de a à un précédent de f
Plus court chemin • Hypothèse : pas de circuit !
Notion de marquage λi= marque de Xi = plus court chemin CONNU de X0 vers Xi (sans considérer Xj)
X0
Xi
Xj
λi
λj
dj,i
λ*i= nouvelle marque de Xi en considérant Xj
λ*i= Min( λi, λj+ dj,i)
0 Principe : Amélioration successive des marques
λj= marque de Xj = plus court chemin CONNU de X0 vers Xj
La marque du sommet Xi est ajustée à partir de celle du sommet Xj
Algorithme de Bellman (1) : Classer les nœuds par niveau • On part d ’une représentation par liste des
précédents • Rang 1 les nœuds sans précédents
• Barrer les nœuds de rang 1 dans toutes les listes de précédents
• Rang 2 les nœuds dont tous les précédents sont barrés • Barrer les nœuds de rang 2 dans toutes les listes de
précédents
• Rang 3 ….
Algorithme de Bellman (graphe sans circuit) • 1/ Classer les sommets par niveau • 2/ mettre la marque 0 sur les sommets de rang1 • 3/ Ajuster la marque de tous les sommets
successeurs de sommets de rang1 • 4/ La marque des nœuds de rang 2 est définitive.
Ajuster la marque de tous les sommets successeurs de sommets de rang 2
• 5/ La marque des nœuds de rang 3 est définitive. Ajuster la marque de tous les sommets
successeurs de sommets de rang 3 • 6/ ...
Repérer le plus court chemin • Principe : lorsqu ’on fait évoluer la marque d ’un
sommet, on note la nom du sommet origine ayant justifié cette marque.
• A la fin de l ’algorithme, • On part du sommet final, on regarde le sommet ayant
justifié sa marque : c’est le sommet précédent du plus court chemin
• On remonte dans le graphe à partir du sommet précédent.
Exemple Bellman
A
B
C
D
E
F
2
6
2
3
1
9
2
Calcul des rangs Calcul des marquesABCDEF
ABCDEF
PERT Méthode CPM ou MPM
Outils pour la gestion de projet et l ’ordonnancement Le problème central de l ’ordonnancement
Le problème central de l’ordonnancement • Soient N tâches Ti nécessitant une durée di donnée et de
date de début ti à déterminer • 3 types de contraintes
• Contraintes dites potentielles : tj -ti ≥ ai,j (ai,j = constante) Ex : Ti de durée di se fini avant de commencer Tj => tj -ti ≥ di
• Contraintes liées aux ressources • Un moyen unique (homme ou machine) doit réaliser
2 tâches : quel ordre ? Contrainte disjonctive (tj - ti ≥ di) ou (ti - tj ≥ dj)
• Moyen a capacité multiple : contrainte cumulative • ∑ Moyen utilisé (i,t) ≤ Capacité (i,t)
Problème central = uniquement les contraintes potentielles
Représentation potentiel étape (CPM ou PERT)
• 1 tâche et associée à 1 arc, 1 sommet va représenter une étape
• Attention : la signification de l ’étape dépend des arcs qui aboutissent.
S5
S1
S2
S4
S3
Tâche 1���d1 Tâche 3���d3S5 = Max (Fin T1, Fin T2) = Min (début T3, début T4)
T1 avant T3 et T4T2 avant T3 et T4
S6
S2
S1
S4
S3
Tâche 2���d2
Tâche 1���d1
Tâche 3���d3
Tâche 4���d4
Ajout de sommets et tâches fictivesT1 avant T3 et T4T2 avant T4S5
0 S6 = Max (Fin T1, Fin Fictive) = début de T3
S5 = Fin de T2 = début de T4
Méthode potentiel Tâche (MPM) • 1 sommet = le début d ’une tache • 1 arc = une contrainte sur le délai Min entre les
débuts de tâches
T1 avant T3 et T4T2 avant T3 et T4
T1
T2
T4
T3
d1
d2
Représentation plus systématique mais plus d ’arcs que CPM
• T2 peut débuter 3 ut avant la fin de T1
• T2 débute au plus tard 3 ut après le début de T1
• T2 débute exactement 3 ut après le début de T1
• T1 commence au plus tôt à la date 3ut
• T1 doit être terminée à la date 20 ut
Autres types de contraintes dans MPM
T1 T2d1 -3
T1 T2-3
t2 - t1 ≤ 3 <=> t1 - t2 ≥ -3
0 T13
3
0 T1d1 - 20
T1 T2-3
Représentation d ’un sommet PERT
• On est intéressé à connaître pour chaque tâche : • Sa date de début au plus tôt sachant que le projet commence à la
date 0 • Sa date de début au plus tard pour ne pas retarder le projet.
T1
Date de début au plus tôt
Date de début au plus tard
• Si ils n ’existent pas ajouter un sommet fictif de début (0) et un sommet fictif de fin (s)
• Date de début au plus tôt d ’un sommet X (tâche, étape ou fin de projet) = chemin le plus défavorable entre le début du projet (0) et le sommet X = plus long chemin entre (0) et X.
• Mode de calcul dépend de la nature du graphe • Souvent graphe sans circuit => Algorithme de Bellman • Arcs tous positifs (pas de contrainte de début ou fin au plus tard)
=> Disjkstra • Si risque de circuits positifs => Dantzig, Blatner, Rao
ou Floyd, Warshall
Calcul des dates de début au plus tôt
0T2
T1
T20
T10s
0
0
0
0
Calcul des dates de début au plus tard
• On fixe la date de début au plus tard du dernier sommet (s) • Date de début au plus tard de (s) = date de début au plus tôt de (s)
• date de début au plus tard d ’une tache X = date de début après laquelle le projet est en retard. = Date de début au plus tard de (s) - Plus court chemin de X à (s)
• Mode de calcul : • On part de (s), on prend tous les arcs en sens inverse (valeur
inverse)
=> Début au plus tard de T1 = Min (début au plus tard de T2 -µ2, début au plus tard de T3 - µ3)
T1
T2
T3µ3
µ2
Exemple
00
T1
T2
T3
T4
(s)
1
2
3
4
5
6
7
Notion de marge • Marge totale d ’une tâche X
= marge possible sur le début de X sans retarder le projet = date de début au plus tard de X - date de début au plus tôt de X
• Marge libre d ’une tâche X = marge possible sur le début de X sans retarder une autre tâche
= Min (début plus tôt de U - durée X->U) - début au plus tôt de X U ∈ Suivants(X)
Durée aléatoire • distribution de probabilité de réaliser une tâche dans
une durée donnée est souvent assimilée à une loi ß-PERT.
Probabilité d ’une durée égale à t
t
O PR
O = durée OptimisteR = durée la plus RéalisteP = durée Pessimiste
durée moyenne = (O + 4 R+P) / 6
Sigma = (P- O) / 6
Flots dans un graphe
Flot max, flot max de cout min Problèmes d ’affectation
Exemple • On a 2 captages d ’eau pour alimenter 4 villages en eau
potable. • Peut on répondre à leur demande à l ’heure de
consommation la plus forte ?
C1
C2
V1
V2
V3
V4
(s)(p)
Débit source
Capacité des canalisationsDemande
200
150
110
80
80
80
80 80
80
30
90
70
140
Problème de flot max et flot max de coût min • Graphe = 1 réseau traversé par un flot de matière sans pertes ni sur
les arcs ni aux sommets. • Flot d ’un arc u = φu = quantité circulant entre l’origine et l’extrémité
de l ’arc • Arcs u a 2 valeur : capacité max cu en matière ET Coût Cu par unité
de matière • 0 ≤ φ u ≤cu
• Coût total = ∑ φu Cu
• 1 sommet source fournit toute la matière, 1 sommet puit absorbe toute la matière
• En tout sommet : ∑ flot entrant = ∑ flot sortant (loi des nœuds)
Problème de flot max et flot max de coût min
(s)
1
2 4
3
(p)13,8
25,220,2
13,1
4,2
15,320,2
13,4
source puit
Flot max de coût min = comment faire passer un maximum de matière entre (s) et (p) à moindre coût
Exemple
• Arc saturé si flot de l ’arc = capacité de l ’arc • Flot complet = tout chemin de (s) à (p) contient au moins un
arc saturé
• Attention flot complet ≠ flot max => re-routage de la matière
Terminologie
(s)
1
2 4
3
(p)13
2520
13
4
1520
131213
1320 5
194
15
(s)
1
2 4
3
(p)13
2520
13
4
1520
13213
1320 15
94
5 Flot complet = 22
Flot complet = 32
Coupe • A ensemble de sommets contenant (p) mais pas (s)
= support de la coupe
• Coupe C = ensemble des arcs d ’origine hors de A et d ’extrémité dans A
• Pour toute coupe, ∑flot des arcs de C = flot entrant = flot sortant
• Théorème : Flot max <=> il existe une coupe dont tous les arcs sont
saturés
Construction d ’un flot de départ 1/ Sélectionner un chemin de (s) à (p) 2/ Saturer ce chemin :
augmenter le flot de manière à saturer un arc du chemin
3/ Revenir au 1/ tant qu ’on trouve des chemins non saturés
• Remarque : si on a bien pris tous le chemins, on a construit un flot complet
Algorithme de marquage de Ford Fulkerson • 2 règles :
R1 : marquer à (+x) un sommet Y si X marqué et arc u X->Y non saturé φu< cu
• On peut ajouter (cu - φu) unité de matière sur l ’arc u R2 : marquer à (-x) un sommet Y si X marqué et arc u Y->X de flux φu >0
• On peut enlever φu unité de matière sur l ’arc u Algorithme de marquage :
• A = ens des sommets nouvellement marqués • 1/ marquer (s) à 0 et ajouter (s) à A • 2/ Tant que A ≠ {}
• 3/ sélectionner un sommet X de A • 4/ essayer de marquer les successeurs de X non marqués avec R1 ou R2 • 5/ ajouter ces successeurs nouvellement marqués à A • 6/ si (p) ∈ A, STOP, Sinon aller en 2/
• Si on a pu marquer (p) c ’est que le flot n ’est pas max • Il existe une chaine de sommets marqués de (s) à (p).
Exemple (s)
1
2(p)
715
20
13
15
020 13
13
7
(s)
1
2
(p)7
15
20
13
15
020 13
13
7
(0)(+s)
(-1)(+2)
(0) R1 permet de marquer 1 à (+s)���on peut ajouter 7 unités de matière
(s)
1
2(p)
715
20
13
15
020 13
13
7
(+s)R2 permet de marquer 2 à (-1)On peut enlever 13 unités de matière
(-1)
R1 permet de marquer (p) à (+2)on peut ajouter 8 unités de matière
Principe de re-routage de la matière • Il existe une chaine reliant des sommets marqués de (s) à (p) • Pour chaque arc u de la chaîne,
repérer la quantité maximale ϕu pouvant être re-routée • ajoutée sur l’arc X->Y si Y est marqué à (+x) • enlevée sur l’arc Y->X si Y est marqué à (-x)
• Soit ϕ = Min(ϕu ) • Re-router ϕ unité de matière
• Ajouter ϕ sur l’arc X->Y si Y est marqué à (+x) • Enlever ϕ sur l’arc Y->X si Y est marqué à (-x)
(s)
1
2
(p)7
15
20
13
15
020 13
13
7
(0)(+s)
(-1)(+2)
Sur (s)-> 1 on peut ajouter 7Sur 2-> 1 on peut enlever 13Sur (2) ->p on peut ajouter 8
=> ϕ = 7 (s)
1
2
(p)7
15
20
13
15
720 6
13
14
Flot Max : algorithme de Ford Fulkerson L ’algorithme de marquage permet de savoir par où
ajouter de la matière tant qu ’on le peut
• 1/ construire un flot initial (il peut être nul) • 2/ Appliquer l ’algorithme de marquage sur ce flot • 3/ Si (p) est marqué
• 4/ repérer la chaine de marquage de (s) à (p) • 5/ ajouter le max de matière possible selon cette chaine • 6/ Aller en 2/
Ford-Fulkerson
Flot max : par le graphe d ’écart • 1/ construire un flot initial φ • 2/ construire le graphe d ’écart Ge de ce flot φ • 3/ si il existe un chemin de (s) à (p) dans Ge,
• Soit ϕ = Min(capacité des arcs du chemin de (s) à (p) dans Ge)
• 4/ Ajouter ϕ au flot φ • Pour tout arc du chemin de (s) à (p) Ajouter ϕ à l ’arc correspondant du flot φ si il est dans le même sens que
u Enlever ϕ à l ’arc correspondant du flot φ si il est dans le sens inverse de
u
• 5/ aller en 2/
Exemple
(s)
1
2(p)
715
20
13
15
020 13
13
7
Flot Graphe d ’écart Ge
(s)
1
2(p)
7
2013 2
13
778
(s)
1
2(p)
715
20
13
15
720 6
13
14
Flot
ϕ = 7
Graphe d ’écart Ge
(s)
1
2(p)
7
206 9
13
114
Pas de chemin de (s) à (p)=> flot = Max
Flot max de coût Min : première méthode • Théorème : Si il existe un circuit de coût < 0 dans le graphe
d ’écart, on peut re-router de la matière à moindre coût dans le flot associé.
• On construit un flot max, puis on réduit son coût. 1/ construire un flot max 2/ construire le graphe d ’écart Ge associé (capacité et coût) 3/ rechercher un circuit de coût <0 dans Ge 4/ re-router la matière (idem flot max) • Recherche du circuit de coût < 0 :
• On recherche tous les plus court chemin dans Ge avec l ’algorithme de Floyd, Warshall
• Si on trouve un chemin de (s) à (p), le flot n ’était pas max et on l ’augmente
• Si on trouve un circuit absorbant dans Ge, il est de coût <0
Exemple (s)
1
2 4
3
(p)13,8
25,220,2
13,1
4,2
15,320,2
13,4
source puit
1313
13
194
19
4
15
Flot max : Coupe {3, 4 , (p) } est saturée.
(s)
1
2 4
3
(p)13,-8
21,21,2
13,-1
4,-2
15,-320,-2
13,-4
source puit4,-2
19,-2
Graphe d ’écart :
Pas de chemin de (s) à (p) => Flot max.Circuit (s)-2-1-(s) : valeur = 2 + 2 -8 = -4Maximum de matière re-routée = 1 (arc (s)->2)
Exemple (2)
(s)
1
2 4
3
(p)13,8
25,220,2
13,1
4,2
15,320,2
13,4
source puit
12 13
205
19
4
15
(s)
1
2 4
3
(p)
12,-8 13,-1
4,-2
15,-320,-2
13,-4
source puit5,-2
20,-2
Graphe d ’écart :
1 Circuit (s)-1-2-(s) : valeur = -2 - 2 +8 = +4Flot max de coût Min
1,8 20,2
• Principe : on part du flot nul et on l ’augmente petit à petit à moindre coût.
• 1/ on part du flot nul, φ=0 • 2/ construire le graphe d ’écart associé à φ • 3/ Si il existe un plus court chemin de (s) à (p) dans Ge
• Augmenter le flot φ selon ce chemin (cf méthode flot max par le graphe d ’écart)
• Aller en 2/
• 4/Sinon le flot est max de coût min
• Remarque : il ne peut y avoir de circuit absorbant au 3/ car sinon cela signifie qu ’il existait un chemin plus court à une étape précédente.
Flot max de coût Min : deuxième méthode
(s)
1
2 4
3
(p)13,8
25,2
20,2
4,2
15,320,2
13,413,1
Marquage + court cheminFlot
(s)
1
2 4
3
(p)13,8
25,2
20,2
4,2
15,320,2
13,413,1
0
2
4
5
7
5
(s)
1
2 4
3
(p)13,8
25,2
20,2
4,2
15,320,2
13,413,1
15 1515
(s)
1
2 4
3
(p)13,8
25,25,2
4,2
15,-3
5,2
13,413,1
0 15,-2 15,-22
4 5
6
8
(s)
1
2 4
3
(p)13,8
25,2
20,2
4,2
15,320,2
13,413,1
19 1519
ϕ = 15
ϕ = 1 4
4(s)
1
2 4
3
(p)13,8
21,21,2
4,-2
15,-3
1,2
13,413,1
0 19,-2 19,-22
4 5
94,-2
ϕ = 4
Marquage + court cheminFlot
(s)
1
2 4
3
(p)13,8
25,2
20,2
4,2
15,320,2
13,413,1
20 1519 ϕ = 12
5
1
(s)
1
2 4
3
(p)13,8
20,24,-2
15,-3
12,412,1
0 20,-2 19,-26
8 9
135,-2
11,-1
1,-4
11
(s)
1
2 4
3
(p)13,8
25,2
20,2
4,2
15,320,2
13,413,1
20 1519
5
1313
12
4
4 (s)
1
2 4
3
(p)1,820,2 4,-2
15,-30 20,-2 20,-26
8
5,-2
13,-113,-412-,8
L ’algorithme de plus court chemin ne permet pas de marquer (p)=> il n ’y a pas de chemin de (s) à (p) => flot Max.=> il n ’y a pas de circuit absorbant => flot max de coût min
1,2
Affectation
Algorithme Hongrois
Problème basique d ’affectation • Soient N taches à affecter à N personnes • Chaque personne ayant des compétences
différentes, on donne par personne un temps de réalisation de chaque tâche.
• Objectif : Affecter les personnes aux tâches de manière à générer une charge minimale
T1 T2 T3 T4 T5 Lionel 86 94 82 84 37 Emmanuel 59 22 56 27 30 Didier 56 19 64 20 20 Jacques 54 26 95 75 17 Michel 28 68 45 49 97
Algorithme Hongrois 1/ Soustraire a chaque ligne la valeur Min
T1 T2 T3 T4 T5 Lionel 49 57 45 47 0 37 Emmanuel 37 0 34 5 8 22 Didier 37 0 45 1 1 19 Jacques 37 9 78 58 0 17 Michel 0 40 17 21 69 28
2/ Soustraire a chaque colonne la valeur Min T1 T2 T3 T4 T5
Lionel 49 57 28 46 0 37 Emmanuel 37 0 17 4 8 22 Didier 37 0 28 0 1 19 Jacques 37 9 61 57 0 17 Michel 0 40 0 20 69 28
0 0 17 1 0 141
Somme des Min ligne et colonne= coût minimal d ’une affectation
=> Au moins un « 0 » par ligne et par colonne
Algorithme Hongrois • 3/ Pour chaque « 0 »intersection de ligne i et colonne j
Regreti,j = Min (ligne i sauf le « 0 ») + Min (colonne j sauf le « 0 ») • 4/ tant qu ’il reste des « 0 » non barrés,
• 4.1/ encadrer le « 0 » non barré ou encadré ayant le Regret Max Si regret Max = 0 et plusieurs « 0 » possibles, voir cas plus loin
• 4.2/ barrer tous les autres « 0 » sur la même ligne et colonne T1 T2 T3 T4 T5 Lionel 49 57 28 46 0 Emmanuel 37 0 17 4 8 Didier 37 0 28 0 1 Jacques 37 9 61 57 0 Michel 0 40 0 20 69
0 <=> affectation d ’une tâche à une personne à coût nulSi toutes les personnes affectées STOP : optimum trouvé
37
4
0 4
17
28
9
Regret
• Lorsqu ’on doit choisir un « 0 » à encadrer, Si le regret maximal est 0 et plusieurs « 0 » ont le regret maximal. • Alors, recalculer les regrets dans la sous matrice restante :
on met à jour les regrets en considérant les affectations déjà réalisées
• Si plusieurs « 0 » ont encore le regret maximal. • Sélectionner l ’un quelconque de ces « 0 » : cela n ’a aucune
influence sur le résultat .
Algorithme Hongrois : cas du regret Max = 0
Algorithme Hongrois • 6/ Marquage des lignes et colonnes
• 6.1/ Marquer * toute ligne n ’ayant pas de « 0 » encadré • 6.2/ Marquer * toute colonne ayant un « 0 » barré sur une ligne marquée • 6.3/ Marquer * toute ligne ayant un « 0 » encadré dans une colonne marquée • 6.4/ aller au 6.2/ tant qu ’on peut.
• 7/ Obtention de nouveaux « 0 » • 7.1/ Rayer les lignes non marquées et les colonnes marquées • 7.2/ Soustraire µ (la plus petite valeur non barrée) à tous les éléments non rayés • 7.3/ Ajouter µ à tous les éléments barrés 2 fois et Revenir au 3/
T1 T2 T3 T4 T5Lionel 49 57 28 46 0Emmanuel 37 0 17 4 8Didier 37 0 28 0 1Jacques 37 9 61 57 0Michel 0 40 0 20 69
µ = 9
*
*
*
Fin de l ’exemple T1 T2 T3 T4 T5
Lionel 40 48 19 37 0 Emmanuel 37 0 17 4 17 Didier 37 0 28 0 10 Jacques 28 0 52 48 0 Michel 0 40 0 20 78
*
*
*
*
* µ = 4
µ = 13
T1 T2 T3 T4 T5 Lionel 36 48 15 33 0 Emmanuel 33 0 13 0 17 Didier 37 4 28 0 14 Jacques 24 0 48 44 0 Michel 0 44 0 20 82
*
*
*
*
*
*
*
STOP T1 T2 T3 T4 T5 Lionel 23 48 2 33 0 Emmanuel 20 0 0 0 17 Didier 24 4 15 0 14 Jacques 11 0 35 44 0 Michel 0 57 0 33 95
Coût = 141 +9+4+13 = 177
Affectation = Flot Max de Coût Min • Construction du graphe G
• 1 sommet par personne + 1 sommet par tâche + (s) + (p) • Arc de (s) à une personne de coût 0 et capacité 1(nombre de
tâches affectables simultanément à 1 personne) • Arc d ’une personne P à une tâche T de capacité 1 et de coût
égal au coût d ’affecter P à la tâche T. • Arc d ’une tâche à (p) de coût 0 et de capacité 1 (nombre de
personnes a affecter à la tâche pour la réaliser)
• Une personne P est affectée à une tâche T <=> il existe un flot de P à T dans le graphe G
• Affectation de coût Min = Flot Max de coût Min sur G • Démonstration de l ’algorithme hongrois par équivalence
des opérations réalisées sur le flot Max de coût Min.
Transport de matière
Algorithme de Stepping Stone
Problème Type • Soient N usines de fabrication de capacité limitée • Soient M centres de consommation ayant émis une demande ∑ Capacité de production = ∑ demandes
• Soit une matrice NxM donnant les coût de transport de N à M • Trouver qui produit pour qui au moindre coût Coûts a b c d e Capacité A 1,5 6,4 1,8 4 3,5 90 B 1,6 2,6 1,9 3,1 5,8 75 C 5,3 3,5 2,4 1,3 2,2 35 D ∆ ∆ ∆ ∆ ∆ 25 Dmde 40 35 70 30 50 ∆ très grand Site D est ajouté pour que « capacité Totale = Demande Totale » Coûts de transport infinis (∆) pour préciser que ceux ci ne seront pas
réalisés.
Modèle linéaire • Variables : xi,j = la quantité transportée depuis l ’usine i vers le centre de
consommation j. • Données : Ci = capacité de l ’usine i, Dj = demande du centre de
consommation j, Ci,j = coût de transport d ’une unité entre l ’usine i et le centre j.
• Min (∑ci,j xi,j) Pour tout i , ∑xi,j = Ci Pour tout j, ∑xi,j = Dj
• Modèle à N*M variables et N+M contraintes. Une solution est donc caractérisée par N*M-N+M = (N-1)*(M-1) variables à 0
• Stepping Stone = méthode adaptée pour limiter les calculs du simplex + méthode pour construire facilement une première solution
j
i
Algorithme Stepping Stone (1) • 1/ Construire une solution de départ
• 1/ sélectionner le trajet de coût min (C-d) et lui affecter un max de matière => on sature une colonne ou une ligne
• 2/ Tant qu’on le peut • a/ sélectionner la ligne ou la colonne non saturée sur le dernier trajet
considéré, • b/ y affecter la matière restante sur le trajet non évalué de coût min • c/ mettre à 0 les trajets non évalués de la ligne ou colonne saturée
Transp a b c d e Capacité A 40 0 5 0 45 90 B 0 10 65 0 0 75 C 0 0 0 30 5 35 D 0 25 0 0 0 25 Dmde 40 35 70 30 50
• Au moins (N-1)(M-1) trajets à « 0 ». • 1/ Pour chaque « 0 », évaluer le coût de l ’augmentation d ’une unité de la
quantité sur ce trajet (= calcul du coût marginal du simplex) • a/construire un circuit passant par ce trajet et des trajets de flot ≠ 0 • b/ Evaluer le coût de re-router une unité de matière selon ce circuit :
ajoutée au premier trajet, enlevée au deuxième, ajoutée au troisième,…
Transp a b c d e Capacité A 40 0 5 0 45 90 B 0 10 65 0 0 75 C 0 0 0 30 5 35 D 0 25 0 0 0 25 Dmde 40 35 70 30 50
Algorithme Stepping Stone (2)
Théorème : le circuit passant par 1 trajet = 0 et des trajets de flot ≠ 0, existe toujours et est unique
Circuit Bd = Bd - Cd + Ce - Ae + Ac - Bc��� = +3,1- 1,3 + 2,2 - 3,5 + 1,8 - 1,9 = 0,4
Algorithme Stepping Stone (2) • 2/ Si tous les circuits des « 0 » sont >0, le plan est optimum
(i.e. tous les coûts marginaux sont >0) • 3/Sinon,
• a/ sélectionner un « 0 » de circuit négatif (souvent le plus négatif)
• b/ affecter sur son circuit le plus de matière possible et aller au 1/
• Exemple • Circuit Ab : Ab-Ac+Bc-Bb Coût = 6,4 - 1,8 + 1,9 - 2,6
= 3,9 • Circuit Dd : Dd-Bd+Bc-Ac+Ae-Ce+Cd-Dd
Coût = ∆ - ∆ +2,6 - 1,9 + 1,8 - 3,5 +2,2 - 1,3 = -0,1 • Circuit De : De - Db+Bc-Ac+Ae-De Coût = ∆- ∆ + 2,6 - 1,9 +
1,8 -3,5 = -1 • Circuit De est le plus négatif
Problème : comment rechercher tous les circuits rapidement ??
Rechercher les circuits négatifs : méthode du potentiel
• 1/ tracer le graphe Ge dont les sommets sont les Usines ou les Centres de consommation et les arcs sont les trajets
• 2/ sélectionner un sommet Usine et lui affecter le potentiel 0 • 3/ A partir d ’un sommet Usine U ayant un potentiel fixé,
• Définir le potentiel d ’un sommet Centre de consommation CC relié à U dans Ge par : Potentiel (CC) = Potentiel (U) + coût(U->CC)
• 4/ A partir d ’un sommet Centre de consommation CC ’ ayant un potentiel fixé, • Définir le potentiel d ’un sommet Usine U ’ relié à CC ’ dans Ge par :
Potentiel (U ’) = Potentiel (CC ’) - coût(U ’->CC ’) • 5/ boucler sur 3/ tant que tous les sommets n ’ont pas un potentiel fixé.
A
B
C
D
a
b
c
d
e
0
1,8-1,9=-0,1
3,5-2,2=1,3
2,5-∆
1,5
2,5=2,6-0,1
1,8
2,6= 1,3 + 1,3
3,5
Graphe Ge et potentiels correspondants au premier plan de
distribution
Trouver les circuits négatifs : méthode du potentiel (2) • La méthode permet de calculer le coût marginal
d ’un circuit passant par 1 trajet de flot 0 et des trajets de flot ≠ 0
• Pour tout trajet à 0 allant d ’une Usine U à un centre CC : • Coût du circuit = coût (U->CC) + Potentiel (U) -Potentiel
(CC) • Circuit Bd = 3,1- 0,1 - 2,6 = 0,4 => on sait trouver la valeur du circuit d ’un trajet à « 0 » sans
connaître ce circuit.
• Sélectionner le « 0 » ayant le circuit le plus négatif puis rechercher le circuit correspondant. On sait que ce circuit est unique.
Fin de l ’ exemple Transp a b c d e Capacité
A 40 0 30 0 20 90 Ab 3,9 Ad 1,4 B 0 35 40 0 0 75 Ba 0 Bd 0,4 Be 2,2 C 0 0 0 30 5 35 Ca 5,1 Cb 2,3 Cc 1,9 D 0 0 0 0 25 25 Da 2 Db 1 Dc 1,7
Dmde 40 35 70 30 50 Dd 0,9 Circuit Ab -Ac-Bc-Bb-Ab : 3,9 Circuit Ad-Ae-Ce-Cd-Ad : 1,4 Circuit Ba-Bc-Ac-Aa-Ba : 0 Circuit Bd-Cd-Ce-Ae-Ac-Bc-Bd : 0,4 Circuit Be-Ae-Ac-Bc-Be : 2,2 Circuit Ca-Ce-Ae-Ca : 5,1 Circuit Cb-Bb-Bc-Ac-Ae-Ce-Cb : 2,3 Circuit Cc-Bc-Ac-Ae-Ce-Cc : 1,9 Circuit Da-De-Ae-Aa-Da : 2 Circuit Db-De-Ae-Ac-Bc-Bb-Db : 1 Circuit Dc-De-Ae-Ac-Dc : 1,7 Circuit Dd-De-Ce-Cd-Dd : 0,9
Tous les circuits sont >0 => le plan est optimum.
Routage de matière = Flot max de coût Min • Construction du graphe G
• 1 sommet par usine + 1 sommet par centre de consommation + (s) + (p)
• Arc de (s) à une usine de coût 0 et capacité celle de l ’usine • Arc d ’une Usine U à un centre de consommation CC de capacité ∞ et
de coût celui du trajet de U à CC. • Arc d ’un centre de consommation CC à (p) de coût 0 et de capacité
égale à la demande du centre. • Un trajet de U à CC est utilisé
<=> il existe un flot de U à CC dans le graphe G • Plan de transport de coût Min = Flot Max de coût Min sur G • Remarque : Stepping Stone <=>
1/construire un flot max 2/ évaluer tous les circuits de coûts négatif dans le graphe d ’écart 3/ réduire le coût du flot selon un circuit négatif et retourner au 1/
Merci !