Problème de flot

[invitea1d36d7d]

merci, c'est la formulation du problème de flot max en programme linéaire que je cherche SVP.
-----

[invite2bd4953c]

Salut,

je pense ce serait mieux que tu répondes dans le premier sujet que tu as posté.
Cela dit :
je te conseille d'essayer de prendre une variable par arc (i,j) qui correspondra à la valeur du flot sur l'arc (i,j). Ensuite les conditions de Kirchoff (pour chaque sommet qui n'est ni une source ni un puit), de flot réalisable (positivité et respect des capacités) s'écrivent directement. La fonction objectif a aussi une écriture très simple.
Autrement dit, reprend la définition d'un flot et remplace partout la valeur du flot sur un arc par une variable x_(i,j) et tu auras ta formulation.

[invitea1d36d7d]

Salut,

je pense ce serait mieux que tu répondes dans le premier sujet que tu as posté.
Cela dit :
je te conseille d'essayer de prendre une variable par arc (i,j) qui correspondra à la valeur du flot sur l'arc (i,j). Ensuite les conditions de Kirchoff (pour chaque sommet qui n'est ni une source ni un puit), de flot réalisable (positivité et respect des capacités) s'écrivent directement. La fonction objectif a aussi une écriture très simple.
Autrement dit, reprend la définition d'un flot et remplace partout la valeur du flot sur un arc par une variable x_(i,j) et tu auras ta formulation.

merci de votre repense
selon la formulation que vous m'avez propose comment on peut extraire la matrice d'incidence de la graphe associe a ce probleme?

[invite2bd4953c]

Salut,

qu'est ce que tu veux dire par "extraire la matrice d'incidence de la graphe associe a ce probleme" ? Est-ce que ca correspond a ecrire la matrice des contraintes du programme lineaire ?

[A voir en vidéo sur Futura]

[invitea1d36d7d]

Salut,

qu'est ce que tu veux dire par "extraire la matrice d'incidence de la graphe associe a ce probleme" ? Est-ce que ca correspond a ecrire la matrice des contraintes du programme lineaire ?

salut,
oui, je veux savoir la forme de la matrice des contraintes de la programme lineaire SVP
j'ai une question pour la formulation de programme est ce qu'on peut introduire la somme des valeurs de flot sortant de la source (resp entrant dans le puit) comme une contrainte?
merci d'avance

[invite2bd4953c]

Salut,

si c'est un problème de flot max que tu résous avec l'algorithme de Ford-Fulkerson dans sa version la plus basique (i.e avec les (s,t)-chemins augmentant dans le graphe auxiliaire) alors la source s n'a pas d'arcs entrants et le puits t pas d'arcs sortants. La valeur du flot correspond justement à la somme des valeurs du flot sur les arcs sortants de s (ou sur les arcs entrants en t). Ainsi contraindre ces fonctions reviendrait à contraindre la valeur du flot en plus des contraintes liées au graphe et là le problème correspondrait plus à de la décision (réalisabilité du polyèdre sous-jacent) qu'à de l'optimisation, mais cela revient en fait au même dans ce cas précis. Bref : pas de contraintes de Kirchoff pour s et t !

Les seules conditions à imposer sont donc la condition de Kirchoff pour tous les sommets distincts de s et t, la positivité du flot et le respect de capacités. Ce qui te donne immédiatement la matrice des contraintes :

-pour les conditions de Kirchoff, écris les comme une égalité à 0 et tu vas certainement reconnaître de quelle matrice il s'agit (c'est presque la matrice d'incidence, comme tu l'as dit plus haut).
-pour la positivité c'est l'opposé de l'identité, comme d'habitude (avec pour vecteur des bornes le vecteur dont toutes les coordonnées sont nulles)
-pour le respect des capacités, c'est l'identité et tu changes le vecteur des bornes.

Si ce genre de choses t'intéresse, il est aussi intéressant de savoir qu'il existe une autre formulation de ce problème qui correspond à un packing de (s,t)-chemins à partir duquel on peut retrouver Ford-Fulkerson avec l'intégralité duale totale des contraintes (qu'on déduit ici facilement de la totale unimodularité).

J'espère que c'est plus clair pour toi!

[invitea1d36d7d]

Salut,

si c'est un problème de flot max que tu résous avec l'algorithme de Ford-Fulkerson dans sa version la plus basique (i.e avec les (s,t)-chemins augmentant dans le graphe auxiliaire) alors la source s n'a pas d'arcs entrants et le puits t pas d'arcs sortants. La valeur du flot correspond justement à la somme des valeurs du flot sur les arcs sortants de s (ou sur les arcs entrants en t). Ainsi contraindre ces fonctions reviendrait à contraindre la valeur du flot en plus des contraintes liées au graphe et là le problème correspondrait plus à de la décision (réalisabilité du polyèdre sous-jacent) qu'à de l'optimisation, mais cela revient en fait au même dans ce cas précis. Bref : pas de contraintes de Kirchoff pour s et t !

Les seules conditions à imposer sont donc la condition de Kirchoff pour tous les sommets distincts de s et t, la positivité du flot et le respect de capacités. Ce qui te donne immédiatement la matrice des contraintes :

-pour les conditions de Kirchoff, écris les comme une égalité à 0 et tu vas certainement reconnaître de quelle matrice il s'agit (c'est presque la matrice d'incidence, comme tu l'as dit plus haut).
-pour la positivité c'est l'opposé de l'identité, comme d'habitude (avec pour vecteur des bornes le vecteur dont toutes les coordonnées sont nulles)
-pour le respect des capacités, c'est l'identité et tu changes le vecteur des bornes.

Si ce genre de choses t'intéresse, il est aussi intéressant de savoir qu'il existe une autre formulation de ce problème qui correspond à un packing de (s,t)-chemins à partir duquel on peut retrouver Ford-Fulkerson avec l'intégralité duale totale des contraintes (qu'on déduit ici facilement de la totale unimodularité).

J'espère que c'est plus clair pour toi!

merci
c'est bien