56
Recherche opérationnelle
On a donc le tableau C :
1
2
3
4
5
2
0
1
1/2
0
-1/2
125
4
0
0
1/2
1
-5/2
75
1
1
0
-1/2
0
3/2
75
0
0
-1/2
0
-1/2
z-325
Tous les gains marginaux des variables hors base sont négatifs : on a donc atteint
l'optimum qui est :
75
=
1
x
125
=
2
x
0
=
3
x
75
=
4
x
0
=
5
x
325
=
Z
Sur la figure 1 du chapitre I, cette solution correspond au sommet B, et l'on retrouve bien
la solution optimale que le raisonnement géométrique nous avait fournie.
2.2. CAS GENERAL. REGLES DU PIVOTAGE
Nous venons de voir sur un exemple simple comment fonctionne l'algorithme du
simplexe et comment on peut, en raisonnant uniquement sur ces combinaisons
d'équations, passer d'un sommet du polyèdre des solutions réalisables à un autre en
améliorant chaque fois la fonction économique.
Nous allons maintenant examiner ce que ces opérations impliquent comme calculs
systématiques dans le cas général. Nous allons supposer que, pour un programme
linéaire quelconque, nous ayons obtenu une solution de base et que nous sachions
obtenir les formules (3), c'est-à-dire (avec les notations précédentes) :