SOLUTIONNAIRE : DUAL

EXERCICES

1 Formulation du dual
(1) PROBLÈME–PPL : Maximiser z = x1 + 7x2 sujet aux contraintes
x1 + x2 ≤ 8
−2x1 + 3x2 ≤ 6
x1 − x2 ≤ 2
où x1 ≥ 0 et x2 ≥ 0.
DUAL : Le nombre de variables est déterminé par le nombre de contrainte du primal : il y
a donc 3 variables dans le modèle dual. Le nombre de contraintes dans le dual est égal au
nombre de variables dans le primal : il y a deux contraintes. DUAL : Minimiser
w = 8y1 + 6y2 + 2y3
sujet aux contraintes
y1 − 2y2 + y3 ≥ 1
y1 + 3y2 − y3 ≥ 7
avec yi ≥ 0 pour i = 1, 2, 3.
– La premième contrainte est déterminée par les coefficient de la première variable (x1 ) dans
chacune des contraintes du primal (du PPL original) sous forme standard. x1 a comme
coefficient 1 pour la première contrainte (y1 ), -2 pour la deuxième contrainte (y2 ) et 1 pour
la troisième contrainte (y3 ).
– La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x2 )
dans chacune des contraintes du primal (du PPL original) sous forme standard. x2 a
comme coefficient 1 pour la première contrainte (y1 ), 3 pour la deuxième contrainte (y2 )
et -1 pour la troisième contrainte (y3 ).
(2) PROBLÈME–PPL : Maximiser x1 − 3x2 = z sujet aux contraintes
x1 + x2 ≤ 8
−2x1 + 3x2 ≥ 6
x1 − x2 ≤ 2
où x1 ≥ 0 et x2 ≥ 0.
DUAL : Le modèle n’est pas sous forme canonique : il est plus simple de considérer la forme
canonique pour construire le dual.
 FORME CANONIQUE DU PPL : Maximiser x1 − 3x2 = z sujet aux contraintes
x1 + x2 ≤ 8
2x1 − 3x2 ≤ −6
x1 − x2 ≤ 2
où x1 ≥ 0 et x2 ≥ 0.
– Il y a 3 contraintes dans le PPL donc il y a 3 variables dans le dual
– Il y a 2 variables de décision dans le PPL donc il y a deux contraintes dans le dual.
DUAL : Minimiser
w = 8y1 − 6y2 + 2y3
sujet aux contraintes
y1 + 2y2 + y3 ≥ 1
y1 − 3y2 − y3 ≥ −3
avec y1 ≥ 0, y2 ≥ 0 et y3 ≥ 0.
– La premième contrainte est déterminée par les coefficient de la première variable (x1 ) dans
chacune des contraintes du primal (du PPL original) sous forme standard. x1 a comme
coefficient 1 pour la première contrainte (y1 ), 2 pour la deuxième contrainte (y2 ) et 1 pour
la troisième contrainte (y3 ).
– La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x2 )
dans chacune des contraintes du primal (du PPL original) sous forme standard. x2 a
comme coefficient 1 pour la première contrainte (y1 ), -3 pour la deuxième contrainte (y2 )
et -1 pour la troisième contrainte (y3 ).
(3) PROBLÈME-PPL : Maximiser z = 6x1 + 5x2 sujet aux contraintes
x1 + x2 ≤ 8
−2x1 + 3x2 ≤ 6
x1 − x2 ≤ 2
avec xi ≥ 0
Le problème est déjà sous forme canonique.
– Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual
– Il y a deux variables de décision dans le PPL donc deux contraintes dans le dual.
DUAL : Minimiser
w = 8y1 + 6y2 + 2y3
sujet aux contraintes
y1 − 2y2 + y3 ≥ 6
y1 + 3y2 − y3 ≥ 5
avec y1 ≥ 0, y2 ≥ 0 et y3 ≥ 0.
– La premième contrainte est déterminée par les coefficient de la première variable (x1 ) dans
chacune des contraintes du primal (du PPL original) sous forme standard. x1 a comme
coefficient 1 pour la première contrainte (y1 ), -2 pour la deuxième contrainte (y2 ) et 1 pour
la troisième contrainte (y3 ).
– La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x2 )
 dans chacune des contraintes du primal (du PPL original) sous forme standard. x2 a
comme coefficient 1 pour la première contrainte (y1 ), 3 pour la deuxième contrainte (y2 )
et -1 pour la troisième contrainte (y3 ).
(4) PROBLÈME–PPL : Maximiser z = 5x1 + 5x2 sujet aux contraintes
x1 + x2 ≤ 8
−2x1 + 3x2 ≥ 6
x1 − x2 ≤ 2
où x1 ≥ 0 et x2 ≥ 0.
Le modèle primal sous sa forme canonique est donné par :
Maximiser z = 5x1 + 5x2 sujet aux contraintes
x1 + x2 ≤ 8
2x1 − 3x2 ≤ −6
x1 − x2 ≤ 2
où x1 ≥ 0 et x2 ≥ 0.
– Il y a 3 variables dans le modèle dual (nombre de contraintes dans le PPL)
– Il y a deux contraintes dans le modèle dual (nombre de variables dans le PPL).
DUAL : Minimiser
w = 8y1 − 6y2 + 2y3
sujet aux contraintes
y1 + 2y2 + y3 ≥ 5
y1 − 3y2 − y3 ≥ 5
avec y1 ≥ 0, y2 ≥ 0 et y3 ≥ 0.
– La premième contrainte est déterminée par les coefficient de la première variable (x1 ) dans
chacune des contraintes du primal (du PPL original) sous forme standard. x1 a comme
coefficient 1 pour la première contrainte (y1 ), 2 pour la deuxième contrainte (y2 ) et 1 pour
la troisième contrainte (y3 ).
– La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x2 )
dans chacune des contraintes du primal (du PPL original) sous forme standard. x2 a
comme coefficient 1 pour la première contrainte (y1 ), -3 pour la deuxième contrainte (y2 )
et -1 pour la troisième contrainte (y3 ).
(5) PROBLÈME – PPL : Maximiser z = 6x1 + 5x2 sujet aux contraintes
x1 + x2 ≥ 8
−2x1 + 3x2 ≥ 6
x1 − x2 ≥ 2
où x1 ≥ 0 et x2 ≥ 0.
DUAL : La forme canonique du modèle primal est de maximiser z = 6x1 + 5x2 sujet aux
contraintes
−x1 − x2 ≤ −8
2x1 − 3x2 ≤ −6
−x1 + x2 ≤ −2
 où x1 ≥ 0 et x2 ≥ 0.
– Il y a trois variables dans le modèle dual
– Il y a deux contraintes dans le modèle dual.
DUAL : Minimiser
w = −8y1 − 6y2 − 2y3
sujet aux contraintes
−y1 + 2y2 − y3 ≥ 6
−y1 − 3y2 + y3 ≥ 5
avec yi ≥ 0, pour i = 1, 2, 3...
– La premième contrainte est déterminée par les coefficient de la première variable (x1 ) dans
chacune des contraintes du primal (du PPL original) sous forme standard. x1 a comme
coefficient -1 pour la première contrainte (y1 ), 2 pour la deuxième contrainte (y2 ) et -1
pour la troisième contrainte (y3 ).
– La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x2 )
dans chacune des contraintes du primal (du PPL original) sous forme standard. x2 a
comme coefficient -1 pour la première contrainte (y1 ), -3 pour la deuxième contrainte (y2 )
et 1 pour la troisième contrainte (y3 ).
(6) PROBLÈME : Une compagnie fabrique deux types d’acier : Acier trempé (T) et l’acier
détrempé (D). Le profit pour une tonne d’acier est de 6k$ et 4k$ pour l’acier T et
D respectivement. Il faut 2 et 3 tonnes de matières premières pour les aciers T et D
respectivement tandis que le temps de production est respectivement de 6 et 4 unités. La
compagnie dispose de 120 tonnes de matières premières et de 100 unités de temps.
PPL : Le problème de programmation linéaire sous forme canonique est de maximiser
z = 6x1 + 4x2
sujet aux contraintes
2x1 + 3x2 ≤ 120
6x1 + 4x2 ≤ 100
et xi ≥ 0 pour i = 1, 2.
– Le dual comprend 2 variables
– Le dual comprend 2 contraintes
DUAL : Minimiser
w = 120y1 + 100y2
sujet aux contraintes
2y1 + 6y2 ≥ 6
3y1 + 4y2 ≥ 4
avec y1 ≥ 0 et y2 ≥ 0.
(7) PROBLÈME : Un constructeur automobile doit livrer son modèle AA à 4 concessionnaires
à partir de trois usines de production. Les disponibilités aux usines sont respectivement de
80, 40 et 100 unités tandis que les démandes des vendeurs sont de 40, 75, 25 et 60 pour les
concessionnaires I, II, III et IV respectivement. Les coûts de livraison des automobiles, en
centaine de $, sont donnés par le tableau suivant :
Concessionnaire
I II III IV
1 4 2 6 4
Usines 2 8 6 10 8
3 6 4 8 6
On cherche à établir le plan de livraison optimal.
VARIABLES DE DÉCISION : Considérons xij les variables de décision qui donnent le
nombre de véhicules livrés de l’usine i vers le concessionnaire j. On cherche à minimiser le
coût de la livraison.
Le PPL donne comme fonction objectif à minimiser :
4x11 + 8x21 + 6x31 + 2x12 + 6x22 + 4x32 +
6x13 + 10x23 + 8x33 + 4x14 + 8x24 + 6x34
Les contraintes sont des contraintes de production et des contraintes de demande :
x11 + x12 + x13 + x14 ≤ 80
x21 + x22 + x23 + x24 ≤ 40
x31 + x32 + x33 + x34 ≤ 100
x11 + x21 + x31 ≥ 40
x12 + x22 + x32 ≥ 75
x13 + x23 + x33 ≥ 25
x14 + x24 + x34 ≥ 60
avec les contraintes de non négativité xij ≥ 0.
Le modèle sous sa forme canonique est de maximiser
z = −4x11 − 8x21 − 6x31 − 2x12 − 6x22 − 4x32 −
6x13 − 10x23 − 8x33 − 4x14 − 8x24 − 6x34
sujet à
x11 + x12 + x13 + x14 ≤ 80
x21 + x22 + x23 + x24 ≤ 40
x31 + x32 + x33 + x34 ≤ 100
−x11 − x21 − x31 ≤ −40
−x12 − x22 − x32 ≤ −75
−x13 − x23 − x33 ≤ −25
−x14 − x24 − x34 ≤ −60
– Puisqu’il y a 7 contraintes pour le PPL dans sa forme canonique, le dual a 7 variables
– Puisqu’il y a 12 variables dans le PPL sous sa forme canonique il y a 12 contraintes dans
le dual.
DUAL : Minimiser
w = 80y1 + 40y2 + 100y3 − 40y4 − 75y5 − 25y6 − 60y7
 sujet aux contraintes
y1 − y4 ≥ −4
y2 − y4 ≥ −8
y3 − y4 ≥ −6
y1 − y5 ≥ −2
y2 − y5 ≥ −6
y3 − y5 ≥ −4
y1 − y6 ≥ −6
y2 − y6 ≥ −10
y3 − y6 ≥ −8
y1 − y7 ≥ −4
y2 − y7 ≥ −8
y3 − y7 ≥ −6
avec yi ≥ 0 pour i = 1, . . . , 7.
– Pour la première contrainte du dual on s’intéresse aux coefficients de la variable x11 dans
chaque contrainte du PPL. x11 se retrouve avec un coefficient 1 dans la première contrainte
et -1 dans la quatrièmre contrainte du PPL sous forme canonique.
– On procède de la même façon pour la variable x21 ce qui donne la deuxième contrainte
du dual. Le même principe est appliqué pour toutes les variables du PPL pour donner
chacune des contraintes du dual.
(8) PROBLÈME : Une compagnie fabrique 3 modèles de jouets : voiture de police, camions de
pompiers et avions à réaction. À cet effet, elle utilise du bois et du plastique dont elle dispose
à raison de 2500 et 3500 unités respectivement.
Les quantités de matières premières en unité nécessaires à la fabrication d’un jouet sont les
suivantes : Voiture (3 bois et 5 plastique), camion (5 bois et 3 plastique), avion (7 bois et
4 plastique). Le temps de travail nécessaire pour produire un avion est le double de celui
nécessaire pour produire un camion et le triple de celui nécessaire pour produire une voiture.
La capacité de production de l’entreprise est équivalente à 600 avions. Une étude de marché
indique que la demande minimale pour chaque jouet est de 125 unités. Cependant, on doit
produire deux fois plus de voitures que d’avions. Les profits sont de 20$, 25$ et 50$ pour les
voitures, les camions et les avions respectivement. Maximiser les profits.
DUAL : Posons les variables xi le nombre de jouets du type i ou le type 1 représente la
voiture de police, le type 2 le camion de pompier et le type 3 l’avion à réaction. La fonction à
maximiser est
z = 20x1 + 25x2 + 50x3
 avec les contraintes
1
x1 + 0.5x2 + x3 ≤ 600
3
3x1 + 5x2 + 7x3 ≤ 2500
5x1 + 3x2 + 4x3 ≤ 3500
x1 − 2x3 ≥ 0
On a aussi les contraintes xi ≥ 125 pour i = 1, 2, 3.
FORME CANONIQUE : Maximiser
z = 20x1 + 25x2 + 50x3
avec les contraintes
1
x1 + 0.5x2 + x3 ≤ 600
3
3x1 + 5x2 + 7x3 ≤ 2500
5x1 + 3x2 + 4x3 ≤ 3500
−x1 + 2x3 ≤ 0
On a aussi les contraintes −xi ≤ −125
– Le dual contient 7 variables puisqu’il y a 7 contraintes dans le PPL
– Le dual contient 3 contraintes puisqu’il y a trois variables dans le PPL.
DUAL : Minimiser
w = 600y1 + 2500y2 + 3500y3 − 125y5 − 125y6 − 125y7
sujet aux contraintes :
1/3y1 + 3y2 + 5y3 − y4 − y5 ≥ 20
0.5y1 + 5y2 + 3y3 − y6 ≥ 25
y1 + 7y2 + 4y3 + 2y4 − y7 ≥ 50
sujet à yi ≥ 0 pour i = 1, 2, 3.
(9) PROBLÈME : Un laboratoire conduit des tests sur la composition des sols. Il peut traiter
jusqu’à 1200 échantillons de sol par jour. Il a un contrat avec la coopérative agricole
régionale pour le traitement quotidien de 400 échantillons. Le laboratoire traite également des
échantillons de sols de jardins privés et de parcs municipaux. Les profits réalisés sont 0,18$
par échantillon en provenance de la coopérative agricole, 0,23$ par échantillon de jardins
privés et 0,21$ par échantillon de parcs municipaux. Ce laboratoire ne dispose que de 1400
unités de temps de traitement par jour.
Les échantillons de la coopérative agricole nécessitent deux fois plus de temps que ceux des
parcs municipaux, qui eux prennent une unité de temps de traitement. Les échantillons des
jardins privés nécessitent 1,5 unité de temps de traitement. Le laboratoire doit se maintenir
dans les bonnes grâces du conseil municipal et, par conséquent, ne peut pas traiter plus
d’échantillons de jardins privés que d’échantillons de parc municipaux. Maximiser les profits.
VARIABLES DE DÉCISION : Soit les variables de décision
– x1 : nombre d’analyses pour la coopérative agricole
– x2 : nombre d’analyses pour des jardins privés
– x3 : nombre d’analyses pour les parcs municipaux.
 PPL : Maximiser
z = 0.18x1 + 0.23x2 + 0.21x3
sujet aux contraintes
x1 + x2 + x3 ≤ 1200
−x1 ≤ −400
2x1 + 1.5x2 + x3 ≤ 1400
x2 − x3 ≤ 0
avec xi ≥ 0.
FORME CANONIQUE : Le problème est sous forme canonique.
DUAL :
– Le dual a 4 variables puisque le PPL sous forme canonique a 4 contraintes
– Le dual a 3 contraintes puisque le PPL sous forme canonique a 3 variables.
DUAL : Minimiser
w = 1200y1 − 400y2 + 1400y3
sujet aux contraintes
y1 − y2 + 2y3 ≥ 0.18
y1 + 1.5y3 + y4 ≥ 0.23
y1 + y3 − y4 ≥ 0.21
avec yi ≥ 0.
– La première contrainte du dual est donnée par les coefficients de la variable x1 à chaque
contrtainte (1,1,2,0).
– Pour la deuxième contrainte c’est le même principe mais pour la variable x2 du PPL. C’est
la même chose pour les autres contraintes.
(10)PROBLÈME : Une compagnie construit des circuits électriques qui nécessitent plusieurs
composantes et plusieurs étapes de fabrication ou de test. Le tableau suivant résume les
données relatives à la production de 7 circuits différents :
Circuit fab fini cont conc cap obj prix ext. coût int.
1 5 1 1 3 3 20 150 70
2 2 1 0 1 5 17 175 60
3 1 4 2 3 1 30 180 80
4 3 0 3 2 1 20 105 55
5 1 5 2 2 2 10 220 90
6 0 2 2 3 2 11 205 100
7 2 1 1 1 4 8 120 60
Disponibilité 105 145 130 240 200
Cela veut dire qu’il y a 105 unités de temps disponible pour la fabrication et que le circuit 1
demande 5 unités. On a aussi 145 unités de temps disponibles pour la finition et le circuit 3,
par exemple, en demande 4.
Il faut produire 20 circuits de type 1 au minimum (colonne "objectif") et le prix de cette
composante achetée à l’externe est de 150$ tandis que le coût de fabrication est de 70$.
L’objectif est de déterminer les composantes à fabriquer à l’interne dans le but de minimiser
les coûts.
– Le problème est un peu plus complexe dans un cas de PPL défini avec les variables de
décision à deux indices du type xij .
VARIABLES DE DÉCISION : Posons xij le nombre de circuits de type i qui seront fabriqués
en usine si j = 1 et en sous-traitance si j = 2.
PPL : MINIMISER :
z = 70x11 + 150x12 + 60x21 + 175x22 + 80x31 + 180x32
+55x41 + 105x42 + 90x51 + 220x52 + 100x61 + 205x62
+60x71 + 120x72
sujet aux contraintes
5x11 + 2x21 + x31 + 3x41 + x51 + 2x71 ≤ 105
x11 + x21 + 4x31 + 5x51 + 2x61 + x71 ≤ 145
x11 + 2x31 + 3x41 + 2x51 + 2x61 + x71 ≤ 130
3x11 + x21 + 3x31 + 2x41 + 2x51 + 3x61 + x71 ≤ 240
3x11 + 5x21 + x31 + x41 + 2x51 + 2x61 + 4x71 ≤ 200
x11 + x12 ≥ 20
x21 + x22 ≥ 17
x31 + x32 ≥ 30
x41 + x42 ≥ 20
x51 + x52 ≥ 10
x61 + x62 ≥ 11
x71 + x72 ≥ 8
FORME CANONIQUE : Maximiser
−70x11 − 150x12 − 60x21 − 175x22 − 80x31 − 180x32
−55x41 − 105x42 − 90x51 − 220x52 − 100x61 − 205x62
−60x71 − 120x72
sujet aux contraintes
5x11 + 2x21 + x31 + 3x41 + x51 + 2x71 ≤ 105
x11 + x21 + 4x31 + 5x51 + 2x61 + x71 ≤ 145
x11 + 2x31 + 3x41 + 2x51 + 2x61 + x71 ≤ 130
3x11 + x21 + 3x31 + 2x41 + 2x51 + 3x61 + x71 ≤ 240
3x11 + 5x21 + x31 + x41 + 2x51 + 2x61 + 4x71 ≤ 200
−x11 − x12 ≤ −20
−x21 − x22 ≤ −17
−x31 − x32 ≤ −30
−x41 − x42 ≤ −20
−x51 − x52 ≤ −10
−x61 − x62 ≤ −11
−x71 − x72 ≤ −8
DUAL :
– Il y a 16 variables dans le problème initial (ou primal) donc 16 contraintes dans le modèle
dual
– Il y a 12 contraintes dans le modèle primale donc 12 variables dans le modèle dual, une
pour chaque contrainte.
Le dual est de minimiser
w = 105y1 + 145y2 + 130y3 + 240y4 + 200y5 − 20y6
−17y7 − 30y8 − 20y9 − 10y10 − 11y11 − 8y8
sujet aux contraintes
5y1 + y2 + y3 + 3y4 + 3y5 − y6 ≥ −70
−y6 ≥ −150
2y1 + y2 + y4 + 5y5 − y7 ≥ −60
−y7 ≥ −175
y1 + 4y2 + 2y3 + 3y4 + y5 − y8 ≥ −80
−y8 ≥ −180
3y1 + 3y3 + 2y4 + y5 − y9 ≥ −55
−y9 ≥ −105
y1 + 5y2 + 2y3 + 2y4 + 2y5 − y10 ≥ −90
−y10 ≥ −220
2y2 + 2y3 + 3y4 + 2y5 − y11 ≥ −100
−y11 ≥ −205
2y1 + y2 + y3 + 4y4 − y12 ≥ −60
−y12 ≥ −120
avec yi ≥ 0 .
 La solution de EXCEL donne les valeurs pour chaque variables dans la section "rapport de
sensibilité" : sensibilité"
Finale Réduit Objectif Admissible Admissible
Cellule Nom Valeur Coût Coefficient Augmentation Réduction
$B$25 Interne type 1 0 24,16666667 70 1E+30 24,16666667
$C$25 Interne type 2 17 0 60 60,83333333 114,1666667
$D$25 Interne type 3 24,5 0 80 83,33333333 23,33333333
$E$25 Interne type 4 10,16666667 0 55 15,26315789 10
$F$25 Interne type 5 0 250,8333333 220 1E+30 250,8333333
$G$25 Interne type 6 11 0 100 63,33333333 141,6666667
$H$25 Interne type 7 8 0 60 5,833333333 114,1666667
$B$26 Externe type 1 20 0 150 24,16666667 150
$C$26 Externe type 2 0 60,83333333 175 1E+30 60,83333333
$D$26 Externe type 3 5,5 0 180 23,33333333 83,33333333
$E$26 Externe type 4 9,833333333 0 105 10 15,26315789
$F$26 Externe type 5 10 0 90 250,8333333 90
$G$26 Externe type 6 0 63,33333333 205 1E+30 63,33333333
$H$26 Externe type 7 0 5,833333333 120 1E+30 5,833333333

Contraintes
Finale Ombre Contrainte Admissible Admissible
Cellule Nom Valeur Coût à droite Augmentation Réduction
$C$28 Contraintes Disp Fab 105 -16,66666667 105 20,5 30,5
$D$28 Contraintes Disp Fini 145 -20,83333333 145 22 98
$E$28 Contraintes Disp Cont 109,5 0 130 1E+30 20,5
$F$28 Contraintes Disp Conc 151,8333333 0 240 1E+30 88,16666667
$G$28 Contraintes Disp Cap 173,6666667 0 200 1E+30 26,33333333
$J$28 Contraintes Tot 3 30 180 30 1E+30 5,5
$L$28 Contraintes Tot 5 10 90 10 1E+30 10
$I$28 Contraintes Tot 2 17 114,1666667 17 6,32 9,111111111
$H$28 Contraintes Tot 1 20 150 20 1E+30 20
$M$28 Contraintes Tot 6 11 141,6666667 11 13,66666667 11
$N$28 Contraintes Tot 7 8 114,1666667 8 8,315789474 8
$K$28 Contraintes Tot 4 20 105 20 1E+30 9,833333333

La solution du dual est donc (-16.67,-20.83,0,0,0,180,90,114.17,150,141.67,114.17,105). Or

les premières variables sont négatives pour excel bien que notre modélisation du dual donne
des valeurs strictement positives pour les variables de décision yi . Cela provient du fait que
Excel dans son algorithme du simplexe utilise une construction du dual directe sans passer par
la forme canonique. Il ne faut donc pas s’inquièter des solutions du dual de Excel qui donne
des valeurs négatives.
L’augmentation de 20 unités à l’usine pour la fabrication est possible puisqu’une augmentation
possible de 20, 5 est admissible tout en restant dans le domaine des solutions réalisables.
L’impact sur la fonction à optimiser sera de 20 ∗ −16.67 = −333. 4 tandis qu’une
augmentation de 22 unités dans la section "finition" donne une réduction des coûts de
22 ∗ −20.83 = −458. 26. Ce qui est nettement mieux.
On ne peut déterminer l’effet d’une augmentation des unités de fabrication ET d’une
augmentation des unités de finition en même temps.
Il faut alors refaire le problème puisque la lecture du tableau de sensibilité n’est valide que si
on regarde un changement dans une variable à la fois.
(11)PROBLÈME : Un constructeur automobile doit livrer son modèle AA à 4 concessionnaires
à partir de trois usines de production. Les disponibilités aux usines sont respectivement de
80, 40 et 100 unités tandis que les démandes des vendeurs sont de 40, 75, 25 et 60 pour les
concessionnaires I, II, III et IV respectivement. Les coûts de livraison des automobiles, en
centaine de $, sont donnés par le tableau suivant :
Concessionnaire
I II III IV
1 4 2 6 4
Usines 2 8 6 10 8
3 6 4 8 6
On cherche à établir le plan de livraison optimal.
a) Déterminer la solution optimale pour le problème dual.
b) Donner l’effet d’une augmentation de 50 unités à l’usine 2.
c) Si le garage II n’a que 70 véhicules quelle est l’effet sur le plan de livraison ?
d) Si tous les garages demandent 10 automobiles de plus, quel sera l’effet sur la solution
optimale ?
Faire une analyse de sensibilité pour la capacité de fabrication des usines.
VARIABLES DE DÉCISION : xij le nombre d’automobiles envoyées de l’usine i vers le
concessionnaire j.
PPL : Minimiser
4x11 + 2x12 + 6x13 + 4x14 +
8x21 + 6x22 + 10x23 + 8x24 +
6x31 + 4x32 + 8x33 + 6x34
sujet aux contraintes
x11 + x12 + x13 + x14 ≤ 80
x21 + x22 + x23 + x24 ≤ 40
x31 + x32 + x33 + x34 ≤ 100
x11 + x21 + x31 ≥ 40
x12 + x22 + x32 ≥ 75
x13 + x23 + x33 ≥ 25
x14 + x24 + x34 ≥ 60
et xij ≥ 0.
FORME CANONIQUE : Maximiser
−4x11 − 2x12 − 6x13 − 4x14 −
8x21 − 6x22 − 10x23 − 8x24 −
6x31 − 4x32 − 8x33 − 6x34
sujet aux contraintes
x11 + x12 + x13 + x14 ≤ 80
x21 + x22 + x23 + x24 ≤ 40
x31 + x32 + x33 + x34 ≤ 100
−x11 − x21 − x31 ≤ −40
−x12 − x22 − x32 ≤ −75
−x13 − x23 − x33 ≤ −25
−x14 − x24 − x34 ≤ −60
DUAL : Minimiser
80y1 + 40y2 + 100y3 − 40y4 − 75y5 − 25y6 − 60y7
sujet à
y1 − y4 ≥ −4
y1 − y5 ≥ −2
y1 − y6 ≥ −6
y1 − y7 ≥ −4
y2 − y4 ≥ −8
y2 − y5 ≥ −6
y2 − y6 ≥ −10
y2 − y7 ≥ −8
y3 − y4 ≥ −6
y3 − y5 ≥ −4
y3 − y6 ≥ −8
y3 − y7 ≥ −6
et yi ≥ 0.
 SOLUTION PAR LE SOLVEUR EXCEL (SIMPLEXE) :
Cellules variables
Finale Réduit Objectif Admissible Admissible
Cellule Nom Valeur Coût Coefficient Augmentation Réduction
$C$35 USINE 1 => CONC 1 20 0 4 0 0
$D$35 USINE 1 => CONC 2 0 0 2 1E+30 0
$E$35 USINE 1 => CONC 3 0 0 6 1E+30 0
$F$35 USINE 1 => CONC 4 60 0 4 0 8
$C$36 USINE 2 => CONC 1 20 0 8 0 0
$D$36 USINE 2 => CONC 2 0 0 6 1E+30 0
$E$36 USINE 2 => CONC 3 9,23691E-10 0 10 0 0
$F$36 USINE 2 => CONC 4 0 0 8 1E+30 0
$C$37 USINE 3 => CONC 1 0 0 6 1E+30 0
$D$37 USINE 3 => CONC 2 75 0 4 0 6
$E$37 USINE 3 => CONC 3 25 0 8 0 0
$F$37 USINE 3 => CONC 4 0 0 6 1E+30 0

Contraintes
Finale Ombre Contrainte Admissible Admissible
Cellule Nom Valeur Coût à droite Augmentation Réduction
$C$47 CONTRAINTE DISP U1 80 -4 80 20 20
$D$47 CONTRAINTE DISP U2 20 0 40 1E+30 20
$I$47 CONTRAINTE DEMANDE 4 60 8 60 20 20
$F$47 CONTRAINTE DEMANDE 1 40 8 40 20 20
$G$47 CONTRAINTE DEMANDE 2 75 6 75 20 0
$H$47 CONTRAINTE DEMANDE 3 25 10 25 20 0
$E$47 CONTRAINTE DISP U3 100 -2 100 0 20

Solution optimale du dual (-4,0,8,8,6,10,-2). On peut augmenter la disponibilité de l’usine 2

jusqu’à l’infini (1 × 1030 ) mais comme la solution optimale du dual est 0 pour la variable y2
associée alors cela n’a aucun effet sur la fonction objectif.
Si le garage 2 ne veut que 70 véhicule cela veut dire que la demande est réduite de 5 mais
pour le plan de livraison cela n’est pas admissible pour rester dans le cadre d’une solution
optimale.
On ne peut dire l’effet d’une augmentation de 10 pour tous les garages selon la sortie du
solveur mais on peut déduire qu’il y aura une demande de 230 automobiles et que les usines
ne peuvent en fournir que 220 ce qui est impossible.
(12)PROBLÈME : Un laboratoire conduit des tests sur la composition des sols. Il peut traiter
jusqu’à 1200 échantillons de sol par jour. Il a un contrat avec la coopérative agricole
régionale pour le traitement quotidien de 400 échantillons. Le laboratoire traite également des
échantillons de sols de jardins privés et de parcs municipaux. Les profits réalisés sont 0,18$
par échantillon en provenance de la coopérative agricole, 0,23$ par échantillon de jardins
privés et 0,21$ par échantillon de parcs municipaux. Ce laboratoire ne dispose que de 1400
unités de temps de traitement par jour. Les échantillons de la coopérative agricole nécessitent
deux fois plus de temps que ceux des parcs municipaux, qui eux prennent une unité de
temps de traitement. Les échantillons des jardins privés nécessitent 1,5 unité de temps de
traitement. Le laboratoire doit se maintenir dans les bonnes grâces du conseil municipal et,
par conséquent, ne peut pas traiter plus d’échantillons de jardins privés que d’échantillons de
parcs municipaux. On veut maximiser les profits.
Devrait-on modifier le contrat avec la coopérative agricole ?
SOLUTION PAR LE SOLVEUR :
Cellules variables
Finale Réduit Objectif Admissible Admissible
Cellule Nom Valeur Coût Coefficient Augmentation Réduction
$B$8 Coopérative 400 0 0,18 0,24 1E+30
$C$8 Jardins 0 -0,085 0,23 0,085 1E+30
$D$8 Parcs 600 0 0,21 1E+30 0,056666667

Contraintes
Finale Ombre Contrainte Admissible Admissible
Cellule Nom Valeur Coût à droite Augmentation Réduction
$B$14 Capacité 1000 0 1200 1E+30 200
$C$14 Coopérative 400 -0,24 400 300 200
$D$14 Temps 1400 0,21 1400 200 600
$E$14 Rapport -600 0 0 1E+30 600

Il est possible de modifier le contrat en acceptant de faire 200 analyses de moins pour la
coopérative et ainsi gagner 200 ∗ 0.25 = 50.0$ de plus.