Une méthode de résolution

Toute solution optimale peut être décrite sous forme d'un arbre, c'est à dire à l'aide d'un graphe comparable à la figure 1.2 sans cycle.

On part d'un arbre solution. La méthode, apparentée à la méthode du simplexe, consiste ensuite à faire entrer une arête et à en faire sortir une autre pour obtenir une meilleure solution.

 

Figure 1.3: Un arbre solution

Le coût de cet arbre est de 1603.

Il faut à présent trouver un arc entrant. Pour cela, on calcul les coûts relatifs des nds du graphe. Notons c[i] le coût du nud i et c(i,j) le coût de l'arc (i,j). On pose c[1] = 0 et on calcule c[i] = c[j] + c(j,i) s'il existe un arc (j,i) et c[i] = c[j] - c(i,j) s'il existe un arc (i,j).

On obtient pour notre exemple :

$$\begin{eqnarray*}c[1] &=& 0\\ c[2] &=& -10\\ c[3] &=& 50\\ c[4] &=& 18\\ c[5] &=& 29\\ c[6] &=& -44\\ c[7] &=& -33\\ \end{eqnarray*}$$

On cherche un arc (i,j) du graphe qui ne se trouve pas dans l'arbre et tel que c[j] > c[i] + c(i,j).

Dans l'exemple l'arc (2,1) vérifie cette propriété : 0 > -10 + 8. On fait donc entrer cet arc.

 

Figure 1.4: L'arc (2,1) entre

Le nouvel arc crée un cycle. On appelle t le futur poids de (2,1). L'apparition de cet arc modifira le poids des arcs du cycle. On additionne t au poids des arcs qui vont dans le même sens que (2,1), et on soustrait t au poids des arcs qui vont dans le sens contraire. On augmente t jusqu'à ce qu'au moins un poids tombe à 0. L'arête sortante est un arc du cycle dont le poids est 0.

Dans notre exemple, t croit jusqu'à 9. L'arc (2,4) sort.

 

Figure 1.5: Le nouvel arbre

On obtient alors un nouvel arbre solution. Le coût de celui-ci est 1585. On a ainsi réalisé une itération de la méthode.

Remarque :
Il y a forcément une arête candidate à la sortie. Supposons par l'arbsurde le contraire. Alors toutes les arêtes du cycle vont dans le même sens. Le graphe du cycle serait comparable à la figure 1.6.

 

Figure 1.6: Le cycle

Dans ce cas c[A] >= c[B], ce qui est une contradiction puisqu'on fait entrer l'arc (A,B) seulement si c[A] < c[B].