min_lcost_flow1

Scilab function
Last update : 25/04/2007

min_lcost_flow1 - flot de coût linéaire minimum

### Calling Sequence

  `[c,phi,flag] = min_lcost_flow1(g)`

### Parameters

- `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_flow1` 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 `edge_min_cap` et `edge_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 `edge_cost` n'est pas donnée (vecteur vide `[]` ), elle est supposé nulle 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.

Les demandes, i.e. les élément `node_demand` du graphe, doivent être égales à zéro.

Cette fonction utilise l'algorithme out-of-kilter.

### Examples

    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('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
    g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
    show_graph(g);
    g1=g;ma=arc_number(g1);
    rand('uniform');
    while %T then
      g1('edge_min_cap')=round(20*rand(1,ma));
      g1('edge_max_cap')=round(20*rand(1,ma))+g1('edge_min_cap')+33*ones(1,ma);
      g1('edge_cost')=round(10*rand(1,ma))+ones(1,ma);
      [c,phi,flag]=min_lcost_flow1(g1);
      if flag==1 then break; end;
    end;
    x_message(['Le cout est: '+string(c);
               'Flots sur les arcs ']);
    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);
    g1('edge_font_size')=edgefontsize;
    g1('edge_label')=string(phi);
    show_graph(g1);

### See Also

`min_lcost_cflow` , `min_lcost_flow2` , `min_qcost_flow` ,