Flot Max À Coût Min [PDF]

  • 0 0 0
  • Gefällt Ihnen dieses papier und der download? Sie können Ihre eigene PDF-Datei in wenigen Minuten kostenlos online veröffentlichen! Anmelden
Datei wird geladen, bitte warten...
Zitiervorschau

Flot initial = 0 ; C = C restantes min des capacités restantes sur le chemin à moindre coût.

Question 5 (4pt) Utilisez l’algorithme de Busacker et Gowen pour trouver le flot max à coût min du graphe suivant (vous avez le droit de voir les plus courts chemins sans les prouver, et le flot maximal du graphe est de 4 tonnes). Première itération : Le plus court chemin est A → B → D → C → E. Il coûte 40 k euros, et permet un flot de 3 tonnes. On peut donc faire passer un premier flot de 3 tonnes pour un coût global de 40 × 3 = 120 k euros. Reportez le flot trouvé par cette première itération et si le flot max n’est pas atteint calculez le nouveau graphe associé : restante = capacité - flot min des capacités restantes sur le chemin à moindre coût.

Si le flot max n’est pas atteint : Deuxième itération : Le plus court chemin est A → D → B → E. Il coûte 70 k euros, et permet un flot de 1 tonne. On peut donc faire passer un second flot de 1 tonne pour un coût global de 70 × 1 = 70 k euros. La somme des deux premiers flots atteint 4 tonnes, qui est le flot max. Reportez le flot trouvé par cette deuxième itération et si le flot max n’est pas atteint calculez le nouveau graphe associé :

Si le flot max n’est pas atteint : Troisième itération :

Reportez le flot trouvé par cette troisième itération et si le flot max n’est pas atteint calculez le nouveau graphe associé : Eric L ALLET, Jean-Luc R AFFY

17

Quel est le coût minimal du flot maximal ? Réponse : 120 + 70 = 190 k euros. Commentaires : Beaucoup ne tentent même pas de répondre à cette question. Pourtant il y avait au moins 1 point facile à gagner. Le flot max à coût min commence par la recherche du plus court chemin (au sens du coût). Comme on ne vous demande même pas de le prouver, il suffit de le voir et de le dire. – Chaque itération de l’algorithme commence par une recherche du plus court chemin au sens du coût sur le graphe associé. Au sens du coût signifie qu’on fait la somme des coûts de tous les arcs du chemin choisi (qui va de la source au puits) et que celle-ci doit être la plus petite possible. Donc par exemple pour le chemin A → B → E cette somme vaut 10 + 50 = 60. Ce n’est donc pas le plus court chemin (puisque le chemin A → B → D → C → E coûte 10 + 10 + 10 + 10 = 40. Les deux autres A → D → C → E et A → C → E coûtent 50 et 100). – La capacité du chemin retenu (le PCCH) est la plus petite des capacités restantes des arcs du chemin. On ne fait surtout pas la somme des capacités de tous les arcs. – Le coût du flot ajouté est la capacité du chemin multipliée par sa longueur (au sens du coût : donc le coût de tout le chemin), donc ici 3 × 40 = 120. Vous pouvez si voulez faire la somme des «coûts × flot» de tous les arcs du chemin, vous allez trouver le même résultat. Mais attention dans ce cas il faut bien multiplier par le flot que l’ont fait passé, et non pas par la capacité des arcs. Pour le chemin A → B → D → C → E, le flot que l’on peut faire passer était de 3, donc si vous faites arc par arc, cela fait 10 × 3 + 10 × 3 + 10 × 3 + 10 × 3 = 120 (et non pas 10 × 3 + 10 × 5 + 10 × 3 + 10 × 3 = 140 que certains ont calculé). – Après le report du premier flot, l’arc B → D n’est pas saturé (il y a un flot de 3 pour capacité de 5). Donc sur le graphe associé on va trouver deux arcs entre B et D. L’arc direct B → D avec la capacité restante (5-3 = 2) et le coût normal (10), et l’arc inverse D → B avec le flot (3) qui devient sa capacité, et le coût négatif (-10). Beaucoup ont oublié l’arc direct restant (qui n’était pas sur le PCCH de la seconde itération, et qui n’a donc pas gêné les calculs qui suivaient). – Après la second itération, même s’il n’est pas utile de calculer le graphe associé (puisque le flot max est atteint et que l’algorithme est terminé), il faut reporter ce second flot sur le graphe de flot. Sinon vous n’avez toujours pas donné le flot de la solution ! – Enfin, n’oubliez pas de répondre à la question final. Faites la somme des coûts de deux itérations 120 + 70 = 190 kC.

18

Eric L ALLET, Jean-Luc R AFFY