Réseau Modèles de programmation de flux
Exemple de distribution
Le responsable de la logistique a le problème de matériel d'expédition dans les entrepôts aux emplacements des clients comme illustré sur la figure. 1. Les entrepôts sont à Phoenix, Austin et Gainesville, les noeuds gris dans la figure. Les approvisionnements disponibles sont indiqués dans les supports adjacents aux noeuds avec un nombre positif indiquant une alimentation du matériau. Les clients sont à Chicago, Los Angeles, Dallas, Atlanta et New York. Les nombres négatifs adjacents à ces noeuds sont les exigences. Possibles liens de navigation aérienne sont les arcs orientés entre les nœuds. Les chiffres adjacents aux arcs sont les frais d'expédition de l'unité. Le débit de chaque liaison est limitée à un maximum de 200 unités. Dallas et Atlanta sont des plaques tournantes qui, en plus de leurs propres exigences, peut transborder matériel à d'autres clients. Le problème est de déterminer un plan d'expédition optimal qui minimise le coût total de l'expédition, tout en répondant à toutes les exigences des clients avec des fournitures disponibles.
Figure 1. Problème de distribution.
Arc bornes inférieures 0 et 200 limite supérieure.
Modèle réseau pur
Ce problème est prêt à l'emploi pour un modèle de flux réseau, et nous l'utilisons pour décrire les différents composants de ce type de modèle. Le modèle de réseau est graphique en ce qu 'il se présente comme un ensemble de noeuds et d'arcs tirés sur la figure. Les nœuds représentent les villes de ce problème, et nous les nommer les noms raccourcies des villes d'offre et de demande. Les arcs sont les segments de droite orientés de la figure. Les noeuds à ses extrémités identifient un arc. Un arc dans la figure origine au niveau du noeud Phoenix et se termine au niveau du noeud de Chicago.
Le débit est limité dans un arc par les bornes inférieures et supérieures sur le flux. Dans cet exemple, nous spécifions 0 comme la limite inférieure pour tous les arcs et 200 comme la limite supérieure. Parfois, la capacité à long terme se réfère à la limite supérieure du débit. Dans les limites imposées par la conservation des flux pour chaque noeud et les limites sur le flux pour chaque arc, il y a généralement beaucoup de flux possibles (un flux est une affectation d'un flux d'arc à chaque arc). Le problème est de trouver un flux possible, le cas échéant, et un débit optimal de l'ensemble des flux possibles.
Le critère d'optimalité est le coût. Associé à chaque arc est un coût par unité de débit (le numéro dans la parenthèse). Si un x flux passe à travers l'arc avec coût unitaire c. un cx de coût est engagé. Le coût total du réseau est la somme des coûts d'arc, et l'objectif d'optimisation est de trouver le débit possible qui minimise cette mesure.
Nous appelons le modèle de cette section un modèle pur de flux de réseau, car le flux entrant d'un arc à son noeud d'origine est égale au flux sortant de l'arc à son noeud terminal. C'est ensuite opposé au modèle généralisé de flux réseau qui ne possède pas cette limitation. Le modèle pur a la caractéristique importante de solutions optimales intégrales. Chaque fois que l'ensemble des flux externes de noeuds et de toutes les limites supérieures et inférieures arc sont des nombres entiers, la solution de l'écoulement vers le modèle pur est également entier. Comme nous le verrons, cela a des ramifications importantes.
Le modèle défini sur la Fig. 1 peut être résolu pour trouver les flux optimal. La solution est indiquée sur la page suivante.