CHAPITRE 1

La Programmation Linéaire

Introduction

L’objectif principal de ce cours est d’acquérir une connaissance approfondie de

certaines techniques considérées à l’heure actuelle comme des méthodes de base et
permettre à l'étudiant de se familiariser avec les principales techniques décisionnelles
et d'optimisation de la recherche opérationnelle. Cette dernière représente l'ensemble
des méthodes mathématiques et algorithmiques qui permettent de résoudre un
problème donné de la meilleure façon possible
La programmation linéaire est lié à des problèmes d’allocations de ressources
limitées, de la meilleure façon afin de maximiser un profit ou de minimiser un coût.
Elle consiste à chercher l’optimum d’une fonction économique linéaire de

plusieurs variables sous certaines contraintes exprimées par des équations

(ou inéquations) qui sont linéaires.

I) La modélisation en recherche opérationnelle et son application

La RO s’intéresse à la compréhension et à la résolution des problèmes de décision se

posant dans les organisations et vise à l’amélioration de leur fonctionnement. Ceci en
se basant sur des méthodes scientifiques (Mathématiques et informatiques) pour
résoudre des problèmes d'optimisation.

L’application de la RO touche plusieurs domaines tels que la gestion de production et

la gestion de ressources humaines. Elle permet de prendre des décisions optimales
concernant nombreux problèmes, afin de maximiser un profit ou de minimiser un
coût tout en utilisant la meilleure combinaison des ressources disponibles. Dans le
domaine de la production l'application de la RO revient à maximiser le profit selon la
disponibilité des ressources suivantes : main d'œuvre, capacité de production,
demande du marché, prix de revient du matériau brut.

1
II) Formulation mathématiques d’un programme linéaire (PL)

1. Les conditions de formulation d’un PL

Afin de formuler un PL certaines hypothèses doivent être vérifiées1. En effet,

 Les variables de décision du problème sont positives
 Une fonction linéaire des variables de décision est définie afin de prendre
décision. Cette fonction est dite fonction objectif ou fonction économique.
 Les contraintes (ou les restrictions) relatives aux variables de décision sont
exprimées par un ensemble d’équations linéaires.
 Les paramètres du problème ont une valeur connue (en dehors des variables de
décisions)

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

La formulation d'un PL nécessite de suivre les étapes suivantes :

 IL faut Identifier les variables de décision du problème notées généralement par xi

(i= 1,...,n) avec x1  0, x2  0, , x N  0 .

 Identifier les contraintes du problème et les présenter sous forme d' un système
d’équations linéaires. ( a11x1  a12 x2    a1N xN b)

 Écrire la fonction "objectif" et spécifier si le critère de sélection est à maximiser

ou à minimiser. Cette fonction "objectif" est linéaire de type:
z  c1 x1  c2 x2    cN xN
Ainsi après avoir présenté les différentes étapes, on peut écrire le PL lié au problème
en question:
Pour un problème de maximisation le système se présente 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

1
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

2
Pour un problème de minimisation le système se présente comme suit

Min c1 x1  c2 x2    cN x N
s .c a11x1  a12 x2    a1N xN  b1
a21x1  a22 x2    a2 N xN  b2

aM 1 x1  aM 2 x2    aMN xN  bN
x1  0 , x2  0 , , xN  0

3. Formulation
Plusieurs problèmes dans divers domaines peuvent être représentés par des modèles
de PL. L’utilisation de ces techniques de modélisation s’est approfondie par la
construction des algorithmes et des logiciels capables de résoudre des problèmes avec
autant de variables de décision que de contraintes.

La formulation d'un PL demande, en général, une certaine connaissance du problème

pour pouvoir relever facilement les différentes composantes du problème et donner un
programme qui modélise la situation réelle. Dans la suite, on présente des exemples
de formulation en programme linéaire qui sont liés à différents problèmes de
décision.

Exemple 1: usine de fabrication des jouets

Une usine fabrique deux types de jouets en bois : des soldats et des trains. Les
données de ce problème sont représentées dans le tableau suivant :

Menuiserie Finition
1 soldat 1h de travail 2h de travail
1 train 1h de travail 1h de travail

L'usine dispose par semaine de toutes les matières premières nécessaires à la

fabrication et ne dispose que de 100 heures de finition et 80 heures de menuiserie. La

3
demande des trains et des soldats est illimitée. Sachant que Le prix de vente du jouet
de type soldat est de 3 dinars et celui de type train est de 2 dinars, déterminer le plan
de production qui maximise le profit de l'usine.

On note par :
x1= le nombre de soldats produits chaque semaine,
x2= le nombre de trains produits chaque semaine.
D'après les données, on définie les contraintes suivantes représentent la disponibilité
des facteurs de production:
 Menuiserie: on dispose de 80 heures de menuiseries, pour fabrique 1 soldat il faut
1 heure et pour un train il faut 1 heure. la contrainte liée à la menuiserie est :
x1  x 2  80
 Finition : la finition d’1 soldat nécessite 2 heures de travail, et celle d'1 train
nécessite 1 heure, le fabriquant ne dispose que de 100 heures de travail. La
contrainte liée à la limitation de la finition est:
2 x1  x2  100 .
Il s'agit d'un programme linéaire à deux variables de décision, la fonction objectif est
la suivante : z  3x1  2 x 2 .

Le problème consiste à maximiser le profit de l'usine, donc le programme linéaire

suivant :

Max 3 x1  2 x 2
s .c. x1  x 2  80
2 x1  x 2  100
x1  0, x 2  0

Exemple 2 : Problème d’agriculture 2

Un des meilleurs exemples qui explique bien la formulation d'un PL est celui lié au
problème de l'agriculteur. Par conséquent, on reprend dans ce qui suit les différentes
étapes de sa formulation.

2
Exemple du cours du Prof. Mohamed Saleh Hannachi

4
Cet agriculteur veut allouer 150 hectares de surface irrigable entre la culture de
tomates et la culture de piments. Pour cela, il dispose de 480 heures de main d’œuvre
et de 440 m3 d’eau. L'hectare de tomates demande 1 heure de main d’œuvre, 4 m3
d’eau et donne un bénéfice net de 100 dinars. Cependant, 1 hectare de piments
nécessite 4 heures de main d’œuvre, 2 m3 d’eau et donne un bénéfice net de 200
dinars.
De plus, pour des raisons de protection du prix des tomates le bureau du périmètre
irrigué ne lui permet pas de cultiver plus de 90 hec de tomates.
Quelle est donc la meilleure allocation de ses différentes ressources ?

Formulation du problème en un PL :

1ère Étape: On considère

 x1 : la surface allouée à la culture des tomates
 x2 : la surface allouée à la culture des piments
Les variables de décision x1 et x2 sont positives : x1  0, x2  0 .
2ème Étape: Identification des contraintes.
 Terrain : la contrainte liée à la limitation de la surface de terrain est
x1  x2  150
 Eau : La contrainte qui exprime les limitations des ressources en eau est
4 x1  2 x2  440 .
 Main d’œuvre : La contrainte représentant les limitations des ressources humaines
est x1  4 x2  480
 Les limitations du bureau du périmètre irrigué : La contrainte qui représente cette
restriction est x1  90.
3ème Étape : La fonction objectif consiste à maximiser le profit apporté par la culture
de tomates et de piments. Les contributions respectives des deux variables de
décision x1 et x2 sont 100 et 200. La fonction objectif est z  100 x1  200 x2 .
Le PL lié au problème d’agriculture est le suivant:

5
 Max 100 x1  200 x2
s.c. x1  x2  150
4 x1  2 x2  440
x1  4 x2  480
x1  90
x1  0, x2  0

Exemple 3 : Problème de médecine 3

Comme pour l'exemple précédent ce problème fait l'un des plus connus dans la
programmation linéaire des problèmes de minimisation. En conséquence, nous avons
vue utile de le reprendre dans ce chapitre.
Un spécialiste a fabriqué des pilules pour guérir les malades atteints d’un rhume. Ces
pilules sont fabriquées selon deux formats :
 La petite taille : contient deux grains d’aspirine, cinq grains de bicarbonate et un
grain de codéine.
 La grande taille : contient un grain d’aspirine, huit grains de bicarbonate et six
grains de codéine.
Pour guérir le rhume, le malade a besoin de 12 grains d’aspirine, 74 grains de
bicarbonate et 24 grains de codéine.
Déterminer le nombre de pilules minimales à prescrire au sujet pour qu’il soit guérit.

Formulation du problème en un PL :
Les variables de décision sont :
 x1 : le nombre de pilules de petite taille.
 x2 : le nombre de pilules de grande taille.
Les variables de décision x1 et x2 sont positives : x1  0, x2  0 .
Les contraintes liées au problème sur les valeurs possibles de x1 et x2 sont :

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

6
 une petite pilule contient 2 grains d’aspirine et une grande pilule contient 1 seul
grain d’aspirine. La prescription doit contenir des pilules avec au moins 12 grains
d’aspirine. on obtient la contrainte suivante :
2 x1  x2  12
 La prescription du spécialiste doit contenir au moins 74 grains de bicarbonate.
Ainsi la contrainte suivante doit être satisfaite :
5x1  8x2  74 .
 La prescription doit contenir au moins 24 grains de codéine donc la contrainte
suivante doit être satisfaite :
x1  6 x2  24 .
La quantité de pilules à prescrire est celle qui minimise le nombre total des pilules, La
fonction objectif est donc la suivante:
z  x1  x2 .

Le programme linéaire lié à ce problème est le suivant :

Max 100 x1  200 x2 Min z  x1  x2

s .c. 2 x1  x2  12
s.c. x1  x2  150
5 x1  8 x2  74
4 x1  2 x2  440
x1  6 x2  24
x1  4 x2  480 x1  0 , x2  0
x1  90
x1  0, x2  0

7
CHAPITRE 2

Résolution graphique d’un programme linéaire

I. Introduction

Comment un problème modélisé par un programme linéaire, peut être résolu?

Pour répondre à cette question, la méthode graphique est l’une des premières
méthodes utilisées à ce sujet. Cette méthode permet de résoudre le PL mis sous forme
d'un problème mathématique.

La résolution graphique se limiter à une représentation à deux variables (au plus à

trois variables. Ceci indique que dans ce chapitre on examinera seulement les
programmes linéaires à deux variables de décision.

II. Représentation graphique d'un PL

1) Représentation des contraintes

Afin de résoudre graphiquement un PL, il est indispensable de faire une

représentation graphique précise et claire.

Cette représentation se limite seulement au cadran positif vue que les variables de
décision sont positives. Cette région s’appelle la "Zone des solutions possibles" du
problème notée ZSR.

Reprenons l’exemple relatif au problème de médecine:

Min z  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

8
Remarque:

Plusieurs solutions possibles d’un problème:

- ceux qui vont satisfaire toutes les contraintes du PL sont appelés "les solutions
réalisables". - ceux qui vont satisfaire une partie ou aucune de ces contraintes, appelés
solutions non réalisables.

La représentation graphique des contraintes permet de déterminer l’ensemble des

solutions réalisables.

Ainsi, pour le problème de médecine les contraintes sont représentées par des
droites. Pour 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 .
Pour la vérification, il suffit de prendre un point de cette zone et voir s'il satisfait la
contrainte en question.
Et ainsi de suite jusqu'à représenter toutes les contraintes et définir les zones des
points qui les satisfont.

Enfin, il devient possible de définir une solution réalisable du problème. Cette solution
vérifié toutes les contraintes, c’est à dire elle appartient aux zones relatifs à chacune
des contraintes du PL. Le graphique obtenue est le suivant :

x2
Zone des
12 solutions
réalisables

x1
6 12 24

2) Représentation de la fonction objective

Considérons " z " la valeur de la fonction objectif du problème de médecine:

z  x1  x2 .

9
Pour z =0, la fonction objectif est représentée de la manière suivante :

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

Dans ce cadrant positif, on peut tracer une infinité de droites qui représentent les
différentes valeurs de la fonction objectif, qui sont parallèles entre elles.
Puisqu'il s'agit d'un problème de minimisation, on doit diminuer la fonction objectif
(voire graphique) jusqu'à avoir la solution réalisable qui permet de minimiser cette
fonction

x2

12

x1
6
z  18
z  6 z  12

Après avoir fait la représentation graphique, le problème qui se pose est de connaître
qu’elle est la droite qui correspond à la valeur minimale de la fonction objectif ? C'est
l'objet de la section suivante.

III. Recherche de la solution optimale

1) Résolution graphique

La représentation graphique de toutes les contraintes permet de déterminer la zone des

solutions réalisables. Cette zone fait l'intersection de toutes les solutions qui vérifient
toutes les contraintes. La droite relatives à la fonction objectif permet selon la nature
du problème de déterminer la solution optimale. Cette dernière correspond à la
solution réalisable qui intercepte la droite à la plus petite valeur de z. (puisqu'il s'agit
d'un problème de minimisation).

Le graphique suivant correspond à la représentation finale du problème de médecine.

10
 x2

12
B

x1
6 12
Z=10

La solution optimale de ce programme est l’intersection des deux contraintes

suivantes :
2 x1  x2  12
et
5x1  8x2  74
La résolution du système linéaire suivant :
 2 x1  x2  12

5 x1  8 x2  74
Permet de trouver le point qui minimise la fonction objectif. Celle ci correspond
d’après le graphique au point B= (2,8).

Ainsi le nombre de pilules de petites tailles est égal à 2 et 8 pour les pilules de grande
taille.

La valeur de la fonction objectif est donc égal à z  x1  x2  2  8  10 .

2) Résolution par énumération

Le graphique lié au problème de médecine montre plusieurs points d’intersection des

droites qui forment les contraintes. Ainsi, il convient de calculer pour chaque point la
valeur de la fonction objectif et déterminer par suite la valeur optimale de la fonction
objectif.

Remarque: la solution optimale d'un PL est un point extrême qui se trouve sur le
bord de l’ensemble des solutions. Cette solution est dite solution réalisable de base.
x2

12 A
B

3 C D

x1
6 12

Les points extrêmes du problème de médecine, appartenant à l’ensemble des solutions

réalisables sont:

11
  A(0,12) : donne une valeur de la fonction z  x1  x2  0  12  12

 B(2,8) (intersection des contraintes 1 et 2): donne une valeur de la fonction

z  x1  x2  2  8  10

 C (23/11,126/11) (intersection des contraintes 2 et 3) : donne une valeur de la

fonction z  23 / 11  126 / 11  13.54

 D(24,0): donne une valeur de la fonction z  x1  x2  24  0  24

D'après les valeurs de la fonction objectif associée aux différents points A, B, C et D,

on peut vérifier que le point B(2,8) correspond à la solution optimale du problème
dont sa valeur optimale égale à 10.

IV. Application

Reprenons l'exemple de la fabrication des jouets et trouvons à l'aide de la

représentation graphique la solution de son programme linéaire donné ci-dessous:

Max 3 x1  2 x 2
s .c. x1  x 2  80
2 x1  x 2  100
x1  0, x 2  0

Il s'agit d'un programme linéaire de deux dimensions (deux variables de décision).

La représentation graphique du PL est la suivante:

ZSR

12
 Le tableau suivant présente les différents points extrêmes :

Coordonnées des Valeur de la

points extrêmes fonction objectif
A (0,80) 3  0+2  80=160
B (20,60) 3  20+2  60=180
C(50,0) 3  50+2  0=150

On conclut que le meilleur plan de production est donné par le point B (20,60) qui est
l'intersection des deux contraintes : 20 soldats et 60 trains, qui permettent de donner la
valeur maximale de la fonction objectif qui est égale à 180

Exercice :(cas particuliers)

Résoudre graphiquement les programmes linéaires suivants :

b) M ax Z  3x1  2x 2
a) M in Z  2 x1  x 2 c) M ax Z  x1  2x 2
Sc 2 x1  x  5
Sc x1  2 x 2  4 2 Sc  2 x1  x 2  2
x1  x 2  3 x1  x 2  1  x1  2 x 2  5
3x1  x 2  5 x1  x  3 x1  4 x 2  4
2
x1 , x 2  0 x1 , x 2  0 x1 , x 2  0

Corrigé :

a) M in Z  2 x1  x 2
Sc x1  2 x 2  4
x1  x 2  3
3x1  x 2  5
x1 , x 2  0

13
b) M ax Z  3x 1  2x 2
Sc 2x 1  x  5
2
x1  x 2  1
x1  x  3
2
x1 , x 2  0

c) M ax Z  x 1  2x 2
Sc  2x 1  x 2  2
 x 1  2x 2  5
x1  4 x 2  4
x1 , x 2  0

14
15
CHAPITRE 3
L’Algorithme de simplexe

I. Introduction

La résolution d'un PL par la représentation graphique est liée au problème avec deux
variables de décision. Ainsi, si un problème possède plus que deux variables (qui est
le cas le plus fréquent) à détermine, il faut passer à une autre méthode adapté à ce
genre de problème.

Cette méthode fera l'objet de ce chapitre et c'est la méthode de simplexe qui a

permis de résoudre des programmes avec plusieurs variables.

Dans ce chapitre nous commençons par présenter la méthode de simplexe pour les
problèmes de maximisation.

Afin de résoudre les problèmes de maximation par la méthode de simplexe plusieurs

étapes doivent être respectées. Dans ce qui suit nous présentons avec détails ces
étapes.

II. Forme standard d'un PL

Cette étape consiste à mettre le PL sous une forme standard qui consiste à introduire
des variables supplémentaires dans chaque contrainte qui permettent de réécrire les
contraintes avec les inégalités (  ) sous la forme d'égalités.

Ces variables supplémentaires ou encore appelées variables d'écarts représentent les

ressources non utilisés

16
 La forme standard est le suivant :
Max c1 x1  c2 x2    c N x N Max c1 x1  c2 x2    c N x N
s .c a11 x1  a12 x2    a1N x N  b1 s .c a1 1x1  a1 2 x2    a1 N x N  S1  b1
a21 x1  a22 x2    a2 N x N  b2  a2 1 x1  a 2 2 x2    a2 N x N  S 2  b2
 
a M 1 x1  a M 2 x2    a MN x N  bM a M 1 x1  a M 2 x2    a MN x N  S M  bM
x1  0 , x2  0 , , x N  0 x1  0 , x2  0 , , x N  0
S1  0 , S 2  0 , , S M  0

Initial Standard
Max 100 x1  200 x2 Max 100 x  200 x
1 2
s.c. x1  x2  150 s .c. x  x  S1  150
1 2
4 x1  2 x2  440 4 x  2 x  S 2  440
1 2
x1  4 x2  480 x  4 x  S 3  480
1 2
x1  90 x  S4  90
1
x1  0, x2  0 x  0, x  0
1 2

s1= 150 , s2=440 s3=480 et s4=90 ressources non utilisées

Exemple: pour l'application on considère l'exemple suivant

Max 1000 x1  1200 x 2

s.c. 10 x1  5 x 2  200
2 x1  3 x 2  60
x1  34
x2  14
x1  0, x 2  0

La forme standard du programme linéaire de ce PL est :

Max 1000 x1  1200 x 2  0.S 1  0.S 2  0.S 3  0.S 4

s .c. 10 x1  5 x 2  s1  200
2 x1  3 x 2  s 2  60
x1  s 3  34
x 2  s4  14
x1  0, x 2  0; s1  0; s 2  0; s3  0; s 4  0

Où s1;s2; s3 et s4 représentent les variables d'écart (appelées aussi surplus). L'impact

de ces variables sur la fonction objectif est nul et leur existence est liée à la mise en
forme du programme linéaire initial. Ces variables d'écart peuvent prendre des valeurs

17
non négatives. La valeur des variables d'écart à l'optimum représente les ressources
non utilisées.

III. La méthode du simplexe: Les étapes de l'algorithme

Variables de base et variables hors base

Soit un système d’équations à n variables et m équations où n  m. Une solution de

base pour ce système est obtenue comme suit :

- On pose n - m variables égales à 0. Ces variables sont dites des variables hors
base notées : V.H.B.
- On résout le système pour les autres variables. Qui sont appelées des variables
de base : V. B.
- Les variables obtenues sont appelées solutions de base (la solution de base
contient les variables de base et aussi les variables hors base).

Pour notre exemple : on n= 6 (nombre de variables)

m=4 (nombre d'équations)

Le nombre de variables à annuler ou les variables hors bases sont telles que n-m=6-
4=2
Donc on a deux variables hors base, et comme la solution initiale de base est l'origine
alors pour le programme donné ci-dessus, une solution réalisable de base serait celle
où x1 = x2 = 0,

Ainsi les variables de base sont: s1 = 200 ; s2 = 460 ; s3 = 34 et s4 = 14 est une

solution qui correspond l’origine O de l’ensemble des solutions réalisables. La
solution est retrouvée en annulant toutes les variables de décision.

La méthode de simplexe permet à partir de l’origine de générer successivement des

solutions réalisables de base pour le PL et la valeur de "la fonction objectif " va à
chaque fois augmenter jusqu'à arriver à la solution optimale du problème.
La solution optimale ne peut être qu'un point extrême appartenant à la ZSR.

"La méthode de simplexe est une procédure itérative permettant de passe d’une
solution réalisable de base à une autre afin de trouver la solution optimale".

18
 IV. La présentation des tableaux

Nous présentons dans ce qui suit les différentes étapes de la méthode

1ère étape : Tableau de simplexe initial

Comme nous l'avons mentionné plus haut, une solution réalisable de base est obtenue
en annulant les (n-m) variables de décision et par suite la valeur des variables d'écart
est directement donnée par le second membre. De même les contraintes de non
négativité des variables d'écart sont satisfaites.

Un programme linéaire doit satisfaire les propriétés suivantes :

 P1) Les variables d'écart dans un problème mis sous sa forme standard, il y a m
variables avec un coefficient non nul figurant dans chaque contraintes: S1, S2,
S3 et S4.
 P2) Toutes les valeurs du second membre des contraintes doivent être positives.
(les composants du vecteur b)
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 4 est :

Max 1000 x1  1200 x2  0.S 1  0.S 2  0.S 3  0.S 4

s .c. 0  0  s1  200
0  0 2  s 2  60
0  s 3  34
0  s4  14
x1  0 , x2  0; s1  0; s 2  0; s3  0; s 4  0

cj coefficient correspond aux variables dans la fonction

"objectif"

VB Toutes les variables

Ci VVB

A = (aij)i,j
coefficients variables Valeur
des de base des matrice des coefficients
variables variables
des contraintes du programme
de base de base
standard

4
Hatem Mnasri (2001) "NOTE DU COURS DE RECHERCHE OPERATIONNELLE"

19
Pour notre exemple le tableau de simplexe initial est le suivant :

z = 1000x1+1200x2 +0s1+0s2+0s3+0s4 (coefficients des variables de

1000 1200 0 0 0 0 la
x1 x2 s1 s2 s3 s4 fonction objectif)
0 s1 200 10 5 1 0 0 0
0 s2 60 2 3 0 1 0 0 10x1+5x2+1s1= 200 (Coefficients des variables dans la 1ère contrainte)
0 s3 34 1 0 0 0 1 0
0 s4 14 0 1 0 0 0 1

Valeur des variables de base

Coefficients des Variables de Base (les contributions nulles des variables d'écart de la
solution de base initiale).

Pour x1 = x2 = 0 : la valeur de la fonction objectif est z0 = 1000.0+1200.0=0.

Ainsi, il sera indispensable d'améliorer cette valeur.

2ème étape : Augmentation de la solution optimale

Cette étape consiste de passer de cette solution réalisable de base initiale à une
solution réalisable de base qui améliore la valeur de la fonction objectif. Afin
d'améliorer cette solution il faut générer une autre solution de base qui augmente la
valeur de la fonction objectif. Autrement dit, on doit choisir une variable hors base et
une variable de base et les permuter de telle façon que la nouvelle solution donne une
valeur plus grande de la fonction objectif.

Pour ce faire on doit introduire deux nouvelles lignes au-dessus du tableau de

simplexe.

La 1è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.
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

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

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

suivant :

cj 1000 1200 0 0 0 0
x1 x2 s1 s2 s3 s4
0 s1 200 10 5 1 0 0 0
0 s2 60 2 3 0 1 0 0
0 s3 34 1 0 0 0 1 0
0 s4 14 0 1 0 0 0 1
zj 0 0 0 0 0 0
cj - zj 1000 1200 0 0 0 0

Choix de la variable entrante et de la variable sortante

Au niveau de la ligne relative à l’évaluation nette cj - zj, on remarque qu’une

augmentation d’1 unité de la valeur de x1 engendre un profit de 1000 dinars, alors
qu’une augmentation d’1 unité de la valeur de x2 engendre un profit supplémentaire
de 1200 dinars. Donc, on doit opter pour une augmentation de la valeur de x2. x2 est
la variable entrante (VE)
Le fait de faire introduire dans la base une variable, nous oblige à faire sortir une autre
variable.
La variable sortante est obtenue en choisissant la plus petite valeur positive des
divisions de 200/5, 60/3, 34/0 et 14/1 (on suppose que 34/0 est égale à l’infini).

En général, la valeur maximale de la variable sortante xj est le minimum des valeurs

positives des rapports de Qi/aik ( aik sont les coefficients de la colonne de la variable
entrante).
Les valeurs de Qi/aik feront l’objet d’une autre colonne à droite de la matrice A.

21
Dans notre exemple, on obtient le tableau suivant :

cj 1000 1200 0 0 0 0
Qi/aik
x1 x2 s1 s2 s3 s4
0 s1 200 10 5 1 0 0 0 40
0 s2 60 2 3 0 1 0 0 30
0 s3 34 1 0 0 0 1 0 
0 s4 14 0 1 0 0 0 1 14 VS
zj 0 0 0 0 0 0
cj - zj 1000 1200 0 0 0 0

VE

Si x2 augmenter jusqu’à la valeur 14 va engendrer l’annulation de la valeur de S3, ce

qui élimine S4 de la base.

À l’intersection de la ligne pivot relative à la variable entrante x1 et de la colonne

pivot relative à la variable sortante s4 est l’élément pivot. Donc 1 est l'élément pivot.

Calcul des tableaux suivants: Le pivotage s’effectue de la manière suivante

- On commence par diviser la ligne du pivot par le chiffre du pivot.

- On poursuit avec la matrice identité pour les variables de base. Ainsi, on met
1 à l’intersection de chaque variable et 0 ailleurs.

On présente le tableau suivant relatif à la nouvelle solution de base :

cj 1000 1200 0 0 0 0
x1 x2 s 1 s 2 s 3 s 4
0 s1 . . 0 1 0 0 .
0 s2 . . 0 0 1 0 .
0 s3 . . 0 0 0 1 .
1200 x2 14 0 1 0 0 0 .

On doit à présent déterminer les coefficients aij de la nouvelle matrice A et les valeurs
Qi des variables de base (les cases avec des valeurs manquantes).
Pour faire les calcules nécessaires on utilise la règle de pivot :

22
 cj 1000 1200 0 0 0 0 cj 1000 1200 0 0 0 0
Qi/aik
x1 x2 s1 s2 s3 s4 x1 x2 s 1 s 2 s 3 s 4
0 s1 10 0 1 0 0 .
0 s1 200 10 5 1 0 0 0 40
30
0 s2 . . 0 0 1 0 .
0 s2 60 2 3 0 1 0 0
0 s3 34 . 0 0 0 1 .
0 s3 34 1 0 0 0 1 0 
14
1200 x2 14 0 1 0 0 0 .
0 s4 14 0 1 0 0 0 1

On présente dans ce qui suit des exemples de calcule de quelques valeurs:

Pour remplacer 10 on multiplie 10 par l'élément pivot 1 et on multiplie 0 (l'élément
sue la même ligne 0 par 5 puis on divise par l'élément pivot.

10  1  0  5
La valeur trouvée est 10 :  10
1

34  1  14  0
 34
1

En faisant tous les calcules, on trouve le tableau suivant :

cj 1000 1200 0 0 0 0
x1 x2 s1 s2 s3 s4
0 s1 130 10 0 1 0 0 -5
0 s2 18 2 0 0 1 0 -3
0 s3 3 1 0 0 0 1 0
1200 x2 14 0 1 0 0 0 1

Il est possible de passer à la deuxième itération qui s'effectue de la même façon.

On remarque que la valeur de la fonction objectif augment car la nouvelle solution

réalisable de base est
x1 = 0 ; x2 = 14 ; S1 = 130 ; S2 = 13; S3 = 3; S4 = 0

La valeur de la fonction objectif augment et passe de 0 à 16800. En effet, pour x1 = 0 et

x2 =14: la valeur de la fonction objectif est z0 = 1000.0+1200.14=16800.

23
 La question qui se pose maintenant est à quel point il faut augmenter la valeur de la
fonction objectif? Pour répondre, on applique la règle qui permet de s'arrêter et de
donner le tableau optimale. Ainsi l'algorithme du simplexe s'arrête lorsque: les cj-zj
sont négatives ou nulles pour un problème de maximisation. c j  z j  0

cj 1000 1200 0 0 0 0
Qi/aik
x1 x2 s1 s2 s3 s4
0 s1 130 10 0 1 0 0 -5 13
0 s2 18 2 0 0 1 0 -3 9
0 s3 3 1 0 0 0 1 0 3 VS (s3)
1200 x2 14 0 1 0 0 0 1 
cj 0 1200 0 0 0 1200
cj-zj 1000 0 0 0 0 -1200

VE(x1)
cj 1000 1200 0 0 0 0
x1 x2 s1 s2 s3 s4
0 s1 100 0 0 1 0 -10 -5
0 s2 6 0 0 0 1 -2 -3
1000 x1 3 1 0 0 0 1 0
1200 x2 14 0 1 0 0 0 1
cj 1000 1200 0 0 1000 1200
cj-zj 0 0 0 -1000 -1200

On remarque que les c j  z j  0 donc il s'agit du dernier tableau de simplexe. c'est le

tableau de la solution optimale qui maxmise la fonction objectif.

Cette nouvelle solution est donc

x1 = 3; x2 = 14; S1 = 100; S2 = 6; S3 =0; S4 = 0

Avec : Z=1000.3+1200.14=19800

La valeur de la fonction objectif augmente jusqu'à atteindre l'optimum et il n’y a pas

une autre solution réalisable de base qui peut maximiser la valeur de la fonction
objectif. Ce tableau de simplexe est donc le tableau optimal.

24
V. Procédure de la méthode du simplexe:

Dans ce qui suit on présente les étapes à suivre pour résoudre un problème de
maximisation sous des contraintes de type  et avec un second membre positif.

Les étapes à suivre sont les suivantes:

1. Formuler un programme linéaire pour le problème réel: Pour obtenir une

représentation mathématique du problème
2. Vérifier que le second membre du programme linéaire est positif: Ceci est
nécessaire pour obtenir comme variable de base initiale l’origine
3. Écrire le programme linéaire sous une forme standard : Mettre toutes les contraintes
sous forme d’égalité
4. Construire le premier tableau de simplexe : Ce tableau correspond à la solution
initiale de base
5. Choisir comme variable entrante dans la base celle qui admet le plus grand effet net
positif cj-zj: La valeur de cj-zj indique la quantité d’augmentation de la fonction
objective si on augmente la valeur de xj d’une unité.
6. Choisir la variable sortante de la base celle qui admet le plus petit ratio supérieur à
zéro: La plus petite valeur de Qi/aij indique le nombre 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 règle de pivot: Cette règle nous permet
entre autre de calculer les valeurs des nouvelles variables de décision
8. Test d’optimalité: Si (cj-zj)  0 pour toutes les variables (HB), la solution obtenue
est donc optimale. Sinon on doit retourner à l’étape 5.

25