Programmation Linéaire: Séance 2: Solutions Réalisables (Ou Admissibles) Domaine Réalisable Ou Admissible
Programmation Linéaire: Séance 2: Solutions Réalisables (Ou Admissibles) Domaine Réalisable Ou Admissible
Programmation Linéaire: Séance 2: Solutions Réalisables (Ou Admissibles) Domaine Réalisable Ou Admissible
La méthode du simplexe est due à G. Dantzig Une fois l’indice e choisi, il faut déterminer quelle
(1947). Elle comporte 2 phases. variable doit quitter la base. On a Ax = b, on
augmente xe jusqu’à annuler une des variables de
Phase 1 - Initialisation : Trouver une solution de
base réalisable (ou bien détecter l’impossibilité). base (si possible). Cette variable sera alors la
variable sortante. On note Ae la e-ième colonne de
Phase 2 - Progression : On passe d’un sommet à A
un sommet voisin pour augmenter la fonction
objectif (ou bien on détecte une fonction objectif F Ax = b ⇔ ABxB + Aexe = b ⇔ xB = A−B1(b − Aexe)
non majorée). ⇔ xB = xB − A−B1Aexe ⇔ xB = xB − zxe
L’algorithme du simplexe proprement dit : la Si z ≤ 0, on peut augmenter xe autant qu’on veut,
phase 2 on aura toujours la positivité de la variable de base
On dispose d’une solution de base réalisable x xB. La fonction objectif n’est pas majorée sur DR
d’un PL sous forme standard. La matrice A peut i.e. le maximum de F vaut +∞. Dans ce cas,
s’écrire A = (AB | AH ) avec AB une matrice carrée l’algorithme s’arrête.
de taille m × m, inversible, correspondant aux
Sinon il existe zi > 0, pour avoir la positivité (xB)i
variables de base et AH une matrice de taille m ×
−zixe ≥ 0 pour tout i, on choisit la variable sortante
(n − m), correspondant aux variables hors-base.
pour laquelle le rapport (xB)i/zi pour i = 1, · · · , m
avec zi > 0, est le plus petit possible.
On décompose également x = (xB | xH )T . On va
chercher une autre base B∗ et une solution de base
x∗ associée telles que F (x∗) > F (x).