Problème de flux de coût minimum

Le problème de flux de coût minimum ou problème de flux de coût minimum est un problème d' optimisation et de décision de la classe des problèmes de flux de réseau et est une méthode générale de modélisation et de résolution du problème de rechargement ou de transport.Des problèmes de ce genre ont déjà été identifiés Formulé en 1781 par le mathématicien français Gaspard Monge et a reçu une attention accrue lors du réarmement dans la guerre froide en raison de la pertinence militaire de la logistique de transport de fournitures . L'objectif est de déterminer, étant donné une fonction de coût pour le transport de marchandises , l'option la moins chère pour le transport d'un ou plusieurs points de départ (sources) à travers un réseau vers un ou plusieurs points de destination (puits). Selon la structure de la fonction de coût, le problème est qu'il existe des algorithmes np-difficiles ou polynomialement exacts. En général, la solution aux problèmes de flux de coûts minimaux est ambiguë.

Libellé du problème

Un réseau de flux est un graphe orienté avec un nœud de départ avec l'offre et un nœud de destination avec une demande correspondant à l'offre , ainsi que 2 fonctions qui sont définies sur l'ensemble de bord : ${\ style d'affichage G = (V, E)}$${\ displaystyle s \ in V}$${\ displaystyle a \ in \ mathbb {R} ^ {+}}$${\ displaystyle t \ in V}$${\ style d'affichage -a}$

1. La fonction de capacité attribue à chaque bord la quantité maximale de marchandises pouvant être transportées le long du bord.${\ displaystyle \ kappa: E \ rightarrow \ mathbb {R} ^ {+}}$
2. La fonction de flux affecte à chaque arête le nombre de marchandises réellement affectées au transport. Par conséquent, la limitation de capacité s'applique également à tout le monde .${\ displaystyle f: E \ rightarrow \ mathbb {R} _ {0} ^ {+}}$ ${\ displaystyle f (u, v) \ leq \ kappa (u, v)}$${\ displaystyle v, u \ in V}$

De plus, les 2 propriétés suivantes doivent s'appliquer à la fonction de flux :

1. La conservation du fleuve , qui peut s'exprimer par tous .${\ displaystyle u \ neq s, t}$${\ displaystyle \, \ sum _ {w \ in V} f (u, w) = 0}$
2. La satisfaction du flux de l'offre et de la demande, qui peut être exprimée pour le nœud de départ par et le nœud de destination par .${\ displaystyle \, \ sum _ {w \ in V} f (s, w) = d}$${\ displaystyle \, \ sum _ {w \ in V} f (w, t) = d}$

Si une fonction de coût (séparable) est également introduite , qui attribue une valeur pour les coûts de transport à chaque arête en fonction de la valeur de flux allouée, les coûts totaux du flux sont calculés à l'aide de la formule de coût . ${\ displaystyle c: E \ times \ mathbb {R} \ rightarrow \ mathbb {R} _ {0} ^ {+}}$${\ style d'affichage f}$ ${\ displaystyle \, C (f) = \ sum _ {(u, v) \ in E} c (u, v, f (u, v))}$

Dans le cas d'un problème de flux à coût minimal, on recherche une fonction de flux qui minimise la formule de coût.

Complexité et structure de la fonction de coût

La restriction de capacité, le maintien du flux et l'exécution du flux font de la recherche d'une fonction de flux qui minimise la formule de coût un problème d'optimisation avec des contraintes. Par conséquent, au moins en théorie, le problème pourrait être résolu numériquement en utilisant le mode multiplicateur de Lagrange . En pratique, cependant, cela se traduit généralement par des fonctions si fortement non linéaires qu'il est souvent impossible de trouver une solution à l'aide de méthodes numériques. Dans le domaine de l' informatique et de la recherche opérationnelle , des algorithmes et des procédures pour la solution exacte de cette classe de problèmes ont été développés depuis la fin des années 1960 . Ces solutions existent souvent en faisant d'autres hypothèses sur le problème. Cela rend le problème dans le cas discret, dans lequel les fonctions de capacité et de flux ne supposent que des nombres naturels ou la valeur 0, beaucoup plus facile à calculer.

Fonction de coût linéaire

Dans le cas d'une fonction de coût linéaire , le problème peut être résolu en utilisant des techniques de programmation linéaire et la méthode du simplexe .

Fonction de coût convexe

En 1986, Minoux a montré que pour le cas discret, il existe des solutions exactes polynomiales pour le problème dans le cas d'une fonction de coût convexe . Ceux-ci peuvent être trouvés, par exemple, en linéarisant la fonction de coût pièce par pièce dans les différentes phases delta de l'algorithme de mise à l'échelle de la capacité .

Fonction de coût non linéaire générale

Pour les fonctions de coût non linéaires générales, trouver une solution est NP-difficile.

Voir également

• Problèmes de débit maximum
• Le plus court chemin
• Problème d'affectation
• Recherche opérationnelle

Littérature

• Oliver Zlotowski : Conception, mise en œuvre et évaluation de structures de données de réseau et d'algorithmes de réseau pour résoudre le problème de flux à coût minimum . Logos Berlin (20 septembre 2010). ISBN 978-3832526009

Preuve individuelle

1. ↑ Leena Suhl, Taieb Mellouli : Systèmes d'optimisation : modèles, processus, logiciels, applications . Sauteur; Édition : 2e, révisée. Édition 2009 (10 juin 2009). ISBN 978-3642015793 . Page 169
2. ↑ G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l'Académie des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, p. 666-704.
3. ↑ ^{a b} Ravindra K. Ahuja, Thomas Magnanti, James Orlin : Flux de réseau : théorie, algorithmes et applications . Prentice Hall, Englewood Cliffs, NJ 1993, ISBN 978-0-13-617549-0 . 
4. ^ Morton Klein: Une méthode primaire pour des flux de coûts minimaux avec des applications aux problèmes d'affectation et de transport . Dans : Sciences de gestion . ruban 14 , non. 3 , 1er novembre 1967, ISSN  0025-1909 , p. 205–220 , doi : 10.1287 / mnsc.14.3.105 ( informs.org [consulté le 5 septembre 2021]). 
5. ^ M. Minoux : Résolution des flux de coût minimum entiers avec un objectif de coût convexe séparable polynomialement . Dans : Netflow à Pise (=  Mathematical Programming Studies ). Springer, Berlin, Heidelberg 1986, ISBN 978-3-642-00923-5 , p. 237-239 , doi : 10.1007 / bfb0121104 . 
6. ↑ GM Guisewite, PM Pardalos : Problèmes de flux réseau à coût concave minimum : applications, complexité et algorithmes . Dans : Annals of Operations Research . ruban 25 , non. 1 , 1er décembre 1990, ISSN  1572-9338 , p. 75-99 , doi : 10.1007 / BF02283688 .