Approvisionnement (modélisation)

Une société organise le transport de céréales des villes vers les villes .

La disponibilité en tonnes des villes est de
$(val14[$m_k])
$(val26[1;$m_l+1])

Les besoins en tonnes des villes sont de
$(val15[$m_k])
$(val26[$m_l;$val6])

Le tableau suivant donne les capacités de transport, en tonnes, entre les villes :
  $(val15[$m_k])
$(val16[$m_l]) $(val26[$m_l;$m_v])  

On désire modéliser le problème. Pour cela, on introduit un graphe valué avec des capacités. Quelles capacités doit-on mettre sur chaque arête ?


Approvisionnement (résolution)

Une société organise le transport de céréales des villes vers les villes .

La disponibilité en tonnes des villes est de
$(val14[$m_k])
$(val26[1;$m_l+1])

Les besoins en tonnes des villes sont de
$(val15[$m_k])
$(val26[$m_l;$val6])

Le tableau suivant donne les capacités de transport, en tonnes, entre les villes :
  $(val15[$m_k])
$(val16[$m_l]) $(val26[$m_l;$m_v])  

On a modélisé le problème par le graphe valué avec capacités suivantes. Déterminer les quantités à transporter de chaque ville d'origine vers chaque ville d'arrivée pour satisfaire au mieux la demande totale.

$val21 $val46

  $(val15[$m_k])
$(val16[$m_l])  

Saturation d'une chaîne

Voici un flot de $(val10[$val7]) à $(val10[$val19]) dans un graphe muni de capacités :

$val17 $val46

Arc $(val10[$(val36[$m_K;1])])$(val10[$(val36[$m_K;2])])
Flot $(val39[$m_K])
Capacité $(val38[$m_K])

Cliquer sur les chaînes qui ne sont pas des chemins :

.

On se demande si le flot peut être amélioré en utilisant $val82 $val75. Pour cela, on calcule pour chacun des arcs la capacité résiduelle :

$(val10[$(val69[$m_v])])$(val10[$(val69[$m_v+1])])

Peut-on améliorer le flot à l'aide de $val75 ? si oui, de combien ? sinon répondre 0.


Saturation d'un chemin

Voici un flot de $(val10[$val7]) à $(val10[$val19]) dans un graphe muni de capacités :

$val17 $val46

Arc $(val10[$(val36[$m_K;1])])$(val10[$(val36[$m_K;2])])
Flot $(val39[$m_K])
Capacité $(val38[$m_K])

Cliquer sur les chemins du graphe :

.

On se demande si le flot peut être amélioré en utilisant $val84 $val75. Pour cela, on calcule pour chacun des arcs la capacité résiduelle :

$(val10[$(val69[$m_v])])$(val10[$(val69[$m_v+1])])

Peut-on améliorer le flot à l'aide de $val75 ? si oui, de combien ? sinon répondre 0.


Construire un flot complet

Le dessin suivant représente un graphe muni de capacités. A vous de construire un flot complet en partant du flot nul. La méthode utilisée ici est de saturer tous les arcs allant de à . La liste de tels arcs est la suivante :

$(val31[$m_H;])

$val16 $(val54[$(val48[$m_step])])

Arc $(val9[$(val35[$m_K;1])])$(val9[$(val35[$m_K;2])])
Flot $(val38[$(val48[$m_step]);$m_K])
Capacité $(val37[$m_K])

L'arc Les arcs $(val31[$m_m;]) , a été saturé. ont été saturés. Il reste encore à examiner les arcs $(val31[$m_H;]) Il ne reste plus que l'arc $(val31[$(val42[$m_step]);]) à examiner.

L'arc $(val31[$(val42[$m_step]);]) est-il saturé ?

Répondre oui ou non. Saturez l'arc $(val31[$(val42[$m_step]);]) en donnant les nouvelles valeurs du flot :
$(val9[$(val28[$(val42[$m_step]);$m_v])])$(val9[$(val28[$(val42[$m_step]);$m_v+1])])


Rendre complet un flot donné

Le dessin suivant représente un flot muni de capacités. Il n'est peut-être pas complet. A vous de le rendre complet. La méthode utilisée ici est de saturer tous les arcs allant de à . La liste de tels arcs est la suivante :

$(val31[$m_H;])

$val16 $(val56[$(val54[$m_step])])

Arc $(val9[$(val35[$m_K;1])])$(val9[$(val35[$m_K;2])])
Flot $(val38[$(val54[$m_step]);$m_K])
Capacité $(val37[$m_K])

L'arc Les arcs $(val31[$m_m;]) , a été saturé. ont été saturés. Il reste encore à examiner les arcs $(val31[$m_H;]) Il ne reste plus que l'arc $(val31[$(val48[$m_step]);]) à examiner.

L'arc $(val31[$(val48[$m_step]);]) est-il saturé ?

Répondre oui ou non. Saturez l'arc $(val31[$(val48[$m_step]);]) en donnant les nouvelles valeurs du flot :
$(val9[$(val28[$(val48[$m_step]);$m_v])])$(val9[$(val28[$(val48[$m_step]);$m_v+1])])


Coupure d'un flot

Calculer la capacité de la coupure $m_leftbrace1 $m_rightbrace1 du flot valué de à représenté ci-dessous :

$val16 $val45
Arc $(val9[$(val35[$m_K;1])])$(val9[$(val35[$m_K;2])])
Flot $(val38[$m_K])
Capacité $(val37[$m_K])


Flot maximal et coupure

Le flot de à représenté ci-dessous est complet (saturé) pour les capacités indiquées :

$val16 $val45
Arc $(val9[$(val35[$m_K;1])])$(val9[$(val35[$m_K;2])])
Flot $(val38[$m_K])
Capacité $(val37[$m_K])

Sa valeur est de .

La capacité minimale des coupures est obtenue pour la coupure suivante (indiquer le sous-ensemble choisi contenant ) et vaut .

La valeur du flot maximal possible est de et le flot représenté


Définition d'un flot

Le dessin suivant représente un flot de à de valeur $val54

$val17 $val47

à condition de bien compléter les valeurs manquantes :

Arc
Flot $(val39[$m_K])
Capacité $(val38[$m_K])


Valeur d'un flot

Le dessin suivant représente un flot de à .

$val16 $val46

à condition de bien compléter le tableau suivant :

Arc
Flot $(val38[$m_K])
Capacité $(val37[$m_K])

La valeur du flot est .