Année Préparatoire Master Stats-Eco Claudie Hassenforder-Chabriac

Corrigés des exercices du Chapitre 3

10 1) Le pays va acheter x1 lots 1, x2 lots 2 et x3 lots 3. Il souhaite minimiser son coût qui sera
en fait z 0 = 10x1 +12x2 +15x3 . Il veut au moins 100 000 fusils donc on doit avoir 500x1 +300x2 +
800x3 ≥ 100 000. De même, pour les grenades, on doit avoir 1 000x1 +2 000x2 +1 500x3 ≥ 200 000,
pour les chars, 10x1 + 20x2 + 15x3 ≥ 100, pour les mitrailleuses 100x1 + 80x2 + 150x3 ≥ 400 et
pour les bazookas 80x1 + 120x2 + 200x3 ≥ 400. Le programme s’écrit donc :


 10x1 + 12x2 + 15x3 = z[min]

 500x + 300x + 800x

 1 2 3 ≥ 100 000

1 000x1 + 2 000x2 + 1 500x3 ≥ 200 000
(P )

 10x1 + 20x2 + 15x3 ≥ 100



 100x1 + 80x2 + 150x3 ≥ 400

80x1 + 120x2 + 200x3 ≥ 400
2) Le programme dual s’écrit :


 100 000y1 + 200 000y2 + 100y3 + 400y4 + 400y5 = z 0 [max]


 500y1 + 1 000y2 + 10y3 + 100y4 + 80y5 ≤ 10
(D) 300y1 + 2 000y2 + 20y3 + 80y4 + 120y5 ≤ 12



 800y1 + 1 500y2 + 15y3 + 150y4 + 200y5 ≤ 15

y1 , y2 , y3 , y4 , y5 ≥ 0.
3) Le programme dual peut être interprété comme suit :
Un fabriquant d’armements qui produit ces différents types d’armes à la demande veut s’emparer
du marché.
Soit y1 , le prix de vente d’un fusil, y2 celui d’une grenade, y3 celui d’un char, y4 celui d’une
mitrailleuse et y5 celui d’un bazooka.

- Un lot de type 1 coûtera : 500y1 + 1 000y2 + 10y3 + 100y4 + 80y5 = Y1 ;

- Un lot de type 2 coûtera : 300y1 + 2 000y2 + 20y3 + 80y4 + 120y5 = Y2 ;

- Un lot de type 3 coûtera : 800y1 + 1 500y2 + 15y3 + 150y4 + 200y5 = Y3 .

Le marché rapportera globalement : 100 000y1 + 200 000y2 + 100y3 + 400y4 + 400y5 .

Pour remporter le marché, le fabriquant d’armements doit calculer ses prix de vente unitaires
de façon concurrencer le marchand d’armes (c’est-à-dire Y1 ≤ 10, Y2 ≤ 12 et Y3 ≤ 15), tout en
faisant un bénéfice maximal.
Le programme est donc ici le programme dual écrit à la question 2.

11 Il convient de ramener chaque contrainte, si nécessaire, à la forme αx 1 + βx2 + γx3 ≤ δ

(où δ ici, peut être négatif), de s’assurer de ce que toutes les variables du primal sont positives
ou nulles, et - enfin - de ramener la fonction économique, si nécessaire, à une maximisation. En
particulier ici, on remplacera la contrainte en égalité : 3x1 − 2x2 + 7x3 = 5 par deux inéquations
de sens contraire
3x1 − 2x2 + 7x3 ≤ 5 et 3x1 − 2x2 + 7x3 ≥ 5,

15
CORRIGÉS DES EXERCICES Programmation Linéaire

cette dernière inéquation, (de même que x1 − 5x2 + 6x3 ≥ 2) doit être multipliée par −1 pour ob-
tenir une inégalité de la forme αx1 +βx2 +γx3 ≤ δ ; de même, on ramène la fonction économique
à une maximisation en la multipliant par −1. Ainsi, le primal devient, sous forme standard de
passage au dual :


 2x1 − 3x2 − 4x3 = −z[max]

 2x1 + x2 − 4x3 ≤ 10



−x1 + 5x2 − 6x3 ≤ −2

 3x 1 − 2x 2 + 7x 3 ≤ 5



 −3x 1 + 2x 2 − 7x 3 ≤ −5

x1 , x2 , x3 ≥ 0

D’où le dual :



 10y1 − 2y2 + 5y3 − 5y4 = z 0 [min]


 2y1 − y2 + 3y3 − 3y4 ≥ 2
y1 + 5y2 − 2y3 + 2y4 ≥ −3



 −4y1 − 6y2 + 7y3 − 7y4 ≥ −4

y1 , y2 , y3 , y4 ≥ 0

12 1) On commence par chercher la solution optimale de (P ), mis sous forme standard en

introduisant des variables d’écart :

 4x1 + 5x2 = z[max]
3x1 + x2 + x3 = 1

x1 + x 2 + x4 = 1

On a une solution initiale évidente avec y3 = y4 = 1 et y1 = y2 = y3 = 1. On peut donc aisément

démarrer le simplexe.
Premier tableau :

ci i ↓ j → 1 2 3 4 β βi /αi,e
0 3 3 1 1 0 1 1
s← 0 4 1 4 0 1 1 1/4
cj 4 5 0 0
∆j 4 5 0 0 z−0
↑e

Deuxième tableau :

ci i ↓ j → 1 2 3 4 β βi /αi,e
s← 0 3 11/4 0 1 −1/4 3/4 3/11
5 2 1/4 1 0 1/4 1/4 1
cj 4 5 0 0
∆j 11/4 0 0 −5/4 z − 5/4
↑e

16
Année Préparatoire Master Stats-Eco Claudie Hassenforder-Chabriac

Troisième tableau :

ci i ↓ j → 1 2 3 4 β βi /αi,e
4 1 1 0 4/11 −1/11 3/11
5 2 0 1 −1/11 3/11 2/11
cj 4 5 0 0
∆j 0 0 0 −1 z−2
↑e
 
∗ 3 2
On est donc à l’optimum, et ceci, pour x = , .
11 11


 y1 + y2 = z 0 [min]

3y1 + y2 ≥ 4
2) (D) .

 y 1 + 4y 2 ≥ 5

y1 , y 2 ≥ 0
Les relations d’exclusion s’écrivent :
 ∗ 
y1 (1 − 3x∗1 − x∗2 − x∗3 ) = 0 ; (4 − 3y1∗ − y2∗ )x∗1 = 0 ;
(1) (2) .
y2∗ (1 − x∗1 − x∗2 − x∗4 ) = 0 (5 − y1∗ − 4y2∗ )x∗2 = 0
Comme on a x∗1 > 0 et x∗2 > 0, on en déduit que 3y1∗ + y2∗ = 4 et y1∗ + 4y2∗ = 5, ce qui donne
finalement (y1∗ , y2∗ ) = (1, 1).
 
∗ ∗ 3 2
Donc y1 = y2 = 1 donne la solution optimale de (D). En effet, z , = 2 = z 0 (1, 1).
11 11
Le lien entre les solutions du primal et le dual sont facilement visibles si on les résout par le
simplexe. En fait, les tableaux terminaux se recouvrent partiellement. Les colonnes de x 1 et x2
et la dernière colonne représentent le tableau final du simplexe appliqué au primal. La solution
optimale du primal apparaı̂t en dernière ligne : x1 = 3/11, x2 = 2/11 (le tableau est transposé
par rapport à la représentation habituelle : les lignes du tableau habituel deviennent ici les co-
lonnes.

Les lignes de y1 et y2 et la dernière ligne forment le tableau optimal du simplexe appliqué au

dual. La solution optimale du dual apparaı̂t en dernière colonne : y1 = y2 = 1.

Il n’est donc pas nécessaire de résoudre (P ) et (D). Il suffit de résoudre (P ) ou (D), la solution
optimale de l’autre se trouve dans le tableau optimal du premier, en dernière ligne.

13 Le programme (P L) s’écrit aussi :



 −2x1 − 3x2 = −z[max]

−4x1 − x2 ≤ −8

 −x1 − 4x2 ≤ −8

−7x1 − 10x2 ≤ −47
et il est alors aisé de passer au programme dual :


 −8y1 − 8y2 − 47y3 = −z 0 [min]

−4y 1 − y2 − 7y3 ≥ −2
(P L∗ )

 −y 1 − 4y2 − 10y3 ≥ −3

y1 , y2 , y3 ≥ 0.

17
CORRIGÉS DES EXERCICES Programmation Linéaire

soit encore 

 8y1 + 8y2 + 47y3 = z 0 [max]

4y 1 + y2 + 7y3 ≤ 2
(P L∗ )
 1
 y + 4y 2 + 10y3 ≤ 3

y1 , y 2 , y3 ≥ 0.
→ “0” est solution de (P L∗ ).

Optimisation de (P L∗ ) : simplexe. On introduit des variables d’écart (1 par contrainte) :



 8y1 + 8y2 + 47y3 = z 0 [max]

4y1 + y2 + 7y3 + y1̄ = 2
(P L∗ )

 y + 4y2 + 10y3 + y2̄ = 3
 1
y1 , y 2 , y3 , y1̄ , y2̄ ≥ 0.
On a une solution de base évidente ye1̄ = 2, ye2̄ = 3, les variables hors-base ye1 , ye2 , ye3 étant nulles.

On va résoudre (P L∗ ) par la méthode des tableaux.

Premier tableau :

ci i ↓ j → 1 2 3 1̄ 2̄ β βi /αi,e
s← 0 1̄ 4 1 7 1 0 2 2/7 = 20/70
0 2̄ 1 4 10 0 1 3 3/10 = 21/70
cj 8 8 47 0 0
∆j 8 8 47 0 0 z−0
↑e
Deuxième tableau :

ci i ↓ j → 1 2 3 1̄ 2̄ β βi /αi,e
47 3 4/7 1/7 1 1/7 0 2/7 2
s← 0 2 −33/7 18/7 0 −10/7 1 1/7 1/18
cj 8 8 47 0 0
∆j −132/7 9/7 0 −47/7 0 z − 94/7
↑e
Troisième tableau :

ci i ↓ j → 1 2 3 1̄ 2̄ β
47 3 5/6 0 1 2/9 −1/18 5/18
8 2 −33/18 1 0 −5/9 7/18 1/18

∆j −33/2 0 0 −6 −1/2 z − 27/2

et c’est le tableau optimal.
La solution du programme dual est donc y1 = 0, y2 = 1/18, y3 = 5/18 et ȳ1 = ȳ2 = 0 .

2) Récupération de la solution optimale de (P L) à partir du tableau optimal du dual (P L ∗ ).

Le tableau dual du tableau dual optimal est le tableau primal optimal.

18
Année Préparatoire Master Stats-Eco Claudie Hassenforder-Chabriac

Pour obtenir celui-ci, on commence par compléter le tableau optimal du dual en ajoutant les
contraintes de positivité des variables hors-base. On obtient ainsi un tableau carré que l’on va
transposer pour obtenir son dual.

Les 3 dernières lignes du tableau carré représentent les contraintes :


 −y1 ≤ 0
−y1̄ ≤ 0

−y2̄ ≤ 0

max 1 2 3 1̄ 2̄ u
3 5/6 0 1 2/9 −1/18 5/18
2 −33/18 1 0 −5/9 7/18 1/18
1 −1 0 0 0 0 ≤ 0
1̄ 0 0 0 −1 0 0
2̄ 0 0 0 0 −1 0

∆j −33/2 0 0 −6 −1/2 27/2

On va transposer ce tableau : les indices des variables d’écart du dual deviennent les indices des
variables structurelles du primal et les indices des variables structuelles du dual deviennent les
indices des variables d’écart du primal (¯1̄ = 1 !). Les seconds membres du dual deviennent les
coefficients de la fonction économique du primal et les coefficients de la fonction économique du
dual deviennent les seconds membres du primal :

min 1 2 1̄ 2̄ 3̄ u
1 −1 0 0 −5/9 2/9 −6
2 0 −1 0 7/18 −1/18 −1/2
1̄ 0 0 −1 −33/18 5/6 ≥ −33/2
2̄ 0 0 0 1 0 0
3̄ 0 0 0 0 1 0

∆j 0 0 0 1/18 5/18 27/2

Les deux dernières lignes expriment simplement la positivité des variables x2̄ et x3̄ hors-base.

La première ligne peut s’écrire :

−x1 − 5/9x2̄ + 2/9x3̄ = −6 ou x1 + 5/9x2̄ − 2/9x3̄ = 6.

De même pour les deuxième et troisième lignes :

−x2 + 7/18x2̄ − 1/18x3̄ = −1/2

−x1̄ − 33/18x2̄ + 5/6x3̄ = −33/2

qui peuvent s’écrire :
x2 − 7/18x2̄ + 1/18x3̄ = 1/2
x1̄ + 33/18x2̄ − 5/6x3̄ = 33/2.
Le tableau optimal du primal est donc :

19
CORRIGÉS DES EXERCICES Programmation Linéaire

1 2 1̄ 2̄ 3̄ u
1 1 0 0 5/9 −2/9 6
2 0 1 0 −7/18 1/18 1/2
1̄ 0 0 1 33/18 −5/6 ≥ 33/2

∆j 0 0 0 1/18 5/18 27/2

La solution optimale du primal est donc : x∗1 = 6, x∗2 = 1/2, x∗1̄ = 33/2, x∗2̄ = x∗3̄ = 0 et z ∗ = 27/2.

3) Méthode duale du simplexe

Lorsque les coefficients de la fonction économique sont positifs, on dispose d’une solution
initiale duale réalisable. La méthode duale du simplexe, dans ce cas, permet de résoudre le
problème en donnant à chaque itération, une solution réalisable du programme dual. Lorsque la
solution est à la fois primale et duale réalisable, elle est optimale.

La solution initiale du problème a pour variables de base les variables d’écart x 1̄ , x2̄ , x3̄ : elle
n’est pas admissible.

Le programme dual s’écrit :



 2x1 + 3x2 = z[min]


 4x 1 + x2 − x1̄ = 8
x1 + 4x2 − x2̄ = 8



 7x1 + 10x2 − x3̄ = 47

x1 , x2 , x1̄ , x2̄ , x3̄ ≥ 0

ou, avec z 0 = −z,



 −2x1 − 3x2 = z 0 [max]


 −4x1 − x2 + x1̄ = −8
−x1 − 4x2 + x2̄ = −8


 −7x1
 − 10x2 + x3̄ = −47

x1 , x2 , x1̄ , x2̄ , x3̄ ≥ 0
Le premier tableau du simplexe est donc
i↓ j→ 1 2 1̄ 2̄ 3̄
1 −4 −1 1 0 0 −8
2̄ −1 −4 0 1 0 −8
3̄ -7 −10 0 0 1 −47

∆j −2 −3 0 0 0 0
En se reportant au tableau initial de la méthode du simplexe pour le programme dual, on
constate que les 3 colonnes correspondant aux variables structurelles de ce tableau ainsi que
le second membre et les premières composantes de la fonction économique sont, au signe près,
identiques aux composantes sur x1 et x2 des 3 lignes de contraintes, aux 2 premières compo-
santes de la fonction économique et aux composantes du second membre (respectivement) du
tableau ci-dessus.

20
Année Préparatoire Master Stats-Eco Claudie Hassenforder-Chabriac

On va en fait utiliser la méthode du simplexe sur le programme dual à partir de ce tableau.

Pour commencer, on cherche la variable négative la plus petite, en l’occurrence x 3̄ , elle va sortir
de la base : ce n’est autre que le premier critère de Dantzig appliqué au programme dual.

On cherche alors, sur la ligne correspondant à la variable de base x 3̄ les coefficients négatifs :
a3,1 = −7 et a3,2 = −10.
   
∆e ∆1 ∆2 2 3 2 ∆1
On calcule = min , = min , = = : la variable x1 entre dans la
a3,e a3,1 a3,2 7 10 7 a3,1
base. Ceci n’est autre que l’application du deuxième critère de Dantzig au programme dual.

On pivote alors de façon classique sur l’élément a3,1 = −7, ce qui donne le nouveau tableau :

i↓ j→ 1 2 1̄ 2̄ 3̄ β
1 0 33/7 1 0 −4/7 132/7
2̄ 0 -18/7 0 1 −1/7 −9/7
1 1 10/7 0 0 −1/7 47/7

∆j 0 −1/7 0 0 −2/7 94/7

On constate que la solution est duale et pas primale admisible ; elle n’est donc pas optimale.

La seule variable négative est x2̄ : elle va sortir de la base.

Les coefficients négatifs de la ligne correspondante sont a2̄,2 et a2̄,3̄ :

   
∆e ∆2 ∆3̄ −1/7 −2/7 1 ∆2
= min , = min ; = = .
a2̄,e a2̄,2 a2̄,3̄ −18/7 −1/7 18 a2̄,2

18
La variable qui entre dans la base est donc x2 . On pivote sur l’élément a2̄,2 = − et on obtient
7
le tableau suivant :
i ↓ j → 1 2 1̄ 2̄ 3̄ β
1 0 0 1 −33/18 −5/18 33/2
2 0 1 0 −7/18 1/18 1/2
1 1 0 0 5/9 −2/9 6

∆j 0 0 0 −1/18 −5/18 27/2

Le tableau donne une solution primale et duale admissible : la solution est donc optimale.

21