Faculté des Sciences Économiques et Sociales - Université de Lille

Licence 3 MISEG
Optimisation

Programmation linéaire
V. Ledda

23 juin 2018

Table des matières

1 Introduction

FT
1.1 Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Le cas de deux variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 La méthode du simplexe
2.1 Écriture matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
2

2
2
RA
2.2 Solutions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Le tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 La méthode de Dantzig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Formalisme et démonstration 6

4 Quelques prolongements 12
4.1 Cas où la base de départ n’est pas évidente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
D
 Programmation linéaire Chapitre 1

1 Introduction
1.1 Présentation du problème
On se donne une grandeur économique M qui dépend linéairement de plusieurs paramètres X = (x1 ; x2 ; · · · ; xn ).
On cherche à optimiser cette grandeur, c’est à dire que l’on cherche les valeurs Xm = (x1m ; x2m ; · · · ; xnm ) qui
rendent M maximale (ou minimale). Bien évidement, les valeurs de X sont contraintes ! Premièrement, les xi
sont positifs ; de plus on suppose qu’il existe k relation du type ai1 x1 + ai2 x2 + · · · + ain xn 6 ki .

Exemple 1. Une entreprise vend trois produits différents. On note P1 , P2 , P3 les quantités produites par

FT
l’entreprise de chacun de ces produits. Le prix de vente de chaque produit est fixé à l’année. L’entreprise
cherche à maximiser la fonction :

(P1 ; P2 ; P3 ) 7−→ 4P1 + 12P2 + 3P3

Cette fonction est appelée la fonction économique.
Ces articles sont produits sur une chaîne qui «tourne» 45 h par semaine. Sur cette chaîne, l’entreprise peut
produire 50 articles P1 par heure, 25 articles P2 par heure et 75 articles P3 par heure. De plus les études de
marché, montre que les possibilités de vente des 3 produits ne dépassent pas respectivement 1 000, 500
et 1 500 unités par semaine. Quelle répartition hebdomadaire de la production assure un chiffre d’affaire
RA
maximum ?

1.2 Le cas de deux variables

Une usine produit deux ciments Portland :
— le ciment «OPTIM» rapportant 30 € la tonne ;
— le ciment «EXTREM» rapportant 40 € la tonne.
Pour réaliser une tonne de ciment «OPTIM» 40 minutes de calcination dans un four à chaux et 20 minutes
de broyage sont nécessaires.
Pour réaliser une tonne de ciment «EXTREM» 30 minutes de calcination dans un four à chaux et 30 minutes
D

de broyage sont nécessaires.

Le four et l’atelier de broyage sont disponibles respectivement 12 heures et 8 heures par jour. Pour des
raisons de stockage, l’entreprise ne peut stocker que 19 tonnes de ciment par jour.
Combien de ciment de chaque type peut-on produire par jour pour maximiser le bénéfice ?

2 La méthode du simplexe
2.1 Écriture matricielle
Dans la partie précédente 1.2 on a obtenu le système de contraintes suivant :



 4x + 3y 6 72

x + y 6 19



(1)

2x + 3y 6 48






0 6 x et 0 6 y


représenté par le polygone des contraintes :

2 V. Ledda
 Programmation linéaire Chapitre 1

FT
RA
La fonction économique est :
B = 30x + 40y
Dans cette partie, nous allons présenter le même problème de manière matricielle. Cette démarche nous
permettra de généraliser au cas de plusieurs variables. Introduisons, trois variables positives, appelées
variables d’écart, e1 , e2 et e3 pour écrire les inégalités du système (1 1) sous forme d’égalités.


 4x + 3y + e1 = 72
D



x + y + e2 = 19



(2)

2x + 3y + e3 = 48






0 6 x, 0 6 y, 0 6 e1 , 0 6 e2 , 0 6 e3


On peut écrire matriciellement ce système :

  x   
 

4 3 1 0 0  y  72
1 1 0 1 0 × e1  = 19 (S)
     
     
2 3 0 0 1 e2  48
 
e3

2.2 Solutions de base

Lorsque x = y = 0, le système admet une unique solution. Mais B = 0, on est loin du maximum ! ! C’est une
solution de base réalisable du système.
Lorsque y = e2 = 0, le système admet pour solution x = 19, e1 = −4 < 0 et e3 = 4. C’est une solution de base
du système. Mais, ici, cette solution n’est pas réalisable.

Exemple 2. Reprendre le travail précédent : annuler 2 variables, résoudre, calculer B, interpréter graphi-
quement, dire s’il s’agit d’une solution de base réalisable ; pour tous les cas possibles. (Il y a 52 = 10 cas à


traiter)

3 V. Ledda
 Programmation linéaire Chapitre 1

2.3 Le tableau du simplexe

Considérons le tableau suivant :

Hors base En base

z}|{ z }| {

x y e1 e2 e3
 
4 3 1 0 0 72

FT
1 1 0 1 0 19
 

2 3 0 0 1 48


Lors que x = y = 0, e1 , e2 et e3 forment une base de R3 . (Il s’agit de la base canonique de R3 ). On dit que e1 ,
e2 et e3 sont «en base» et que x et y sont «hors base».
À l’aide du pivot de Gauss, remplacer la deuxième colonne du tableau par la colonne :
 
0
1
 
 
RA
0

Que remarque-t-on ? Interpréter géométriquement. Cette opération s’appelle un «pivotement», y est entré
en base et e2 est sorti, il est maintenant hors base.
En général parcourir tous les sommets n’est pas réalisable car leur nombre croît très vite avec le nombre de
contraintes et de variables 1 .
L’idée de l’algorithme du simplexe 2 est de parcourir un chemin parmi les solutions de bases réalisables
en augmentant à chaque étape la valeur de la fonction économique pour arriver à une solution de base
réalisable optimale.
L’algorithme du simplexe se présente généralement sous la forme d’une succession de tableaux, dans le cas
présent le tableau initial pourrait être :
D

 
 4 3 1 0 0 72
 1 1 0 1 0 19
 
  (3)
 2 3 0 0 1 48
30 40 0 0 0 0
 

2.4 La méthode de Dantzig

Il s’agit, à l’aide de «pivotements», de faire entrer et sortir judicieusement des vecteurs de l’ensemble des
vecteurs de base. On parcourt ainsi le polygone des contraintes et l’on s’arrête une fois que l’on a trouvé une
solution de base réalisable optimale.

L’algorithme du simplexe On appelle S le tableau à n+1 lignes et m+n+1 colonnes issue d’un problème de
programmation linéaire à m variables et n contraintes. La dernière ligne représente la fonction économique
que l’on cherche à maximiser.
n

1. Pour n variable et m contraintes, il est inférieur ou égal à m
2. George Dantzig (1951)

4 V. Ledda
 Programmation linéaire Chapitre 1

1 Algorithme Simplexe
2 TantQue La dernière ligne contient des coefficients strictement positifs Faire
3 j←{j|Sn+1,j = maxi∈~1,··· ,m+n Sn+1,i }
Si,n+m+1 Sk,n+m+1
4 i← {i| Si,j = mink∈~1,··· ,n,Si,j >0 Sk,j }
5 Par pivotement, faire entrer la colonne j et sortir la colonne i de la liste
des colonnes «en base»
6 FinTantQue
7 Dans le tableau, on lit les variables en base

FT
8 Si la variable i est «en base» alors Si,n+m+1 donne la valeur à donner à la
variable i pour obtenir une solution optimale
9 −Sn+1,n+m+1 est le maximum de la fonction économique

Quelques explications
• À la ligne 3, Pour déterminer la variable qui entre en base, on choisit parmi les variables celle qui
«rapporte» le plus. Autrement dit, on choisit la variable associée au plus grand gain marginal. S’il y a
RA
plusieurs colonnes où le coefficient est maximal, on en choisit une.
S
• À la ligne 4, Pour déterminer la variable qui sort de la base, on prend la ligne où le rapport k,n+m+1
Si,j
est le plus petit possible pour ne pas sortir du polygone des contraintes. En effet, se faisant, lors du
pivotement on a pour k , i :
S
Lk ← Lk − Sk,j Li
i,j
Plus précisément pour la dernière colonne :

Sk,j
Sk,n+m+1 ← Sk,n+m+1 − Si,n+m+1
Si,j

S S
D

Donc Sk,n+m+1 6 0 car par le choix de i , k,n+m+1 i,n+m+1

Sk,j − Si,j > 0.
S’il y a plusieurs lignes où le rapport est minimal, on en choisit une.
• À la ligne 2, dès que tous les coefficients sur la dernière ligne sont tous négatifs ou nuls, on s’arrête.

Remarque 1. À côté des tableaux simplexes, il peut être intéressant de tenir à jour les listes des variables
en base et des variables hors base.

Remarque 2. Les coefficients Si,j et Sn+1,j sont par construction de l’algorithme strictement positifs. Lors du
S
pivotement, la dernière ligne est transformée par Ln+1 ← Ln+1 − Sn+1,j Lj . Pour le coefficient Sn+1,n+m+1 étant
i,j
donné que les coefficients Sk,n+m+1 sont positifs pour 1 6 k 6 n, on est assuré qu’à chaque étape le coefficient
sera négatif et plus petit que le précédent. C’est à dire, que la nouvelle solution de base est équivalente ou
meilleure que la précédente.

Exemple 3. Appliquer l’algorithme du simplexe au tableau (3

3) et retrouver les résultats obtenus graphique-
ment lors d’une séance précédente.

5 V. Ledda
 Programmation linéaire Chapitre 1

3 Formalisme et démonstration
Définition 1. On appelle programme linéaire, (P), la donnée :
1. d’un système d’équations ou d’inéquations linéaires :



 X>0
 11 1 12 2 + · · · + a1n xn ≶1 b1
a x + a x



 .. .. (I)



 . .

FT
 a x + a x + ··· + a x ≶ b

p1 1 p2 2 pn n p p
 
 x1 
x2
 
 
avec X =  ..
 et ≶ est soit le symbole “=”, soit “6”, soit “>” ;
 i
 . 

xn

 
 c1 
c2
 
 
t
2. d’une forme linéaire m = C · X où C =  ..
.
RA


 . 

cn

Résoudre un programme linéaire consiste à trouver le ou les valeurs de X qui optimisent m, c’est à dire le ou
les valeurs de X qui rende(nt) m maximale ou minimale selon les cas.

Définition 2. Une solution réalisable est une solution de (II). Une solution optimale est une solution réalisable
qui optimise m. La fonction objectif, ou la fonction économique, est la forme linéaire m. La valeur de (P) est le
nombre t C · Xo où Xo est une solution optimale.
D

Définition 3. On appelle programme linéaire canonique de type max tout programme linéaire de la forme :



 X>0
AX 6 B


 m = t C · X (max)



où A ∈ Mp,n , B ∈ Mp,1 et C ∈ Mn,1 .

En remplaçant AX 6 B par AX > B et m = t C · X (max) par m = t C · X (min) on obtient un programme

linéaire canonique de type min. Un programme linéaire standard est un P.L. canonique où les contraintes
(hormis celles de positivitées) sont des égalités.

Proposition 1. Tout programme linéaire est équivalent à un programme linéaire canonique de type max. Tout
programme linéaire est équivalent à un programme linéaire standard de type max.

Exemple 4. Considérons le programme linéaire suivant :

X>0







 2x + y − z 6 4
−3x + y + z > 2 (P)



2x + 7y = 3





 m = x+y −z (min)

6 V. Ledda
 Programmation linéaire Chapitre 1

(P
P) est équivalent à 


 X>0
2x + y − z 6 4






 3x − y − z 6 −2
(P’)

2x + 7y 6 3








 −2x − 7y 6 −3
m = −x − y + z (max)



P) est équivalent à
(P 
 X0 > 0

FT


2x + y − z + e1 = 4






 3x − y − z + e2 = −2
(P”)

2x + 7y + e3 = 3








 −2x − 7y + e4 = −3
m = −x − y + z (max)



x 
 

y 
 

z 
 

RA
où X0 = 

e1 .


e2 



e3 
 
 
e4
Les variables ei sont appelées variables d’écarts.

Proposition 2. L’ensemble des solutions réalisables d’un programme linéaire est une partie convexe de Rn .

Preuve. Soit t ∈ [0; 1], X = tX0 +(1−t)X1 où X0 et X1 sont deux solutions réalisable d’un programme linéaire,
que l’on peut supposer sous la forme canonique de type max. Comme t et 1 − t sont positifs,
D

AX = tAX0 + (1 − t)X1 6 tB + (1 − t)B = B

Ainsi X est une solution réalisable.
cqfd

Définition 4. Soit (P) un programme linéaire. On dit qu’une solution réalisable est un sommet de (P) s’il
n’existe pas deux solutions réalisables distinctes X1 et X2 de (P) telles que X soit le milieu du segment [X1 ; X2 ].

Proposition 3. Si un programme linéaire (P) admet une unique solution maximale X alors X est un sommet
de P.
Preuve. Procédons par l’absurde. Supposons qu’il existe deux solutions réalisables distinctes X1 et X2 de
(P) telles que X soit le milieu du segment [X1 ; X2 ]. Sans perte de généralité, on peut supposer également que
le programme linéaire (P) est sous la forme canonique de type max.
Considérons la fonction 
[0; 1] → R


f :
x 7→ t C(xX1 + (1 − x)X2 ).


La fonction f est une fonction affine, f (x) = t C(X1 − X2 )x + t CX2 ; cette fonction est soit croissante soit
décroissante. Supposons qu’elle soit croissante. f (0, 5) = t CX 6 f (1) = t CX1 . Comme X est l’unique solution
optimale, X = X1 . Or X est le milieu du segment [X1 ; X2 ], donc X1 = X = X2 ; ceci contredit l’hypothèse.
Donc X est un sommet de l’ensemble des contraintes. cqfd
De la même manière on peut démontrer la proposition suivante :

7 V. Ledda
 Programmation linéaire Chapitre 1

Proposition 4. Si X1 et X2 sont deux solutions optimales distinctes d’un programme linéaire (P) alors tous
les points du segment [X1 ; X2 ] sont des solutions optimales de (P).

Dans la suite on suppose que (P) est un programme linéaire standard




 X>0
AX = B


 m = t C · X (max)



où A ∈ Mp,n , B ∈ Mp,1 et C ∈ Mn,1 ; tel que p 6 n et rang A = p. Ces deux conditions sont raisonnables car :

FT
— On peut toujours rajouter des variables
— Si rang A < p alors soit le système n’a pas de solution ! soit il en a et certaines équations sont
redondantes (combinaisons linéaires des autres)

Définition 5. On appelle base réalisable de (P) toute famille B de vecteurs colonnes extraites de A telle que :
i) B est une base de Rp
ii) les coordonnées de B dans la base B sont toutes positives ou nulles.
RA
Définition 6. Soit B une base réalisable de (P). Notons i1 , i2 , · · · , ip les indices des colonnes de A sélectionnées
pour former B. En particulier B = xi1 Ai1 + xi2 Ai2 + · · · + xip Aip = xi1 B1 + xi2 B2 + · · · + xip Bp .
On appelle solution de base réalisable associée à la base réalisable B, le vecteur de Rn dont la coordonnée de
rang ik vaut xk et 0 sinon.
 
4 3 1 0 0
Exemple 5. Dans l’exemple de la cimenterie, A = 1 1 0 1 0 les 3 dernières colonnes forment une
 
2 3 0 0 1
 

 0 
 
 
72
 0 
D

 
3
base de R . B = 19 ainsi B = 72A3 + 19A4 + 48A5 = 72B1 + 19B2 + 48B3 . Le vecteur 72 est la solution de






 
48 19
   
 
48
base réalisable associé à la base réalisable B.
On dit que les variables xik sont les variables de base (ou en base), les autres sont les variables hors-base.
Remarque 3. Lorsque l’on transforme un programme linéaire canonique en un programme linéaire standard
en ajoutant k variables d’écart, les k dernières colonnes forment une base réalisable.

O Théorème 1 (admis). Soit X une solution réalisable de (P). Notons i1 , i2 , · · · , ir les indices des coordonnées
strictement positives.
On a l’équivalence suivante :
X est un sommet de (P) si et seulement si le système (Ai1 ; Ai2 ; · · · ; Air ) est libre.

En conséquence toute solution de base réalisable de (P) est un sommet de (P). Réciproquement, si X est un
sommet, en sélectionnant les colonnes de A dont les indices sont ceux des coordonnées strictement positives
de X, on obtient une famille libre. On obtient une base de Rp en complétant si besoin cette famille.

Attention
En général pour un sommet donné, il existe plusieurs bases réalisables correspondantes.

8 V. Ledda
 Programmation linéaire Chapitre 1

n

Remarque 4. Comme il y a au plus m bases de m vecteurs sélectionnés parmi les n colonnes de A, le
n

programme linéaire (P) possède au plus m sommets.

Remarque 5. Dans le cas où un sommet à r < p coordonnées strictement positive, il y a autant de base
réalisable associée à ce sommet que de façon de compléter la famille libre en une base. On dit qu’il s’agit
d’un sommet dégénéré. Géométriquement, il s’agit de situation où au moins r + 1 hyperplan “se coupent”
au même point.

FT
RA
O Théorème 2. Soit (P) un programme linéaire. Si (P) possède des solutions optimales, alors au moins un des
sommets de (P) est solution optimale.
D

Preuve. Soit X une solution optimale de (P). On suppose que X possède r coordonnées strictement positives.
On peut supposer, sans perte de généralité, qu’il s’agit des r premières coordonnées.
Si X est un sommet, il n’y a rien à démontrer. Sinon, d’après le théorème 1, A1 ; A2 ; · · · ; Ar forment une famille
liée de Rp . C’est à dire qu’il existe un vecteur non nul W ∈ Rn dont les n − r coordonnées sont nulles (comme
X) tel que AW = 0. Nous allons construire une solution optimale de (P) qui possède au plus r −1 coordonnées
strictement positives. (C’est à dire un zéro de plus que X).

Construction de solutions réalisables Soit t un réel strictement positif et cherchons notre vecteur sous la
forme X + tW. Posons Xt = X + tW et X−t = X − tW. Par construction ces deux vecteurs sont des solutions du
système (A(Xt ) = A(X−t ) = A(X) = B). Cherchons les valeurs de t qui rendent réalisable ses solutions. Pour
cela, il est nécessaire que :
 xi
(  si w i > 0 t 6 !
xi + twi > 0


 wi xi xi
∀i ∈ ~1; r ⇔ ⇔ t 6 τ = min , wi > 0 ; − , wi < 0

xi − twi > 0 si w < 0 t 6 − xi
 i∈~1;r wi wi
 i
wi


Lorsque t = τ, non seulement Xt et X−t sont des solutions réalisables (coordonnées positives) mais de plus
soit Xt soit X−t a une coordonnées nulles supplémentaires.

9 V. Ledda
 Programmation linéaire Chapitre 1

Montrons que Xt et X−t sont optimales. Par définition de X, t CXt 6 t CX et t CX−t 6 t CX

( t
CXt = t CX + t t CW 6 t CX
( t
t CW 6 0
t t t t ⇔
CX−t = CX − t CW 6 CX −t t CW 6 0
Or t > 0, donc t CW = 0 et t CXt = t CX−t = t CX.
Ainsi Xt et X−t sont optimales.

Conclusion Nous avons donc une nouvelle solution optimale qui possède au plus k − 1 coordonnées non
nulles, d’après le théorème 1 soit il s’agit d’un sommet soit nous avons une famille d’au plus k − 1 vecteurs

FT
liés parmi les colonnes de A. On peut reprendre le raisonnement précédent et diminuer encore le nombre
de colonnes. Or rang(A) = m, donc nécessairement après un certain nombre d’itération, on obtiendra une
famille libre et donc un sommet de (P) cqfd

Remarque 6. Une conséquence du théorème 2 est la suivante : tout programme linéaire réalisable possède
au moins un sommet.

Définition 7. Deux bases réalisables sont dites voisines si elles ne diffèrent que d’un seul vecteur.
RA
Une base B peut être améliorable s’il existe une meilleure base voisine. Plus précisément, B est meilleur que
B 0 si t CXB 6 t CXB 0 . Elle peut être optimale dans le cas où il n’y a pas de meilleur base. Il se peut également
que le programme linéaire (P) ne possède pas de solution optimale.

Définition 8. Mettre la base B en position test c’est construire le programme linéaire (P0 ) = (PB ) équivalent à
P où :
i) les colonnes de A0 correspondant aux colonnes de B forment (à l’ordre près) la matrice Ip ;
ii) les coefficients de C0 dont les indices sont ceux des colonne de B sont nulles.
D

Lorsque le système standard provient d’un système canonique. La matrice identité se lit sur les dernières
colonne de A.

Proposition 5. Considérons (PB ) un programme linéaire standard à second membre positif où la base réalisable
B est en position test. Notons XB la solution de base réalisable associée.
1. Si tous les coefficients de C sont négatifs ou nul alors XB est une solution optimale.
2. S’il existe ci un coefficient de C strictement positif alors en posant XB (t) = XB + tei on a pour t > 0,
m(XB (t)) = tci
(a) Si ∀k ∈ ~1; p, aki < 0 alors (P) n’a pas de solution optimale.
(b) S’il existe des indices k tels que aki > 0 alors B est améliorable en remplaçant dans le B le vecteur
d’indice i de A par le vecteur d’indice j = mink∈~1;p ( abk |aik > 0) de A.
ik

Preuve. 1. Quel que soit X > 0, t CX 6 0, comme t CXB = 0, ∀X > 0, t

CX 6 XB .
2. m(XB (t)) = tci car d’une part t CXB = 0 et d’autre part t Cei = ci .
(a) Observons que AXB (t) = A(XB + tei ) = B + tAi 6 B. Donc XB (t) est une solution réalisable quelque
soit t > 0 et m(XB (t)) = tci est aussi grand que l’on veut : (P) n’a pas de solution optimale.
(b) Sans sacrifier à la généralité, on peut supposer que A est de la forme

10 V. Ledda
 Programmation linéaire Chapitre 1

Ai

 

 a1i 

 
a2i
 
 
 

Ip

 .. 
.
 
 
 
 

FT
 .. 

 . 

 

 api 


 0 
 
 . 
 .. 
 
 t 
 
 .. 
 
 . 
RA
Cherchons un vecteur X(t) de la forme  0  où t est à la i ème position.
 
 
x1 
 
x2 
 .. 
 
 . 
 
xp
Pour que la solution soit réalisable il est nécessaire que

∀k ∈ ~1; p aki t + xk = bk ⇔ bk − aki t = xk > 0 (4)

Si aki < 0 alors bk − aki t > 0 quelque soit t.

D

Donc (4 4) est équivalent à

bk
∀k ∈ ~1; p tel que aki > 0 ,t 6
aki

La plus grande solution que l’on peut obtenir est atteinte pour t = mini∈~1;r,aki >0 abk .
 
ki
b 
k
Soit j un indice pour lequel mini∈~1;r,aki >0 a est atteint.
ki
On montre en utilisant le théorème 1 qu’avec de tels choix de i et de j, B est améliorable et que
cette solution réalisable est un sommet du programme linéaire.
cqfd

11 V. Ledda
 Programmation linéaire Chapitre 1

4 Quelques prolongements
4.1 Cas où la base de départ n’est pas évidente
4.2 Dualité
Exemple 6. Une entreprise fabrique deux types produits, ces produits requièrent 3 matières premières. On
note c1 et c2 les bénéfices obtenus par la vente des produits fabriqués et l’on suppose que les quantités x1 et
x2 vérifient le système des contraintes suivant :


FT
x + 3x2 6 18
 1




 x1 + x2 6 8
 2x + x 6 14

1 2
Que l’on peut écrire :



 X>0
AX 6B (P)


 m = tC · X

(max)


La résolution de ce problème par la méthode du simplexe donne :

RA
 
1 31 0 0 18
1 10 1 0 8 
 
 
2 10 0 1 14
1 10 0 0 0
 

L1 ← L1 − 12 L3 0 5
1 0 − 12
11 
 
2
L2 ← L2 − 21 L3 0 1
0 1 − 12
1 
 
2
L3 ← 21 L3 1
0 12
 
1 0 7 
 2
1 1
L4 ← L4 − 2 L3 0 0 0 − 12
−7

2
D

 
L1 ← L1 −5L2 0 0 1 −5 2 6 
L2 ← 2L2 0 1 0 2 −1 2 
 
 
L3 ← L3 −1L2 1 0 0 −1 1 6 
L4 ← L4 −1L2 0 0 0 −1 0 −8
 

En donnant les valeurs : 6 à la variable x1 , 2 à la variable x2 , on obtient un maximum de 8. Dans cette

situation, les variables d’écart e2 et e3 sont nulles, donc les deux dernières contraintes sont serrées et la
première contrainte est lâche, il reste 6 unités de la première matière première. L’entreprise peut être
intéressée par la revente de ces 6 unités de matière première inutilisée.
Notons y1 , y2 et y3 le prix de revente des matières premières. Si 18y1 + 8y2 + 14y3 > 8 produire n’est pas
rentable.
Notons t Y = (y1 ; y2 ; y3 ). Le bénéfice pour l’entreprise s’écrit donc :

t
CX + t Y(B − AX) = t CX + t Y(B − AX) = t YB + (t C − t YA)X
Lorsque (t C − t YA)X est négatif, la production des quantités X n’est pas rentable.
Plaçons nous maintenant du point de vue d’une entreprise qui rachète les matières premières, si elle souhaite
dissuader l’entreprise de produire elle doit proposer un système de prix t Y = (y1 ; y2 ; y3 ) tel que t C − t YA 6 0
tout en minimisant son coût t YB.
Donc l’entreprise qui rachète les matières premières doit résoudre le programme linéaire suivant :


 Y>0
 t


 AY > C (D)
 m = t B · Y (min)


12 V. Ledda
 Programmation linéaire Chapitre 1

Où de manière explicite :

y + y + 2y3 > 1
 1 2




 3y 1 + y2 + y3 > 2
 18y + 8y + 14y = m (min)

1 2 3
Le programme linéaire (D
D) est appelé programme linéaire dual de (P
P).
Exemple 7. La cimenterie. Le dual du système (11) est :

a > 0, b > 0, c > 0

FT



 4a + b + 2c > 30


3a + b + 3c > 40





 72a + 19b + 48c (min)

On peut résoudre ce problème qui a pour solution a = 0, b = 10 et c = 10. À l’optimum 72a + 19b + 48c vaut
670 comme pour le primal.
Si l’on augmente la capacité de stockage d’une unité, le primal devient :


 4x + 3y 6 72
RA


x + y 6 20



(5)

2x + 3y 6 48






0 6 x et 0 6 y


Sa résolution donne :
D

une augmentation du bénéfice de 10 unités. Ce qui correspond à la solution pour la deuxième variable du
dual. Les solutions du dual sont les élasticités du bénéfice par rapport à chacune des contraintes.

Définition 9. À tout programme linéaire canonique de type max de la forme :




 X>0
AX 6 B


 m = t C · X (max)



on associe le programme linéaire canonique de type min de la forme :



 Y>0
 t


 AY > C
 m = t B · Y (min)


appelé programme linéaire dual.

13 V. Ledda
 Programmation linéaire Chapitre 1

Proposition 6. Le dual du dual est le primal.

O Théorème 3. Soit X et Y des solutions réalisables respectivement du primal et du dual. On a l’inégalité

suivante :
t
CX 6 t BY.

Preuve.

FT
AX 6 B
t
YAX 6 t YB
t
YAX 6 t BY
t t
( AY)X 6 t BY
t
CX 6 t YAX 6 t BY
RA
cqfd

Corollaire 1. Soit X et Y des solutions réalisables respectivement du primal et du dual. Si t CX > t BY alors

t
CX = t BY
et X et Y sont respectivement des solutions réalisables optimales du primal et du dual.

Preuve. Soit X0 une autre solution réalisable de (P), d’après le théorème (3

3) :
t
CX0 6 t BY = t CX
D

Donc X est optimale. En reprenant le même raisonnement avec une solution réalisable quelconque du dual
on obtient le résultat annoncé. cqfd

O Théorème 4 (Théorème fondamental de la programmation linéaire). Soit un programme linéaire. Alors

1. s’il admet une solution réalisable alors il admet une solution réalisable de base ;
2. s’il admet une solution optimale, alors il admet une solution optimale de base ;
3. s’il admet une solution réalisable et si la valeur de la fonction objectif est bornée, alors il admet une
solution optimale de base.

O Théorème 5. 1. Si le programme linéaire primal et le PL dual admettent des solutions réalisable, alors ils
admettent tous les deux une solution optimale et les fonctions objectifs sont égales à l’optimum.
2. Si le programme linéaire primal n’est pas borné alors le PL dual n’admet pas de solution de base réalisable.

Exemple 8. 


 X>0

 2x1 − x2 6 2
(6)

3x1 − 2x2 6 6





 z = 2x1 + x2 (max)

14 V. Ledda
 Programmation linéaire Chapitre 1

Le PL (6
6) n’est pas borné, on peut faire croître x2 indéfiniment.
Examinons le dual :



 Y>0
 2y + 3y > 2
 1
 2
 −y1 − 2y2 > 1




 z = 2y + 6y (min)
1 2

La seconde contrainte ne peut être satisfaite.

Exemple 9.

FT



 X>0


 x1 + 2x2 > 12
2x1 + x2 > 9





 z = −3x1 − 4x2 (min)
RA
D

15 V. Ledda