Embed Size (px)
Citation preview
Plan du bloc 2
1. Présentation générale et exemples
2. Forme générale d’un PL
3. Résolution géométrique (2 variables)
4. Les différents résultats d’un PL
5. Résolution et analyse de sensibilité avec le solveur Excel
6. Programmation linéaire en nombres entiers
1. Présentation générale et exemples
• Exemple 1 : Une usine fabrique 2 produits finis P1 et P2 à l’aide de 3 matières premières M1,M2 et M3 selon le procédé suivant
M1 M2 M3Prix de vente
unitaire
P1 1 2 4 2 euros
P2 6 2 1 3 euros
Nombre d'unités disponibles
30 15 24
Question Comment organiser la production de manière à atteindre le CA le plus élevé ?
1. Présentation générale et exemples
• Modélisation de l’exemple 1– Définition des variables de décision : ce sur
quoi porte la décision• x1 : nombre d’unités de P1 à produire• x2 : nombre d’unités de P2 à produire
– Spécification des contraintes du problème• Contraintes liées à la disponibilité des MP• Contraintes de non négativité
– Spécification de la fonction objectif• Maximiser CA = 2x1+3x2
– Écriture du modèle (récap)
1. Présentation générale et exemples
• Exemple 2 : Une raffinerie produit du super SP98 (P1) et du super SP95 (P2) à partir de 3 constituants C1,C2 et C3.
Question Chercher la structure de production journalière qui maximise la marge d’exploitation de la raffinerie.
C1 C2 C3 Prix de vente par baril
P1au plus
30%au moins
40%au moins
50%18 euros
P2au plus
50%au moins
10%--- 22 euros
Nombre de barils disponibles par jour
3000 2000 1000
Prix d'achat par baril 12 euros 24 euros 20 euros
1. Présentation générale et exemples
• Modélisation de l’exemple 2– Définition des variables de décision
• Ui : Quantité journalière du constituant Ci utilisée (en baril), i=1,2,3
• Vj : Quantité journalière du carburants Pj produite (en baril), j=1,2
• Xij : Quantité journalière du constituant Ci intervenant dans le carburant Pj (en baril), i=1,2,3 et j=1,2
– Lien entre les variables de décision
1. Présentation générale et exemples
• Modélisation de l’exemple 2– Spécification des contraintes du problème
• Contraintes liées à la disponibilité des constituants• Contraintes liées au respect des proportions• Contraintes de non négativité
– Spécification de la fonction objectif
22V1+18V2 – (12U1+24U2+20U3)
CA Coût
2. Forme générale d’un PL
• Un PL peut s’écrire Max ou Min jcj xj
jaij xj ≤ bi pour i =1,…,m1
jaij xj ≥ bi pour i =m1+1,…,m1+m2
jaij xj = bi pour i =m1+m2+1,…,m1+m2+m3
xj ≥ 0 pour j =1,…, n1
xj ≤ 0 pour j =n1+1,…, n1+n2
xj s.r.s. pour j =n1+n2+1,…, n1+n2+n3
3. Résolution géométrique
• Illustration avec l’exemple 1 :
Max 2x1 + 3x2
x1 + 6x2 ≤ 30
2x1 + 2x2 ≤ 15
4x1 + x2 ≤ 24
x1,x2 ≥0
3. Résolution géométrique
a. Représentation géométrique de l’ensemble des solutions réalisables
• Chaque solution est un couple de valeurs (x1,x2). Elle est représentée par un point de IR²
• Chaque contrainte élimine un demi-plan de IR² délimité par la droite associée à la contrainte
• L’ensemble des solutions réalisables est un sous-ensemble de points EIR², appelé polyèdre des solutions réalisables
3. Résolution géométrique
a. Représentation géométrique de l’ensemble des solutions réalisables
3. Résolution géométrique
b. Résolution géométrique– Tous les points de la droite 2x1 + 3x2 = M (D)
donnent la même valeur M à la fonction objectif– On remarque qu’en déplaçant la droite (D) vers
le Nord-Est on obtient 2x1 + 3x2 = M’ (D) avec M’>M
– On continue jusqu’à ce qu’on trouve le dernier point admissible : ici c’est le point B.
3. Résolution géométrique
b. Résolution géométrique– D’une façon générale, la direction déterminée
par le gradient de la fonction objectif est une direction d’augmentation de cette fonction
– Vecteur gradient f(x1,x2) = (f/x1, f/x2)
– Si f(x1,x2)= 2x1+3x2 alors f(x1,x2) =(2,3)
3. Résolution géométrique
c. Introduction graphique à l’analyse de sensibilité
– Question 1 : Quelle modification sur les coefficients de la fonction objectif peut laisser invariant l’optimum ?
– Question 2 : Jusqu’à quelle quantité d peut on restreindre les disponibilités en matière première M3 sans changer de solution optimale
– Question 3 : On a la possibilité de disposer d’une quantité supplémentaire de M2. Est-ce intéressant ? Jusqu’à quelle quantité ?
3. Résolution géométrique
c. Introduction graphique à l’analyse de sensibilité
– Question 1 : Quelle modification sur les coefficients de la fonction objectif peut laisser invariant l’optimum ?• (D) : c1x1+c2x2• Il faut que la pente de (D) soit comprise entre celle
de (D1) et celle de (D2)
-1 ≤ -c1/c2 ≤ -1/6
3. Résolution géométrique
c. Introduction graphique à l’analyse de sensibilité
– Question 2 : Jusqu’à quelle quantité d peut on restreindre les disponibilités en M3 sans changer de solution optimale• La contrainte associée à M3 4x1+x2 ≤ d =24 n’est
pas active.• Si on diminue d, on déplace parallèlement la droite
vers l’ouest• La valeur limite est obtenue quand la droite passe
par B
3. Résolution géométrique
c. Introduction graphique à l’analyse de sensibilité
– Question 3 : On a la possibilité de disposer d’une quantité supplémentaire de M2. Est-ce intéressant ? Jusqu’à quelle quantité ?
4. Les différents résultats d’un PL
a. Cas usuel– Le PL a une solution optimale unique– Cette solution correspond à un somment du
polyèdre : ceci reste vrai même si n>2– Résultat général : Si un PL admet une ou
plusieurs solutions optimales alors une au moins de ces solutions est un sommet du polyèdre des solutions réalisable
4. Les différents résultats d’un PL
b. Plusieurs solutions optimales
Max x1 + x2
x1 + x2 ≤ 2
x1 ≤ 1
x1,x2 ≥0
– L’ensemble des solutions optimales se situe sur le segment [A,B] : ensemble infini
4. Les différents résultats d’un PL
c. Aucune solution optimale
c.1 E=videMax 2x1 + x2 x1 + x2 ≤ 2 x1 ≥ 3 x1,x2 ≥0
c.2 E non bornéMax 2x1 + x2 x1 + x2 ≥ 2 x1 ≤ 1 x1,x2 ≥0
Attention : E peut être non borné et admettre une solution optimale
5. Résolution et analyse de sensibilité avec le solveur Excel
6. Programmation linéaire en nombres entiers
