Exercices corrigés de Branch and cut

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).

branch and cut Gomory cutting plane

Branch and cut / Gomory cutting plane

Exercice 1

Considérons le programme linéaire suivant :

Branch and cut Gomory cutting plane

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 :

Branch and cut Gomory cutting plane

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 :

Branch and cut Gomory cutting plane

Nous créons une nouvelle variable d’écart pour cette nouvelle contrainte ce qui donne le dictionnaire suivant :

Branch and cut Gomory cutting plane

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 :

Branch and cut Gomory cutting plane

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 :

Branch and cut Gomory cutting plane

Ce qui donne une nouvelle variable d’écart x_6 :

Branch and cut Gomory cutting plane

Après application du simplexe dual (x_6 est forcé de sortir et x_5 rentre) nous obtenons le résultat suivant :

Branch and cut Gomory cutting plane

Notons que cela ne résout toujours pas notre problème !

Partager
fr_FRFR
%d blogueurs aiment cette page :