Guide d’étude : Résolution de Programmes
Linéaires
1. Méthode Graphique
La méthode graphique est utilisée uniquement pour les programmes
linéaires à deux variables. Elle permet de visualiser l’ensemble des solu-
tions admissibles et la fonction objectif.
1. Représenter graphiquement les contraintes : Chaque contrainte
linéaire définit une région dans le plan. Pour une inégalité, on trace
la droite correspondante et on détermine le demi-plan satisfait par
l’inégalité.
2. Déterminer la région admissible : L’intersection de tous les demi-
plans (et droites) définis par les contraintes.
3. Identifier les sommets de la région admissible : Points d’inter-
section des droites frontières.
4. Évaluer la fonction objectif aux sommets : Z = c1 x1 + c2 x2 à
chaque sommet (x1 , x2 ).
5. Déterminer la solution optimale : Le sommet qui donne la valeur
optimale (max ou min) de Z.
Cas particuliers :
— Région admissible vide : aucune solution.
— Fonction objectif non bornée.
— Solutions optimales multiples : optimum sur une arête.
Limite : Non applicable si plus de deux variables.
2. Méthode du Simplexe
La méthode du simplexe est un algorithme itératif pour tout nombre de
variables.
1
Forme standard
— Maximiser Z (ou minimiser −Z).
— Contraintes sous forme d’égalités (≤ : ajouter variable d’écart ; ≥ :
ajouter variable d’excédent et artificielle).
— Toutes les variables ≥ 0.
Algorithme du Simplexe
1. Mettre sous forme standard et construire le tableau initial.
2. Tester l’optimalité : ligne Z (tous les coefficients ≥ 0 pour max, ≤ 0
pour min).
3. Choisir la variable entrante : le plus négatif (max) ou plus positif (min)
dans la ligne Z.
4. Choisir la variable sortante : plus petit ratio non négatif.
5. Pivotement : opération pour avoir 1 à l’élément pivot, 0 ailleurs dans
la colonne.
6. Répéter jusqu’à optimalité.
Variables artificielles : Utiliser la méthode M ou la méthode à deux
phases pour les éliminer.
Cas particuliers :
— Solutions multiples : un coefficient nul non de base à l’optimum.
— Problème illimité : tous les coefficients de la colonne entrante sont
≤ 0.
— Dégénérescence : ratio minimal nul.
— Pas de solution réalisable : variable artificielle positive à la fin de la
phase 1.
3. Méthode Primale-Duale
Chaque programme linéaire (primal) a un programme linéaire dual as-
socié.
2
Formulation
Primal (maximisation) :
Maximiser Z = c1 x1 + c2 x2 + ... + cn xn
sous a11 x1 + a12 x2 + ... + a1n xn ≤ b1
..
.
am1 x1 + am2 x2 + ... + amn xn ≤ bm
xj ≥ 0 ∀j
Dual :
Minimiser W = b1 y1 + b2 y2 + ... + bm ym
sous a11 y1 + a21 y2 + ... + am1 ym ≥ c1
..
.
a1n y1 + a2n y2 + ... + amn ym ≥ cn
yi ≥ 0 ∀i
Théorèmes de la dualité
— Dualité faible : Si x est admissible pour le primal et y pour le dual,
alors Z(x) ≤ W (y).
— Dualité forte : Si le primal (ou dual) a une solution optimale finie,
alors les deux en ont une, et Zopt = Wopt .
— Complémentarité :
- yi∗ ai1 x∗1 + ... + ain x∗n − bi = 0
- x∗j a1j y1∗ + ... + amj ym ∗
− cj = 0
Utilité : Méthode primale-duale utile si solution duale admissible facile
à trouver.
Fiche de Référence Rapide
— Graphique (2 variables) : Tracer, intersection, sommets, évaluer
Z, choisir optimum.
— Simplexe : Forme standard, tableau, entrante/sortante, pivot, répéter.
— Primale-duale : Formuler dual, appliquer théorèmes de dualité et
complémentarité.