Cours sur le simplexe - Chapitre 4

Chapitre 4Compl´ements sur le simplexe4.1 Calcul d’une Solution de base admissible4.1.1 PrincipeSileprobl`emenedonnepasunebaseadmissiblenaturellementquefaire?Onenfabriqueune avec des variables artificielles qui ne correspondent `a rien mais permet de d´emarrer lesimplexe mais sur un probl`eme auxiliaire qui a une solution annulant les variables artifi-cielles si et seulement si le probl`eme initial a une solution.On part d’un probl`eme en forme standard avec les coefficients b ≥ 0 (si n´ecessaireimultiplier l’´equation par -1). Pour chaque ´equation on rajoute une variable a et on va mi-inimiser la somme des a (ou de mani`ere´equivalente maximiser sa n´egation). Si le probl`emeiinitial a une solution admissible alors le probl`eme auxiliaire a une solution qui donne 0pour chaque a .iMax z = c.xA.x = bx≥ 0′demande `a r´esoudre PMax ω =−a −a ...−a1 2 mz = c.xI.a+A.x = bx,a≥ 0′Cas 1 : le probl`eme P a une solution optimale avec ω < 0. Alors P n’a pas de solution.′Cas2: leprobl`emeP aunesolutionoptimaleavecω = 0.AlorsP aunebaseadmissible.On effectue le simplexe pour ´eliminer les a . Deux sous-cas :i1. on obtient une base admissible ne contenant pas de variable a : on ´elimine ceux-ciiet on a un tableau pour d´emarrer le simplexe avec les variables initiales.1´2 CHAPITRE 4. COMPLEMENTS SUR LE SIMPLEXE2. la base admissible contient encore des a : ils valent 0 et alors la ligne correspondanteiest redondante. On l’´elimine et on a une tableau pour ...