48
Recherche opérationnelle
Lorsque l'on a choisi la variable hors base entrant dans la base la variable sortant de la
base est donc déterminée par l'indice tel que:
pour
tel que
(6)
Cette condition, qui permet de trouver
est appelée second critère de Dantzig. Ce
critère, contrairement au premier, est absolu : il détermine la variable sortante sans
ambiguïté, sauf si plusieurs indices obéissant à (6), cas que l'on étudiera plus loin.
Le passage que nous avons effectué d'une base
à une autre
a
été particulièrement simple du fait que les équations du P.L étaient sous la forme (3) cidessus (chaque variable de base et exprimées en fonction des variables hors base). En
particulier, pour savoir quelle variable il serait intéressant par la suite de faire entrer dans
la base, il faudrait que la fonction économique soit exprimée uniquement en fonction des
nouvelles variables hors base
Nous allons donc remettre le programme sous la forme (3), avec la nouvelle définition
de , donc de . Théoriquement, rien de difficile à cela : il s'agit d'inversion et de
multiplication de matrices (voir les formules (5) et (6) du paragraphe II du Chapitre I).
En fait, l'opération est encore plus facile que cela et peut se faire uniquement à partir de
combinaisons d'équations du programme linéaire, comme nous allons le voir.
Pour faciliter la compréhension, nous utiliserons la présentation habituellement en
vigueur, dite méthode des tableaux (due à Charnes, Cooper et Hendersen).
5) Remise en forme du programme linéaire.
Reprenons notre exemple, c'est-à-dire le programme linéaire (2) et mettons-le sous la
forme suivante :
1
2
3
4
5
3
1
3
1
0
0
450
4
2
1
0
1
0
350
5
1
1
0
0
1
200
1
2
0
0
0
z
Le grand tableau représente la matrice des contraintes
, si l'on prend les
notations précédentes (à chaque variable est associée une colonne); la colonne de droite
représente le second membre des contraintes.
La ligne du dessous donne les coefficients de la fonction économique.