1

PLAN DU COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE 1: FORMULATION D’UN PROGRAMME LINEAIRE (PL)

CHAPITRE 2: RESOLUTION GRAPHIQUE DU PROGRAMME LINEAIRE (PL)
CHAPITRE 3: LA METHODE DE SIMPLEXE
CHAPITRE 4: PROBLEMES DE MINIMISATION ET PROBLEMES IRREGULIERS
CHAPITRE 5: DUALITE ET ANALYSE DE SENSIBILITE
CHAPITRE 6: INTRODUCTION A LA PROGRAMMATION DYNAMIQUE

CHAP. 1 : FORMULATION D’UN PROGRAMME LINEAIRE (PL)

I. Introduction
L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes
de décision que soit économique, militaire ou autres ont fait de la programmation linéaire un
des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers travaux1
(1947) sont ceux de George B. Dantzig et ses associés du département des forces de l’air des
Etats Unis d’Amérique.
Les problèmes de programmations linéaires sont généralement liés à des problèmes
d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit
ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble
de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont
en général le résultat d’un problème mathématique.

II. Les conditions de formulation d’un PL

La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que
le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces
hypothèses sont 2 :

1. Les variables de décision du problème sont positives

2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces
variables, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé de
deux de ces variables. La fonction qui représente le critère de sélection est dite fonction
objectif (ou fonction économique).
3. Les restrictions relatives aux variables de décision (exemple : limitations des ressources)
peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment
l’ensemble des contraintes.
4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue
avec certitude

1 De nombreux mathématiciens, parmi eux le Russe L. V. Kantorovich, se sont penchés sur le problème de
programmation linéaire avant 1947.
2
Ces hypothèses résument celles qui ont été donné par G. B. Dantzig : La proportionnalité, la non-négativité,
l’additivité et la linéarité de la fonction objectif

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 2

III. Les étapes de formulation d’un PL :

Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme
linéaire :
1. Identifier les variables du problème à valeur non connues (variable de décision) et les
représenter sous forme symbolique (exp. x1 , y1 ).
2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système
d’équations linéaires.
3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en
fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à
minimiser.

IV. Présentation Théorique

Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire
dite fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En
langage mathématique, on décrira de tels modèles de la manière suivante :

Soient N variables de décision x1 , x2 ,…, xn, l’hypothèse que les variables de décision sont
positives implique que x1  0, x 2  0, , x N  0 .
La fonction-objectif est une forme linéaire en fonction des variables de décision de type

z = c1 x1 + c2 x2 +  + c N x N

où les coefficients c1 ,…,cN doivent avoir une valeur bien déterminée (avec certitude) et peuvent
être positifs, négatifs ou nuls. Par exemple le coefficient cj peut représenter un profit unitaire lié
à la production d’une unité supplémentaire du bien xj, ainsi la valeur de z est le profit total lié à
la production des différents biens en quantités égales à x1 , x 2 , , x N .

Supposons que ces variables de décision doivent vérifier un système d’équations linéaires
définis par M inégalités
a11 x1 + a12 x2 +  + a1 N x N  b1
a21 x1 + a22 x2 +  + a2 N x N  b2

a M 1 x1 + aM 2 x2 +  + a MN x N  bM

où les coefficients a1N,…, aMN et b1 ,…, bM doivent avoir une valeur bien déterminée (avec
certitude) et peuvent être positifs, négatifs ou nuls. Le paramètre bi représente la quantité de
matière première disponible dont le bien x j utilise une quantité égale à aij xj .

En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :

Max c1 x1 + c 2 x 2 +  + c N x N
s.c a11 x1 + a12 x 2 +  + a1 N x N  b1
a 21 x1 + a 22 x 2 +  + a 2 N x N  b2

a M 1 x1 + a M 2 x 2 +  + a MN x N  b N
x1  0, x 2  0,  , x N  0

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 3

V. Exemples de formulations
Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de
divers domaines sont représentés ou approximés par des modèles de PL. L’utilisation de ces
techniques de modélisation s’est renforcée encore après avoir construit des algorithmes et des
logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision
que de contraintes.

La tâche de formulation demande généralement une certaine expertise et connaissance du

problème pour pouvoir relever facilement les différentes composantes du problème et ainsi
donner un programme qui modélise au mieux la situation réelle. Dans ce qui suit, on présentera
quelques exemples de formulation en programme linéaire liés à différents problèmes de
décision :

Exemple 1 : Problème d’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 dinars. Un
hectare de piments demande 4 heures de main d’œuvre, 2 m3 d’eau et donne un bénéfice net de
200 dinars.

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 ?

Formulation du problème en un PL :

Etape 1 : Identification des variables de décision. Les deux activités que l’agriculteur doit
déterminer sont les surfaces à allouer pour la culture de tomates et de piments :
• x1 : la surface allouée à la culture des tomates
• x2 : la surface allouée à la culture des piments
On vérifie bien que les variables de décision x1 et x2 sont positives : x1  0, x2  0 .
Etape 2 : Identification des contraintes. Dans ce problème les contraintes représentent la
disponibilité des facteurs de production :
• Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte liée à la
limitation de la surface de terrain est x1 + x2  150
• Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare de piments
demande 2m3 mais l’agriculteur ne dispose que de 440m3 . La contrainte qui exprime les
limitations des ressources en eau est .
• Main d’œuvre : Les 480 heures de main d’œuvre seront départagées (pas nécessairement en
totalité) entre la culture des tomates et celles des piments. Sachant qu’un hectare de tomates
demande une heure de main d’œuvre et un hectare de piments demande 4 heures de main
d’œuvre alors la contrainte représentant les limitations des ressources humaines est
x1 + 4 x2  480
• Les limitations du bureau du périmètre irrigué : Ces limitations exigent que l’agriculteur ne
cultive pas plus de 90 hectares de tomates. La contrainte qui représente cette restriction est
x1  90.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 4

Etape 3 : Identification de la fonction objectif. La fonction objectif consiste à maximiser le

profit apporté par la culture de tomates et de piments. Les contributions respectives 100 et 200,
des deux variables de décision x1 et x2 sont proportionnelles à leur valeur. La fonction objectif
est donc z = 100x1 + 200x2 .
Le programme linéaire qui modélise le problème d’agriculture est :
Max 100x + 200x
1 2
s.c. x +x  150
1 2
4 x + 2 x  440
1 2
x + 4 x  480
1 2
x  90
1
x  0, x  0
1 2

Exemple 2 : Problème de médecine 3

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 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 d’au moins 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.

Formulation du problème en un PL :

Le problème de médecine présente certaines ressemblances avec le problème de l’agriculture,

dans les deux cas c’est un problème d’allocation de ressources.
Les variables de décision qui représentent des valeurs inconnues par le décideur qui est dans ce
cas le spécialiste en médecine sont :
• x1 : le nombre de pilules de petite taille à prescrire.
• x2 : le nombre de pilules de grande taille à prescrire.
On vérifie bien que les variables de décision x1 et x2 sont positives : x1  0, x2  0 .
Les contraintes imposées par le problème sur les valeurs possibles de x1 et x2 sont :
• La prescription doit contenir des pilules avec au moins 12 grains d’aspirine. Sachant qu’une
petite pilule contient 2 grains d’aspirine et qu’une grande pilule contient un seul grain
d’aspirine, on obtient la contrainte suivante : 2 x1 + x2  12 .
• De la même façon que pour l’aspirine, la prescription du spécialiste en médecine doit
contenir au moins 74 grains de bicarbonate. Ainsi la contrainte suivante doit être satisfaite :
5x1 + 8x2  74 .
• Finalement la contrainte imposée par le fait que la prescription doit contenir au moins 24
grains de codéine est x1 + 6 x2  24 .
Etape 3 : Identification de la fonction objectif. On remarque qu’il y a plusieurs couples de
solutions ( x1 , x2 ) qui peuvent satisfaire les contraintes spécifiées à l’étape 2. La prescription
doit contenir le minimum possible de pilules. Donc le critère de sélection de la quantité de
pilules à prescrire est celle qui minimise le nombre total des pilules z = x1 + x2 .

3 An introduction to linear programming and the theory of games, A. M. Glicksman

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 5

Le programme linéaire qui modélise ce problème médical est donc le suivant :

Min x1 + x2
s.c. 2 x1 + x2  12
5 x1 + 8 x2  74
x1 + 6 x2  24
x1  0, x2  0

Exemple 3 : problème de production 4

Pour fabriquer deux produits P1 et P2 on doit effectuer des opérations sur trois machines M1,
M2 et M3, successivement mais dans un ordre quelconque. Les temps unitaires d’exécution
sont donnés par le tableau suivant :
M1 M2 M3
P1 11 mn 7 mn 6 mn
P2 9 mn 12 mn 16 mn
On supposera que les machines n’ont pas de temps d’inactivité.
Les disponibilités, pour chaque machine, sont :
• 165 heures (9900 minutes) pour la machine M1 ;
• 140 heures (8400 minutes) pour la machine M2 ;
• 160 heures (9600 minutes) pour la machine M3 .
Le produit P1 donne un profit unitaire de 900 dinars et le produit P2 un profit unitaire de 1000
dinars.
Dans ces conditions, combien doit-on fabriquer mensuellement de produits P1 et P2 pour avoir
un profit total maximum ?

Formulation en un PL :

Les variables de décisions sont :

• x1 : le nombre d’unités du produit P1 à fabriquer
• x2 : le nombre d’unités du produit P2 à fabriquer
Les contraintes outre les contraintes de non-négativité sont :
• 11x1 + 9 x2  9900 pour la machine M1
• 7 x1 + 12x2  8400 pour la machine M2
• 6 x1 + 16x2  9600 pour la machine M3
Le profit à maximiser est : z = 900x1 + 1000 x2

Le programme linéaire résultant est :

Max 900x1 + 1000x2
s.c. 11x1 + 9 x2  9900
7 x1 + 12 x2  8400
6 x1 + 16 x2  9600
x1  0, x2  0

4 Méthodes et modèles de la recherche opérationnelle, A. Kaufmann, pp 22 -23

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 6

Exemple 4 : Problème d’alimentation 5

On se propose de réaliser une alimentation économique pour des bestiaux, qui contient
obligatoirement 4 sortes de composants nutritifs, A, B, C et D. L’industrie alimentaire produit
précisément deux aliments M et N qui contiennent ces composants : 1 Kg d’aliment M contient
100 g de A, 100 g de C, 200 g de D ; 1 Kg d’aliment N contient 100 g de B, 200 g de C, 100 g
de D.
Un animal doit consommer par jour au moins : 0.4 Kg de A ; 0.6 Kg de B ; 2 Kg de C ; 1.7 Kg
de D. L’aliment M coûte 10 DT le Kg et N coûte 4 DT le Kg. Quelles quantités d’aliments M
et N doit-on utiliser par jour et par animal pour réaliser l’alimentation la moins coûteuse ?

Formulation en un PL :

On peut résumer toutes les données du problème dans le tableau suivant

M N Quantités prescrites
A 0.1 0 0.4
B 0 0.1 0.6
C 0.1 0.2 2
D 0.2 0.1 1.7
Coût 10 4
Ce genre de tableau peut aider à mieux analyser le problème et ainsi formuler le programme
linéaire correspondant.
Les variables de décision sont
• x1 : la quantité d’aliments M à utiliser pour l’alimentation des deux bestiaux
• x2 : la quantité d’aliments N à utiliser pour l’alimentation des deux bestiaux
Les contraintes de non-négativité sont x1  0, x2  0.
Le choix de cette quantité est contraint à la présence dans l’alimentation du composant
• A : 0.1 x1  0.4  x1  4
• B : 0.1 x2  0.6  x2  6
• C : 0.1 x1 + 0.2 x2  2  x1 + 2 x2  20
• D : 0.2 x1 + 0.1 x2  1.7  2 x1 + x2  17
La fonction objectif est une fonction de coût : z = 10x1 + 4 x2 .
Le programme linéaire est un programme de minimisation :

Min 10 x1 + 4 x2
s.c. x1  4
x2  6
x1 + 2 x2  20
2 x1 + x2  17
x1  0, x2  0

5 Méthodes et modèles de la recherche opérationnelle, A. Kaufmann, pp 24 -25

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 7

Exemple 5 : Problème de mélange 6

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 :

Compositions des A B C D E F G H I Alliage à

alliages fabriquer
(en %)
Plomb 10 10 40 60 30 30 30 50 20 30
Zinc 10 30 50 30 30 40 20 40 30 30
Etain 80 60 10 10 40 30 50 10 50 40
Coût au Kilo 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 1 Kg de l’alliage Z ?

Formulation en un PL :

La décision à prendre : Combien acheter de chaque alliage A, B, …, I ?

Les variables de décision sont :
• xi : la quantité d’alliage i, i= A, B, …, I, à acheter.
On vérifie bien que les variables de décision xi, i= A, B, …, I, sont positives :
xA  0, xB  0, xC  0, xD  0, xE  0, xF  0, xG  0, xH  0, xI  0 .

Les contraintes relatives au problème sont :

• Equation de la conservation de la matière : x A + x B + xC + x D + x E + x F + xG + x H + x I = 1
• Equation de la satisfaction des proportions en Plomb :
0.1x A + 0.1 x B + 0.4 x C + 0.6 x D + 0.3 x E + 0.3 x F + 0.3 x G + 0.5 x H + 0.2 x I = 0.3
• Equation de la satisfaction des proportions en Zinc :
0.1 x A + 0.3 x B + 0.5 xC + 0.3 x D + 0.3 x E + 0.4 x F + 0.2 xG + 0.4 x H + 0.3 x I = 0.3
• Equation de la satisfaction des proportions en Etain :
0.8 x A + 0.6 xB + 0.1 xC + 0.1 xD + 0.4 xE + 0.3 xF + 0.5 xG + 0.1 xH + 0.5 xI = 0.4
La fonction objectif dans cet exemple représente le coût d’achat des différents alliages A, B, C,
D, E, F, G, H et I. Donc l’expression de la fonction objectif est la suivante :
z = 4.1 x A + 4.3 x B + 5.8 xC + 6 x D + 7.6 x E + 7.5 x F + 7.3 xG + 6.9 x H + 7.3 x I
Le programme linéaire qui modélise ce problème de mélange s'écrit :
Min 4.1 x A + 4.3 xB + 5.8 xC + 6 xD + 7.6 xE + 7.5 xF + 7.3 xG + 6.9 xH + 7.3 xI
s.c. x A + xB + xC + xD + xE + xF + xG + xH + xI = 1
0.1 x A + 0.1 xB + 0.4 xC + 0.6 xD + 0.3 xE + 0.3 xF + 0.3 xG + 0.5 xH + 0.2 xI = 0.3
0.1 x A + 0.3 xB + 0.5 xC + 0.3 xD + 0.3 xE + 0.4 xF + 0.2 xG + 0.4 xH + 0.3 xI = 0.3
0.8 x A + 0.6 xB + 0.1 xC + 0.1 xD + 0.4 xE + 0.3 xF + 0.5 xG + 0.1 xH + 0.5 xI = 0.4
x A , xB , xC , xD , xE , xF xG , xH , xI  0

6 G. B. Dantzig applications et prolongements de la programmation linéaire pp :13-14

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 8

Exemple 6 : Sélection de Médias 7

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 :
Télévision Radio Journaux
Locale Par satellite
Coût d’une publicité 40 DT 75 DT 30 DT 15 DT
Nombre de clients potentiels 400 900 500 200
par publicité
Nombre de clients potentiels 300 400 200 100
femmes par publicité

Pour la campagne, on prévoit de ne pas payer plus que 800 DT pour toute la campagne et on
demande que ces objectifs soient atteints :
1. Au minimum 2000 femmes regardent, entendent ou lisent la publicité ;
2. La campagne publicitaire dans la télévision ne doit pas dépasser
500 DT ;
3. Au moins 3 spots publicitaires seront assurés par la télévision locale et au moins de deux
spots par la télévision par satellite.
4. Le nombre des publicités dans la radio ou dans les journaux sont pour chacun entre 5 et 10.

Formulation en un PL :

Les variables de décision du problème sont :

• 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
Les contraintes de non-négativité sont vérifiées.
Les contraintes du problème sont :
• Coût total de la compagne publicitaire : 40x1 + 75x 2 + 30x3 + 15x 4  800
• Nombre de clients femmes potentiels par publicité :
300x1 + 400x2 + 200x3 + 100x 4  2000
• Contraintes de la télévision : 40x1 + 75x2  500 , x1  3 et x 2  2
• Contraintes sur le nombre de publicités dans la radio et dans les journaux 5  x3  10 et
5  x4  10 .
La fonction objectif à maximiser représente le nombre de clients potentiels par publicité
z = 400 x1 + 900 x2 + 500 x3 + 200 x4 .

7 Operations research principles and practice, pp17-18

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 9

Le programme linéaire résultant est :

Max 400 x1 + 900 x2 + 500 x3 + 200 x4

s.c. 40x1 + 75 x2 + 30x3 + 15x4  800
30x1 + 40 x2 + 20x3 + 10x4  2000
40x1 + 75 x2  500
x1 3
x2 2
x3 5
x3  10
x4 5
x4  10
x1  0, x2  0, x3  0, x4  0

CHAP.2 : RESOLUTION GRAPHIQUE D’UN PROGRAMME LINEAIRE (PL)

I. Introduction
Après avoir illustré par des exemples, comment un problème pratique peut être modélisé par
un programme linéaire, l’étape qui va suivre sera certainement celle de la résolution de ce
problème mathématique. La méthode graphique est l’une des premières méthodes utilisées à ce
sujet.

Si on parle de résolution graphique alors on doit se limiter à une représentation à deux variables
et au plus à trois variables. Ceci indique que dans ce chapitre on examinera seulement les
programmes linéaires à deux variables de décision.

II. Système d’axes

Une des conditions de la réussite de notre représentation graphique est le choix d'un système
d’axes. Un mauvais choix peut rendre notre représentation non claire et imprécise.

A cause des contraintes de non-négativité des variables de décision, nous nous intéressons
seulement au cadran positif (voir figure ci-dessus).
Cette région s’appelle la région des solutions possibles du problème.
Prenons l’exemple 2 relatif au problème de médecine. Le programme linéaire est le suivant :

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 10

Min x1 + x 2
s.c. 2 x1 + x 2  12
5 x1 + 8 x 2  74
x1 + 6 x 2  24
x1  0, x 2  0

Un bon choix se base sur une lecture des différents paramètres du programme linéaire. Dans
notre cas, on ne peut pas qualifier de bon, le choix de 20 comme unité dans les deux axes.

Pour l’exemple, on peut choisir le système d’axes suivant :

x2

12

6
3

x1
6 12 24

III. Représentation graphique des contraintes

Parmi les solutions possibles d’un problème, il y a ceux qui vont satisfaire toutes les contraintes
du programme, appelés solutions réalisables, et ceux qui vont satisfaire une partie ou aucune de
ces contraintes, appelés solutions non réalisables.

Une représentation graphique des inégalités (des contraintes) va nous permettre de déterminer
l’ensemble des solutions réalisables.

Revenons à l’exemple 2 du problème de médecine.

Une des contraintes de ce problème est celle relative au grain d’aspirine :

2 x1 + x2  12 .

L’ensemble des solutions qui vérifient cette inégalité est le même que celui qui vérifie
2 x1 + x2 = 12 et 2 x1 + x2  12 .

x2

12

6
3

x1
6 12 24

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 11

L’ensemble des solutions qui correspond à l’équation est l’ensemble des points de la droite l
définie par x2 = −2 x1 + 12 . Cette droite admet une valeur de la pente égale à –2 et intercepte
l’axe des ordonnées en 12 (voir figure ci-dessus).

L’inégalité 2 x1 + x2  12 correspond à un demi-plan limité par la droite x2 = −2 x1 + 12 . Or

cette droite divise le plan en deux demi-plans ouverts donc quel est le demi-plan à choisir ?

x2

12 1

6
3

x1
6 12 24

Pour ce faire, il suffit de prendre un point de l’un des demi-plans (c’est à dire n’appartenant pas
à la droite x2 = −2 x1 + 12 ) et voir s’il vérifie l’inégalité 2 x1 + x2  12 . Par exemple le point de
coordonnées (0,0) ne vérifie pas l’inégalité 2 x1 + x2  12 donc le demi-plan 1 , au-dessus de la
droite, est celui recherché (voir figure ci-dessus).

L’espace hachuré représente le demi-plan fermé des solutions qui vérifient la contrainte
2 x1 + x2  12 .

Si on fait de même pour les deux autres contraintes du problème (voir figures
ci-dessous), on obtient les deux autres demi-plans 2 et 3 relatifs aux solutions vérifiant
respectivement les contraintes 5 x1 + 8x2  74 et x1 + 6 x2  24 .

3 2
9.25

6
4
3

x1 x1
6 12 24 6 14,8 24

Une solution possible du problème est dite réalisable si et seulement si elle vérifie toutes les
contraintes, c’est à dire si elle appartient aux trois demi-plans relatifs à chaque contrainte du
programme linéaire, en d’autres termes à
1  2  3 (voir figure).

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 12

x2
Ensemble des
12 solutions
réalisables

x1
6 12 24

IV. Représentation de la fonction objectif

Soit z la valeur de la fonction objectif du problème de médecine z = x1 + x2 .
Pour z=0, la fonction objectif est représentée de la manière suivante :
x2

12

x1
6 24
x1 + x 2 = 0

Pour z=6, c’est à dire que le nombre de pilules à prescrire est égale à 6 pilules. La fonction
objectif est représentée comme suit :

x2

12

x1
6 24
x1 + x 2 = 6

Chaque point du segment qui relie les points (6,0) à (0,6) représente des solutions qui
engendrent une prescription avec 6 pilules des deux tailles.
On peut tracer une infinité de droites qui représentent les différentes valeurs de la fonction
objectif, toutes ces droites ont le même coefficient directeur (-1). Par suite elles sont parallèles
entre elles. De plus on peut diminuer la valeur de z indéfiniment dans le sens indiqué dans la
figure ci-dessous.
x2

12

x1
6
z = 18
z = 6 z = 12
Le problème est de connaître quelle est la droite qui correspond à la valeur minimale de la
fonction objectif ?

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 13

V. Recherche de la solution optimale

a. Résolution graphique
Si nous retraçons l’ensemble des droites parallèles relatives à différentes valeurs de la fonction
objectif sur la figure qui représente l’ensemble des solutions réalisables, on peut localiser la
solution optimale. Elle correspond à la solution réalisable qui intercepte la droite à la plus petite
valeur de z.

x2

12
B

x1
6 12
Z=10

Dans notre exemple, la solution optimale est l’intersection des deux contraintes 2 x1 + x2  12
et 5 x1 + 8x2  74 . Une évaluation des coordonnées de ce point revient à résoudre le système
linéaire suivant :

 2 x1 + x2 = 12

5 x1 + 8 x2 = 74

Elle correspond d’après le graphique au point (2,8). Donc la prescription optimale est de 2
pilules de petite taille et 8 pilules de grande taille. Le nombre de pilules (la valeur de la fonction
objectif) est égale à 10.

b. Résolution par énumération :

On remarque que la solution optimale du problème de médecine est un point extrême qui se
trouve sur le bord de l’ensemble des solutions. Une telle solution est dite solution réalisable de
base.

On peut admettre le résultat suivant : « Si un programme linéaire admet une solution optimale
alors il existe une solution réalisable de base pour laquelle la fonction objectif atteint la valeur
optimale »

Une méthode de résolution du programme linéaire consiste donc à déterminer les solutions
réalisables de base (les points d’intersection des droites qui forment les contraintes) et à calculer
pour chaque point la valeur de la fonction objectif. La solution du programme linéaire est la
solution à qui on associe la valeur optimale de la fonction objectif.
x2

12 A
B

3 C D

x1
6 12

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 14

Dans le problème de médecine, l’ensemble des solutions réalisables de base présente 4 points
extrêmes A(0,12), B(2,8), C(23/11,126/11) et D(24,0). La valeur de la fonction objectif associée
respectivement à A, B, C et D est 12, 10, 149/11 et 24. On vérifie bien que B est la solution
optimale du problème avec une valeur optimale égale à 10.

VI. Exemples
Dans cette section on donne quelques exemples de résolution graphique de problèmes
linéaires relatifs aux différents cas possibles :

Problème de maximisation
Max 100 x1 + 200 x2 x2 (2)
(4)
s.c. x1 + x2  150 (1) A
B

4 x1 + 2 x2  440 (2)
110
C
(3)
x1 + 4 x2  480 (3) Z=0 30
D (1)

x1  90 (4) 40
E x1

x1  0, x2  0
la solution optimale est B(40,110)

Problème avec solution non bornée

Max - 2 x1 + 3x 2 x2

s.c. x1  5 (1) (2)

2 x1 − 3x 2  6 (2)
x1  0, x 2  0
5 x1
Z=0
(1)

On peut augmenter la valeur de la fonction objectif dans la direction des flèches indéfiniment
donc la solution est non bornée

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 15

Problème impossible
Min 3x1 + 2 x 2 x2

s.c. x1 + 2 x 2  2 (1)
2 x1 + 4 x 2  8 (2)
x1  0, x 2  0
x1
(2)
(1)

L’espace des solutions réalisables est vide, il est l’intersection des deux zones grises de la
figure ci-dessus

Problème à solutions multiples

Max x1 + 3 x 2 x2
(2)

s.c. 2 x1 + 6 x 2  30 (1) (1)

A (3)
x1  10 (2) B

x2  4 (3)
10 x1
x1  0, x 2  0
Z=0

L’ensemble des points décrit par le segment [AB] représente les solutions optimales du
problème linéaire

Problème de dégénerescence
Max x1 + x 2 x2
(2)

s.c. 3 x1 + 2 x 2  40 (1) (1)

B (3)
A
x1  10 (2)
x2  5 (3)
x1  0, x 2  0
O C x1

Z=0

La solution optimale B(10,5) est dite dégénérée si trois contraintes concourent en ce point.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 16

VII. Analyse de sensibilité

Une analyse de sensibilité se résume à la recherche des intervalles de variations possibles des
paramètres du programme linéaire sans que la solution optimale ne soit modifiée.

Question : De combien peut-on faire varier la quantité de codéine dans le problème de

médecine sans changer la solution optimale.

Réponse :

x2

12
B

x1
6 12
Z=10

On peut changer la valeur du second membre de la troisième contrainte jusqu'à ce que la droite
de coefficient directeur –1/6 touche le point optimal (2,8). C’est à dire qu’on peut varier le
second membre de la troisième contrainte de 24 jusqu'à 50 sans changer la solution optimale.

Question : De combien peut-on faire varier le profit engendré par la culture d’un hectare de
tomates, dans le problème de l'agriculture, sans changer la solution optimale ?

Réponse :

x2 (2)
(4)
A
B
110
C
(3)
Z=0 30
D (1)

E x1
40

Soit  la variation du profit engendré par la culture d’un hectare de tomate. La fonction objectif
est égale à (100 +  ) x1 + 200x2

La solution demeure optimale si la pente de la fonction objectif reste toujours comprise entre la
pente de la contrainte (1) et (3). Ceci est équivalent à dire que :
(100 + 𝜆) 1
−1 ≤ − ≤− − 50 ≤ 𝜆 ≤ 100
200 4
On peut vérifier aussi que si :
•   −50 alors la solution optimale est A
•  = −50 alors le problème est à solutions multiples : [AB]
• − 50    100 alors la solution optimale est B
•  = 100 alors le problème est à solutions multiples : [BC]

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 17

• 100    300 alors la solution optimale est C

•  = 300 alors le problème est à solutions multiples : [CD]
•   300 alors la solution optimale est D

CHAP.3 : LA METHODE DE SIMPLEXE

I. Introduction
On a présenté dans le chapitre précédent une procédure graphique pour résoudre un programme
linéaire à deux variables. Par contre, dans la plupart des problèmes réels, on a plus que deux
variables à déterminer. Une procédure algébrique pour résoudre les programmes linéaires avec
plus que deux variables fera l’objet de ce chapitre. C'est la méthode de simplexe.

Une implémentation de cette procédure a permis de résoudre des programmes avec un peu plus
de quelques milliers de variables. Le programme LINDO (Linear INteractive Discrete
Optimizer) supporte au plus 200 variables et 100 contraintes.

Max c t x
Dans ce chapitre la méthode de simplexe est présentée pour les problèmes s.c Axb et
X 0
en utilisant le problème de l’agriculteur :

Max 100x1 + 200x2

s.c. x1 + x2  150
4 x1 + 2 x2  440
x1 + 4 x2  480
x1  90
x1  0, x2  0

II. Mise sous forme standard

La mise sous forme standard consiste à introduire des variables supplémentaires (une pour
chaque contrainte) de manière à réécrire les inégalités (  ) sous la forme d'égalités. Chacune de
ces variables représente le nombre de ressources non utilisées. On les appelle variables d'écart.
La forme standard s'écrit donc :
Max c1 x1 + c2 x2 +  + c N x N
s.c a11 x1 + a12 x2 +  + a1N x N + S1 = b1
Max c t x
 a 21 x1 + a 22 x2 +  + a 2 N x N + S 2 = b2
s.c Ax+S b

X  0, S  0
a M 1 x1 + a M 2 x2 +  + a MN x N + S M = bM
x1  0, x2  0, , x N  0
S1  0, S 2  0, , S M  0

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 18

La forme standard du programme linéaire de l'agriculteur est :

Max 100x1 + 200x2 (3.1)

s. c x1 + x2 + S1 = 150 (3.2)
4x1 + 2x2 + S2 = 440 (3.3)
x1 + 4x2 + S3 = 480 (3.4)
x1 + S4 = 90 (3.5)
x1 , x2 , S1 , S2 , S3 , S4 0 (3.6)
L'impact de ces variables d'écart sur la fonction objectif est nul. Ceci explique le fait que leur
existence soit tout simplement liée à une mise en forme du programme linéaire initial. Ces
variables d'écart peuvent prendre des valeurs non négatives. Le fait de donner la valeur des
variables d'écart à l'optimum donne une idée du nombre des ressources non utilisées.

III. Revue algébrique de la méthode du simplexe

La question qui se pose : que demande-t-on d’une procédure algébrique ?

En premier lieu, on note que les contraintes, du problème (3.2)-(3.5), forment un système de 4
équations et de 6 variables. Or il y a un nombre infini de solutions de ce système d’équations.
Donc une procédure algébrique, pour la résolution d’un programme linéaire doit être capable
de retrouver les solutions des systèmes d’équations où il y a plus de variables que de contraintes.

En deuxième lieu, ce ne sont pas toutes les solutions qui vérifient (3.2)-(3.5) qui sont des
solutions du programme linéaire ; ils doivent en plus satisfaire les contraintes de non-négativité.
Ainsi une procédure algébrique doit être capable d’éliminer, de l’ensemble des solutions qui
satisfait (3.2)-(3.5) celles qui n’arrivent pas à satisfaire les contraintes de non-négativité.

Finalement, une procédure algébrique pour résoudre les programmes linéaires doit être en
mesure de choisir parmi les solutions réalisables ceux qui maximisent la fonction objectif.

La méthode de simplexe est une procédure algébrique qui tient compte de ces trois
considérations.

Pour illustrer cette procédure, supposons que x2 = 0 et S1 = 0. Notre système devient

x1 = 150 x1 = 150
4x1 + S2 = 440 S2 = -160
x1 + S3 = 480 S3 = 330
x1 + S4 = 90 S4 = -60

Les variables x1 , S2 , S3 et S4 (non nulles) sont dites variables de base et les variables S1 , x2,
(nulles) sont dites variables hors base.

Généralement, si on a un programme linéaire standard constitué de n variables et m contraintes

(n  m) alors une solution de base (extrême) est obtenue, en annulant (n-m) variables et en
résolvant les m contraintes pour déterminer les valeurs des autres m variables.

On note qu’une solution de base n’est pas toujours réalisable. C’est le cas de la solution qu’on
vient de retrouver.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 19

Une solution réalisable de base serait celle où x1 = x2 = 0, ainsi on a :

S1 = 150
S2 = 440
S3 = 480
S4 = 90
Cette solution correspond à un point extrême de l’ensemble des solutions réalisables qui est
l’origine O.

Pour la méthode de simplexe une solution réalisable de base initiale est demandée. Une telle
solution peut être retrouvée en annulant toutes les variables de décision. Ce qui correspond dans
notre exemple au point d’origine O.

A partir de ce point la méthode de simplexe va générer successivement des solutions réalisables

de base pour notre système d’équations en s’assurant que la valeur de la fonction objectif est en
train d’augmenter jusqu'à localiser la solution optimale du problème qui est un point extrême
de l’espace des solutions réalisables donc une solution réalisable de base.

Ainsi, on peut décrire la méthode de simplexe comme étant une procédure itérative qui passe
d’une solution réalisable de base à une autre jusqu’à atteindre la solution optimale.

La description mathématique de ce processus fera l’objet de la section suivante.

IV. La méthode des tableaux

La méthode de simplexe commence par l'identification d'une solution réalisable de base et
ensuite, elle essaye de trouver d'autres solutions réalisables de base jusqu’à atteindre à la
solution optimale. Ainsi, on doit, tout d’abord, retrouver cette solution réalisable de base.

Généralement si le programme linéaire satisfait ces deux propriétés :

P1/ Parmi les variables du programme standard, il y a m variables qui apparaissent avec un
coefficient non nul dans chaque contrainte (dans notre exemple : S1 , S2 , S3 et S4 ).

P2/ Les valeurs du second membre des contraintes (les composants du vecteur b) sont positives.

Alors une solution réalisable de base est obtenue en annulant les (n-m) variables de décision et
la valeur des variables d'écart est directement donnée par le second membre. La deuxième
propriété assure la satisfaction des contraintes de non-négativité des variables d'écart.

Dans notre exemple, la forme standard du programme linéaire vérifie ces deux propriétés.

a. Tableau de simplexe initial

Après avoir mis le programme linéaire sous une forme qui vérifie les deux propriétés P1 et P2,
l’étape suivante est de tracer le tableau de simplexe initial.

Le modèle général des tableaux de simplexe est :

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 20

cj coefficient qui correspond aux

variables

Toutes les variables

Ci VB Qi A = (aij)i,j
coefficie varia Valeur matrice des coefficients
nts des bles des des contraintes du programme
variable de variabl standard
s de base es de
base base
Pour notre exemple le tableau de simplexe initial est le suivant :

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 150 1 1 1 0 0 0
0 S2 440 4 2 0 1 0 0
0 S3 480 1 4 0 0 1 0
0 S4 90 1 0 0 0 0 1
On remarque qu’on a placé en première ligne les contributions unitaires de toutes les variables
de décision x1 ,..., S4 dans la fonction objectif. Dans la troisième ligne, on retrouve la première
contrainte x1 + x2 + S1 = 150. La valeur 150 représente ici la valeur de S 1 relative à la solution
réalisable de base initiale. Dans la première colonne on trouve les contributions nulles des
variables d'écart qui forment la solution de base initiale.

Exemple :

Question : Quelles sont les contraintes et la fonction objectif du programme linéaire décrit par
le tableau de simplexe suivant :

6 7 0 0
x1 x2 S1 S2
0 S1 50 4 2 1 0
0 S2 40 1 5 0 1
Réponse : Les contraintes du programme sont :
4 x1 + 2x2 + S1 = 50
x1 + 5x2 + S2 = 40
et la fonction objectif est : 6x1 + 7x2 + 0S1 + 0S2

Remarque : Les variables qui figurent dans la deuxième colonne sont dites variables de base.
A chacune de ces variables, on associe la valeur 1 à l’intersection de la ligne et de la colonne
relative à cette variable et dans le reste de la colonne on trouve des zéros.

Jusqu’ici on a vu comment retrouver une solution réalisable de base et comment présenter le

tableau de simplexe initial. Dans la section suivante, on examinera la procédure liée à la

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 21

méthode de simplexe qui permet de passer de cette solution réalisable de base initiale à une
autre solution réalisable de base qui donne une meilleure valeur de la fonction objectif.

b. Amélioration de la solution
Pour améliorer la solution il faut générer une autre solution de base (point extrême) qui
augmente la valeur de la fonction objectif. C’est à dire, qu’on doit sélectionner une variable
hors base et une variable de base et les permuter de telle façon que la nouvelle solution donne
une plus grande valeur de la fonction objectif.

Pour savoir si on peut améliorer notre solution réalisable de base initiale nous allons introduire
deux nouvelles lignes en dessous du tableau de simplexe.

La première ligne, notée zj, représente la variation de la valeur de la fonction objectif qui résulte
du fait qu’une unité de la variable correspondante à la jème colonne de la matrice A est amenée
dans la base. Par exemple z1 représente la diminution du profit qui résulte de l’ajout d’une unité
à la valeur de x1 .

En effet, si on produit un hectare supplémentaire de x1 , la valeur de quelques variables de base

vont changer vu qu’on a :

x1 + S1 = 150
4x1 + S2 = 440
x1 + S3 = 480
x1 + S4 = 90
Donc, une augmentation de x1 de 0 vers 1 va être accompagnée d'une diminution des variables
de base S1 , S2 , S3 , S4 respectivement de 1, 4, 1 et 1.

L’effet de cette diminution sur la fonction objectif est nul car les coefficients des variables
d’écarts dans cette fonction sont nuls

z1 = 0  1 + 0  4 + 0  1 + 0  1 = 0

La valeur z1 est calculée en multipliant les coefficients de la première colonne de la matrice A

relatifs à la variable x1 par les coefficients ci de la première colonne. Généralement, on a :

zj =  aij  ci
i

La deuxième ligne, notée cj - zj, représente l’effet net de l’augmentation d’une unité de la jème
variable.

Dans notre exemple, l’effet net sur la fonction objectif engendré par l’augmentation d’une unité
dans la valeur de x1 est

c1 - z1 = 100 - 0 = 100

Si on reprend la même opération pour le reste des variables, on trouve le tableau suivant :

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 22

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 150 1 1 1 0 0 0
0 S2 440 4 2 0 1 0 0
0 S3 480 1 4 0 0 1 0
0 S4 90 1 0 0 0 0 1
zj 0 0 0 0 0 0
cj - zj 100 200 0 0 0 0

En analysant la ligne relative à l’évaluation nette cj - zj, on remarque qu’une augmentation d’une
unité de la valeur de x1 engendre un profit de 100 dinars, et qu’une augmentation d’une unité
de la valeur de x2 engendre un profit supplémentaire de 200 dinars. Donc, si on a à choisir, on
va opter pour une augmentation de la valeur de x2. On dit que x2 est la variable entrante.

Le problème est maintenant, jusqu’où peut-on augmenter x2 ?

Cette augmentation ne peut pas se faire infiniment, sous l’hypothèse que x1 reste nulle. On a

x2 + S1 = 150
2x2 + S2 = 440
4x2 + S3 = 480
S4 = 90
On peut voir que x2 peut prendre comme valeur maximale la valeur de 120 (il ne faut pas oublier
que les Si, i=1, 2, 3, 4 sont des variables positives). Cette valeur est obtenue en choisissant la
plus petite valeur positive des divisions de 150/1, 440/2, 480/4 et 90/0 (on suppose que 90/0 est
égale à l’infini ).

En général, la valeur maximale de la variable entrante xj est le minimum des valeurs positives
des rapports de Qi par les coefficients de la colonne de la matrice A relatif à la jème variable. Ces
rapports feront l’objet d’une autre colonne à droite de la matrice A.

Dans notre exemple, on aura :

100 200 0 0 0 0
X1 x2 S1 S2 S3 S4
0 S1 150 1 1 1 0 0 0 150
0 S2 440 4 2 0 1 0 0 220
0 S3 480 1 4 0 0 1 0 120
0 S4 90 1 0 0 0 0 1 
0 0 0 0 0 0
100 200 0 0 0 0

Le fait d’augmenter x2 jusqu’à la valeur 120 va engendrer l’annulation de la valeur de la variable

d’écart S3 , ce qui élimine S3 de la base. On appelle S3 variable sortante.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 23

L’élément 4, à l’intersection de la ligne relative à la variable sortante S3 (dite ligne pivot) et de

la colonne relative à la variable entrante x2 (dite colonne pivot) est l’élément pivot. (C’est
l’élément cerclé dans le tableau).

c. Calcul des tableaux suivants

Dans le nouveau tableau de simplexe on va remplacer S3 par x2 et l’ensemble des variables de
base deviendra S1 , S2 , x2 , S4 . On exige que x2 prenne la même place dans la colonne des variables
de base que celle de la variable sortante S3 .

Jusqu’à maintenant on ne peut pas remplir le tableau relatif à cette nouvelle solution de base :

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1
0 S2
200 x2
0 S4

Ce qui reste à déterminer sont les coefficients aij de la nouvelle matrice A et les valeurs Qi des
variables de base. Ceci est réalisé en utilisant la règle de pivot :

1) Diviser la ligne de pivot par la valeur de l’élément de pivot pour trouver la ligne transformée
de la ligne de pivot.

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1
0 S2
200 x2 120 1/4 1 0 0 1/4 0
0 S4

2) A chacune des variables de base, on associe la valeur 1 à l’intersection de la ligne et de la

colonne relative à cette même variable et dans le reste de la colonne on trouve des zéros.

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 0 1 0 0
0 S2 0 0 1 0
200 x2 120 1/4 1 0 0 1/4 0
0 S4 0 0 0 1

3) Pour calculer le reste des valeurs du tableau, on opère à des combinaisons linéaires dans le
précèdent tableau de simplexe. Par exemple pour calculer la nouvelle valeur qui va prendre
la place de la valeur 150 devant la variable de base S1: On multiplie 150 par le pivot (4), on

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 24

retranche de ce produit le produit de la projection de la valeur 150 sur la ligne pivot par la
projection de la valeur 150 sur la colonne pivot, et on divise le tout par la valeur du pivot
(4).
100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 150 1 1 1 0 0 0
0 S2 440 4 2 0 1 0 0
0 x2 480 1 4 0 0 1 0
0 S4 90 1 0 0 0 0 1

150  4 − 480  1 0  4 − 11 1

= 30 =−
4 4 4

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 30 0 1 0 -1/4 0
0 S2 0 0 1 0
200 x2 120 1/4 1 0 0 1/4 0
0 S4 0 0 0 1

En appliquant cette règle sur notre exemple, on trouve le tableau suivant :

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 30 3/4 0 1 0 -1/4 0
0 S2 200 7/2 0 0 1 -1/2 0
200 x2 120 1/4 1 0 0 1/4 0
0 S4 90 1 0 0 0 0 1

Remarques :

a) On vérifie toujours que les colonnes de la matrice relative à chacune des variables de base
sont formées par des zéros sauf 1 dans l’intersection avec la ligne relative aux mêmes
variables de base.
b) On peut vérifier aussi que l’ensemble des solutions réalisables, induit par les contraintes
décrites dans le dernier tableau de simplexe, est le même que celui représenté par les
contraintes initiales. La règle de pivot est une combinaison linéaire des contraintes du
programme linéaire donc elle ne change pas l’ensemble des solutions réalisables.
c) La nouvelle solution réalisable de base est
x1 = 0
x2 = 120
S1 = 30
S2 = 200
S3 = 0
S4 = 90
Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :
ericnduwi@[Link], enduwimana@[Link]
 25

Cette nouvelle solution correspond au point A(voir graphique). On vérifie bien que la valeur de
la fonction objectif est passée de 0 à 120 x 200. La valeur de la fonction objectif peut être
facilement calculée en multipliant membre à membre les ci de la première colonne par les
valeurs des variables de base Qi dans la 3ème colonne.

d) La solution de départ correspond au point O. La première itération nous a amené dans le

sens de l'amélioration du profit (fonction objectif), c’est à dire le long de l’axe des
ordonnées.
Ayant retrouvé une nouvelle solution, on veut savoir s’il est possible de retrouver une solution
réalisable de base meilleure. Pour arriver à cette fin, on doit ajouter les deux lignes relatives au
choix de la variable entrante, et la colonne relative au choix de la variable sortante.

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 30 3/4 0 1 0 -1/4 0 40
0 S2 200 7/2 0 0 1 -1/2 0 400/7
200 x2 120 1/4 1 0 0 1/4 0 480
0 S4 90 1 0 0 0 0 1 90
50 200 0 0 50 0
50 0 0 0 -50 0

La variable entrante est x1 ; elle présente la plus grande valeur cj- zj. Si on calcule les quotients
Qi/ci1 , on retrouve que la variable sortante est S1 à qui on associe la plus petite valeur du ratio
Q1 /c11 =40. L’élément pivot dans ce tableau est 3/4. La nouvelle base est composée de x1 , S2,
x2 , S4 .

Le tableau de simplexe suivant issu de l’application de la règle de pivot est :

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
100 x1 40 1 0 4/3 0 -1/3 0
0 S2 60 0 0 -14/3 1 2/3 0
200 x2 110 0 1 -1/3 0 1/3 0
0 S4 50 0 0 -4/3 0 1/3 1
Cette nouvelle solution
x1 = 40
x2 = 110
S1 = 0
S2 = 60
S3 = 0
S4 = 50
correspond au point B qui est, d’après les résultats retrouvée par la méthode graphique, la
solution optimale du problème. Ainsi, il faut s’attendre à ce que la méthode de simplexe
reconnaisse cette solution comme étant la solution optimale.

Ajoutons la ligne relative au calcul de l'effet net d’une augmentation unitaire d’une des variables
du problème, on a :

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 26

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
100 x1 40 1 0 4/3 0 -1/3 0
0 S2 60 0 0 -14/3 1 2/3 0
200 x2 110 0 1 -1/3 0 1/3 0
0 S4 50 0 0 -4/3 0 1/3 1
100 200 200/3 0 100/3 0
0 0 -200/3 0 -100/3 0
L’effet net associé aux variables hors base S1 et S3 est négatif. Ceci nous oblige à dire que faire
entrer une de ces deux variables dans la base va engendrer une diminution dans la valeur de la
fonction objectif. Donc il n’y a pas une autre solution réalisable de base qui peut engendrer un
profit meilleur. Par suite cette dernière solution est la solution optimale. Ce dernier tableau de
simplexe est donc dit tableau optimal.

On peut généraliser ce résultat en disant que la solution optimale d’un programme linéaire est
atteinte s’il n’y a aucune valeur positive dans la ligne
cj-zj du tableau du simplexe.

V. Résumé de la procédure de la méthode du simplexe

(dans le cas d'un problème de maximisation sous contraintes  et avec un second membre
positif)

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

VI. Exemple
Résoudre le programme linéaire suivant en utilisant la méthode de simplexe.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 27

Max 3x1 + 2x2

SC - x1 + 2x2  4
3x1 + 2x2  14
x1 - x2  3
x1  0 x2  0
→ La forme standard du programme linéaire s'écrit comme suit :
Max 3x1 + 2x2
SC - x1 + 2x2 + S1 = 4
3x1 + 2x2 + S2 = 1 4
x1 - x2 + S3 = 3
x1 , x2, S1 , S2 , S3 0
→ Tableau de simplexe initial (1ère itération)

3 2 0 0 0
x1 x2 S1 S2 S3
0 S1 4 -1 2 1 0 0 -4
0 S2 14 3 2 0 1 0 14/3
0 S3 3 (1) -1 0 0 1 3
0 0 0 0 0
3 2 0 0 0

La variable entrante est x1 puisqu’elle présente le plus grand effet net positif. La variable
sortante est S3 car elle correspond au plus petit quotient positif.

→ 2ème itération

3 2 0 0 0
x1 x2 S1 S2 S3
0 S1 7 0 1 1 0 1 7
0 S2 5 0 (5) 0 1 -3 1
3 x1 3 1 -1 0 0 1 -3
3 -3 0 0 3
0 5 0 0 -3

La variable entrante est x2 et la variable sortante est S2

→ 3ème itération

3 2 0 0 0
x1 x2 S1 S2 S3
0 S1 6 0 0 1 -1/5 8/5
2 x2 1 0 1 0 1/5 -3/5
3 x1 4 1 0 0 1/5 2/5
3 2 0 1 0
0 0 0 -1 0

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 28

Tous les cj-zj 0 donc le tableau de simplexe est optimal et la solution optimale du programme
linéaire est

x1 = 4
x2 = 1
S1 = 6
S2 = 0
S3 = 0
La valeur de la fonction objectif est 14.

Remarque : L’effet net de l’augmentation d’une unité de la valeur de S3 (variable hors base)
est nul. Donc si on introduit S3 dans la base, on ne modifie pas la valeur de la fonction objectif.
Ainsi une autre solution optimale peut être trouvée pour notre programme linéaire.

Le tableau du simplexe suivant est :

3 2 0 0 0
x1 x2 S1 S2 S3
0 S3 15/4 0 0 5/8 -1/8 1
2 x2 13/4 0 1 3/8 1/8 0
3 x1 5/2 1 0 -1/4 1/4 0
3 2 0 1 0
0 0 0 -1 0
Le tableau est optimal et la solution correspondante est :

x1 = 5/2
x2 = 13/4
S1 = 0
S2 = 0
S3 = 15/4
La valeur de la fonction objectif est 14.

CHAP.4 : PROBLEMES DE MINIMISATION ET PROBLEMES IRREGULIERS

I. Introduction
Dans le chapitre précédent tous les programmes linéaires qu’on a traités sont du type :
Maximiser une fonction linéaire sous contraintes de type inférieur ou égale (et avec un second
membre positif).

Or dans beaucoup de problèmes réels, on peut retrouver des contraintes de type supérieure ou
égale et/ou de type égale, ainsi que des problèmes où on a à minimiser au lieu de maximiser.

Dans ce chapitre, on étudiera les modifications à apporter à la méthode du simplexe pour qu’elle
puisse résoudre tous ces types de programmes.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 29

II. Les variables artificielles

Considérons le programme linéaire suivant :
Max 5x1 + 6x2
S.c -x1 + x2  4
5x1 + 3x2 = 60
x2  5
x1  0 , x2  0
L'introduction des variables d'écart dans le programme linéaire donne
Max 5x1 + 6x2 + 0S1 + 0S2
S.c -x1 + x2 + S1 = 4
5x1 + 3x2 = 60
x2 - S2 = 5
x1  0 , x2  0, S1  0, S2  0
Afin de générer une solution réalisable de base initiale pour la méthode de simplexe, on a annulé
les variables de décision x1 et x2 . Ceci nous permet de commencer à partir de l’origine O. Or,
on vérifie bien que l’origine n’est pas une solution réalisable. La question qui se pose est
comment nous allons réécrire le programme de manière qu’on puisse construire le tableau de
simplexe initial à l’origine.

Pour arriver à cette fin, on doit ressortir une astuce mathématique qui se résume à l’introduction
de nouvelles variables, dites variables artificielles A1 et A2 .

Ces variables n’ont aucune interprétation, comme leur nom l’indique, ils sont conçus
artificiellement pour nous aider à utiliser la procédure de simplexe et à formuler le tableau initial
à partir de l'origine.

Si on ajoute ces deux variables artificielles A1 et A2 respectivement à la 2ème et 3ème contrainte,

le programme devient le suivant.

Max 5x1 + 6x2 +...

S.c -x1 + x2 + S1 = 4
5x1 + 3x2 + A1 = 60
x2 -S2 + A2 = 5
x1  0, x2  0, S1  0, S2  0 , A1  0, A2  0
Maintenant on peut obtenir une solution initiale de base du système d’équations, si on pose x1
= x2 = 0.

La solution initiale est

x1 = 0
x2 = 0
S1 = 4
S2 = 0
A1 = 60
A2 = 5
Cette solution n’est pas réalisable puisque x2 n’est pas supérieur à 5. Ainsi, il est important de
distinguer entre une solution réellement réalisable et une solution du programme linéaire réécrit
pour la procédure du simplexe. Certes, une solution réalisable du problème réel reste toujours

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 30

une solution réalisable pour le programme linéaire transformé, le contraire n’est pas toujours
vrai.

On peut conclure que tant que les variables artificielles restent dans la base, la solution demeure
non réalisable réellement pour notre programme.

Une manière pour garantir que ces variables artificielles sortent de la base avant d’atteindre la
solution optimale est de leur associer un grand coût -M dans la fonction objectif. Ainsi, si ces
variables restent dans la base ils vont causer une diminution importante de la valeur de la
fonction objectif. Ce qui nous contraignent à les faire sortir le plutôt possible de la base.

La fonction objectif s’écrit donc :

Max z = 5x1 + 6x2 - M A1 - M A2
avec M un très grand nombre (exemple: M 1010 ) .

En appliquant de ces modifications, le tableau de simplexe initial est

5 6 0 0 -M -M
x1 X2 S1 S2 A1 A2
0 S1 4 -1 1 1 0 0 0
-M A1 60 (5) 3 0 0 1 0
-M A2 5 0 1 0 -1 0 1

De la même manière que précédemment essayons de retrouver la variable entrante et la variable

sortante :

5 6 0 0 -M -M
x1 x2 S1 S2 A1 A2
0 S1 4 -1 1 1 0 0 0 -4
-M A1 60 (5) 3 0 0 1 0 12
-M A2 5 0 1 0 -1 0 1 
-5M -4M 0 M -M -M
5+5M 6+4M 0 -M 0 0

La variable entrante est x1 (5 +5M  6 + 4M avec M assez grand) et la variable sortante est A 1.
Le tableau de simplexe qui suit est :
5 6 0 0 -M -M
x1 x2 S1 S2 A1 A2
0 S1 16 0 8/5 1 0 1/5 0 10
5 x1 12 1 3/5 0 0 1/5 0 20
-M A2 5 0 (1) 0 -1 0 1 5
5 3-M 0 M 1 -M
0 3+M 0 -M -M-1 0

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :
ericnduwi@[Link], enduwimana@[Link]
 31

Le tableau de simplexe après la deuxième itération indique que la variable sortante est A2 .

Remarque: Simplification du tableau

Les deux premières itérations on fait sortir de la base les variables artificielles A1 et A2 . Leurs
effets nets sont maintenant négatifs et très élevés, elles ne pourront donc pas être sélectionnées
à l’itération suivante, ni même ultérieurement comme on peut facilement le constater. Donc on
peut supprimer du tableau la colonne relative à A1 et A2 .

En appliquant la règle ci-dessus, on obtient le tableau de simplexe suivant :

5 6 0 0
x1 x2 S1 S2
0 S1 8 0 0 1 8/5 5
5 x1 9 1 0 0 3/5 15
6 x2 5 0 1 0 -1 -5
5 6 0 -3
0 0 0 3

5 6 0 0
x1 x2 S1 S2
0 S2 5 0 0 5/8 1
5 x1 6 1 0 -3/8 0
6 x2 10 0 1 5/8 0
5 6 15/8 0
0 0 -15/8 0

Le tableau ci-dessus est optimal car tous les effets nets sont négatifs ou nuls. Donc la solution
optimale est :
x1 = 6
x2 = 10
S1 = 0
S2 = 5

Remarque: cas où le second membre est négatif

Le problème qui peut se poser est que l’une des variables du second membre soit négative. Par
exemple supposons que lors de la formulation on trouve une contrainte de ce type :
x1 - x2  -4
La condition qu’il faut vérifier avant de se lancer dans la réécriture de cette contrainte, en vue
de construire le programme standard, est la non-négativité du second membre.
Ainsi, on doit modifier la contrainte avant de commencer la standardisation et la réécrire comme
suit :
-x1 + x2  4
Exercice :
Réécrire convenablement ces contraintes:
(1) x1 + 3x2 - 5x3 = - 20
(2) -x1 + 3x2  - 5
(3) 5x1 - 2x2  - 10

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 32

III. Les problèmes de minimisation

Il y a deux manières de résoudre un problème de minimisation en utilisant la méthode de
simplexe.

La première méthode nécessite le changement de la règle de choix de la variable entrante. Dans

un problème de maximisation la règle est de choisir comme variable entrante celle qui a le plus
grand effet net positif non nul. Ceci parce que notre objectif est de choisir la variable qui en
entrant dans la base va engendrer un profit supplémentaire et ainsi accroître la valeur de la
fonction objectif. Pour un problème de minimisation, on va utiliser la règle inverse. C’est -à-
dire la variable entrante est celle à laquelle on associe la plus petite valeur négative non nulle
de l’effet net cj - zj.

Ceci va nous amener aussi à changer notre règle d’arrêt de la procédure de simplexe et de définir
le tableau optimal, comme celui où tous les effets nets
cj - zj sont positifs ou nuls.

Essayons d’appliquer la méthode de simplexe sur le problème de médecine :

Min x1 + x2
Sc 2x1 + x2  12
5x1 + 8x2  74
x1 + 6x2  24
x1  0 , x2  0

Pour permettre à la méthode de simplexe de démarrer de l’origine, il faut comme on l’a déjà
vu dans le cas de problème de maximisation, introduire les variables artificielles.
Avec les problèmes de maximisation on attribue à ces variables un coefficient
-M dans la fonction objectif pour les contraindre à quitter la base rapidement. Dans le cas de
problèmes de minimisation, on a intérêt à changer le coefficient de ces variables en M (M très
grand) afin d’arriver au même résultat et de les faire sortir de la base.

Avant de construire le tableau de simplexe initial, on réécrit le programme linéaire relatif au

problème de médecine avec les variables artificielles.

Min x1 + x2 + 0S1 +0S2 +0S3 +MA1 + MA2 + MA3

Sc 2x1 + x2 - S1 + A1 = 12
5x1 + 8x2 - S2 + A2 = 74
x1 + 6x2 - S3 + A3 = 24
x1 , x2 , S1 , S2 , S3, A1 , A2  0
Le tableau de simplexe initial est :

1 1 0 0 0 M M M
x1 x2 S1 S2 S3 A1 A2 A3
M A1 12 2 1 -1 0 0 1 0 0 12
M A2 74 5 8 0 -1 0 0 1 0 37/4
M A3 24 1 6 0 0 -1 0 0 1 4
8M 15M -M -M -M M M M
1-8M 1-15M M M M 0 0 0


Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 33

Après 4 itérations, on trouve le tableau de simplexe optimal suivant :

1 1 0 0 0
x1 x2 S1 S2 S3
1 X2 8 1 0 -8/11 1/11 0
0 S3 26 0 0 2 -1 1
1 X1 2 0 1 5/11 -2/11 0
1 1 -3/11 -1/11 0
0 0 3/11 1/11 0

On retrouve la même solution obtenue par la méthode graphique :

X1 = 2
X2 = 8
S1 = 0
S2 = 0
S3 = 26
Z = 10

Après avoir vérifié que le second membre des contraintes est positif, le tableau suivant résume
les transformations à faire subir à notre programme linéaire avant de le résoudre par la méthode
de simplexe :

Quand la contrainte est Pour la fonction objectif d’un problème de

Maximisation Minimisation
I- de type «  » Attribuer un coefficient nul pour la variable d’écart
Ajouter une variable
d’écart
II- de type « = » Attribuer un coefficient -M pour Attribuer un coefficient M pour
Ajouter une variable artificielle la variable artificielle
variable artificielle
III- de type «  » Attribuer un coefficient nul pour Attribuer un coefficient nul pour
Ajouter une variable la variable d’écart et un la variable d’écart et un
artificielle et une coefficient - M pour variable coefficient M pour variable
variable d’écart avec un artificielle artificielle
signe "-"

Le tableau suivant résume les étapes de la méthode de simplexe relatif aux problèmes de
maximisation et minimisation :

Etape Maximisation Minimisation

1 Formuler un programme linéaire pour le Formuler un programme linéaire pour le
problème réel. problème réel.
2 Vérifier que le second membre du Vérifier que le second membre du
programme linéaire est positif sinon programme linéaire est positif sinon
modifier les contraintes modifier les contraintes
3 Ecrire le programme linéaire sous une Ecrire le programme linéaire sous une
forme standard forme standard
4 Construire le premier tableau de simplexe Construire le premier tableau de simplexe

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 34

5 Choisir comme variable entrante dans la Choisir comme variable entrante dans la
base celle qui admet le plus grand effet net base celle qui admet le plus petit effet net
positif cj-zj. négatif cj-zj.
6 Choisir la variable sortante de la base celle Choisir la variable sortante de la base celle
qui admet le plus petit ratio supérieur à qui admet le plus petit ratio supérieur à
zéro. zéro.
7 Construire le nouveau tableau en utilisant Construire le nouveau tableau en utilisant
la règle de pivot la règle de pivot
8 Faire le test d’optimalité. Si Faire le test d’optimalité. Si
(cj-zj)  0 pour toutes les variables (hors (cj-zj)  0 pour toutes les variables (hors
base) donc la solution obtenue est base) donc la solution obtenue est
optimale. Sinon retourner à l’étape 5. optimale. Sinon retourner à l’étape 5.

La deuxième méthode pour résoudre un problème de minimisation se base sur le résultat suivant
« Résoudre un problème min ctx sujet à un ensemble de contraintes est équivalent à résoudre
un problème max -ctx sujet au même ensemble de contraintes ». Ces deux problèmes sont
équivalents dans la mesure où ils donnent le même vecteur des solutions optimales. La seule
différence est que la valeur de la solution max -ctx est l’opposé de la solution de min ctx; (i.e.
min ctx = - max -ctx).

Donc pour résoudre le programme linéaire relatif au problème de médecine, on peut résoudre
le problème de maximisation suivant:

Max - x1 - x2
S.c. 2x1 + x2  12
5x1 + 8x2 74
x1 + 6x2  24
x1 , x2  0
On peut vérifier facilement que la méthode de simplexe appliquée au programme ci-dessus,
engendre le même vecteur de solutions optimales.
IV. Les problèmes irréguliers
Après avoir examiné comment on peut résoudre un programme linéaire par la méthode de
simplexe, on s’intéresse dans cette section aux problèmes irréguliers qu’on peut rencontrer lors
de la résolution d’un programme linéaire par la méthode de simplexe. Donc, l’objet de cette
section est de reconnaître ces problèmes et de les résoudre par la méthode de simplexe.

a. Les problèmes impossibles

Graphiquement, on a caractérisé ces problèmes par un ensemble de solutions réalisables vide.
Avec la méthode de simplexe, on reconnaît que le problème est impossible si une ou plusieurs
variables artificielles sont présentes dans la base dans le tableau de simplexe optimal, ce qui
signifie que la solution donnée par ce tableau n’est pas réellement réalisable.

Exemple:
Vérifions à l’aide de la méthode de simplexe, que le problème suivant est réellement
impossible:
Max 4 x1 + 3x2
Sc x1 + x2  2
3x1 + x2  10
x1 , x2  0

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 35

En introduisant les variables d’écarts et les variables artificielles le programme s’écrit :

Max 4x1 + 3x2 - MA1
Sc x1 + x2 + S1 = 2
3x1 + x2 - S2 + A1 = 10
x1 , x2 , S1 , S2 , A1  0

4 3 0 0 -M
x1 x2 S1 S2 A1
0 S1 2 (1) 1 1 0 0 2
-M A1 10 3 1 0 -1 1 10/3
-3M -M 0 M -M
3M+4 M+3 0 -M 0


4 3 0 0 -M
x1 x2 S1 S2 a1
4 x1 2 1 1 1 0 0
-M a1 5 0 -2 -3 -1 1
4 4+2M 4+3M M -M
0 -1-2M -4-3M -M 0
Le tableau de simplexe ci-dessus est optimal avec une variable artificielle dans la base.

Remarque : Un programme de maximisation ou de minimisation avec seulement des

contraintes de type «  » ne peut pas être impossible (sous l’hypothèse que le second membre
b est positif). Ceci est dû au fait que lors de la résolution de ce genre de programme par la
méthode de simplexe on n'utilise pas des variables artificielles. Donc il est impossible de les
retrouver dans la solution optimale.

b. Les problèmes à solutions multiples

Graphiquement, ce problème est caractérisé par le fait que la pente de la droite représentant la
fonction objectif (z = 0) est égale à la pente de l’une des contraintes restrictives. Lorsqu’on
utilise la méthode de simplexe, on identifie ce problème lorsqu’un des effets nets (relatif à une
variable hors base) est nul. L’exemple de la section 3 du précédent chapitre représente un
problème avec solutions multiples.

c. Les problèmes à solution infinie

Graphiquement, ce problème est caractérisé par le fait qu’on peut déplacer la droite de la
fonction objectif indéfiniment de manière à accroître la valeur, en gardant toujours une
intersection non vide avec l’ensemble des solutions réalisables.

Avec la méthode de simplexe, on reconnaît ce problème lorsque la variable entrante n’admet

aucune limite sur sa valeur d’entrée, c’est à dire que tous les ratios Qi/aijo sont négatifs ou infini.
Exemple
Max x1 + 2x2
Sc x1 + x2  2
x2  3
x1 , x2  0
On introduit les variables d’écart et les variables artificielles, le programme linéaire devient :

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 36

Max x1 + 2x2 + 0S1 + 0S2 - Ma1

Sc x1 + x2 - S1 + a1 = 2
x2 + S2 = 3
x1 , x2 , S1 , S2 , a1  0
Les tableaux de simplexe sont :

1 2 0 0 -M
x1 x2 S1 S2 a1
-M a1 2 1 (1) -1 0 1 2
0 S2 3 0 1 0 1 0 3
-M -M M 0 -M
1+M 2+M -M 0 0


1 2 0 0
x1 x2 S1 S2
2 x2 2 1 (1) -1 0 -2
0 S2 1 -1 0 (1) 1 1
2 2 -2 0
-1 0 2 0


1 2 0 0
x1 x2 S1 S2
2 x2 3 0 1 0 1 
0 S1 1 -1 0 1 1 -1
0 2 0 2
1 0 0 -2

Le dernier tableau montre que la variable x1 n’admet aucune limite sur sa valeur d’entrée.

d. Les problèmes à solution dégénérée

Graphiquement, on appelle solution dégénérée le point où plusieurs contraintes concourent (un
nombre supérieur ou égal à trois contraintes). Un programme linéaire est dit dégénéré si une ou
plusieurs variables dans la base optimale sont nulles. Dans la résolution graphique ce problème
n’est pas difficile à résoudre, mais avec la méthode de simplexe il peut causer des difficultés.

Exemple
Max z = 2x1 + 0 x2 + 3/2 x3
s.c. x1 - x2  2
2x1 + x3  4
x1 + x2 + x3  3
x1 , x2 , x3  0

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 37

La solution optimale de ce problème est :

x1 = 1
x2 = 0
x3 = 2
z =5

La forme standard du programme linéaire est

Max 2x1 + 0 x2 + 3/2x3 + 0 S1 + 0 S2 + 0 S3
Sc x1 - x2 + S1 = 2
2x1 + x3 + S2 = 4
x1 + x2 + x3 + S3 = 3
x1, x2 , x3 , S1 , S2, S3  0

Le tableau de simplexe initial est :

2 0 3/2 0 0 0
x1 x2 x3 S1 S2 S3
0 S1 2 1 -1 0 1 0 0 2
0 S2 4 2 0 1 0 1 0 2 
0 S3 3 1 1 1 0 0 1 3
0 0 0 0 0 0
2 0 3/2 0 0 0

La variable entrante est x1 , mais les deux premières contraintes donnent la même valeur
minimale du ratio. Ceci indique que lorsque x1 passe à 2, les variables d’écart S1 et S2 vont
s’annuler malgré que l’un des deux demeure encore dans la base.
Choisissons arbitrairement de faire sortir de la base la variable d’écart S1 .

2 0 3/2 0 0 0
x1 x2 x3 S1 S2 S3
2 x1 2 1 -1 0 1 0 0 -2
0 S2 0 0 2 1 -2 1 0 0
0 S3 1 0 2 1 -1 0 1 1/2
2 -2 0 2 0 0
0 2 3/2 -2 0 0

La nouvelle solution réalisable de base est :
x1 = 2
x2 = 0
x3 = 0
S1 = 0
S2 = 0
S3 = 1
et la valeur de la fonction objectif z = 4. Cette solution de base est dite dégénérée. Continuons
les itérations relatives à la méthode de simplexe. La variable entrante est x2 .
Le problème est qu’un des ratios est nul ce qui indique qu’on ne peut pas augmenter la valeur
de x2 puisque la valeur de la fonction objectif ne va pas augmenter et reste égale à 4.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 38

Si on réitère une autre fois, en remplaçant S2 par x2 dans la base on obtient :

2 0 3/2 0 0 0
x1 x2 x3 S1 S2 S3
2 x1 2 1 0 1/2 0 1/2 0 4
0 x2 0 0 1 1/2 -1 1/2 0 0
0 S3 1 0 0 0 1 -1 1 
2 0 0 0 1 0
0 0 1/2 0 -1 0

Ce tableau n’est pas optimal, la variable entrante est x3 et la variable sortante est x2 . On remarque
aussi que ce passage d’une solution à une autre ne s’accompagne pas d’une augmentation de la
valeur de la fonction objectif.

On peut facilement vérifier que nous sommes en train de cycler sans atteindre la solution
optimale. Ce genre de cyclage dans la méthode de simplexe est dangereux et on doit l’identifier
avant de commencer à résoudre le problème, sinon on passera un temps énorme sans atteindre
la solution optimale.
Pour terminer cette section, il faut noter que ce n'est pas tout problème de dégénérescence qui
peut conduire à un cyclage.

Exemple
Max 10 x1 + 9x2
Sc 7/10x1 + x2  630
1/2 x1 +5/6x2  480
x1 + 2/3x2  708
1/10 x1 +1/4x2  135
x1 ,, x2  0
Essayer de résoudre ce programme par la méthode de simplexe (choisir en cas de deux
quotients égaux, celui qui se trouve dans la ligne supérieure).

CHAP.5 : DUALITE ET ANALYSE DE SENSIBILITE

I. Introduction
Dans ce chapitre, on va étudier des notions relatives aux programmes linéaires tels que le
programme dual, les coûts marginaux ainsi que des techniques de validation de la solution d’un
programme linéaire, c’est à dire l’analyse de sensibilité.

Nous allons commencer ce chapitre par donner quelques termes clés du jargon utilisé pour
interpréter économiquement les différents résultats du programme linéaire.
II. Interprétation économique
Les éléments clés d’un programme linéaire standard sont :
- La fonction objectif dite fonction économique. Cette fonction peut représenter un coût, un
profit, etc...
- Les contraintes sont composées, des coefficients aij de la matrice A, dite matrice
technologique, et des constantes bi, qui forment le vecteur du second membre. Le second
membre peut représenter la disponibilité des ressources, les niveaux de demande, etc...

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 39

- Les variables d’écart peuvent représenter, par exemple dans le problème de l’agriculteur,
l’excédent de chacune des ressources : terrain, eau, heures de travail, bureau d’irrigation. Elles
sont aussi dites variables de surplus.

Quand une variable d’écart est nulle, on dit que la contrainte correspondante est saturée. Dans
le problème de l’agriculteur les contraintes terrain et main d’œuvre sont saturées. Elles sont
dites aussi restrictives car une variation du second membre (par exemple) engendre un
changement dans la valeur de la solution optimale.

Toute contrainte non saturée à l’optimum n’est pas restrictive pour le problème, c’est à dire
qu’elle n’a aucune influence sur la solution considérée.

Définition: Coût marginal

Par définition, on appelle coût marginal d’un bien l’augmentation minimale de dépenses, par
rapport à la solution optimale, qui résulterait de l’utilisation d’une unité supplémentaire de ce
bien, lorsque le problème posé consiste à produire des biens au moindre coût.
Si le problème posé consiste à transformer des biens pour vendre une production avec un
meilleur profit et l’augmentation maximale de revenu qui résulte de la possibilité de disposer
d’une unité supplémentaire de l’un des biens, est la valeur marginale de ce bien. Très souvent,
on emploie également dans ce cas le qualificatif coût marginal.

Remarque : Les coûts marginaux sont donc les effets nets associés aux variables d’écart,
puisque ce sont ces variables qui déterminent les excédents (ou les insuffisances) de biens.
Si une variable d’écart n’est pas nulle, dans la solution optimale, c’est que le bien correspondant
est déjà excédentaire. Par conséquent, le fait de disposer d’une unité supplémentaire de ce bien
n’aura aucune influence sur le revenu. On dit alors que ce bien à une valeur marginale nulle, ou
par extension, que la variable d’écart associée à ce bien a une valeur marginale nulle.

Par contre, si une variable d’écart est nulle dans la solution optimale, c’est que le bien
correspondant est totalement utilisé. Par la suite une variation de la disponibilité aura
généralement une influence sur le revenu. C’est pourquoi cette variable d’écart nulle dans la
solution optimale a une valeur marginale non nulle, et cette valeur marginale précise la variation
de la fonction économique résultant de l’utilisation d’une unité supplémentaire du bien associé.
Exemple : Dans le problème de l’agriculteur on a
• Le coût marginal lié à S1 est 200 3
 Une augmentation de S1 d’une unité entraîne une diminution de 200 3 de la valeur de la
fonction économique.
• Le coût marginal lié à S 2 est 0 et à l'optimum S 2 = 60
 On a déjà 60m 3 d’eau de plus donc si on ajoute 1m 3 ça ne va pas changer la solution
optimale ni la valeur de la fonction économique
Le système de contraintes dans le programme linéaire relatif au tableau de simplexe optimal du
problème de l’agriculteur est
 x1 + 4 3 S1 − 1 3 S 3 = 40
S − 14 3 S + 2 3 S = 60
 2 1 3

 2x − 1 3 S 1 + 1 3 S 3 = 110
 S 4 − 4 3 S1 + 1 3 S 3 = 50

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 40

La fonction économique s’écrit

z = 100x1 + 200x2
Si on exprime z en fonction de S1 et S 3 (variables hors base) en utilisant le système d’équation
ci-dessus on a
z = 100(− 4 3 S1 + 1 3 S 3 + 40) + 200(1 3 S1 − 1 3 S 3 + 110)
z = 26000 − 200 3 S1 − 100 3 S 3

La valeur 26000 correspond à la valeur optimale de la fonction économique.

Si S1 = 1 alors un hectare de terrain de moins à utiliser, donc une réduction de 200 3 dinars de
la valeur de la fonction objectif.

Si on ajoute 3 hectares de terrains (S1 = −3) , avec l’hypothèse que les autres quantités restent
inchangées alors le revenu augmente de (200 3)  3 = 200dinars
On vérifie ceci, si on résout le programme linéaire
Max 100x1 + 200x2
S.C x1 + x2  153
4 x1 + 2 x2  440
x1 + 4 x2  480
x1  90
x1  0 , x2  0
On trouve que la valeur optimale va augmenter de 200 dinars est devient 26 200 dinars.

Exercice : Expliquer graphiquement que si on ajoute des m 3 d’eau, on aura aucune

amplification dans la fonction objectif.

Remarque : Dans le cas où on diminuerait 60m 3 d’eau, la solution optimale devient dégénérée.

Les valeurs marginales apportent donc des renseignements économiques particulièrement

intéressantes, mais il faut les utiliser avec prudence car leur domaine de validité est limité.
Par exemple, si on ajoute 30 hectares de terrains aux 150 déjà disponibles dans le problème de
l’agriculteur, le revenu augmentera de(200⁄3) × 30 = 2000𝑑𝑖𝑛𝑎𝑟𝑠. Ceci n’est pas vrai, parce
que si on résout le programme linéaire suivant :
Max 100x1 + 200x2
S.C x1 + x2  180
4 x1 + 2 x2  440
x1 + 4 x2  480
x1  90
x1  0 , x2  0
La valeur optimale du programme linéaire ci-dessus est de 26 875,14 donc le revenu n’a pas
augmenté de 2000 dinars comme prévu.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 41

II. Dualité
a. Définition
La forme d’un programme linéaire de type maximisation est
Max z = ct x
S.C Ax  b (PL1)
x0
avec x, b , c des vecteurs de dimensions respectives n, m et n , et A une matrice de dimension
(m, n)
On appelle programme dual de (PL1) , le programme linéaire suivant :
Min w = bt y
S.C t
A.Y  c
y0
avec y un vecteur de dimension m et t A la transposée de la matrice A .
Le programme (PL1) est appelé programme Primal.
Pour passer du primal au dual, on remarque que :
a ) Les termes du second membre deviennent les coefficients de la fonction objectif et
réciproquement.
b ) Le problème de maximisation devient un problème de minimisation.
c ) Les inégalités "  " deviennent des inégalités "  "
d ) La matrice A se transforme en sa transposée.

Exemple : Le programme primal (problème de l’agriculteur) est

Max z = 100x1 + 200x2
S.C x1 + x2  150
4 x1 + 2 x2  440
x1 + 4 x2  480
x1  90
x1  0 , x2  0

Donc le programme dual est

Min w = 150 y1 + 440 y 2 + 480 y3 + 90 y 4
S.C y1 + 4 y 2 + y3 + y 4  100
y1 + 2 y 2 + 4 y3  200
y1  0 , y 2  0 , y 3  0 , y 4  0

b. Propriétés et signification économique du programme dual

Pour expliquer la signification du problème dual on va se baser sur l’exemple de l’agriculteur.
Supposons qu’un agriculteur (client) voudrait acheter la totalité de nos ressources disponibles.
Notre agriculteur acceptera certainement cette proposition si le prix offert par ce client lui
procure le même profit.

soit y1 le prix d'un hectare de terrain

y 2 le prix d’un m 3 d’eau

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 42

y 3 le prix d’une heure de main d’œuvre

y 4 le prix de la permission de la culture d’un hectare de tomates.

Le problème du client consiste à minimiser les frais d’achat des ressources : c’est à dire
150 y1 + 440 y 2 + 480 y3 + 90 y 4 sous la contrainte que les prix satisfont notre agriculteur.
Pour notre agriculteur un hectare de terrain 4m 3 d’eau, une heure de travail et un hectare de
permission du bureau est équivalent a un revenu de 100 dinars.
Tandis que, un hectare de terrain, 2m 3 d’eau et 4 heures de travail lui engendrent un revenu de
200 dinars.

Il n’est prêt à vendre ses ressources que si y1 + 4 y 2 + y3 + y 4 lui rapporte un revenu supérieur
ou égale à 100 DT et que si y1 + 2 y 2 + 4 y3 lui rapporte un revenu supérieur ou égal à 200 DT.
Ainsi le problème du client est

Min 150 y1 + 440 y 2 + 480 y3 + 90 y 4

S.C y1 + 4 y 2 + y3 + y 4  100
y1 + 2 y 2 + 4 y3  200
y1  0 , y 2  0 , y 3  0 , y 4  0
Donc le problème du client peut être modélisé par le programme dual.

Le tableau de simplexe final du programme dual est :

150 440 480 90 0 0

y1 y2 y3 y4 L1 L2
480 y3 100/3 0 -2/3 1 -1/3 1/3 -1/3
150 y1 200/3 1 14/3 0 4/3 -4/3 1/3
150 380 480 40 -40 -110
0 60 0 50 40 110

Avec L1 et L2 , les variables d’écart à la 1ère et la 2ème contrainte du programme dual.

On remarque que la solution optimale du dual peut être déduite du primal de la manière suivante
:
y1 = 200/3  C3 - z3 = - 200/3
y2 = 0  C4 - z4 = 0
y3 = 100/3  C5 - z5 = - 100/3
y4 = 0  C6 - z6 = 0
L1 = 0  C1 - z1 = 0
L2 = 0  C2 - z2 = 0
C1 - z1 = 0  S1 = 0
C2 - z2 = 60  S2 = 60
C3 - z3 = 0  S3 = 0
C4 - z4 = 50  S4 = 50
C5 - z5 = 40  x1 = 40
C6 - z6 = 110  x2 = 110
w = 26000  z = 260000

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 43

On peut généraliser ce résultat dans le tableau suivant :

Primal (Max) Dual (Min)

Variables de décision variables d’écart
xj = 0  Cj - zj < 0 Li = | Cj - zj |  0  Cj - zj = 0
xj > 0  Cj - zj = 0 Li = 0  Cj - zj = xj
variables d’écart Variables de décision
Sj = 0  Cj - zj  0 yi = | Cj - zj |  0  Cj - zj = 0
Sj > 0  Cj - zj = 0 yi = 0 et Cj – zj = Sj

On remarque aussi qu’à l’optimum la valeur de la fonction objectif du dual est égale à la
valeur de la fonction objectif du primal.

Proposition : Le dual du programme dual est le programme primal.

c. Tableau de correspondance primal-dual

Max Min
- Matrice des contraintes (m, n) - Transposée de la matrice des contraintes (n,
m)
- Second membre des contraintes - Coefficient de la fonction objectif
- Coefficient de la fonction objectif - Second membre des contraintes
Nombre de contraintes Nombre de variables
i ème contrainte de type «  » i ème variable de type «  0 »
i ème contrainte de type «  » i ème variable de type «  0 »
i ème contrainte de type « = » i ème variable qcq « IR »

Nombre de variables Nombre de contraintes

j ème variable «  0 » j ème contrainte de type «  »
j ème variable «  0 » j ème contrainte de type «  »
j ème variable qcq « IR » j ème contrainte de type « = »

Exemples

Primal Dual
Max ½ x1 + x2 Min 3y1 + y2 + 2y3
S.c x1 + x2  3 S.c y1 - y2 + y3  ½
- x1 + x2  1 y1 + y2  1
x1  2 y1  0, y2  0, y3  0
x1  0, x2  0
Min - x1 + x2 Max 2y1 - 2y2 + 5y3
S.c 2x1 - x2  2 S.c 2y1 - y2 + y3  -1
- x1 + 2x2  -2 - y1 + 2y2 + y3  1
x1 + x2  5 y1  0, y2  0, y3  0
x1  0, x2  0
Max 2x1 - x2 Min 3 y1 + 4 y2
S.c x1 - x2 = 3 S.c y1 + y2  2

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 44

x1  4 - y1  -1
x1  0, x2  0 y1 IR, y2  0
Max 2x1 - x2 Min - 2y1 + 6y2 - 5y3
S.c x1 - 2x2  2 S.c y1 + y2 = 2
x1 + x2 = 6 - 2y1 + y2 + y3 = -1
x2  5 y1  0, y2 IR, y3  0
x1 IR, x2 IR

III. Analyse de sensibilité

Définition: Une solution de base optimale est dite stable si l’ensemble des variables de base à
l’optimum ne changent pas, même si les valeurs de ces variables de base sont modifiées.

Dans cette section on examinera la stabilité de la solution optimale d’un programme linéaire
suite à la variation de l’un des paramètres de ce programme.

On utilisera pour présenter l’analyse de sensibilité sur ces différents paramètres du

programme linéaire l’exemple de l’agriculteur.
Max 100x1 + 200x2
S.c x1 + x2  150
4x1 + 2x2  440
x1 + 4x2  480
x1  90
x1  0 , x2  0
a. Analyse de sensibilité sur les Cj
On cherche à déterminer un intervalle dans lequel peut varier Cj sans que la solution optimale
ne change.

Considérons une variation du coefficient Cj de 100 à 100 + 

En remplaçant dans le tableau optimal 100 par 100 +  , on obtient le tableau suivant :

100+ 200 0 0 0 0
x1 x2 S1 S2 S3 S4
100+ x1 40 1 0 4/3 0 -1/3 0
0 S2 60 0 0 -14/3 1 2/3 0
200 x2 110 0 1 -1/3 0 1/3 0
0 S4 50 0 0 -4/3 0 1/3 1
100+ 200 (200+4)/3 0 (100-)/3 0
0 0 -(200+4)/3 0 -100/3 0

La solution donnée par le tableau reste optimale si

 (200 + 4)
− 0
 3   −50
    − 50    100
  − 100  0   100

 3

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 45

Donc la solution optimale est stable et prend la même valeur (x1 ,x2 )=(40,110) tant que 50 
C1  200

Exercice : Supposons que le coefficient Cj d'une variable hors base dans la solution optimale,
est modifié. Dans quel intervalle, Cj peut-il varier sans que la base optimale soit modifiée ?
(Aide : différencier le cas d’un programme de maximisation et le cas d’un programme de
minimisation).
Solution :
-  < Cj  zj cas d’un programme de maximisation
zj  Cj < + cas d’un programme de minimisation

b. Analyse de sensibilité sur les b j

Déterminer l’intervalle pour lequel, la solution optimale reste stable, pour une variation du
second membre de la ième contrainte bi .
Considérons une variation de b1 de 150 à 150 + .
Sachant que dans le premier tableau de simplexe b1 n’est présent que dans la première
contrainte. On obtient ainsi une correspondance entre la colonne des quantités Qi et la colonne
de S1 .

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 150+1  1 1 1 0 0 0
0 S2 440+0  4 2 0 1 0 0
0 S2 480+0  1 4 0 0 1 0
0 S4 90+0  1 0 0 0 0 1
0+1  0 0 0 0 0 0
100 100 0 0 0 0

Dans le tableau optimal, la colonne correspondant à S1 nous donne les coefficients de  dans la
colonne des quantités.

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
100 x1 40+4/3 1 0 4/3 0 -1/3 0
0 S2 60-14/3 0 0 -14/3 1 2/3 0
200 x2 110-1/3 0 1 -1/3 0 1/3 0
0 S4 50-4/3 0 0 -4/3 0 1/3 1
26000+200/3 100 200 200/3 0 100/3 0
0 0 -200/3 0 -100/3 0
La base reste optimale tant que :
40 + 4 / 3  0   −30
60 − 14 / 3  0   90 / 7
 
   - 30    90/7
110 − 1 / 3  0   330

50 − 4 / 3  0 
  75 / 2

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 46

Donc tant que 120  b1  162,85 la base demeure la même et la solution optimale est stable
mais elle change en valeur (exemple : pour = 3 le vecteur de solutions optimale est
(x1 ,x2 ,S1 ,S2 ,S3 ,S4 )=(44,109,0,46,0,46))

Remarque : D’après le résultat ci-dessus on peut conclure que le coût marginal de 200/3 par
hectare de la première ressource n’est valide que si la solution de base demeure stable. Donc si
et seulement si 120  b1  162,85. Ceci est appelé le domaine de validité du coût marginal.

c. Analyse de sensibilité sur les coefficients a ij

Supposons que dans le problème de l’agriculteur, le nombre d’unités de la ième ressources
nécessaire pour produire une unité de produit j, soit (aij + ) au lieu de aij. Ainsi, on se pose la
question si la solution optimale demeure stable suite à un tel changement.

i) xj est une variable de base et la ième ressource est totalement utilisée.

Par exemple : x1 + (4+)x2  480  x1 + (4 +  )x2 + S3 = 480
A l’optimum, la base est inchangée donc
x1* + (4 +  ) x2* + S*3 = 480
S*3 = 0, x1*  0, x2*  0
• Si   0 , alors l’équation ne peut pas être satisfaite sinon S*3  0 puisque
x1* + 4 x 2* = 480 et  x2* + S*3 = 0 , x2*  0 .
• Si   0 , alors on a un excèdent de la 3ème ressource (S3  0), ce qui nous contraint à changer
la base (la solution optimale n’est plus stable).

Conclusion : Dans le cas où xj est une variable de base optimale et la ième ressource est
totalement utilisée, il est impossible de modifier le coefficient aij sans que la base dans la
solution optimale ne change pas (la solution optimale n'est pas stable).

ii) xj est une variable de base et la ième ressource n’est pas totalement utilisée.
Par exemple : (4 +) x1 + 2x2  440
 (4 +  )x1 +2x2 + S2 = 440
A l’optimum, la solution est inchangée donc
(4 +  ) x1* + 2 x2* + S *2 = 440
S*2 = 60, x1*  0, x2*  0
Pour que la base demeure toujours optimale il faut et il suffit que
 x1 + S 2 = 60
 * *
60
 *  60 −  x1*  0    *    3 / 2

S 2  0 x1

Conclusion: Dans le cas où xj serait une variable de base optimale et où la ième ressource n’est
pas totalement utilisée, il est possible de modifier le coefficient aij d’une valeur ij égale à
𝑆
− ∞ < 𝛿𝑖𝑗 ≤ 𝑥𝑖∗ et la solution optimale demeure stable.
𝑗
IV. Introduction d’une nouvelle activité
On sait déjà que la valeur optimale de la variable duale représente les coûts marginaux
(d’opportunité) associés à l’utilisation de ressources limitées.
On peut également utiliser ces coûts marginaux pour évaluer des décision concernant
l’introduction de nouveaux produits ou de nouveaux procédés de fabrication.

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 47

a. Introduction d’une nouvelle variable de décision

L’agriculteur prévoit de produire des pommes de terre. Un hectare de pomme de terre demande
3 m 3 d’eau et 2 heures de travail pour un revenu de C3 dinars.

La question est pour quelle valeur de C3 , l’agriculteur a-t-il intérêt à introduire cette nouvelle
production ?

Sans résoudre le nouveau programme linéaire suivant:

Max 100x1 + 200x2 + C3 x3
S.c x1 + x2 + x3  150
4x1 + 2x2 +3x3  440
x1 + 4x2 + 2x3  480
x1  90
x1 , x2 , x3  0

On peut déterminer si l’agriculteur a un intérêt à introduire la production ou pas. En d’autres

termes, s’il n’a pas intérêt à le faire, la solution optimale du programme linéaire ci-dessus donne
x3 = 0. Ce qui revient à dire, que pour l’agriculteur l’utilisation d’un hectare de terrain, de 3
mètres cube d’eau et de deux heures de travail lui procurent plus de gain s’il va les mettre au
service de la production de tomates et/ou de piments plutôt que dans la production de pommes
de terre. Ceci est équivalent au fait que la contrainte suivante: y1 + 3 y 2 + 2 y3  C3 n’est pas
* * *

satisfaite (avec y1* , y 2* et y3* sont les prix minimaux des ressources pour notre agriculteur).

Cette contrainte correspond à la 3ème contrainte du programme dual du programme linéaire ci-
dessus :
200 * 100
On a : y1* = ,y 2 = 0 et y*3 = , donc :
3 3
• Si C3 < 400/3, l’agriculteur n’a pas intérêt à introduire la nouvelle activité
• Si C3 > 400/3, l’agriculteur a intérêt à introduire cette nouvelle activité, la solution optimale
va changer et la valeur de la fonction objectif augmentera
• Si C3 = 400/3, l’agriculteur est indifférent envers l’introduction de cette nouvelle activité.
b. Introduction d’une nouvelle contrainte
Si la solution optimale satisfait la nouvelle contrainte, le problème admettra la même solution.
Sinon l’introduction de cette contrainte va engendrer une nouvelle solution optimale.

CHAP.6 : INTRODUCTION A LA PROGRAMMATION DYNAMIQUE

I. Introduction
La programmation dynamique est une technique mathématique qui a pour objet d’aider à
prendre des décisions séquentielles indépendantes les unes des autres.
Contrairement à la programmation linéaire, il n’y a pas un formalisme mathématique standard.
C’est une approche de résolution où les équations doivent être spécifiées selon le problème à
résoudre.

II. Exemple prototype. Le problème du voyageur

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 48

7 5
2 1
4 4
2 6 8 3
3 6
4 6 10
1 3 2
4 3

3 3 9 4
4 1
3
4 7
5

Un postier décide d’effectuer un voyage entre différentes villes qu’il ne connaît pas. Son but
est de choisir le chemin le moins dangereux. Pour choisir son chemin, il s’informe auprès des
assurances sur les différentes valeurs des polices d’assurance de vie entre les différentes routes
possibles du voyage.
Le trajet du postier est composé de 4 étapes (voir figure) et il doit arriver à la ville numérotée
10 en partant de la ville numérotée 1. Les autres numéros représentent les villes susceptibles
d’être traversées. Les arcs entre ces nœuds représentent les d ifférents trajets possibles et les
valeurs cij au-dessus des arcs représentent le prix de la police d’assurance vie relatif au trajet
décrit par l’arc.
Le chemin le moins dangereux est celui qui admet la plus petite valeur de la police d’assurance
vie

Exemple : Si le voyageur empreinte le trajet 1→ 2→ 6→ 9→ 10 , le coût total de la police

d’assurance est 13

Soit xn (n=1, ..., 4) les variables de décisions relatives à chacune des 4 étapes. Le chemin à
suivre par le voyageur est 1→ x1 → x2 → x3 → x4 avec x4 = 10.
Soit fn (S, xn ) le coût total de la police d’assurance vie pour le reste des étapes sachant que nous
somme à l’état S de l’étape n et que la destination choisie est xn .

*
Etant donné S et n, soit x n la valeur de xn qui minimise fn (S, xn ) et soit f n* (S) la valeur minimale
de fn (S, xn ). ( f n* (S)= fn (S, xn* )).
L’approche de la programmation dynamique repose sur l’idée qu’un chemin ne peut être
optimal que si chacune de ses composantes est elle même optimale. La démarche de la
programmation dynamique consiste à étudier d’abord les sous problèmes qui se situent
chronologiquement les derniers et sur un principe de retour en arrière.

L’objectif est donc de trouver la valeur de f1* (1). Pour l’avoir, la programmation dynamique
va essayer d’évaluer avec une procédure de chaînage en arrière f 4* (s), f3* (s), f 2* (s) et enfin f1*
(1).

A chaque étape, on va essayer d’évaluer pour chaque état s, la valeur de f (S, xn ) pour chaque
destination xn possible, puis de retrouver la meilleure destination x n* (celle qui correspond au
plus petit coût f(S, xn )) et aussi la valeur de f n* (s).

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 49

Etape 4

x4 f4 (S, x4 )) f 4* (s), x 4*
S
8 3 3 10
9 4 4 10
Etape 3
f3 (S, x3 )=Csx3 + f 4* (x3 )
x3 8 9 f3* (s), x3*
S
5 4(=1+3) 8(=4+4) 4 8
6 9 7 7 9
7 6 7 6 8
Etape 2
f2 (S, x2 )=Csx2 + f3* (x2 )

x2 5 6 7 f 2* (s) x1*
S
2 11 11 12 11 5 ou 6
3 7 9 10 7 5
4 8 8 11 8 5 ou 6
Etape 1
f1 (S, x1 )=Csx1 + f 2* ( x1 )
x1 2 3 4 f1* (1) x1*
S
1 13 11 11 11 3 ou 4

La valeur de f1* (1) = 11 représente le coût total minimal de la police d’assurance vie. Le chemin
*
optimal n’est pas unique puisque dès le départ on peut choisir x 1 = 3 ou 4, donc l’ensemble de
ces chemins est:
1 →3 → 5 → 8 → 10
1 →4 → 5 → 8 → 10
1 →4 → 6 → 9 → 10
III. Caractéristiques d’un problème de programmation dynamique
Nous allons maintenant sur la base de l’exemple précédant analyser les propriétés communes
aux problèmes de programmation dynamique.

(i) Le problème peut être décomposé en étapes et une décision doit être prise à chaque étape.
Le dernier exemple est devisé en 4 étapes où à chaque étape, la décision à prendre est celle de
la destination à choisir. Ces décisions sont interdépendantes et séquentielles.
(ii) A chaque étape correspond un certain nombre d’états. Dans l’exemple du voyageur, les états
à chaque étapes sont représentés par les villes que le voyageur visité. Le nombre de ces états
dans l’exemple est fini. Dans ce qui suit en étudiera des problèmes où le nombre d’états est
infinie (xn  IN) ou continue (xn  IR)

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]
 50

(iii) A chaque étape, la décision prise transforme l’état actuel en un état associé à l’étape
suivante (dans certains cas avec une distribution de probabilité).

Dans notre exemple, se trouvant à une ville donnée, le voyageur décide de se rendre à une autre
ville qui est un état de l’étape suivante.

(iv) Etant donné un état, une stratégie optimale pour les étapes restantes est indépendante des
décisions prises aux étapes précédentes.

Si le voyageur est dans un état quelconque de l’étape i, le chemin optimal entre cet état et l’état
10 sera indépendant de la façon dont il y est arrivé. En d’autres termes, l’état actuel contient
toute l’information nécessaire aux décisions futures. Cette propriété est dite principe
d’optimalité.

(v) L’algorithme de recherche de la solution optimale commence par trouver la stratégie

optimale pour tous les états de la dernière étape.

(vi) Une relation de récurrence identifie la stratégie optimale dans chaque état de l’étape n à
partir de la stratégie optimale dans chaque état de l’étape n+1.

Dans notre exemple la relation est f n* (S)= Min {Csxn + f n*+1 (xn )}
xn
La stratégie optimale étant donné que nous sommes à l’état S de l’étape n, nécessite de retrouver
la valeur de xn qui minimise l’expression ci-dessus.

La relation de récurrence à toujours cette forme f n* (S)= Max ou Min {fn (S,xn )},
xn xn
avec fn (S,xn ) est une expression en fonction de S, xn et f n*+1 (-)

(vii) Utilisant cette relation de récurrence, l’algorithme procède à reculons étape par étape. Il
détermine la stratégie optimale pour chaque état de chaque étape.

Dans tout problème de programmation dynamique, on peut construire à chaque étape un tableau
analogue au suivant.

Etape n
fn (S, x1 )

X1 états n+1 f n* (s) xn*

S
états n le coût ou la La longueur du Le meilleur état
distance chemin optimal à de l’étape n+1 le
partir de S jusqu’à long du chemin
l’état final optimal final

Cours de Recherche opérationnelle. Prof : Dr Eric NDUWIMANA, Tél.71173134, Courriels :

ericnduwi@[Link], enduwimana@[Link]