On a un problème de maximisation :
Max f(x1, x2, x3) = 1 x1 + 2 x2 + 3 x3
| sc : x1 + x2 <= 5
| 2 x2 + 5 x3 <= 6
On passe à la forme standard en rajoutant les variables d'écart (e1 et e2), ce qui nous permet de retirer les <= :
Max f(x1, x2, x3) = 1 x1 + 2 x2 + 3 x3
| sc : x1 + x2 + e1 = 5
| 2 x2 + 5 x3 + e2 = 6
e1 et e2 sont en base et ont pour valeurs 5 et 6 respectivement :
| Vars en base \ Vars | x1 | x2 | x3 | e1 | e2 | Rhs |
|---------------------|----|----|----|----|----|-----|
| e1 | 1 | 1 | 0 | 1 | 0 | 5 |
| e2 | 0 | 2 | 5 | 0 | 1 | 6 |
|---------------------|----|----|----|----|----|-----|
| f | 1 | 2 | 3 | 0 | 0 | 0 |
La variable qui entre en base est celle qui a le coef le plus fort dans la fonction de maximisation (f ou z selon les notations), soit x3. On rajoute une colonne pour calculer le critère de Dantzig, CàD la colonne Rhs divisée par la colonne du pivot (la variable qui entre en base) :
| Vars en base \ Vars | x1 | x2 | x3 | e1 | e2 | Rhs | Dz |
|---------------------|----|----|----|----|----|-----|------------|
| e1 | 1 | 1 | 0 | 1 | 0 | 5 | 5/0 -> NaN |
| e2 | 0 | 2 | 5 | 0 | 1 | 6 | 6/5 |
|---------------------|----|----|----|----|----|-----|------------|
| f | 1 | 2 | 3 | 0 | 0 | 0 |
On fait sortir de la base la variable qui a le plus petit coefficient non nul, CàD e2 dans notre cas :
- x3 remplace e2 en base, on veut donc avoir x3 dans les variables à gauche à la place de e2, et dans la colonne de x3, toutes les valeurs sont nulles sauf à la ligne de x3 (car x3 = x3 donc il y a 1 x3 dans x3).
- Pour obtenir 0 dans les autres cases on procède en opérant par lignes ex : dans la ligne de f on a 3 dans x3 donc on lui soustrait 3 fois la ligne x3 du nouveau tableau (ou 3/5 fois la ligne de e2 dans le tableau précédent)
| Vars en \ Vars | x1 | x2 | x3 | e1 | e2 | Rhs |
|------------------|---------|-------------|----|-----|-------------|-------------|
| e1' = e1 | 1 | 1 | 0 | 1 | 0 | 5 |
| x3 = (1/5) * e2 | 0 | 2/5 | 1 | 0/5 | 1/5 | 6/5 |
|------------------|---------|-------------|----|-----|-------------|-------------|
| f' = f - 3 * x3 | 1 - 3*0 | 2 - 3*(2/5) | 0 | 0 | 0 - 3*(1/5) | 0 - 3*(6/5) |
Après calculs :
| Vars en \ Vars | x1 | x2 | x3 | e1 | e2 | Rhs |
|----------------|----|-----|----|----|------|-------|
| e1 | 1 | 1 | 0 | 1 | 0 | 5 |
| x3 | 0 | 2/5 | 1 | 0 | 1/5 | 6/5 |
|----------------|----|-----|----|----|------|-------|
| f | 1 | 4/5 | 0 | 0 | -3/5 | -18/5 |
Maintenant x1 entre en base, on calcule les critères de Dantzig :
| Vars eb \ Vars | x1 | x2 | x3 | e1 | e2 | Rhs | Dz |
|----------------|----|-----|----|----|------|-------|----------------|
| e1 | 1 | 1 | 0 | 1 | 0 | 5 | 5 |
| x3 | 0 | 2/5 | 1 | 0 | 1/5 | 6/5 | (6/5)/0 -> NaN |
|----------------|----|-----|----|----|------|-------|----------------|
| f | 1 | 4/5 | 0 | 0 | -3/5 | -18/5 |
Et e1 sort de la base (plus petite valeur valide de Dz non nulle ou inférieure à zéro) :
| Vars eb \ Vars | x1 | x2 | x3 | e1 | e2 | Rhs |
|----------------|----|------|----|-----|------|-------|
| x1 | 1 | 1 | 0 | 1 | 0 | 5 | Le coef' de x1 dans x3
| x3 | 0 | 2/5 | 1 | 0 | 1/5 | 6/5 | <- était déjà nul, pas besoin
|----------------|----|------|----|-----|------|-------| d'opérer sur cette ligne
| f | 0 | -1/5 | 0 | -1 | -3/5 | -43/5 |
Tous les coefficients dans f sont inférieurs à zéro, on s'arrête.
Les valeurs de x1 et x3 sont dans la colonne Rhs, les autres sont nulles. La valeur de la fonction objectif dans Rhs est l'opposé de sa valeur max.
On reprend :
Max f(x1, x2, x3) = 1 x1 + 2 x2 + 3 x3
| sc : x1 + x2 <= 5
| 2 x2 + 5 x3 <= 6
f(5, 0, 6/5) = 5 + (6/5) * 3 = 25/5 + 18/5 = 43/5 = valeur max
- Dans le cas de la minimisation, on cherche dans f le coef le plus petit et on s'arrête lorsque chaque coef' est nul ou supérieur à zéro.
- Si vous avez des critères de Dantzig tous nuls ou inférieurs à zéro, c'est que le problème n'a pas de solution (ou alors vous avez fait une erreur).