min_lcost_cflow - flot contraint de coût linéaire minimum
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 cas flag est égal à 0, sinon il est égal à 1.
es bornes sur les flots sont données par les éléments edge_min_cap et edge_max_cap du graphe. La valeur de la capacité minimum doit être égal à zéro. Les valeurs des capacités maximum doivent être entières et positives. Si les valeurs edge_min_cap ou edge_max_cap ne sont pas données (vecteur vide [] ), elles sont supposées nulles sur chaque arête.
Les coûts sur les arêtes sont donnés par les éléments edge_cost du graphe. Les coûts doivent être positifs.
Si la valeur de edge_cost n'est pas donnée (vecteur vide [] ), elle est supposé nulle sur chaque arête.
Si la valeur de edge_cost n'est pas donnée (vecteur vide [] ), elle est supposé nulle sur chaque arête.
Cette fonction utilise l'algorithme de Busacker et Goven.
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('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548]; g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399]; show_graph(g); g1=g; ma=arc_number(g1); n=g1('node_number'); g1('edge_min_cap')=0*ones(1,ma); rand('uniform'); g1('edge_max_cap')=round(20*rand(1,ma))+ones(1,ma); g1('edge_cost')=10*rand(1,ma)+ones(1,ma); source=15; sink=1; cv=5; [c,phi,v]=min_lcost_cflow(source,sink,cv,g1); x_message(['Le cout est: '+string(c); 'Voici les flots sur les arcs']); nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1; g1('node_type')=nodetype; ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii); g1('edge_color')=edgecolor; edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii); nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11; g1('node_color')=nodecolor; g1('edge_font_size')=edgefontsize; g1('edge_label')=string(phi); show_graph(g1);