CHAPITRE

Recherche opérationnelle
Plan du cours



Chapitre I : Introduction à la programmation linéaire ............................................................................... 2
Série 1 : Corrigés des exercices n° 1 à 2 et 5.......................................................................................... 4
Chapitre II : Résolution d’un PL par la méthode graphique ....................................................................... 9
Série 2 : Corrigés d’exercices ............................................................................................................... 20
Chapitre III : Résolution d’un PL par la méthode dite du « Simplexe ».................................................... 24
Série 3 : Corrigés d’exercices..... 30
Chapitre IV : Méthode du Simplexe : Problème de minimisation et problème irrégulier.......................... 39
Chapitre V : Dualité.........................................................................................................................................
Chapitre VI : Ordonnancement ..........................................................................................................................
T.P. : Programme de résolution d’un PL : L.I.N.D.O.........................................................................................
1 Recherche opérationnelle


Recherche opérationnelleCHAPITRE
Introduction à la 18 1
02programmation linéaire





I – Introduction
La programmation linéaire est une classe de modèles mathématiques d’optimisation qui a pour objet la
maximisation ou minimisation d’une fonction linéaire de variables ( appelée fonction objectifs soumise à des
contraintes (équations ou inéquations ).
Le terme « programmation » indique le fait que c’est un problème d’optimisation qui, du point de vue
économique, concerne l’allocation efficace des rares ressources à certaines activités en vue de maximiser ( ou
minimiser ) un certain objectif.
Le terme « linéaire » indique que les relations mathématiques qui lient ces activités aux variables sont
linéaires.
L’une des décisions les plus fréquentes d’un gestionnaire est l’allocation des ressources entre des
activités données en vue d’un objectif déterminé : La minimisation des coûts, la maximisation des profits où
l’optimisation d’un critère quelconque de performance constitue l’une des préoccupations urgentes du chef
d’entreprise surtout que ce dernier dispose de ressources limitées en matières premières, main d’œuvre et fonds.
Donc, la programmation linéaire fournit au décideur une méthode pour la recherche des solutions
optimales à ces problèmes d’allocation.

II – Formulation d’un modèle de
décision
1 – Caractéristiques d’un programme linéaire (PL)
Un PL est caractérisé par :
A – Sa fonction économique ou fonction objectif ou fonction linéaire notée Z :
Z = C x + C x + … + C x1 1 2 2 n n
x ,x , …, x = Variables 1 2 n
Remarque : Si c’est un profit, on parle alors de maximiser Z. S’il s’agit de coûts, l’on parle alors de
minimiser Z tout en respectant les contraintes.

B – Des inconnues (x ,x , …, x ) ou variables de décision. indépendantes dont on cherche les valeurs. 1 2 n
C – Des contraintes qui doivent vérifier ces inconnues qui prennent la forme d’égalités ou inégalités.

2 – Formulation d’un PL
Un menuisier fabrique des portes et des chaises. Quel est l’objectif du menuisier ?
⇒ Sa fonction objectif : Maximiser le profit.
2
2005 Recherche opérationnelle
Ce menuisier est soumis à des contraintes.
On a : Z = C x +C x 1 1 2 2
Avec : x = la quantité produite de tables. 1
x = la quantité produite de chaises. 2
C = Prix de vente des tables. 1 = Prix de vente des chaises. 2
DIl est à noter que le profit unitaire généré par la vente d’une table est de 2 . Le profit unitaire généré par
Dla vente d’une chaise est de 3 . D’où :
Z = 2x +3x 1 2
x x Disposition 1 2
HM 2 4 120
MP 3 2 240
2 3 ΠU
Supposons que :
- 1 unité produite de tables nécessite 2 unités d’heures de main d’œuvre et 3 unités de matières
premières.
- 1 unité produite de chaises nécessite 4 unités d’heures de main d’œuvre et 2 unités de matières
premières.
- Le menuisier dispose de 120 heures de main d’œuvre et de 140 unités de matières premières.
Disposer les données en tableau !

HM = Heures de main d’œuvre.
MP = Matière première.
ΠU = Profit unitaire ( Π - pi – pour profit ).
Le programme linéaire s’écrit sous la forme :
Max Z = 2 x +3 x 1 2
Sous les contraintes :
2x + 4x ≤ 120 1 2
3x +2x ≤ 240 1 2
avec toujours x ≥ 0 et x ≥ 0 . 1 2

La formulation initiale d’un programme linéaire donne en général un problème sous la forme générale
qui est :
n
Max ou Min Z = C x + C x + … + C x = C x 1 1 2 2 n n ∑ i i
i =1
erS/C a x + a x + … + a x ≥ b 1 type 11 1 12 2 1n n 1
ème . ≤ b 2 type i
ème. = b 3 type i
a x + a x + … + a x n1 1 n2 2 nn n

Exemple de formulation
Dans une raffinerie, on fait la distillation de 2 types de pétrole B et B pour déterminer 3 qualités 1 2
d’essences E , E et E . 1 2 3
La raffinerie doit approvisionner un distributeur d’essence. La distillation de 100 litres de B1 fournit 10
litres de E1, 10 litres de E2 et 20 litres de E3 alors que la distillation de la même quantité de B2 fournit 50
litres de E1, 40 litres de E2 et 20 litres de E3.
La raffinerie doit satisfaire une commande de 500 litres de E1, 400 litres de E2 et 600 litres de E3.
Sachant que les coûts par m3 sont de 20 d pour B1 et de 25 D pour B2, formulez le PL qui minimise le
coût des quantités des bruts utilisés pour la satisfaction de la demande.
3 c
d
e
d
e
e
d
c
c
Recherche opérationnelle


Recherche opérationnelleCHAPITRE
Correction d’exercices 19 1
02
de la série n°1



Rappels : Les étapes de la formulation d’un PL sont :
n
Fonction objectif : Max ou Min Z = C x + C x + … + C x = C x 1 1 2 2 n n ∑ i i
i =1

Variables de décision : x j

er Contraintes : a x + a x + … + a x ≥ b 1 type 11 1 12 2 1n n 1
ème . ≤ b 2 type i
ème. = b3 type i
a x + a x + … + a x n1 1 n2 2 nm n
Remarque : Les contraintes forment un système matriciel : A X = b .

Corrigé de l’exercice n°1

Fonction objectif : Minimiser les coûts des quantités de brut. <-> Z = C x + C x min 1 1 2 2
Variables de décision : x : Quantité de brut de B . 1 1
x . 2 2
Contraintes : Contraintes de satisfaction des commandes.

D’où le PL suivant :
Min Z = 20x + 25x1 2
S 10 x + 50 x ≥ 500 1 2
C
10 x + 40 x ≥ 400 1 2
20 x + 20 x ≥ 600 1 1
avec x et x ≥ 0 1 2

Corrigé de l’exercice n°2
Fonction objectif : Maximiser le profit <-> max Π
Variables de décision :
Quantités produites d’interrupteurs de type A : x 1
Π
’ine type B : x2
Contraintes : La production est limitée par :
rea) 1 contrainte : Le temps de travail
T = nombre d’heures de travail disponibles
t = nombre d’heures nécessaires pour fabriquer un interrupteur de type A. 1
4
2005 c
d
e
f
g
Recherche opérationnelle
t = nombre d’heures nécessaires pour fabriquer un interrupteur de type B. 2
T = t x + t x ≤ T 1 1 2 2
T = 2 t1 2
Si x 0 , on fabrique le maximum de B c’.à.d. x = 1000. 1 = 2
Nous avons = t x = T <-> 1000 t = T 2 2 2
D’où : 2 t x + t x ≤ 1000 t 2 1 2 2 2
2 x + x ≤ 1000 1 2

èmeb) 2 contrainte : L’isolant disponible
x + x ≤ 600 1 2

èmec) 3 contrainte : La quantité de fil de laiton
x ≤ 400 1
x ≤ 700 2
D’où le PL suivant :
Max Π = 0,4 x + 0,3 x 1 2
S 2 x + x ≤ 1000 1 2C
x + x ≤ 600 1 2 ≤ 400 1
x ≤ 700 2
avec x et x ≥ 0 1 2

Corrigé de l’exercice n°5
x = nombre de chauffeurs qui commencent le travail au début de la période i de 2 heures. i
Pour avoir a pendant la période i, on essaie de définir les contraintes par période : i

Période : x + x + x + x + x + x + x +x + x + x +x + x ≥ a1 2 3 4 5 6 7 8 9 10 11 12 1
x + x + x + x ≥ a 1 10 11 12 1
Période : x + x + x + x ≥ a 1 2 11 12 2 : x + x + x + x ≥ a 1 2 3 12 3
Période : x + x + x + x ≥ a 1 2 3 4 4
Périodes 5 à 12 : x + x + x +x ≥ a k-3 k-2 k-1 k k
Ex