Geek or not

Accueil du site > MOCA > Flot maximal sur un réseau de transport

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 6 avril 2006.
6832 personnes ont affiché cette page et sa popularité est de 48.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Flot maximal sur un réseau de transport

Problème particulier de transport

1. Enoncé du problème

Soit le tableau suivant traduisant les coûts pour chaque unitée transférée entre les sources $(A,B,C)$ et les puits $(1,2,3,4,5)$ :

	1	2	3	4	5	$a_i$
A	4	1	2	6	9	100
B	6	4	3	5	7	120
C	5	2	6	4	8	120
$c_{ij}$	40	50	70	90	90

Où :

$a_i$ sont les quantités disponibles
$b_j$ sont les demandes
$x_{ij}$ sont les quantités de l’origine $i$ à la destination $j$
$n$ le nombre de destinations
$m$ le nombre d’origines
$\sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j$
$\text{Min } z = \sum\limits_{i=1}^m \sum\limits_{j=1}^n x_{ij} c_{ij}$
$\sum\limits_{i=1}^n x_{ij} = a_i$ pour $i=1,2,...,n$
$\sum\limits_{i=1}^m x_{ij} = b_i$ pour $j=1,2,...,m$


Graphe du problème d’ordonnancement particulier d’ordonnancement

Le problème est que l’on souhaiterait améliorer le coût global dans ce graphe.

2. Algorithme du Stepping Stone

Méthode : 1. Rechercher une solution de base
2. Améliorer la solution de base

1. Recherche d’une solution de base

On assouvit les besoins des destinations en utilisant source après source.

	1	2	3	4	5
A	40	50	10			100
B			60	60		120
C				30	90	120
	40	50	70	90	90

Dans cette configuration $z = 1550$ , et voici le schéma illustrant cette configuration :


Illustration de la solution de base de l’algorithme du Stepping Stone

2. Amélioration de la solution de base
(a) calculer les coûts marginaux notés $\delta_{ij}$ pour chaque liaison non-affectée
(b) Si tous les $\delta_{ij}$ sont positifs ou nuls $\Rightarrow$ Fin
Sinon, prendre le cycle de substitution $\mu$ associé au $\delta_{ij}$ le plus petit

soit $\mu^{-}$ l’ensembles des arcs du cycle $\mu$ représentant les liaisons sur lesquelles la quantité transportée est diminuée.
$q = \text{min} \left[ x_{ij} \right]$ avec $(i,j) \in \mu^{-}$
$x_{ij} = x_{ij} - q$ pour $(i,j) \in \mu^{-}$
$x_{ij} = x_{ij} + q$ pour $(i,j) \in \mu^{+}$

Application de l’algorithme :

La méthode de détermination des coûts marginaux de l’algorithme est très graphique, il faut prendre toutes les lignes non utilisées avec la solution de base déterminée en 1, et pour chacune d’elle essayer de faire passer une unité sur celle-ci tout en préservant l’équilibre originel du graphe. A titre d’exemple, si l’on prends la liaison $(A,4)$ , elle n’est pas utilisée dans la solution de base, nous allons donc essayer de faire passer une unité dessus. Les modifications apportées dans le tableau sont donc :

	1	2	3	4	5
A			-1	+1		100
B			+1	-1		120
C						120
	40	50	70	90	90

Puis après, on détermine les coûts marginaux en additionnant un à un les coûts que les changements engendrent (voir le calcul de $\delta_{A4}$ ).

Détermination des coûts marginaux :

$\delta_{A4} = (+1)*6 + (-1)*2 + (-1)*5 + (+1)*3 = 2$
$\delta_{A5} = (+1)*9 + (-1)*2 + (+1)*3 + (-1)*5 + (+1)*4 + (-1)*8 = 1$
$\delta_{B1} = 1$
$\delta_{B2} = 2$
$\delta_{B5} = -2 \leftarrow$ minimal
$\delta_{C1} = 1$
$\delta_{C2} = 1$
$\delta_{C3} = 4$

On détermine maintenant le cycle de substitution de $\delta_{B5}$ :
$\mu = \lbrace B5, C5, C4, B4 \rbrace$
$\mu^{-} = \lbrace C5, B5 \rbrace$
$\mu^{+} = \lbrace B5, C4 \rbrace$
$q = min( x_{C5}, x_{B4} )$
$=min(90,60)$
$=60$

On détermine donc les modifications à effectuer au final :
$x_{C5} = 90 - 60 = 30$
$x_{B4} = 60 - 60 = 0$
$x_{B5} = 0 + 60 = 60$
$x_{C4} = 30 + 60 = 90$

On obtient donc le schéma suivant et le tableau suivant :


Illustration de la première optimisation de l’algorithme du Stepping Stone

	1	2	3	4	5
A	40	50	10			100
B			60		60	120
C				90	30	120
	40	50	70	90	90

On retourne maintenant à l’étape 1 de l’algorithme :
Calcul des coûts marginaux $\delta_{ij}$ :

$\delta_{A4} = 4$
$\delta_{A5} = 3$
$\delta_{B1} = 1$
$\delta_{B2} = 2$
$\delta_{B4} = 2$
$\delta_{C1} = -1$
$\delta_{C2} = -1$
$\delta_{C3} = 2$

on détermine maintenant le cycle de substitution $\mu$ correspondant à $\delta_{C1}$ :

$\mu = \lbrace C1,A1,A3,B3,B5,C5 \rbrace$
$\mu^{+} = \lbrace C1,A3,B5 \rbrace$
$\mu^{-} = \lbrace A1,B3,C5 \rbrace$
$q = min( x_{A1},x_{B3}, x_{C5} )$
$=min(40,60,30)$
$=30$

On détermine donc les modifications à effectuer au final :
$x_{C1} = 0+30=30$
$x_{A3} = 10+30=40$
$x_{B5} = 60+30=90$
$x_{A1} = 40-30=10$
$x_{B3} = 60-30=30$
$x_{C5} = 30-30=0$