Université Moulay Ismail Meknès

Faculté des Sciences et Techniques Errachidia

Département : Informatique
Filière Master : Systèmes d’information décisionnels et imagerie
Module (M16) : Théorie des graphes et Techniques d’optimisation

Polycopié de cours :
Programmation linéaire

Pr. Youssef QARAAI

Email : [email protected]

2023 - 2024
Sommaire

1 Bases de la programmation linéaire 2

1.1 Définitions / Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Formulation d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . 3
1.3 Solutions en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Problème de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Résolution d’un programme linéaire 14

2.1 Approche graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Passage entre sommets . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.3 Exemples : Cas borné et non borné . . . . . . . . . . . . . . . . . . 21
2.3 Méthode des deux phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Dualité et analyse de sensibilité 30

3.1 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.1 Introduction et règles de transformation . . . . . . . . . . . . . . . 30
3.1.2 Interprétation économique . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.3 Théorèmes de la dualité . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1.4 Dualité et complémentarité . . . . . . . . . . . . . . . . . . . . . . 36
3.2 Analyse de sensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.1 Méthode du simplexe revisitée . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Variation du second membre . . . . . . . . . . . . . . . . . . . . . . 41
3.2.3 Variation du coût . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

1
Chapitre 1

Bases de la programmation linéaire

1.1 Définitions / Motivations

La programmation linéaire (PL) est un outil mathématique d’aide a la décision, elle
consiste à optimiser (minimiser ou maximiser) une fonction linéaire dite fonction éco-
nomique ou fonction objectif exprimée en fonction d’un nombre de variables appelées
variables de décisions sur un ensemble non vide obtenu à partir des contraintes du pro-
blème.
Étant donné un problème en vue de l’optimisation, pour le modéliser sous forme d’un PL,
il faut identifier soigneusement les trois éléments définis comme suit :
1. Variables de décision : Ce sont les facteurs que l’on peut modifier dans le système,
elles décrivent les inconnues du problème et représentent des quantités utiles sur
lesquelles des décisions seront prisent.
2. Contraintes : Ce sont les paramètres du système d’équations linéaires sur les va-
riables de décision, et sur lesquels on ne peut apporter aucune modification. Elles
regroupent toutes les restrictions et conditions imposées au problème posé sous
forme d’inégalités (≤, ≥) ou d’égalités (=).
3. Fonction objectif : Constitue la fonction à optimiser ou bien l’objectif à atteindre.
Elle est exprimée linéairement en fonction des variables de décision.

Remarque 1.1.1. En plus des trois éléments définis ci-dessus, la formulation d’un PL
exige une condition, dite de non-négativité des variables de décision.
Notez que cette condition ne présente aucune restriction en programmation linéaire (voir

2
1.2. FORMULATION D’UN PROGRAMME LINÉAIRE 3

l’explication dans la suite de ce chapitre).

Exemple 1.1.1. Une usine fabrique deux produits P1 et P2 nécessitant des ressources
d’équipement, de main d’œuvre et de matières premières disponibles en quantités limitées.
La fabrication d’une unité de P1 nécessite 3 heures d’équipement, 4 heures de main d’œuvre
et 2 unités de matières premières, tandis qu’une unité de P2 nécessite 9 heures d’équipe-
ment, 5 heures de main d’œuvre et 1 unité de matières premières. Les disponibilités en
équipement, main d’œuvre et matières premières sont limitées respectivement à 81, 55 et
20.
P1 et P2 rapportent à la vente 6 et 4 respectivement par unité.
Formuler le problème permettant la détermination des quantités de produits P1 et P2 que
doit produire l’usine afin de maximiser le bénéfice total venant de la vente des deux pro-
duits.
Pour formuler le PL associé, il suffit de suivre les 4 étapes mentionnées ci-dessus.
— Variables de décision xj : quantité de produit Pj fabriqué.
— Contraintes (disponibilité de chacune des ressources) :

 3x1 + 9x2 ≤ 81


4x1 + 5x2 ≤ 55

 2x + x ≤ 20

1 2

— Condition de non-négativité : x1 , x2 ≥ 0
— Fonction objectif : f (x1 , x2 ) = 6x1 + 4x2
Puisqu’on cherche à maximiser le bénéfice total, alors le PPL ainsi résultant est :



 max f = 6x1 + 4x2

 s.c 3x1 + 9x2 ≤ 81



(P ) 4x1 + 5x2 ≤ 55

≤ 20



 2x1 + x2


 et x1 , x2 ≥ 0

1.2 Formulation d’un programme linéaire

Après avoir introduit les étapes de formulation d’un problème de programmation linéaire
(PPL) en les appliquant sur l’exemple ci-dessus, nous allons donner un cadre général et
les types de formes d’un PPL.

Youssef Qaraai E-MMIS, FSTE, UMI

1.2. FORMULATION D’UN PROGRAMME LINÉAIRE 4

Forme canonique :
Tout problème de programmation linéaire peut être formulé sous la forme suivante :

max f = c1 x1 + c1 x2 + ... + cn xn = nj=1 cj xj
P




s.c a11 x1 + a12 x2 + ... + a1n xn ≤ b1





≤ b2



 a21 x1 + a22 x2 + ... + a2n xn


 .
(P )


 .

.





≤ bm



 am1 x1 + am2 x2 + ... + amn xn


 et x1 , x2 , ..., xn ≥0

Avec : cj ∈ R, j = 1, 2, ..., n coefficients (coûts) de la fonction objectif, bi ∈ R, i = 1, 2, ..., m

seconds membres, et aij ∈ R, i = 1, 2, ..., m, j = 1, 2, ..., n coefficients des contraintes.
Il s’agit d’une écriture algébrique de la forme canonique de (P ). Cependant on peut la
réécrire d’une manière équivalente sous une forme matricielle :

t
 max f = c x


(P ) s.c Ax ≤b

≥0

 et x

Avec : x, c ∈ Rn , b ∈ Rm et A ∈ Mm,n (R).

Remarque 1.2.1. Il est toujours possible de mettre un PPL sous forme canonique grâce
aux règles générales suivantes
1. On a toujours : max(f ) = −min(−f )
2. Si une variable n’est soumise à aucune condition de signe (xj ∈ R), on la remplacera
par deux variables uj ∈ R+ et vj ∈ R+ telles que xj = vj − uj
3. Si on a une contrainte du type égalité, il suffit de la transformer en double inégalités :

ax = b ⇐⇒ ax ≤ b et ax ≥ b ⇐⇒ ax ≤ b et − ax ≤ −b

Forme standard :
Les méthodes et algorithmes développés pour résoudre un PPL sont généralement basés,
non pas sur la forme canonique, mais plutôt sur ce que l’on appelle forme standard.

Youssef Qaraai E-MMIS, FSTE, UMI

1.3. SOLUTIONS EN PROGRAMMATION LINÉAIRE 5

En effet il suffit de rendre toutes les contraintes de types égalités. Un tel passage est
toujours possible, grâce à l’ajout ou à la soustraction des variables positives dites variables
d’écart. De telles variables mesurent la différence entre les deux membres des contraintes
ei = (b − Ax)i , i = 1, 2, ..., k, où k ≤ m est le nombre de contraintes de types non égalité.
Noter que m désigne le nombre total des contraintes du problème.
A partir de la forme canonique de (P ), la forme standard est donnée par

t
 max f = c x


(P ) s.c Ax =b

≥0

 et x

Avec : x, c ∈ Rn+m , b ∈ Rm mais cette fois-ci A ∈ Mm,n+m (R).

Exemple 1.2.1. La forme standard du PPL associée au problème de fabrication modélisé

ci-dessus est donnée par :



 max f = 6x1 + 4x2

 s.c 3x1 + 9x2 + x3 = 81



4x1 + 5x2 + x4 = 55




 2x1 + x2 + x5 = 20


 et x , x , x , x , x
1 2 3 4 5 ≥ 0

La forme standard présente un avantage du fait qu’on n’aura recours qu’aux contraintes de
types égalités, tandis qu’elle augmente la dimension du problème : on passe d’un problème
à n variables de décisions (principales) à un problème de n+m variables dont n principales
et m de surplus ou d’écart.

1.3 Solutions en programmation linéaire

Dans cette section nous allons introduire quelques définitions et résultats utiles dans l’étude
du comportement de la solution d’un PPL. Avec la formulation de (P ) sous une forme
standard, nous avons

Définition 1.3.1.

Youssef Qaraai E-MMIS, FSTE, UMI

1.3. SOLUTIONS EN PROGRAMMATION LINÉAIRE 6

— On appelle solution tout vecteur x vérifiant Ax = b.

— Une solution x qui vérifie Ax = b et x ≥ 0 est une solution admissible. Notons
par X = {x ∈ Rn+m : Ax = b et x ≥ 0} l’ensemble des solutions admissibles (ou
réalisables).
— A ∈ Mm,n+m est supposée de rang m. Une base est une matrice B ∈ Mm,m extraite
de A et qui est inversible.
— On appelle variables hors base les n variables de Rn+m fixées à zéro. Les m variables
restantes sont appelées variables de base.
— On appelle solution de base une solution où en ayant choisi n variables hors base,
on obtient une solution unique en résolvant les m contraintes d’égalité obtenues en
ajoutant les variables d’écart.
Notons xB les m variables de base et xN = 0 les n variables hors base.
— Une solution de base telle que xB > 0 est dite admissible.
— Si xB = 0 alors elle sera dite solution de base admissible dégénérée.

Ensuite nous allons rappeler certaines définitions liées à la convexité

Définition 1.3.2.

— Soient u et v deux points d’un domaine X. Le segment joignant u et v est défini

par l’ensemble des points w tels que w = {(1 − λ)u + λv} où λ ∈ [0, 1].
— Soient u et v deux points intérieurs de X. Alors X est convexe si le segment joignant
u et v reste dans X.
— Une fonction f est convexe sur un domaine convexe X si

f [(1 − λ)u + λv] ≤ (1 − λ)f (u) + λf (v), ∀u, v ∈ X et λ ∈ [0, 1]

— w est un sommet du domaine X si {w = (1 − λ)u + λv, λ ∈ [0, 1]} =⇒ w = u = v.

Autrement dit, un point d’un polyèdre est un sommet s’il ne peut pas être vu comme la
combinaison linéaire convexe de deux autres points du polyèdre.
Tout point d’un polyèdre peut être vu comme combinaison linéaire convexe des sommets
du polyèdre.
Cela étant, la relation existante entre cette terminologie et le programme linéaire (P ) est
assurée par le résultat fondamental suivant.

Youssef Qaraai E-MMIS, FSTE, UMI

1.4. EXEMPLES 7

Théorème 1.3.1. La solution optimale de (P ), lorsqu’elle existe, est atteinte en au moins

un sommet de l’ensemble convexe X.

Cela veut dire que parmi tous les points de l’ensemble admissible X, qui est convexe
par linéarité de A, seuls ses sommets (ou points extrêmes) qui sont accessibles d’être des
solutions optimales ; celles qui optimisent la fonction objectif f en respectant toutes les
contraintes imposées ainsi que la condition de non-négativité des variables de décision.

1.4 Exemples
Pour faire paraître l’utilité de la programmation linéaire en pratique, nous allons donner
quelques exemples de problèmes dans des domaines divers.

Exemple 1.4.1. (Agriculture)

Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et
celles de piments. Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau. Un hectare
de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un bénéfice net de 100
euros. Un hectare de piments demande 4 heures de main d’œuvre, 2m3 d’eau et donne un
bénéfice net de 200 euros.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui permet pas de
cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources ?
Réponse : Si x1 (resp. x2 ) est la surface en hectares allouée à la culture des tomates (resp.
des piments), alors le PPL associé à ce problème est formulé comme suit.



 max f = 100x1 + 200x2

≤ 150



 s.c x1 + x2


 x1 + 4x2 ≤ 480


 4x1 + 2x2 ≤ 440

x1 ≤ 90





 et x1 , x2 ≥ 0


Exemple 1.4.2. (Médecine)

Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir les sujets
atteints d’un rhume. Ces pilules sont fabriquées selon deux formats :
• Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1 grain de

Youssef Qaraai E-MMIS, FSTE, UMI

1.4. EXEMPLES 8

codéine.
• Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6 grains de
codéine.
Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate
et 24 grains de codéine. Déterminer le nombre de pilules minimales à prescrire au sujet
pour qu’il soit guérit.
Réponse : Si x1 (resp. x2 ) est le nombre de pilules de petite (resp. grande) taille, le
programme linéaire est donné par.



 min f = x1 + x2

 s.c 2x1 + x2 ≥ 12



5x1 + 8x2 ≥ 74

≥ 24



 x1 + 6x2


 et x1 , x2 ≥ 0
Exemple 1.4.3. (Sélection de Médias)
Une entreprise désire effectuer une campagne publicitaire dans la télévision, la radio et
les journaux pour un produit lancé récemment sur le marché. Le but de la campagne est
d’attirer le maximum possible de clients. Les résultats d’une étude de marché sont donnés
par le tableau suivant :

TV Locale TV par satellite Radio Journaux

Coût d’une publicité 40 75 30 15
Nombre client potentiel / publicité 400 900 500 200
Nombre client potentiel femme / pu- 300 400 200 100
blicité
Pour la campagne, on prévoit de ne pas payer plus que 800 euros pour toute la campagne
et on demande que ces objectifs soient atteints :
- Au minimum 2000 femmes regardent, entendent ou lisent la publicité,
- La campagne publicitaire dans la télévision ne doit pas dépasser 500 euros,
- Au moins 3 spots publicitaires seront assurer par la télévision locale et au moins de deux
spots par la télévision par satellite.
- Le nombre des publicités dans la radio ou dans les journaux sont pour chacun entre 5 et
10.
Réponse : Les variables de décision sont les nombres de spots ou d’affiches publicitaires.

Youssef Qaraai E-MMIS, FSTE, UMI

1.4. EXEMPLES 9

— x1 : le nombre de spots publicitaires dans la télévision locale

— x2 : le nombre de spots publicitaires dans la télévision par satellite
— x3 : le nombre de spots publicitaires dans la radio
— x4 : le nombre
 d’affiches publicitaires dans les journaux


 max f = 400x1 + 900x2 + 500x1 + 200x2

s.c 40x1 + 75x2 + 30x1 + 15x2 ≤ 800





≥ 2000




 30x1 + 40x2 + 20x1 + 10x2




 40x1 + 75x2 ≤ 500

x1 ≥ 3




x2 ≥ 2

≥



 x3 5





 x3 ≤ 10

x4 ≥ 5





x4 ≤ 10





≥

 et x ,x ,x ,x
1 2 3 4 0

Exemple 1.4.4. (Mélange d’alliages)

Un industriel veut produire un alliage Z à 30% de plomb, 30% de zinc et 40% d’étain.
Supposons qu’il puisse se procurer sur le marché des alliages A, B, C, D, E, F, G, H, I
dont les compositions et les prix respectifs sont donnés dans le tableau suivant :

Compos- ition(%) A B C D E F G H I Alliage

Plomb 10 10 40 60 30 30 30 50 20 30
Zinc 10 30 50 30 30 40 20 40 30 30
Étain 80 60 10 10 40 30 50 10 50 40
Coût/Kg 4.1 4.3 5.8 6 7.6 7.5 7.3 6.9 7.3

Combien doit-il acheter de chaque alliages A, B, C, D, E, F, G, H et I pour obtenir au

prix de revient minimum un 1 Kg de l’alliage Z ?

Youssef Qaraai E-MMIS, FSTE, UMI

1.5. PROBLÈME DE TRANSPORT 10

Réponse : xj signifie la quantité d’alliage j à acheter (j = A, B, ..., I)




 min f = 4.1xA + 4.3xB + 5.8xC + 6xD +

7.6xE + 7.5xF + 7.3xG + 6.9xH + 7.3xI









 s.c xA + xB + xC + xD +




 xE + xF + xG + xH + xI = 1

0.1xA + 0.1xB + 0.4xC + 0.6xD +




0.3xE + 0.3xF + 0.3xG + 0.5xH + 0.2xI = 0.3




 0.1xA + 0.3xB + 0.5xC + 0.3xD +





 0.3xE + 0.4xF + 0.2xG + 0.4xH + 0.3xI = 0.3

0.8xA + 0.6xB + 0.1xC + 0.1xD +





0.4xE + 0.3xF + 0.5xG + 0.1xH + 0.5xI = 0.4





≥

 et xA , xB , ..., xI 0
On note que la première équation du système de contraintes est une conséquence directe
de la loi de conservation.

1.5 Problème de transport

Le transport désigne le déplacement ou la circulation d’objets, de marchandises, ou d’in-
dividus d’un endroit à un autre. Les modes de transport incluent l’aviation, le chemin de
fer, le transport routier, le transport maritime, le transport par câble, l’acheminement de
données, etc.
Le problème général de transport sous l’hypothèse que l’offre totale est égale à la demande
totale, s’énonce comme suit. Notons les sources par S1 , S2 ,..., Sm et les destinations par
D1 , D2 ,..., Dn . On introduit les notations suivantes :
Variables de décision : xij = quantité transportée de Si à Dj ,
Coûts : cij = coût unitaire du transport de Si à Dj ,
Offres : ai = offre de la source Si , (ai ≥ 0)
Demandes : bj = demande de la destination Dj , (bj ≥ 0),
La fonction objectif : f (xij ) = m
P Pn
i=1 j=1 cij xij ,
Xn
Contraintes sur l’offre : xij = ai , ∀i = 1, 2, ..., m,
j=1
m
X
Contraintes sur la demande : xij = bj , ∀j = 1, 2, ..., n.
i=1

Youssef Qaraai E-MMIS, FSTE, UMI

1.5. PROBLÈME DE TRANSPORT 11

Ainsi le problème de transport peut être formulé comme suit :

 Pn Pn


 min f = i=1 j=1 cij xij
n



 X



 s.c xij = ai ∀i = 1, 2, ..., m
j=1
(P ) m
 X
xij = bj ∀j = 1, 2, ..., n






 i=1

 et xij ≥ 0 ∀i = 1, 2, ..., m ∀j = 1, 2, ..., n


Une condition nécessaire et suffisante pour que le problème de transport admette une
solution optimale est que
m
X n
X
ai = bj
i=1 j=1

Démonstration. Si x est une solution qui vérifie les contraintes, alors on a

n
X X m
X
xij = ai ⇒ xij = ai
j=1 i,j i=1

m
X X n
X
xij = bj ⇒ xij = bj
i=1 i,j j=1

Ceci implique
m
X n
X
ai = bj
i=1 j=1
m
X n
X
Inversement, si ai = bj = T , on pose
i=1 j=1

ai b j
xij = ≥0
T
Montrons que ce choix de x vérifie les contraintes. En effet
n n Pn
1X j=1 bj
X
xij = ai b j = ai = ai
j=1
T j=1 T

et m m Pm
X 1X ai
xij = ai bj = bj i=1 = bj
i=1
T i=1 T

Youssef Qaraai E-MMIS, FSTE, UMI

1.5. PROBLÈME DE TRANSPORT 12

De plus, l’ensemble des solutions réalisables est borné. Il suffit d’observer que, pour une
paire d’indices i et j
n
X
xij = ai ≥ 0 ⇒ 0 ≤ xij ≤ ai
j=1

Par conséquent, le problème admet une solution optimale. 

D’autre part, on peut réécrire (P ) sous une forme matricielle :


t
 min f = c x


(P ) s.c Ax =d

≥0

 et x

où x = (x11 , x12 , ..., x1n , x21 , ..., x2n , ..., xmn ) : on déroule la matrice xij suivant les lignes.
On fait de même pour c = (c11 , ..., c1n , c21 , ..., cmn ). Il y a donc n × m variables et n + m
contraintes.
Le vecteur d correspond à d = (a1 , a2 , ..., am , b1 , b2 , ..., bn ), tandis que la matrice A ∈
Mn+m,nm , elle possède les propriétés suivantes :
— Chaque colonne contient exactement deux entrées non nulles et qui sont égales à 1.
— Le rang de A est égal à m + n − 1.
— Chacune des lignes est une combinaisons linéaire des autres lignes.
— Il y a exactement m + n − 1 variables de base réalisables.

Remarque 1.5.1. Lorsque l’hypothèse d’égalité de l’offre et la demande totales n’est pas
satisfaite ; c’est à dire que le problème n’est pas mis sous forme standard, on ajoute une
destination (resp. une source) fictive et de ramener le problème au cas traité précédemment.

Exemple 1.5.1. Il s’agit de déterminer la façon optimale d’acheminer des biens à partir
de 3 entrepôts et de les transporter vers 4 destinations et cela à moindre coût.

Entrepôt Sherbrooke Drumville St-Georges Rimouski Offre

Montréal 147 $ 121 $ 344 $ 552 $ 450 T
Québec 241 $ 153 $ 102 $ 312 $ 450 T
Chicoutimi 451 $ 364 $ 557 $ 285 $ 750 T
Demande 400 T 450 T 550 T 250 T 1650 T

Youssef Qaraai E-MMIS, FSTE, UMI

1.5. PROBLÈME DE TRANSPORT 13

L’offre totale est bien égale à la demande ce qui est conforme à l’hypothèse ci-dessus.
Nous avons donc m = 3, n = 4, x, c ∈ R12 , d ∈ R7 et A ∈ M7,12 :
   
x11 147
   
 x12   121 
   
 x13   344 
     

 x14 
 
 552 
 450
 







  450 
 x21   241   
750
     
 x   153   
 22   
x= , c =   , d =  400 
  
 x23   102  


     450 
 x24   312 
     
     550 
 x31   451   
250
   
   
 x32   364 
   
 x   557 
 34   
x35 285
 
1 1 1 1 0 0 0 0 0 0 0 0
 

 0 0 0 0 1 1 1 1 0 0 0 0 

0 0 0 0 0 0 0 0 1 1 1 1 
 

 
A=
 1 0 0 0 1 0 0 0 1 0 0 0 

 
 0 1 0 0 0 1 0 0 0 1 0 0 
 

 0 0 1 0 0 0 1 0 0 0 1 0 

0 0 0 1 0 0 0 1 0 0 0 1

Youssef Qaraai E-MMIS, FSTE, UMI

Chapitre 2

Résolution d’un programme linéaire

Ce chapitre est consacré à l’introduction de quelques méthodes de résolution d’un pro-

gramme linéaire. Il existe toute une littérature abondante qui abordent ce sujet. Dans
notre cas on va se limiter uniquement à l’aspect algorithmique des méthodes introduites,
moyennant quelques résultats mathématiques avec ou parfois sans donner de démonstra-
tions.

2.1 Approche graphique

Nous avons vu dans le chapitre précédent que la solution d’un problème de programmation
linéaire, lorsqu’elle existe, elle est atteinte en au moins un sommet de l’ensemble admis-
sible. Avant d’aborder les méthodes de résolution d’un PPL dans un cas général, on peut
commencer par une technique, dite approche graphique, permettant de résoudre un PPL
lorsque le nombre de variables n est égale à 2. Le principe de cette approche consiste à :
1. Dessiner, dans un repère orthonormé, les droites définissantes toutes les m contraintes
du problèmes, ainsi que celles issues de la condition de non négativité (x1 , x2 ≥ 0),
2. Localiser les sommets de l’ensemble admissible,
3. Tester l’optimalité de la fonction objectif en ces sommets. Le test peut se faire en
évaluant f point par point, ou bien de considérer la notion des isovaleurs ou lignes
de niveaux (f (x) = constante) est faire translater ces droites parallèles jusqu’à
l’intersection des sommets optimaux (on augmente s’il s’agit de max, et en diminue
en cas de min).

14
2.2. ALGORITHME DU SIMPLEXE 15

Exemple 2.1.1. Considérons le PPL suivant




 max z = 20x1 + 30x2

 x1 + 3x3 ≤ 18



(P ) x1 + x2 ≤ 8

2x1 + x2 ≤ 14






 x ,x ≥ 0
1 2

A l’aide de cette approche, la solution optimale de (P ) est (x∗1 , x∗2 ) = (3, 5) pour laquelle
le maximum de z vaut z ∗ = 210

2.2 Algorithme du simplexe

Même si avec sa simplicité et son efficacité lors de la résolution d’un programme linéaire,
l’approche graphique présente une restriction majeure au niveau de la dimension du PPL
considéré (n = 2 ou 3). Dans cette section nous décrivons un algorithme permettant de
surmonter cette restriction, vu le fait que la majorité des problèmes étudiés font inter-
agir plusieurs variables de décision. Il s’agit du fameux algorithme dit du simplexe. Son
fonctionnement nécessite le respect de certaines étapes décrites ci-dessous.

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 16

2.2.1 Passage entre sommets

Soit A une matrice d’ordre m×n supposée de rang m et b ∈ Rm . On notera les colonnes de
A par [a1 , a2 , ..., an ]. D’après ce qui précède, on sait que la solution optimale du problème
d’optimisation linéaire suivant :

t
 max z = c x


(P ) s.c. Ax = b

 et x ≥ 0


se trouve en un sommet de l’ensemble convexe des solutions admissibles défini par :

K = {x ∈ Rn : Ax = b et x ≥ 0}

De plus, nous savons que les sommets sont étroitement reliés aux solutions de base admis-
sibles. Concrètement, cela signifie que si on choisit une liste de m variables dites de base
B = {xj1 , xj2 , ..., xjm } associées à des colonnes {aj1 , aj2 , ..., ajm } qui forment une base de
l’espace colonne, on peut calculer l’unique solution de bases du système

AxB = b

en imposant que les variables hors-base xi = 0 pour tous les i 6= j1 , j2 , ..., jm .

Si xB ≥ 0, la solution est admissible et sera appelée solution de base admissible ou réa-
lisable. La solution de base xB correspond à un sommet de l’ensemble réalisable K. Par
conséquent, il suffit de calculer tous les sommets de K pour trouver la solution optimale.
n!
Mais le nombre de sommets est de l’ordre ce qui est beaucoup trop pour des
m!(n − m)!
n et m relativement grands. Le principe de la méthode du simplexe est d’éviter de calculer
tous les sommets. A partir d’un sommet donné, la méthode calculera une suite de sommets
adjacents par rapport au précédent et qui améliore la fonction objective. Deux sommets
x et y sont dits adjacents si les variables de base ne diffèrent que d’un seul élément.
Exemple : considérons le problème suivant.



 max z = 5x1 + 4x2

 x1 + x3 = 6



(P ) 1
x + x2 + x4 = 6
4 1




 3x1 + 2x2 + x5 = 22


 x ,x ,x ,x ,x ≥ 0
1 2 3 4 5

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 17

Le sommet x = (4, 5, 2, 0, 0) correspond aux variables de base {x1 , x2 , x3 }. De même, le

sommet y = (6, 2, 0, 2.5, 0) est associé aux variables de base {x1 , x2 , x4 }. Les deux sommets
2
sont adjacents ce qui est conforme au graphique
  de l’ensemble K projeté dans R .
  x1
  
1 0 1 0 0  x2 

  6 
 1
 
Le système s’écrit :  1 0 1 0   x3  =  6 
 
 4    
 x  22
3 2 0 0 1  4 
x5
Pour calculer la solution de base (4, 5, 2, 0, 0) , il suffit d’extraire les 3 colonnes de la
matrice A et de résoudre le système carré par la méthode d’élimination de Gauss. Toute-
fois, lorsque que l’on voudra calculer la nouvelle solution de base (6, 2, 0, 2.5, 0), il faudra
recommencer l’élimination de Gauss avec les nouvelles colonnes de base. Il est plus avan-
tageux de poursuivre l’élimination de Gauss à partir du premier calcul. Voici un exemple
de calcul. En premier, on forme la matrice augmentée
 
1 0 1 0 0 6
 1
 
1 0 1 0 6

 
 4 
3 2 0 0 1 22

On applique l’élimination de Gauss pour les variables de base {x1 , x2 , x3 }.

 
−4 2
 1 0 0
5 5
4 
6 −1
 
 0 1 0 5 
 
 5 10 
 4 −2 
0 0 1 2
5 5
Donc
4 2
x1 = 4 + x4 − x5
5 5
6 1
x2 = 5 − x4 + x5
5 10
4 2
x3 = 2 − x4 + x5
5 5
En posant les variables hors-bases x4 = x5 = 0, on obtient bien la solution de base
x = (4, 5, 2, 0, 0). Maintenant, on désire calculer la solution de base adjacente liées aux
variables de base {x1 , x2 , x4 }. Pour cela, on poursuit l’élimination de Gauss-Jordan à partir
du pivot a3,4

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 18

 
1 0 1 0 0 6
−3 −1
 
0 1 0 5 
 

 2 10 
 5 −1 5 
0 0 1
4 2 2
Donc
x1 = 6 − x 3
3 1
x2 = 2 + x3 − x5
2 2
5 5 1
x4 = − x3 + x5
4 4 2
En posant les variables hors-bases x3 = x5 = 0, on obtient bien la solution de base
y = (6, 2, 0, 2.5, 0).
Poursuivons un autre sommet adjacent z = (6, 0, 0, 4.5, 4) dont les variables de base sont
{x1 , x4 , x5 }. Ce sommet est adjacent à y mais pas à x. Poursuivons l’élimination de Gauss-
Jordan à partir du pivot a2,5
 
1 0 1 0 0 6
 
 0 2 −3 0 1 4 
 
 −1 9 
0 1 1 0
4 2
Donc
x 1 = 6 − x3
x5 = 4 − 2x2 + 3x3
9 1
x 4 = − x2 + x 3
2 4
En posant les variables hors-bases x2 = x3 = 0, on obtient bien la solution de base
z = (6, 0, 0, 4.5, 4).
L’opération décrite ci-dessus est aussi connue sous le nom de pivotement. Cette stratégie
sera à la base de la méthode du simplexe.

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 19

2.2.2 Algorithme
Étape 1 : On forme le tableau initial du simplexe

V ar x1 x2 . . . xn xn+1 xn+2 . . . xn+m

xn+1 a11 a12 . . . a1n 1 0 . . . 0 b1
xn+2 a21 a22 . . . a2n 0 1 . . . 0 b2
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
xn+m am1 am2 . . . a1n 0 0 . . . 1 bm
z c1 c2 . . . cn 0 0 . . . 0 0

La base initiale de l’espace colonne sera {xn+1 , xn+2 , ..., xn+m }. Les autres variables seront
égales à 0 ce qui correspond au point de départ x = (0, 0, ..., 0).
Étape 2 : On doit choisir la colonne de pivot. Pour cela, on choisit l’indice j tel quel

cj = max{ci : ci > 0}.

Si aucun choix n’est possible, on a atteint la solution optimale et l’algorithme se termine.

Sinon, on passe à l’étape suivante. Noter que pour un problème de minimisation, on modifie
le critère en choisissant l’indice j tel que

cj = min{ci : ci < 0}.

Étape 3 : On doit choisir la ligne de pivot. Pour cela, on choisit l’indice i en utilisant le
critère du quotient
bi bk
= min{ : akj > 0 k = 1, 2, ..., m}
aij akj
où j est la colonne de pivot de l’étape 2.

(a) On applique la procédure d’élimination de Gauss autour du pivot situé à l’intersection

de la ligne i et de la colonne j. Ensuite, on divise la ligne i par le pivot pour le rendre est
égale à 1.
(b) On retourne à l’étape 2 et on recommence.

Remarque 2.2.1. Expliquons le critère du quotient. A une certaine itération du simplexe,

nous disposons d’une solution de base xB lié à un choix B de variables de base. Ensuite, il

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 20

s’agit de pivoter vers une solution de base adjacente qui doit être admissible. Le critère du
quotient assure que la nouvelle solution de base sera admissible. En effet, notons par j la
colonne de pivot de l’étape 2 et par i un choix quelconque de la ligne de pivot. A ce choix de
la ligne de pivot correspond une variable xji qui sortira de la base. Le critère du quotient
impose que aij > 0. La nouvelle base s’écrira B̃ = B ∪ {xj }\{xji } et on doit imposer
que la solution de base associée à B̃ doit être admissible. On procède par élimination de
Gauss-Jordan autour du pivot aij . La ligne Lk du tableau du simplexe (à cette itération)
est modifiée par
Li
Lk ← Lk − akj
aij
Ceci modifie la dernière colonne du tableau du simplexe par
akj
bk − bi ≥ 0.
aij

qui doit être positif car elle sera la nouvelle solution de base. Si akj > 0, on obtient

akj bk bi
bk − bi = ( − )akj ≥ 0
aij akj aij

bk bi
⇒ ≥ ∀k akj > 0.
akj aiJ˙
Si akj = 0, on obtient
Li
Lk − akj = Lk .
aij
Donc, aucun changement.
Si akj < 0, on a
akj
bk − bi ≥ 0
aij
car aij > 0 et les bi , bk ≥ 0. Donc seulement les valeurs akj > 0 sont à considérer et, selon
le calcul ci-dessus, on a que
bk bi bi bk
≥ ⇒ = min{ |akj > 0 k = 1, 2, ..., m}.
akj aiJ˙ aiJ˙ akj

Récapitulons Les différentes étapes de l’algorithme du simplexe :

Algorithme 2.2.1.
Initialisation : Trouver une forme simpliciale du problème (sommet de départ),
Test d’optimalité :

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 21

— Exprimer la fonction objectif à partir des variables hors base,

— Si tous les coûts sont négatifs ou nuls (positifs ou nuls pour le cas de la minimisa-
tion) Alors STOP ; la solution obtenue est optimale, Sinon,
Choix de la variable entrante : c’est la variable hors base xr qui correspond au coût le plus
positif (plus négatif en cas de min).
bi
Choix de la variable sortante : c’est la variable de base xs pour laquelle le rapport est
air
le plus petit avec air > 0.
Nouvelle solution de base : Appliquer les opérations pivot

asj
• aij ←− aij − air
asr
air
• bi ←− bi − bs
asr
asj
• cj ←− cj − cr
asr
bs
• z ←− z − cr
asr
Retour au test d’optimalité.

Remarque 2.2.2. — L’hypothèse de no-négativité des variables de décision sert da-

vantage à effectuer le test d’optimalité. Elle ne présente aucune restriction.
— Lorsqu’on manipule cet algorithme à l’aide des tableaux de simplexe, on peut consi-
dérer indifféremment les deux écritures équivalentes suivantes z = c1 x1 + c2 x2 +
... + cn xn dans la dernière ligne :

z − c1 x1 − c2 x2 − ... − cn xn = 0 ⇐⇒ −z + c1 x1 + c2 x2 + ... + cn xn = 0

En effet, il suffit de considérer l’une qui donne la possibilité au test d’optimalité,

et non pas celle qui le bloque dés le départ pour dire que le problème n’admet pas
d’avance une solution optimale.

2.2.3 Exemples : Cas borné et non borné

Exemple 2.2.1. : On cherche à résoudre le PPL suivant

max z = 20x1 + 25x2

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 22

sous les contraintes 

 2x1 + 3x2 ≤ 40


4x1 + 2x2 ≤ 48

 x ,x ≥ 0

1 2

Au préalable, on écrit le problème sous la forme standard :

max z = 20x1 + 25x2

sous les contraintes 

 2x1 + 3x2 + x3 = 40


4x1 + 2x2 + x4 = 48

≥ 0.

 x ,x ,x ,x
1 2 3 4

Voici les étapes de l’algorithme du simplexe.

1. On forme le tableau initial.

V ar x1 x2 x3 x4
x3 2 3 1 0 40
x4 4 2 0 1 48
−z 20 25 0 0 0

Les variables de base sont {x3 , x4 } et la solution de base est (0, 0, 40, 48) ce qui correspond
à l’origine dans le plan.
2. La fonction z varie plus rapidement en fonction de la variable x2 . Donc, on choisit la
deuxième colonne comme colonne de pivot. La variable x2 entre dans la base mais une
variable doit sortir.
3. On doit choisir la ligne de pivot. Pour cela, on utilise le critère du quotient
bi bk
= min{ : akj > 0 k = 1, 2, ..., m}
aij akj

où j est la colonne de pivot de l’étape 2. Le critère assure que la solution sera admissible.

Var x1 x2 x3 x4 critère
x3 2310 40 40 ÷ 3 = 40/3
x4 4201 48 48 ÷ 2 = 24
20 25 0 0 0

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 23

La ligne de pivot sera la première : i = 1. Les variables de base deviennent

B = {x2 , x4 }.

4. On pivote autour de l’élément a1,2

V ar x1 x2 x3 x4
x2 2/3 1 1/3 0 40/3
x4 8/3 0 −2/3 1 64/3
−z 10/3 0 −25/3 0 −1000/3

La solution de base sera x2 = 40/3, x4 = 64/3, x1 = x3 = 0.

5. On choisit la première colonne comme colonne de pivot car x1 est la seule variable qui
augmente z.

V ar x1 critère
x2 2/3 40/3 40/3 ÷ 2/3 = 20
x4 8/3 64/3 64/3 ÷ 8/3 = 8
10/3 -1000/3

On applique le critère du quotient pour chercher la ligne de pivot et on trouve i = 2. La

nouvelle base sera B = {x2 , x1 }.
6. On pivote autour de l’élément a2,1

V ar x1 x2 x3 x4
x2 0 1 1/2 −1/4 8
x1 1 0 −1/4 3/8 8
−z 0 0 −15/2 −5/4 −360

7. L’algorithme se termine car tous les coefficients des colonnes x1 , x2 , x3 , x4 sont négatifs.
Donc, on ne peut augmenter davantage z. La solution optimale sera donc

x1 = 8, x2 = 8, x3 = 0, x4 = 0 avec z = 360

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 24

Exemple 2.2.2. Considérons le PPL donné sous forme canonique :




 min 3x1 − 6x2




 x1 + 2x2 ≥ −1

2x1 + x2 ≥ 0




x1 − x2 ≥ −1

x1 − 4x2 ≥ −13









 −4x1 + x2 ≥ −23

x1 , x2 ≥ 0


ce qui est équivalent à (rendre le second membre b ≥ 0)


 min 3x1 − 6x2






 −x1 − 2x2 ≤ 1

 −2x1 − x2 ≤ 0



−x1 + x2 ≤ 1

−x1 + 4x2 ≤ 13









 4x1 − x2 ≤ 23

x1 , x2 ≥ 0


On ajoutant les variables d’écart, le PPL sous forme standard s’écrit




 min 3x1 − 6x2




 −x1 − 2x2 + x3 = 1

−2x1 − x2 + x4 = 0




−x1 + x2 + x5 = 1

−x1 + 4x2 + x6



 = 13





 4x1 − x2 + x7 = 23

x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0


Le tableau initial s’ écrit

 
−1 −2 1 0 0 0 0 1
 

 −2 −1 0 1 0 0 0 0 

 

 −1 1 0 0 1 0 0 1 


 −1 4 0 0 0 1 0 13 

 

 4 −1 0 0 0 0 1 23 

3 −6 0 0 0 0 0 0

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 25

La colonne de pivot est j = 2 et la ligne de pivot est i = 3. On pivote autour de ce pivot.

 
−3 0 1 0 2 0 0 3
 
 −3 0 0 1 1 0 0 1 
 
 
 −1 1 0 0 1 0 0 1 
 
 3
 0 0 0 −4 1 0 9  
 
 3 0 0 0 1 0 1 24 
 
−3 0 0 0 6 0 0 6

La colonne de pivot est j = 1 et la ligne de pivot est i = 4. On pivote autour de ce pivot.

 
0 0 1 0 −2 1 0 12
 
 0
 0 0 1 −3 1 0 10  
 
 0
 1 0 0 −1/3 1/3 0 4  
 1
 0 0 0 −4/3 1/3 0 3  
 
 0
 0 0 0 5 −1 1 15  
0 0 0 0 2 1 0 15

L’algorithme se termine à cette étape car tous les ci ≥ 0. La solution optimale sera
x1 = 3, x2 = 4, x3 = 12, x4 = 10, x5 = 0, x6 = 0, x7 = 15
Donc (x1 , x2 ) = (3.4) et z = −15.

Exemple 2.2.3. Cas d’un PPL dont la solution est non bornée :



 min −2x1 − 3x2 + x3

−x1 − x2 − x3 ≤ 3




x1 − x2 + x3 ≤ 4

−x1 + x2 + 2x3 ≤



 1


 x ,x ,x 1 2 3≥ 0

Réécrivons le PPL sous forme standard en ajoutant les variables d’écart




 min −2x1 − 3x2 + x3

 −x1 − x2 − x3 + x4 = 3



x1 − x2 + x3 + x5 = 4

−x1 + x2 + 2x3 + x6 = 1






 x ,x ,x ,x ,x ,x
1 2 3 4 5 6 ≥ 0

Youssef Qaraai E-MMIS, FSTE, UMI

2.2. ALGORITHME DU SIMPLEXE 26

Le tableau initial est donné par

 
−1 −1 −1 1 0 0 3
 
 1 −1 1 0 1 0 4 
 
 −1 1 2 0 0 1 1 
 
−2 −3 1 0 0 0 0
La colonne de pivot est j = 2 et la ligne de pivot est i = 3.
On pivote autour du point pivot a32 .
 
−2 0 1 1 0 1 4
 
 0 0 3 0 1 1 5 
 
 −1 1 2 0 0 1 1 
 
−5 0 7 0 0 3 3
La colonne de pivot est j = 1. Toutefois, le critère du quotient ne s’applique plus car toutes
les entrées (lignes 1 à 3) de la colonne 2 sont négatives ou nulles. Analysons cette situation
en écrivant les équations correspondantes du tableau
−2x1 + x3 + x4 + x6 = 4
3x3 + x5 + x6 = 5
−x1 + x2 + 2x3 + x6 = 1
La dernière base était B = {x4 , x5 , x2 }. On voulait faire entrer dans la base la variable x1
. Posons les autres variables x3 = x6 = 0 dans le système ci-dessus,

x4 = 4 + 2x1 ≥ 0, x5 = 5 ≥ 0 , x2 = 1 + x1 ≥ 0.

Donc nous obtenons une famille de solutions admissibles qui dépend de la variables x1 ≥ 0.
Reportons dans la fonction objective (voir la dernière ligne du tableau), on obtient

z = −3 − 5x1 + 7x3 + 3x6

Or x3 = x6 = 0, alors

z = −3 − 5x1 →x1 →∞ −∞
Donc le problème est non borné inférieurement et de ce fait n’admet pas de solution opti-
male.
Remarque 2.2.3. Selon cet exemple, on peut conclure que s’il n’est pas possible de calculer
la ligne de pivot pour un choix de colonne de pivot j, le problème n’admet pas de solution
optimale car il sera toujours non borné.

Youssef Qaraai E-MMIS, FSTE, UMI

2.3. MÉTHODE DES DEUX PHASES 27

2.3 Méthode des deux phases

La méthode du simplexe telle que présentée à la section précédente, exige la connaissance
d’une solution de base admissible. Cette solution initiale peut provenir directement de la
forme simpliciale du PPL. Autrement dit, si on considère le programme suivant

t
 min z = c x


(P ) Ax ≥ b

 x≥0


avec b ≥ 0. Lorsqu’on remet (P ) sous forme standard, on se demande est ce qu’on dispose
d’une écriture de la matrice du problème sous la forme A = [A, Im ], avec A la matrice
donnée ci-dessus et Im est l’identité d’ordre m. Sinon, on ne peut pas démarrer directement
l’algorithme du simplexe.

Un moyen pour remédier à ce problème, est d’utiliser la méthode dite des deux phases. Le
principe consiste à procéder selon les deux étapes suivantes.
— Phase 1 : Ajouter une variable dite artificielle ti pour chaque membre de la contrainte
i sans changer le type = bi . Puis remplacer la fonction objectif z par T = m
P
i=1 ti ,
et résoudre le problème de minimisation résultant par l’algorithme du simplexe (on
l’appelle problème artificiel).
Notons par SA∗ (t∗ , x∗ ) la solution optimale obtenue, et par T abf in le dernier tableau
du simplexe donnant SA∗ . S’il existe un indice k tel que t∗k 6= 0, alors on s’arrête
pour conclure que le problème d’origine (P ) n’admet pas de solution, sinon
— Phase 2 : c-à-d si t∗i = 0, ∀i = 1, ..., m, alors éliminer toutes les ti dans T abf in et
remplacer T par la fonction objectif z puis continuer l’algorithme du simplexe pour
conclure.
Notez qu’on dispose d’un sommet de départ pour le simplexe, ce qu’il faut c’est
juste d’exprimer z en fonction des variables hors base.
Exemple 2.3.1. L’approche graphique a donnée lieu à la solution optimale x∗ = (0, 10)
et z ∗ = 30 du PPL suivant. Retrouvons ce résultat à l’aide de la méthode des deux phases.
 

 max z = 2x 1 + 3x 2 
 max z = 2x1 + 3x2

 

 x + x ≤ 10  x + x + x = 10
1 2 1 2 3
(P ) → Forme standard
 5x1 + 4x2 ≥ 20




 5x1 + 4x2 − x4 = 20
 
x1 , x2 ≥ 0 x1 , x2 , x3 , x4 ≥ 0
 

Youssef Qaraai E-MMIS, FSTE, UMI

2.3. MÉTHODE DES DEUX PHASES 28

On remarque que le problème n’admet pas de forme simpliciale pour démarrer le simplexe
car on n’a pas A = [A, Im ]. Donc on va considérer la phase 1 en introduisant le problème
artificiel donné par : 

 min T = t1 + t2


 x + x + x + t = 10
1 2 3 1

 5x1 + 4x2 − x4 + t2 = 20



x1 , x2 , x3 , x4 , t1 , t2 ≥ 0


Remarquons qu’on a un sommet de départ S0 = (0, 0, 0, 0, 10, 20). En réécrivant T en

fonction de x1 , x2 , x3 et x4 , on aura le tableau initial du simplexe

V ar x1 x2 x3 x4 t1 t2
t1 1 1 1 0 1 0 10
t2 5 4 0 −1 0 1 10
−T −6 −5 −1 1 0 0 −30

Le sommet S0 n’est pas optimal car il existe des coûts négatifs. La variable x1 va entrer
dans la base au lieu de t2 .

V ar x1 x2 x3 x4 t1 t2
t1 0 1/5 1 1/5 1 −1/5 6
x1 1 4/5 0 −1/5 0 1/5 4
−T 0 −1/5 −1 −1/5 0 6/5 −6

Le sommet S1 = (4, 0, 0, 0, 6, 0) n’est pas optimal. On échange x3 et t1 :

V ar x1 x2 x3 x4 t1 t2
x3 0 1/5 1 1/5 1 −1/5 6
x1 1 4/5 0 −1/5 0 1/5 4
−T 0 0 0 0 1 1/5 0

Puisque tous les coûts sont positifs ou nuls, le sommet S2 = (4, 0, 6, 0, 0, 0) est optimal.
Comme t∗1 = t2 = 0, alors on passe à la phase 2. Éliminons les variables artificielles et
réécrivons z en fonction de x2 et x4 . on a

z = 2x1 + 3x2 = 7/5x2 + 2/5x4 + 8 (on a utilisé la contrainte 2)

Youssef Qaraai E-MMIS, FSTE, UMI

2.3. MÉTHODE DES DEUX PHASES 29

D’où le tableau initial pour la phase 2

V ar x1 x2 x3 x4
x3 0 1/5 1 1/5 6
x1 1 4/5 0 −1/5 4
−z 0 7/5 0 2/5 −8

Le sommet X 0 = (4, 0, 6, 0) n’est pas optimal. On échange x2 et x1 :

V ar x1 x2 x3 x4
x3 −1/4 0 1 1/4 5
x2 5/4 1 0 −1/4 5
−z −7/4 0 0 3/4 −15

Le point courant X 1 = (4, 0, 6, 0) n’est pas optimal. On échange x4 et x3 :

V ar x1 x2 x3 x4
x4 −1 0 4 1 20
x2 1 1 1 0 10
−z −1 0 −3 0 −30

Puisque tous les coûts sont négatifs ou nuls, alors le sommet obtenu X 2 = (0, 10, 0, 20)
est optimal. C’est à dire (x∗1 , x∗2 ) = (0, 10) avec z ∗ = 30. Ce qui coïncide avec le résultat
graphique. D’autre part, on retrouve exactement les écarts des deux contraintes (x∗3 , x∗4 ) =
(0, 20).

Youssef Qaraai E-MMIS, FSTE, UMI

Chapitre 3

Dualité et analyse de sensibilité

Dans ce chapitre nous allons aborder deux notions qui jouent un rôle important en pro-
grammation linéaire. En plus de son interprétation concrète, la dualité peut être vue
comme une méthode de résolution d’un programme linéaire. Lorsqu’un PPL est résolu,
c’est à dire que la solution optimale est déterminer, la phase de l’analyse post-optimale sera
aussi traitée. Il s’agit d’étudier la variation (les effets de la perturbation) des paramètres
du programme linéaire à partir de cette solution optimale.

3.1 Dualité

3.1.1 Introduction et règles de transformation

On suppose que A est une matrice d’ordre m × n et b ∈ Rm . A chaque problème d’opti-
misation linéaire, dit primal, nous allons définir un nouveau problème appelé dual.
Soit (P ) le problème de programmation linéaire primal

t
 min z = c x


s.c. Ax ≥ b

x≥0

 et

Le dual (D) du problème (P ) est donné par


t
 max w = b y


s.c. At y ≤ c

y≥0

 et

30
3.1. DUALITÉ 31

On notera que, pour le problème primal, on a x ∈ Rn tandis que y ∈ Rm pour le dual.

Évaluons maintenant le dual du problème en cas de maximisation

t
 max z = c x


s.c. Ax ≤ b

x≥0

 et

Pour cela il suffit de le réécrire sous la forme d’un problème de type min :

 − min

 −ct x
s.c. −Ax ≥ −b

x≥0

 et
Le dual sera 
 − max

 −bt y
s.c. −At y ≤ −c

y≥0

 et
ce qui est équivalent à 
t
 min w = b y


s.c. At y ≥ c

y≥0

 et

En général, le passage d’un primal vers son dual respecte les transformations suivantes :

Primal (P, x, z) dual (D, y, w)

max min
Coût cj de z Second membre des contraintes
Second membre bi Coût de l’objectif w
Matrice A(m, n) Matrice At (n, m)
Nombre de variables n Nombre de contraintes
La variable xj ≥ 0 La jème contrainte de type ≥
La variable xj ∈ R La jème contrainte de type =
La variable xj ≤ 0 La jème contrainte de type ≤
La ième contrainte de type ≤ La variable yi ≥ 0
La ième contrainte de type = La variable yi ∈ R
La ième contrainte de type ≥ La variable xj ≤ 0

Proposition 3.1.1. Le dual du dual est le primal.

Youssef Qaraai E-MMIS, FSTE, UMI

3.1. DUALITÉ 32

Démonstration. Considérons le PPL primal formulé comme suit


 min

 z = ct x
s.c. Ax ≥ b

x≥0

 et

Le dual est donné par 

t
 max w = b y


s.c. At y ≤ c

y≥0

 et

On applique le résultat ci-dessus pour obtenir


t
 min u = c x


s.c. (At )t x ≥ b

x≥0

 et

ce qui donne 
t
 min z = c x


s.c. Ax ≥ b

x≥0

 et

qui n’est autre que le primal. 

3.1.2 Interprétation économique

Considérons le problème d’une entreprise agricole qui désire ensemencer avec 3 variétés
de plantes A, B et C. Il s’agit de déterminer les superficies xi (en hectare) des terres
ensemencées par les plantes A, B et C pour avoir un bénéfice maximal. Voici le tableau
qui résume la situation

Terrain (ha) Travail (h) Machine (h) Rendement

A 2 1 1100
B 3 2 1400
C 1 3 1500
340 2400 560

Par exemple, il faudra 3 heures de travail par hectare pour ensemencer avec la plante B
et 2 heures de machinerie. La dimension totale du terrain est de 340 ha et nous disposons

Youssef Qaraai E-MMIS, FSTE, UMI

3.1. DUALITÉ 33

de 2400 heures de temps de travail et de 560 heures en temps de machinerie. 1 hectare de

la plante A donne un profit de 1100.
L’objectif est donc : max z = 1100x1 + 1400x2 + 1500x3
Contrainte 1 (dimension du terrain) : x1 + x2 + x3 ≤ 340
Contrainte 2 (temps de travail) : 2x1 + 3x2 + x3 ≤ 2400
Contrainte 3 (temps de machinerie) : x1 + 2x2 + 3x3 ≤ 560
Toutes les variables de décision x1 , x2 et x3 sont positives.
On ajoute les variables d’écart x4 , x5 , x6 à ce problème et on applique la méthode du
simplexe. Le tableau final est donné par :
V ar x1 x2 x3 x4 x5 x6
x1 1 0 −1 2 0 1 120
x5 0 0 −3 −1 1 −1 1500
x2 0 1 2 −1 0 1 220
−z 0 0 −200 −800 0 −300 −440000
A l’optimum on trouve

x1 = 120, x2 = 220, x3 = 0, x4 = 0, x5 = 1500, x6 = 0

et le profit associé est égale à z = 440000.

On observe que les ressources de terrain et de machinerie sont pleinement utilisées car
x4 = x6 = 0.
Par contre, la ressource en temps de travail n’est pas pleinement utilisée car x5 6= 0.

Maintenant, regardons le point de vue d’un acheteur des activités de l’entreprise. Les coûts
marginaux sont mieux interprétés de la manière suivante :
— y1 = prix à offrir pour acheter un hectare de terrain,
— y2 = prix à offrir pour acheter une heure de travail,
— y3 = prix à offrir pour acheter une heure de machine,
— Question : Quel sera le problème à résoudre pour déterminer ces variables ?
La fonction objectif correspond au coût à payer pour acheter l’entreprise est

w = 340y1 + 2400y2 + 560y3 = b1 y1 + b2 y2 + b3 y3 = bt y.

Il s’agit de minimiser le prix à payer : min w = bt y.

Pour cela, son offre sera acceptée s’il propose au moins autant que le bénéfice de chacune
des activités.

Youssef Qaraai E-MMIS, FSTE, UMI

3.1. DUALITÉ 34

— Activité A : le bénéfice lié à l’ensemencement de la plante A est

y1 + 2y2 + y3 ≥ 1100

— Activité B : le bénéfice lié à l’ensemencement de la plante B est

y1 + 3y2 + 2y3 ≥ 1400

— Activité C : le bénéfice lié à l’ensemencement de la plante C est

y1 + y2 + 3y3 ≥ 1500.

En résumé, le problème ainsi formulé s’écrit




 min w = 340y1 + 2400y2 + 560y3

 y1 + 2y2 + y3 ≥ 1100



y1 + 3y2 + 2y3 ≥ 1400

y1 + y2 + 3y3 ≥ 1500






 y , y , y ≥0
1 2 3

Le principe de la dualité peut s’énoncer de la manière suivante : le plus bas prix total à
payer pour l’acheteur doit être égale au bénéfice maximal pour le producteur.

3.1.3 Théorèmes de la dualité

Soient (P ) un PPL primal et (D) son dual. Sans perdre de généralités, on considère le cas
de minimisation pour (P ) (pour la maximisation il suffit d’utiliser max(f ) = − min(−f )).

t
 min z = c x


(P ) s.c. Ax ≥ b

x≥0

 et

t
 max w = b y


(D) s.c. At y ≤ c

y≥0

 et

D’autre part, et sans rentrer dans les détails de la théorie de l’optimisation (conditions
d’optimalité, conditions KKT, Lagrangien, etc), énonçons un résultat dit de dualité faible.

Youssef Qaraai E-MMIS, FSTE, UMI

3.1. DUALITÉ 35

Théorème 3.1.1. (Dualité faible)

Si x et y sont des solutions réalisables respectivement de (P ) et D alors on a

w = bt y ≤ c t x = z ∀x, y

Autrement dit, la fonction objectif du primal est toujours bornée inférieurement par bt y
et cela pour tous les y vérifiant At y ≤ c et y ≥ 0. De même, la fonction objectif du dual
est toujours bornée supérieurement par ct x pour tous les x vérifiant Ax ≥ b et x ≥ 0.
En effet, on a

w = bt y = y t b ≤ y t Ax = (Ax)t y = xt At y ≤ xt c = ct x = z

Le théorème faible de la dualité nous conduit à

bt y ≤ ct x ⇒ bt y ≤ min ct x ⇒ max bt y ≤ min ct x

x y x

Maintenant on se demande pour quelle couple (x, y) a-t-on l’égalité.

Théorème 3.1.2. (Dualité forte)
Si x∗ et y ∗ sont les solutions optimales respectivement de (P ) et D alors :
1. w∗ = bt y ∗ = ct x∗ = z ∗
2. De plus une des alternatives suivantes a lieu :
— Si un des problèmes primal ou dual admet une solution, alors l’autre problème
admet aussi une solution.
— Si un des problèmes primal ou dual n’admet pas une solution, alors l’autre pro-
blème n’admet pas de solution.
3. Les relations suivantes, dites de complémentarité, sont vérifiées
n

X
(b − aij x∗j )yi∗ = 0 ∀i = 1, 2, ..., m


 i


j=1
m
X

∗
 xj (cj − aji yi∗ ) = 0 ∀j = 1, 2, ..., n



i=1

Le point 3 de ce théorème, s’appelle parfois, le théorème des écarts complémentaires.

Exemple 3.1.1. Considérons le problème suivant

 min z = −x1 − x2



 −x − 3x ≥ −3
1 2

 −2x1 − x2 ≥ −2



x1 , x2 ≥ 0


Youssef Qaraai E-MMIS, FSTE, UMI

3.1. DUALITÉ 36

3 4 7
qui admet la solution : (x∗1 , x∗2 ) = ( , ) et z ∗ = − .
5 5 5
Le problème dual s’écrit sous la forme :


 max w = −3y1 − 2y2


 −y − 2y ≤ −1
1 2


 −3yl − y2 ≤ −1

y1 , y2 ≥ 0


1 2 7
qui admet la solution (y1∗ , y2∗ ) = ( , ) et w∗ = −
5 5 5
Les deux problèmes ont été résolus graphiquement, mais on peut utiliser le simplexe, sinon
la méthode des deux phases vues aux chapitres précédents.

Dans cet exemple, on observe que la valeur minimale du primal est égale à la valeur
maximale du dual.
3 4
Il est facile de vérifier les relations de complémentarité. On a m = n = 2, (x∗1 , x∗2 ) = ( , )
5 5
∗ ∗ 1 2
et (y1 , y2 ) = ( , ), donc
5 5
1 3 4 1
i = 1, (− − 3 + 3) = (0) = 0
5 5 5 5
2 3 4 2
i = 2, (−2 − + 2) = (0) = 0
5 5 5 5
3 1 2 3
j = 1, (−1 + + 2 ) = (0) = 0
5 5 5 5
4 1 2 4
j = 2, (−1 + 3 + ) = (0) = 0
5 5 5 5

3.1.4 Dualité et complémentarité

Jusqu’à ce niveau, on a pas encore préciser comment exploiter la notion de dualité en
programmation linéaire. Après avoir détaillé l’algorithme du simplexe ainsi que la méthode

Youssef Qaraai E-MMIS, FSTE, UMI

3.1. DUALITÉ 37

des deux phases, cette dernière parait comme méthode très coûteuse en termes de calculs
effectués : augmentation de la dimension du problème par des variables artificielles. De ce
fait, on peut considérer la dualité comme un autre outil de résolution d’un problème de
programmation linéaire. Cela consiste à :
1. Mettre le problème sous forme standard.
2. S’il admet une forme simpliciale, utiliser directement le simplexe.
3. Sinon donner le dual associé, et voir est ce que le dual est directement solvable par
le simplexe.
4. Si oui, déterminer la solution optimale et utiliser les relations de complémentarités
pour déduire la solution du primal
5. Sinon, on applique la méthode des deux phases au primal ou au dual selon la
dimension des deux problèmes.
Noter que le passage de la solution optimale du primal (resp. dual) vers celle du dual (resp.
primal), est assuré par l’application du théorème des écarts complémentaires.

Exemple 3.1.2. Rappelons le problème de l’entreprise agricole :




 max z = 1100x1 + 1400x2 + 1500x3

 x1 + x2 + x3 ≤ 340



2x1 + 3x2 + x3 ≤ 2400

x1 + 2x2 + 3x3 ≤ 560






 x ,x ,x ≥ 0
1 2 3

La solution optimale de ce problème est donnée par x∗1 = 120, x∗2 = 220, x∗3 = 0 et z ∗ =
440000. Considérons maintenant son dual donné par :



 min w = 340y1 + 2400y2 + 560y3

 y1 + 2y2 + y3 ≥ 1100



y1 + 3y2 + 2y3 ≥ 1400

y1 + y2 + 3y3 ≥ 1500






 y , y , y ≥0
1 2 3

Sans utiliser la méthode des deux phases, on va résoudre le dual en utilisant les relations

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 38

de complémentarité. En effet on a

i = 1, x∗1 6= 0 =⇒ y1∗ + 2y2∗ + y3∗ = 1100

i = 2, x∗2 6= 0 =⇒ y1∗ + 3y2∗ + 2y3∗ = 1400
i = 3, x∗3 = 0 =⇒ pas d’informations
j = 1, y1∗ (340 − 120 − 220 − 0) = 0 =⇒ y1∗ quelconque
j = 2, y2∗ (2400 − 240 − 660 − 0) = 0 =⇒ y2∗ = 0
j = 3, y3∗ (560 − 120 − 440 − 0) = 0 =⇒ y3∗ quelconque

Donc à partir de ce système d’équations on en déduit que la solution optimale du dual est
donnée par y1∗ = 800, y2∗ = 0, y3∗ = 300 pour la quelle w∗ = 440000.

3.2 Analyse de sensibilité

Étant donné un problème d’optimisation linéaire

t
 min z = c x


(P ) s.c. Ax ≥ b

x≥0

 et

nous allons étudier la sensibilité de la solution optimale par rapport aux données du
problème. Autrement dit, comment varie la solution ou encore la fonction objectif si l’on
modifie une entrée du vecteur c ou de b ou encore de la matrice A. L’analyse de sensibilité
est aussi connue sous le nom d’analyse post-optimale.

3.2.1 Méthode du simplexe revisitée

Pour faire une analyse de sensibilité, il faut pouvoir exprimer la solution du simplexe par
rapport aux données initiales du problème et non par rapport aux tableaux du simplexe
qui change à chaque itération.
Commençons par standardiser (P ) en introduisons les variables d’écart et notons par A la
nouvelle matrice d’ordre m×(m+n). De plus, faisons l’hypothèse que nous connaissons les
variables de base B de la solution optimale xB . Évidemment, cette information provient
du tableau final du simplexe, d’où le terme d’analyse post-optimale.
Notons par B = {xj1 , xj2 , ..., xjm } la liste des variables de base et par N son complémentaire
par rapport à l’ensemble d’indices {1, 2, ..., m + n}. Par exemple, si m = n = 3 et B =

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 39

{x1 , x5 , x2 }, on a N = {x3 , x4 , x6 }.
A partir des ensembles B et N , nous pouvons extraire les sous-matrices suivantes de A :
• AB est la sous-matrice formée des colonnes correspondantes aux variables de B. On suit
l’ordre spécifié par B.
• AN est la sous-matrice formée des colonnes correspondantes aux variables de N ordonnées
selon N .
A l’aide d’une partition par blocs selon les ensembles d’indices B et N , on peut écrire
" #
xB
Ax = b ⇐⇒ [AB AN ] = b ⇐⇒ AB xB + AN xN = b
xN

On peut calculer algébriquement la solution xB :

Ax = b ⇐⇒ AB xB + AN xN = b ⇐⇒ xB + A−1 −1
B AN xN = AB b.

C’est-à-dire
xB = A−1
B (b − AN xN )

La matrice AB est inversible car B est une base. En particulier, la solution optimale est
donnée par la formule
xB = A−1
B b

car les variables hors-base doivent être nulles, i.e. xN = 0.

Tout ce qui a été fait jusqu’à maintenant s’applique autant pour un choix quelconque de
variables de base B pas nécessairement optimale. Comment calculer alors la dernière ligne
du tableau du simplexe ?
z = ct x = ctB xB + ctN xN

On substitue la valeur de xB = A−1

B (b − AN xN )

z = ctB [A−1 t
B (b − AN xN )] + cN xN

= ctB A−1 t t −1
B b + cN x N − cB A B A N x N

= ctB A−1 t t −1
B b + [cN − cB AB AN ]xN

Le tableau du simplexe aura la forme matricielle

xB xN
I A−1
B AN A−1
B b
0 ctN − ctB A−1
B AN −ctB A−1
B b

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 40

Dans la forme matricielle du tableau du simplexe, on note que la première colonne est
inutile. Ainsi on peut écrire la version simplifiée

xN
A−1
B AN A−1
B b
ctN − ctB A−1
B AN −ctB A−1
B b

Le tableau ci-dessus sera optimale si

• la solution de base est réalisable : A−1
B b ≥ 0.
• Les coûts réduits sont tous positifs : ctN − ctB A−1
B AN ≥ 0.

Exemple 3.2.1. Prenons le problème




 min z = −1100x1 − 1400x2 − 1500x3

 x1 + x2 + x3 ≤ 340



2x1 + 3x2 + x3 ≤ 2400

x1 + 2x2 + 3x3 ≤ 560






 x ,x ,x ≥ 0
1 2 3

Le système matriciel Ax = b avec les variables d’écarts est

 
  x1  
1 1 1 1 0 0   340
  x2   
 2 3 1 0 1 0  = 2400
 
  .. 

.
  
1 2 3 0 0 1   560
x6

Le tableau final du simplexe est donné par :

V ar x1 x2 x3 x4 x5 x6
x1 1 0 −1 2 0 1 120
x5 0 0 −3 −1 1 −1 1500
x2 0 1 2 −1 0 1 220
z 0 0 200 800 0 300 440000

Ainsi, on a bien que B = {x1 , x5 , x2 } et N = {x3 , x4 , x6 }. Les sous-matrices AB et AN

s’écrivent    
1 0 1 1 1 0
   
AB = 
 2 1 3  , AN =  1 0 0 
  
1 0 2 3 0 1

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 41

Ax = b est donc équivalent à

       
1 0 1 x1 1 1 0 x3 340
       
 2 1 3   x5  +  1 0 0   x4  =  2400 
       
1 0 2 x2 3 0 1 x6 560

ce qui donne
      
x1 2 0 −1 340 120
      
xB =  x
 5 
 = 
 −1 1 −1 

 2400 
 = 
 1500 

x2 −1 0 1 560 220

qui est la bonne solution optimale selon le tableau final du simplexe.

Les autres colonnes du tableau final correspondent à
    
2 0 −1 1 1 0 −1 2 −1
−1
    
AB AN =   −1 1 −1  
 1 0 0  =  −3 −1 −1 
  
−1 0 1 3 0 1 2 −1 1

ce qui est bien les colonnes correspondantes à N = {x3 , x4 , x6 }.

De plus on a cB = [−1100, 0, −1400]t , cN = [−1500, 0, 0]t et
 
−1 2 −1
A−1
 
B AN =  −3 −1 −1 
 
2 −1 1

Donc  
−1 2 −1
ctB A−1
 
ctN − B AN = [−1500, 0, 0] − [−1100, 0, −1400]  −3 −1 −1 


2 −1 1
= [−1500, 0, 0] − [−1700, −800, −300] = [200, 800, 300]

et
−ctB A−1
B b = 440000

3.2.2 Variation du second membre

Analysons l’effet d’une modification du vecteur b (second membre du système de contraintes).
Autrement dit, il s’agit d’étudier le comportement de la solution pour le problème modifié

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 42

lorsque que l’on change b par b̃ = b + ∆b


t
 min z = c x


Ax ≥ b̃

 x≥0


Soit xB les variables de base de la solution. La question est de savoir sous quelle condition
on aura que la base B demeure optimale. En fait, il est facile de répondre à cette question.
Le vecteur b n’apparait que dans la condition d’optimalité A−1
B b ≥ 0. Par conséquent, les
variables de base xB demeurent optimales pour le problème modifié si

A−1 −1 −1
B b̃ ≥ 0 ⇔ AB ∆b ≥ −AB b

Exemple 3.2.2. 

 min z = x1 + 23 x2 + 3x3


 x + x + 2x ≥ 6,
1 2 3


 x1 + 2x2 + x3 ≥ 10,

x1 , x2 , x3 ≥ 0.


Les données sont (avec les variables d’écart)

 
1
 
" # " #  3/2 
−1 −1 −2 1 0 −6  
A= ,b = ,c =  3 
 
−1 −2 −1 0 1 −10 
 0 

 
0

Supposons que la base optimale est B = {x1 , x2 }. On a donc

" # " #
−1 −1 −2 1
AB = =⇒ A−1 B =
−1 −2 1 −1
" #
−2 1 0
AN =
−1 0 1
Calcul de xB : " #" # " #
−2 1 −6 2
xB = A−1
B b = = ≥0
1 −1 −10 4

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 43

Calcul des coûts réduits ctN − ctB A−1

B AN :
" #" #
−2 1 −2 1 0
ctN − ctB A−1
B AN = [3, 0, 0] − [1, 3/2]
1 −1 −1 0 1
" #
3 −2 1
= [3, 0, 0] − [1, 3/2]
−1 1 1
= [3, 0, 0] − [3/2, −1/2, −1/2]
= [3/2, 1/2, 1/2] ≥ 0

" xB = (2,#4) est optimale, i.e. x = (2, 4, 0, 0, 0).

Donc la solution
−6 − a
Si −b → −b̃ = . Autrement dit, on regarde seulement un changement de b1 ,
−10
" #" # " #
−2 1 −6 − a 2 + 2a
xB = A−1
B (−b̃) = =
1 −1 −10 4−a
On aura que x̃B ≥ 0 si et seulement si
2 + 2a ≥ 0 et 4 − a ≥ 0
On obtient l’intervalle pour le paramètre b1

−1 ≤ a ≤ 4

Quel sera l’intervalle "pour b2 ? #

−6
On pose −b → −b̃ =
−10 − a
" #" # " #
−2 1 −6 2−a
xB = A−1
B (−b̃) = =
1 −1 −10 − a 4+a
On aura que x̃B ≥ 0 si et seulement si
2 − a ≥ 0 et 4 + a ≥ 0
On obtient l’intervalle pour le paramètre b2

−4 ≤ a ≤ 2

Quel sera l’effet sur la valeur minimale de la fonction objectif ? Nous avons :
" #
2−a a
z(b̃) = ctB x̃B + ctN x̃N = ctB x̃B = [1, 3/2] =8+
4+a 2

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 44

Remarque 3.2.1. Dans l’exemple précédent, on a un problème du type min avec Ax ≥ b.

Il est inutile de changer Ax ≥ b sous la forme −Ax ≤ −b. Pour appliquer la méthode du
simplexe revisitée, il suffit de mettre tout d’abord le problème sous forme standard (toutes
les contraintes de type égalité en ajoutant les variables d’écart). Ax = b avec A = [A−Im ].
On observe que, pour ce problème, la matrice du tableau initial du simplexe est donnée
par −A et que b est changé en −b. En se référant à l’écriture sous forme matricielle du
tableau du simplexe, on constate que les formules sont inchangées. Toutefois, AB et AN
sont évaluées à partir de la matrice A. Dans l’exemple ci-dessus, on aura
" # " #
1 1 2 −1 0
AB = et AN =
1 2 1 0 −1

Point de vue du dual :

Primal : min z = ct x, Ax ≥ b̃, x ≥ 0
Dual : max z = b̃t y, At y ≤ c, y ≥ 0.
La solution du dual y se lit à la dernière ligne du tableau optimal. Or cette ligne est
indépendante de b donc de tout changement de b → b̃. Autrement dit, la solution du dual
demeure la même tant que b̃ vérifie la condition de stabilité ci-dessus.
Notons par x(b̃) la solution du problème primal qui varie avec b̃. Par dualité on a

ct x(b̃) = b̃t y

ct x(b) = bt y

⇒ ∆z = ct (x(b̃) − x(b)) = (b̃ − b)t y

⇒ ∆z = ct ∆x = (∆b)t y

Par conséquent, on obtient le taux de variation de la fonction objectif par rapport aux bi .
∂z
= yi
∂bi

3.2.3 Variation du coût

On désire trouver la condition qui assure que la base B demeure optimale si l’on change le
coût c par c̃ = c + ∆c. En premier, on observe que la solution xB = A−1
B b reste inchangée.

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 45

Mais le tableau du simplexe peut perdre le caractère optimal. Pour cela, on doit imposer
la condition de stabilité

c̃tN − c̃tB A−1 t t −1

B AN ≥ 0 ⇔ (c + ∆c)N − (c + ∆c)B AB AN ≥ 0

En général, on désire connaître l’effet d’une modification pour une seule variable xi

ci → c̃i = ci + ∆ci

Il y a 2 cas à analyser selon que xi est une variable de base ou non.

Cas d’une variable hors base :
Notons par ei le vecteur de base canonique de Rn , i.e. ei = (0, 0, ..., 1, 0, ..., 0)t avec le 1 à
la position i. On a
∆cB = 0

∆cN = ∆ci ei = ∆c

La composante i du vecteur c̃tN − c̃tB A−1

B AN s’écrit :

ci + ∆ci − (ctB A−1

B AN )i ≥ 0

∆ci ≥ −(ci − (ctB A−1

B AN )i ) = −ri

c̃i ≥ ci − ri

où les ri sont les composantes de la dernière ligne du tableau du simplexe. Autrement dit,
nous avons toute l’information pour calculer les intervalles de stabilité des coefficients ci .

Exemple 3.2.3. On reprend le PPL de l’exemple 3.2.2. Le tableau final du simplexe est

V ar x1 x2 x3 x4 x5
x1 1 0 3 −2 1 2
x2 0 1 −1 1 −1 4
−z 0 0 3/2 1/2 1/2 −8

La dernière ligne fournit le vecteur des coûts réduits : r = (0, 0, 3/2, 1/2, 1/2).
Les variables de base sont B = {x1 , x2 } et celles hors-base N = {x3 , x4 , x5 }. La fonction
objective est de la forme
z = c1 x 1 + c2 x 3 + c3 x 3

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 46

avec c1 = 1, c2 = 3/2 et c3 = 3. Cela n’a pas de sens de perturber les coefficients c4 et c5 .

Donc nous avons seulement la possibilité de perturber c3 . Calculons l’intervalle de stabilité
autour de c3 associé à la variable hors base x3 . La condition de stabilité est

c3 ≥ c3 − r3 = 3 − 3/2 = 3/2 ⇔ c̃3 ≥ 3/2

La solution optimale x = (2, 4, 0, 0, 0) est la même pour toutes les valeurs c̃3 ≥ 3/2. De
plus, la valeur de la fonction objective (z = 8) demeure inchangée car la variable est hors
base.

Cas d’une variable de base :

On pose ∆ci = α. On a
∆c = ∆ci ei
(∆c)B = ∆ci ei = αei
(∆c)N = 0
Le vecteur c̃tN − c̃tB A−1
B AN s’écrit

ctN − (ctB A−1 t −1

B AN ) − αei AB AN ≥ 0

rN − αeti A−1 −1
B AN ≥ 0 ⇐⇒ rN − α(AB AN )i ≥ 0

Avec ces conditions, on obtient l’intervalle de stabilité pour ci .

Reprenons l’exemple ci-dessus. Le tableau final du simplexe est :

V ar x1 x2 x3 x4 x5
x1 1 0 3 −2 1 2
x2 0 1 −1 1 −1 4
−z 0 0 3/2 1/2 1/2 −8

xB xN
I A−1
B AN A−1
B b
0 rN −ctB xB
Intervalle pour c1 : On pose c̃1 = c1 + α = 1 + α. La condition s’écrit :

rN − α(A−1
B AN )1 = (3/2, 1/2, 1/2) − α(3, −2, 1)

= (3/2 − α, 1/2 + 2α, 1/2 − α)

≥0

Youssef Qaraai E-MMIS, FSTE, UMI

3.2. ANALYSE DE SENSIBILITÉ 47

Sachant que c1 = 1, on trouve

1 1 3
− ≤ α ≤ ⇒ ≤ c1 ≤ 3/2
4 2 4
et que z est changé en
!
2
z = ctB xB = (1 + α, 3/2) = 8 + 2α.
4

Par conséquent, on observe bien que

∂z
= x1 = 2
∂c1
Intervalle pour c2 : On pose c2 = c2 + α = 3/2 + α. La condition s’écrit

rN − α(A−1
B AN )2 = (3/2, 1/2, 1/2) − α(−1, 1, −1)

= (3/2 + α, 1/2 − α, 1/2 + α)

≥0

Sachant que c2 = 3/2, on trouve

1 1
− ≤ α ≤ ⇒ 1 ≤ c2 ≤ 2
2 2
et que z est changé en
!
2
z = ctB xB = (1, 3/2 + α) = 8 + 4α
4

Par conséquent, on observe bien que

∂z
= x2 = 4
∂c2

Youssef Qaraai E-MMIS, FSTE, UMI