Analyse et conception d'un solveur simplexe en python -Progr

Télécharger PDF

Mini-projet : Programmation Linéaire à l'École Nationale des Sciences Appliquées de Fès

Ce document décrit un mini-projet de programmation linéaire.

L'objectif de ce mini-projet se divise en deux parties principales :

Écrire une fonction nommée "domaine réalisable" capable de tracer graphiquement le domaine des solutions réalisables, ainsi que la fonction objectif (par exemple, c^Tx = p) pour différentes valeurs du paramètre p.
La deuxième partie vise à programmer la méthode tabulaire de l'algorithme du Simplex. Le problème de programmation linéaire (PL) à implémenter se présente généralement sous la forme standard suivante :
Maximiser f(x) = c^Tx

Sous contraintes :
- Ax ≤ b
- x ≥ 0
- où x ∈ Rⁿ est le vecteur des variables de décision.

Pour programmer l'algorithme du Simplex, les étapes essentielles à suivre sont les suivantes :

Définir une fonction qui initialise le tableau du Simplex :
- Fournit la forme canonique du problème et génère le tableau initial du Simplex.
- Définit une solution de base initiale réalisable.
- Présente le tableau initial du Simplex.
Définir une fonction pour vérifier l'optimalité de la solution courante.
Définir une fonction qui sélectionne la variable entrante dans la base.
Créer une fonction pour identifier la ligne de pivot (variable sortante de la base) en utilisant la règle du plus petit rapport. Cette fonction doit également détecter si la fonction objectif est bornée ou non.
Mettre à jour le tableau du Simplex et la solution, en effectuant les opérations suivantes :
- Exécuter l'opération de pivotage : diviser la ligne de pivot par l'élément pivot.
- Rendre les autres éléments de la colonne de pivot égaux à zéro.
- Transformer les autres éléments du tableau en appliquant la règle de pivot.
Combiner toutes les étapes précédentes pour construire le programme complet de résolution du problème.
Appliquer le programme développé à des exemples étudiés en cours et comparer les résultats obtenus avec ceux de fonctions d'optimisation mathématique standard.

Les tâches suivantes peuvent être considérées comme optionnelles :

Implémenter les mêmes étapes pour la résolution d'un problème de minimisation.
Développer un programme interactif qui permet à l'utilisateur de choisir entre la maximisation et la minimisation d'un système donné, puis de le résoudre.

Qu'est-ce que l'algorithme du Simplex ?: L'algorithme du Simplex est une méthode itérative très efficace pour résoudre des problèmes d'optimisation linéaire. Il explore les sommets d'un polyèdre (défini par les contraintes du problème) afin de trouver la solution optimale qui maximise ou minimise une fonction objectif linéaire.
Quelle est la différence entre un problème de maximisation et de minimisation en programmation linéaire ?: En programmation linéaire, les problèmes de maximisation visent à trouver la valeur la plus élevée possible pour une fonction objectif (par exemple, le profit d'une entreprise), tandis que les problèmes de minimisation cherchent la valeur la plus basse (par exemple, le coût de production), tout en respectant un ensemble de contraintes définies par des inégalités linéaires.
Pourquoi est-il important de détecter si la fonction objectif est bornée lors de l'application de l'algorithme du Simplex ?: Il est crucial de vérifier si la fonction objectif est bornée pour s'assurer que le problème a une solution finie. Une fonction objectif non bornée indique que sa valeur peut être augmentée (ou diminuée) à l'infini sans violer les contraintes. Dans ce cas, il n'existe pas de solution optimale unique et finie, et l'algorithme doit être capable de signaler cette situation.