PHPSimplex

Optimiser les ressources avec Optimisation Linéaire



Plus court chemin

Les problèmes connus comme problèmes de plus court chemin ou problèmes de cheminement, essayent de trouver le chemin plus court entre deux points. Cela peut s'agir de la distance entre les points d'origine et de destination ou bien le temps écoulé d'un point à l'autre. Il est très utilisé dans les problèmes des réseaux de communications.

Ce type de problèmes peut se résoudre moyennant la méthode du Simplexe, cependant, il y a d'autres méthodes plus efficaces comme l'algorithme de Dijkstra ou celui de Bellman-Ford.

Exemple

Une personne doit se déplacer tous les jours d'une ville A à une autre G. Elle analyse le trajet plus court avec la carte de routes. On montre les routes et les distances dans la prochaine figure:

Problème de plus court chemin

 

Déterminer les variables de décision et les représenter de manière algébrique. Dans ce cas:

Déterminer les contraintes et les formuler comme équation ou inéquations dépendants des variables de décision. Ces contraintes sont déduites du bilan entre les possibles trajets qui partent de chaque ville et ceux qui arrivent jusqu'à elle (en obviant à tous les trajets qui nous rendent au point de départ et ceux qui viennent du point de destination):

Présenter toutes les conditions implicitement établies conformément à la nature des variables: qu'elles ne peuvent pas être négatives, qu'elles soient entièrs, qu'elles ne peuvent que prendre valeurs déterminées, ... Dans ce cas les conditions sont que les variables doivent être booléens (0 on ne prend pas le chemin, 1 on prend le chemin), et par conséquent elles ne peuvent pas être négatives:

Déterminer la fonction objectif:

On effectue un changement dans la nomenclature des variables. La correspondance suivante s'établie:

XAB XAC XBE XBD XDB XEB XCD XCF XFC XDC XDE XED XEG XFG
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14

Résoudre avec PHPSimplex.

Copyright ©2006-2016 PHPSimplex. Tous droits réservés.
Suivez-nous sur Twitter
X

PHPSimplex
Version 0.81

Copyright ©2006-2016. Tous droits réservés.

Développé par:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Traduction en langue anglais par:
Luciano Miguel Tobaria

Traduction en langue française par:
Ester Rute Ruiz