<< max_flow Flots min_lcost_flow1 >>

metanet >> metanet > Flots > min_lcost_cflow

min_lcost_cflow

flot contraint de coût linéaire minimum

Séquence d'appel

[c,phi,v,flag] = min_lcost_cflow(i,j,cv,g)

Paramètres

i

entier, numéros des sommets sources

j

entier, numéros des sommets puits

cv

scalaire, valeur du flot contraint

g

graphe (liste)

c

valeur du coût

phi

vecteur ligne des valeurs des flots sur les arcs

v

vecteur ligne des flots des sources aux puits

flag

problème soluble ou pas (0 ou 1)

Description

min_lcost_cflow calcule flot de coût linéaire minimum dans un réseau g, avec les valeurs des flots des sommets sources i aux puits j contraints à valoir cv.

Elle renvoie le coût total du flot sur les arcs c et le vecteur ligne des flots sur les arcs phi et les valeurs des flots v sur les arcs virtuels des sources aux puits. Si v est plus petit que cv, un message est affiché, mais le calcul est fait quand même. Dans ce casflag est égal à 0, sinon il est égal à 1.

Les bornes sur les flots sont données par les éléments g.edges.data.min_cap et g.edges.data.max_cap du graphe.

Les valeurs des capacités maximum doivent être entières et positives. La valeur de la capacité minimum doit être égal à zéro. Si la valeur de min_cap ou de max_cap n'est pas donnée elle est supposé nulle sur chaque arête.

Les coûts sur les arêtes sont donnés par les éléments g.edges.data.cost du graphe. Les coûts doivent être non négatifs. Si la valeur de cost n'est pas donnée, elle est supposé nulle sur chaque arête.

Si les champs de donnée min_cap ou max_cap ou cost ne sont pas présents dans la structure du graphe, ils peuvent être ajoutés et affectés en utilisant la fonction add_edge_data.

Cette fonction utilise l'algorithme de Busacker et Goven.

Exemples

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g.nodes.graphics.x=[155,153,85,155,237,244,244,334,338,346,442,440,439,333,438];
g.nodes.graphics.y=[45,145,221,222,221,82,139,225,142,69,140,72,232,318,319];
source=15;g.nodes.graphics.type(source)=2; //source node
sink=1;g.nodes.graphics.type(sink)=1; //sink node
show_graph(g);

g=add_edge_data(g,'max_cap',[11,8,9,19,20,8,9,16,6,11,6,12,12,3,6,14,16,2,14,5,9,18,13,11,5,18,3,7,18]);
g=add_edge_data(g,'cost',[9,6,11,7,11,2,8,5,7,10,2,9,10,7,7,9,2,7,2,8,4,6,11,8,1,7,4,4,7]);
flow_constraint=5;
[c,phi,v,flag]=min_lcost_cflow(source,sink,flow_constraint,g);

g.edges.graphics.foreground(find(phi<>0))=color('red');
g=add_edge_data(g,'flow',phi)
g.edges.graphics.display='flow';
show_graph(g);

Voir Aussi


Report an issue
<< max_flow Flots min_lcost_flow1 >>