CHAPITRE 2

Résolution d’un problème de la programmation linéaire

I. Notions préliminaires de programmation linéaire

a) Forme canonique et forme standard d’un programme linéaire
On dit qu’un programme linéaire est écrit sous forme canonique si le domaine des solutions réalisables
est défini par un système d'inéquations linéaires, Si par contre, en dehors des contraintes de non-
négativité toutes les contraintes sont des égalités, on dit que le programme linéaire, est mis sous forme
standard. On peut toujours mettre un programme linéaire quelconque sous forme standard en ajoutant
des variables supplémentaires appelées variables d'écart.

Forme canonique de maximisation Forme standard

Max CX Max CX
AX  b; AX = b;
X 0 X 0

Forme canonique de minimisation Forme standard

Min CX Min CX
AX  b; AX = b;
X 0 X 0

Exemple 1: Soit le programme linéaire (P) suivant

Max 3 x1 + 2 x 2
s.c. x1 + x 2  80
(P) :
2 x1 + x 2  100
x1  0, x 2  0

En introduisant les variables d'écart x3  et x4  dans la première et la deuxième contrainte on met le
problème sous la forme équivalente (P') :

Max 3 x1 + 2 x 2
s.c. x1 + x 2 + x3 = 80
(P ') :
2 x1 + x 2 + x 4 = 100
x1  0, x 2  0, x3  0, x 4  0

Le problème (P') est la forme standard du problème (P).

Notons que les problèmes de minimisation et de maximisation sont en fait équivalents puisque :

Min f (x) = −Max(−f (x))

D D

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 1

Exemple 2 : Mettre sous forme canonique puis sous forme standard le problème linéaire suivant :

Max x1 + x 2
s.c. 2 x1 + x 2  1
x1 + 2 x 2 = 2
x1  0,
Forme canonique de maximisation : On pose que x2= x' 2 - x' ' 2 avec x' 2 , x' ' 2 ≥0.

Max x1 + x' 2 − x' ' 2

s.c. 2 x1 + x' 2 − x' ' 2  1
x1 + 2 x' 2 −2 x' ' 2  2
- x1 − 2 x' 2 +2 x' ' 2  −2
x1  0, x' 2  0, x' ' 2  0

Forme standard : On pose que x2= x' 2 - x' ' 2 avec x' 2 , x' ' 2 ≥0.

Max x1 + x' 2 - x' ' 2

s.c. 2 x1 + x' 2 - x' ' 2 + x3 = 1
x1 + 2 x' 2 -2x' ' 2 = 2
x1 , x' 2 , x' ' 2 , x3  0,

Exemple 3 : Mettre sous forme canonique puis sous forme standard le problème linéaire suivant :

Min x1 − x 2 + x3 − x 4
s.c. x1 + x 2 − x3  1
x1 + x 2 − x 4  3
x 1  0, x2  0, x3  0
Forme canonique de minimisation : On pose que x3=-x’3 avec x’3 ≥0 et x4= x' 4 - x' ' 4 avec x' 4 , x' ' 4 ≥0.

Min x1 − x 2 − x'3 − x' 4 + x' ' 4

s.c. - x1 − x 2 − x'3  −1
x1 + x 2 − x' 4 + x' ' 4  3
x1, x2 , x'3 , x' 4 , x' ' 4  0,
Forme standard : On pose toujours que x’3=-x3 avec x’3 ≥0 et x4= x' 4 - x' ' 4 .

Min x1 − x 2 − x'3 − x' 4 + x' ' 4

s.c. x1 + x 2 + x'3 + x5 = 1
x1 + x 2 − x' 4 + x' ' 4 − x6 = 3
x1, x2 , x'3 , x' 4 , x' ' 4 , x5 , x6  0,

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 2

 b) Résolution d’un système linéaire
Un système de m équations à n inconnues x1, x2,...,xn s’écrit sous forme matricielle : AX = b où A est
une matrice comportant m lignes et n colonnes, X est le vecteur colonne dont les composantes sont les xi
et b, le second membre, est aussi un vecteur colonne avec n composantes. Le vecteur X est appelé
solution du système. Soit la m×(n+1)-matrice Ab, matrice formée par A à laquelle b est accolé. A est
dite de plein rang si rang(A)=m.

Théorème : Etant donné un système linéaire AX = b, b≠0, trois cas peuvent sont possible :
1) Le système est de plein rang, dans ce cas l’ensemble des solutions {X | AX = b} n’est pas vide, la
solution est unique si et seulement si m=n, et une infinité de solution si m<n.
2) Le système n’est pas de plein rang, et le système AX = b est incompatible, donc pas de solution.
3) Le système n’est pas de plein rang, et le système AX = b est redondant et en enlevant la
redondance on retourne au cas 1).

Exemple 1 : Soit le système d'équations suivant :

x₁+2x₂+x₃=7. 1 2 1 x1 7

(S₁): 2x₁-x₂+2x₃=6. ≡ 2 -1 2 x2 = 6

x₁+x₂+3x₃=12. 1 1 3 x3 12

Il est clair que A est de plein rang (rang A=3) et le système est de Cramer, possède donc une solution
unique X=A-1b. Vérifions ça par le résultat précédent en échelonnant la matrice Ab.

1 2 1 7 1 2 1 7 1 2 1 7 1 2 1 7
2 -1 2 6 0 -5 0 -8 0 -5 0 -8 0 1 0 8/5
1 1 3 12 0 -1 2 5 0 0 2 33/5 0 0 1 33/10

Ceci implique : x1 = 0.5, x2 = 1.6 et x3 = 3.3

Exemple 2 : Soit le système d'équations suivant :

x₁+2x₂+x₃+x₄ = 7. 1 2 1 1 x1 7

(S₁): 2x₁-x₂+2x₃+2x₄ = 6. ≡ 2 -1 2 2 x2 = 6

x₁+x₂+3x₃-x₄ =12. 1 1 3 -1 x3 12

Il est clair que A est de plein rang (rang A=3=min(3,4)) et que le rang(Ab)=3 en échelonnant la matrice
Ab.

1 2 1 1 7 1 2 1 1 7 1 2 1 1 7
2 -1 2 2 6 0 -5 0 0 -8 0 -5 0 0 -8
1 1 3 -1 12 0 -1 2 -2 5 0 0 2 -2 33/5

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 3

 1 2 1 1 7
0 1 0 0 8/5
0 0 1 -1 33/10

Donc il est clair que le rang(Ab)=rang(A)=3 avec m<n, donc le système possède une infinité de
solutions. Si x4 =0, alors ; x1 = 0.5, x2 = 1.6 et x3 =3.3 et en changeant la valeur de x4 on aura une
infinité de solutions.
Exemple 3 :

x₁+3x₂+x₃ = 5 1 3 1 x1 5

(S): 2x₁ - x₂ - x₃ = -3 2 -1 -1 x2 = -3

4x₁+2x₂+x₃ =7 4 2 1 x3 7

5x₁ -2x₂+4x₃ = -4 5 -2 4 -4

Il est clair que A n’est pas de plein rang (rang A=3=min(3,4)) et que le rang(Ab)=4 en échelonnant la
matrice Ab. D’où le système est incompatible.

1 3 1 5 1 3 1 5 1 3 1 5
2 -1 -1 -3 0 -7 -3 -13 0 -7 -3 -13
4 2 1 7 0 -10 -3 -13 0 0 9/7 39/7
5 -2 4 -4 0 -17 -1 -29 0 0 44/7 18/7
Donc d’après l’échelonnement de Gauss, on a :
(9/7)×z= 39/7, ce qui implique que z =39/9, et que (44/7)×z =18/7, ce qui implique que z =18/44, et
ceci est impossible. Donc le système est incompatible (pas de solution).

c) Bases, bases réalisables et solutions de bases

Définition 1 : Etant donné le système linéaire {AX=b, X≥0}, où A est une matrice m×n de rang égal à
m tel que m≤n. Soit N={1,2,…,n} ; I={1,2,…,m} : I⊆N. A cet ensemble d’indices correspond une
matrice carrée
régulière (mm) extraite de A notée AI=(a1,…,am). L’ensemble I est dit une base si A I est non
singulière i.e det(AI) ≠ 0.
Les éléments de I sont les indices de base.
Les éléments de J=N-I sont les indices hors base.
Etant donnée une base I, en réordonnant les colonnes de A, on peut écrire A=( AI,AJ) ; ceci est
équivalent à dire que :
AX=b → (AI,AJ)(XI,XJ)t = b
→ (AI)XI+(AJ)XJ = b
→ XI+( AI)-1(AJ)XJ = ( AI)-1b

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 4

 → XI = ( AI)-1b-( AI)-1(AJ)XJ
X*=(XI,XJ)t est dit solution de base si elle vérifie AX*=b et X*=(XI=( AI)-1b, XJ=0)t. Si en plus XI≥0,
alors X* est une solution de base réalisable.
Remarque: Si A est du rang m, le nombre de solutions de bases réalisables est au plus égal à
Cmn=n!\(m!(n-m)!).
Exemple d’application 1 : Déterminer les bases et les bases réalisables du système d’inéquations
suivant :

x1 + x₂+x₃ =6 1 1 1 0 6
A= b=
x₂ +x4 = 3 0 1 0 1 3

x₁, x₂, x₃, x4 ≥ 0

1 1 1 -1 6 3 0
1) Pour I={1,2}, AI = , On a, XI=(AI)-1×b = × = ≥
0 1 0 1 3 3 0
D,’où I est une base réalisable.

1 1
2) Pour I={1,3}, AI = , On a, det(AI) = 0, d’où I n’est pas une base.
0 0

1 0 1 0 6 6 0
3) Pour I={1,4}, A =I
, On a, XI=(A ) ×b =
I -1
× = ≥
0 1 0 1 3 3 0
D’où, I est une base réalisable.

1 1 0 1 6 3 0
4) Pour I={2,3}, A =I
, On a, XI=(A ) ×b =
I -1
× = ≥
1 0 1 -1 3 3 0
D’où, I est une base réalisable.

1 0 1 0 6 6
5) Pour I={2,4}, AI = , On a, XI=(AI)-1×b = × =
1 1 -1 1 3 -3
D’où, I n’est pas une base réalisable.

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 5

 1 0 1 0 6 6 0
6) Pour I={3,4}, A = I , On a, XI=(AI)-1×b = × = ≥
0 1 0 1 3 3 0
Donc, I est une base réalisable.
On récapitule,

Sommet (x1, x2, x3, x4) I base Nature de base

(3, 3) (3, 3, 0, 0) {1,2} {a1,a2} base réalisable

/ / {1,3} {a1,a3} n’est pas une base

(6, 0) (6, 0, 3, 0) {1,4} {a1,a4} base réalisable

(0, 3) (0, 3, 3, 0) {2,3} {a2,a3} base réalisable

(0, 6) (0, 6, 0, -3) {2,4} {a2,a4} base non réalisable

(0, 0) (0, 0, 6, 3) {3,4} {a3,a4} base réalisable

Pour les bases non réalisables, les sommets correspondant n’appartiennent pas au domaine des solutions
réalisables.
Exemple 2 : Etant donné le système des inégalités linéaires suivant :

x1 ≤6 x1 +x3 =6

x1\4 +x2 ≤ 6 , en rajoutant des variables d’écarts x1\4 +x2 +x4 =6

3 x1 +2x2 ≤ 22 aux différentes inégalités, on aura, 3 x1 +2x2 +x5 = 22

x₁, x₂ ≥ 0 x₁, x₂, x₃, x4, x5≥ 0

1 0 1 0 0 6
Donc , A= 1/4 1 0 1 0 , b= 6
3 2 0 0 1 22
Après le calcul de toutes les solutions de base associées aux différentes bases on aura le tableau
suivant :

Sommet (x1, x2) (x1, x2, x3, x4, x5) I base

(4, 5) (4, 5, 2, 0, 0) {1,2,3} {a1,a2,a3}

(6, 2) (6, 2, 0, 2.5, 0) {1,2,4} {a1,a2,a4}

(6, 0) (6, 0, 0, 4.5, 4) {1,4,5} {a1,a4,a5}

(0, 6) (0, 6, 6, 0, 10) {2,3,5} {a2,a3,a5}

(0, 0) (0, 0, 6, 6, 22) {3,4,5} {a3,a4,a5}

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 6

On a le nombre total de solutions de base est C35=10, or on a déterminé uniquement 5, les 5 autres
choix de bases ne conduisent pas à des solutions réalisables.

d) Forme standard par rapport à une base :

Soit le programme linéaire (P) suivant :

Z(max)=CX
(P) : AX=b ;
X≥0.
D’après ce qui précède et pour une base I, on a : AX=b → XI=( AI)-1b-( AI)-1(AJ)XJ
Et CX=CIXI+ CJXJ
= CI( AI)-1b-CI(AI)-1(AJ)XJ+ CJXJ
=ᴫb+(CJ-ᴫAJ) XJ, où ᴫ= CI( AI)-1 est dit vecteur multiplicateur
Donc on peut réécrire le PL (P) sous la forme :
Z(max)= ᴫb + (CJ - ᴫAJ )XJ

(Ps): XI + (AI)‒1(AJ)XJ= (AI) ‒1b

XI , XJ ≥ 0
Dite forme standard de (P) par rapport à la base I.
Exemple : soit le programme linéaire (P) suivant :

Z(max)= 2x₁+ x₂+6x₃ -2x4+5x5

(P): x1 + x₂+3x₃ - x4+4x5 = 4

x₂+2x₃ +x4+2x5 = 3

x₁, x₂, x₃, x4, x5 ≥ 0

Ecrire (P) sous forme standard par rapport à la base I ={1,2 }.
Il est clair que l’ensemble des indices des variables est N={1, 2, 3, 4, 5} et AI = (a1, a 2).
1 1
Comme la matrice AI = est inversible, alors on peut écrire le système sous la forme suivante :
0 1
1 1 x1 3 -1 4 x3 4
+ x4 =
0 1 x2 2 1 2 x5 3

En multipliant ce dernier système par (AI)-1, matrice inverse de la matrice (AI), on aura :
x3
x1 1 -1 3 -1 4 1 -1 4
+ x4 =
x2 0 1 2 1 2 x5 0 1 3

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 7

Après le calcul, on aura, x1 =1- x₃+2 x4 - 2x5

x₂ =3- 2x₃ - x4 - 2x5 ,

On remplace les deux expressions de x1 et x2 dans la fonction objectif on aura, Z(max)=2x₃+x4 - x5 +5,
d’où la forme standard (Ps) de (P) par rapport à la base {1,2} est :

Z(max)= 2x₃ +x4 - x5 +5,

x1 =1 - x₃+2x4 - 2x5

(Ps) : x₂ =3 - 2x₃ - x4 - 2x5

x1 , x₂, x₃, x4, x5 ≥0

Il est clair que le PL (Ps) possède x1=1 et x₂=3 comme solution de base réalisable associée à la base
{1,2} et Z(x1=1, x₂=3)=5.
Théorème d’optimalité : Etant donné un programme linéaire écrit sous forme standard relativement à
une base I. Si le vecteur coût C est négatif (i.e. (CJ - ᴫAJ) ≤ 0), alors la solution de base réalisable
correspondante à la base I est optimale (i.e. XJ*=(AI)-1b et XJ*=0) et la valeur de la fonction objectif
correspondante est Z*=ᴫb.
Remarque : Si le programme linéaire est de minimisation, alors le critère d’optimalité est
(CJ - ᴫAJ) ≥ 0.
Remarque : Si pour une base donnée I, la solution de base réalisable correspondante est optimale, alors
la base I est dite base optimale.

Remarque : La solution (x1=1, x₂=3) de base réalisable associée à la base {1,2} de PL (Ps) précédent
n’est pas optimale car il existe dans la fonction objectif, des cj≥0 : pour j∈J (J est l’ensemble des indices
hors base).

II. Méthode du simplexe :

On a présenté dans le chapitre précédent une procédure graphique pour résoudre un programme
linéaire à deux variables. Par contre, dans la plupart des problèmes réels, on a plus que deux variables à
déterminer. Nous décrivons ici une procédure algébrique pour résoudre les programmes linéaires avec
plus que deux variables. Cette méthode a été développée par G. B DANDZIG aux États unis en 1947, et
est appelée méthode du simplexe. L’idée de base de l’algorithme du simplexe consiste à partir d’un
point extrême X0 de l’ensemble D des solutions réalisables à se déplacer vers un point extrême X1, où la
valeur de Z(X1) est meilleure. On suppose dans l’algorithme du simplexe qu’on a une solution de base
de départ. Dans cette section, la méthode de simplexe est présentée pour les problèmes de maximisation
Z(max)=CX
(P) : AX≤b ;
X≥0.

a) Algorithme du simplexe :
(0) Mettre le PL sous sa forme standard par rapport à une base réalisable I.

(1) Déterminer les coefficients des variables hors base de la fonction objectif et poser cs=maxj∊J{cj}.

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 8

 i) Si cs ≤0, stop la solution de base correspondante est optimale.
ii) Si cs >0, aller en (2).
(2) Examiner la colonne As.
i) Si {i / Ais >0}=Ø, stop le PL na pas de solution finie.
ii) Si {i / Ais >0}≠Ø, alors soit K={k /( bk\Aks)=min( bi\Ais) pour i=1,…,m}.

Choisir r∊K et mettre à nouveau le PL sous forme standard par rapport à la nouvelle base
I=I-{r}+{s} et aller en (1).

Remarque : Pour un problème de minimisation, l’étape (1) de l’algorithme de simplexe devient :

(1) Déterminer les coefficients des variables hors base de la fonction objectif et poser cs=minj∊J{cj}.
(i) Si cs ≥0, stop la solution de base correspondante est optimale.
(ii) Si cs <0, aller en (2).

b) Illustration de la méthode sur un exemple :

Soit le programme linéaire suivant :
Z(max)= x₁+2x₂

-3x1 +2 x₂≤2

(P): -x1 +2 x₂≤4

x1 + x₂≤5

x₁, x₂ ≥ 0

Forme standard de maximisation :

Z(max)= x₁+2x₂

-3x1 +2 x₂+x3 =2

(P): -x1 +2 x₂ + x4 = 4
x1 + x₂ + x5 = 5
x₁, x₂, x3, x4, x5 ≥ 0

Il est clair que {3,4,5} forme une base réalisable de départ (ce qui est en bleu dans le tableau), d’où les
variables hors base x1 =x₂=0 et x3=2, x4=4, x5 =5 et Z*=0. La solution (0, 0, 2, 4, 5) n’est pas optimale
car d’après le théorème d’optimalité il existe au moins un élément dans le vecteur (CJ - ᴫAJ) qui est
positif (on a le 1 et le 2).

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 9

 VB x1 x₂ x3 x4 x5 b k=cp/Lp
x3 -3 2 1 0 0 2 2/2=1 Lp
x4 -1 2 0 1 0 4 4/2=2 ligne pivot
x5 1 1 0 0 1 5 5/1=5
-Z 1 2 0 0 0 0

Cp colonne pivot
colonne pivot

Variable entrante (colonne pivot) : On a max (coeff (Z))=2>0, donc x2 est la variable entrante.
Variable sortante (ligne pivot) : On a min(k>0), min(1, 2, 5)=1, donc x3 est la variable sortante.
Lp∩Cp = l’élément pivot=2.

On met à nouveau le PL sous forme standard par rapport à la base nouvelle base {2, 4, 5}, on aura le
tableau suivant

VB x1 x₂ x3 x4 x5 b k=cp/Lp
x2 -3/2 1 ½ 0 0 1
x4 2 0 -1 1 0 2 2/2=1 Lp
x5 5/2 0 -½ 0 1 4 4/(5/2)=8/5
-Z 4 0 -1 0 0 -2

Cp

La solution (0, 1, 0, 2, 4) n’est pas optimale car d’après le théorème d’optimalité il existe au moins un
élément dans le vecteur (CJ - ᴫAJ) qui est positif (on a uniquement le 4). Donc on cherche d’avoir une
solution de base réalisable meilleure.

Variable entrante (colonne pivot) : On a max (coeff (Z))=4>0, donc x1 est la variable entrante.
Variable sortante (ligne pivot) : On a min (k>0), min (1, 8/5)=1, donc x4 est la variable sortante.
Lp∩Cp = l’élément pivot=2.

On met à nouveau le PL sous forme standard par rapport à la base {2, 1, 5}, on aura le tableau suivant

VB x1 x₂ x3 x4 x5 b k=cp/Lp
x2 0 1 -¼ ¾ 0 5/2
x1 1 0 -½ ½ 0 1
x5 0 0 ¾ -5/4 1 3/2 (3/2)/(3/4)=2
-Z 0 0 1 -2 0 -4

VB x1 x₂ x3 x4 x5 b k=cp/Lp
x2 0 1 0 ⅓ ⅓ 3
x1 1 0 0 -⅓ -⅔ 2
x3 0 0 1 -5/3 4/3 2
-Z 0 0 0 -1/3 -4/3 -8

Il est clair d’après le tableau final que tous les cj : j∊J sont négatifs, alors la solution actuelle est
optimale avec Z*=8 et x1=2, x2=3.
Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 10
Résumé de la procédure de la méthode du simplexe
Dans le cas d'un problème de maximisation sous contraintes  et avec un second membre positif :

Etapes Justification
1. Formuler un programme linéaire pour le Pour obtenir une représentation mathématique du
problème réel. problème
2. Vérifier que le second membre du Ceci est nécessaire pour obtenir comme variable
programme linéaire est positif de base initiale l’origine
3. Ecrire le programme linéaire sous une Mettre toutes les contraintes sous forme d’égalité
forme standard
4. Construire le premier tableau de simplexe Ce tableau correspond à la solution initiale de
base
5. Choisir comme variable entrante dans la La valeur de cj-zj indique la quantité
base celle qui admet le plus grand effet net d’augmentation de la fonction objectif si on
positif cj-zj. augmente la valeur de xj d’une unité.
6. Choisir la variable sortante de la base celle La plus petite valeur de bi/aij indique le nombre
qui admet le plus petit ratio supérieur à zéro. maximal d’unité de xj qu’on peut introduire avant
que la variable de base de l’ième ligne ne soit
égale à zéro.
7. Construire le nouveau tableau en utilisant la Cette règle nous permet entre autre de calculer les
règle de pivot valeurs des nouvelles variables de décision
8. Faire le test d’optimalité. Si Si (cj-zj)  0 alors on n’a pas d’intérêt à faire
(cj-zj)  0 pour toutes les variables (hors entrer dans la base aucune de ces variables. Une
base), la solution obtenue est donc optimale. telle introduction engendra une diminution de la
Sinon retourner à l’étape 5. fonction objectif.

III. Méthode des deux phases :

a) Initialisation à la méthode des deux phases :

L’application de la méthode du simplexe nécessite la connaissance d’une solution de base

réalisable ce qui n’est pas toujours évident. La méthode des deux phases consiste à créer
artificiellement une solution de base réalisable initiale.

Soit (P) un PL écrit sous sa forme standard. On associe à (P) le programme auxiliaire (PA)
suivant :

Z(max)=CX Z(max)=CX
(P) : AX=b ; (PA) : AX+IV=b ;
X≥0. ψ(min)=Ʃivi,
X≥0, V≥0
Tels que : I : est la matrice d’identité et V : est le vecteur des variables artificielles vi.
Théorème : Si (X ,V ) est une solution optimale de (PA) telle que les vi = 0 ∀i, alors X* est une
* *

solution réalisable de base pour (P).

Lemme : Soit (X*,V*,Z) une solution optimale de (PA). Si ψ>0, alors le PL (P) n’admet pas de solution.

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 11

Théorème : Etant donné un programme linéaire (P), alors :
- S’il admet une solution réalisable, alors il admet une solution réalisable de base.
- S’il admet une solution optimale, alors il admet une solution optimale de base.
- S’il admet une solution réalisable et si la fonction objectif est bornée, alors il admet une solution
optimale de base.

Méthode des deux phases :

Soit le PL suivant :
Z(max)=CX
(P) : AX ≤ b ;
X≥0.
Phase 1 :
- Mettre le PL (P) sous sa forme standard.
- Multiplier par (-1) les équations dont les bi<0.
- Associer à (P) le problème auxiliaire (PA) en ajoutant un minimum de variables artificielles.
- Ecrire PA sous sa forme standard par rapport à une base réalisable.
- Appliquer l’algorithme du simplexe au (PA) en supprimant les variables artificielles.
- Soit ψ le minimum de la fonction objectif de (PA).
Cas 1 : Si ψ >0, alors le domaine des solutions réalisables de P, D(P) est vide et le PL (P)
n’admet pas de solution.
Cas 2 : Si ψ =0, alors faire sortir les variables artificielles de la base en appliquant la procédure
suivante :

Soit vr une variable artificielle de base. Effectuer un pivotage faisant sortir le vr et entrant une
variable xi.

Phase 2 :
Appliquer l’algorithme du simplexe à (P) sous sa forme obtenue à la fin de la première phase.

b) Illustration de la méthode sur des exemples :

Soit les exemples suivants :
Exemple 1 :
Z (max) = x1 + 2 x2
3x1 + x2 − x3 =6
(P) :
x1 + 3x2 + x4 = 10
x1 , x2 , x3 , x4  0
Phase 1 : On associe à (P) son problème auxiliaire (PA) suivant :

Z (max) = x1 + 2 x2 3x1 + x2 − x3 + = 6
3x1 + x2 − x3 + = 6 x1 + 3x2 + x4 = 10
(PA) : x1 + 3x2 + x4 = 10 ≡ x1 + 2 x2 − Z = 0
 (min) =  - 3x1 − x2 + x3 − = −6
x1 , x2 , x3 , x4  0,   0 x1 , x2 , x3 , x4  0,   0

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 12

On applique l’algorithme du simplexe pour le (PA), on aura :

VB x1 x₂ x3 x4 v b
v 3 1 -1 0 1 6
x4 1 3 0 1 0 10
-Z 1 2 0 0 0 0
-ψ -3 -1 1 0 0 -6
x1 1 1/3 -1/3 0 1/3 2
x4 0 8/3 1/3 1 -1/3 8
-Z 0 5/3 1/3 0 -1/3 -2
-ψ 0 0 0 0 1 0

On a d’après le tableau final, ψ*=0, d’où la solution de base actuelle (x1, x2 ,x3, x4) = (2,0,0,8) est
optimale pour le PL (PA) et est réalisable pour le PL (P), mais elle n’est pas optimale, car les
coefficients de la fonction Z sont positifs.

Phase 2 : On réapplique l’algorithme du simplexe à (P) sous sa forme obtenue à la fin de la phase 1, on
aura :

VB x1 x₂ x3 x4 b
x1 1 1/3 -1/3 0 2
x4 0 8/3 1/3 1 8
-Z 0 5/3 1/3 0 -2
x1 1 0 -3/8 -1/8 1
x2 0 1 1/8 3/8 3
-Z 0 0 1/8 -5/8 -7
x1 1 3 0 1 10
x3 0 8 1 3 24
-Z 0 -1 0 -1 -10

D’où la solution optimale est X*= (10,0,24,0) et Z*=10.

Exemple 2 :
Z (max) = 2 x1 + x 2
x1 + x 2 + x3 = 1
(P) :
x 2 + x3 = 1
x1  0, x 2  0, x3  0,

Phase 1 : On associe à (P) son problème auxiliaire (PA) suivant :

x1 + x2 + x3 + 1 = 1 x1 + x2 + x3 + 1 = 1
x2 + x3 + 2 = 1 x2 + x3 +  2 = 1
(PA) : 2 x1 + x2 − Z = 0 ≡ 2 x1 + x2 − Z = 0
 (min) =  1 + v 2 − x1 − 2 x2 − 2 x3 − = −2
x1 , x2 , x3  0, v1 , v2  0 x1 , x2 , x3  0, v1 , v2  0

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 13

On applique l’algorithme du simplexe pour le (PA), on aura :

VB x1 x₂ x3 v1 v2 b
v1 1 1 1 1 0 1
v2 0 1 1 0 1 1
-Z 2 1 0 0 0 0
-ψ -1 -2 -2 0 0 -2
x2 1 1 1 / 0 1
v2 -1 0 0 / 1 0 Oter la variable
-Z 1 0 -1 / 0 -1 artificielle
de la base optimale
-ψ 1 0 0 / 0 0
x2 0 1 1 / / 1
x1 1 0 0 / / 0
-Z 0 0 -1 / / -1
-ψ 0 0 0 / / 0

On a d’après le tableau final ψ*=0, d’où la solution de base actuelle (x1, x2 ,x3) = (0,1,0) est optimale
pour le PL (PA) et est optimale pour le PL (P) (avec Z*=1) car tous les coefficients des variables hors
base de la fonction objectif Z sont négatifs (ie. le vecteur C≤0).

Exemple 3 :
Z (max) = x1 + x 2 + x3 + x 4
x1 + 2 x 2 + x3 = 2
(P) : x1 + x 2 + 5 x3 = 12
x1 + 2 x 2 + 6 x3 + x 4 = 13
x1 , x 2 , x3 , x 4  0,

Phase 1 : On associe à (P) son problème auxiliaire (PA) suivant :

x1 + 2 x2 + x3 +  1 = 2
x1 + x2 + 5 x3 +  2 = 12
x1 + 2 x2 + 6 x3 + x4 = 13
(PA) :
- x2 − 5 x3 − Z = −13
 = v1 + v2
x1 , x2 , x3 , x4  0, v1 , v2  0

Et ceci implique que :

x1 + 2 x2 + x3 +  1 = 2
x1 + x2 + 5 x3 +  2 = 12
x1 + 2 x2 + 6 x3 + x4 = 13
(PA) :
- x2 − 5 x3 − Z = −13
- 2 x1 − 3 x2 − 6 x3 − = 14
x1 , x2 , x3 , x4  0, v1 , v2  0

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 14

On applique l’algorithme du simplexe pour le (PA), on aura :
VB x1 x₂ x3 x4 v1 v2 b
v1 1 2 1 0 1 0 2
v2 1 1 5 0 0 1 12
x4 1 2 6 1 0 0 13
-Z 0 -1 -5 0 0 0 -13
-ψ -2 -3 -6 0 0 0 -14
x3 2
v2 2
x4 1
-Z -3
-ψ 4 9 0 0 6 0 -2

Il est clair que la solution de base actuelle est optimale pour le PL (PA) (contraintes d’optimalité sont
vérifiées), avec un ψ* >0. Donc le problème (P) n’admet pas de solution réalisable car son domaine de
solutions réalisables D(P) est vide.

IV. La notion de dualité :

La dualité est un concept fondamental en programmation linéaire et conduit à un résultat de grande
portée théorique et pratique.

a) Dual d’un problème de la PL :

Définition : Soit donné un PL mis sous sa forme canonique :

Z (max) = CX
(P) : AX  b,
X  0,
Avec : X est un vecteur colonne de ℝn , C est un vecteur ligne de ℝn ,
b est un vecteur colonne de ℝm; A : m×n.

On lui associe un autre problème de la PL (D) dit dual de (P) ((P) est dit primal).

W (min) = Yb
(D) : YA  C, ; avec Y∈ℝm : vecteur ligne des variables duales.
Y  0,

b) Définition du dual dans le cas général.

Primal (Dual) Dual (Primal)

Fonction objective (Max) | Fonction objective (Min)
i`eme contrainte ≥ i`eme variable ≤ 0
i`eme contrainte ≤ i`eme variable ≥ 0
i`eme contrainte = i`eme variable <(>) 0
j`eme variable ≥ 0 j`eme contrainte ≥
j`eme variable ≤ 0 j`eme contrainte ≤
j`eme variable <(>)0 j`eme contrainte =

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 15

Remarque : Le dual du dual est le primal.
Preuve : En effet, on peut réécrire le dual (D) sous cette forme :

W (min) = Yb − W (max) = Y (−b) = −b t Y t

(D) : YA  C, ceci implique que (D) : − A t Y t  −C t ,
Y  0, Y  0,

Donc le dual de (D) est :

Z ' (min) = X t (−C t ) = −CX Z (max) = CX

(D(D)) : X t (−A t )  −b t , → (D(D)) ≡ (P) : AX  b,
X t  0, X  0,

Théorème de dualité : Soit le problème linéaire suivant :

Z (max) = CX
(P) : AX = b,
X  0,

Son dual est le programme linéaire suivant :

W (min) = Yb
(D) : YA  C,
Y qcq

Exemple : Soit le PL Primal suivant :

Z (max) = 4 x1 + 6 x2 + 20 x3 + 17 x4
x1 + x3 + 2 x4  10
(P) :
x2 + 2 x3 + x4  4
x1 , x2 , x3 , x4  0,

Son dual est le PL suivant :

W (min) = 10 y1 + 4 y2
y1 4
y2  6
(D) :
y1 + 2 y2  20
2 y1 + y2  17
y1 , y2  0

Proposition : Etant donné deux PLs duaux (P) et (D). Pour toute solution réalisable X de (P) et pour
toute solution réalisable Y de (D) on a CX≤ Yb.
Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 16
Peuve : On a X≥0, Y≥ 0, AX≤b et YA ≥C, d’où CX ≤ YAX ≤ Yb et donc CX ≤ Yb.

Proposition : Soient X et Y deux solutions réalisables de (P) et (D), respectivement. Si CX=Yb, alors X
et Y sont optimales de (P) et (D), respectivement.

Proposition : Etant donnés deux programmes linéaires duaux. On a toujours l’un des trois cas
exclusifs :
1) Les deux programmes ont des solutions optimales finies X* et Y* telles que CX*=Y*b.
2) L’un des deux problèmes n’a pas de solutions réalisables et l’autre a des solutions réalisables
mais pas de solutions optimales finies (i.e non bornée).
3) Aucun des deux n’a de solutions réalisables.

Exemples :

Cas 1 : Soient les deux problèmes duaux suivants :

(Primal) (Dual)
Z (max) = x1 + x2 W (min) = y1
- x1 + x2 = 1 − y1 + y2  1
(P) : 1 (D) : 1
x1 − x2 = 0 y1 − y2  1
2 2
x1 , x2  0, y1 , y2 qcq

On a X*=( x1* , x2* )=(1,2) est réalisable avec Z*=3, et Y*=(y1, y2)=(3,4) est réalisable avec W*=3. Ces
deux solutions sont optimales de (P) et (D) respectivement (car on a CX*= x1* + x2* =3=Y*b= y1* =3).

Cas 2 : Soient les deux problèmes duaux suivants :

(Primal) (Dual)
Z (max) = - x1 + x2 W (min) = y1
- x1 + x2 = 1 − y1 + y2  −1
(P) : (D) :
x1 − x2 = 0 y1 − y2  1
x1  0, x2  0, y1 , y2 qcq

Il est clair que le primal n’a pas de solutions réalisables et le dual a une infinité de solutions réalisables :
En effet y1-y2=1. Si y1 =d, alors y2=d-1. Si d→-∞, alors W* =y1→-∞, et on obtient un W aussi négatif
que l’on veut (W non bornée).

Cas 3 : Soient les deux problèmes duaux suivants :

(Primal) (Dual)
Z (max) = x1 + x 2 W (min) = y1
- x1 + x 2 = 1 − y1 + y2  1
(P) : (D) :
x1 − x 2 = 0 y1 − y2  1
x1  0, x 2  0, y1 , y2 qcq

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 17

(P) ne possède pas de solutions (D) ne possède pas de solutions
Nous allons maintenant donner une condition nécessaire et suffisante pour que deux solutions
réalisables X et Y soient optimales. Cette condition sera utilisée dans certaines techniques de résolution
de problèmes de programmation linéaire (méthode primal-dual). Etant données les deux PLs duaux
suivants :

Z (max) = CX W (min) = Yb
(P) : AX  b, (D) : YA  C,
X  0, Y  0,

Théorème faible des écarts complémentaires (E.C) : Soient X et Y deux solutions réalisables de (P)
et (D) respectivement. X et Y sont optimales si et seulement si :
n
yi (bi −  aijxj ) = 0, pour i=1,..,m.
j =1
Et
m
( aijyj − cj ) xj = 0, pour j=1,...,n.
i =1

Exemple : Soient les deux PLs duaux suivants :

(Primal) (Dual)
W (min) = 10 y1 + 4 y2
Z (max) = 4 x1 + 6 x2 + 20 x3 + 17 x4 y1 4
x1 + x3 + 2 x4  10 y2  6
(P) : (D) :
x2 + 2 x3 + x4  4 y1 + 2 y2  20
x1 , x2 , x3 , x4  0, 2 y1 + y2  17
y1 , y2  0

Après la résolution des deux PLs on aura, les solutions optimales : X*= (2,0,0,4) et Y*= (4,9) de (P) et
(D), respectivement, avec Z*= W*=76. On peut vérifier les conditions du théorème des E.C :
n
Si (bi −  aijxj ) 0, alors yi* = 0,
j =1
n
Si yi*  0, alors (bi −  aijxj ) = 0,
j =1
m
Si ( aijyj − cj ) 0, alors x*j = 0,
i =1
m
Si x*j 0, alors ( aijyj − cj ) = 0,
i =1

Pour le PL (D) la troisième contrainte y1 + 2 y2  20 , correspond à la variable x3 dans (P). On peut

vérifier facilement que y1* + 2 y2* = 4 + 2(9) = 22  20 , Ceci implique forcement que x3* = 0, et c’est le
cas car x3* = 0 .

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 18

 V. Complément à l’algorithme du simplexe

a) Algorithme dual du simplexe :

Z (max) = CX
Soit le programme linéaire (P) : AX  b, , écrit sous forme standard par rapport à une base
X  0,

non forcément réalisable càd le vecteur b n’a pas toutes ses composantes positives ou nulles, mais le
vecteur C ≤ 0.

Exemple : Soit le PL (P) suivant :

Z (min) = x1 + x2 Z ' (max) = − x1 − x2

3 x1 + x2  4 − 3x1 − x2 + x3 = −4
(P) : ≡ (P) :
x1 + 4 x2  5 − x1 − 4 x2 + x4 = −5
x1 , x2  0. x1 , x2 , x3 , x4  0.

On dit que (P) est dual réalisable car C ≤ 0. Au lieu de mettre en œuvre la méthode des deux
phases pour rendre (P) primal réalisable (phase 1) et ensuite appliquer la phase 2, on applique
l’algorithme dual du simplexe qui va préserver la duale réalisabilité à chaque itération càd C ≤ 0 restera
vérifiée ( comme pour le simplexe qui préserve la primale réalisabilité b ≥ 0), pour aboutir au terme
d’un certain nombre de pivotage à la forme à la fois primale et duale réalisable, càd (P) écrit sous forme
standard par rapport à une base réalisable et donc optimale. On commence par choisir un indice r pour
lequel br < 0. Si un tel indice n’existe pas, la base courante est évidement optimale à cause de C ≤ 0.

Désignons par s l’indice de la colonne sur laquelle nous allons effectuer le pivotage (pour le
moment inconnue). Pour que le pivotage soit possible, il faut que Ars  0 . Après pivotage le second
b
membre de la rème équation est br ' = rs . Comme nous souhaitons que br ' soit positif nous allons
Ar
imposer que Ars  0 . Si les coefficients de la rème ligne sont tous positifs ou nuls, un tel pivotage est
impossible et on peut conclure que le PL ne possède pas de solution. Rappelons que :
N={1,2,…,n} : est l’ensemble des indices des variables du PL,
I ={1,2,…,m} : Les indices des variables de base.
J=N-I sont les indices des variables hors base.

Algorithme dual du simplexe (pour un problème de maximisation):

1) Déterminer une base I telle que Cj≤0, j∊J i.e une solution duale réalisable.
2) Tester X I = ( AI ) −1 b
a) Si X I  0 , alors X I est une solution optimale du primale.
b) Sinon il existe un i  I / xi  0 . Soit I '  I l’ensemble des indices tels que xi  0 ,
Aller en (3).
3) Considérer A I ' :

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 19

 a) Si au moins pour un i  I ' , tous les Ai j  0 , alors le primal n’a pas de solution.
b) Si pour chaque i  I ' , au moins un Ai j  0 , alors aller en (4).

4) Déterminer :
a) xr = imin
/ xi 0
( xi ) (xi ou bien bi dans le tableau du simplexe) critère de sortie

(ligne pivot).
cs cj
b) = min ( ) critère d’entrée (colonne pivot).
Ar s
j / Arj 0 Arj

Aller en (5).

5) Considérer la nouvelle base obtenue I = I − r+ s. Mettre (P) sous sa forme standard
par rapport à I et aller en (2).

b) Illustration de l’algorithme sur un exemple :

Soit le PL (P) suivant :

Z (min) = x1 + x2 Z ' (max) = − x1 − x2

3 x1 + x2  4 − 3x1 − x2 + x3 = −4
(P) : ≡ (Ps) :
x1 + 4 x2  5 − x1 − 4 x2 + x4 = −5
x1 , x2  0. x1 , x2 , x3 , x4  0.

VB x1 x₂ x3 x4 b
x3 -3 -1 1 0 -4
x4 -1 -4 0 1 -5
-Z’ -1 -1 0 0 0
x3 -11/4 0 1 -¼ -11/4
x2 ¼ 1 0 -¼ 5/4
-Z’ -¾ 0 0 -¼ 5/4
x1 1 0 -4/11 1/11 1
x2 0 1 1/11 -3/11 1
-Z’ 0 0 -3/11 -2/11 2

Donc la solution X * = ( x1* , x2* ) = (1,1) est primale et duale réalisable, alors elle est optimale avec
Z '* = −2 , d’où Z * = 2 .

Optimisation linéaire : N. Meddah, MCB en mathématiques appliquées Page 20