Scilab function

min_qcost_flow - flot de coût quadratique minimum

Sequence d'appel

[c,phi,flag] = min_qcost_flow(eps,g)

Parametres

Description

min_qcost_flow calcule flot de coût quadratique 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. eps est la précision de l'algorithme itératif. 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. La valeur de la capacité maximum doit être supérieure ou égale à la valeur de la capacité minimum. 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_q_orig et edge_q_weight du graphe. Le coût sur l'arc u est donné par:

(1/2)*edge_q_weight[u](phi[u]-edge_q_orig[u])^2

Les coûts doivent être positifs. Si les valeurs de edge_q_orig ou edge_q_weight ne sont pas données (vecteur vide []), elles sont supposées nulles sur chaque arête.

Cette fonction utilise un algorithme dû à M. Minoux.

Exemples

Voir aussi