2.

FORME STANDARD D’UN PROGRAMME LINÉAIRE

Nous avons vu que les contraintes peuvent être écrites sous différentes
formes, ≥,≤ et =.
Ce n’est pas trop pratique d’avoir différents types de contraintes avec des
signes différents, Nous préfèrerons d’avoir une forme standard pour
étudier les problèmes d’un PL.
Dans le chapitre précédent, tous les exemples ont conduit à un problème
mathématique fondamental : l’optimisation d’une fonction linéaire
soumise à un système de contraintes linéaires.
Une complication mineure dans l’étude du problème est que le problème
d’optimisation peut prendre différentes formes. Par exemple, nous avons
vu des problèmes de maximisation et de minimisation et des ensembles
de contraintes qui ont consisté en égalités et inégalités dans les deux
sens. Cependant, cette difficulté est facilement résolue parce que tous les
problèmes de programmation linéaire peuvent être transformés en
problèmes équivalents qui sont dans ce que nous appelons la forme
standard.

C'est cette forme standard du problème de la programmation linéaire, un

problème de minimisation impliquant uniquement les égalités,
que nous allons résoudre.
Ainsi, notre première tâche est de montrer que tout problème de
programmation linéaire peut être formulé comme un problème sous forme
standard, où le nombre d’égalités, m et le nombre de variables, n, sont
déterminés par le problème.
Définition : La forme standard du problème de programmation linéaire
est de déterminer une solution d'un ensemble d'équations :
a 11 x 1 +a 12 x 2+ a13 x 3 +…+ a1 n x n=b 1
a 21 x 1+ a22 x 2 +a23 x3 + …+a2 n x n=b2
.
.
a m 1 x 1+ am 2 x2 + am 3 x 3 +…+ amn xn =bm
Avec x j ≥ 0, j= l,...,n

z=c 1 x1 +c 2 x2 + c3 x 3+ …+c n xn −z 0

(Le terme z 0 permet d'inclure une constante dans l'expression pour que la
fonction soit optimisée. Dans une application, une telle constante pourrait
représenter, par exemple, des coûts fixes ou des avantages garantis. Nous
précédons la constante d'un signe négatif pour l'avenir. la commodité, z 0
peut être positif, négatif ou nul.)
Les contraintes sont données sous forme d’égalité
Ici a ij , c j , b j(i=1 ,m ; j=1 , n) et z 0 une constante donnée.

Chaque fonction peut être écrite sous forme standard

 Transposer tous les PL au forme standard.
Technique 1 : Maximiser z=f (x 1 , x 2)

C’est équivalent au problème de minimiser f en écrivant z=−f (x 1 , x 2)

Contraintes : x 1+ x2 + x 3 ≤10

x 1−x 2 ≥ 5

x1 , x2 , x3 ≥ 0

Comment changer les contraintes en forme standard.

Soit : x≤b avec x ≥ 0
On peut ajouter une quantité ≥0
x + x=b avec x ≥ 0
Cas x≥b avec x ≥ 0
x−x=b avec x ≥ 0
Revenons à notre exemple : x 1+ x 2+ x 3+ x 4=10
x 1−x 2−x 5=5
x1, x2, x3, x 4, x5≥0
Maintenant, les contraintes sont sous forme standard.
Les variables introduites sont appelées variables d’écart. Elles mesurent
l’écart ou le surplus des contraintes originales
Récapitulations :
 Pour toutes inéquation avec ≤, on ajoute une variable d’écart x k
pour changer ≤ à =
 Pour toutes inéquation avec ≥, on ajoute une variable d’écart -x k
pour changer ≥ à =

Avec xk : variables d’écart

Exemple : Convertir en forme standard :

Maximiser : 3. x 1 – 2. x 2 – x 3+ x 4−87
Contraintes : 4. x 1 – x 2 – x 4 ≤ 6
−7. x 1+8. x 2+ x 3 ≥7
x 1+ x 2+4. x 4=12
Avec x1, x2, x3, x 4≥0
Minimiser  −3. x 1+2. x 2+ x 3−x 4+ 87
4. x 1 – x 2 – x 4+ x 5=6
−7. x 1+8. x 2+ x 3+ x 6=7
x 1+ x 2+4. x 4=12
Avec x1, x2, x3, x 4, x5, x6≥0
2.1 Rappel Mathématique :

Exemple 1
Soit le système d’équations linéaires

[ ]
2 x−4 y +2 z=6
x+ y−z=0
− y +3 z=8

Qu’on peut mettre sous forme matricielle :

( )( ) ( )
2−4 2 x 6
.
11−1 y = 0
0−1 3 z 8

Pour résoudre ce système nous allons utiliser la méthode du pivot de

Gauss-Jordan qui permet de mettre la matrice sous forme diagonale.
L’élimination de Gauss-Jordan, aussi appelée méthode du pivot de
Gauss, nommée en hommage à Carl Friedrich Gauss et Wilhelm Jordan,
est un algorithme pour déterminer les solutions d'un système d'équations
linéaires.
Exemple 3x3 :

( )( ) ( )
1 0 0 x ¿a
.
0 1 0 y = b
0 0 1 z c

Méthode du pivot de Gauss

La méthode du pivot de Gauss est une méthode pour transformer un
système en un autre système équivalent (ayant les mêmes solutions) qui
est diagonale et est donc facile à résoudre. Les opérations autorisées pour
transformer ce système sont :
Théorème de Gauss-Jordan Tout système linéaire se ramène à un système
échelonné équivalent en utilisant trois types d’opérations élémentaires :

 Échange de deux lignes. Li ↔ L j

 Remplacer une équation Li par Li + L j .

 Addition d'une ligne à une autre ligne.

Pour que le système ait une solution, il faut que le déterminant de la

matrice soit non nul.
Le choix du pivot est arbitraire, on peut commencer par n’importe quelle
variable.

On choisit de pivoter x1, le coefficient de x1 doit être égale à 1. On divise

la ligne L1 par 2
L 1 L 1/2 : x−2 y + z=3
Puis éliminer les termes en x1 dans les autres équations L2 et L3.
L 2 L 2 – L1 : 0+3 y +2 z=−3
Et L 3 L 3 : le coefficient de x1 dans L3 et nul. – y+ 3 z=8

[ ]
x−2 y + z=3
0+3 y−2 z=−3
0− y +3 z=8

Pivot de y :

L3  L3+L2 : (7/3)z = 7
L 2 L 2/3 : y – (2/3) z=−1

Normalisation de la ligne L3  L3/(7/3) : z = 3

[ ]
x −2 y + z=3
0+ y−(2/3)z=−1
0+0+ z=3

La matrice est diagonale supérieure, faire retour en arrière pour éliminer

les autres coefficients

L2  L2+(2/3)L3
L 1 L 1−L 3 : x – 2y = 0

Puis, L1  L1+ 2L2

:y=1

La dernière étape L1  L1 + 2L2 : x = 2 ; y=1 et z=3

:x=2

Vérification ; 4–4+6=6
2+1–3=0
-1+9=8
Exemple 2 :

[ ]
x 1 +2 x 2 + x 3=4
x1 +2 x 2+ 3 x 3=7
x 1+ x2 + 4 x 3=6

Etape 1 :
On choisit de pivoter x 1 dans l’équation (1)
Le coefficient de x 1 dans (1) doit être égale et 0 dans les deux équations
(2) et (3) :

Ainsi :
(1’)  (1)
(2’)  (2)*(-1)+(2)
(3’)  (3)*(-1)+(3)

[ ]
x1 +2 x 2+ x 3 =4
−2 x 2 + x 3=−1
−x 2 +3 x 3=2

Etape 2 : on va pivoter x 2 dans (2’) :

(1’’)  (1)
(2’’)  (2’)*(-1/2)
(3’’)  (2)*(-1/2)+(3’)

[ ]
x1 +2 x 2+ x 3 =4
1 1
x 2− x 3=
2 2
5 5
x=
2 3 2

Etape 3 : on va pivoter x 3 dans(3’’) :

(3’’’)  (3’’)*(2/5)

{ }
x 1=1
x 2=1
x 3=1

Observations :
Ce que nous faisons ici est essentiel, comment peut-on l’utiliser de
manière plus approfondie ?
 C’est un problème de 3 inconnues avec 3 équations : la solution est
unique
 Le choix du pivot est arbitraire
 En PL, on a généralement plus d’inconnues que d’équations
 Les solutions ne sont plus uniques
 Une procédure similaire (non la même) peut être appliquée à un PL.
2.2 Introduction À La Méthode Simplexe

Considérons le problème de la programmation linéaire sous forme

standard suivant :
Minimiser x 1−x 2+2 x 3−5 x 4=f (x 1 , x 2, x 3 , x 4)
Sujet à x 1+ x 2+2. x 3+ x 4=6
3. x 2+ x 3+8. x 4=3
x1, x2, x3, x 4≥0
Solution : utilisation de la méthode de pivot :
Remarques : le système a 4 variable et seulement 2 équations.
o On choisit x1 comme pivot :
Etape 1 : le coefficient de x1 est 1  pas de changement
Etape 2 : éliminer x1 de la deuxième équation  coefficient déjà nul, pas
de changement
o On va pivoter x2 dans l’équation 2 : rendre le coefficient de x2 égale
à 1 et éliminer x2 de la première équation.
Etape 1 : L2  L2/3 : 0+ x 2+(1 /3) x 3+(8/3)x 4=1
Etape 2 : L1  L1 – (1/3) L2 : x 1+ 0+(5 /3) x 3−(5 /3) x 4=5
Terminologie : Cette forme est appelée forme canonique
x1 et x2 sont appelées variables de base.
x3 et x4 sont appelées variables hors base.
Comment allons-nous interpréter la solution si nous l’avons sous forme
canonique ?
Une façon d’exprimer la solution est de garder les variables de base sur le
côté gauche et de déplacer tout le reste sur le côté droit c.-à-d. écrire les
variables des bases en fonction des variables hors base.
x 1=5 – ((5 /3) x 3−(5 /3) x 4)

x2 = 1- ((1/3)x3 + (8/3)x4)
Une solution particulière à ce système d'équations est évidente :
  Définir les variables non basiques x3 et x4 égales à 0,
x 3=0 et x 4=0
 x1 et x2 égales aux termes constants
x 1=5 et x 2=1.
Le point (5,1,0,0) est une solution pour le problème. On l’appelle
« Solution de base ». Cette solution n'est pas la seule
Dans la forme canonique, une solution particulière est de donner aux
variables hors base une valeur nulle.
Puisque cette solution de base respecte la non négativité des variables,
Cette solution est appelée une « solution de base réalisable » ou
« solution faisable de base ».
Remarque 1 : il y a plusieurs solutions de base
Remarque 2 : toutes les solutions de base, ne sont pas faisables.
Exemple :
Si on choisit x1 et x4 comme pivot :
x 1+(5/8) x 2+(15/8)x 3+0=45/8 (*)
0+(3/8) x 2+(1/8)x 3+ x 4=3 /8 (**)
Ici, l'ensemble de contraintes est représenté par un système d'équations
sous forme canonique avec les variables de base x1 et x4, et la solution de
base associée (45/8,0,0,3/8) est une autre solution réalisable de base.
Pivotons x2 de la première équation ce qui donne le système équivalent :

(*) (*) x (8/5) : ( 85 ) x 1+ x 2+3. x 3=9

−( ) x 1−x 3+ x 4=−3
3
(**)(**)-(*)’x(8/3) :
5

Ce système est sous forme canonique avec les variables de base x2 et x4,
mais la solution de base associée (0,9,0,-3) n’est pas réalisable. La valeur
de x4 est négative.
Évidemment, sélectionner au hasard les variables qui serviront de
variables de base peut conduire à un système d’équations avec des
termes constants négatifs et donc à une solution de base associée qui
n’est pas réalisable.
La question de la faisabilité d’une solution de base, pour deux équations,
peut être posée géométriquement à l’aide des vecteurs colonne associés à
la matrice de coefficients du système d’équations.
Nous voulons une interprétation par la géométrie. On va utiliser des
vecteurs pour représenter le système à deux équations de la manière
suivante :

x1
[ 10]+ x [ 13]+ x [ 21]+ x [ 18]=[63 ]
2 3 4

Ainsi, le système de deux équations et de quatre variables est équivalent

au problème de l’expression du vecteur
6
3 []
sous la forme d’une

combinaison linéaire des vecteurs

1 1 2
,
0 3 1
, et
1
8
. [][][] []
De plus, pour nos besoins, nous sommes limités aux solutions qui
respectent la non négativité de x 1 , x 2 , x 3 et x 4 .
Supposons maintenant que nous souhaitons déterminer géométriquement
si x 1 et x 2 peuvent servir comme variables de base pour une solution de
base réalisable. Si tel est le cas, les variables hors base x 3 et x 4 seront
égales à zéro et l’équation vectorielle résultante se réduit à :

x1
[ 10]+ x [ 13]=[ 63] x , x ≥ 0
2 1 2

Question : ( x 1 , x 2)peuvent-ils utilisés comme variables de base ?

R : oui puisque b est à l’intérieur du cône formé par x 1 et x 2

Q : est-ce ( x 3 et x 4) peuvent-ils aussi utilisés ?

R : Non, ça va donner une solution de base non réalisable.
Q : V 3 b , est ce x 3 peut etre utilisé comme variable de base ?

Une solution de base : x 1=0 ; x 3=3

Les variables hors base x 2=x 4=0

Nous appelons cette situation où une variable de base est égale à 0, une
solution dégénérée. C’est en fait un fauteur de troubles.
Nous revenons maintenant au problème original de programmation
linéaire, mais avec le système de contraintes remplacé par le système
équivalent où x 1 et x 2 sont des variables de base.
x 1+ 0+(5 /3) x 3−(5 /3) x 4=5
0+ x 2+(1 /3) x 3+(8/3)x 4=1
On élimine x 1 et x 2dans la fonction objectif.
Exemple : Minimiser z=x 1−x 2 +2 x 3−5 x 4 avec les contraintes précédentes.
Dans z :

(
Z= 5 –
5
3
5
3 )(1
3
8
x 3+ x 4 − 1− x 3− x 4 +2 x 3−5 x 4
3 )
2 2
Z= x 3− x 4+ 4
3 3
Ça nous donne maintenant un PL
2 2
Minimiser Z= x 3− x 4+ 4
3 3

{ }
5 5
x 1+0+ x 3− x 4=5
3 3
1 8
0+ x 2+ x 3+ x 4=1
3 3
x 1, x 2 , x 3 et x 4 ≥ 0

Programme Linéaire sous forme canonique

Définition :
Le problème de programmation linéaire standard est dite sous forme
canonique avec un ensemble distingué de variables de base si :
(a) Le système de contraintes est en forme canonique avec cet
ensemble distingué de variables de base.
(b) La solution de base associée est réalisable.
(c) La fonction objectif est exprimée en termes de variables hors base.
Si les deux premières conditions de cette définition sont satisfaites pour
un problème de PL, le système de contraintes peut être utilisé, pour
éliminer les variables de base de la fonction objectif.
En organisant et en maintenant un problème sous forme canonique, nous
abuserons un peu du langage et parlerons toujours d'une fonction objectif
fixe.
Certes, dans l'exemple ci-dessus, la fonction z=x 1−x 2+2 x 3−5 x 4 n'est pas
2 2
égale à la fonction z= x 3 – x 4+ 4.
3 3
Cependant, les problèmes d'optimisation de ces fonctions sur l'ensemble
de contraintes donné sont équivalents, c'est-à-dire ont la même valeur
minimale et les ensembles de solutions réalisables sur lesquels cette
valeur optimale commune est atteinte sont les mêmes.
C’est cette équivalence que nous gardons à l’esprit lorsque nous disons,
par exemple, que la fonction objectif est maintenant donnée par :
2 2
z= x 3 – x 4 + 4
3 3