III.2.5.3. La Forme Standard
Certaines techniques de résolution des programmes
linéaires nécessitent de transformer les inégalités
subsistants dans les systèmes de contraintes en égalités.
On obtient alors la forme standard du programme linéaire. On peut
remplacer les inéquations par les équations en introduisant une
variable non négative appelée variable d'écart,
notée ti, qui mesure l'écart existant entre le deuxième
membre et le premier membre de la contrainte
D'une manière générale si l'on a
On peut transformer le système d'inéquation en
un système d'équation en introduisant les variables
d'écarts ti affectées d'un (+1), que l'objectif soit un minimum
ou un maximum. On aura
82
De la même manière suivante :
Lorsqu'on introduit des variables d'écart dans toutes
les inéquations des systèmes des contraintes, on obtient un
programme qui convient au total n+m variables, les Xj (j = 1,2,... n) et les
Xn+i (i = 1,2, ..., m). Dans un tel programme linéaire, on a
m contraintes et n+m variables. Dans la fonction économique, ces
variables d'écart seront accompagnées d'un coefficient nul. Quel
que soit l'objectif, car elles représentent des écarts ou marges
ou encore des bénéfices incertains de production fictives (dans
le cadre de fabrication par exemple). Il est utile de savoir que certaines
autres techniques de résolution des programmes linéaires
(notamment l'algorithme du simplexe) nécessitent, pour démarrer
les interactions, une première résolution de base qui soit
admissible. Lorsque, dans la forme canonique les contraintes sont
tournées dans le sens =, On obtient la forme standard introduisant les
variables d'écarts affectées d'un signe négatif. Le
système d'équations qui en découlent ne pourra jamais
donner une solution de base admissible à la forme standard en
introduisant des variables d'écarts et des variables artificielles.
Les contraintes de type (=) n'admettent point de variables
d'écarts mais seulement de variables artificielles affectées du
signe correspondant à celui du second membre.
Si l'objet est un minimum, les variables artificielles sont
accompagnées d'un coefficient positif M dans la fonction
économique. Si, par contre il s'agit d'une maximisation, las variables
artificielles devront être accompagnées dans la fonction -
objectif d'un coefficient négatif que l'on convient de noter -M avec M
> 0
Exemple : soit un problème de programmation
linéaire écrit sous forme :
|
FORME CANONIQUE
|
FORME STANDARD
|
|
Max Z = 2X1 + 9X2 +X3 Sous les contraintes S/C 2X1 + 2X2 + 10X3 =
10
X1 X3 = 7
X1 + 17X2 + 15X3 = 25 Ex Xj = 0 ; j = 1, 2,3
|
Max Z = 2X1 + 9X2 +X3 +0X4 -MX5 -MX6-MX7 Sous contraintes :
2X1 + 2X2 + 7X3 + X5 = 10
X1 + 3X3 + X6 = 7
X1 + 17X2 + 15X3 - X4 + X7 = 25
Et Xj = 0 (j =1,2,.....7)
|
83
| 
