Embed Size (px)
Citation preview
Programmation linéaire 1/15 Introduction RésolutionModélisation
Introduction à la programmation linéaire
Programmation linéaire 2/15 Introduction RésolutionModélisation
Recherche opérationnelle
• Applications de la théorie des
graphes
problèmes d’ordonnancement
• Programmation linéaire
Programmation linéaire 3/15 Introduction RésolutionModélisation
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 4/15 Introduction RésolutionModélisation
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 5/15 Introduction RésolutionModélisation
Skigliss : identification du problème
Décider Décider quelle quelle
quantité produire quantité produire
pour chaque pour chaque
modèle, de modèle, de
manière àmanière à
maximisermaximiser le le
profitprofit,, tout en tout en
respectant les respectant les
contraintescontraintes..
Programmation linéaire 6/15 Introduction RésolutionModélisation
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 7/15 Introduction RésolutionModélisation
Skigliss : modélisation
• Choix des variables de décision
– Soit x1 le nombre de modèles 1 produits en 1 jour
– Soit x2 le nombre de modèles 2 produits en 1 jour
• Détermination des contraintes
– Si la production d’un modèle 2 utilise 1 minute, la production de
x2 unités utilise x2 minutes. Comme la disponibilité journalière
est de 40 minutes, on doit avoir :
– x2 40
– 2 x1 120
– 2 x1 + 3 x2180
Programmation linéaire 8/15 Introduction RésolutionModélisation
Skigliss : modélisation
• Objectif = Fonction économique
on cherche à maximiser le profit,
c’est à dire à maximiser :
Z = 40 x1 + 30 x2
Programmation linéaire 9/15 Introduction RésolutionModélisation
Le modèle : un programme linéaire
MAX Z = 40 x1 + 30 x2
x2 40
2 x1 120
2 x1 + 3 x2180
x1≥ 0; x2 ≥ 0
Programmation linéaire 10/15 Introduction RésolutionModélisation
Résolution graphique
20
40
60
80
90
70
10
10
20
60
40
50
30
50
30
0
x2
x1
x2 = 40
Programmation linéaire 11/15 Introduction RésolutionModélisation
Résolution graphique
20
40
60
80
90
70
10
10
20
60
40
50
30
50
30
0
x2
x1
2 x1 = 120
x2 = 40
Programmation linéaire 12/15 Introduction RésolutionModélisation
Résolution graphique
20
40
60
80
90
70
10
10
20
60
40
50
30
50
30
0
x2
x1
x2 = 40
2 x1 + 3x2 = 1802 x1 = 120
Résolution
Programmation linéaire 13/15 Introduction RésolutionModélisation
Résolution graphique
20
40
60
80
90
70
10
10
20
60
40
50
30
50
30
0
x2
x1
x2 = 40
2 x1 + 3x2 = 180
Ensembledes solutionsréalisables
Droited’iso-profit
solution optimalex1 = 60x2 = 20
Z = 3 000
2 x1 = 120
Programmation linéaire 14/15 Introduction RésolutionModélisation
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
