Université Mohammed V de Rabat Département Génie Électrique

Ecole Mohammdia d’Ingénieurs Recherche Opérationnelle

AU 2019–2020 Khalil Amine

Correction TD 2 – Programmation linéaire

Exercice 1
Résoudre par la méthode du simplexe les programmes suivants:
 

 maximiser 2x 1 + 5x 2 
 maximiser 3x 1 + 2x 2 + 4x 3
sujet à sujet à

 


 

 
2x 1 + 3x 2 ≤ 30 x1 + x2 + x3 ≤ 4
 
(P 1) (P 2)

 x 1 + 2x 2 ≥ 10 
 2x 1 + 3x 2 ≤ 7
 



 −x 1 + x 2 ≤ −1 


 3x 1 + x 2 + 3x 3 ≤ 7
x1 , x2 ≥ 0 x1 , x2 , x3 ≥ 0
 

 

 maximiser 3x 1 + 5x 2 + 8x 3 
 maximiser 13x 1 + 6x 2 − 2x 3 − 10x 4
sujet à sujet à

 


 

 
x 1 + x 2 + x 3 ≤ 100 −x 1 + x 2 + 5x 3 − 2x 4 ≥ 5
 
(P 3) (P 4)

 3x 1 + 2x 2 + 4x 3 ≤ 200 
 x1 − 3x 3 + x 4 = 7
 



 x 1 + 2x 2 ≤ 150 


 x1 + x 2 + 4x 3 − 3x 4 = 4
x1 , x2 , x3 ≥ 0 x1 , x2 , x3 , x4 ≥ 0
 

Les formes standards pour (P 1) et (P 2) sont:


 maximiser 2x 1 + 5x 2

sujet à





2x 1 + 3x 2 + e 1 = 30

(P 1)

 x 1 + 2x 2 − e2 + a1 = 10




 x 1 − x 2 − e 3 + + a2 = 1
x1 , x2 , e 1 , e 2 , e 3 , a1 , a2 ≥ 0


Avec e 1 , e 2 et e 3 sont les variables d’écart, et a 1 et a 2 les variables artificielles. On procède avec la
méthode des deux phases avec la fonction artificielle à maximiser à la première phase :
−a 1 − a 2 + 11 = 2x 1 + x 2 + e 2 + e 3
¡ 33
, 28 de valeur optimale 206
¢
La solution optimale de (P 1) est 5 5 5
.


 maximiser 13x 1 + 6x 2 − 2x 3 − 10x 4
sujet à





−x 1 + x 2 + 5x 3 − 2x 4 − e 1 + a 1 = 5

(P 4)

 x1 − 3x 3 + x 4 + a2 = 7




 x 1 + x 2 + 4x 3 − 3x 4 + a3 = 4
x1 , x2 , x3 , x4 , e 1 , a1 , a2 , a3 ≥ 0


Avec e 1 une variables d’écart, et a 1 , a 2 et a 3 des variables artificielles. On procède avec la méthode des
deux phases avec la fonction artificielle à maximiser à la première phase :
−a 1 − a 2 − a 3 + 16 = x 1 + 2x 2 + 6x 3 − 4x 4 − e 1
La première phase permet de trouver une solution réalisable, mais l’algorithme ne converge pas à la
deuxième phase et la solution du problème est non-bornée.

1 / 13
Exercice 2
Un médecin recommande à un athlète de consommer des quantités en vitamines et en protéines
chaque jour. En effet, le corps d’un athlète doit disposer, au minimum et chaque jour de 15g de
vitamine et 10g de protéine. Le médecin préconise aussi de consommer les fruits F1, F2 et F3 dans
lesquels la présence des vitamines et des protéines est abondante.
Le coût d’achat d’une caisse de 10kg du fruit F1 coûte 240 MAD, le coût d’achat d’un panier de 20kg du
fruit F2 coûte 900 MAD et il faut dépenser 30 MAD pour acheter 1kg du fruit F3.
La présence des vitamines et des protéines en g dans 1kg des fruits est donnée dans le tableau suivant :
F1 F2 F3
Vitamine 1 2 1
Protéine 2 1 3
1. Formuler un programme linéaire qui permette à l’athlète de suivre les recommandations du
médecin tout en minimisant ses dépenses en argent
Variables de décision:
x 1 : Nombre de caisses à acheter du fruit F 1
x 2 : Nombre de paniers à acheter du fruit F 2
x 3 : Quantité en Kg à acheter du fruit F 3

Fonction-objectif:
Minimiser 240x 1 + 900x 2 + 30x 3
Contraintes:
1 × 10x 1 + 2 × 20x 2 + 1 × 1x 3 ≥ 15 (Quantité de vitamine disponible au moins égale à 15)
2 × 10x 1 + 1 × 20x 2 + 3 × 1x 3 ≥ 10 (Quantité de protéine disponible au moins égale à 10)
x1 ≥ 0 x 2 ≥ 0 (Contraintes de positivité)
(Le menuisier M 1 serait convaincu si l’offre du menuisier M 2 est au moins égale à son gain attendu)
Programme linéaire:

 minimiser 240x 1 + 900x 2 + 30x 3


 sujet à


10x 1 + 40x 2 + x 3 ≥ 15
20x 1 + 20x 2 + 3x 3 ≥ 10





 x1 , x2 , x3 ≥ 0
2. Donner la forme canonique du programme
La forme canonique du programme s’écrit


 maximiser − 240x 1 − 900x 2 − 30x 3

 sujet à


−10x 1 − 40x 2 − x 3 ≤ 15
−20x 1 − 20x 2 − 3x 3 ≤ 10





 x1 , x2 , x3 ≥ 0
3. Donner son dual
La forme duale du programme s’écrit:


 maximiser 15y 1 + 10y 2
sujet à





y 1 + 2y 2 ≤ 24


 2y 1 + y 2 ≤ 45




 y 1 + 3y 2 ≤ 30
y1 , y2 ≥ 0


2 / 13
4. Résoudre le Programme dual par la méthode graphique

On dessine les droites des contraintes et de la fonction-objectif et on détermine le domaine réalisable.

Une translation de la droite de la fonction-objectif permet de déterminer le point optimum du problème

qui est l’intersection des deux droites d’équations:
½
y 1 + 2y 2 = 24
2y 1 + y 2 = 45

d’où la solution optimale est (22, 1) avec une valeur optimale de 340.

5. Résoudre le Programme dual par la méthode des tableaux

(Itération 0) Le premier tableau du simplexe:

y1 y2 e1 e2 e3 c
e1 1 2 1 0 0 24
e2 2 1 0 1 0 45
e3 1 3 0 0 1 30
z 15 10 0 0 0 0

(Itération 1) On prend y 1 comme variable entrante et on cherche le pivot

y1 y2 e1 e2 e3 c r
e1 1 2 1 0 0 24 1
45
e2 2 1 0 1 0 45 2
e3 1 3 0 0 1 30 30
z 15 10 0 0 0 0

On choisit e 2 comme variable sortante et on met à jour le tableau

y1 y2 e1 e2 e3 c r
3
e1 0 2 1 - 12 0 3
2
1 1 1
y1 1 2 0 2 0 2
5
e3 0 2
0 - 12 1 15
2
5
z 0 2
0 - 152
0 - 675
2

3 / 13
(Itération 2) On choisit y 2 comme variable entrante et et on cherche le pivot

y1 y2 e1 e2 e3 c r
e1 0 3
2
1 - 12 0 3
2
1
1 1 1
y1 1 2 0 2 0 2 45
5
e3 0 2
0 - 21 1 15
2
3
5
z 0 2
0 - 152
0 - 675
2

On choisit e 2 comme variable sortante et on met à jour le tableau

y1 y2 e1 e2 e3 c r
2
y2 0 1 3 - 31 0 1
y1 1 0 - 13 2
3
0 22
e3 0 0 - 53 1
3
1 5
z 0 0 - 53 - 20
3
0 -340

On se trouve alors à l’optimalité après deux itérations avec la solution optimale (22, 1) et une valeur
optimale de 340.

6. En déduire la solution du programme primal

On utilise le théorème des écarts complémentaires. On note y = (22, 1), et x la solution optimale du
primal à chercher.
On commence par le test de saturation des contraintes pour la solution optimale y du dual :

y 1 + 2y 2 ≤ 24 : 22 + 2 × 1 = 24 Contrainte saturée Rien à déduire sur x 1

2y 1 + y 2 ≤ 45 : 2 × 22 + 1 = 45 Contrainte saturée Rien à déduire sur x 2
y 1 + 3y 2 ≤ 30 : 22 + 3 × 1 = 25 Contrainte non-saturée ⇒ x3 = 0

Les variables y 2 et y 2 sont non-nulles, alors les deux contraintes du primal sont saturées, c’est-à-dire:

10x 1 + 40x 2 + x 3 = 15
20x 1 + 20x 2 + 3x 3 = 10

Ce qui donne x = ( 16 , 31 , 0) avec une valeur optimale de 340.

4 / 13
Exercice 3
On considère le programme linéaire suivant:


 minimiser 5x 1 + 20x 2 + 10x 3

 sujet à


x 1 + 10x 2 + 2x 3 ≥ 1
x 1 + 5x 2 + 3x 3 ≥ 2





 x1 , x2 , x3 ≥ 0

1. Donner la forme canonique du programme

La forme canonique du programme s’écrit:


 maximiser − 5x 1 − 20x 2 − 10x 3



 sujet à
−x 1 − 10x 2 − 2x 3 ≤ −1
5x 2 − 3x 3 ≤ −2



 −x 1 −

 x1 , x2 , x3 ≤ 0

Avec la remarque que la valeur optimale retourner de la résolution de cette forme est l’opposée de la
valeur optimale du problème de départ.

2. Donner son dual

On reprend la forme de départ et on applique les règles de transition primal-dual du tableau ci-dessous.
En notant les variables duales y 1 et y 2 , le dual s’écrit:


 maximiser y 1 + 2y 2 Primal à minimiser −→ Dual à maximiser
≤0 ≥0
sujet à


i ème contrainte ≥ 0 i ème variable


 ≤0
y1 + y2 ≤ 5

=0 ≶0
 10y 1 + 5y 2 ≤ 20 ≥0 ≥0
ème ème

 j variable ≤ 0 j contrainte ≤0



 2y 1 + 3y 2 ≤ 10 ≶0 =0
y1 , y2 ≥ 0 Dual à maximiser ←− Primal à minimiser

qui est équivalent à: 

 maximiser y 1 + 2y 2
sujet à





y1 + y2 ≤ 5


 2y 1 + y2 ≤ 4




 2y 1 + 3y 2 ≤ 10
y1 , y2 ≥ 0


Remarquer aussi que la contrainte y 1 + y 2 ≤ 5 est redondante. En effet, en sommant les deux autre
contraintes on trouve: y 1 + y 2 ≤ 14
4 ≤ 5. Cette redondance n’affecte pas la résolution.

3. Résoudre le Programme dual par la méthode graphique

(On ignore ici la redondance de la première contrainte)
On dessine les droites des contraintes et de la fonction-objectif et on détermine le domaine réalisable.

5 / 13
Une translation de la droite de la fonction-objectif permet de déterminer le point optimum du problème
qui est l’intersection des deux droites:
½
2y 1 + 3y 2 = 10
y1 = 0

d’où la solution optimale est (0, 10

3
) avec une valeur optimale de 20
3
.

4. Résoudre le Programme dual par la méthode des tableaux

Le premier tableau du simplexe:

y1 y2 e1 e2 e3 c r
e1 1 1 1 0 0 5 5
e2 2 1 0 1 0 4 4
10
e3 2 3 0 0 1 10 3
z 1 2 0 0 0 0
On choisit la variable y 2 comme variable entrante et la variable e 3 comme variable sortante, on met à
jour le tableau du simplexe:
y1 y2 e1 e2 e3 c r
1
e1 3
0 1 0 − 13 5
3
4
e2 3 0 0 1 − 13 2
3
2 1 10
y2 3
1 0 0 3 3
1 2
z −3 0 0 0 −3 − 20
3
On se trouve à l’optimalité du fait que tous les coûts réduits sont négatifs ou nuls, et la solution optimale
est (0, 10
3
) avec une valeur optimale de 20
3
.

5. En déduire la solution du programme primal

Pour répondre à cette question, on utilise le théorème des écarts complémentaires stipulant que
si une variable primale (respectivement duale) est non nulle alors la contrainte correspondante
dans le dual (respectivement le primal) est saturée, ainsi que sa contraposée: si une contrainte du
primal (respectivement du dual) est non-saturée alors la variable duale (respectivement primale)
correspondante est nulle.

6 / 13
On commence par le test de saturation des contraintes pour la solution optimale (0, 10 3
) du dual (Ce test
permet aussi de tester la réalisabilité de la solution, sans oublier le test préliminaire de la réalisabilité
des contraintes de positivité):

y1 + y2 ≤ 5 : 0 + 10
3
= 103
Contrainte non-saturée ⇒ x1 = 0
2y 1 + y 2 ≤ 4 : 2 × 0 + 10
3
= 10
3
Contrainte non-saturée ⇒ x2 = 0
2y 1 + 3y 2 ≤ 10 : 2 × 0 + 3 × 10
3 = 10 Contrainte saturée Rien à déduire sur x 3
10
On cherche les variables non-nulles du problème dual: y 2 = 3
6= 0 alors la deuxième contrainte du
primal est saturée, c’est-à-dire:
x 1 + 5x 2 + 3x 3 = 2
Ce qui donne x 3 = 23 .
2 20
Ainsi la solution optimale du primal est (0, 0, ) avec une valeur optimale de .
3 3

7 / 13
Exercice 4
On considère le problème linéaire suivant:


 minimiser z = −2x 1 − 3x 2 − 2x 3 − 3x 4

 sujet à


(P ) −2x 1 − x 2 − 3x 3 − 2x 4 ≥ −8
3x 1 + 2x 2 + 2x 3 + x 4 ≤ 7





 x1 , x2 , x3 , x4 ≥ 0

1. Écrire le programme (P ) sous forme canonique

La forme canonique du programme s’écrit:


 maximiser z = 2x 1 + 3x 2 + 2x 3 + 3x 4

 sujet à


(P 0 ) 2x 1 + x 2 + 3x 3 + 2x 4 ≤ 8
3x 1 + 2x 2 + 2x 3 + x 4 ≤ 7





 x1 , x2 , x3 , x4 ≥ 0

Avec la remarque que la valeur optimale retourner de la résolution de cette forme est l’opposée de la
valeur optimale du problème de départ.

2. Écrire le dual (D) du programme (P )

Le dual s’écrit: 

 maximiser − 8y 1 − 7y 2
sujet à







 2y 1 + 3y 2 ≥ 2
(D) y 1 + 2y 2 ≥ 3
3y 1 + 2y 2 ≥ 2








 2y 1 + y 2 ≥ 3
y1 , y2 ≥ 0


3. Donner une solution graphique du programme (D)

On dessine les droites des contraintes et de la fonction-objectif et on détermine le domaine réalisable.

8 / 13
Une translation de la droite de la fonction-objectif permet de déterminer le point optimum du problème
qui est l’intersection des deux droites:
½
2y 1 + y 2 = 2
y 1 + 2y 2 = 3

d’où la solution optimale est (1, 1) avec une valeur optimale de −15.
Remarquer que les contraintes: ½
2y 1 + 3y 2 ≥ 2
3y 1 + 2y 2 ≥ 2
sont redondantes. Ceci peut être prouvé analytiquement comme suit:

y 1 + 2y 2 ≥ 3 ½ ½
y1 + y2 ≥ 2 2y 1 + 3y 2 ≥ y 1 + y 2 ≥ 2

2y 1 + y 2 ≥ 3 =⇒ =⇒
y1 , y2 ≥ 0 3y 1 + 2y 2 ≥ y 1 + y 2 ≥ 2
y1 , y2 ≥ 0


4. Effectuer la première itération du simplexe sur le programme (P )

On considère le problème (P ) sous sa forme canonique (P 0 ). Le premier tableau du simplexe est le

suivant:
x1 x2 x3 x4 e1 e2 c r
e1 2 1 3 2 1 0 8 8
7
e2 3 2 2 1 0 1 7 2
z 2 3 2 3 0 0 0

où on choisit la variable x 2 comme variable entrante, et la variable e 2 comme variable sortante. La

première itération donne le tableau suivant:

x1 x2 x3 x4 e1 e2 c r
1 3
e1 2 0 2 2 1 - 12 9
2
3 1 1 7
x2 2
1 1 2
0 2 2
z − 52 0 1 3
2 0 − 32 − 21
2

Après trois itérations, on trouve que la solution optimale de ce programme est x 1 = 0, x 2 = 2, x 3 = 0 et

x 4 = 3.
5. Vérifiez que la solution de (D) obtenue à la question (3.) est optimale

On applique le théorème de la dualité forte.

La valeur de la fonction-objectif du primal (P ) en (0, 2, 0, 3) est égale à 15.
Puisque la valeur de la fonction-objectif du dual (D) en (1, 1) vaut 15 aussi, alors la solution (1, 1) est
optimale.

9 / 13
Exercice 5
On considère le problème linéaire suivant :


 maximiser x 1 − 3x 2 + 3x 3
sujet à





2x 1 − x 2 + x 3 ≤ 4

(P )

 −4x 1 + 3x 2 ≤ 2




 3x 1 − 2x 2 − x 3 ≤ 5
x1 , x2 , x3 ≥ 0


1. Le point x = (0, 0, 4) est-il une solution optimale du problème ?

Le point x est réalisable.
On procède par application du théorème des écarts complémentaires.
Le problème dual (D) du problème (P ) s’écrit:


 minimiser 4y 1 + 4y 2 + 5y 3
sujet à





2y 1 − 4y 2 + 3y 3 ≥ 1

(D)

 −y 1 + 3y 2 − 2y 3 ≥ −3




 y 1 − y 3 ≥ 3
y1 , y2 , y3 ≥ 0


On suppose que le point x = (0, 0, 4) est solution optimale de (P ) et on cherche la solution duale
correspondante. On commence par le test de saturation des contraintes pour x:

2x 1 − x 2 + x 3 ≤ 4 : 2×0−0+4 = 4 Contrainte saturée Rien à déduire sur y 1

−4x 1 + 3x 2 ≤ 2 : −4 × 0 + 3 × 0 = 0 ≤ 2 Contrainte non-saturée ⇒ y2 = 0
3x 1 − 2x 2 − x 3 ≤ 5 : 3 × 0 − 2 × 0 − 4 = −4 ≤ 5 Contrainte non-saturée ⇒ y3 = 0

Par ailleurs, du fait que x 3 6= 0, la troisième contrainte du problème dual (D) est saturée, soit:

y1 − y3 = 3

ce qui donne y 1 = 3.
On calcul la valeur de la fonction objectif de (P ) en x = (0, 0, 4), et la valeur de la fonction objectif de (D)
en y = (3, 0, 0):

x 1 − 3x 2 + 3x 3 = 12
4y 1 + 2y 2 + 5y 3 = 12

Puisque x et y sont réalisables pour (P ) et (D) respectivement et que les fonction-objectifs (P )

et (D) prennent la même valeur en x et y respectivement, alors d’après le théorème des écarts
complémentaires, x est solution optimale de (P ) (et y est solution optimale de (D))

2. Que peut-on en déduire pour le point (0, 32 , 14

3 )?

On teste la réalisabilité du point (0, 23 , 14

3
) pour le problème (P )

2x 1 − x 2 + x 3 ≤ 4 : 2 × 0 − 23 + 14
3 =4 Contrainte réalisée
−4x 1 + 3x 2 ≤ 2 : −4 × 0 + 3 × 23 = 2 Contrainte réalisée
3x 1 − 2x 2 − x 3 ≤ 5 : 3 × 0 − 2 × 32 − 14
3 = −6 ≤ 5 Contrainte réalisée

(0, 32 , 14
3
) est donc une solution réalisable de (P ) et donne une valeur à la fonction-objectif égale à 12 (qui
est la valeur optimale). En conséquence ce point est aussi une solution optimale de (P ).

10 / 13
Exercice 6
On considère le problème linéaire suivant :


 maximiser 7x 1 + 6x 2 + 5x 3 − 2x 4 + 3x 5
sujet à







 x 1 + 3x 2 + 5x 3 − 2x 4 + 2x 5 ≤ 4
4x 1 + 2x 2 − 2x 3 + x 4 + x5 ≤ 3
2x 1 + 4x 2 + 4x 3 − 2x 4 + 5x 5 5



 ≤




 3x 1 + x 2 + 2x 3 − x 4 − 2x 5 ≤ 1
x1 , x2 , x3 , x4 , x5 ≥ 0


Le point x = (0, 43 , 23 , 53 , 0) est-il une solution optimale du problème ?

Le point x est réalisable.

On procède par application du théorème des écarts complémentaires.
On note le problème (P ). Le problème dual (D) de (P ) s’écrit:


 minimiser 4y 1 + 3y 2 + 5y 3 + y 4
sujet à




y 1 + 4y 2 + 2y 3 + 3y 4 ≥ 7





3y 1 + 2y 2 + 4y 3 + y 4 ≥ 6

(D)

 5y 1 − 2y 2 + 4y 3 + 2y 4 ≥ 5




 −2y 1 + y 2 − 2y 3 − y 4 ≥ −2
2y 1 + y 2 + 5y 3 − 2y 4 ≥ 3




y1 , y2 , y3 , y4 ≥ 0


On suppose que le point x = (0, 43 , 32 , 53 , 0) est solution optimale de (P ) et on cherche la solution duale
correspondante. On commence par le test de saturation des contraintes pour x:
4 2 5
x 1 + 3x 2 + 5x 3 − 2x 4 + 2x 5 ≤ 4 : 0+3× +5× −2× +2×0 = 4 Contrainte saturée Rien à déduire sur y 1
3 3 3
4 2 5
4x 1 + 2x 2 − 2x 3 + x 4 + x 5 ≤ 3 : 4×0+2× −2× + +0 = 3 Contrainte saturée Rien à déduire sur y 2
3 3 3
4 2 5 14
2x 1 + 4x 2 + 4x 3 − 2x 4 + 5x 5 ≤ 5 : 2×0+4× +4× −2× +5×0 = ≤5 Contrainte non-saturée ⇒ y3 = 0
3 3 3 3
4 2 5
3x 1 + x 2 + 2x 3 − x 4 − 2x 5 ≤ 1 : 3 × 0 + + 2 × − − 2 × 0 = −1 ≤ 1 Contrainte non-saturée ⇒ y4 = 0
3 3 3
Par ailleurs, du fait que x 2 , x 3 , x 4 6= 0, la deuxième, la troisième et la quatrième contraintes du problème
dual (D) devraient être saturées, soient:
11
  
 3y 1 + 2y 2 + 4y 3 + y 4 = 6  3y 1 + 2y 2 = 6  y1 =

5y 1 − 2y 2 + 4y 3 + 2y 4 = 5 ⇐⇒ 5y 1 − 2y 2 = 5 ⇐⇒ 8
7

−2y 1 + y 2 − 2y 3 − y 4 = −2

−2y 1 + y 2 = −2  y2 =

4
On calcul la valeur de la fonction objectif de (P ) en x = (0, 43 , 32 , 53 , 0), et la valeur de la fonction objectif de
(D) en y = ( 11 7
8 , 4 , 0, 0):

7x 1 + 6x 2 + 5x 3 − 2x 4 + 3x 5 = 8
43
4y 1 + 3y 2 + 5y 3 + y 4 =
4
Puisque x et y sont réalisables pour (P ) et (D) respectivement et que les fonction-objectifs (P ) et
(D) prennent des valeurs différentes en x et y respectivement, alors d’après le théorème des écarts
complémentaires, x n’est pas solution optimale de (P ) (et y n’est pas solution optimale de (D))

11 / 13
Exercice 7
Un menuisier M 1 fabrique des tables et des armoires avec trois types de bois : chêne, pin et noyer. Le
nombre de mètres carrés de bois nécessaire à la fabrication de chaque type de meubles et les stocks de
chaque type de bois sont résumés dans le tableau suivant :

Armoire Table Stock

Chêne 2 1 8
Pin 1 2 7
Noyer 0 1 3

Le menuisier gagne 1300 MAD par armoire et 1000 MAD par table.

1. Écrire un programme linéaire dont l’objectif est de maximiser le gain de menuisier M 1

Variables de décision:
x 1 : Nombre d’unités d’armoires à produire
x 2 : Nombre d’unités de tables à produire
Fonction-objectif:
Maximiser 1300x 1 + 1000x 2
Contraintes:
2x 1 + x 2 ≤ 8 (Contrainte liée à la limite de la quantité de chêne en stock)
x 1 + 2x 2 ≤ 7 (Contrainte liée à la limite de la quantité de pin en stock)
x 2 ≤ 3 (Contrainte liée à la limite de la quantité de noyer en stock)
x 1 ≥ 0 x 2 ≥ 0 (Contraintes de positivité)
Programme linéaire:


 maximiser 1300x 1 + 1000x 2
sujet à





2x 1 + x 2 ≤ 8


 x 1 + 2x 2 ≤ 7




 x2 ≤ 3
x1 , x2 ≥ 0


2. Résoudre le programme linéaire proposé

On procède par la méthode graphique:

12 / 13
Une translation de la droite de la fonction-objectif permet de déterminer le point optimum du problème
qui est l’intersection des deux droites:
½
x 1 + 2x 2 = 7
2x 1 + x 2 = 8

d’où la solution optimale est x ∗ = (3, 2) avec une valeur optimale de 5900.

3. Un autre menuisier M 2 a épuisé son stock, malheureusement les fournisseurs du bois sont en grève,
alors il ne peut pas acheter ses besoins en matière première. Le menuisier M 2 veut proposer à M 1
de racheter la totalité de ses stocks. Quel est le prix minimal que doit proposer M 2 pour chaque type
de bois afin de minimiser ses dépenses tout en convaincant M 1 de lui vendre son stock en bois ?

Variables de décision:
y 1 : Prix d’unité de chêne
y 2 : Prix d’unité de pin
y 3 : Prix d’unité de noyer
Fonction-objectif:
Maximiser 8y 1 + 7y 2 + 3y 3
Contraintes:
2y 1 + y 2 ≥ 1300 (Contrainte exigée pour convaincre le menuisier M 1 à vendre son stock)
y 1 + 2y 2 + y 3 ≥ 1000 (Contrainte exigée pour convaincre le menuisier M 1 à vendre son stock)
y 1 ≥ 0 y 2 ≥ 0 y 3 ≥ 0 (Contraintes de positivité)
(Le menuisier M 1 serait convaincu si l’offre du menuisier M 2 est au moins égale à son gain attendu)
Programme linéaire:


 minimiser 8y 1 + 7y 2 + 3y 3

 sujet à


2y 1 + y 2 ≥ 1300
y 2y y 3 ≥ 1000



 1 + 2 +

 y1 , y2 , y3 ≥ 0
On remarque ici que ce programme est le dual de celui de la question 1., ainsi d’après le théorème de
la dualité forte, le prix minimal que doit proposer M 2 pour chaque type de bois dans les hypothèses de
l’exercice (soit y ∗ cette solution) est la solution duale de la solution optimale x ∗ du premier programme.
On procède ici par application du théorème des écarts complémentaires pour construire cette solution.
On commence par le test de saturation des contraintes pour x ∗ :
2x 1 + x 2 ≤ 8 : 2 × 3 + 2 = 8 Contrainte saturée Rien à déduire sur y 1∗

x 1 + 2x 2 ≤ 7 : 3+2×2 = 7 Contrainte saturée Rien à déduire sur y 2∗

x2 ≤ 3 : 2≤3 Contrainte non-saturée ⇒ y 3∗ = 0

Par ailleurs, du fait que x 1∗ 6= 0 et x 2∗ 6= 0, les deux contraintes du problème dual devraient être saturées,
soient:

2y 1∗ + y 2∗ 2y 1∗ + y 2∗ = 1300 y 1 = 1600
½ ½ ½
= 1300 3
⇐⇒ ⇐⇒
∗ ∗ ∗
y 1 + 2y 2 + y 3 = 1000 ∗ ∗
y 1 + 2y 2 = 1000 y 2 = 700 3
µ ¶
∗1600 700
D’où la solution est y = , , 0 avec une valeur optimale de 5900.
300 3

13 / 13