Solveur de Programmation Linéaire

Solveur de Programmation Linéaire

Le Solveur de programmation linéaire est un calculateur en ligne qui trouve le maximum ou le minimum d'une fonction objectif linéaire soumise à un système d'inégalités ou d'égalités linéaires. Il utilise la méthode du simplexe (variante du Grand M) pour que les contraintes <=, >= et = puissent être mélangées librement. Pour les problèmes à 2 variables, il dessine un graphique interactif de la région réalisable avec chaque sommet et l'optimum mis en évidence.

Qu'est-ce que la programmation linéaire ?

Un problème de programmation linéaire (PL) se pose ainsi :

L'ensemble des points satisfaisant chaque contrainte est appelé la région réalisable, un polyèdre convexe. Le Théorème fondamental de la programmation linéaire stipule que si le PL a un optimum fini, il est atteint à un sommet (point extrême) de ce polyèdre. C'est pourquoi la méthode du simplexe — qui passe de sommet en sommet — est si efficace.

Comment fonctionne la méthode du simplexe

En partant d'un sommet réalisable, la méthode du simplexe améliore l'objectif de manière itérative en pivotant vers un sommet voisin ayant une meilleure valeur. Le mécanisme :

1. Forme standard : convertit le PL en max c^Tx sous contraintes Ax = b, x ≥ 0. Pour les contraintes <=, on ajoute des variables d'écart ; pour >=, on soustrait un surplus et on ajoute une variable artificielle avec une pénalité élevée −M ; pour les égalités, on ajoute une artificielle.
2. Tableau initial : la base est constituée des variables d'écart et artificielles, ce qui donne un sommet de départ évident.
3. Variable entrante : on choisit la variable hors base ayant le coût réduit \( c_j - z_j \) le plus positif. Si aucune variable de ce type n'existe, la solution actuelle est optimale.
4. Variable sortante : à partir de la colonne entrante, on effectue le test du ratio minimum — on divise le RHS de chaque ligne par son coefficient positif dans la colonne entrante, et on choisit la ligne avec le plus petit ratio. Si aucun coefficient n'est positif, le PL est non borné.
5. Pivot : on utilise l'élimination de Gauss pour transformer la colonne entrante en vecteur unitaire, avec un 1 sur la ligne sortante.
6. Répétez jusqu'à ce que le critère d'arrêt soit satisfait.

Si une variable artificielle reste dans la base avec une valeur positive à la fin, le PL d'origine est impossible.

Méthode graphique (pour 2 variables)

Pour les problèmes à deux variables, la région réalisable est un polygone convexe en 2D. Comme l'optimum est toujours à un sommet, énumérer chaque sommet et évaluer l'objectif à cet endroit suffit à résoudre le problème. Ce calculateur effectue cette énumération en intersectant chaque paire de frontières de contraintes, en ne gardant que les intersections satisfaisant toutes les autres contraintes, et en les triant dans le sens inverse des aiguilles d'une montre pour la visualisation.

Syntaxe de saisie

Écrivez l'objectif sur la première ligne, puis une contrainte par ligne. Les noms de variables peuvent être n'importe quel identifiant (x, y, x1, profit…). Les opérateurs sont <=, >= et =. La non-négativité peut être écrite sous la forme x, y >= 0 par raccourci.

Les lignes vides et les commentaires commençant par # sont ignorés. Le solveur accepte jusqu'à 8 variables de décision et 20 contraintes.

Exemple concret

Considérons un atelier de menuiserie qui fabrique des tables et des chaises. Chaque table génère 3 \$ de profit et nécessite 1 unité de bois et 2 unités de main-d'œuvre. Chaque chaise génère 5 \$ de profit et nécessite 1 unité de bois, 1 unité de main-d'œuvre et 3 unités de vernis. Disponibles : 10 bois, 16 main-d'œuvre, 18 vernis. Avec x = tables et y = chaises, le PL est :

La région réalisable est un pentagone. Évaluation de Z à chaque sommet :

L'atelier devrait donc fabriquer 6 tables et 4 chaises pour un profit maximum de 38 \$. Les contraintes de bois et de main-d'œuvre sont saturantes (elles égalent leur RHS à l'optimum) ; le vernis a un écart de 0 (également saturante dans ce cas), ce qui signifie que les trois ressources sont épuisées.

Pièges courants et détections du solveur

Applications

• Mix produit et planification de la production — combien de chaque produit fabriquer pour un profit maximum sous limites de ressources.
• Problèmes de régime et de mélange — minimiser le coût d'un régime ou d'un aliment tout en respectant les minima nutritionnels.
• Transport et affectation — minimiser les coûts d'expédition lorsque l'offre et la demande doivent s'équilibrer.
• Optimisation de portefeuille — maximiser le rendement attendu sous contraintes de risque ou d'exposition (linéarisé).
• Flux réseau — le flux max et le flux de coût min se réduisent à des PL avec des matrices de coefficients totalement unimodulaires.
• Planification — gestion des effectifs avec exigences de quarts et limites d'heures totales.

Comment utiliser ce calculateur

1. Saisissez votre PL dans la zone de texte. La première ligne doit commencer par Maximiser ou Minimiser. Chaque ligne suivante est une contrainte, une par ligne.
2. Utilisez le raccourci x, y >= 0 pour déclarer la non-négativité de toutes les variables listées à la fois.
3. Cliquez sur Résoudre le problème de PL. Le solveur affiche la valeur optimale Z, les valeurs optimales de chaque variable de décision, une liste de contraintes saturantes, et pour les PL à 2 variables, un graphique interactif de la région réalisable.
4. Survolez un sommet dans le graphique pour voir ses coordonnées et sa valeur Z. L'optimum est mis en évidence par une étoile.
5. Consultez les tableaux du simplexe pour voir chaque pivot et suivre comment la méthode améliore Z. La colonne entrante est surlignée en ambre ; la ligne sortante en rouge.

Foire aux questions

Qu'est-ce qu'un problème de programmation linéaire ?

Un problème de programmation linéaire (PL) consiste à maximiser ou minimiser une fonction objectif linéaire sur un ensemble de variables de décision satisfaisant un système d'inégalités ou d'égalités linéaires. L'ensemble réalisable est un polyèdre convexe, et l'optimum est toujours atteint à l'un de ses sommets — le fait crucial exploité par la méthode du simplexe.

Comment fonctionne la méthode du simplexe ?

La méthode du simplexe se déplace le long des sommets du polyèdre réalisable. Chaque étape (un "pivot") échange une variable de la base contre une autre, passant à un sommet voisin avec un objectif strictement meilleur. L'algorithme s'arrête lorsqu'aucun pivot ne peut améliorer Z — le sommet actuel est alors optimal. Cet outil utilise la variante Grand M pour mélanger les contraintes <=, >= et =.

Qu'est-ce que la région réalisable ?

La région réalisable est l'ensemble de toutes les valeurs de variables satisfaisant simultanément chaque contrainte. Pour 2 variables, c'est un polygone convexe 2D ; pour n variables, c'est un polyèdre à n dimensions. Un polyèdre vide signifie que le PL est impossible ; un polyèdre s'étendant à l'infini dans la direction de l'amélioration signifie que le PL est non borné.

Que signifie "non borné" en programmation linéaire ?

Un PL est non borné lorsque la région réalisable s'étire à l'infini dans une direction où l'objectif continue de s'améliorer. Par exemple, Maximiser x sous la seule contrainte x ≥ 0 n'a pas de maximum fini. Les PL réels qui renvoient "non borné" révèlent généralement une contrainte manquante — souvent une borne supérieure sur une ressource.

Que signifie "optima multiples" ?

Les optima multiples surviennent lorsque plusieurs points atteignent la même meilleure valeur d'objectif. Géométriquement, l'objectif est parallèle à une arête saturante du polygone, donc chaque point de cette arête — et chaque combinaison convexe de ses extrémités — est optimal. Le solveur le signale lorsqu'une variable de décision hors base a un coût réduit de zéro à la fin.

Combien de variables et de contraintes le solveur accepte-t-il ?

Jusqu'à 8 variables de décision et 20 contraintes. Le graphique interactif de la région réalisable n'est dessiné que pour les problèmes à 2 variables ; avec 3 variables ou plus, vous obtenez toujours la solution numérique complète du simplexe, les tableaux étape par étape et le rapport sur les contraintes saturantes.

Lectures complémentaires

• Programmation linéaire — Wikipédia
• Algorithme du simplexe — Wikipédia
• Méthode du Grand M — Wikipédia (EN)
• Dualité en optimisation — Wikipédia

Opérations mathématiques avancées:

• Calculateur de Matrice d'Adjacence Nouveau
• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial
• Calculatrice de distribution binomiale
• Calculatrice de Bit Populaire
• Simplificateur d'Algèbre de Boole Nouveau
• Calculateur du Théorème Central Limite
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de Combinaison Populaire
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice de fractions continues
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de plus court chemin de Dijkstra
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• Calculatrice des Exposants (Haute Précision) Populaire
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma
• Calculateur de Nombre d'Or
• Calculateur de Coloration de Graphes Nouveau
• Validateur de séquence de degrés de graphe
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculatrice de demi-vie
• Vérificateur de Chemin Hamiltonien Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Solveur de Programmation Linéaire Nouveau
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'arbre couvrant minimum
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Calculatrice du Taux de Croissance en Pourcentage Populaire
• Calculatrice de permutation
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur du principe des tiroirs
• Vérificateur de Graphe Planaire Nouveau
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculateur de Racine Primitive
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique Populaire
• Calculateur d’Anneaux et de Corps Nouveau
• Calculateur d'Arrondi Nouveau
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Théorie des Ensembles
• Calculateur de Chiffres Significatifs Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur de Nombres de Stirling
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Calculateur de Tri Topologique Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Générateur de table de vérité
• Générateur de Diagramme de Venn (3 Ensembles)