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

Ejercicio 1

Considere el siguiente programa lineal:

Exercices corrigés de Branch and cut branch and cut

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 :

Exercices corrigés de Branch and cut branch and cut

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 :

Exercices corrigés de Branch and cut branch and cut

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

Exercices corrigés de Branch and cut branch and cut

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 :

Exercices corrigés de Branch and cut branch and cut

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 :

Exercices corrigés de Branch and cut branch and cut

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

Exercices corrigés de Branch and cut branch and cut

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

Exercices corrigés de Branch and cut branch and cut

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

 

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: