Algorithme du simplex
47
3) Choisir une variable hors base qui doit entrer dans la base.
Comme les coefficients de
dans sont tous les deux positifs, on peut choisir
l'une ou l'autre pour la faire entrer dans la base : l'opération sera toujours intéressante.
Cela dit, le coefficient de
est plus grand que le coefficient de
. On peut
donc penser qu'il est plus intéressant de faire entrer
dans la base. Nous choisirons
donc .
Ce critère, qui consiste à choisir pour entrer dans la base la variable
celle pour
laquelle
est le plus grand possible, s'appelle le premier critère de Dantzig
(mathématicien auquel nous devons l'algorithme du simplexe). Il faut remarquer que ce
critère n'a rien d'absolu : on n'est pas sûr, en l'appliquant systématiquement, d'aller au
plus vite sur la solution optimale. On améliore les chances d'une convergence rapide,
c'est tout.
4) Faire varier la variable entrant dans la base jusqu'à ce qu'une variable de base
s'annule.
On a vu au chapitre précédent que la valeur de la variable entrante annulant juste une
variable de base est, en regard des équations (3)
ij
i
j
t
t
x
min
=
0
0
>
| ij
t
i
On peut retrouver ici ce résultat en utilisant directement les équations (4). En effet, si
varie et si reste nul on a :
450
=
3 2
3
x
x
350
=
2
4
x
x
200
=
2
5
x
x
On voit que si
varie, il ne peut le faire que jusqu'à
, valeur qui annule juste
. Pour cette valeur, est égal à 200, à 50.
On a ainsi retrouvé (5). En effet, ici,
Nous sommes donc passés d'une solution de base à une nouvelle solution de base, qui
est:
(3 variables de base non nulles)
(2 variables hors base nulles).