Cours Mme BOUKERRAM

Programmation linéaire
Chapitre 3 : Formes canoniques et Standard

INTRODUCTION
Pour résoudre des problèmes de programmation linéaire ayant un nombre de variables
(principales) supérieur à trois, nous devons obligatoirement faire appel à une autre méthode
de résolution que celle déjà étudiée. Toutefois, avant d’aborder la méthode du simplexe comme
technique de résolution d’un problème de programmation linéaire, vous découvrirez dans ce
chapitre une version modifiée – la méthode algébrique - qui permettra d’étudier les différentes
étapes à franchir pour arriver à une solution optimale.
3.1 Forme générale d’un PL
Max(Min)Z  j 1c j x j
n

Sous les contraintes

 a x  b pour i  I  1,..m
n
j 1 ij j i

 a x b pour k  K  1,..m
n
j 1 kj j k

 a x b pour r  R  1,..m
n
j 1 rj j r

l  x  u pour j  1.. n
j j j

Les ensembles I, K, et R sont disjoints, I  K  R = {1…. M} et lj = - et uj = + sont

des valeurs possibles.
3.2 Formes canoniques
3.2.1. Forme canonique de type max
MaxZ  j 1c j x j
n

Sous les contraintes

 a x  b pour i 1,..m
n
j 1 ij j i

x  0 pour j  1.. n
j

 Problème de maximisation
 Toutes les contraintes sont du type «  »
 Toutes les variables sont non négatives (xj >= 0)

3.2.2. Forme canonique de type min

MinZ  j 1c j x j
n

Sous les contraintes

1
Cours Mme BOUKERRAM

 a x  b pour i 1,..m x  0 pour j  1.. n

n
j 1 ij j i j

 Problème de minimisation
 Toutes les contraintes sont du type « »
 Toutes les variables sont non négatives (xj >= 0)
3.3 Forme standard
Max(Min)Z  j 1c j x j
n

Sous les contraintes

 a x  b pour i 1,..m
n
j 1 ij j i

x  0 pour j  1.. n
j

 Problème de maximisation ou minimisation

 Toutes les contraintes sont du type « = »
 Toutes les variables sont non négatives (xj >= 0)
 Le passage de la forme canonique à la forme standard se fait par l’ajout de
variables d’écart qui représente la différence entre le membre gauche et droit de
l’inéquation

3.4 Equivalence des formulations canonique et standard

o Théorème 1. Au prix éventuel de l'ajout de contraintes et/ou de variables,
tout PL peut être transformé en un PL sous forme canonique équivalent.
o Théorème 2. Au prix éventuel de l'ajout de contraintes et/ou de variables,
tout PL peut être transformé en un PL sous forme standard équivalent.

 Par programme équivalent, on entend :

o Toute solution admissible (optimale) du problème équivalent correspond à
une solution admissible (optimale) du problème initial ;
o Toute solution admissible (optimale) du problème initial correspond à au
moins une solution admissible (optimale) du problème équivalent ;
o L'issue de l'optimisation des deux problèmes est la même (sans solution
admissible, optimum fini, problème non borné).
3.5 Variables d’écart
La méthode de résolution que nous étudions dans ce chapitre nécessite que les contraintes du
modèle soient exprimées sous forme d’équations linéaires au lieu d’inéquations. On peut
facilement transformer une inéquation linéaire en une équation linéaire en ajoutant (cas <=)
ou retranchant (cas >=) une variable non négative dite variable d’écart.
La variable d’écart représente l’écart entre la quantité disponible de la ressource i et la quantité
effectivement utilisée par l’ensemble des xi.

2
Cours Mme BOUKERRAM

Inéquation Equation
x1 + x2 + x3 <= 3 Avec x1,x2,x3>=0 x1 + x2 + x3 + e = 3 Avec x1,x2,x3>=0
et e>=0
x1 + x2 + x3 >= 3 Avec x1,x2,x3>=0 x1 + x2 + x3 - e = 3 Avec x1,x2,x3>=0
et e>=0

Remarque : à chaque inéquation, sa variable d’écart pour la transformer en équation

Coefficients des variables d’écart dans la fonction économique (Objectif)
Etant donné que les variables d’écart permettant de mesurer le niveau d’activités fictives alors,
pour qu’elles n’influencent pas l’optimisation, on suppose nuls les bénéfices ou coûts liés à ces
activités. Ainsi, à chaque variable d’écart ei correspondra le coefficient ci = 0 dans la fonction
économique.
Exemple : le restaurateur
Forme canonique de type max Forme Standard
5x1 + x2 <= 30 5x1 + x2 +e1= 30
2x1 + 3x2 <= 24 2x1 + 3x2 +e2= 24
x1 + 3x2 <= 18 x1 + 3x2+e3= 18
x1, x2 >= 0 x1, x2 >= 0 ; e1,e2,e3>=0
Max(Z) = 80x1 + 60x2 Max(Z) = 80x1 + 60x2

3.6 Notation matricielle

Max(Z)CX

Sc AX  B, (AX = B ou A X  0 )

X0
avec

 a11 .. a1n   b1   x1

A  B ..  X  ..  Ct =(c1,…,cn)
 am1...amn     
   bm   xn 

3.7 Règles de transformation particulières

o Minimisation ↔ maximisation : min f(x) = -max ( - f(x))
o Pour minimiser Z = CX, il suffit de maximiser w = -CX = ( -C)X et de
multiplier la valeur optimale de w par -1 pour obtenir celle de Z.
o Inéquation «  » ↔ inéquation «  » :
AX  B ↔ (-A)X  (-B)

o Equation « = » → inéquation «  » :
AX = B ↔ AX  B et AX  B↔ AX  B et (-A)X  (-B)

o Inéquation → Equation : Ajout des variables d’écarts (ei)

3
Cours Mme BOUKERRAM

AX B↔ AX + E = B (E0)

AX  B ↔ AX - E = B (E0)

o Variable libre (réelle) → variable non négative : Tout nombre réel peut être
écrit comme la différence de deux nombres non négatifs.
xR  x= x1 – x2 / x1, x2 0

3.8 Exemples d’application

 Soit le PL mixte suivant :
xi>=0 i=1,2,3
x1 + x2 + x3 <= 3
2x1 + x2 – x3 = 5
x1 + 2x2 –3x3 >= 2
Max(Z)=3x1 + 2x2 + x3
Mettre le PL sous forme standard puis sous forme canonique de type max, puis min.

 Soit le Pl suivant :
x1 >= 0
x1 + 2x2 <= 1
4x1 + 3x2 >= 2
Z(Max) = x1 – 2x2
Mettre sous forme canonique de type max, puis sous forme standard