COGNITIA · Graphes et optimisation

De la Théorie des Graphes à l'Optimisation

Chapitre 2 — L'Art de la Contrainte

La programmation linéaire devient visuelle : modifiez les coefficients, explorez les contraintes et observez le déplacement de l'optimum.

✦ Tester mes connaissances — QCM

⚙️ Laboratoire de programmation linéaire

Maximiser z = c₁x₁ + c₂x₂, sous deux contraintes de type ≤, avec x₁ ≥ 0 et x₂ ≥ 0. Les coefficients peuvent être négatifs. Le simulateur détecte également les cas impossibles et non bornés.

Objectif x₁ + x₂
C1 x₁ + x₂ ≤
C2 x₁ + x₂ ≤

La visualisation est recalculée automatiquement après une modification.

📈 Domaine réalisable

Contrainte C1Contrainte C2Domaine réalisableOptimum

La zone affichée est limitée au cadre du graphique. Une zone colorée touchant le bord ne signifie pas nécessairement que le problème est non borné.

🏆 Résolution et interprétation

🧠 Comprendre la méthode

  1. Tracer les droites correspondant aux contraintes.
  2. Identifier les points satisfaisant toutes les inégalités, ainsi que x₁ ≥ 0 et x₂ ≥ 0.
  3. Calculer les sommets candidats : intersections des droites et des axes.
  4. Évaluer la fonction objectif en chaque sommet réalisable.
  5. Vérifier si l'objectif est non borné avant de conclure à un maximum fini.
Précision pédagogique : cette application résout le problème par la méthode graphique des sommets, et non par les pivots successifs du simplexe. Un tableau initial du simplexe n'est pas une preuve de résolution. Pour un maximum fini, un sommet optimal existe dans ce cadre à deux variables.