Algorithme de réseau simplex - Network simplex algorithm

En optimisation mathématique , l' algorithme du simplexe de réseau est une spécialisation théorique des graphes de l' algorithme du simplexe . L'algorithme est généralement formulé en termes de problème de flux à coût minimum . La méthode du réseau simplex fonctionne très bien dans la pratique, généralement 200 à 300 fois plus rapide que la méthode du simplexe appliquée au programme linéaire général de mêmes dimensions.

L'histoire

Pendant longtemps, l'existence d'un algorithme simplex de réseau dont l'efficacité a été prouvée a été l'un des principaux problèmes ouverts de la théorie de la complexité, même si des versions efficaces dans la pratique étaient disponibles. En 1995, Orlin a fourni le premier algorithme polynomial avec un temps d'exécution où est le coût maximum de toutes les arêtes. Plus tard, Tarjan a amélioré cela en utilisant des arbres dynamiques en 1997. Des algorithmes simplex à double réseau fortement polynomiaux pour le même problème, mais avec une plus grande dépendance au nombre d'arêtes et de sommets dans le graphe, sont connus depuis plus longtemps. ${\ displaystyle O (V ^ {2} E \ log (VC))}$${\ displaystyle C}$${\ displaystyle O (VE \ log V \ log (VC))}$

Aperçu

La méthode du simplexe de réseau est une adaptation de l'algorithme du simplex primal à variable bornée. La base est représentée par un arbre couvrant enraciné du réseau sous-jacent, dans lequel les variables sont représentées par des arcs, et les multiplicateurs simplex par les potentiels de nœud. A chaque itération, une variable d'entrée est sélectionnée par une stratégie de tarification, basée sur les doubles multiplicateurs (potentiels de nœud), et forme un cycle avec les arcs de l'arbre. La variable sortante est l'arc du cycle avec le débit le moins croissant. La substitution de l'entrée à la sortie de l'arc et la reconstruction de l'arbre s'appelle un pivot. Lorsqu'aucun arc non basique ne peut entrer, la solution optimale a été atteinte.

Applications

L'algorithme de réseau simplex peut être utilisé pour résoudre de nombreux problèmes pratiques, notamment:

• Problème de transbordement
• Problème de transport Hitchcock
• Problème d'affectation
• Chaînes et antichains en ensembles partiellement ordonnés
• Système de représentants distincts
• Couvertures et correspondance dans les graphiques bipartites
• Problème de traiteur

Références

Liens externes

• Résolution des problèmes de réseau La section 14, p B-113 montre un exemple d'exécution