La mise en forme de cet article est à améliorer (avril 2021).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Comment faire ?

Les points d'amélioration suivants sont les cas les plus fréquents :

• Les titres sont pré-formatés par le logiciel. Ils ne sont ni en capitales, ni en gras.
• Le texte ne doit pas être écrit en capitales (les noms de famille non plus), ni en gras, ni en italique, ni en « petit »…
• Le gras n'est utilisé que pour surligner le titre de l'article dans l'introduction, une seule fois.
• L'italique est rarement utilisé : mots en langue étrangère, titres d'œuvres, noms de bateaux, etc.
• Les citations ne sont pas en italique mais en corps de texte normal. Elles sont entourées par des guillemets français : « et ».
• Les listes à puces sont à éviter, des paragraphes rédigés étant largement préférés. Les tableaux sont à réserver à la présentation de données structurées (résultats, etc.).
• Les appels de note de bas de page (petits chiffres en exposant, introduits par l'outil «  Source ») sont à placer entre la fin de phrase et le point final^{[comme ça]}.
• Les liens internes (vers d'autres articles de Wikipédia) sont à choisir avec parcimonie. Créez des liens vers des articles approfondissant le sujet. Les termes génériques sans rapport avec le sujet sont à éviter, ainsi que les répétitions de liens vers un même terme.
• Les liens externes sont à placer uniquement dans une section « Liens externes », à la fin de l'article. Ces liens sont à choisir avec parcimonie suivant les règles définies. Si un lien sert de source à l'article, son insertion dans le texte est à faire par les notes de bas de page.
• La présentation des références doit suivre les conventions bibliographiques. Il est recommandé d'utiliser les modèles {{Ouvrage}}, {{Chapitre}}, {{Article}}, {{Lien web}} et/ou {{Bibliographie}}. Le mode d'édition visuel peut mettre en forme automatiquement les références.
• Insérer une infobox (cadre d'informations à droite) n'est pas obligatoire pour parachever la mise en page.

Pour une aide détaillée, merci de consulter Aide:Wikification.

Si vous pensez que ces points ont été résolus, vous pouvez retirer ce bandeau et améliorer la mise en forme d'un autre article.

Cet article a besoin d’être illustré (mai 2021).

Pour améliorer cet article, des médias (images, animations, vidéos, sons) sous licence libre ou du domaine public sont les bienvenus.
Si vous êtes l’auteur d’un média que vous souhaitez partager, importez-le. Si vous n’êtes pas l’auteur, vous pouvez néanmoins faire une demande de libération d’image à son auteur.

Le problème de flot multi-commodités est un problème de réseau de flot avec plusieurs commodités sur le même graphe, c'est-à-dire qu'il y a plusieurs demandes de flot entre des paires de nœuds source et puits. Ce problème généralise le cadre du problème du flot maximum.

Soit un réseau de flot ${\displaystyle G=(V,E)}$, où chaque arête ${\displaystyle (u,v)\in E}$ a une capacité${\displaystyle \,c(u,v)}$. Soit${\displaystyle \,k}$ le nombre de commodités sur le réseau, on définit ces commodités ${\displaystyle K_{1},K_{2},\dots ,K_{k}}$, tel que ${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$, avec ${\displaystyle \,s_{i}}$ et ${\displaystyle \,t_{i}}$ qui sont respectivement la source et le puits de la commodité ${\displaystyle \,i}$, enfin ${\displaystyle \,d_{i}}$ est la demande de cette commodité. On note${\displaystyle \,f_{i}(u,v)}$ la proportion du flot ${\displaystyle \,i}$ passant par l'arête${\displaystyle \,(u,v)}$. On a${\displaystyle \,f_{i}(u,v)\in [0,1]}$ si le flot est séparé en plusieurs chemins, ${\displaystyle \,f_{i}(u,v)\in \{0,1\}}$ sinon. Le problème de flot multi-commodités consiste à trouver les variables de flot qui satisfont les contraintes suivantes :

(1) Capacité des arêtes : Le flot total sur une arête ne doit pas excéder la capacité de cette arête

${\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v){\dot {d}}_{i}\leq c(u,v)}$

(2) Conservation du flot dans les nœuds intermédiaire : Pour chaque nœud intermédiaire ${\displaystyle u}$, le flot total entrant est égal au flot total sortant.

${\displaystyle \forall i\in K:\,\sum _{w\in V}f_{i}(u,w)-\sum _{w\in V}f_{i}(w,u)=0\quad \mathrm {quand} \quad u\neq s_{i},t_{i}}$où K = [1..k]

(3) Conservation du flot des sources : Chaque source doit émettre tout son flot.

${\displaystyle \forall i\in K:\,\sum _{w\in V}f_{i}(s_{i},w)-\sum _{w\in V}f_{i}(w,s_{i})=1}$

(4) Conservation du flux des puits : Chaque puits doit recevoir tout son flot.

${\displaystyle \forall i\in K:\,\sum _{w\in V}f_{i}(w,t_{i})-\sum _{w\in V}f_{i}(t_{i},w)=1}$

Plusieurs problèmes d'correspondent ont été proposés^{[réf. nécessaire]}.

• Dans le problème d'équilibrage des charges, le but est d'acheminer les flux tels que l'utilisation ${\displaystyle U(u,v)}$ de tous les liens ${\displaystyle (u,v)\in E}$ soit la même. On définit :

${\displaystyle U(u,v)={\dfrac {\sum _{i=1}^{k}f_{i}(u,v)d_{i}}{c(u,v)}}}$.

Le problème peut être résolu en minimisant ${\displaystyle \displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$. Une linéarisation fréquente de ce problème consiste à minimiser l'utilisation maximale ${\displaystyle U_{max}}$, avec

${\displaystyle \forall (u,v)\in E:U_{max}\geq U(u,v)}$.

• Dans le problème de flot multi-commodités minimum, il y a un coût ${\displaystyle a(u,v)f(u,v)}$ à tout envoi de flots sur ${\displaystyle (u,v)\in E}$.

Ensuite, il faut minimiser ${\displaystyle \displaystyle \sum _{(u,v)\in E}(a(u,v)\sum _{i=1}^{k}f_{i}(u,v))}$.

• Dans le problème de flot multi-commodités maximal, la demande de chaque commodité n'est pas fixé, le flot traversant le graphe doit être maximisé en maximisant la somme des demandes ${\displaystyle \displaystyle \sum _{i=1}^{k}d_{i}}$.

Le problème qui consiste à décider si un réseau de flot peut satisfaire toutes les demandes des commodités est NP-complet pour des flots à valeur entière et est dans P pour des flots à valeur fractionnaire.

Le problème de flot multi-commodités permet de modéliser de nombreux problèmes de la vie courante. Il peut par exemple modéliser un réseau ferroviaire où chaque axe a une capacité et plusieurs couples de gares doivent s'échanger de la marchandise. Un autre exemple est la modélisation de réseaux téléphoniques, où chaque liaison a une bande passante maximum et des couples de nœuds veulent s'envoyer une certaine quantité de données.

• Article de Clifford Stein sur ce problème : http://www.columbia.edu/~cs2035/papers/#mcf
• Logiciel résolvant ce problème : https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

• Portail des mathématiques
• Portail de l'informatique théorique