Série N°5
Formulation - Résolution de PL - Analyse de sensibilité
Exercice n° 1.
On considère le programme linéaire suivant représentant un problème de mixage de trois
ressources b1, b2 et b3, d’une compagnie, pour produire 6 produits finis.
min z = 15x1 + 7x2 + 3x3 + 39x4 + 51x5 + 35x6
s.c. 5x1 + 2 x2 + x3 + 10x4 + 13x5 + 11x6 = 41 (b1)
x1+ x2 + 3x4 + 3x5 + 3x6 = 12 (b2)
4x1 + 2x2 + x3 + 9x4 +11x5 + 10x6 = 38 (b3)
x1, x2, x3, x4, x5, x6 ≥ 0
1. Les variables x1, x2 et x3 peuvent‐elles former une SBR du PL ?
5 2 1
La base B associée à xB={ x1, x2, x3} est B= 1 1 0
4 2 1
1 0 −1 3
B-1= − 1 1 1 et B-1b= 9 ≥0 donc les variables x1, x2, x3 forment une SBR
− 2 − 2 3 8
2. Si oui, la SBR est‐elle optimale ? Sinon trouver la solution optimale de P.
Pour savoir si cette SBR est optimale ou non calculons H
39 15 10 13 11
H=(1 2 3) =cH -cBB-1H avec cH = 51 ; cB = 7 et H=
3 3 3
35 3 9 11 10
Ainsi H=(7 11 0) ≥0 donc la solution courante est optimale (N.B. : il s’agit d’un
problème de minimisation).
3. Donner la solution optimale du dual de ce problème (sans résoudre le dual).
La solution optimale du dual de ce problème est y*= cBB-1
1 0 −1
y =( 15 7 3) − 1 1 1 = (2 1 1)
*
− 2 − 2 3
1/5
4. La compagnie a le choix de diminuer la quantité de l’une des ressources bi par rapport
à sa valeur actuelle. Est‐ce que c’est avantageux de le faire ? Si oui, lesquelles des
ressources est‐elle la plus prioritaire d’être diminuée ? Toutes les réponses doivent être
justifiées.
Si bi →bi- alors z*→z*-yi*, étant donné que yi* i donc il est avantageux de
diminuer les bi. La ressource la plus prioritaire à diminuer est b1 étant donné que y1*
a la plus grande valeur parmi les yi*.
Exercice n° 2.
La Société Fromagère du Nord Ouest (SOFNO) est spécialisée dans la production de deux
types de fromage : le chevron et le brebon. Ces fromages sont produits à partir de lait de
brebis, de chèvre et de vache. Les quantités nécessaires à la fabrication d’une tomme (d’un
poids moyen de 6,2 Kg), les quantités de lait disponibles par jour, ainsi que les profits
unitaires sont indiqués dans le tableau ci-dessous :
Lait de chèvre Lait de brebis Lait de vache Profit unitaire
Chevron 1 5 35 6.5
Brebon 1 15 20 11.5
Quantité disponible 120 1440 3570
1. Déterminer le programme de production qui maximise le profit.
Variables de décision :
x1 : quantité à produire de chevron
x2 : quantité à produire de brebon
Le programme de production (P) qui maximise le profit est :
Max z=6.5x1+11.5x2
s.c. x1+ x2 ≤ 120
5x1+ 15x2 ≤ 1440
35x1+ 20x2 ≤ 3570
x1, x2≥0
2. Ecrire le problème dual et déterminer la solution duale optimale à partir de celle du
primal.
Le dual de (P) s’écrit :
Min w=120y1+1440y2+3570y3
s.c. y1+ 5y2+ 35y3 ≥ 6.5
y1+ 15y2+ 20y3 ≥ 11.5
y1, y2, y3≥0
2/5
La solution du primal peut être trouvée par résolution graphique ou par la méthode de
simplexe. Solution optimale x1*=36 ; x2*=84 ; z*=1200
Solution optimale du dual à partir de celle du primal :
Utilisation du théorème des écarts complémentaires. On a x1*0 et x2*0 donc les deux
contraintes du dual sont saturées.
D’autre part, la 3ème contrainte du primal est non saturée pour x1*=36 et x2*=84 donc
y3*=0.
y1* et y2* sont la solution du système :
y1+5y2=6.5
y1+15y2=11.5
Ce qui donne y1*=4 ; y2*=1/2 y3*=0 et w*=z*=1200
3. La SOFNO a la possibilité d’acquérir des quantités supplémentaires de lait. Quel est le
prix maximal à payer pour les différents types de laits ?
Pour le lait de chèvre, le prix maximal à payer pour une litre supplémentaire est donné
par y1*=4D.
Pour le lait de brebis, le prix maximal à payer pour une litre supplémentaire est donné
par y2*=1/2D.
Pour le lait de vache, le prix maximal à payer pour une litre supplémentaire est donné
par y3*=0D.
5. Des études marketing menées par la SOFNO ont prouvé la nécessité de lancer un
nouveau fromage fabriqué essentiellement à base de lait de vache. Ce nouveau produit
sera appelé “le vacheron”. La fabrication d’une tomme de ce fromage nécessite 27
litres de lait de vache et 9 litres de lait de brebis. Son coût unitaire est estimé à 18 D.
Quel sera son prix de vente minimal ?
On pose x3 la quantité à produire de vacheron. En introduisant cette nouvelle variable,
le problème deviendra :
Max z=6.5x1+11.5x2+px3-18x3
s.c. x1+ x2 ≤ 120
5x1+ 15x2 + 9x3≤ 1440
35x1+ 20x2 +27x3≤ 3570
x1, x2, x3≥0
Il ne sera intéressant de produire cette nouvelle variété de fromage qu’à partir d’un
prix minimal à déterminer qui permettra à x3 de devenir variable de base. Ainsi :
• Si 3=c3-yA3≤0 , la base actuelle reste optimale et il n’est pas intéressant de
fabriquer le nouveau fromage.
• Si 3=c3-yA3>0, il est intéressant de fabriquer le nouveau fromage.
Déterminons le prix à partir duquel il est intéressant de fabriquer du vacheron.
3/5
0
3=p-18-(4 1/2 0) 9 =p-45/2=p-22.5
27
3>0 si p>22.5 ainsi le prix minimal de vente du vacheron est de 22.5D
Exercice n° 3.
Compte tenu des heures d’entretien, une machine est disponible 170 heures par mois. On peut
fabriquer avec cette machine l’article A1 à la cadence de 50 unités/heure, et l’article A2 à la
cadence de 80 unités/heure. Les principales données respectives aux articles A1 et A2 sont
résumés dans le tableau ci-dessous:
Coût unitaire Marge unitaire Demande/mois
A1 270 30 7000
A2 210 20 10000
1. Déterminer le programme de production de profit maximal.
Les variables de décision :
x1 : quantité à produire de l’article A1.
x2 : quantité à produire de l’article A2.
Le programme de production de profit maximal s’écrit alors :
Max 30x1+20x2
s.c. x1/50+x2/30≤ 170
x1 ≤ 7000
x2 ≤10000
x1, x2≥0
La résolution de ce problème peut se faire par la méthode graphique ou par la méthode
de simplexe. La solution optimale est :
x1*=2250 ; x2*=10000 et z*=267500
2. On peut augmenter la production en ayant recours à la sous‐traitance, le coût horaire
est 1400, est ce que l’entreprise a intérêt à augmenter sa production ?
Le dual du problème actuel s’écrit :
Min w=170y1+7000y2+10000y3
s.c. 1/50y1+y2 ≥30
1/80y1 +y3≥20
y1, y2, y3≥0
4/5
A partir de la solution du primal, on peut déterminer la solution du dual et on trouve :
y1*=1500 ; y2*=0 ; y3*=5/4
Le coût maximal à payer pour une heure de production est égal à y1*=1500.
Le coût horaire de la sous-traitance est 1400<y1*, il est donc dans l’intérêt de
l’entreprise d’augmenter sa production en ayant recours à la sous-traitance.
5/5
