On va supprimer une seule des équations xi=0; donc cette variable xi va devenir positive et les autres resteront nulles. Donc, il faut choisir une variable à coefficient positif en z.
En choisir une (peut-être celle au coefficient le plus élevé?)
Chaque contrainte avec un coefficient ai,j>0 donne une borne supérieure sur la nouvelle valeur de xi;
Choisir la plus petite de ces bornes; c'est la contrainte qu'il faut rajouter.
Transformer le problème en ``forme standard''.
C'est la forme où les seules contraintes sont que chaque variable est positive ou nulle et des contraintes dans la forme d'équations. La transformation s'effectue en ajoutant une nouvelle variable ``variable d'écart'' pour chaque contrainte d'inéquation:
Par exemple
devient
3x1+2x2+x3 = 30
où x3 est la variable d'écart, contrainte
d'être positive ou nulle.
Cette forme est dite ``forme canonique par rapport à la base''
Parce que chaque contrainte a un seul coefficient non nul
d'une variable de la base et ce coefficient est 1,
la contrainte
(si Ai,s>0)
nous dit que xs ne peut pas être
augmenté au delà de bi/Ai,s;
Choisir une variable xi qui donne le minimum de bi/Ai,s
(entre les variables pour lesquelles il est ).
Tous Ai,s négatifs (pour la valeur choisie de s) veut dire que z est sans borne finie
Si le minimum des bi/Ai,s est nul,
parce que des bi sont nuls, continuer quand même!
Un sommet est donné par plusieurs bases;
Un bon choix de base permettra de s'en sortir.
Une manipulation simple renvoie le système de contraintes
dans la forme canonique par rapport à la nouvelle base.
L'équation de la variable qui sort de la base donne une
équation pour celle qui entre
et permet à mettre
à jour les autres équations et la fonction objective
(opération de ``pivotage'')
Et ainsi de suite...