Cours sur l'algorithme du simplexe

Chapitre 3Algorithme du simplexe3.1 Solution de base admissibleP en forme standard.1 nA = (a ,...,a )Hypoth`ese : n≥ m (plus de variables que d’´equations) et rg(A)=m (pas d’´equationinutile).Donc apr`es rearrangement des vecteurs on peut ´ecrirei i i i1 m m+1 nA = (a ,...,a ,a ,...,a )avec les m premiers vecteurs ind´ependants c.a.d.A = B +N avec B(m,m) de rang m. D’ou` !xBAx = b iff (B +N) = bxNce qui donne−1 −1x = B b+B N(−x )B N−1Definition 1 B est appel´ee une base et x = B b la solution de base associ´ee `a BBSi x ≥ 0 alors (x ,0) est une solution admissible de P. Deux id´ees `a retenir pour laB Bsuite :– unesolutiondebaseadmissibleestunsommetdupolyh`edred´efiniparlescontraintes.– Lesimplexe va fairepasser d’une solutionde baseadmissible `a une autrequiam´eliorela fonction objectif.3.2 SolutiondebaseadmissibleetpolytopedescontraintesOn consid`ere que des polyh`edres situ´e dans l’orthant positif (x ≥ 0 pour i = 1,...,n).iLes´equationsded´efinitionssontdonc:des´equationsd’hyperplansetlescontraintesx ≥ 0.i12 CHAPITRE 3. ALGORITHME DU SIMPLEXEPremier r´esultat : on suppose que Ax = b,x≥ 0 avec rang(A) = m d´efinit un ensemblen−mborn´e. Alors c’est un polytope deR .Deuxi`eme r´esultat : x est une solution de base admissible ssi x correspond `a unB Bsommet du polytope associ´e.Le polytope associ´e `aAx = bx≥ 0−1 −1donne x = B b+B N(−x ) avec x ,x ≥ 0, c.a.d.B N B N−1 −1B N(x )≤ B bNx ≥ 0Nn−mce qui donne bien un polytope deR ...