Introduction à la programmation linéaire

Introduction à la
programmation linéaire
Programmation linéaire 1/15
Introduction
Modélisation
Résolution

---

Recherche opérationnelle
• Applications de la théorie des graphes
problèmes d’ordonnancement
• Programmation linéaire
Programmation linéaire 2/15
Introduction
Modélisation
Résolution

---

La démarche de la R.O.

Identification du problème
 Collecte des informations

Construction d'un modèle

Obtention des solutions

Interprétation et discussion
Programmation linéaire 3/15
Introduction
Modélisation
Résolution

---

Skigliss : l’histoire d’une diversification
 Une entreprise de production de skis
–
division 1 : noyaux bois
–
division 2 : noyaux PU
–
division 3 : moulage
 Diversification avec :
–
le snowboard freestyle (produit 1)
–
et le snowboard alpin (produit 2)
 Réorganisation de la production
–
40 minutes libérées dans la division 1
–
120 minutes libérées dans la division 2
–
180 minutes libérées dans la division 3
Programmation linéaire 4/15
Introduction
Modélisation
Résolution

---

Skigliss : identification du problème
Décider quelle
quantité produire
pour chaque modèle,
de manière à
maximiser le
profit, tout en
respectant les
contraintes.
Programmation linéaire 5/15
Introduction
Modélisation
Résolution

---

Skigliss : collecte des informations
• La production d’un modèle 1 utilise 2 minutes en
division 2 et 2 minutes en division 3 .
• La production d’un modèle 2 utilise 1 minute en
division 1 et 3 minutes en division 3.
• Le profit généré par la production d’un modèle 1 est
égal à 40 € et pour un modèle 2 à 30 €.
Programmation linéaire 6/15
Introduction
Modélisation
Résolution

---

Skigliss : modélisation
• Choix des variables de décision
–
Soit x le nombre de modèles 1 produits en 1 jour
1
–
Soit x le nombre de modèles 2 produits en 1 jour
2
• Détermination des contraintes
–
Si la production d’un modèle 2 utilise 1 minute, la production de x2
unités utilise x minutes. Comme la disponibilité journalière est de 40
2
minutes, on doit avoir :
–
x
≤
40
2
– 2 x
≤
120
1
– 2 x + 3 x ≤180
1
2
Programmation linéaire 7/15
Introduction
Modélisation
Résolution

---

Skigliss : modélisation
• Objectif = Fonction économique
on cherche à maximiser le profit,
c’est à dire à maximiser :
Z = 40 x + 30 x
1
2
Programmation linéaire 8/15
Introduction
Modélisation
Résolution

---

Le modèle : un programme linéaire
MAX Z =
40 x +
30 x
1
2
x ≤
40
2
2 x
≤
120
1
2 x + 3 x ≤180
1
2
x ≥ 0; x ≥ 0
1
2
Programmation linéaire 9/15
Introduction
Modélisation
Résolution

---

Résolution graphique
x2
6
0
50
40
x = 40
2
3
0
2
0
1
0
x
0
1
Programmation linéa
1 ire 10/1
2 5
In
3 troduc
4tion
0
5
Modé
6 lisation7
8 Résolut
9 ion
0
0
0
0
0
0
0
0

---

Résolution graphique
x2
2 x = 120
6
1
0
50
40
x = 40
2
3
0
2
0
1
0
x
0
1
Programmation linéa
1 ire 11/1
2 5
In
3 troduc
4tion
0
5
Modé
6 lisation7
8 Résolut
9 ion
0
0
0
0
0
0
0
0

---

Résolution graphique
x2
2 x = 120
6
2 x + 3x = 180
1
1
2
0
50
40
x = 40
2
3
0
2
0
1
0
x
0
1
Programmation linéa
1 ire 12/1
2 5
In
3 troduc
4tion
0
5
Modé
6 lisation7
8 Résolut
9 ion
Résolution
0
0
0
0
0
0
0
0

---

Résolution graphique
x2
2 x = 120
6
2 x + 3x = 180
1
1
2
0
50
40
x = 40
2
Ensemble
3
0
des solutions
2
réalisables
solution optimale
0
x = 60
1
1
Droite
x = 20
2
0
d’iso-profit
Z = 3 000
x
0
1
Programmation linéa
1 ire 13/1
2 5
In
3 troduc
4tion
0
5
Modé
6 lisation7
8 Résolut
9 ion
0
0
0
0
0
0
0
0

---

Résolution avec Excel
a) On appelle le solveur (Outils
Solveur)
b) On définit la cellule cible
(ici : D10)
c) On définit le sens de
l’optimisation (ici : Max)
d) On indique les cellules
variables (ici B2 et C2)
e) On ajoute les contraintes
(elles peuvent être entrées
sous forme vectorielle)
f) On spécifie l’option :
« Modèle supposé linéaire »
g) Et enfin on clique sur le
bouton Résoudre
Programmation linéaire 14/15
Introduction
Modélisation
Résolution

---