Chapitre 1

Programmation linéaire : Simplexe

Recherche opérationnelle Chapitre 1 Programmation linéaire 1/55

Introduction

La recherche opérationnelle est une discipline dont le but est de

fournir des méthodes pour répondre à un type précis de problème, c’est-
à-dire à élaborer une démarche universelle pour un type de problème
qui aboutit à la ou les solutions les plus efficaces. La particularité
de la recherche opérationnelle est que les méthodes proposées sont des
démarches rationnelles basées sur des concepts et outils mathématiques
et/ou statistiques.

Généralement les démarches proposées par la recherche opérationnelle

peuvent être traduites en programmes informatiques exacte.

Recherche opérationnelle Chapitre 1 Programmation linéaire 2/55

Introduction

La programmation linéaire est un outil très puissant de la recherche

opérationnelle. C’est un outil générique qui peut résoudre un grand nombre
de problèmes. En effet, une fois un problème modélisé sous la forme
d’équations linéaires, des méthodes assurent la résolution du problème de
manière exacte.

Une des méthodes les plus connues pour résoudre des programmes linéaires
en nombre réels est la méthode du Simplexe. En théorie, elle a une
complexité non polynômiale et est donc supposée peu efficace. Cependant,
en pratique, il s’avère au contraire qu’il s’agit d’une bonne méthode.

Recherche opérationnelle Chapitre 1 Programmation linéaire 3/55

Programme linè
èaaire

On cherche à maximiser ou minimiser la fonction objectif :

z = c1 x1 + c2 x2 + . . . + cn xn

où les variables de décision xj vérifiant les m inégalités suivantes appelées

contraintes :


 a11 x1 + a12 x2 + . . . + a1n xn ≤ b1
 a21 x1 + a22 x2 + . . . + a2n xn ≤ b2

.. .. .. ..


 . . . .
am1 x1 + am2 x2 + . . . + amn xn ≤ bm


xi ≥ 0, i = 1, 2, . . . n.

Les coefficients aij , bi et cj sont des réels donnés. Si on cherche le maximum

de z alors cette forme est appelée la forme canonique du programme
linéaire (PL).

Recherche opérationnelle Chapitre 1 Programmation linéaire 4/55

Programme linè
èaaire

On peut écrire le programme linéaire sous la forme matricielle suivante :

Trouver x ∈ Rn qui vérifie

 max (z = c T x)
Ax ≤ b (1)
x ≥0


avec
       
a11 a12 ... a1n x1 b1 c1
 a21 a22 ... a2n   x2   b2   c2 
A= .. .. .. , x = .. , b =  ..  c = ..
       

 . . .   .   .   . 
am1 am2 ... amn xn bm cm

Lorsque les contraintes sont des égalités (=) alors le programme linéaire
est sous forme standard. Chaque PL canonique peut se transformer en
un PL standard et inversement.

Recherche opérationnelle Chapitre 1 Programmation linéaire 5/55

Programme linè
èaaire

Pour passer de la forme canonique à la forme standard on ajout des

variables d’écart aux contraintes. Trouver x ∈ Rn qui vérifie


 max(c1 x1 + c2 x2 + . . . + cn xn )
a11 x1 + . . . + a1n xn + xn+1 = b1




 a21 x1 + . . . + a2n xn + xn+2 = b2

. .. ..
 ..

 . .
 am1 x1 + . . . + amn xn + xn+m = bm



xj ≥ 0, j = 1, 2, . . . n + m


Le PL s’écrit matriciellement
 
x1
  .   
a11 ... a1n 1 0 ... 0  ..  b1
 a21 ... a2n 0 1 ... 0 
 xn
 
  b2 

.. .. .. .. .. ..  = ..

 xn+1
 
 . . . . . .   
 . 
 .
am1 ... amn 0 0 ... 1  .. bm


xn+m

Recherche opérationnelle Chapitre 1 Programmation linéaire 6/55

Exemples de formulations

Exemple 1 : Problème d’économie

Une entreprise fabrique deux produit A et B a partir de trois matériaux

premiers M1 , M2 et M3 . Le stock est M1 = 300, M2 = 400 et M3 = 250.
1 Pour fabriquer 1kg de A il faut 1kg de M1 et 2kg de M2 .
2 Pour fabriquer 1kg de B il faut 1kg de M1 , 1kg de M2 et 1kg de M3 .
La vente d’un kilogramme de A rapporte un profit de 50DH et celle de B
rapporte un profit de 100DH.

Quelles quantités de produits A et B l’entreprise doit fabriquer pour

maximiser son profit?

Recherche opérationnelle Chapitre 1 Programmation linéaire 7/55

Exemples de formulations

Formulation du problème en un PL :

Étape 1 : Identification des variables de décision

Les deux quantités qu’on doit déterminer sont les produits A et B :
o x1 : la quantité inconnue à fabriquer de A
p x2 : la quantité inconnue à fabriquer de B
On vérifie bien qu’on a x1 ≥ 0 et x2 ≥ 0.

Étape 2 : Identification des contraintes

L’entreprise dispose de 300 unités de M1 =⇒ x1 + x2 ≤ 300
L’entreprise dispose de 400 unités de M2 =⇒ 2x1 + x2 ≤ 400
L’entreprise dispose de 400 unités de M3 =⇒ x2 ≤ 250

Recherche opérationnelle Chapitre 1 Programmation linéaire 8/55

Exemples de formulations

Étape 3 : Identification de la fonction objectif

La fonction objectif consiste à maximiser le profit apporté par la fabrication

des deux produits. Les contributions respectives 50 et 100, des deux
variables de décision x1 et x2 sont proportionnelles à leur valeur. La
fonction objectif est donc

z = 50x1 + 100x2

Le programme linéaire (sous forme canonique) est donné comme suit :

max (50x1 + 100x2 )



 x1 + x2 ≤ 300
2x1 + x2 ≤ 400

x ≤ 250
 2


x1 , x2 ≥ 0

Recherche opérationnelle Chapitre 1 Programmation linéaire 9/55

Exemples de formulations

Exemple 2 : 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’oeuvre
et de 440m3 d’eau.
o Un hectare de tomates demande 1 heure de main d’oeuvre, 4m3 d’eau
et donne un bénéfice net de 100 euros.
p Un hectare de piments demande 4 heures de main d’oeuvre, 2m3 d’eau
et donne un bénéfice net de 200 euros.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui
permet pas de cultiver plus de 90 hectares de tomates.

Quelle est la meilleure allocation de ses ressources ?

Recherche opérationnelle Chapitre 1 Programmation linéaire 10/55

Exemples de formulations

Formulation du problème en un PL :

Étape 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 :
q x1 : la surface allouée à la culture des tomates
r x2 : la surface allouée à la culture des piments
On vérifie bien qu’on a x1 ≥ 0 et x2 ≥ 0.

Étape 2: Identification des contraintes

L’agriculteur dispose de 150 hectares de terrain =⇒ x1 + x2 ≤ 150

L’agriculteur ne dispose que de 440 m3 d’eau =⇒ 4x1 + 2x2 ≤ 440
L’agriculteur dispose de 480 heures de main d’oeuvre =⇒ x1 + 4x2 ≤ 480
L’agriculteur ne cultive pas plus de 90 hectares de tomates =⇒ x1 ≤ 90

Recherche opérationnelle Chapitre 1 Programmation linéaire 11/55

Exemples de formulations

Étape 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 est donné comme suit

max (100x1 + 200x2 )



 x1 + x2 ≤ 150
 4x1 + 2x2 ≤ 440


x1 + 4x2 ≤ 480
x 1 ≤ 90




x1 , x2 ≥ 0


Recherche opérationnelle Chapitre 1 Programmation linéaire 12/55

Exemples de formulations

Exercice 1 : 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 composantes :
1 1 Kg d’aliment M contient 100 g de A, 100 g de C , 200 g de D.
2 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 euros le Kg et N coûte 4 euros 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 ?

Recherche opérationnelle Chapitre 1 Programmation linéaire 13/55

Ré
éssolution graphique

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.

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.

Recherche opérationnelle Chapitre 1 Programmation linéaire 14/55

Ré
éssolution graphique

x2
On considère le programme linéaire suivant

min z = x1 + x2
 π1
 2x1 + x2 ≥ 12
 12
5x1 + 8x2 ≥ 74

2x1 +x2 −12=0
 x1 + 6x2 ≥ 24


x1 , x2 ≥ 0 6
3
Étape 1 : (Représentation graphique des x1
0 3 6 9
contraintes) La première contrainte est donnée
par l’inégalité 2x1 + x2 ≥ 12 qui correspond à
un demi-plan π1 (espace hachuré dans la figure)
limité par la droite x2 = 12 − 2x1 .

Recherche opérationnelle Chapitre 1 Programmation linéaire 15/55

Ré
éssolution graphique

Pour les deux autres contraintes du problème on obtient les deux demi-
plans π2 et π3 représentés par les espaces hachurés suivants :

x2 π2 π3
5x1 +8x2 −74=0
9.25
x2 x1 +6x2 −24=0

3 4
x1 x1
6 14.8 24 6 12 24

Il faut également prendre en considération la contrainte x1 , x2 ≥ 0.

Recherche opérationnelle Chapitre 1 Programmation linéaire 16/55

Ré
éssolution graphique

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’autre terme
à π1 ∩ π2 ∩ π3 .

x2

20

Ensemble des
solutions réalisables
10

2x1 + x2 − 12 = 0
5x1 + 8x2 − 74 = 0
x1
x1 + 6x2 − 24 = 0 10 20 30

Recherche opérationnelle Chapitre 1 Programmation linéaire 17/55

Ré
éssolution graphique

Étape 2 : Représentation de la fonction objectif

Soit z la valeur de la fonction objectif

z = x1 + x2

Par exemple pour z = 0 ou z = 6, la fonction objectif est représentée de

la manière suivante :
x2 x2
12
x1 +x2 =6
6 6
x1 +x2 =0
x1 x1
−10 0 10 0 6
−6

−12

Recherche opérationnelle Chapitre 1 Programmation linéaire 18/55

Ré
éssolution graphique

On peut tracer une infinité de droites qui représentent les différentes valeurs
de la fonction objectif, toutes ces droites sont parallèles entre elles. De
plus on peut diminuer la valeur de z dans le sens indiqué dans la figure
ci-dessous.

x2

18
x1
+
x2
=
12
x1

18
+
x2
=
x1

12
+

6
x2
=
6

x1
6 12 18

Recherche opérationnelle Chapitre 1 Programmation linéaire 19/55

Ré
éssolution graphique

On translate la droite de la fonction objectif jusqu’a trouver la limite

inférieure du polygone réalisable qui est une région non bornée.

π1 ∩ π2 ∩ π3
A
8

0 2 10
x1
+
x2
=
10

La valeur minimale est z = 10 elle est atteinte au point A = (x1 , x2 ) =

(2, 8) qui est un point extrême du polygone π1 ∩ π2 ∩ π3 .

Recherche opérationnelle Chapitre 1 Programmation linéaire 20/55

Solution optimale

Un parie S ⊂ Rn est dite convexe si

∀x, y ∈ S, αx + (1 − α)y ∈ S, 0≤α≤1

Un point z d’un ensemble convexe S est appelé point extrême s’il n’existe
pas deux points distincts x et y de S et un nombre α ∈]0, 1[ tels que

z = αx + (1 − α)y .

L’ensemble des solutions réalisables d’un programme linéaire s’il n’est pas
vide est un polyèdre convexe de Rn donc un ensemble qui contient une
infinité de points.

Recherche opérationnelle Chapitre 1 Programmation linéaire 21/55

Solution optimale

Le domaine suivant est un polyèdre (polygone) convexe borné de R2 .

A

B F

D
E
Les points extrêmes de cet ensemble convexe sont A, B, C , D, E , F , et G .

Recherche opérationnelle Chapitre 1 Programmation linéaire 22/55

Solution optimale

Le théorème suivant, dont la preuve nous ne donnons pas, montre que,

si un problème de programmation linéaire a une solution optimale, alors
cette solution est atteinte en un point extrême.

Théorème 1 : (points extrêmes)

Soit S l’ensemble des solutions réalisables d’un PL.
1 Si S n’est pas vide et borné, alors une solution optimale au problème
existe et se produit à un point extr^eme.
2 Si S est non vide et non borné et si une solution optimale au problème
existe, alors cette solution se produit à un point extr^
eme.
3 S’il n’existe pas une solution optimale au problème, alors soit S est
vide ou S est non borné.

Recherche opérationnelle Chapitre 1 Programmation linéaire 23/55

Solutions de base

Considérons le programme linéaire standard suivant:

max z = c T x
ß
Ax = b, x ≥ 0

avec A une matrice pq, c, x ∈ Rq et b ∈ Rp . (p ≤ q)

On appelle matrice de base de A, toute sous matrice carrée B inversible

d’ordre p. Les p variables xj qui corresponds aux p colonnes de B sont
appelées variables de base de B. Alors que les (q − p) autres variables
sont dites variables hors base.

Si A possède une matrice de base identité Ip alors celle-ci est dite matrice
de base évidente de A.

Recherche opérationnelle Chapitre 1 Programmation linéaire 24/55

Solutions de base

Soit B une matrice de base de A et soit x ∗ la solution du système

Bx ∗ = b

On appelle solution de base du système Ax = b , associée à la matrice

B la solution x de dimension q obtenue en faisant augmenter le vecteur
x ∗ par (q − p) composantes nulles.

Une solution de base est dite admissible si toute ces composantes sont
positives.

Une solution de base est dite dégénérée si elle a au moins une variable
de base nulle.

Recherche opérationnelle Chapitre 1 Programmation linéaire 25/55

Solutions de base

Exemple 3 : On considère le système à six variables suivant


 −x1 + x2 + x3 + x4 + x5 = 1 ï ò
−1 1 1 1 1 0
x1 + x2 + 2x3 + 2x4 + x6 = 2 A=
1 1 2 2 0 1
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0


ï ò
−1 1
m B= est une matrice de base de A et on a
1 1
1
ß ß
−x1 + x2 = 1 x1 = 2
=⇒ 3
x1 + x2 = 2 x2 = 2

( 12 , 32 , 0, 0, 0, 0) est une solution de base admissible du système

Ax = b.

Recherche opérationnelle Chapitre 1 Programmation linéaire 26/55

Solutions de base

ï ò
−1 1
m B= est une matrice de base de A et on a
1 2
ß ß
−x1 + x3 = 1 x1 = 0
=⇒
x1 + 2x3 = 2 x3 = 1

(0, 0, 1, 0, 0, 0) est une solution de base admissible du système

Ax = b.
ï ò
−1 0
m B= est une matrice de base de A et on a
1 1
ß ß
−x1 = 1 x1 = −1
=⇒
x1 + x6 = 2 x6 = 3

(−1, 0, 0, 0, 0, 3) est une solution de base non admissible.

Recherche opérationnelle Chapitre 1 Programmation linéaire 27/55

Solutions de base

Théorème 2
Considérons le programme linéaire standard suivant :

max z = c T x
ß
Ax = b, x ≥ 0

Alors x est une solution de base admissible ⇐⇒ x est un point

extrême de l’ensemble des solutions réalisables.

De plus le nombre des solution de base admissibles est fini.

Recherche opérationnelle Chapitre 1 Programmation linéaire 28/55

Mé
étthode de simplexe

Considérons le programme linéaire canonique suivant:

max(z = c1 x1 + c2 x2 + . . . + cn xn )


 a11 x1 + a12 x2 + . . . + a1n xn ≤ b1
 a21 x1 + a22 x2 + . . . + a2n xn ≤ b2

.. .. .. ..


 . . . .
am1 x1 + am2 x2 + . . . + amn xn ≤ bm


xi ≥ 0, i = 1, 2, . . . n.

On suppose dans cette section que le vecteur b est positif

b≥0

c’est-à-dire bi ≥ 0 pour i = 1, . . . , m.

Recherche opérationnelle Chapitre 1 Programmation linéaire 29/55

Mé
étthode de simplexe

La forme standard de ce programme est donnée par :


 max (z = c T x)
Ax = b
x ≥0


Avec cette fois :

c1
 
 
 c2  x1
..  ..
   
a11 ... a1n 1 0 ... 0 
 .

  .


 a21 ... a2n 0 1 ... 0   
cn 

 xn

A=
 
.. .. .. .. .. , c= , x = ,
 
.. 0   xn+1
 . . . . . .  
  


0   .
am1 ... amn 0 0 ... 1  ..
 
  
 .. 
 .  xn+m
0
et b comme avant.

Recherche opérationnelle Chapitre 1 Programmation linéaire 30/55

Mé
étthode de simplexe

Dans la suite nous décrirons les différentes étapes de la méthode de

simplexe appliquée à l’exemple simple suivant:

max (120x1 + 100x2 )


 2x1 + 2x2 ≤ 8
5x1 + 3x2 ≤ 15
x1 , x2 ≥ 0


La forme standard du programme est

max (120x1 + 100x2 )


 2x1 + 2x2 + x3 = 8
5x + 3x2 + x4 = 15
 1
x1 , x2 , x3 , x4 ≥ 0.
On voit bien que le vecteur b = (8, 15) est positif.

Recherche opérationnelle Chapitre 1 Programmation linéaire 31/55

Mé
étthode de simplexe

Étape 1 : Solution de base admissible initiale

La matrice A admet une matrice de base évidente dont les variables de

base sont xn+1 , xn+2 , . . . , xn+m .

La solution de base associée est donnée par

x1 = x2 = . . . = xn = 0 et xn+1 = b1 , xn+2 = b2 , . . . , xn+m = bm

Puisque nous avons supposé que b ≥ 0, alors cette solution est bien une
solution admissible.

Pour notre exemple, il est simple de voir que la solution de base admissible
est la suivante :
x1 = 0, x2 = 0, x3 = 8, x4 = 15

Recherche opérationnelle Chapitre 1 Programmation linéaire 32/55

Mé
étthode de simplexe

Étape 2 : Tableau initial de la méthode du simplexe

v.b x1 x2 x3 x4 b
x3 2 2 1 0 8
x4 5 3 0 1 15
−cj -120 -100 0 0 0
↑
valeur de
l’objectif

La dernière case (colorée) du tableau est la valeur de l’objectif qui est égale
à 0 car les variables de décision sont nulles.

Recherche opérationnelle Chapitre 1 Programmation linéaire 33/55

Mé
étthode de simplexe

En général, le tableau initial est donné par

v.b x1 x2 ... xn xn+1 xn+2 ... xn+m b

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

A ce niveau, le PL est transformé sous forme d’un tableau initial. Ce

tableau contient les contraintes, la fonction objectif avec une solution de
base admissible et la valeur correspondante de l’objectif.

Recherche opérationnelle Chapitre 1 Programmation linéaire 34/55

Mé
étthode de simplexe

Étape 3 : Recherche de pivot

Choix de la colonne pivot (variable entrante) :

G La colonne pivot est définie à partir des coefficients de la fonction

objectif.
G Parmi les coefficients de la ligne objective (dernière ligne du tableau)
on choisit le plus petit coefficient négatif.
G La colonne correspondante est la colonne pivot. La variable
correspondante est dite la variable entrante.

Recherche opérationnelle Chapitre 1 Programmation linéaire 35/55

Méthode de simplexe

Choix de la ligne pivot (variable sortante) :

3 La variable entrante va prendre la place d’une des variables de base,

appelée variable sortante.
bi
3 La ligne pivot est la ligne i telle que (aij > 0) soit positif et
aij
minimal où j est l’indice de la colonne pivot.
3 La variable correspondante à cette ligne est la variable sortante.

Si tous les aij sont négatifs alors le problème est sans solution optimale finie

Recherche opérationnelle Chapitre 1 Programmation linéaire 36/55

Mé
étthode de simplexe

Reprenons notre exemple :

↓
v.b x1 x2 x3 x4 b
x3 2 2 1 0 8
← x4 5 3 0 1 15
−cj -120 -100 0 0 0

x1 : est la variable entrante.

x4 : est la variable sortante.

L’intersection entre la ligne pivot et la colonne pivot s’appelle le pivot(=5).

Signaler la colonne pivot par ↓ et la ligne pivot par ←.

Étape 3 : Réduction du tableau

Si le pivot est égale à un nombre k, multiplier la ligne pivot par k1 .

Recherche opérationnelle Chapitre 1 Programmation linéaire 37/55

Mé
étthode de simplexe

Ajouter des multiples appropries de la ligne pivot à toutes les autres lignes
(incluant la ligne objective) afin de faire apparaı̂tre des zéros sur le reste
de la colonne pivot.
Dans le nouveau tableau remplacer le label de la ligne pivot par la variable
entrante. Le tableau obtenu à partir du pivotage de tableau initial est
donné par :

↓
v.b x1 x2 x3 x4 b
← x3 0 4
5 1 − 25 2
3 1
x1 1 5 0 5 3
−cj 0 -28 0 24 360

x2 : est la variable entrante.

x3 : est la variable sortante.

Recherche opérationnelle Chapitre 1 Programmation linéaire 38/55

Mé
étthode de simplexe

On obtient finalement le tableau suivant

v.b x1 x2 x3 x4 b
5
x2 0 1 4 − 12 5
2
x1 1 0 − 34 1
2
3
2
−cj 0 0 35 10 430

Tous les coefficients de la ligne objective sont positifs. STOP!

La solution optimale est

Å ã
3 5
(x1 , x2 ) = ,
2 2

La valeur optimale de l’objectif est 430.

Recherche opérationnelle Chapitre 1 Programmation linéaire 39/55

Mé
étthode de simplexe

La representation graphique de ce PL est la suivante

x2
5

5
2

12
12

0x 1
0x 1

+
10
+
10

0x 2
0x 2

=
43
=
0

0
x1
0 3 3 4
2

Recherche opérationnelle Chapitre 1 Programmation linéaire 40/55

Mé
étthode de simplexe

Exercice 2 : Résoudre par la méthode du simplexe les programmes

linéaires suivants

max (x1 + 3x2 ) max (8x1 + 9x2 + 5x3 )

 

 2x1 + 6x2 ≤ 30 
 x1 + x2 ≤ 2
x1 ≤ 10 2x1 + 4x3 ≤ 3
 

 x2 ≤ 4 
 −x2 + 2x3 ≤ 8
x1 , x2 ≥ 0 x1 , x2 , x3 ≥ 0
 

Exercice 3 : Résoudre les programmes linéaires des problèmes

d’économie et d’agriculture.

Recherche opérationnelle Chapitre 1 Programmation linéaire 41/55

Mé
étthode de simplexe

La representation graphique du premier PL de l’Exercice 2 est la suivante

x2

A x2 =4
4 2x +
1 6x =
2 30

2 B

x1
0
3 5 10

La valeur optimale est 15 elle est atteinte aux points

Å ã
10
A = (3, 4) et B = 10, .
6

Recherche opérationnelle Chapitre 1 Programmation linéaire 42/55

Algorithme de simplexe géné
én ralisé
ér

Dans la section précédente nous avons limité notre étude à un PL

canonique avec un second membre positif (b ≥ 0). Cela à donné
automatiquement une solution de base admissible évidente.
Dans cette section nous considérons un PL donné sous sa forme générale:

max z = c T x


 a11 x1 + a12 x2 + . . . + a1n xn (≤)(=)(≥)b1
 a21 x1 + a22 x2 + . . . + a2n xn (≤)(=)(≥)b2

.. .. .. ..


 . . . .
am1 x1 + am2 x2 + . . . + amn xn (≤)(=)(≥)bm


xj ≥ 0, j = 1, 2, . . . n.
Ce PL sous forme générale peut être écrit sous sa forme standard avec un
second membre positif (b ≥ 0).

Recherche opérationnelle Chapitre 1 Programmation linéaire 43/55

Algorithme de simplexe géné
én ralisé
ér

Par exemple :
max (2x1 + x2 )  max (2x1 + x2 )
 x1 + x2 ≤ 3  x1 + x2 + x 3 = 3
x1 + 4x2 ≥ 1 =⇒ x1 + 4x2 − x4 = 1 (2)
x1 , x2 ≥ 0 x1 , x2 ≥ 0
 

La solution évidente (0, 0, 3, −1) n’est pas admissible car elle n’est pas
positive.
Pour cela on propose une méthode pour trouver tout d’abord une solution
de base admissible initiale, puis on applique l’algorithme de simplexe
vu précédemment. Cette méthode dite simplexe généralisée (ou bien
méthode à deux phases).
L’idée est d’introduire m variables artificielles temporaires et positifs
notées yi dans chaque contrainte de PL. On obtient le PL suivant :

Recherche opérationnelle Chapitre 1 Programmation linéaire 44/55

Algorithme de simplexe géné
én ralisé
ér


Xn
max (z = c j xj )






 j=1
p
X (3)


 aij xj + yi = bi , i = 1, 2, . . . , m

 j=1

xj ≥ 0, j = 1, 2, . . . , p; yi ≥ 0, i = 1, 2, . . . , m


Pour l’exemple précèdent on aura les contraintes suivantes :


 x1 + x2 + x3 + y1 = 3
x1 + 4x2 − x4 + y2 = 1
x1 , x2 , y1 , y2 ≥ 0


C’est facile de voir que x est une solution de PL d’origine ⇐⇒ [x 0]T

est une solution de PL (3). De plus, une solution de base admissible du
problème est donnée par x = 0, y = b.

Recherche opérationnelle Chapitre 1 Programmation linéaire 45/55

Algorithme de simplexe géné
én ralisé
ér

Phase 1 : Nous allons voir maintenant une méthode (Phase 1) pour

changer cette dernière solution admissible (x = 0, y = b) en une solution
admissible avec y = 0. On obtient ainsi une solution admissible pour le
problème d’origine.

Pour cela on considère le problème auxiliaire suivant :


 Xm
0

(z = yi )



 min

 i=1
Xp


 aij xj + yi = bi , i = 1, 2, . . . , m

j=1



xj ≥ 0, j = 1, 2, . . . , p; yi ≥ 0, i = 1, 2, . . . , m


Ce problème admet la solution de base admissible suivante

(0, 0, . . . , 0, b1 , b2 , . . . , bm )

A l’optimum deux cas peuvent se présenter :

Recherche opérationnelle Chapitre 1 Programmation linéaire 46/55
Algorithme de simplexe géné
én ralisé
ér

o La valeur optimale de l’objectif est non nulle. Dans ce cas le problème

d’origine est sans solution de base admissible.
p La valeur optimale de l’objectif est nulle. Dans ce cas nous avons
obtenu une solution de base admissible au problème d’origine et on
commence la (Phase 2).
Pour mettre en oeuvre la méthode du simplexe pour résoudre le PL
auxiliaire nous supprimons les coefficients associés aux variables de base
dans la fonction objectif. Alors on a
Ñ é
m
X m
X Xp
−z 0 = −yi = aij xj − bi
i=1 i=1 j=1

Puisque min(z 0 ) = − max(−z 0 ) alors le PL auxiliaire devient le problème

de maximisation suivant :

Recherche opérationnelle Chapitre 1 Programmation linéaire 47/55

Algorithme de simplexe géné
én ralisé
ér

 Ñ é
 X m Xp




 − max aij xj − bi

 i=1 j=1
Xp



 aij xj + yi = bi , i = 1, 2, . . . , m
j=1



xj ≥ 0, j = 1, 2, . . . , p; yi ≥ 0, i = 1, 2, . . . , m


Dans le cas où on obtient une solution optimale après la (Phase 1) avec
un objectif égal à zéro, deux cas se présentent :
Tous les variables artificielles sont des variables hors base dans le
tableau final du problème auxiliaire.
Quelques variables artificielles restent dans la base avec évidemment
des valeurs nulles.
Nous discutons seulement le premier cas dans ce chapitre.

Recherche opérationnelle Chapitre 1 Programmation linéaire 48/55

Algorithme de simplexe géné
én ralisé
ér

Reprenons l’exemple (3), le PL auxiliaire est donné par

− max(2x1 + 5x2 + x3 − x4 − 4)

 x1 + x2 + x3 + y1 = 3
x + 4x2 − x4 + y2 = 1
 1
x1 , x2 , y1 , y2 ≥ 0
La solution de base admissible est (x1 , x2 , x3 , x4 , y1 , y2 ) = (0, 0, 0, 0, 3, 1).
La valeur de l’objectif correspondante est -4.

Le tableau initial de la méthode de simplexe est donné par :

↓
v.b x1 x2 x3 x4 y1 y2 b
y1 1 1 1 0 1 0 3
← y2 1 4 0 -1 0 1 1
−cj -2 -5 -1 1 0 0 −4

Recherche opérationnelle Chapitre 1 Programmation linéaire 49/55

Algorithme de simplexe géné
én ralisé
ér

Après le pivotage on obtient le tableau suivant :

↓
v.b x1 x2 x3 x4 y1 y2 b
← y1 3
4 0 1 1
4 1 − 14 11
4
1
x2 4 1 0 − 14 0 1
4
1
4
−cj − 34 0 -1 − 14 0 5
4 − 114

et après un deuxième pivotage

v.b x1 x2 x3 x4 y1 y2 b
3 1
x3 4 0 1 4 1 − 14 11
4
1
x2 4 1 0 − 14 0 1
4
1
4
−cj 0 0 0 0 1 1 0

On vérifie que (0, 14 , 11

4 , 0) est une solution admissible du problème
original.

Recherche opérationnelle Chapitre 1 Programmation linéaire 50/55

Algorithme de simplexe géné
én ralisé
ér

Phase 2 : On suppose que les variables artificielles se trouvent hors base

à la fin de la Phase 1 et que la valeur de la fonction objectif du problème
auxiliaire est nulle.
En supprimant les yi de la solution optimale trouvée, on trouve une solution
de base admissible initiale pour la Phase 2. Le tableau initial de la Phase
2 est celui final de la Phase 1 avec quelques modifications :
Supprimer les colonnes associées aux variables artificielles.
Calculer la nouvelle ligne objective comme suivant : Pour chaque
variable de base dans le tableau final de la Phase 1, annuler le
coefficient cj de la fonction objectif du problème original en ajoutant
des multiples appropriés de la ligne associée à cette variable de base.
Le tableau initial de la Phase 2 est ainsi construit. Appliquer ensuite
l’algorithme de Simplexe.

Recherche opérationnelle Chapitre 1 Programmation linéaire 51/55

Algorithme de simplexe géné
én ralisé
ér

La ligne objective du problème original est

-2 -1 0 0 0

On doit annuler les coefficients des variables de base x2 et x3 qui sont −1

et 0. Il suffit d’en ajouter la ligne qui correspond a la variable x2 .
En supprimant les colonnes qui correspondent aux variables y1 et y2 on
obtient finalement le tableau suivant :
v.b x1 x2 x3 x4 b
3 1 11
x3 4 0 1 4 4
1
x2 4 1 0 − 14 1
4
1
−cj - 74 0 0 - 14 4

En suite on applique la méthode de simplexe.

Recherche opérationnelle Chapitre 1 Programmation linéaire 52/55

Algorithme de simplexe géné
én ralisé
ér

La representation graphique de ce PL est la suivante

x2

2x 1
3

2x 1
+x 2

+x 2
=0

=6
2

x1
0 1 2 3

La valeur optimale est 6 elle est atteinte au point (3, 0).

Recherche opérationnelle Chapitre 1 Programmation linéaire 53/55
Algorithme de simplexe géné
én ralisé
ér

Exercice 4 : Effectuer la Phase 1 de la méthode de simplexe généralisée

pour les PLs suivants :

max (3x1 − 4x3 ) max (2x1 + 3x2 )

 
 2x1 + x2 + 3x3 ≥ 5  2x1 + 3x2 ≤ 6
x1 − x2 + x3 ≥ 1 x1 + x2 ≥ 4
x1 , x2 , x3 ≥ 0 x1 , x2 ≥ 0
 

Exercice 5 : Résoudre le problème des animaux.

Recherche opérationnelle Chapitre 1 Programmation linéaire 54/55

Algorithme de simplexe géné
én ralisé
ér

La représentation graphique du 2ème PL de l’exercice 4 est donnée par :

x2

2x
1 +3
x2
=6
4

x1
+
x2
=
4
2

6
x1
0 3

-2

On voit bien que l’ensemble des solutions réalisables est vide car x1 et x2
doivent être positifs.

Recherche opérationnelle Chapitre 1 Programmation linéaire 55/55