2.

La Programmation Linéaire
2.1. Introduction
Beaucoup de décisions majeures dans une entreprise
sont centrées autour de la meilleure manière d’atteindre
les objectifs de l’entreprise sujette aux restrictions
occasionnées par l’environnement opérationnel sur le
manager d’entreprise.
Les restrictions peuvent prendre la forme de ressources
limitées, telles que le temps, la main-d’œuvre, l’énergie,
le matériel, ou l’argent; elles peuvent être aussi sous la
forme de directives restrictives.

1
En général, l’objectif le plus fréquent pour les
entreprises est de faire le plus de profit possible,
c’est-à-dire de maximiser un profit. Par contre
l’objectif des services organisationnels individuels
dans une entreprise est de souvent de minimiser
le coût.
Lorsqu’un manager essaie de résoudre un type
quelconque de problème en recherchant un
objectif qui est sujet aux restrictions, la technique
de la science du management qui est
habituellement utilisée est la programmation
linéaire (PL).

2
Il y a trois étapes dans l’application de la P.L.
1) Le problème doit être identifié comme
pouvant être résolu par la P.L.
2) Le problème non structuré (brut) doit être
formulé comme un modèle mathématique.
3) Le modèle doit être résolu en utilisant des
techniques mathématiques établies.
La technique de la P.L. tire son nom au fait que les
relations fonctionnelles dans le modèle
mathématique sont linéaires et la technique de
solution consiste en des étapes mathématiques
prédéterminées, c’est-à-dire, un programme.

3
Exemple de problème de P.L.: Exemple 1
Une usine produit deux types de ciments
rapportant 25 000 F et 35 000 F/tonne. Pour
produire une tonne de ciment 1, il faut 40
minutes de calcination dans un four à chaux et 20
minutes de broyage. Pour fabriquer une tonne de
ciment 2, il faut 30 minutes dans le four à chaux
et 30 minutes de broyage. Le four et l’atelier de
broyage sont disponibles 6 h et 8 h par jour.
Quelle quantité de ciment de chaque type peut-
on produire par jour pour maximiser le bénéfice?

4
Modélisation du problème par la P.L.
Soient x1 et x2 les quantités à produire des deux
ciments.
Max Z = 25000x1 + 35000x2 (1)
40x1 + 30x2  360 (2)
20x1 + 30 x2  480 (3)
X1, x2 0 (4)

La ligne (1) représente le profit total Z qui est le

critère à optimiser; Z est appelé aussi fonction
objectif, fonction de coût ou fonction
économique.

5
Max signifie que ce critère doit être maximisé,
on mettrait Min pour minimiser.
Les lignes suivantes désignent les contraintes.
La contrainte (2) concerne la disponibilité du
four: elle stipule que le temps total de
calcination requis par les ciments ne doit pas
dépasser 360 minutes (6h). La contrainte (3)
décrit de même la disponibilité du broyeur.
Les contraintes (4) précisent le domaine des
variables x1 et x2, appelées variables de
décision (ou variables décisionnelles).

6
 2.2. Formulation générale d’un problème de P.L.
En général, on appelle programme
mathématique un problème d’optimisation d’une
fonction objectif de plusieurs variables en
présence de contraintes. Le programme est dit
linéaire si la fonction et les contraintes sont
toutes des combinaisons linéaires de variables. Il
a la forme générique suivante:
Max ou Min Z = cjxj ; avec j = 1, …,n (1)
Sujet à:
aijxj , = ou  bi ;  i = 1, 2, …, m (2)
xj  0 ;  j = 1, 2, …, n (3)
7
Le programme linéaire (PL) comporte n
variables non négatives (3), m contraintes
d’égalité ou d’inégalité (2) ou contraintes
fonctionnelles (contraintes ne portant pas sur
la non-négativité des variables), et la fonction
objectif à optimiser (1).
cj : coefficient de coût ou de profit de la
variable xj;
aij: coefficient de coût ou de profit de la
variable xj dans la contrainte i;
bi: second membre constant de la contrainte i.

8
Des valeurs de variables qui vérifient toutes les contraintes
forment une solution réalisable (SR) du PL. Une solution est
optimale si aucune autre solution n’a un profit supérieur.

Extension d’un PL
Un PL en variables continues (variables réelles) est
simplement dit programme linéaire.
Si variables astreintes à être entières: PL en nombres entiers
(PLNE).
Si variables uniquement deux valeurs 0 et 1: PL en 0-1; ces
variables sont dites booléennes, binaires ou de décision.
Si à la fois variables continues et variables entières: PL mixte.
On a affaire à un programme non linéaire (PNL) à partir du
moment où au moins une contrainte ou la fonction objectif
n’est plus une combinaison linéaire de variables.
9
2.3. Formes matricielles classiques et
conversions
On écrire un PL sous forme matricielle.
Deux formes sont courantes:
- la forme canonique avec des contraintes  ,
utilisée pour la résolution graphique,
- la forme standard avec égalités, pour la
résolution algébrique par des algorithmes.

10
Forme canonique Forme standard
Max c.x Max c.x
sujet à: sujet à:
A.x  b A.x = b
x0 x0

avec:
x = (x1, x2, …, xn)T, le vecteur des variables;
b = (b1, b2, …, bm)T, le vecteur des 2nds membres des
contraintes;
c = (c1, c2, …, cn), les coûts ou profits associés aux
variables;
A: matrice mn des aij.
11
Dans la réalité, un PL peut comporter à la fois des
égalités et des inégalités.
On convertir une inégalité en égalité en ajoutant ou en
soustrayant une variable d’écart ei  0, propre à
chaque contrainte i.
aijxj  bi et ei  0  aijxj + ei = bi ; j = 1, 2, …, n

On peut passer d’une maximisation à une

minimisation. En effet, maximiser Z revient à minimiser
–Z. On a:
MaxZ = - Min(-Z)

N.B. Ne pas oublier dans ce cas de multiplier par -1 la

valeur de la fonction objectif trouvée par la
minimisation.
12
2. 4. Hypothèses de la programmation linéaire
Pour résoudre un problème de PL, on suppose les hypothèses
suivantes:

1) Proportionnalité
Le terme linéaire ne signifie pas seulement que les fonctions
dans les modèles sont tracées comme des lignes droites; il
signifie aussi que les relations montrent une proportionnalité.
S’il n’y a qu’une seule variable active xk (xj = 0, jk) alors:
• Z = ckxk
• la quantité de ressource i utilisée = aikxk
Il y a proportionnalité des coûts et des consommations de
ressources aux intensités d’activités (xk).

13
2) Additivité
La programmation linéaire nécessite aussi que les termes de la
fonction objectif et les termes des contraintes soient additifs.
L’additivité des consommations de ressources signifie qu’il n’y a pas
d’interactions entre activités.

3) Divisibilité
Les valeurs des solutions ne peuvent pas être limitées aux valeurs
entières; les variables de décision prennent n’importe quelle valeur
fractionnaire. Les variables sont ainsi appelées à être continues ou
divisibles, à l’opposé des variables entières ou discrètes.

4) Déterminisme
Les valeurs de tous les paramètres du modèle sont supposées être
constantes et connues avec certitude. En d’autres termes, les
paramètres aij, cj et bi du modèle sont des constantes connues.
14
Dans les situations réelles, cependant, les paramètres du
modèle sont habituellement incertains, puisqu’ils reflètent
le futur aussi bien que le présent et les conditions futures
sont rarement connues avec certitude.

2. 5. Résolution graphique (ou géométrique)

Elle est possible pour un PL sous forme canonique avec n =
2 ou 3.
Exemple 2:
Calculer les quantités x1 et x2 de deux produits pour
maximiser un profit Z.
Max Z = x1 + 2x2
sujet à:
x1 + x2  6
x2  3
x1, x2  0

15
 x2

I J

Région réalisable
K
x1
O

Le domaine des solutions réalisables (région réalisable)

forme un polygone convexe. Les points O, I, J et K sont des
points extrêmes; ils représentent les solutions extrêmes
réalisables.
16
Remarques:
Les contraintes de positivité confinent les solutions dans le
quart de plan positif; chacune des autres contraintes définit
un demi-espace (un demi-plan dans notre exemple).
L’intersection de tous ces espaces forme un polygone convexe
non vide (OIJK).
Pour un nombre quelconque n de variables, on parle de
polyèdre convexe.
L’optimum x* est atteint au sommet J = (3, 3) du polyèdre. Le
coût optimal correspondant est Z* = 9.
En pratique, l’optimum est borné à cause de limites sur les
ressources. Dans un problème réel, l’absence de solution
indique en général un problème surcontraint, tandis que
l’oubli d’une contrainte peut donner un optimum non borné.
Un résolution graphique est encore possible pour trois
variables, mais très délicat au-delà. Il faut une autre méthode
de calcul: c’est le but de la résolution algébrique.

17
2. 6. Principes de la résolution algébrique
2. 6. 1. La méthode du simplexe
La méthode du simplexe est une technique
algébrique pour trouver la solution optimale
d’un PL (Dantzig, 1947). Elle se base sur un
algorithme: l’algorithme du simplexe. Cet
algorithme construit une suite de solutions de
base réalisables (SBR) de profit croissant,
jusqu’à ce qu’il n’y ait plus de gain possible.
Géométriquement, il visite une suite de
sommets adjacents du polyèdre.

18
La méthode simplexiale est composée de trois étapes: l’étape
initiale, l’étape itérative et l’étape d’arrêt.
1) Etape initiale
La méthode du simplexe commence à une solution extrême
réalisable (SER), dite solution extrême réalisable initiale
(SERI). Autrement dit, le départ s’effectue de la base évidente
formée par les variables d’écart.
2) Etape itérative
De la SERI, la méthode du simplexe avance à une meilleure
SER adjacente. Ensuite elle avance à une meilleure SER
adjacente, et ainsi de suite.
3) Etape d’arrêt
La méthode du simplexe cesse d’avancer lorsqu’elle rencontre
une SER qui est meilleure que toutes les SER qui lui sont
adjacents.
19
 A part la forme algébrique de la méthode du simplexe,
il existe la forme tabulaire qui lui est
mathématiquement équivalente et plus élégante.

2. 6. 2. Forme tabulaire de la méthode du simplexe

La forme tableau de l’algorithme du simplexe rend les
calculs plus faciles que la méthode algébrique et se
prête bien à la programmation.
On suppose un PL sous forme canonique:
Max Z = cx
sujet à:
Ax  b , b  0
x0

20
Le tableau simplexe initial de ce programme
est donné ci-dessous, une fois mis sous forme
standard.
Tableau 2.1: Tableau simplexe initial d’un PL
Variable de base Coefficient de Membre
x1 x2 … xn xn+1 … xn+m de droite
Z -c1 -c2 … -cn 0 … 0 0
xn+1 a11 a12 … a1n 1 … 0 b1
xn+2 a21 a22 … a2n 0 … 0 b2
… … … … …. … … …
xn+m am1 am2 … amn 0 … 1 bm

21
La solution de base réalisable (SBR)
correspondant au tableau 2.1 se lit directement
sans aucune nécessité de calcul. En effet, en
fixant les variables hors base égales à zéro, on a
immédiatement les valeurs des variables de base.
On voit que (0, …, 0, b1, b2, …, bm) est la solution
de base réalisable correspondant au tableau 2.1.
D’une solution de base réalisable à une autre, la
méthode du simplexe génère des tableaux
similaires au tableau 2.1. jusqu’à l’obtention d’un
tableau optimal où la SBR correspondante est la
SBR optimale.
22
2. 6. 3. Algorithme de la méthode du
simplexe sous forme tableau

1) Etape initiale
1. Introduire les variables d’écart.
2. Choisir les variables (x1, …, xn) comme
variables hors base.
3. Choisir les variables (xn+1, …, xn+m) comme
variables de base initiales.
4. Aller à l’étape d’arrêt.

23
2) Etape d’arrêt
La solution actuelle est optimale si et seulement
si tous les coefficients de l’équation (0), correspondant
à la ligne (0), sont tous non-négatifs.
1. Si tous les coefficients de la ligne (0) sont non-
négatifs, alors arrêter.
2. Sinon aller à l’étape itérative.

3) Etape itérative
Partie 1: Choix de la variable de base entrant (VBE)
1. Identifier les variables hors base (VHB) dont les
coefficients sur la ligne (0) sont négatifs.
2. Parmi les variables identifiées en (1), choisir celle qui
a le plus grand (en valeur absolue) coefficient négatif.
C’est la variable de base entrant (VBE).

24
3. Marquer la colonne correspondant à cette variable.
Nommer cette colonne: colonne pivot.

Partie 2: Choix de la variable de base sortant (VBS)

1. Identifier les lignes du tableau, à part la ligne (0),
dont les coefficients sur la colonne pivot sont
strictement positifs.
2. Pour chaque ligne identifiée en (1), diviser son
membre de droite par son coefficient sur la colonne
pivot.
3. Identifier la ligne du tableau ayant le plus le plus
petit des rapports calculés en (2). Nommer cette ligne:
ligne pivot.
4. Choisir comme variable de base sortant (VBS), la
variable de base correspondant à la ligne pivot.

25
Algébriquement, le choix de la VBS peut s’énoncer
comme suit:
xs/ase = Min (bi/aie , aie  0) ; i = 1, 2, …, m

s: indice de la VBS
e: indice de la VBE
aie: coefficient de la VBE dans l’équation i
bi: membre de droite correspondant à l’équation i.

Définition: Le nombre sur le tableau simplexe, à

l’intersection de la colonne pivot et de la ligne
pivot, est appelé le pivot.
26
Partie 3: Choix de la nouvelle solution de base
réalisable
On construit un nouveau tableau simplexe à partir du
tableau actuel.
1. Dans la colonne des variables de base, remplacer la
VBS par la VBE.
2. Amener le coefficient de la VBE à +1 dans la ligne
pivot en divisant la ligne pivot par le nombre pivot.
Soit:
Nouvelle ligne pivot = ancienne ligne pivot/pivot
3. Eliminer la VBE des autres lignes du tableau en
appliquant les transformations suivantes:
Nouvelle ligne = Ancienne ligne – [(coefficient
ancienne ligne sur colonne pivot)  (nouvelle ligne
pivot)]

27
Définition: Le pivotage est l’application des
étapes 2 et 3 de la partie 3 de l’étape itérative. On
dit alors que l’on pivote sur l’élément pivot.

Remarque: Un tableau simplexe est dit sous

forme propre lorsque le principe suivant est
respecté: toute ligne du tableau a une et une
seule variable de base dont le coefficient est égal
à +1 sur cette ligne et nul sur les autres lignes.
La méthode du simplexe ne s’applique que sur les
tableaux ayant la forme propre.

28
Exemple 2: Calcul des quantités à produire x1 et x2 de deux
produits pour maximiser un profit Z.
Max Z = x1 + 2x2
sujet à:
x1 + x2  6
x2  3
x1, x2  0
Pour construire le tableau simplexe initial, il faut convertir le
problème de la forme canonique à la forme standard. D’où:
Max Z = x1 + 2x2
sujet à:
x1 + x2 + x3 = 6
x2 + x4 = 3
x1, x2, x3, x4  0
29
Tableau 2. 2: Tableau simplexe initial
e

Variable de base Coefficient de Membre de

x1 x2 x3 x4 droite
Z -1 -2 0 0 0
x3 1 1 1 0 6
x4 0 1 0 1 3 s
Etape d’arrêt
La SBR correspondante est (0, 0, 6, 3).
L’équation (0) indique que le tableau n’est pas optimal puisque (-1)
et (-2) sont encore négatifs.
On va donc à l’étape itérative (itération 1).
Nouvelle ligne pivot (2) = (0, 1, 0, 1, 3)/1 = (0, 1, 0, 1, 3)
Nouvelle ligne (0) = (-1, -2, 0, 0, 0) - (-2) (0, 1, 0, 1, 3)
= (-1, 0, 0, 2, 6)
Nouvelle ligne (1) = (1, 1, 1, 0, 6) - (1) (0, 1, 0, 1, 3) = (1, 0, 1, -1, 3)

30
Tableau 2.3: 2ème tableau simplexe (1ère itération)

Variable de base Coefficient de Membre de droite

x1 x2 x3 x4
Z -1 0 0 2 6
x3 1 0 1 -1 3
x2 0 1 0 1 3

Etape d’arrêt
L’équation (0) a encore un coefficient négatif (-1), le coefficient de x1. La SBR (0, 3, 3, 0)
dont la valeur de la fonction objectif Z se lit directement sur le tableau est égale à 6,
n’est pas encore optimale. On continue à itérer (itération 2).
La 2ème itération conduite au tableau 2.4.

Tableau 2. 4: Tableau simplexe optimal

Variable de base Coefficient de Membre de droite

x1 x2 x3 x4
Z 0 0 1 1 9
x1 1 0 1 -1 3
x2 0 1 0 1 3
31
La solution correspondante est (3, 3, 0, 0), avec Z = 9.

Etape d’arrêt
Tous les coefficients de la ligne (0) sont positifs ou nuls; Ce
tableau simplexe est optimal. La valeur Z* correspondante, la
valeur de la fonction objectif optimale, est ainsi lue
directement sur le tableau optimale: Z* = 9. La solution
optimale est aussi lue directement. Elle est: x1* = 3, x2* = 3,
x3* = 0, x4* = 0.
On peut donc dire qu’à l’optimum, la totalité de la 1ère
ressource (x3 = x2+1 = 0) et de la 2ème ressource (x4 =
x2+2 = 0) est utilisée.

N.B.: Les variables de base ont toujours un coefficient nul

dans la ligne (0) du tableau simplexe.

32
2. 6. 4. Règle de sélection en cas de plusieurs
candidats
a) Plusieurs candidats pour variable de base entrant
On rencontre cette situation lorsqu’il existe, dans l’équation
(0), plus d’une variable hors base qui ont la même valeur du
plus grand coefficient négatif. Dans ce cas, l’une d’entre ces
variables peut être choisie arbitrairement comme variable
de base entrant et la solution optimale sera toujours
atteinte. Le nombre d’itérations dépend de ce choix.

b) Plusieurs candidats pour variable de base sortant

Le choix de la VBS peut être critique.
Selon que l’on choisisse l’un ou l’autre des candidats, il y a
risque d’entrer dans un cycle où la même série de solutions
se répèterait sans toutefois changer la valeur de Z.

33
Le problème de cycle peut être évité en utilisant la règle du
minimum lexicographique à la place du minimum des
rapports.

Définition:
1. Un vecteur u est dit lexicographiquement positif si son
1er élément non nul est positif. On note alors: u  0.
2. Le vecteur u est lexicographiquement plus grand que le
vecteur v si: u – v  0. On note alors u  v.

Dans le cas de dégénérescence d’un PL, la VBS est

déterminée en utilisant la règle minimum lexicographique
suivante: si e est l’indice de la colonne pivot, s, l’indice de la
ligne pivot est telle que:

34
 1 as1, as2, …, ase, … , asn, bs =
ase

1
Minimum lexicographique ai1, ai2, …, aie, … , ain, bi , aie  0
aie

Exemple 3
Soit le tableau simplexe suivant d’un PL:

1 2 3 4 5 6 7
Z 0 0 0 -6 20 -3 6 30
3 0 0 1 1/4 8 -1 9 0
2 0 1 0 1/2 - 12 - 1/2 3 0
1 1 0 0 0 0 1 0 1
La colonne de x4 est la colonne pivot. Les variables x2 et x3
peuvent être choisies comme VBS.

35
Le minimum lexicographique (Mlex) des lignes
associées à ces variables est donné par:
Mlex[4 (0, 0, 1, 1/4, 8, - 1, 9, 0), 2 (0, 1, 0, 1/2, -12,
- 1/2, 3, 0)]
= 4 (0, 0, 1, 1/4, 8, - 1, 9, 0)
Donc x3 est la variable de base sortant.

36
2. 7. Cas spéciaux pour l’algorithme du simplexe
2. 7. 1. Fonction objectif illimité – Optimum non
borné
Si, après avoir trouvé la VBE, disons xk, tous les
coefficients de la colonne de cette variable dans le
tableau simplexe sont négatifs ou nuls, alors, on peut
accroître à l’infini la valeur de cette variable sans
diminuer les valeurs des autres variables de base.
Accroître de zéro à l’infini la valeur de xk revient à avoir
une valeur illimitée de la fonction objectif. L’optimum
n’est pas borné, car on peut augmenter xk sans annuler
une variable hors base.
En général, cette situation se produit si le problème est
mal formulé ou s’il y a eu des erreurs de calcul.

37
2. 7. 2. Présence des contraintes d’égalité
Supposons que la contrainte i d’un PL soit de la forme:
ai1x1 + ai2x2 + … + ainxn = bi
La ligne correspondant à cette contrainte d’égalité n’aura
pas de variable indicatrice (variable avec un coefficient
égal à 1 dans cette contrainte et de coefficients nuls
partout ailleurs) dans le tableau simplexe. On introduit une
variable fictive: la variable artificielle, pour jouer le rôle de
variable indicatrice de cette contrainte. On obtient ainsi un
problème révisé où la contrainte i est devenue:
ai1x1 + ai2x2 + … + ainxn + xn+1= bi
L’objectif est de trouver une solution optimale d’un
problème révisé qui est réalisable pour le problème
d’origine. Autrement dit, une solution optimale du
problème révisé qui est telle que la valeur de la variable
artificielle soit nulle.

38
Il existe deux méthodes pour trouver une telle solution
optimale: la méthode du grand M (ou méthode de
pénalités) et la méthode de deux phases.

a) Méthode du grand M
La méthode du grand M consiste à pénaliser la variable
artificielle à ne jamais être strictement positive dans la
solution optimale, c’est-à-dire à être hors base ou de base
mais de valeur nulle. Pour cela, on affecte un grand
coefficient (- M) à la variable artificielle dans la fonction
objectif. La fonction objectif change de:
Z = c1x1 + c2x2 + … + cnxn
à Z = c1x1 + c2x2 + … + cnxn -Mxn+i
où M est un nombre positif très grand. La plus grande
valeur de Z est atteinte lorsque xn+i vaudra zéro.

39
L’introduction de xn+i dans la fonction objectif viole sa
qualité de variable de base dans la contrainte i (tableau
simplexe initial). Il faut donc la ramener dans la base
pour obtenir le premier tableau simplexe en pivotant
sur la ligne de la contrainte i et de la colonne xn+i.

Exemple 4:
Soit le PL suivant:
Max Z = 3x1 + 5x2
sujet à:
x1 4
2x2  12
3x1 + 2x2 = 18
x1, x2  0

40
Il faut introduire deux variables d’écart x3 et x4, et
une variable artificielle x5 pour obtenir le nouveau
problème:

Max Z = 3x1 + 5x2

sujet à:
x1 + x3 =4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
x1, x2 , x3, x4, x5  0

L’introduction de x5 dans la fonction objectif donne:

41
 Max Z = 3x1 + 5x2 -Mx5
sujet à:
x1 + x3 =4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
x1, x2 , x3, x4, x5  0
Soit sous forme tableau:

42
 1 2 3 4 5
Z -3 -5 0 0 M 0
3 1 0 1 0 0 4
4 0 2 0 1 0 12
5 3 2 0 0 1 18

Ce tableau n’est pas un tableau simplexe. Il faut

pivoter sur l’élément cerclé pour le rendre propre .

43
 1 2 3 4 5
Z -3M - 3 -2M - 5 0 0 0 -18M
3 1 0 1 0 0 4
4 0 2 0 1 0 12
5 3 2 0 0 1 18
On peut maintenant appliquer les itérations de la
méthode du simplexe.
1 2 3 4 5
Z 0 -2M - 5 3M + 3 0 0 -6M + 12
1 1 0 1 0 0 4
4 0 2 0 1 0 12
5 0 2 -3 0 1 6
44
Après calcul, on trouve la solution optimale suivante:
x*1 = 2; x*2 = 6, et la valeur de la fonction objectif Z* =
36.
Comme la solution optimale du problème révisé est
telle que la valeur de x5 est nulle, cette solution est
aussi optimale pour le problème initial.
En général, si la solution optimale du problème révisé
possède au moins une VA de valeur non nulle, alors le
problème initial est non réalisable.
La méthode du grand M recherche donc
simultanément une solution réalisable du problème
initial et une solution optimale du problème révisé.

45
b) Méthode des deux phases
La méthode des deux phases recherche d’abord dans la
phase 1, une solution initiale réalisable du problème
initial et dans la phase 2 une solution optimale de ce
problème.
Si à la fin de la phase 1 aucune solution réalisable du
problème initial n’est trouvée, la procédure s’arrête et
on conclut que le problème est non réalisable. Si une
telle solution existe, la procédure passe à la phase 2 et
la solution réalisable trouvée à la fin de la phase 1 est
utilisée comme solution de base réalisable pour la 2ème
phase d’application de la méthode du simplexe. La
solution optimale obtenue à la 2ème phase est une
solution de base réalisable optimale du problème
initial.

46
Phase 1
Le but de cette phase est de trouver une SBR pour le
problème initial, c-a-d d’éliminer toutes les variables
artificielles de la base ou de faire en sorte que leurs
valeurs soient nulles.
Il faut commencer par introduire une nouvelle fonction
objectif qui est la minimisation de la somme des
variables artificielles. Autrement dit on doit introduire
une nouvelle ligne: la ligne (-1), dans le tableau
simplexe.
Etant donné que la nouvelle fonction objectif est une
minimisation, il faudrait d’abord la transformer en une
fonction sous la forme maximisation en utilisant
l’identité:
Min f(x) = - Max (-f(x)) , pour toute fonction f(x).

47
La méthode du simplexe est appliquée avec cette
nouvelle ligne comme ligne de la fonction objectif. La
ligne (0) de la fonction objectif du problème initial est
considérée comme une ligne des contraintes sauf que
seule Z peut y être de base. Donc la ligne (0) ne sera
jamais candidate pour être ligne pivot.
Si le tableau optimal de la phase 1 est tel que la valeur
de la fonction objectif est nulle, cela voudra dire que
toutes les variables artificielles sont nulles et alors, le
problème initial est réalisable, c-a-d possède une
solution réalisable. Si le tableau optimal est atteint
avec une valeur non nulle de la fonction objectif, cela
signifie qu’il existe au moins une variable artificielle
dans la base de valeur non nulle, c-a-d que le problème
initial n’a pas de solution réalisable.

48
Phase 2
La phase 2 commence si à la fin de la phase 1, il existe
une SBR du problème initial. Dans ce cas, il faut
éliminer du tableau:
a) la ligne de la nouvelle fonction objectif
introduite, c-a-d la ligne (- 1).
b) les colonnes des variables artificielles
introduites.
Puis continuer la méthode du simplexe au reste du
tableau avec la ligne (0), ligne de la fonction objectif du
problème initial comme ligne de la fonction objectif du
tableau.
La solution optimale obtenue à cette phase sera bien
celle du problème initial.

49
Exemple 5
Reprenons le PL de l’exemple 4 et résolvons le par la
méthode des deux phases.
Phase 1
On introduit la fonction objectif Min W = x5. Elle est
équivalente à – Max (– W). Soit: – Max W’ = – x5 .
D’où le premier tableau simplexe:
1 2 3 4 5
W’ 0 0 0 0 1 0
Z -3 -5 0 0 0 0
3 1 0 1 0 0 4
4 0 2 0 1 0 12
5 3 2 0 0 1 18
50
En ramenant x5 dans la base, on a le 1er tableau
simplexe:

1 2 3 4 5
W’ -3 -2 0 0 1 - 18
Z -3 -5 0 0 0 0
3 1 0 1 0 0 4
4 0 2 0 1 0 12
5 3 2 0 0 1 18

51
 1 2 3 4 5
W’ 0 -2 3 0 0 -6
Z 0 -5 3 0 0 12
1 1 0 1 0 0 4
4 0 2 0 1 0 12
5 0 2 -3 0 1 6

1 2 3 4 5
W’ 0 0 0 0 1 0
Z 0 0 - 9/2 0 5/2 27
1 1 0 1 0 0 4
4 0 0 3 1 -1 6
2 0 1 - 3/2 0 1/2 3
52
Ce tableau est optimal avec la valeur de W’, c-a-d de
W nulle. Donc le problème est réalisable et on peut
passer à la phase 2.

Phase 2
La suppression de la ligne de W’ et de la colonne de
x5 donne le tableau simplexe initial de la 2ème phase
suivant:
1 2 3 4
Z 0 0 - 9/2 0 27
1 1 0 1 0 4
4 0 0 3 1 6
2 0 1 - 3/2 0 3
53
 1 2 3 4
Z 0 0 0 3/2 36
1 1 0 0 - 1/3 2
3 0 0 1 1/3 2
2 0 1 0 1/2 6

Tableau optimal de solution optimale. Donc, la

solution du problème est: x*1 = 2 et x*2 = 6, avec Z* =
36.

54
2.7.3. Présence des contraintes d’inégalité de
la forme 
S’il existe une contrainte d’inégalité de la forme:
ai1x1 + ai2x2 + …. + ainxn  bi
il suffit d’introduire une variable de surplus pour obtenir
une contrainte d’égalité:
ai1x1 + ai2x2 + …. + ainxn + xn+i = bi
On se retrouve alors dans la situation du paragraphe 2.7.2.

2.7.4. Présence des membres de droite négatifs

Si un membre de droite est négatif, multiplier les deux
membres de l’inégalité par (- 1). Le membre de droite
devient alors positif et le sens de l’inégalité passe de  à .
On se retrouvera ainsi dans la situation précédente (§
7.2.3).

55
2.7.5. Présence des variables libres
En général, dans un PL, des valeurs négatives des variables
décisionnelles n’auraient aucun sens physique. Mais
parfois, il peut arriver qu’une valeur négative d’une variable
décisionnelle soit désirée.

a) Présence des variables libres avec bornes négatives

Soit la variable xj telle que:
xj  Lj , avec Lj  0
Pour ramener à la forme standard, il faut faire la
substitution suivante:
x’j = xj – Lj
Donc x’j  0; de sorte qu’en remplaçant toutes les
occurrences de xj par x’j + Lj , on obtient un problème de PL
équivalent où toutes les variables décisionnelles seront
non-négatives.

56
Exemple 6: D’où le problème de PL
Max Z = 3x1 + 5x2 équivalent:
sujet à:
x1 4 Max Z = - 15 + 3x’1 + 5x2
2x2  12 sujet à:
3x1 + 2x2  18 x’1 9
x1  -5 2x2  12
x2  0 3x’1 + 2x2  33
x’1, x2  0
Posons:
x’1 = x1 + 5 Dans cet exemple, on
Soit: permet à x1 d’être négative,
mais avec une valeur
x1 = x’1 - 5 supérieure ou égale à -5.

57
b) Présence des variables libres sans borne négative
Si xj peut être libre mais sans borne négative, alors on peut utiliser
la transformation qui remplacerait toutes les occurrences de xj par
x’j – x’’j , où x’j et x’’j sont des variables non-négatives, l’une
représentant la partie positive de xj et l’autre sa partie négative.
Ces variables sont telles qu’à la solution optimale obtenue par la
méthode du simplexe, nous avons: x’j = Max[0, xj]; x’’j = Max[0, -xj].

Exemple 7:
Max Z = 30x1 – 4x2
sujet à:
5x1 – x2  30
x1 5
x1 0
x2 libre
58
On pose x2 = x’2 – x’’2 , où x’2 = Max[0, x2] et x’’2 =
Max[0, -x2]. On obtient le nouveau problème suivant:

Max Z = 30x1 – 4x’2 + 4x’’2

sujet à:
5x1 – x’2 + x’’2  30
x1 5
x1, x’2, x’’2  0

La solution optimale de ce problème est:

x1 = 5; x’2 = 0; x’’2 = 5
D’où les variables décisionnelles initiales:
x1 = 5; x2 = - 5

59
2.8. Théorie de la dualité
2.8.1. Définition et exemple
A tout PL, appelé par convention PL primal, on
peut associer un autre PL appelé dual.
Considérons un PL primal sous forme générale,
c-a-d non mis sous forme canonique ou standard,
et son dual. On a séparé dans ce primal les
variables positives de celles non contraintes en
signe, d’une part, et les contraintes d’égalité des
contraintes d’inégalité, d’autre part.

60
 Primal Dual
Max Z = cT1x1 + cT2x2 Min W = b1y1 + b2y2
sujet à sujet à
A1,1x1 + A1,2x2  b1 y1  0
A2,1x1 + A2,2x2 = b2 y2 de signe quelconque
x1  0 AT1,1y1 + AT2,1y2  c1
x2 de signe quelconque AT1,2y1 + AT2,2y2 = c2

61
Exemple 8: PL primal sous forme canonique
Primal Dual
Max Z = 4x1 + 7x2 Min W = 6y1 + 8y2
sujet à sujet à
3x1 + 5x2  6 3y1 + y2  4
x1 +2x2  8 5y1 + 2y2  7
x1, x2  0 y1, y2  0

On est passé mécaniquement au dual pour ce PL canonique

comme suit:
- une variable duale yi  0 est associée à chaque contrainte i du
primal.
- dans l’objectif, c est remplacé par b et le sens de l’optimisation
est inversé.
- dans les contraintes, le 2nd membre b est remplacé par c, et  est
remplacé par  .
- la matrice A est transposée.
62
2.8.2. Correspondance de forme entre le primal
et le dual

Problème primal Problème dual

(ou problème dual) (ou problème primal)
Maximiser Z (ou W) Minimiser W (ou Z)
Contrainte i Variable yi (ou xi)
forme  yi  0
forme = yi libre
Variable xj (ou yj) Contrainte j
xj  0 forme 
xj libre forme =

63
Exemple 9: Donner le PL dual du PL primal ci-après:
Max Z = 3x1 + 5x2
sujet à
x1 4
2x2  12
3x1 + 2x2  18
x1, x2  0
La notion de primal et du dual est relative, car la transformation
peut se faire dans les deux sens: le dual du dual est le primal.
L’objectif du problème dual est de minimiser la valeur implicite
totale des ressources consommées, plutôt que des ressources
allouées.
En plus la dualité est très utilisée en programmation linéaire,
notamment pour faciliter les calculs en réduisant le nombre de
variables.
64
2.8.3. Relations entre le primal et le dual
- Relation 1
Toute solution de base dans le primal a une solution de base
complémentaire dans le dual (tableau 2. 2).

Tableau 2.2. Correspondance entre solution de base du primal

et du dual
Variables primales Variables duales
- de base - hors base (m variables)
- hors base - de base (n variables)

Sur le tableau simplexe du primal, le coefficient de chaque

variable sur la ligne (0) est égal à la valeur de la variable duale
dans la solution de base complémentaire, de sorte que:
n m
Z =  cjxj =  biyi = W
j=1 i=1 65
Exemple 10
Reprenons l’exemple 9. Les tableaux simplexes successifs sont:

Variables de Coefficients de Membres de

base x1 x2 x3 x4 x5 droite
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18

Variables de Coefficients de Membres de

base x1 x2 x3 x4 x5 droite
Z -3 0 0 5/2 0 30
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
x5 3 0 0 -1 1 6
66
 Variables Coefficients de Membres de
de base x1 x2 x3 x4 x5 droite
Z* 0 0 0 3/2 1 36
x*3 0 0 1 1/3 - 1/3 2
x*2 0 1 0 1/2 0 6
x*1 1 0 0 - 1/3 1/3 2
D’où la correspondance entre solution de base du primal et
du dual:
Primal Dual
Solution de base Z=W Solution de base
(0, 0, 4, 12, 18) 0 (0, 0, 0, - 3, - 5)
(0, 6, 4, 0, 6) 30 (0, 5/2, 0, - 3, 0)
(2, 6, 2, 0, 0) 36 (0, 3/2, 1, 0, 0)

67
Les valeurs de la solution duale sont les coefficients dans l’équation
(0) de (x3, x4, x5, x1, x2), pris dans cet ordre.

Relation 2
Si (x1, x2, …, xn) est une solution réalisable du problème primal en
maximisation et (y1, y2,…, ym) une solution réalisable du problème
dual, alors:
n m
 cjxj   biyi
j=1 i=1

Relation 3
Si (x*1, x*2, …, x*n) et (y*1, y*2,…, y*m) sont des solutions optimales du
problème primal et du problème dual respectivement, alors:
n m
 cjx*j =  biy*i
j=1 i=1

68
2.9. Algorithme de la méthode du simplexe
dual

69