<< min_lcost_flow1 Flots min_qcost_flow >>

metanet >> metanet > Flots > min_lcost_flow2

min_lcost_flow2

flot de coût linéaire minimum

Séquence d'appel

[c,phi,flag] = min_lcost_flow2(g)

Paramètres

g

graphe (liste)

c

valeur du coût

phi

vecteur ligne des valeurs des flots sur les arcs

flag

problème soluble ou pas (0 ou 1)

Description

min_lcost_flow2 calcule flot de coût linéaire minimum dans un réseau g. Elle renvoie le coût total du flot sur les arcs c et le vecteur ligne des flots sur les arcs phi. Si le problème n'est pas soluble (impossible de trouver un flot compatible), flag 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 et minimum doivent être entières et positives. La valeur de la capacité maximum doit être supérieure ou égale à la valeur de la capacité minimum. 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.

La demande sur les sommets est donnée par l'élément g.nodes.data.demand du graphe. Les demandes doivent être des nombre entiers. La somme des demandes doit être nulle pour que le problème soit soluble. Si la valeur de demand n'est pas donnée, elle est supposée nulle sur chaque sommet.

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. Si le champs de donnée demand n'est pas présent dans la structure du graphe, il peut être ajouté et affecté en utilisant la fonction add_node_data.

Cette fonction utilise un algorithme de relaxation dû à D. Bertsekas.

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 1 8];
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 12 14];
g=make_graph('foo',1,15,ta,he);
g.nodes.graphics.x=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g.nodes.graphics.y=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);

g=add_edge_data(g,'max_cap',[37,24,23,30,25,27,27,24,34,40,21,38,35,23,38,28,26,..
                       22,40,22,28,24,31,25,26,24,23,30,22,24,35]);
g=add_edge_data(g,'cost',[10,6,3,8,10,8,11,1,2,6,5,6,5,3,4,2,4,4,8,2,4,5,4,8,8,3,4,3,7,10,10]);
g=add_node_data(g,'demand',[22,-29,18,-3,-16,20,-9,7,-6,17,21,-6,-8,-37,9]);

[c,phi,flag]=min_lcost_flow2(g);flag

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

show_graph(g);

Voir Aussi


Report an issue
<< min_lcost_flow1 Flots min_qcost_flow >>