De la Théorie des Graphes à l'Optimisation

Chapitre 2 : L'Art de la Contrainte (Programmation Linéaire)

Modélisation du Problème Linéaire

Forme Canonique
Max z = $x_1$ + $x_2$

Domaine Réalisable & Droite d'Objectif (2D)

Zone verte = Domaine réalisable | Ligne rouge = Iso-valeur de z
Valeur testée $z$ : 0 Glissez pour balayer le plan

Méthode du Simplexe (Forme Standard)

Itération : 0

Forme Standard & Variables d'Écart :

Tableau du Simplexe / Dictionnaire :

Entrante Sortante

Initialisation de la forme standard. Les variables d'écart sont en base avec valeur initiale égal au membre de droite.

Synthèse Théorique & Principes Clés

1. Forme Canonique vs Standard : En forme canonique, les contraintes sont des inégalités ($\le$). Pour appliquer le Simplexe, on passe en forme standard en ajoutant des variables d'écart non négatives ($x_3, x_4 \ge 0$).

2. Géométrie du Simplexe : Le domaine réalisable est un polyèdre convexe. Le théorème fondamental de la PL garantit que si une solution optimale existe, elle se trouve sur au moins un sommet du polyèdre.

3. Règle du Pivot : On choisit la variable entrante (plus grand coefficient positif dans $z$), puis la variable sortante via le test du ratio minimum $c_i / a_{ij}$ positif le plus strict.