Université Hassan II – Casablanca-
Licence Professionnelle: Logistique et Commerce
Cours
Recherche opérationnelle
Programmation linéaire
AU:2016-2017
1 M [Link] AU:2016-2017
Plan du cours
1) Introduction
2) Objectifs de la programmation linéaire
3) Méthode graphique
4) Méthode de simplex
5) Dualité
2 M [Link] AU:2016-2017
introduction
.
A) Recherche opérationnelle
Méthodes et techniques d’aide a la décision
Trouve son origine au début du XXème siècle et a commencé à
ce développer lors de la 2ème guerre mondiale.
Plusieurs modèles mathématiques traitant des problèmes:
- Optimalisation linéaire;
- ordonnancement et gestion de projets;
- Optimisation des flux;
3 M [Link] AU:2016-2017
introduction
.
B) Programmation linéaire
Ensemble de techniques d’optimisation sous des contraintes
dont l’objectif est de déterminer une solution optimale pour une
fonction objective.
Plusieurs domaines d’application:
- Gestion de la production:
-- élaboration de plan de production et de stockage.
-- Choix de techniques de production;
-- affectation de moyens de production
-- etc.
- MARKETING:
-- Détermination de politique de prix.
-- répartition des efforts de la force de vente;
-- etc.
-Finance(Choix de programmes d’investissements), en logistique(
gestion des transports); en RH( affectation de personnel)
4 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
. en PL:
Modélisation d’un problème
-Un programme linéaire contient deux parties: Une fonction objective à
maximiser ou minimiser et un ensemble de contraintes à satisfaire. C’est un
programme mathématique dont la fonction objective et les contraintes
sont des fonctions linéaires.
-La modélisation d’un problème consiste à identifier:
-- les variables du problème(les inconnus ou les variables de décision);
-- la fonction objectif à optimiser (Fonction économique);
-- Les différentes contraintes linéaires auxquelles sont soumises ces
variables.
-En pl, un problème doit être formulé sous la forme:
..Maximiser Fonction objectif: F(x1, x2, ….., xn)=
.. Sous les contraintes:
5 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
Exemple 1: .
-P1 et P2 rapportent à la vente 6dh et 4dh par unité
Quelles quantités de produits P1 et P2 doit produire l’usine
pour maximiser le bénéfice total venant de la vente des deux
produits?
6 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
.
Modélisation de l’exemple 1:
7 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
Exemple 2: .
Quelles quantités de produits A et B doit produire l’usine pour
maximiser le bénéfice total venant de la vente des deux
produits?
8 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
Modélisation de l’exemple 2:
9 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
Exemple 3: .
10 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
Modélisation de l’exemple 3:
Variables:
Objectif : Maximiser le profit apporter par la culture de tomates et de
piments.
Contraintes:
11 M [Link] AU:2016-2017
Eléments fondamentaux de la programmation
Linéaire
Modélisation de d’un PL: cas de minimisation de la fonction
objectif.
En PL, l’optimisation formulé par un cas peut exiger la minimisation de la
fonction objectif. Dans ce cas, le problème doit être formulé de la façon
suivante:
..Minimiser F(x1, x2, ….., xn)=
.. Sous les contraintes:
12 M [Link] AU:2016-2017
Méthode graphique
.
A) Régionalisation du plan
Exemple: Cas de la droite 2x+Y-4=0
13 M [Link] AU:2016-2017
Méthode graphique
.
B) Démarche de la méthode graphique
Cette méthode ne s’applique que dans le cas de deux variables de décision. Elle
repose sur les éléments suivants:
Solution réalisable: Une solution est réalisable si les valeurs
numériques associées aux variables de décision satisfont à l’ensemble des
contraintes du programme linéaire.
Région réalisable: Ensemble de solution réalisable.
La solution optimale (s’il en existe une) se trouve sur
la frontière de la région réalisable.
Quand une solution optimale existe, il existe toujours
une sur un sommet (point extrême ) de la région
réalisable.
14 M [Link] AU:2016-2017
Méthode graphique
.
C) Exemples:
Cas 1:
Maximiser Z(x1,x2)=2x1+4x2
Sachant que:
La région réalisable est donnée graphiquement par:
15 M [Link] AU:2016-2017
Méthode graphique
.
C) Exemples:
Cas 1:
(D1): x1 +3x2 -18=0; (D2): x1 + x2 -8=0; (D3): 2x1 + x2 -14=0
La région réalisable est délimitée par le polygone OABCD
16 M [Link] AU:2016-2017
Méthode graphique
.
Cas 1: Lorsque Z augmente, la droite Dz (2x1+4x2=z) se déplace parallèlement à
elle-même vers le haut:
Quand une solution optimale existe, il existe une sur un
sommet (point extrême ) de la région réalisable càd un des
sommets: O, A, B, C ou D
17 M [Link] AU:2016-2017
Méthode graphique
.
Cas 1: Lorsque Z augmente, la droite Dz (2x1+4x2=z) se déplace parallèlement à
elle-même vers le haut:
18 M [Link] AU:2016-2017
Méthode graphique
.
C) Exemples:
Cas 2: Exemple 2 précédent (Cas fabrication des yaourts A et B)
19 M [Link] AU:2016-2017
Méthode graphique
.
C) Exemples:
Cas 2: Exemple 2 précédent (Cas fabrication des yaourts A et B)
Région
réalisable
20 M [Link] AU:2016-2017
Méthode graphique
.
C) Exemples:
Cas 2: Exemple 2 précédent (Cas fabrication des yaourts A et B)
Pour maximiser le bénéfice total, l’usine doit produire 300kg
de A et 200 kg de B. Le bénéfice maximal est de 2200€
21 M [Link] AU:2016-2017
Méthode graphique
.
D) Exercices
1) Traiter le cas de l’exemple 3 (Allocation des ressources pour l’agriculture):
2) Cas de production:
22 M [Link] AU:2016-2017
Méthode simplex
.
A) Démarche de la méthode simplex
1) Ecrire le PL sous forme standard
-- Un PL est dit sous forme canonique s’il s’écrit:
Où
La mise sous forme standard consiste à introduire des variables supplémentaires
(une pour chaque contrainte) de manière à réécrire les inégalités sous la forme
d’égalités.
Chacune des variables supplémentaires représente le nombre de ressources non
utilisées. On les appel les variables d’écart.
Tout PL sous forme canonique s’écrit de façon équivalente sous forme standard et
inversement.
23 M [Link] AU:2016-2017
Méthode simplex
.
A) Démarche de la méthode simplex
1) Ecrire le PL sous forme standard
-- La forme standard d’un PL s’écrit donc:
24 M [Link] AU:2016-2017
Méthode simplex
.
A) Démarche de la méthode simplex
1) Ecrire le PL sous forme standard
-- Exemple: Soit le PL sous la forme canonique suivante:
Max F(x1, x2, x3)=2x1+ x2 + x3
--La forme standard de ce PL est:
Max F(x1, x2, x3)=2x1+ x2 + x3
S.C
--Variables de décision:
--Variables d’écart:
25 M [Link] AU:2016-2017
Méthode simplex
.
A) Démarche de la méthode simplex
2) Application de l’algorithme de simplex:
-- La méthode de simplex repose sur le théorème fondamental suivant :
--L’algorithme du simplex consiste à:
26 M [Link] AU:2016-2017
Méthode simplex
.
A) Démarche de la méthode simplex
2) Application de l’algorithme de simplex:
-- Chaque itération de l’algorithme du simplex consiste à :
Choisir la variable entrante: Celle qui a le plus grand coût marginal positif
Choisir la variable sortante: Celle qui a le minimum des
e: est le numéro de la colonne de la
variable entrante.
Déterminer le pivot: Intersection entre la ligne de la variable sortante et la colonne
de la variable entrante.
Remplacer les coefficients de la ligne du pivot par:
Remplacer les coefficients des autres lignes selon la formule:
--Condition d’arrêt: La solution est optimale si les coûts marginaux sont négatifs ou
27 nuls. Sinon on recommence une nouvelle itération M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 1:Soit le PL suivant: Maximiser
S.C
1)Introduire les variables d’écart pour avoir la forme standard suivante :
Max:
S.C
-- Solution de base:
-- Variables de Base: -- Variables hors Base:
28 M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 1:
2) Préparation du tableau initial :
bi
29 M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 1:
3) 1ère itération:
bi
Variable entrante: X1; (Celle dont le coefficient de z est Maximal)
Variable sortante: X3 (Celle dont le rapport bi sur ai1 est minimal)
Pivot=1 (Intersection de la colonne de la variable entrante avec celle de la variable sortante)
Replacer la variable entrante et diviser la ligne du pivot par le pivot
Recalculer les autres lignes selon la formule précédente
30 M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 1:
3) 1ère itération: Tableau 2
bi
Les coefficients de Z ne sont pas tous nuls ou négatifs. On passe donc à une 2ème
itération.
La variable entrante est X2 et la variable sortante est X6.
Pivot=1.
31 M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 1:
3) 2ème itération: Tableau 3
bi
Les coefficients de Z ne sont pas tous nuls ou négatifs. On passe donc à une 3ème
itération.
La variable entrante est X3 et la variable sortante est X5.
Pivot=1.
32 M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 1:
3) 3ème itération: Tableau 4
Les coefficients de Z sont tous nuls ou négatifs (Condition d’arrêt). Fin de
l’algorithme et la solution optimale est:
X1=200 et X2=300 pour que la fonction objectif Z atteint la valeur de 2900.
33 M [Link] AU:2016-2017
Méthode simplex
.
B) EXEMPLES
CAS 2: Appliquer la méthode de simplex au cas suivant:
Maximiser :
S.C
34 M [Link] AU:2016-2017
Méthode simplex
.
C) Exercices: Appliquer la méthode de simplex aux cas suivants:
1)
2)
35 M [Link] AU:2016-2017
Méthode de simplex
.
2) (suite)
36 M [Link] AU:2016-2017
dualité
.
a) Principe:
37 M [Link] AU:2016-2017
dualité
.
B) Exemple
C) Donner les Duals de PLs suivants:
38 M [Link] AU:2016-2017