RO + Graphe orienté + Programmation linéaire

[nikolas1975]

Bonjour,

J'ai un problème concernant un graphe orienté.. Je dois déterminer le plus long chemin entre le sommet A et le sommet B par le biais de Bellman puis modéliser ce problème sous forme de programme linéaire.

Le graphe:
A vers E
A vers B
E vers D
D vers B
Entre A et D, il y a A vers C et C vers D
E vers C

Je comprend Bellman mais comment passer d'un graphe orienté vers un programme linéaire ?

Merci pour votre aide,

Cdt,

Nikolas

[WillyCagnes]

bjr

voir ces liens
http://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford
http://www.gaudry.be/graphes-ford-bellman.html
http://fr.openclassrooms.com/forum/sujet/bellman-ford-21479
http://www.developpez.net/forums/d732564/c-cpp/cpp/algorithme-ford-bellman/


http://www.youtube.com/watch?v=e4V3izmZADg
http://www.youtube.com/watch?v=2Lrm0_SOZyo

[Cliffe]

Données :

On note la distance du sommet vers le sommet .
Soit le graphe où (avec où représente le sommet de départ et le sommet d'arrivé) représente les sommets et représente l'ensemble des arcs.

Variables de décisions :
- est une variable binaire indiquant si l'arc fait partie de la solution.

Programme linéaire en nombre entier :

[CENTER]






[/CENTER]

La fonction objectif maximise la distance totale. Les deux contraintes assurent la conservation du flot. La dernière contrainte fixe la nature des variables de décisions.

[nikolas1975]

Merci pour ces informations. Dans le cas d'un graphe non-orienté, la technique est la même ?

[Cliffe]

Oui. Y'a rien a changer. C'est le mm programme. :lol3:
Je fais la différence entre l'arc et l'arc .

Si n'existe pas, alors .

[nikolas1975]

Par contre cela change entre le plus long chemin et le plus court chemin?

...je vois que vous êtes fort en Math, je viens de poser une nouvelle question sur le simplex sur ce même forum. Pourriez-vous jeter un coup d’œil. C'est la phase 1 du simplex sous forme de tableau.

Merci par avance

[Cliffe]

Tu met pour le plus court chemin.

Quelles études fais-tu ?

[nikolas1975]

Je suis en Master MIAGE (informatique) et j'ai des cours de RO. Le seul problème est que j'ai 40 ans et en reprise d'étude donc je galère un peux en math ;-)...et toi ?