Exercices corrigés de Branch and cut

Ejercicio 1

Considere el siguiente programa lineal:

Résoudre par la méthode de Gomory le problème (les deux premières coupes).

Solución

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 !