INTRODUCTION À LA RECHERCHE
OPÉRATIONNELLE
Chapitre 2: Programmation Linéaire
Méthode graphique
Rappel:
Programme linéaire:
min cx
sous les contraintes
matrice
Ax = b ,
x0
contrainte de
non négativité
vecteur des variables
de décision
12-juin-19 UFR SET MMA Département de 2
Mathématiques et Informatique
La résolution graphique
La méthode de résolution graphique
n’est valide que si le problème possède
au plus 2 variables.
Nécessité de transformer la forme
géométrique en forme algébrique pour
résoudre des problèmes de plus grande
taille.
Focus sur de petits problèmes pour
illustrer les méthodes.
12-juin-19 UFR SET MMA Département de 3
Mathématiques et Informatique
Objectif immédiat
Description de la méthode du simplexe
où il suffit de vérifier/visiter les
sommets (coins) de l’ensemble des
solutions réalisables (ensemble de
définition).
12-juin-19 UFR SET MMA Département de 4
Mathématiques et Informatique
Entreprise FRB: description du contexte
Produits et demande
N o Description Demande (t) Profit ($ / t)
1 Tuyauterie 34 1 000
2 Gueuses 14 1 200
Durée de fabrication
Temps requis Ébarbage Peinture
Tuyauterie 10 h/t 2 h/t
Gueuses 5 h/t 3 h/t
Heures disponibles 200 h 60 h
12-juin-19 UFR SET MMA Département de 5
Mathématiques et Informatique
FRB : le modèle linéaire
12-juin-19 UFR SET MMA Département de 6
Mathématiques et Informatique
S
12-juin-19 UFR SET MMA Département de 7
Mathématiques et Informatique
12-juin-19 UFR SET MMA Département de 8
Mathématiques et Informatique
Théorème fondamental de la
programmation linéaire :
Si un modèle linéaire continu admet au
moins une solution optimale, l’une
d’entre elles correspond à un point
extrême.
12-juin-19 UFR SET MMA Département de 9
Mathématiques et Informatique
FRB et fonctions-objectifs modifiées
Solution(s) optimales(s)
Fonction - objectif
dans OABCD
z1 600 x1 1200 x2 A = ( 0;14 )
z2 600 x1 1200 x2 B = ( 9;14 )
z3 1000 x1 1200 x2 C = (15;10)
z4 2400 x1 1200 x2 Segment C; D
z5 2500 x1 500 x2 D = ( 20;0 )
z6 200 x1 1000 x2 O = ( 0;0)
12-juin-19 UFR SET MMA Département de 10
Mathématiques et Informatique
12-juin-19 UFR SET MMA Département de 11
Mathématiques et Informatique
Dans la solution optimale :
contrainte active <=> l’égalité est vérifiée
(binding constraint)
contrainte inactive <=> l’égalité n’est pas
vérifiée (< ou >) (il y a un “surplus” de
ressource)
géométriquement: une contrainte active
<=> une droite qui passe par la solution
optimale
Points extrêmes <=> sommets du polygone
Dans PL: si solution optimale => au moins
une des solutions optimales = point extrême
12-juin-19 UFR SET MMA Département de 12
Mathématiques et Informatique
Exemple
Objectif
Min Z 3 x1 4 x2
Sous les contrainte s
x1 x2 9
x1 x2 9
x1 3 x2 17
x1 3
x2 10
x1 0
x2 0
12-juin-19 UFR SET MMA Département de 13
Mathématiques et Informatique
x2 X1 = 3
12-juin-19 UFR SET MMA Département de 14
Mathématiques et Informatique
12-juin-19 UFR SET MMA Département de 15
Mathématiques et Informatique
