Optimisation des Systèmes Programmation Linéaire

PROGRAMMATION LINÉAIRE

1 Introduction
Un problème de programmation linéaire (PL) ou programme linéaire, traite de la
maximisation ou de la minimisation d’une fonction linéaire en présence de contraintes
linéaires.
Exemple : Max Z = 2.x1 + 6.x2
s.a x1 + x2 ≤ 80
x1 - x2 ≤ 30
-x1 + 4.x2 ≤ 160
x1 ≥ 0 ; x2 ≥ 0
Hypothèses :
• Proportionnalité,
• Additivité,
• Divisibilité.

2 Forme matricielle:
 x1   2
X =  ,C =  
  6 
 x2   
1 1  80 
   
A = 1 −1  , b =  30  ,
   
 −1  160 
 4   
b est appelé Second membre (Right Hand Side (RHS))

 x1 
Maximiser Z =(2 6)  
x 
Max Z = CT.X  2
s.a A.X ≤b 1 1  80 
Ou    x1   
X≥0 ; s.à  1 -1*   ≤  30 
   x2   
 -1
 4     160 

 x1  ≥ 0
avec  
 
 x2 

© M. Daoud AIT-KADI Page 1/34

Optimisation des Systèmes Programmation Linéaire

(
A= a1 a2 ) avec a1 vecteur colonne 1  a1 
 
 
1 1 A =  a2  avec a1 vecteur ligne 1
   
 
a1 =  1  ; a2 =  -1
     a3 
 -1 4 a1 = (1 1) ; a2 = (1 −1) ; a3 = (−1 4)

3 Forme Standard d’un PL :

 Contraintes d' égalité Max Z = CT.X

 s.a A.X =b
SM ≥0 (SM : second membre) ou
 X≥0 ;
 Variables ≥0

N.B :
• forme canonique d’un programme linéaire (contraintes d’inégalité).
• Pour passer d’une forme canonique à une forme standard, on introduit des variables
d’écart.
Exemple : Soit le programme linéaire (P1)
Forme canonique du problème (P1) :
Max Z = 2.x1 + 6.x2
s.a x1 + x2 ≤ 80
x1 - x2 ≤ 30 (P1)
-x1 + 4.x2 ≤ 160
x1 ≥ 0 ; x2 ≥ 0

Forme standard du problème (P1) :

On introduit des variables d’écart pour transformer les inégalités en égalités :
Max Z = 2.x1 + 6.x2
s.a x1 + x2 + x3 = 80 (1)
x1 - x2 + x4 = 30 (2)
-x1 + 4.x2 + x5 = 160 (3)
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x5≥ 0;

© M. Daoud AIT-KADI Page 2/34

Optimisation des Systèmes Programmation Linéaire

• Si une variable xj est libre, pour ramener le problème à sa forme standard, on effectue
la transformation suivante :
xj = x+j – x -j avec x+j ≥ 0; x -j ≥0.

Exemple : Soit le programme linéaire (P2)

Forme canonique du problème (P2) :
Max Z = 2.x1 + 6.x2
s.a x1 + x2 ≤ 80
x1 - x2 ≤ 30 (P2)
-x1 + 4.x2 ≤ 160
x1 ≥ 0 ; x2 libre

Forme standard du problème (P2) :

On effectue la transformation suivante : x2 = x+2 – x -2
On introduit des variables d’écart pour transformer les inégalités en égalités :
Max Z = 2.x1 + 6. x+2 – 6x -2
s.a x1 + x+2 – x –2 + x3 = 80
+ –
x1 - x2 +x 2 + x4 = 30
+ –
-x1 + 4 x 2 – 4x 2 + x5 = 160
x1 ≥ 0; x+2 ≥ 0; x -2≥ 0;x3≥ 0; x4≥ 0; x5≥ 0;

N.B :

 x1 x2+ x2− x3 x4 x5 
 
1 1 −1 1 0 0
 
1 −1 1 0 1 0
 
 −1 4 −4 0 0 1 


Non inversible

Les variables x+2 et x–2 ne peuvent jamais être toutes les deux >0 ⇒ elles ne
peuvent jamais être toutes les deux des variables de base.

© M. Daoud AIT-KADI Page 3/34

Optimisation des Systèmes Programmation Linéaire

4 Résolution graphique :

x2
x1 = 0
x2=80

-x1 + 4.x2= 160

(32,48,0,46,0)
x1 -x2= 30
(0,40,40,70,0)

Domaine (55,25,0,0,16)
réalisable
x1 +x2= 80

x1
(0,0,80, 30,160) (30,0,50,0,190)

Droite de l’objectif

x1 = 0 Z =2.x1 +6.x2
x2=-30

• La solution optimale correspond à un point extrême du domaine.

• Chaque point extrême correspond à trois variables positives et deux variables
nulles
 x1 
 
x 
 2
 
X =  x3 
 
 x4 
 
 x5 

VB (variables de VN (variables hors

base : variables >0) base : variables = 0)

© M. Daoud AIT-KADI Page 4/34

Optimisation des Systèmes Programmation Linéaire

• N.B : le nombre de VB correspond au nombre de contraintes.

5 Résolution analytique :

Forme standard du problème (P) :

Max Z = 2.x1 + 6.x2
s.a x1 + x2 + x3 = 80 (1)
x1 - x2 + x4 = 30 (2)
-x1 + 4.x2 + x5 = 160 (3)
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x5≥ 0;
• On génère une solution initiale :
x1 =0 ; x3 = 80
x2 =0 ; x4 = 30
x5 = 160

Variables hors base Variables de base

• On exprime les variables de base ( x3 ; x4 ; x5 ) en fonction des variables hors
base (à partir des contraintes (1), (2), (3))
x3 = 80 - x1 - x2 (1)’
x4 = 30 - x1 + x2 (2)’
x5 = 160 + x1 - 4x2 (3)’

• On remplace dans l’objectif (O) les variables de base par leurs expressions en
fonction des variables hors base, on obtient :
Z = 2.x1 + 6.x2
N.B : l’objectif est actuellement à zéro (en effet, x1 = 0; x2 = 0)

• Test d’optimalité :
Peut-on augmenter Z en augmentant x1 ou x2 ?
Réponse : Oui.
Quelle variable augmenter x1 ou x2 ?
Réponse : on peut choisir x1 ou x2 . Sans perte de généralité, on
choisit la variable affectée du coefficient le plus élevé.
On décide donc d’augmenter x2 .

© M. Daoud AIT-KADI Page 5/34

Optimisation des Systèmes Programmation Linéaire

Question : de combien? (à noter que x1 est maintenue à 0)

Réponse : On reprend les expressions de x3 ; x4 ; et x5) : (1)’,
(2)’, (3)’
x3 = 80 - x1 - x2 (1)’
x4 = 30 - x1 + x2 (2)’
x5 = 160 + x1 - 4x2 (3)’

Si x1 = 0, pour que x3 demeure ≥ 0, la valeur maximale que peut
prendre x2 est 80.

Pour que x4 demeure ≥ 0, avec x1 = 0, on peut augmenter x2 autant
qu’on le désire sans violer la contrainte. Ainsi, x2 n’a pas de limite.

Pour maintenir x5≥ 0, x2 doit être inférieure ou égale à 160/4=40
En récapitulant,
(1)’ x3 ≥ 0 ⇒ x2 ≤ 80/1
(2)’ x4 ≥ 0 ⇒ x2 → +∝ (pas de restriction)
(3)’ x5 ≥ 0 x2 ≤ 160/4 = 40
La contrainte (3)’ est la plus restrictive.
Pour x1 =0, lorsque x2 prend la valeur 40, x3 prend également la valeur 40,
x4 =70 et x5=0.

• Les variables hors base demeurent x1 et x5. Les variables de base deviennent x2, x3
et x4 .
• On exprime les variables de base en fonction des variables hors base :
De la relation (3)’, on exprime x2 en fonction de x1 et de x5 et on
la remplace dans les expressions de x3 et x4.
(3)’ = 40 + x1/4 - x5/4

x2 d’après (1)’ x3 = 80 - x1 - x2
⇒ x3 = 40 - 5/4 x1 + x5/4

d’après (2)’ x4 = 30 - x1 + x2
⇒ x4 = 70 - 3/4 x1 - x5/4

• On remplace x2 dans Z, par son expression en fonction de x1 et de x5 , on obtient :

Z = 2.x1 + 6.x2
Z = 2.x1 + 6.( 40 + x1/4 - x5/4)
⇒ Z = 240 + 7/2 x1 - 3/2 x5
• Test d’optimalité :

© M. Daoud AIT-KADI Page 6/34

Optimisation des Systèmes Programmation Linéaire

Peut-on augmenter Z en augmentant x1 ou x5 ?

Réponse : Oui : si on augmente x1, l’objectif s’améliore.
Question : de combien peut-on augmenter x1?
Réponse : On revient aux expressions des variables de base (x2 ;
x3 et x4 ). On maintient x5 à zéro.
D’après ce qui précède,
x2 = 40 + x1/4 - x5/4 (a)
x3 = 40 - 5/4 x1 + x5/4 (b)
x4 = 70 - 3/4 x1 - x5/4 (c)
(a) n’impose aucune restriction pour x1 .
(b) x3 ≥ 0 ⇒ 5/4x1 ≤ 40 ⇒ x1 ≤ 32.
(c) x4 ≥ 0 ⇒ 3/4x1 ≤ 70 ⇒ x1 ≤ 280/3.
Ainsi, la contrainte (b) est la plus restrictive.
Pour x5 =0, lorsque x1 prend la valeur 32, x2 prend la valeur 48, x3
prend la valeur 0 et x4 prend la valeur 36.

• De nouveau, les variables de base (variables >0) sont :

x1 = 32
x2 = 48
x4 = 36
Les variables hors base sont , x3 et x5.

• On exprime les variables de base en fonction des variables hors base :

De la relation (b), on extrait l’expression de x1 en fonction de des variables
hors base x3 et x5 . On obtient :
(b) ⇒ x1 = 32 - 4/5x3 + x5/5

On remplace x1 par son expression dans les deux autres
contraintes et dans Z. on obtient :

d’après (a) x2 = 40 + x1/4 - x5/4
⇒ x2 = 48 - x3/5 - x5/5

d’après (c) x4 = 70 - 3/4 x1 - x5/4
⇒ x4 = 46 + 3/5 x3 - 2/5x5

Or, Z = 240 + 7/2 x1 - 3/2x5
⇒ Z = 352 - 14/5 x3 - 4/5x5
• Test d’optimalité :

© M. Daoud AIT-KADI Page 7/34

 Optimisation des Systèmes Programmation Linéaire

Peut-on augmenter Z en augmentant x3 ou x5 ?

Réponse : Non.
Donc, la solution optimale est :
x3 =0 x2 = 48 Z=352
x5 =0 x1 = 32
x4 = 46
• vérification :
Pour x2 = 48 et x1 = 32, on a bien Z = 2*32 + 6*48 = 352.

6 Tableau du Simplex
On réécrit le problème P (forme standard) sous la forme suivante :
S.M
1Z - 2.x1 - 6.x2 =0
0Z + x1 + x2 + x3 = 80
0Z + x1 - x2 + x4 = 30
0Z - x1 + 4.x2 + x5 = 160

V.B V.N
x3 = 80 x1 =0
x4 = 30 x2 =0
x5 = 160

Ce qui se traduit par le tableau de simplex suivant :

variables Z x1 x2 x3 x4 x5 Second
de base membre
Fonction
objectif Z 1 -2 -6 0 0 0 0
x3 0 1 1 1 0 0 80
Variables
de base x4 0 1 -1 0 1 0 30
x5 0 -1 4 0 0 1 160

1. On constate que les colonnes du tableau correspondant aux variables de base

contiennent un 1 à la ligne où la variable apparaît et des zéro ailleurs.
2. Le fait de réécrire la fonction objectif sous forme Z -Ψ ( x1; x2; x3 ; x4; x5) fait en
sorte que les coefficients des variables soient multipliés par –1.

© M. Daoud AIT-KADI Page 8/34

Optimisation des Systèmes Programmation Linéaire

Ainsi, l’optimalité sera atteinte lorsque tous les coefficients apparaissant à la ligne
Z du tableau sont tous ≥ 0 (Pour un problème de maximisation).
 Il en résulte que le tableau actuel n’est pas optimal.
La valeur de la fonction objectif : Z = 0.
3. On lit directement les valeurs des variables de base (colonne correspondant au
second membre).

6.1 Variable d’entrée :

On considère les variables hors base et on sélectionne celles ayant le coefficient négatif le
plus élevé (dans la ligne du tableau de simplexe correspondant à la fonction objectif ).
Dans notre cas, c’est la variable x2.
x2 est alors la variable d’entrée.

6.2 Variable de sortie :

Soit y12, y22 et y32 les éléments du vecteur colonne correspondant à la variable x2.
Dans notre cas,
y12 = 1
y22 = -1
y32 = 4
Soit b1, b2 et b3 les coefficients du second membre.
b1 = 80
b2 = 30
b3 = 160
bi
On considère uniquement yi2 > 0, et on calcule les ratios θ i = , i =1,2,3 . Ainsi, on a :
yi2
b1 80
θ1 = = = 80
y12 1
b3 160
θ3 = = = 40
y32 4
On choisit la variable de base qui correspond au plus petit ratio θi. dans notre cas la
variable correspondant au plus petit ratio est la variable x5.
La case [x5 , x2] correspond au Pivot.
Variable
d’entrée

© M. Daoud AIT-KADI Page 9/34

Optimisation des Systèmes Programmation Linéaire

variables Z x1 x2 x3 x4 x5 Second θi
de base membre
Z 1 -2 -6 0 0 0 0
x3 0 1 1 1 0 0 80 80 = 80
1
x4 0 1 -1 0 1 0 30 ---
x5 0 -1 4 0 0 1 160 160 = 40
4

N.B : Si dans la colonne de la variable d’entrée, les valeurs correspondant aux variables
de base sont toutes négatives, on peut augmenter x2 autant qu’on veut. On dira que le
problème est non borné.

6.3 Transformation du tableau :

Cette transformation consiste à ramener le vecteur colonne
x2 x2

 −6  0
  à  
1 0
   
 −1  0
  Opérations sur  
4 les lignes 1
Ceci est obtenu en ajoutant ou en retranchant à chaque ligne du tableau un multiple de la
ligne du Pivot.

• Transformation de la ligne du pivot : on divise la ligne du pivot par 4.

x5 0 -1 4 0 0 1 160
⇓
x2 0 -1/4 1 0 0 1/4 40

• Transformation de la ligne objectif : on ajoute à la ligne objectif [Link] (Ligne

Pivot).
Z 1 -2 -6 0 0 0 0

© M. Daoud AIT-KADI Page 10/34

Optimisation des Systèmes Programmation Linéaire

+ 6LP
x2 0 -3/2 6 0 0 3/2 240
⇓
Z 1 -7/2 0 0 0 3/2 240

• Transformation de la ligne x3 : on retranche à la ligne x3 [Link].

x3 0 1 1 1 0 0 80
-
LP
x2 0 -1/4 1 0 0 1/4 40
⇓
x3 0 5/4 0 1 0 -1/4 40

• Transformation de la ligne x4 : on ajoute à la ligne x4 [Link].

x4 0 1 -1 0 1 0 30
+
x2 0 -1/4 1 0 0 1/4 40 LP
⇓
x4 0 3/4 0 0 1 1/4 70
• D’où le tableau de simplex suivant :

variables Z x1 x2 x3 x4 x5 Second θi
de base membre
Z 1 -7/2 0 0 3/2 0 240
x3 0 5/4 0 1 0 -1/4 40 40 = 32
5/ 4
x4 0 3/4 0 0 1 1/4 70 70 = 93.3
3/ 4
x2 0 -1/4 1 0 0 1/4 40 ---

Est ce qu’on peut augmenter Z ? Oui, en augmentant x1.

Variable d’entrée x1.
Variable de sortie x3.

• Transformation de la ligne du pivot : on multiplie la ligne du pivot par 4/5.

⇓
x1 0 0 0 4/5 0 -1/5 32

© M. Daoud AIT-KADI Page 11/34

Optimisation des Systèmes Programmation Linéaire

• Transformation de la ligne objectif : on ajoute à la ligne objectif

7/[Link]. ⇓
Z 1 0 0 14/5 0 4/5 352

• Transformation de la ligne x4 : on retranche à la ligne x4 3 LP.

4
⇓
x4 0 0 0 -3/5 1 2/5 46

• Transformation de la ligne x2 : on ajoute à la ligne x2 1 LP.

4
⇓
x2 0 0 1 1/5 0 1/5 48

• D’où le tableau de simplex suivant :

variables Z x1 x2 x3 x4 x5 Second θi
de base membre
Z 1 0 0 14/5 0 4/5 352
x1 0 0 0 4/5 0 -1/5 32
x4 0 0 0 -3/5 1 2/5 46
x2 0 0 1 1/5 0 1/5 48

Est ce qu’on peut augmenter Z ? Non.

Tous les coefficients de la ligne Z sont ≥ 0.
La solution optimale se lit directement du tableau.
x1 = 32 x4 = 46
x2 = 48 x5 =0
x3 =0 Z = 352

1. Le résultat est parfaitement identique à celui obtenu à partir des itérations

effectuées . (Méthode algébrique).
2. Si, à une itération donnée, tous les coefficients yij de la variable d’entrée xj sont
tous (< 0 ) négatifs, on conclut que le problème est non borné. Cela signifie
qu’aucune contrainte ne limite l’augmentation de la variable d’entrée.

© M. Daoud AIT-KADI Page 12/34

Optimisation des Systèmes Programmation Linéaire

3. Si, à une itération donnée, un élément du second membre devient nul, on parlera
de solution dégénérée.

© M. Daoud AIT-KADI Page 13/34

 Optimisation des Systèmes Programmation Linéaire

Les étapes du processus

Forme canonique

Forme standard

Solution initiale

Partitionnement des
variables en

Variables de base (VB) Variables Hors base (VN)

Variables >0 Variables nulles

On exprime les variables de base (VB)

La variable retenue prendra en fonction des variables Hors base en
une valeur >0 et devient se servant des contraintes
variable de base. La première
variable qui était dans la base
et qui devient nulle VN
On effectue les substitutions
dans l’objectif.

Test d’optimalité
Répondre à la question : peut-on améliorer l’objectif en
augmentant une des variables hors base ?

De combien peut-on
augmenter la variable hors Oui Non
base retenue ?
(on utilise les contraintes)
La solution actuelle est
optimale

© M. Daoud AIT-KADI Page 14/34

Optimisation des Systèmes Programmation Linéaire

7 Algorithme du Simplex
L’algorithme du simplex traite les problèmes de PL mis sous la forme standard : [
contraintes d’égalité – variables positives ou nulles – second membre ≥ 0 ]

Minimiser Z = CT.X
s.a A.X = b
X≥0 ;
Ou encore
n
Min Z = ∑C j x j
j =1

n
s .à ∑a x
j =1
ij j = bi ; i =1,2,....m

x j ≥0 ; j =1,2,....n
Ou encore

n
Min Z = ∑C j x j
j =1

n
s .à ∑x a
j =1
j j =b ; j =1,2,....n

x j ≥0 ; j =1,2,....n
a j : vecteur colonne de A correspondant à la variable xj.

Désignons par XB les variables de base et par XN les variables hors base.
 XB 
Le vecteur X est donc partitionné en X = .
 
 XN 
On procède au partionnement correspondant de A et de C :
 CB 
A= [B, N] et C = 
 
 CN 
Le problème original peut alors s’écrire :
 XB 
Minimiser Z = (CB , CN).  
 
 XN 

© M. Daoud AIT-KADI Page 15/34

Optimisation des Systèmes Programmation Linéaire

 XB 
Sujet à : [B, N] .   =b
 
 XN 
XB ≥ 0; XN ≥ 0;

Soit :
Minimiser Z = CB XB + CN XN
Sujet à : B XB + N XN = b
XB ≥ 0; XN ≥ 0;
B étant une matrice régulière [Bmxm], il existe une matrice B-1 (inverse de B) [B-1B = B B-
1
= I].
En multipliant l’ensemble des contraintes par B-1, on obtient :
XB + B-1NXN = B-1b. (1)
d’où XB = B-1b - B-1NXN
XB = B-1b
XN = 0 Est une solution de base

• Si de plus, XB = B-1b ≥ 0, on parlera d’une solution de base réalisable.

• Si, XB = B-1b > 0, on parlera d’une solution de base non dégénérée.

Remarque :
Pour le système AX = b , (Amn), X≥ 0, il existe au plus :
Cmn = n! solutions de base possibles
m! (n-m)!
Ce nombre étant fini, l’algorithme du simplex s’exécuterait alors en un nombre fini
d’itérations.

L’objectif s’écrit :
Minimiser Z = CB XB + CN XN (2)
De la solution (1), on obtient :
XB = B-1b - B-1NXN
En effectuant la substitution dans (2), on obtient :
Z = CB (B-1b - B-1NXN) + CN XN
-1 -1
= CB B b - CB B NXN + CN XN (3)

© M. Daoud AIT-KADI Page 16/34

Optimisation des Systèmes Programmation Linéaire

Or NXN = ∑a X
j∈R
j j R={indice des variables hors base}

Et CN XN = ∑C X
j∈R
j j

La relation (3) s’écrit alors :

Z = CB B-1b - CB B-1 ∑a j X j + ∑C X j j
j∈R j∈R

= CB B-1b - ∑[C B
j∈R
B
−1 aj - Cj] X j (4)

Désignons par :
Z0 = CB B-1b
Zj = CB B-1 a j
La relation (4) devient :
Z = Z0 - ∑(Z
j∈R
j - Cj ) X j (5)

1. Pour le problème de minimisation, si :

∀ j∈R , Zj - Cj ≤0, alors la solution actuelle [XB = B-1b et XN =0 ] est
une solution optimale.
En effet, toute variation positive de Xj (j∈R) entraînerait une augmentation de Z.
L’objectif étant de minimiser Z.

2. Pour un problème de maximisation, si :

∀ j∈R , Zj - Cj ≥ 0, alors la solution en main est une solution optimale.
Toute augmentation de Xj (j∈R) entraînerait une réduction de l’objectif.

3. Si pour une variable Xk (hors base), on a : Zk - Ck >0, alors

Z = Z0 - (Zk - Ck ) Xk
En augmentant Xk (on passe d’une valeur nulle à une valeur positive), on améliore
la valeur Z de l’objectif. (problème de minimisation)

Problème : De combien peut-on augmenter Xk ? [toutes les autres variables hors

base sont maintenues à zéro]
Pour ce faire, on examine les contraintes. On a :
XB = B-1b - B-1 ak X k

© M. Daoud AIT-KADI Page 17/34

Optimisation des Systèmes Programmation Linéaire

 b1' 
 
Soit b’ = B-1b b’=  b2' 
 
 bm' 
 
 y1k 
 
-1  
Et yk= B ak =  y2k 
 
 ymk 
Soit
XB1 = b’1 - y1kXk
XB2 = b’2 - y2kXk
.
.
.
XBr = b’r - yrkXk (6)
.
.
.
XBm = b’m - ymkXk

En augmentant Xk , XBi augmente si yik < 0 ; , XBi diminue si yik >0.

Comme tous les XBi doivent être ≥0, les relations (6) nous permettent d’écrire :
b1I
Xk ≤
y1k
b2I
Xk ≤
y2k
.
. I
X k ≤ bm
ymk
Soit XBr la première variable de base à atteindre zéro quand Xk augmente.

X k = br >0
I
[Pas de dégénérescence]
yrk
 bI 
X k = br = Min  i
I
; yik >0
yrk  yik 
La nouvelle solution devient :
yik br
I
XBi = b’i -
yrk

© M. Daoud AIT-KADI Page 18/34

Optimisation des Systèmes Programmation Linéaire

XBr quitte la base et Xk rentre dans la base.

Remarque :
Si pour Xk B-1 ak <0; [ yik <0], le problème est non borné. [On peut augmenter Xk
autant qu’on veut sans violer la contrainte de non négativité des variables].

Tableau du Simplex :

Variables de base (VB) Variables hors base (VN)

Z xB1 xB2 --- xBm xj --- xk --- S.M

Z 1 0 0 0 0 Zj-Cj Zk-Ck Z0
xB1 0 1 0 --- 0 y1j --- y1k b’1
xB2 0 y2j --- y2k b’2
. . . .
. . . .
xBr 0 yrj --- yrk b’r
. . . .
. . . .
xBm 0 ymj --- ymk b’m

Avec :
Z0 = CB B-1b
Zj = CB B-1 a j

yj = B-1 a j

© M. Daoud AIT-KADI Page 19/34

Optimisation des Systèmes Programmation Linéaire

Les étapes de l’algorithme du Simplex

Générer une première solution de base

réalisable : XB
Soit B la matrice de base correspondante
XB = B-1b ≥ 0 ; Z0 = CB B-1b

Calculer les Zj - Cj pour tout j∈R

Zj = CB B-1 a j
Z = Z0 - ∑(Z
j∈R
j - Cj ) X j

Choisir la variable Xk (k ∈ R) telle que :

Zk - Ck = Max {Z j - C j }
j∈R

Si ∀ j ∈ R; Zj - Cj <0 Stop L’optimum est atteint

Il existe Xk telle que : Calculer yk= B-1 ak

Zk - Ck >0 b’ = B-1b

Oui Problème non borné

yk ≤ 0 ?

Non

 bI 
X k = br = Min  i
I
; yik >0
yrk  yik 

Effectuer le pivotage

© M. Daoud AIT-KADI Page 20/34

Optimisation des Systèmes Programmation Linéaire

8 Génération d’une première solution de base réalisable :

2 méthodes sont disponibles :
1. la méthode des 2 phases
2. la méthode du grand M (membre positif très grand)

Soit le programme linéaire suivant :

Min Z = x1 - 2.x2
s.a x1 + x2 ≥2
-x1 + x2 ≥1 (P)
x2 ≤3
x1 ≥ 0 ; x2 ≥ 0

Forme standard :
Min Z = x1 - 2.x2
s.a x1 + x2 - x3 =2
-x1 + x2 - x4 =1 (P)
x2 + x5 =3
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x5≥ 0;

Notons que pour x1 = 0 et x2 = 0, on a x3 = -2;⇒ pas de solution réalisable

simple. ⇒ On introduit des variables artificielles

Min Z = x1 - 2.x2
s.a x1 + x2 - x3 +xa1 =2
-x1 + x2 - x4 + xa2 =1
x2 + x5 =3
a
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x5≥ 0; x 1≥ 0; xa2≥ 0;

Ainsi, x1 = 0, x2 = 0, x3= 0 et x4= 0, on a xa1=2; xa2 =1 et x5=3.

N.B : La philosophie de cette transformation consiste à gonfler le domaine des solutions

réalisables pour inclure le point (0,0).

© M. Daoud AIT-KADI Page 21/34

Optimisation des Systèmes Programmation Linéaire

8.1 Méthode du grand M :

Exemple : Max Z = 4.x1 + 5.x2
s.a 5.x1 + 4.x2 ≤ 200
3.x1 + 6.x2 =180
8.x1 + 5.x2 ≥ 160
x1 ≥ 0 ; x2 ≥ 0
Problème augmenté :
Max Z = 4.x1 + 5.x2 - M xa2 - M xa3
s.a 5.x1 + 4.x2 + x3 = 200
3.x1 + 6.x2 + xa2 =180
a
8.x1 + 5.x2 - x4 + x 3 =160
a
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x 2≥ 0; xa3≥ 0;

• Solution initiale :
x1 = 0; x2 = 0; x3 =200; x4 = 0; xa2= 180; xa3 =160;
• Exprimons les variables de base en fonction des variables hors base. Il vient :
x3 = 200 - 5.x1 - 4.x2 (1)
xa2 =180 - 3.x1 - 6.x2 (2)
xa3 =160 - 8.x1 - 5.x2 + x4 (3)
• On remplace dans Z , xa2 et xa3 par leurs expression (2) et (3)
Z =4.x1 +5.x2 - M[180 - 3.x1 - 6.x2] - M [160 - 8.x1 - 5.x2 + x4]
Z =-340 M + (4+11M)x1 +(5+11M).x2 - M .x4
Ou encore :
Z - (4+11M)x1 - (5+11M).x2 + M .x4 = -340 M

variables Z x1 x2 x3 x4 xa 2 x a3 Second θi
de base membre
Z 1 -(4+11M) -(5+11M) 0 M 0 0 -340 M

x3 0 5 4 1 0 0 0 200 200 =50

4
xa 2 0 3 6 0 0 1 0 180 180 =30
6
xa 3 0 8 5 0 -1 0 1 160 160 =32
5

© M. Daoud AIT-KADI Page 22/34

Optimisation des Systèmes Programmation Linéaire

variables Z x1 x2 x3 x4 xa 2 x a3 Second θi
de base membre
1 0 0 M 0 150-10 M
Z − 1 (3+11M) 1 (5+11M)
2 6
x3 0 3 0 1 0 -2/3 0 80 80
3
x2 0 ½ 1 0 0 1/6 0 30 30 =60
1/ 2
xa 3 0 11/2 0 0 -1 -5/6 1 10 10 = 20
11/ 2 11

variables Z x1 x2 x3 x4 xa 2 x a3 Second θi
de base membre
Z 1 0 0 0 -3/11 20 + M 3 +M 1680/M
33 11
x3 0 0 0 1 6/11 -7/33 -6/11 820/11 410/3
x2 0 0 1 0 1/11 8/33 -1/11 320/11 320
x1 0 1 0 0 -2/11 -5/33 2/11 20/11 ---

variables Z x1 x2 x3 x4 xa 2 x a3 Second θi
de base membre
Z 1 0 0 1/2 0 M + 1/2 M 190

x4 0 0 0 11/6 1 -7/18 -1 410/3

x2 0 0 1 -1/6 0 41/198 0 50/3
x1 0 1 0 1/3 0 -2/9 0 80/3

Solution optimale : tous les coefficients de la ligne Z sont ≥ 0.

x*1 = 80/3 x*3 = 0 xa 2 = 0

x*2 = 50/3 x*4 = 410/3 xa 3 = 0

© M. Daoud AIT-KADI Page 23/34

Optimisation des Systèmes Programmation Linéaire

8.2 Méthode des deux phases :

Exemple : Min Z = x1 - 2.x2
s.a x1 + x2 ≥2
-x1 + x2 ≥1 (P)
x2 ≤3
x1 ≥ 0 ; x2 ≥ 0
Transformation :
Min Z = x1 - 2.x2
s.a x1 + x2 - x3 +xa1 =2
a
-x1 + x2 - x4 +x 2 =1
(C)
x2 + x5 =3
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x5≥ 0; xa1≥ 0; xa2≥ 0;

Solution initiale :
VN ( x1 = 0, x2 = 0, x3= 0 et x4= 0), et VB ( xa1=2; xa2 =1 et x5=3.)

8.2.1 Phase I :
On cherche à se débarrasser des variables artificielles, pour ce faire, on résout le
programme linéaire suivant :
Min W = xa1 + xa2

(C)

W >0 W =0 et xa hors base

(Pas de solution) ⇒ solution initiale

Phase II

D’après le système de contraintes (C),

© M. Daoud AIT-KADI Page 24/34

Optimisation des Systèmes Programmation Linéaire

W = xa1 + xa2
=3 - 2.x2, + x3 + x4
la fonction objectif s’écrit alors comme suit :
W + 2.x2, - x3 - x4 =3

D’où le tableau de simplex suivant :

variables W x1 x2 x3 x4 x5 xa 1 x a2 Second θi
de base membre
W 1 0 2 -1 -1 0 0 0 3
xa 1 0 1 1 -1 0 0 1 0 2 2
x a2 0 -1 1 0 -1 0 0 1 1 1
x5 0 0 1 0 0 1 0 0 3 3

variables W x1 x2 x3 x4 x5 xa 1 x a2 Second θi
de base membre
W 1 2 0 -1 1 0 0 -2 1
a
x1 0 2 0 -1 1 0 1 -1 1 ½
x2 0 -1 1 0 -1 0 0 1 1 ---
x5 0 1 0 0 1 1 0 -1 2 2

variables W x1 x2 x3 x4 x5 xa 1 x a2 Second θi
de base membre
W 1 0 0 0 1 0 -2 0 0
x1 0 1 0 -½ ½ 0 1 -1 ½
x2 0 0 1 -½ -½ 0 1 0 3/2
x5 0 0 0 ½ ½ 1 -1 0 3/2

D’où la solution réalisable :

x1 =½
x2 = 3/2
x5 = 3/2

© M. Daoud AIT-KADI Page 25/34

Optimisation des Systèmes Programmation Linéaire

8.2.2 Phase II :
• Elle consiste à résoudre le programme linéaire suivant :
Min Z = x1 - 2.x2
s.a x1 - ½ x3 + ½ x4 = 1/2
x2 - ½ x3 - ½ x4 = 3/2
(C’)
½ x3 + ½ x4 + x5 = 3/2
x1 ≥ 0; x2 ≥ 0; x3≥ 0; x4≥ 0; x5≥ 0;

Ce nouveau système de contraintes (C’) est obtenu à partir du dernier tableau Simplex de
la phase I.
N.B : On remarque la disparition de xa1 et xa2 : ceci est dû au fait qu’elles sont des
variables hors base dans le dernier tableau Simplex de la phase I

• On exprime les variables de Base (VB) en fonction des variables hors base (VN)
x1 =½ x3 =0
x2 = 3/2 x4 =0
x5 = 3/2

x1 =½ + ½ x3 - ½ x4
x2 = 3/2 + ½ x3 + ½ x4
x5 = 3/2 - ½ x3 - ½ x4

⇒ Z = -5/2 - ½ x3 - 3/2 x4

Ainsi, Z + ½ x3 + 3/2 x4 = -5/2

variables Z x1 x2 x3 x4 x5 Second θi
de base membre
Z 1 0 0 ½ 3/2 0 -5/2
x1 0 1 0 -½ ½ 0 ½ 1
x2 0 0 1 -½ -½ 0 3/2 ---
x5 0 0 0 ½ ½ 1 3/2 3

© M. Daoud AIT-KADI Page 26/34

Optimisation des Systèmes Programmation Linéaire

variables Z x1 x2 x3 x4 x5 Second θi
de base membre
Z 1 -3 0 2 0 0 -4
x4 0 2 0 -1 1 0 1 ---
x2 0 1 1 1 0 0 2 ---
x5 0 -1 0 1 0 1 1 1

variables Z x1 x2 x3 x4 x5 Second θi
de base membre
Z 1 -1 0 0 0 -2 -6
x4 0 1 0 0 1 1 2
x2 0 0 1 0 0 1 3
x3 0 -1 0 1 0 1 1

L’optimalité est atteinte.

La solution optimale :
x1 * = 0 x2 * = 3 x3 * = 1
x4 * = 2 x5 * = 0
Z* = -6

On vérifie bien que pour x1 = 0 et x2 = 3, on a Z = 0 – 2*3 = -6.

8.3 Théorème:
Si à l’optimum (tableau final du Simplex), une ou plusieurs variables artificielles
demeurent dans la base avec des valeurs positives alors le programme original est non
réalisable.
Dans la méthode des 2 phases, si à l’optimum, W>0, le problème original est non
réalisable.

© M. Daoud AIT-KADI Page 27/34

Optimisation des Systèmes Programmation Linéaire

9 Théorie de la dualité :

9.1 Introduction
A chaque programme linéaire dit primal (P), on associe un autre programme linéaire dit
dual (D).
Les relations entre le primal et le dual se sont révélées extrêmement utiles pour plusieurs
applications particulièrement dans l’analyse de sensibilité.
Cette analyse de sensibilité est très importante étant donné que les valeurs des paramètres
utilisés dans le modèle sont des estimations et leur impact sur la solution optimale doit
être examiné.

9.2 Illustration du problème:

Une entreprise fabrique des tables et des chaises. Elle utilise 2 essences de bois B1 et B2.
Le directeur de production dispose des données suivantes :
B1 B2 # heures ouvrables Profit
(Pieds/unité) (Pieds/unité) par unité ($/unité)
Tables 5 2 4 12
Chaises 2 3 2 8
Ressources 150 pi 100 pi 80
disponibles

Problème: Déterminer le nombre optimal de tables et de chaises à fabriquer.

Primal
• Soit:
x1: nombre de tables à fabriquer.
x2: nombre de chaises à fabriquer.
• Modèle mathématique :
Maximiser Z = 12.x1 + 8.x2
s.a 5.x1 + 2.x2 ≤ 150 (Bois B1)
2.x1 + 3.x2 ≤ 100 (Bois B2)
4.x1 + 2.x2 ≤ 80 (heures ouvrables)
x1 ≥ 0 ; x2 ≥ 0 (non négativité des variables)

Dual
Supposons qu’un acheteur soit intéressé par les ressources dont dispose l’entreprise qui
fabrique les tables et les chaises.

© M. Daoud AIT-KADI Page 28/34

Optimisation des Systèmes Programmation Linéaire

L’objectif de l’acheteur est de déterminer les prix unitaires y1 ,y2,et y3 qui minimise le
coût total d’acquisition des ressources disponibles.
Min W = y1*150 + ,y2*100 + y3 *80
Par ailleurs, l’acheteur est parfaitement conscient que l’entreprise ne peut lui céder les
ressources qu’à condition que le prix offert soit supérieur ou égal au profit unitaire que
l’entreprise réaliserait en transformant ses ressources en produits finis. D’où les
contraintes suivantes :
5.y1 + 2y2 + 4.y3 ≥ 12
2.y1 + 3y2 + 2.y3 ≥ 8
y1 ≥ 0 ; y2 ≥ 0; y3 ≥ 0;

Primal Dual
 x1   150 
Max Z = (12 8)    
  Min W = ( y1 y2 y3 )  100 
 x2   
 80 
5 2  150   
   x1   
s.à : 2 3    ≤  100   y1 
 
   x2    5 2 4    12 

4
 2     80  s.à :   y ≥ 
2 2     8 
2
 3
x1 ≥ 0 ; x2 ≥ 0  y3 
y1 ≥ 0 ; y2 ≥ 0; y3 ≥ 0;
Variable Contrainte
Max Min
Min Max

A tout problème primal, on associe un problème Dual.

Max Z = CTX Min W = YTb

s.à : AX ≤ b s.à : ATY ≥ C
X≥0 Y≥0

Min Z = CTX Max W = YTb

s.à : AX ≥ b s.à : ATY ≤ C
X≥0 Y≥0

© M. Daoud AIT-KADI Page 29/34

Optimisation des Systèmes Programmation Linéaire

Exemple :
Minimiser Z = 6.x1 + 8.x2
s.a 3.x1 + x2 ≥4 (1)
5.x1 + 2.x2 ≤ 10 (2)
x1 + 2.x2 =3 (3)
x1 ≥ 0 ; x2 ≥ 0
Question : Écrire ce problème sous forme duale !!!!
Solution :

On écrit le problème sous sa forme primale (classique –
systématique).
Pour ce faire, on transforme la contrainte (3) de la manière suivante :
 x1 + 2x2 ≥ 3
x1 + 2.x2 =3⇔ 
− x1 − 2x2 ≥ -3
Le primal s’écrit alors :
Minimiser Z = 6.x1 + 8.x2
s.a 3.x1 + x2 ≥4 (1)’
5.x1 + 2.x2 ≤ 10 (2)’
x1 + 2.x2 ≥3 (3)’
- x1 - 2.x2 ≥-3 (3)’’
x1 ≥ 0 ; x2 ≥ 0

Maintenant, on peut écrire la forme duale.

Primal Dual
 x1   4 
Min Z = (6 8)    
   -10 
 x2  Max W =( y1 y2 y3 y4 )  
 3 
3 1  4   
   
 −5 −2   x1   -10   -3 
s.à :   ≥ 
1 2   x2   3   y1 
 
     
 −1 −2   -3  3 −5 1 −1   y2   6 
s.à :    
x1 ≥ 0 ; x2 ≥ 0 1   ≤ 
 −2 2 −2   y3   8 
 
 y4 
y1 ≥ 0 ; y2 ≥ 0; y3 ≥ 0; y4 ≥ 0;

© M. Daoud AIT-KADI Page 30/34

Optimisation des Systèmes Programmation Linéaire

Ainsi, le problème dual se présente comme suit :

Max W = 4y1 -10y2 + 3.y3 - 3.y4
s.à : 3.y1 - 5y2 + y3 - y4 ≤ 6
y1 - 2y2 + 2.y3 - 2.y4 ≤ 6
y1 ≥ 0 ; y2 ≥ 0; y3 ≥ 0; y4 ≥ 0;

9.3 Relations entre Primal et Dual :

Ici le primal est un problème de minimisation
Théorème : Si X est réalisable pour le Primal et si Y est réalisable pour le
Dual, alors :
CTX ≥ YTb

A l’optimum
Primal CTX CTX = YTb

Dual YTb

Corollaire :
Si X est réalisable pour (P),
Si Y est réalisable pour (D),
Si CTX = YTb alors :
X est optimal pour (P)
Et Y est optimal pour (D)

Théorème : (complémentarité des écarts):

Si X* est optimal pour (P),
Et Y* est optimal pour (D), alors :
T T
C X* = Y* b
Théorème :

Si à l’optimum une contrainte du primal (P) est non saturée, alors la
variable correspondante du dual (D) est nulle.

Si une variable du primal est positive strictement (>0), alors la
contrainte correspondante du dual est saturée.

Si le primal est non borné alors le dual est non réalisable

© M. Daoud AIT-KADI Page 31/34

Optimisation des Systèmes Programmation Linéaire

9.4 Algorithme du Simplex Dual :

(Primal : Min Z = CT.X , A.X≥ b , X ≥ 0 )
Étape 1 : (initialisation)
• Trouver une base B telle que Zj - Cj ≤0, ∀ j∈R ,
• Aller à l’étape 2
Étape 2 :
• Si B-1b ≥ 0 ⇒ terminer ⇒ L’optimum est atteint
• Sinon choisir b’r = Min {b'i } et Aller à l’étape 3.
1≤ i ≤ m

Étape 3 :
• Si b’rj ≥ 0 ∀ j∈R ⇒ Stop : le dual est non borné et le primal est non
réalisable.
Z k - Ck Z - Cj 
• Sinon choisir k tel que : = Min  j , yrj <0  et aller à l’étape 4.
yrk j∈R
 yrj 
Étape 4 :
• Effectuer le pivotage autour de yrk et aller à l’étape 2.

Z x1 x2 --- xj --- xk --- xn Second

membre
Z 1 Z1-C1≤0 Z2-C2≤0 --- Z1-C1≤0 --- Zk-Ck≤0 --- Zn-Cn≤0
XB1 b’1
XB2 b’2
.
.
XBr --- yrj yrk <0 yrn b’r
.
.
XBm b’m

Exemple :
Minimiser Z = 2.x1 + 3.x2 + 4.x3
s.a x1 + 2.x2 + x3 ≥3
2.x1 - x2 + 3x3 ≥4
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0

© M. Daoud AIT-KADI Page 32/34

Optimisation des Systèmes Programmation Linéaire

Forme standard :
Minimiser Z
s.a : Z - 2.x1 - 3.x2 - 4.x3 =0
- x1 - 2.x2 - x3 + x4 =-3
-2.x1 + x2 - 3x3 + x5 =-4
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0 ; x4 ≥ 0 ; x5 ≥ 0

variables Z x1 x2 x3 x4 x5 Second
de base membre
Z 1 -2 -3 -4 0 0 0
x4 0 -1 -2 -1 1 0 -3
x5 0 -2 1 -3 0 1 -4
Min { -2/-2 ; -4/-3} = 1 ⇒ la variable d’entrée est x1

variables Z x1 x2 x3 x4 x5 Second
de base membre
Z 1 0 -4 -1 0 -1 4
x4 0 0 -5/2 ½ 1 -1/2 -1
x1 0 1 -1/2 3/2 0 -1/2 2

variables Z x1 x2 x3 x4 x5 Second
de base membre
Z 1 0 0 -9/15 -8/5 -1/5 28/5
x2 2/5
x1 11/5

x1 = 11/5 y*1 = 8/5

x2 = 2/5 y*2 = 1/5
Z* = 28/5 W = 28/5

A partir d’un tableau du simplex dual, on obtient la solution optimale du primal et du

dual.

© M. Daoud AIT-KADI Page 33/34

Optimisation des Systèmes Programmation Linéaire

TABLE DES MATIÈRES

1 Introduction................................................................................................................. 1
2 Forme matricielle:....................................................................................................... 1
3 Forme Standard d’un PL :........................................................................................... 2
4 Résolution graphique : ................................................................................................ 4
5 Résolution analytique : ............................................................................................... 5
6 Tableau du Simplex .................................................................................................... 8
6.1 Variable d’entrée :............................................................................................... 9
6.2 Variable de sortie : .............................................................................................. 9
6.3 Transformation du tableau : .............................................................................. 10
7 Algorithme du Simplex............................................................................................. 15
8 Génération d’une première solution de base réalisable : .......................................... 21
8.1 Méthode du grand M :....................................................................................... 22
8.2 Méthode des deux phases : ............................................................................... 24
8.2.1 Phase I :..................................................................................................... 24
8.2.2 Phase II : ................................................................................................... 26
8.3 Théorème: ......................................................................................................... 27
9 Théorie de la dualité : ............................................................................................... 28
9.1 Introduction....................................................................................................... 28
9.2 Illustration du problème:................................................................................... 28
9.3 Relations entre Primal et Dual : ........................................................................ 31
9.4 Algorithme du Simplex Dual :.......................................................................... 32

© M. Daoud AIT-KADI Page 34/34