TDN°3 : Correction

Maroua SBITI, Achraf TOUIL, Fouad RIANE

Exercice 1 :
(a) Dual du premier programme :
min w = 10y1 + 7y2 + 8y3
s.c.
y1 + 3y2 + y3 = 3
2y1 − y2 ≥ 1
−y2 + 3y3 ≥ −2
y1 ≤ 0, y2 libre, y3 ≤ 0
(b) Dual du deuxième programme :
min w = 12y1 + 8y2 + 6y3
s.c.
y1 + y2 ≥ 10
y1 + y3 ≥ 14
y1 , y2 ≤ 0, y3 ≥ 0
(c) Dual du troisième programme :
min w = 120y1 + 160y2 + 100y3
s.c.
2y1 + 4y2 + 3y3 = 400
−3y1 + 3y2 − 2y3 ≥ 350
2y1 + 4y3 = 450
y1 ≥ 0, y2 libre, y3 ≤ 0

Exercice 2 :
1 Question 1 : Formulation du programme linéaire
La société JET produit deux types de peintures A et B, à partir de trois matières
premières M1, M2 et M3.

1
 Données :
ˆ Peinture A : 10 Kg de M1, 2 Kg de M2, 1 Kg de M3, prix de vente 1200
Dhs

ˆ Peinture B : 5 Kg de M1, 3 Kg de M2, prix de vente 1000 Dhs

ˆ Disponibilités : 200 Kg de M1, 60 Kg de M2, 34 Kg de M3

Définissons les variables de décision :

ˆ x1 : nombre d’unités de peinture A à produire

ˆ x2 : nombre d’unités de peinture B à produire

1.1 Fonction objectif

L’objectif est de maximiser le bénéfice total :
Maximiser : Z = 1200x1 + 1000x2

1.2 Contraintes
1. Contrainte pour M1 : 10x1 + 5x2 ≤ 200
2. Contrainte pour M2 : 2x1 + 3x2 ≤ 60
3. Contrainte pour M3 : x1 ≤ 34
4. Contraintes de non-négativité : x1 ≥ 0, x2 ≥ 0

1.3 Programme linéaire complet

Le programme linéaire complet s’écrit donc :
Maximiser : Z = 1200x1 + 1000x2
Sous les contraintes :

10x1 + 5x2 ≤ 200 (M1)

2x1 + 3x2 ≤ 60 (M2)
x1 ≤ 34 (M3)
x1 , x2 ≥ 0

2 Question 2 : Résolution par la méthode du

simplexe
2.1 Mise sous forme standard
Nous introduisons des variables d’écart s1 , s2 , s3 pour transformer les inégalités
en égalités :

2
 10x1 + 5x2 + s1 = 200
2x1 + 3x2 + s2 = 60
x1 + s3 = 34
x1 , x2 , s1 , s2 , s3 ≥ 0

2.2 Tableau initial du simplexe

Base x1 x2 s1 s2 s3 RHS
s1 10 5 1 0 0 200
s2 2 3 0 1 0 60
s3 1 0 0 0 1 34
Zj 0 0 0 0 0 0
Cj − Zj 1200 1000 0 0 0

2.3 Première itération

Variable entrante : x1 (coefficient le plus élevé dans la ligne Cj − Zj )
Ratios :

s1 : 200/10 = 20
s2 : 60/2 = 30
s3 : 34/1 = 34

Variable sortante : s1 (ratio minimum)

Pivot : 10
Nouvelle ligne pour x1 : Ancienne ligne s1 divisée par 10

Base x1 x2 s1 s2 s3 RHS
x1 1 0.5 0.1 0 0 20
s2 0 2 -0.2 1 0 20
s3 0 -0.5 -0.1 0 1 14
Zj 1200 600 120 0 0 24000
Cj − Zj 0 400 -120 0 0

2.4 Deuxième itération

Variable entrante : x2 (coefficient positif restant dans la ligne Cj − Zj )

3
 Ratios :

x1 : 20/0.5 = 40
s2 : 20/2 = 10
s3 : 14/(−0.5) = −28 (ignoré car négatif)

Variable sortante : s2 (ratio minimum positif)

Pivot : 2
Nouvelle ligne pour x2 : Ancienne ligne s2 divisée par 2

Base x1 x2 s1 s2 s3 RHS
x1 1 0 0.2 -0.25 0 15
x2 0 1 -0.1 0.5 0 10
s3 0 0 -0.15 0.25 1 19
Zj 1200 1000 80 200 0 28000
C j − Zj 0 0 -80 -200 0

2.5 Vérification de l’optimalité

Tous les coefficients dans la ligne Cj − Zj sont non positifs, donc la solution est
optimale.

2.6 Solution optimale

x1 = 15 unités de peinture A
x2 = 10 unités de peinture B
Z = 28000 Dhs de profit

2.7 Vérification des contraintes

M1: 10(15) + 5(10) = 200 ≤ 200

M2: 2(15) + 3(10) = 60 ≤ 60
M3: 15 ≤ 34

Toutes les contraintes sont satisfaites.

2.8 Interprétation
La société JET devrait produire 15 unités de peinture A et 10 unités de peinture
B pour maximiser son bénéfice à 28000 Dhs. Les matières premières M1 et M2
sont entièrement utilisées, tandis qu’il reste 19 kg de M3 non utilisés.

4
3 Question 3 : Programme dual et sa solution
3.1 Rappel du programme primal
Le programme primal était :
Maximiser : Z = 1200x1 + 1000x2
Sous les contraintes :

10x1 + 5x2 ≤ 200 (M1)

2x1 + 3x2 ≤ 60 (M2)
x1 ≤ 34 (M3)
x1 , x2 ≥ 0

3.2 Formulation du programme dual

Pour formuler le programme dual, nous suivons ces règles :
1. Le problème de maximisation devient un problème de minimisation. 2.
Les inégalités sont inversées. 3. Les coefficients de la fonction objectif du primal
deviennent les termes de droite des contraintes du dual. 4. Les termes de droite
des contraintes du primal deviennent les coefficients de la fonction objectif du
dual. 5. La matrice des coefficients des contraintes est transposée.
Introduisons les variables duales y1 , y2 , et y3 correspondant respectivement
aux contraintes M1, M2, et M3 du problème primal.
Le programme dual s’écrit donc :
Minimiser : W = 200y1 + 60y2 + 34y3
Sous les contraintes :

10y1 + 2y2 + y3 ≥ 1200 (correspondant à x1 )

5y1 + 3y2 ≥ 1000 (correspondant à x2 )
y1 , y2 , y3 ≥ 0

3.3 Interprétation économique du dual

Les variables duales y1 , y2 , et y3 peuvent être interprétées comme les valeurs
marginales (ou prix implicites) des ressources M1, M2, et M3 respectivement.
- y1 : valeur d’un kg supplémentaire de M1 - y2 : valeur d’un kg supplémentaire
de M2 - y3 : valeur d’un kg supplémentaire de M3
La fonction objectif du dual représente la valeur totale des ressources disponibles.

3.4 Solution du problème dual

D’après le théorème de la dualité, la solution optimale du problème dual peut
être directement déduite du tableau final du simplexe du problème primal. Les
valeurs des variables duales correspondent aux coefficients des variables d’écart
dans la ligne Zj du tableau final du simplexe.
Rappelons le tableau final du simplexe du primal :

5
 Base x1 x2 s1 s2 s3 RHS
x1 1 0 0.2 -0.25 0 15
x2 0 1 -0.1 0.5 0 10
s3 0 0 -0.15 0.25 1 19
Zj 1200 1000 80 200 0 28000
C j − Zj 0 0 -80 -200 0

La solution du dual est donc :

y1 = 80 Dhs/kg (valeur marginale de M1)

y2 = 200 Dhs/kg (valeur marginale de M2)
y3 = 0 Dhs/kg (valeur marginale de M3)

3.5 Vérification de la solution duale

Vérifions que cette solution satisfait les contraintes du dual :
1. 10y1 + 2y2 + y3 ≥ 1200 : 10(80) + 2(200) + 0 = 1200 ≥ 1200 (satisfaite)
2. 5y1 + 3y2 ≥ 1000 : 5(80) + 3(200) = 1000 ≥ 1000 (satisfaite)
3. y1 , y2 , y3 ≥ 0 : 80 ≥ 0, 200 ≥ 0, 0 ≥ 0 (satisfaite)
Toutes les contraintes du dual sont satisfaites.

3.6 Valeur de la fonction objectif duale

W = 200y1 + 60y2 + 34y3 = 200(80) + 60(200) + 34(0) = 28000 Dhs
Cette valeur est égale à la valeur optimale de la fonction objectif du primal,
ce qui confirme le théorème de la dualité forte.

3.7 Interprétation économique des résultats

1. La valeur marginale de M1 est de 80 Dhs/kg. Cela signifie qu’une augmen-
tation d’un kg de M1 augmenterait le profit de 80 Dhs.
2. La valeur marginale de M2 est de 200 Dhs/kg. Une augmentation d’un
kg de M2 augmenterait le profit de 200 Dhs.
3. La valeur marginale de M3 est de 0 Dhs/kg. Cela indique que M3 n’est pas
une ressource limitante, et qu’une augmentation de sa disponibilité n’affecterait
pas le profit.
Ces valeurs marginales peuvent guider les décisions d’approvisionnement et
d’allocation des ressources de l’entreprise.

4 Question 4 : Analyse de sensibilité pour le

prix de vente de la peinture type B
Rappelons d’abord le tableau final du simplexe et la solution optimale :

6
 Base x1 x2 s1 s2 s3 RHS
x1 1 0 0.2 -0.25 0 15
x2 0 1 -0.1 0.5 0 10
s3 0 0 -0.15 0.25 1 19
Zj 1200 1000 80 200 0 28000
C j − Zj 0 0 -80 -200 0

Solution optimale : x1 = 15, x2 = 10, Z = 28000 Dhs

4.1 Analyse de sensibilité

L’analyse de sensibilité pour le prix de vente de la peinture B consiste à déterminer
dans quelle mesure ce prix peut varier sans modifier la structure de la solution
optimale actuelle.
Soit ∆ la variation du prix de vente de la peinture B. Le nouveau prix sera
donc 1000 + ∆.

4.2 Modification du tableau final

Avec cette variation, la ligne Zj du tableau final devient :

Zj = 1200x1 + (1000 + ∆)x2

= 1200 · 15 + (1000 + ∆) · 10
= 18000 + 10000 + 10∆
= 28000 + 10∆

La nouvelle ligne Cj − Zj sera :

C1 − Z1 = 1200 − 1200 = 0
C2 − Z2 = (1000 + ∆) − (1000 + ∆) = 0
C3 − Z3 = 0 − (80 − 0.1∆) = −80 + 0.1∆
C4 − Z4 = 0 − (200 + 0.5∆) = −200 − 0.5∆
C5 − Z5 = 0 − 0 = 0

4.3 Conditions d’optimalité

Pour que la solution reste optimale, tous les coefficients de la ligne Cj − Zj
doivent rester non positifs. Cela nous donne deux conditions :
1. −80 + 0.1∆ ≤ 0 2. −200 − 0.5∆ ≤ 0

7
4.4 Résolution des inéquations
De la première inéquation :

−80 + 0.1∆ ≤ 0
0.1∆ ≤ 80
∆ ≤ 800

De la deuxième inéquation :

−200 − 0.5∆ ≤ 0
−0.5∆ ≤ 200
∆ ≥ −400

4.5 Intervalle de variation

En combinant ces deux conditions, nous obtenons l’intervalle de variation pour
∆:

−400 ≤ ∆ ≤ 800
Cela signifie que le prix de vente de la peinture B peut varier de -400 Dhs à
+800 Dhs sans modifier la structure de la solution optimale actuelle.

4.6 Interprétation des résultats

1. Limite inférieure : Le prix de vente de la peinture B peut diminuer jusqu’à
1000 - 400 = 600 Dhs sans changer la structure de la solution optimale.
2. Limite supérieure : Le prix de vente de la peinture B peut augmenter
jusqu’à 1000 + 800 = 1800 Dhs sans changer la structure de la solution optimale.
3. Intervalle de stabilité : [600 Dhs, 1800 Dhs]

4.7 Conclusion
L’analyse de sensibilité révèle que la solution optimale est relativement robuste
par rapport au prix de vente de la peinture B. Elle reste structurellement la
même même si ce prix varie considérablement (de 600 Dhs à 1800 Dhs).
Si le prix sort de cet intervalle : - En dessous de 600 Dhs : la production de
peinture B pourrait devenir moins attractive, potentiellement conduisant à une
réduction ou à l’arrêt de sa production. - Au-dessus de 1800 Dhs : la production
de peinture B pourrait devenir tellement attractive qu’elle pourrait conduire à
une réallocation majeure des ressources, potentiellement au détriment de la
production de peinture A.
Cette information est précieuse pour la prise de décision stratégique, notam-
ment en matière de tarification et de planification de la production. Elle indique
que l’entreprise a une marge de manœuvre considérable pour ajuster le prix de
la peinture B sans nécessiter une refonte complète de son plan de production.

8
5 Question 5 : Prix minimum pour vendre 50%
de M1
5.1 Énoncé du problème
Une entreprise concurrente demande à la société JET de lui vendre 50% de la
matière M1 (avant que la fabrication ne soit lancée). À quel prix minimum la
société JET devra-t-elle vendre cette quantité ?

5.2 Données pertinentes

Rappelons les informations clés :
ˆ La société dispose initialement de 200 kg de M1.

ˆ 50% de M1 représente donc 100 kg.

ˆ D’après la solution du problème dual (question 3), la valeur marginale de

M1 est de 80 Dhs/kg.

5.3 Raisonnement
Pour déterminer le prix minimum, nous devons considérer le concept de coût
d’opportunité :
1. Le coût d’opportunité représente le bénéfice auquel JET renonce en ven-
dant M1 plutôt qu’en l’utilisant pour sa propre production.
2. La valeur marginale de M1 (80 Dhs/kg) nous indique exactement ce
coût d’opportunité. Elle représente l’augmentation du profit que JET pourrait
obtenir pour chaque kilogramme supplémentaire de M1.
3. En vendant M1 à un prix inférieur à sa valeur marginale, JET réaliserait
moins de profit qu’en l’utilisant pour sa propre production.
4. Donc, le prix minimum de vente doit être égal à la valeur marginale de
M1.

5.4 Calcul du prix minimum

Prix minimum = Quantité à vendre × Valeur marginale de M1

P rixminimum = 100 kg × 80 Dhs/kg = 8000 Dhs

5.5 Vérification du raisonnement

1. Si JET vend à moins de 8000 Dhs :
ˆ JET gagnerait moins que ce qu’elle aurait gagné en utilisant M1 pour sa
propre production.
ˆ Ce ne serait pas économiquement avantageux.

9
 2. Si JET vend à plus de 8000 Dhs :
ˆ JET gagnerait plus que ce qu’elle aurait gagné en utilisant M1 pour sa
propre production.
ˆ Ce serait avantageux, mais ce n’est pas le prix minimum demandé.
3. En vendant à exactement 8000 Dhs :
ˆ JET est indifférente entre vendre M1 ou l’utiliser pour sa propre produc-
tion.
ˆ C’est donc le prix minimum acceptable.

5.6 Interprétation économique

1. La valeur marginale de 80 Dhs/kg pour M1 signifie que chaque kilogramme
de M1 contribue à 80 Dhs de bénéfice dans le plan de production optimal.
2. En vendant 100 kg de M1 pour 8000 Dhs, JET compense exactement la
perte de profit qu’elle aurait subie en ne pouvant pas utiliser ces 100 kg dans sa
production.
3. Ce prix minimum garantit que JET ne perd pas d’opportunité de profit
en vendant M1 plutôt qu’en l’utilisant.

5.7 Conclusion
La société JET devrait vendre 50% de la matière M1 (soit 100 kg) à un prix
minimum de 8000 Dhs à l’entreprise concurrente.
Ce prix :
ˆ Compense exactement le coût d’opportunité de ne pas utiliser M1 dans la
production.
ˆ Maintient le niveau de profit de JET, que la société vende M1 ou l’utilise
pour sa propre production.
ˆ Représente le seuil de rentabilité pour cette transaction.
Toute vente au-dessus de ce prix minimum générerait un profit supplémentaire
pour JET par rapport à son plan de production optimal actuel.

6 Question 6 : Décision concernant la produc-

tion du type C
6.1 Énoncé du problème
Un troisième type de peinture C est proposé par le département de production.
Il nécessite 2 kg de M1 et 3 kg de M2, et son prix de vente est de 650 Dhs.
En tenant compte de la valeur marginale de M1 et M2, la société JET doit-elle
produire ce type ?

10
6.2 Données pertinentes
Rappelons les informations clés :
ˆ Peinture C : 2 kg de M1, 3 kg de M2
ˆ Prix de vente de C : 650 Dhs
ˆ Valeur marginale de M1 : 80 Dhs/kg (d’après la solution duale)
ˆ Valeur marginale de M2 : 200 Dhs/kg (d’après la solution duale)

6.3 Raisonnement
Pour décider si la production de la peinture C est rentable, nous devons comparer
son prix de vente à son coût marginal :
1. Le coût marginal représente le coût d’opportunité d’utiliser les ressources
pour produire C plutôt que A ou B.
2. Ce coût est calculé en utilisant les valeurs marginales de M1 et M2,
qui représentent la contribution au profit de chaque kg de ces matières dans la
solution optimale actuelle.
3. Si le prix de vente de C est supérieur à son coût marginal, alors sa
production générera un profit supplémentaire.
4. Si le prix de vente de C est inférieur à son coût marginal, alors sa pro-
duction réduira le profit global.

6.4 Calcul du coût marginal de C

Coût marginal de C = (Quantité de M1 × Valeur marginale de M1) + (Quantité
de M2 × Valeur marginale de M2)
Coût marginal = (2 kg × 80 Dhs/kg) + (3 kg × 200 Dhs/kg) = 160 + 600 =
760 Dhs

6.5 Comparaison avec le prix de vente

ˆ Prix de vente de C : 650 Dhs
ˆ Coût marginal de C : 760 Dhs
ˆ Différence : 650 - 760 = -110 Dhs

6.6 Analyse de la rentabilité

Puisque le prix de vente (650 Dhs) est inférieur au coût marginal (760 Dhs), la
production de la peinture C générerait une perte de 110 Dhs par unité produite.

6.7 Décision
La société JET ne devrait pas produire la peinture de type C car elle n’est pas
rentable dans les conditions actuelles.

11
6.8 Interprétation économique
1. La production de C utiliserait des ressources (M1 et M2) qui sont actuelle-
ment employées de manière plus profitable dans la production de A et B.
2. Chaque unité de C produite réduirait le profit total de l’entreprise de 110
Dhs.
3. Les valeurs marginales élevées de M1 et M2 indiquent que ces ressources
sont pleinement utilisées dans la solution optimale actuelle, et leur réallocation
à la production de C serait sous-optimale.

6.9 Analyse de sensibilité

Pour que la production de C devienne rentable, il faudrait que :
1. Le prix de vente de C augmente : Il devrait être supérieur à 760 Dhs pour
être rentable.
2. Le coût des matières premières diminue :
ˆ Si la valeur marginale de M1 baisse à moins de 65 Dhs/kg (avec M2 in-
changée), ou
ˆ Si la valeur marginale de M2 baisse à moins de 163.33 Dhs/kg (avec M1
inchangée).

3. La composition de C change : Une réduction de l’utilisation de M1 ou

M2 pourrait rendre C rentable.

6.10 Conclusion
Dans les conditions actuelles, la société JET ne devrait pas produire la peinture
de type C car elle n’est pas rentable. Sa production réduirait le profit global de
l’entreprise.
Cependant, JET pourrait envisager de :

ˆ Négocier un prix de vente plus élevé pour C

ˆ Chercher des moyens de réduire la quantité de M1 et M2 nécessaire pour

produire C
ˆ Attendre que les conditions du marché changent, rendant M1 et M2 moins
précieuses pour la production de A et B

Cette analyse démontre l’importance d’utiliser les informations fournies par

la programmation linéaire et l’analyse de sensibilité pour prendre des décisions
éclairées en matière de gamme de produits.

12