Chapitre1 : Programmation Linéaire

1
 Chapitre1 : Programmation Linéaire

1. Introduction
La « direction et la gestion » de grands systèmes d’hommes, de matériaux et d’argents
dans l’industrie, la gouvernance et la défense nécessitent l’application des méthodes
d’optimisation et de recherche opérationnelle. Ces méthodes permettent aux responsables de
pallier éventuellement l’insuffisance du bon sens et de les aider dans l’élaboration des
meilleures décisions.
La diminution des ressources naturelles et des sources de financement combinées à une
concurrence toujours plus vive entre les entreprises, entrainent une répartition optimale des
moyens disponibles. Cette répartition constitue la tâche principale des responsables politiques
et économiques de notre société. Ce problème se retrouve dans tous les domaines de l’activité
économique, politique, scientifique et sociale. En raison de l’importance des enjeux, le
gestionnaire ne peut plus prendre de décisions hâtives et justifier un choix d’attribution fondé
sur un raisonnement instinctif ou des calculs naïfs. Une bonne résolution de ce type de
problèmes nécessite la connaissance de méthodes approuvées ainsi que la maîtrise des outils
mathématiques et informatiques développés à cet effet.

2. Formulation de la fonction objective et des contraintes.

Mathématiquement il s’agit de déterminer les valeurs (niveaux d’activité des variables ou

activités) x1 , x2 , x3 ..... xn représentant les paramètres du programme. Ces valeurs devant

satisfaire simultanément à un certain nombre de « contraintes » relatives aux ressources
(disponibilités), et de plus, rendre maximale ou minimale une fonction de coûts
(fonctionnelle, fonction objective ou fonction économique)

Comme par exemple on peut chercher dans une entreprise les valeurs x j d’un certain nombre

d’activités X j , les ressources étant limitées b1 pour l’investissement, b2 pour les frais de

stockage, b3 pour les heures de travail, b4 pour la consommation de l’énergie et ainsi de

suite. En supposant connus, pour chaque activité X j l’investissement unitaire a1 j , le coût de

stockage unitaire a2 j , le temps de fabrication unitaire a3 j , la consommation unitaire de

l’énergie a4 j etc. Après avoir évalué le profit unitaire c j escompté sur chaque activité X j et
si on cherche à maximiser le profit total le programme linéaire à résoudre sera :

2
 Chapitre1 : Programmation Linéaire

MaxF   c j x j
 n

P.L  aij x j  b j 1  j  m
 i 1
x j  0


3. Résolution du programme linéaire par la méthode graphique.

Nous allons prendre un exemple simple pour résoudre un programme linéaire par la
méthode graphique.
Exemple : Une petite entreprise fabrique deux types d’écrous. Un écrou peut être fabriqué
en trois opérations :
 Opération de coupe : découpage d’une barre hexagonale (2 machines sont
disponibles pour cette opération)
 Opération de perçage : un trou est réalisé dans chaque pièce découpée (4 machines
sont disponibles pour cette opération)
 Opération de filetage : à l’intérieur de chaque trou on procède à un filetage (17
machines sont disponibles pour cette opération)
Cette entreprise travaille 8 heures par journée et les machines suivant le tableau ci-
dessous :
Opérations Ecrou de type 1 Ecrou de type 2
Coupe 2 secondes 2s
Perçage 5s 3s
Filetage 10s 20s

Le profit attendu est de 3 unités (3 D.A par exemple) pout un écrou de type 1 et de 4
unités pout un écrou de type 2. Le problème qui se pose au gérant de cette entreprise est le
suivant : Combien d’écrous de chaque type devrait-on fabriqué pour que le profit

soit maximum ?
Formulation du P.L. : Nous allons d’abord établir le modèle mathématique du PL.

 Définitions des variables :

Soit : X1 le nombre d’écrous de type 1.
X2 le nombre d’écrous de type 2.

3
 Chapitre1 : Programmation Linéaire

 Disponibilité des machines (contraintes):

Coupe 2x (8x60x60) 57.600 s
Perçage 4x (8x60x60) 115.200 s
Filetage 17x (8x60x60) 489.600 s

Le P.L. à résoudre est:

MaxF   3x1  4 x2
2 x  2 x  57.600
 1 2

P.L 5 x1  3 x2  115.200
10 x  20 x  489.600
 1 2

 x1 , x2  0

La résolution graphique consiste à tracer les droites (x1,x2) pour chaque contrainte et
ainsi déterminer le domaine des solutions possible pour enfin trouver le point (x1,x2) qui
maximise la fonction économique F. La figure ci-dessous montre « le domaine des solutions
possibles ». Tous les points situés à l’intérieur du polyèdre OABCDO sont des solutions
possibles. Le couple (x1,x2) qui maximise la fonction économique est le point le plus éloigné
possible de l’origine O (x1=0,x2=0) donc c’est forcément l’un des sommets A, B, C, ou D.

4
 Chapitre1 : Programmation Linéaire

Les coordonnées des ces points sont :

 x2  0.  x2  0.
A intersection de    F  A  69.120
 1
5 x  3 x 2  115.200  1
x  23 .040

2 x1  2 x2  57.600  x1  14.400
B intersection de    F B   100.800
 1
5 x  3 x 2  115.200  2
x  14.400

2 x1  2 x2  57.600  x1  8.640
C intersection de    F C   106.560
 1
10 x  20 x 2  489.600  2
x  20 .160

 x1  0.  x1  0.
D intersection de    F D   97.920
 1
10 x  20 x 2  489.600  2
x  24 .480

Nous constatons que la fonction économique F (106 560) est maximale au point C dont les
coordonnées sont : x1=8 640 et x2=20 160. La solution de ce P.L. est :

 x1  8.640
  F  106.560
 2
x  20 .160
Remarque : Vérification des contraintes : en remplaçant : x1 et x2 par leurs valeurs dans les
inéquations définissant les contraintes nous obtenons :

2 x1  2 x2  57.600
5 x1  3x2  103.680  115.200
10x1  20x2  489.600
Ce qui veut dire que les machines destinées à la coupe et au filetage travaillent à plein
temps et celles destinées au perçage restent inoccupées pendant (115 200-103 680 = 11 520 s)
correspondant à 3h 12’.
Remarque : la méthode graphique que nous venons de voir s’applique seulement aux modèles
comportant 2 ou au maximum 3 variables. La méthode du simplexe permet la résolution de
programmes linéaires de taille quelconque.
4. Résolution du programme linéaire par la méthode du simplexe.
La méthode du « simplexe » ou méthode de Dantzig est une technique qui permet de
trouver la solution optimale d’un P.L. d’une façon ordonnée et précise. Nous allons la
détaillée sur un exemple simple. Le P.L. à résoudre est le suivant :

5
 Chapitre1 : Programmation Linéaire

MaxF   4 x1  3 x2
 x  4.000


1

P.L  x2  6.000
 x  3 2 x  6.000
 1 2


 1 2
x , x  0

1ère étape : La première étape consiste à mettre le P.L. sous forme standard c'est-à-dire
transformer les inégalités en égalités en ajoutant des variables d’écart. La forme standard du
P.L. est :
1x1  0 x2  1x3  0 x4  0 x5  4.000

aij x j  bi  0 x1  1x2  0 x3  1x4  0 x5  6.000
 x  3 2 x  0 x  0 x  1x  6.000
 1 2 3 4 5

et F  Max4 x1  3 x2  0 x3  0 x4  0 x5 

Avec :
x1, x2 : variables principales (inconnues du problème)
x3, x4, x5: variables d’écart (variables de base)
Nous exprimons cette forme standard du P.L. sous forme de tableau :
Tableau N°1 :

V. X1 X2 X3 X4 X5 bi
V.B.
X3 1 0 1 0 0 4000
X4 0 1 0 1 0 6000
X5 1 3/2 0 0 1 6000
F 4 3 0 0 0 0

Les coefficients des variables d’écart forment une matrice unitaire I qui est la base
initiale.
Ce tableau présente la première solution admissible c'est-à-dire :
 x1  0.0 x2  0.0

Point O (0,0)  x3  4.000 x4  6.000 x5  6.000
MaxF   4 x  3 x  4 x0  3 x0  0.0
 1 2

2ère étape : Pour débuter le processus de la recherche de la solution optimale du P.L. on

s’appui sur les 2 critères de Dantzig :

6
 Chapitre1 : Programmation Linéaire

 Premier critère : Pour déterminer la colonne xj qui doit entrer dans la base, on choisit celle
qui comporte le coefficient positif le plus grand dans la dernière rangée (coefficients de la
fonction économique).
 Deuxième critère : On calcul le rapport entre les bi et les coefficients de la nouvelle
variable qui entre dans la base et la variable qui doit sortir de cette base est celle dont le
rapport est le plus petit.

V. X1 X2 X3 X4 X5 bi Rapport
V.B. bi/aj
X3 1 0 1 0 0 4000 4000/1=4000
pivot X3 sort de la base
X4 0 1 0 1 0 6000 6000/0=∞
X5 1 3/2 0 0 1 6000 6000/1=6000
F 4 3 0 0 0 0

X1 entre dans base

En appliquant ces critères pour notre cas c’est la variable x1 qui rentre dans la base et
la variable x3 qui sort de la base. Le pivot représente le terme aij qui se trouve à l’intersection
de la colonne j et de la ligne i des variables qui entre et qui sort de la base.
3ère étape : Transformation du tableau (recherche d’une autre solution). Le tableau précédent
sera transformé en adoptant les règles suivantes :
1] On repère le pivot (intersection de la colonne j et de la ligne i des variables qui entre et qui
sort de la base)
2] On divise la ligne i de la variable qui sort de la base par le pivot.

V. X1 X2 X3 X4 X5 bi
V.B.
X1 intègre la base 1/1 0/1 1/1 0/1 0/1 4000/1

3] Pour les lignes du tableau qui comportent un 0 dans la colonne de la variable qui entre dans
la base ne seront pas modifiées (ligne i=2 pour la variable de base x4).

7
 Chapitre1 : Programmation Linéaire

V. X1 X2 X3 X4 X5 bi
V.B.
X4 0 1 0 1 0 6000

4] Pour les autres lignes du tableau qui comportent un élément ≠ 0 dans la colonne de la
variable qui entre dans la base on multiplie les éléments de la ligne i (ligne du pivot) par
l’élément ≠ 0 divisé par le pivot et on retranche le résultat des éléments correspondant de la
ligne à modifiée. Ceci est valable pour la colonne des bi et ceux de la fonction économique.
Pour la valeur de la fonction économique il faut ajouter et non retrancher.
Application pour la variable x5 :

Ligne à modifiée (X5) 1 3/2 0 0 1 6000

Ligne du pivot (X1) 1 0 1 0 0 4000

Coefficient multiplicateur Cm=1/1=1

Ligne à modifiée (X5) 1 3/2 0 0 1 6000

- Cm x Ligne du pivot (X1) -1x1 -1x0 -1x1 -1x0 -1x0 -1x4000
Coefficients de la ligne modifiée 0 3/2 -1 0 1 2000

Application pour les coefficients de la fonction économique F :

Ligne à modifiée (F) 4 3 0 0 0 0

Ligne du pivot (X1) 1 0 1 0 0 4000

Coefficient multiplicateur Cm=4/1=4

ligne à modifiée (F) 4 3 0 0 0 0

- Cm x Ligne du pivot (X1) -4x1 -4x0 -4x1 -4x0 -4x0 +4x4000
Coefficients de la ligne modifiée 0 3 -4 0 0 +16000

8
 Chapitre1 : Programmation Linéaire

Nous obtenons une nouvelle solution donnée par le tableau N°2

Tableau N°2 :

V. X1 X2 X3 X4 X5 bi
V.B.
X1 1 0 1 0 0 4000
X4 0 1 0 1 0 6000
X5 0 3/2 -1 0 1 2000
F 0 3 -4 0 0 +16000

 x1  4.000 x2  0.0

Point A( 4.000,0)  x3  0.000 x4  6.000 x5  2.000
MaxF   4 x  3 x  4 x 4.000  3x 0  16.000
 1 2

4ère étape : Arrêt du processus : Le processus de la recherche de la solution optimale du P.L.

sera arrêté lorsque tous les coefficients des variables hors base de la fonction économique F
sont ≤ 0. Pour un problème de maximisation et ≥ 0. Pour un problème de minimisation. Si
cette condition n’est pas satisfaite il faut revenir à l’étape N°3.
Dans le cas de notre P.L. nous constatons que, dans la rangée de la fonction économique, le
coefficient de la variable hors base x2 est positif (+3) mais celui de l’autre variable hors base
x3 est négatif (-4) et donc le processus doit continuer car la solution optimale n’est pas encore
atteinte. Il faut revenir à l’étape 3.
3ère étape : Transformation du tableau N°2

V. X1 X2 X3 X4 X5 bi Rapport
V.B. bi/aj
X1 1 0 1 0 0 4000 4000/0=∞
X4 0 1 0 1 0 6000 6000/1=6000
X5 0 3/2 -1 0 1 2000 2000/3 /2=4000/3
Pivot X5 sort de la base
F 0 3 -4 0 0 +16000

X1 entre dans
base

9
 Chapitre1 : Programmation Linéaire

1] On repère le pivot, c’est 3/2

2] On divise la ligne i de la variable qui sort de la base par le pivot.

V. X1 X2 X3 X4 X5 bi
V.B.
X2 intègre la base 0/3/2 3/2/3/2 -1/3/2 0/3/2 1/3/2 2000/3/2
0 1 -2 /3 0 2/3 4000/3

3] Les coefficients de la ligne i=1 pour la variable de base x1 ne changent pas

V. X4 X1 X2 X3 X5 bi
V.B.
X1 1 0 1 0 0 4000

4] Pour les autres lignes du tableau qui restent :

Ligne i=2 x4 :

Ligne à modifiée (X4) 0 1 0 1 0 6000

Ligne du pivot (X5) 0 3/2 -1 0 1 2000

Coefficient multiplicateur Cm=1/3/2=2/3

Ligne à modifiée (X4) 0 1 0 1 0 6000

- Cm x Ligne du pivot (X5) -2/3x0 -2/3x3/2 -2/3x-1 -2/3x0 -2/3x1 -2/3x2000
Coefficients de la ligne modifiée 0 0 2/3 1 -2/3 14000/3

Ligne de la fonction économique F :

Ligne à modifiée (F) 0 3 -4 0 0 +16000

Ligne du pivot (X1) 0 3/2 -1 0 1 2000

Coefficient multiplicateur Cm=3/3/2=2

10
 Chapitre1 : Programmation Linéaire

ligne à modifiée ( F) 0 3 -4 0 0 +16000

- Cm x Ligne du pivot (X1) -2x0 -2x3/2 -2x-1 -2x0 -2x1 +2x2000
Coefficients de la ligne modifiée 0 0 -2 0 -2 +20000

Nous obtenons une nouvelle solution donnée par le tableau N°3

Tableau N°3 :

V. X1 X2 X3 X4 X5 bi
V.B.
X1 1 0 1 0 0 4000
X4 0 0 2/3 1 -2/3 14000/3
X2 0 1 -2/3 0 2/3 4000/3
F 0 0 -2 0 -2 +20000

Nous obtenons une nouvelle solution qui est :

 x1  4000 x2  4000 3

Point B ( 4.000,0)  x3  0. x4  14000 3 x5  0.
MaxF   4 x  3 x  4 x 4.000  3x 4000 3  20.000
 1 2

Arrêt du processus : Dans le cas de notre P.L. nous constatons que, dans la rangée de la
fonction économique, les coefficients des variables hors base x3 et x5 sont négatifs (-2) et
donc le processus doit s’arrêter et la solution optimale atteinte.
Vérification de la solution par la méthode graphique : La résolution graphique est
donnée dans la figure ci-dessous. Tous les points situés à l’intérieur du polyèdre OABCO sont
des solutions possibles. Le couple (x1,x2) qui maximise la fonction économique est le point le
plus éloigné possible de l’origine O (x1=0,x2=0) c’est le sommet B.

 x1  4.000  x1  4000
B intersection de    F B   20.000
 1
x  3 2 x 2  6.000  2
x  4000 3

Nous pouvons vérifier qu’au point A (x1=4000,x2=0) la fonction économique est

FA=16000 et qu’au point C (x1=0,x2=4000) la fonction économique est FC=12000

11
 Chapitre1 : Programmation Linéaire

Pour résumer la méthode du simplexe un organigramme de l’algorithme de celle-ci est

donné dans la page suivante.

12
 Chapitre1 : Programmation Linéaire

Etape N°1
Mise en équation du P.L.

Etape N°2
Construction du tableau
inital

Solution Oui
Optimale Fin
?

Non
Etape N°3
Choix de la variable entrante
variabuation du P.L.

Etape N°4 Il n’en existe pas

Fin
Choix de la variable sortante
variabuation du P.L.
Etape N°5
Pivotage

Etape N°6
Construction du nouveau tableau
inital

Organigramme de l’algorithme de la méthode du simplexe.

13
 Chapitre1 : Programmation Linéaire

REMARQUE :
1. Dans tous ce que l’on vient de considérer toutes les contraintes des différents P.L.
contenaient des signes ≤. Quand le P.L. contient des signes ≥ ou = on transforme le
problème de sorte qu’il soit écrit sous une forme canonique. Pour y arriver on introduit
des « variables artificielles » puis on applique la méthode du simplexe. Les contraintes
k k
de type a
j 1
ij x j  bi sont transformées en a
j 1
ij x j  xk 1  yi  bi et celles de

k k
type a
j 1
ij x j  bi sont transformées en a
j 1
ij x j  yi  bi dans lesquelles les

variables yi sont des variables artificielles qui initialement serviront de variables de

base et qui doivent être égales à 0. dans le tableau final. Pour s’assurer que ces
variables ne seront pas dans la solution finale on leur associe un « coût fictif »
arbitrairement grand (M) dans la fonction économique F lorsqu’on minimise, ou
un « profit fictif » (- M) lorsqu’on maximise. Nous traiterons un exemple pour bien
illustrer ces nouvelles notions.
2. La solution optimale ne peut être atteinte dans tous les cas de figure (solutions non
réalisables, solutions réalisables sans bornes, solutions multiples, solutions
dégénérées…)

5. Dualité. C’est un aspect important de la programmation linéaire. A partir d’un P.L. on

peut former un autre P.L. intimement lié au premier. A tout problème de maximisation
correspond un problème de minimisation impliquant les mêmes données. L’un des
problèmes est appelé « le primal » et l’autre le « dual ». Ces programmes linéaires
possèdent les caractéristiques suivantes :
 La fonction économique d’un des problèmes est maximisée l’autre est minimisée.
 Minimisation des contraintes ≥ et maximisation des contraintes ≤.
 La matrice des coefficients de l’un des problèmes est la transposée de la matrice des
coefficients de l’autre.
 Le coté droit des contraintes de l’un des problèmes est la fonction économique de
l’autre.
 A chaque contrainte du « primal » correspond une variable du « dual » et vice versa.

Exemple : Nous allons considérer un P.L. quelconque comme « primal » et nous nous
proposons de construire son P.L. « dual ».
14
 Chapitre1 : Programmation Linéaire

Soit le P.L. suivant :

MaxF   3 x1  4 x2
 x  x  600


1 2

P.L Primal 2 x1  x2  1000

 x  2 x  1000
 1 2

 x1 , x2  0

 Le P.L. « primal » possède 2 variables principales (x1, x2) et 3 contraintes donc le P.L.
« dual » va avoir 3 variables principales (y1, y2 et y3) et 2 contraintes.
 Le P.L. « primal » maximise F donc le P.L. « dual » minimise F’
 Les contraintes du P.L. « primal » sont ≤ celles du P.L. « dual » seront ≥. A ce stade
nous pouvons écrire :

MaxF   3 x1  4 x2
 x  x  600  
Min F '  . y1  . y 2  . y3
 
. y  . y 2  . y 2  .
1 2

P.L Primal 2 x1  x2  1000 P.L Dual  1
 x  2 x  1000 . y1  . y 2  . y 2  .
 1 2
y , y , y  0
  1 2 3
 x1 , x2  0
 Il faut maintenant remplacer les points des coefficients du P.L. « dual » par les chiffres
qui leurs correspondent. La matrice des coefficients du P.L. « dual » est la matrice
transposée du P.L. « primal » donc :
1 1
1 2 1
2 1
1 1 2
1 2
Et d’autres parts les coefficients du coté droit du P.L. « primal » sont ceux de la fonction
économique du P.L. « dual » donc
 
Min F '  600 y1  1000y2  1000y3

Et finalement nous obtenons :

MaxF   3 x1  4 x2
 x  x  600  
Min F '  600 y1  1000 y 2  1000 y3
 
1 y  2 y 2  1 y 2  3
1 2

P.L P 2 x1  x2  1000 P.L D  1
 x  2 x  1000 1 y1  1 y 2  2 y 2  4
 1 2
y , y , y  0
   1 2 3
 1 2 0
x , x

15
 Chapitre1 : Programmation Linéaire

Nous nous proposons de résoudre P.L. « dual » par la méthode du simplexe et comparer la
solution avec celle donnée par la résolution du P.L. « primal » (méthode du simplexe et
graphique).
Résolution du P.L. dual par la méthode du simplexe :
 
Min F '  600 y1  1000y 2  1000y3

1 y  2 y 2  1 y 2  3
P.L Dual  1
1 y1  1 y 2  2 y 2  4
y , y , y  0
 1 2 3
 Obtention de la forme canonique :
k
Les contraintes sont de type a
j 1
ij y j  bi elles seront transformées en

a
j 1
ij y j  y k 1  xi  bi Nous obtenons :

1y1  2 y 2  1y 2  y 4  x1  3 (I )
1y1  1y 2  2 y 2  y5  x2  4 ( II )

y1, y2, y3 sont les variables principales, y4 et y5 les variables d’écarts et x1 et x2 sont les
variables artificielles
Et la fonction économique devient :
 
Min F '  600 y1  1000y 2  1000y3  0 y 4  0 y5  Mx1  Mx2

Maintenant nous exprimons la fonction économique F’ en fonction des principales et des

variables d’écarts seulement :
Les équations (I) et (II) deviennent :
Mx1  3  1y1  2 y 2  1y2  y 4 M
Mx2  4  1y1  1y2  2 y 2  y5 M

En remplaçant ces valeurs dans la première expression de la fonction économique F’ nous

obtenons une deuxième expression de la fonction économique F’ qui sera bien commode pour
la résolution du P.L. par la méthode du simplexe.
 
Min F '  (600  2M ) y1  (1000  3M ) y2  (1000  3M ) y3  My4  My5  7 M

Le P.L. dual à résoudre par la méthode du simplexe est le suivant :

16
 Chapitre1 : Programmation Linéaire

 
Min F '  600 y1  1000 y 2  1000 y3  0 y 4  0 y 5  Mx1  Mx2 ou bien

 
Min F  (600  2 M ) y1  (1000  3M ) y 2  (1000  3M ) y 3  My4  My5  7 M
'


P.L Dual 1 y1  2 y 2  1 y 2  3
1 y  1 y  2 y  4
 1 2 2

 y1 , y 2 , y 3  0


Tableau N°1 :

V. Y1 Y2 Y3 Y4 Y5 X1 X2 bi Rapport
V.B. bi/aj
X1 1 2 1 -1 0 1 0 3 3/2
X2 1 1 2 0 -1 0 1 4 4/1
F’ 600 1000 1000 0 0 M M 0
-2M -3M -3M M M 0 0 7M

Les coefficients des variables artificielles forment une matrice unitaire I qui est la base
initiale. La rangée de F est divisée en 2 lignes, la première ligne est la première expression de
F (en fonction des variables artificielles) et la seconde ligne qui est la deuxième expression de
F.
Ce tableau présente la première solution admissible c'est-à-dire :
 y3  0 y 4  0 y5  0

Point O(0,0,0)  x1  3.0 x2  4.0

 
Min F  600 y1  1000 y 2  1000y3  0 y 4  0 y5  Mx1  Mx2  7 M
'

En appliquant les critères de la méthode du simplexe pour ce cas c’est la variable y2 qui rentre dans la
base et la variable x1 qui sort de la base. Le pivot est égal à 2 et on transforme ce premier tableau pour
déterminer une autre solution. Comme x1 qui est une variable artificielle et qui sort de la base elle ne
doit plus figurer dans les tableaux à venir.
 Transformation du tableau (recherche d’une autre solution). Le tableau précédent sera
transformé en adoptant les règles suivantes :
Ligne du pivot : On divise la ligne i de la variable qui sort de la base par le pivot.

V. Y1 Y2 Y3 Y4 Y5 X2 bi
V.B.
Y2 1/2 2/2 1/2 -1/2 0/2 0/2 3/2

17
 Chapitre1 : Programmation Linéaire

Pour les autres lignes du tableau qui restent :

Ligne i=2 x2 :
Coefficient multiplicateur Cm=1/2=1/2
V. Y1 Y2 Y3 Y4 Y5 X2 bi
V.B.
X2 Ligne à modifiée 1 1 2 0 -1 1 4
- Cm x Ligne du pivot -1/2x 1 -1/2x 2 -1/2x 1 -1/2x -1 -1/2x 0 -1/2x 0 -1/2x 3
(X1)
Coefficients de la ligne 1/2 0 3/2 1/2 -1 1 5/2
modifiée

1ère ligne de la fonction économique F :

Coefficient multiplicateur Cm=1000/2=500

V. Y1 Y2 Y3 Y4 Y5 X2 bi
V.B.
Ligne à modifiée 600 1000 1000 0 0 M 0
- Cm x Ligne du pivot -500x 1 -500x 2 -500x 1 -500x -1 -500x 0 -500x 0 -500x 3
(X1)
Coefficients de la ligne 100 0 500 500 0 M 1500
modifiée

2ème ligne de la fonction économique F :

Coefficient multiplicateur Cm=-3M/2=-3M/2

V. Y1 Y2 Y3 Y4 Y5 X2 bi
V.B.
Ligne à modifiée -2M -3M -3M M M 0 7M
- Cm x Ligne du pivot 3M/2x1 3M/2x2 3M/2x1 3M/2x-1 3M/2x0 -3M/2x0 3M/2x3
(X1)
Coefficients de la ligne -M/2 0 -3M/2 -M/2 M 0 5M/2
modifiée

18
 Chapitre1 : Programmation Linéaire

Nous obtenons une nouvelle solution donnée par le tableau N°2

Tableau N°2 :
V. Y1 Y2 Y3 Y4 Y5 X2 bi Rapport
V.B. bi/aj
Y2 1/2 1 1/2 -1/2 0 0 3/2 3
X2 1/2 0 3/2 1/2 -1 1 5/2 5/3
F’ 100 0 500 500 0 M 1500
-M/2 0 -3/2M -M/2 M 0 5/2M

Le processus de la méthode du simplexe continue c’est la variable y3 qui rentre dans la

base et la variable x2 qui sort de la base. Le pivot est égal à 3/2 et on transforme ce tableau
pour déterminer une autre solution. Comme x2 qui est une variable artificielle et qui sort de la
base elle ne doit plus figurer dans les tableaux à venir.
 Transformation du tableau (recherche d’une autre solution). Le tableau précédent sera
transformé en adoptant les règles suivantes :
Ligne du pivot : On divise la ligne i de la variable qui sort de la base par le pivot. Nous
obtenons :

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Y3 1/3 0 1 1/3 -2/3 5 /3

Pour les autres lignes du tableau qui restent :

Ligne i=2 x2 :
Coefficient multiplicateur Cm=1/2/3/2=1/3
V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Y2 Ligne à modifiée 1/2 1 1/2 -1/2 0 3/2
- Cm x Ligne du pivot -1/3x1/2 -1/3x 0 -1/3x 3/2 -1/3x 1/2 -1/3x -1 -1/3x 5/2
(X2)
Coefficients de la ligne 1/3 1 0 -2/3 1/3 2/3
modifiée

19
 Chapitre1 : Programmation Linéaire

Lignes de la fonction économique :

Première ligne : Cm=1000/3

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
1ère ligne de 100 0 500 500 0 1500
F’ à modifiée
- Cm x Ligne -1000/3x1/2 -1000/3x 0 -1000/3x 3/2 -1000/3x 1/2 -1000/3x -1 -1000/3x 5/2
du pivot (X2)
Coefficients -200/3 0 0 1000/3 1000/3 7000/3
de la ligne
modifiée

Deuxième ligne : Cm=-3/2Xm/3/2=-M

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
1ère ligne de F -M/2 0 -3/2M -M/2 M 5/2M
à modifiée
- Cm x Ligne -Mx-1/2 -Mx 0 -Mx 3/2 -Mx -1/2 -Mx -1 -Mx 5/2
du pivot (X2)
Coefficients 0 0 0 0 0 0
de la ligne
modifiée

Nous obtenons une nouvelle solution donnée par le tableau N°3.

Tableau N°3 :

20
 Chapitre1 : Programmation Linéaire

V. Y1 Y2 Y3 Y4 Y5 bi Rapport
V.B. bi/aj
Y2 1/3 1 0 -2/3 1/3 2/3 2
Y3 1/3 0 1 1/3 -2/3 5/3 5
F’ -200/3 0 0 1000/3 1000/3 7000/3
0 0 0 0 0 0

Le processus de la méthode du simplexe continue c’est la variable y1 qui rentre dans la

base et la variable y2 qui sort de la base. Le pivot est égal à 1/3 et on transforme ce tableau
pour déterminer une autre solution. Transformation du tableau (recherche d’une autre
solution). Le tableau précédent sera transformé en adoptant les règles suivantes :
Ligne du pivot : On divise la ligne i de la variable qui sort de la base par le pivot. Nous
obtenons :

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Y1 1 3 0 -2 1 2

Pour les autres lignes du tableau qui restent :

Ligne i=2 y2 :
Coefficient multiplicateur Cm=1/3/1/3=1

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Y2 Ligne à modifiée 1/3 0 1 1/3 -2/3 5/3
- Cm x Ligne du pivot -1x1/3 -1x 1 -1x 0 -1x -2/3 -1x 1/3 -1x 2/3
(Y2)
Coefficients de la ligne 0 -1 1 1 -1 1
modifiée

Ligne de la fonction économique:

21
 Chapitre1 : Programmation Linéaire

Coefficient multiplicateur Cm=-200/3/1/3=-200

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Ligne de F à modifiée -200/3 0 0 1000/3 1000/3 7000/3
- Cm x Ligne du pivot 200x1/3 200x 1 200x 0 200x -2/3 200x 1/3 200x 2/3
(Y2)
Coefficients de la ligne 0 200 0 200 400 2200
modifiée

Nous obtenons une nouvelle solution donnée par le tableau N°4.

Tableau N°4 :

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Y1 1 3 0 -2 1 2
Y3 0 -1 1 1 -1 1
F’ 0 200 0 200 400 2200

Arrêt du processus : Dans le cas de ce P.L. nous constatons que, dans la rangée de la fonction
économique, les coefficients des variables hors base y2, y2 et y5 sont positifs (minimisation) et
donc le processus doit s’arrêter et la solution optimale atteinte. Cette solution est :

 y1  2 y2  0 y3  1
  F '  2200
 y4  0 y5  0

Nous allons maintenant résoudre le programme primal pour pouvoir tirer certaines
conclusions importantes

MaxF   3 x1  4 x2
 x  x  600


1 2

P.L P 2 x1  x2  1000
 x  2 x  1000
 1 2


 1 2 0
x , x 

22
 Chapitre1 : Programmation Linéaire

La forme standard du P.L. est :

1x1  1x2  1x3  0 x4  0 x5  600

aij x j  bi  2 x1  1x2  0 x3  1x4  0 x5  1000
 x  2 x  0 x  0 x  1x  1000
 1 2 3 4 5

et F  Max3 x1  4 x2  0 x3  0 x4  0 x5 

Avec :
x1, x2 : variables principales (inconnues du problème)
x3, x4, x5: variables d’écart (variables de base)
Le processus de la méthode du simplexe étant déjà bien expliqué nous donnons à titre
d’information les différents pour aboutir à la solution optimale.
Tableau N°1 :

V. X1 X2 X3 X4 X5 bi
V.B.
X3 1 1 1 0 0 600
X4 2 1 0 1 0 1000
X5 1 2 0 0 1 1000
F 3 4 0 0 0 0

Tableau N°2 :

V. X1 X2 X3 X4 X5 bi
V.B.
X3 1/2 0 1 0 -1/2 100
X4 3/2 0 0 1 -1/2 1000/3
X2 1/2 1 0 0 1/2 1000
F 1 0 0 0 -2 2000

Tableau N°3 :

23
 Chapitre1 : Programmation Linéaire

V. X1 X2 X3 X4 X5 bi
V.B.
X1 1 0 2 0 -1 200
X4 0 0 -3 1 1 200
X2 0 1 -1 0 1 400
F 0 0 -2 0 -1 2200

La solution optimale (confirmée par la méthode graphique) du P.L. primal est :

 x1  200 x2  400
  F  2200
 x3  0 x4  200 x5  0

Comparaison des solutions du P.L. primal et du P.L. dual : Nous rappelons les deux P.L. leurs
derniers tableaux ainsi que leurs solutions pour pouvoir les comparer.

MaxF   3 x1  4 x2
 x  x  600  
Min F '  600 y1  1000 y 2  1000 y3
 
1 y  2 y 2  1 y 2  3
1 2

P.L P 2 x1  x2  1000 P.L D  1
 x  2 x  1000 1 y1  1 y 2  2 y 2  4
 1 2
y , y , y  0
  1 2 3
 x1 , x2  0

Dernier tableau du P.L. primal

V. X1 X2 X3 X4 X5 bi
V.B.
X1 1 0 2 0 -1 200
X4 0 0 -3 1 1 200
X2 0 1 -1 0 1 400
F Δ1=0 Δ1=0 Δ1=-2 Δ1=0 Δ1=-1 2200

Dernier tableau du P.L. dual

V. Y1 Y2 Y3 Y4 Y5 bi
V.B.
Y1 1 3 0 -2 1 2
Y3 0 -1 1 1 -1 1
F’ Δ’1=0 Δ’2=200 Δ’3=0 Δ’4=200 Δ’5=400 2200

24
 Chapitre1 : Programmation Linéaire

Solution du P.L. primal Solution du P.L. dual

 x1  200 x 2  400  y1  2 y2  0 y3  1
  F  2200   F '  2200
 x3  0 x 4  200 x5  0  y4  0 y5  0

Nous remarquons que :

 Les fonctions économiques des deux P.L. sont égales F = F’

 Les valeurs des variables principales du P.L. primal (x1=200, x2=400) sont égales aux
coefficients des valeurs des variables d’écart dans la ligne de la fonction économique
F’ du P.L. dual (Δ’4=200, Δ’5=400)
 Les valeurs des variables principales du P.L. dual (y1=2, y2=0, y3=1) sont égales (aux
signes prés) aux coefficients des valeurs des variables d’écart dans la ligne de la
fonction économique F du P.L. primal (Δ3=-2, Δ4=0, Δ5=-1)

25