Cette page présente un exercice corrigé détaillé résolu par l’algorithme de branch and cut (aussi connu sous le nom de Gomory cutting plane).
Exercice 1
Considérons le programme linéaire suivant :
Résoudre par la méthode de Gomory le problème (les deux premières coupes).
Solution
Résolvons le problème relaxé en nombre réel. La solution est :
L’algorithme de Gomory cutting plane prend la variable ayant la partie non entière la plus grande, ici x_1. Nous allons formuler une nouvelle contrainte en considérant seulement les restes fractionnaires de chaque coefficient :
Nous créons une nouvelle variable d’écart pour cette nouvelle contrainte ce qui donne le dictionnaire suivant :
Ce programme est non réalisable, il faut donc faire le simplexe dual. En d’autre terme, nous forçons la sortie de x_5 (ici x_4 rentre), cela donne le dictionnaire suivant :
La solution n’est toujours pas satisfaisante, nous prenons la contrainte avec la plus grande part fractionnaire donc x_2 ce qui donne la coupe (en reste fractionnaire) suivante :
Ce qui donne une nouvelle variable d’écart x_6 :
Après application du simplexe dual (x_6 est forcé de sortir et x_5 rentre) nous obtenons le résultat suivant :
Notons que cela ne résout toujours pas notre problème !
