Initialisation du simplexe : méthode des deux phases

Thèmes abordés

Initialisation, simplexe, méthode des deux phases, algorithme, hypothèses, P2, propriété

Résumé du document

Algorithme du simplexe :
Nécessite une solution de base admissible initiale x0
Comment déterminer x0 ?
En d'autres termes, comment déterminer le dictionnaire initial ?
C'est le rôle de la Phase I !

Cas simple (déjà vu) :
– PL en forme canonique avec un second
membre b tel que b ³ 0
– On ajoute des variables d'écart, qui
forment la première base
n Cas difficile :
– PL en forme canonique avec un second
membre quelconque
– La méthode précédente est inapplicable !

Extraits

[...] : En partant de -3x1 + 2x2 + x3 = on obtient 3x1 - 2x2 - x3 = 4 puis 3x1 - 2x2 - x3 + x'1 = 4 Base initiale avec variables artificielles s Solution de base admissible : x = 0 (variables de décision ET variables d'écart nulles) y = b (variables artificielles) Matrice de base : B = I (la base est formée des variables artificielles) Quelques remarques Les variables artificielles permettent facilement de définir une base (comme les variables d'écart dans le cas simple) s Comme on a supposé que bi 0 pour tout cette base initiale est bien admissible pour ce nouveau PL s MAIS ceci ne fournit pas toujours une solution admissible au PL initial s Quelques remarques s Exemple : Si, dans 3x1 - 2x2 - x3 + x'1 = on pose s x1 s x'1 = x2 = x3 = 0 - 2x2 = 0 Alors, on obtient s 3x1 s La contrainte 3x1 - 2x2 4 est donc violée Du PL auxiliaire au PL initial Comment alors utiliser le PL auxiliaire (pour lequel on sait déterminer une solution de base admissible initiale) pour trouver une solution admissible au PL initial ? s Idée : résoudre le PL auxiliaire en modifiant la fonction de coût s Nouvelle fonction de coût s Considérons la fonction de coût : min Σi x'i On cherche à minimiser la somme des variables artificielles s Comment relier la valeur (optimale) de cette fonction à l'existence d'une solution de base admissible pour le PL initial ? [...]

[...] Cours 6 : Initialisation du simplexe : méthode des deux phases Introduction s Algorithme du simplexe : Nécessite une solution de base admissible initiale x0 Comment déterminer x0 ? s En d'autres termes, comment déterminer le dictionnaire initial ? s C'est le rôle de la Phase I ! [...]

[...] s Difficulté de la Phase I ? s Cas simple (déjà vu) : PL en forme canonique avec un second membre b tel que b 0 On ajoute des variables d'écart, qui forment la première base PL en forme canonique avec un second membre quelconque La méthode précédente est inapplicable ! s Cas difficile : Rappel : cas simple avec b 0 (hypothèse non générale). [...]

[...] du PL initial k sort de la base, j rentre dans la base s Pivotage du tableau s Un exemple d'élimination impossible s Que se passe-t-il si aucun élément de la sorte n'existe ? Un exemple d'élimination impossible s Cela signifie que la matrice A n'est pas de rang plein la ligne en question correspond à une contrainte redondante, qui peut donc être supprimée x1 + -x1 + 2x2 2x2 4x2 + 3x3 + 6x3 + 9x3 = = = Dictionnaire initial de P2 (cas général) On obtient la solution (dictionnaire) optimale de P2 s Puis, on fait quitter la base à toutes les variables artificielles qui y sont s On obtient le tableau initial de P1 en s supprimant les colonnes associées aux variables artificielles calculant les coûts réduits initiaux Un exemple complet P2 : tableau initial x x x x - x x x x Dernière ligne = -somme des colonnes x x - x x - x x - x x x x - x x x - x - x x x - x - x x x x x1 x Solution optimale de P2 s Valeur optimale = 0 s MAIS x7 est dans la base s P2 : tableau final x x x x4 - x x6 x7 x P1 : tableau initial coûts 2 x x x x4 - x - cT cTBB-1A -cTBB-1b Algorithme du simplexe : version complète s s On dispose à présent d'un algorithme complet pour la résolution de PL Phase I En multipliant certaines contraintes par modifier le PL pour que b 0 Introduire des variables artificielles, et résoudre le PL auxiliaire P2 par simplexe Algorithme du simplexe : version complète s Fin de la Phase I Si la valeur optimale de P2 n'est pas égale à le PL initial P1 n'admet aucune solution admissible STOP Si la ke variable de base est artificielle, choisir sur la ligne k un élément non nul et qui est sur une colonne associée à une variable de P1 : pivoter sur j et k s Si j n'existe pas : la ligne k est redondante s L'enlever (recommencer tant que k existe) Algorithme du simplexe : version complète s Phase II Les variables artificielles et les colonnes correspondantes sont supprimées du tableau La ligne des coûts réduits est calculée (on exprime z en fonction des variables de base) dictionnaire initial Appliquer la méthode du simplexe au dictionnaire obtenu Algorithme du simplexe : version complète Algorithme complet car il peut gérer toutes les issues possibles s Sans cyclage, on a une de ces 4 issues en Phase I en Phase II) : s Le PL n'admet pas de sol. [...]

[...] C'est donc une solution optimale Propriétés de P2 Donc, si P1 possède une solution admissible alors la valeur optimale de P2 est 0 s Contraposée : Si la valeur optimale de P2 est strictement négative, alors P1 ne possède aucune solution admissible s Propriétés de P2 s Si est solution optimale de P2 et si sa valeur est alors : + + . + = 0 D'où : Et donc : Ax* = b et 0 Par conséquent, est une solution admissible pour P1 Bilan de la résolution de P2 s On résout P2 Si est une solution optimale pour P2 et si sa valeur est alors = 0 est une solution admissible pour P1 Si la valeur optimale de P2 est [...]