LP : forme canonique et forme standard

Forme canonique et forme standard

Les programmes linéaires suivent certaines règles lors de son écriture. Un programme linéaire qui suit les règles est dit de forme canonique. L’algorithme du simplexe ne peut que s’appliquer sur des programmes linéaires sous la forme canonique.

Forme canonique

Un programme linéaire sous sa forme canonique est :

• Un problème de Maximisation, sous contraintes Inférieure ou égale, dont toutes les variables sont strictement positives.
• Un problème de Minimisation, sous contraintes Supérieure ou égale, dont toutes les variables sont strictement positives.

Si le programme linéaire ne correspond pas à ces critères, il faut transformer les contraintes ou la fonction objectif selon les opérations suivantes :

• max z = – min -z
• x + y ≥ b est équivalent à – x – y ≤ – b
• x + y = b est équivalent à x + y ≥ b, x + y ≤ b

La forme canonique est souvent représenté sous une forme matricielle :

• le vecteur des coefficients de la fonction objectif : c de taille n
• la matrice des coefficients de la partie gauche des contraintes : A de taille m*n
• le vecteur des constantes de la partie droite des contraintes : b de taille m
• le vecteur des variables : x de taille n

Ainsi le programme linéaire suivant :

S’écrit sous la forme suivante :

Forme standard

Pour chaque contrainte inégalité de la forme canonique, nous ajoutons une variable d’écart positive e tel que :

Ax ≤ b ⇔ Ax + e = b, e ≥ 0, ici e est un vecteur de taille m de variables d’écarts.

Ainsi la forme canonique est amené à la forme standard par l’ajout des variables d’écarts dans le vecteur des variables :

• le vecteur des coefficients de la fonction objectif : c de taille n+m (n pour x et m pour e bien que ces dernières ne rentrent pas dans le calcul)
• la matrice des coefficients de la partie gauche des contraintes : Ã de taille m*(n+m), la partie de droite de la matrice étant une matrice Identité de taille m.
• le vecteur des constantes de la partie droite des contraintes : b de taille m
• le vecteur des variables de taille n+m

Certaines inégalités ne permettent pas d’avoir les variables de bases positives. Pour cela il faut rajouter d’autres variables appelées variables d’excès et artificielles.

Voici les règles à suivre pour transformer au mieux le simplexe sous forme standard :

• contraintes « supérieur ou égale » ou « inférieur ou égale avec b négatif » : rendre b positif et ajouter « – variable d’écart + variable artificielle »
• contraintes « égalité » : ajouter « + variable artificielle »
• contraintes « inférieur ou égale avec b positif » : ajouter « + variable d’écart » comme vu précédemment.