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 ...
P en forme standard. 1n A= (a , . . . , a) Hypoth`ese:n≥m(g)Am=p(oisne)rtationasd’´equpl(rivadeuseuqselbatauqe´’d inutile). Doncapre`srearrangementdesvecteursonpeute´crire i1imim+1in A= (a , . . . , a , a , . . . , a) avec lesmadnecstnd.a..iveeermsepurctinrsepd´ A=B+NavecB(m, m) de rangm.’D`ou ! xB Ax=biff(B+N) =b xN
ce qui donne
−1−1 xB=B b+B N(−xN)
−1 Definition 1Btspaeeenuep´lsabeteexB=B blasolution de baseaasosice´`eB
SixB≥0 alors (xB,eed´xieu.DePedblissimdanoitulose0)estunrualrioptene`sra suite : –unesolutiondebaseadmissibleestunsommetdupolyh`edred´efiniparlescontraintes. –Lesimplexevafairepasserd’unesolutiondebaseadmissiblea`uneautrequiam´eliore la fonction objectif.
3.2
Solution de base admissible et polytope des contraintes
Premierre´sultat:onsupposequeAx=b, x≥0 avecrang(A) =msemblefinitunene´d n−m borne´.Alorsc’estunpolytopedeR. Deuxie`mere´sultat:xBest une solution de base admissible ssixBun`andopserroc sommetdupolytopeassocie´. Lepolytopeassocie´a` Ax=b x≥0 −1−1 donnexB=B b+B N(−xN) avecxB, xN≥0, c.a.d.
−1−1 B N(xN)≤B b xN≥0
n−m ce qui donne bien un polytope deR. n−m R´eciproquement,e´tantdonne´unpolytopedeReiortrahsnelrpmee´ses,tdnasnoitauq dede´finitionsont: xl≥0 pourl= 1, . . . , n−m l=n−m a Σl=1i,lxl≤bipouri= 1, . . . , n. d’ou xk≥0 pourk= 1, . . . , m l=n−m Σai,lxl+xn=bipouri= 1, . . . , n. l=1 n−m B´neeo,ansscoeia`donxle ˆxdeRobtenu en ne gardant que les valeursxi6∈B. Onadmettraquesi(P)estunpolytopeet(C)estleproble`mestandardassocie´,alors 1.xsolution de base admissible de (C) 2.xˆ le sommet correspondant est un sommet de (P)
3.3
Me´thodedeGaussJordan
3.3.1 Principe du pivotage Lam´ethodedupivot(GaussJordan)pourre´soudreunsyst`emed’´equationline´aire consiste`ait´ererles´etapessuivantes: 1.a`l’e´tapep, choisir une variablexjet une lignertel que le coefficientar,jsoit nonnul 2.gardercetteligneapr`esl’avoirdivis´eeparlecoefficientar,j(pour que le nouveau coefficient dexjsoit 1) ligne r←(ligne r)/ar,j 3.Ajoutercetteligneauxautreslignesapr`esmultiplicationparlecoefficientquipermet de faire disparaitrexj.
ligne i←ligne i−ai,k/ar,jligne r
3.3.
´ METHODE DE GAUSSJORDAN
3
ieme 4.onre´arrangelesvariablesdemani`erea`cequexjsoit lapvariable. Enit´erantetregroupantlesvariablescorrespondantauxpivotsonobtientunematrice ′ (Im, A) avecIlbseraairoeruqcidentspon`aamalediecirt(m´eitntsvLe).,mImssintned´efi une base.
3.3.2Maintenirl’admissibilit´edelabase Leprincipedusimplexeestd’appliquerlam´ethodedepivotagesurunematricequiest ′ d´eja`delaforme(Im, A) et telle que la base soit admissible. On verra comment on peut toujoursseramenera`cecasplustard.Celacorresponda`:
1 a 1 0 . . 0
. 0 1 . . .
. . 0 . . .
. . . . . 0
m a 0 0 . 0 1
m+1 a
.
.
′ A
.
n a
! xB xN
=
b1 . . bm
etou`bi≥0 pouri= 1, . . . , m(sinon la base n’est pas admissible).
Les variablesx1, . . . , xmsont les variables de bases et les variablesxm+1, . . . , xnsont les variableshorsbase.Pouravoirlabaseadmissible,onmetlesvariableshorsbasese´gales`a 0 et la valeur des variables de base se lit sur le tableau :xi=bi. La base est admissible ssi bi>0. Par abus de language, on identifiera la base et ses variables de base. Lepivotageconsistea`choisirunevariablexjishoirsnadabald(esccnoafai`trerreen une colonnejeasabelrdtiriable`afairesor)a`hcioisurenavxr(donc choisir une ligner) cequicorresponda`unpivotar,jq.luentrnondouiˆeit Le pivotage donne un tableau tel que :
4
CHAPITRE 3.
ALGORITHME DU SIMPLEXE
1.ligne r←ligne r/ar,j 2.ligne i←ligne i+ligne r(−ai,j/ar,j) pouri6=r 3. les variablesxjetxrnentsoch´eeeesna´glonoltcajstreec´eemplalocalrapsedenno coefficients multiplicateurs : 1/ar,jsur la ligneret (−ai,j/ar,j) sur les lignesi6=j.
Maintiendel’admissibilit´edelabase.On a une nouvelle base admissible si les nouveaux coefficients pour b sont≥0. Ces coefficients sont : *br/ar,jpour la ligner *bi−br(ai,j/ar,j) Silabasepr´ece´denteestadmissiblelanouvellel’estssi:ar,j>0 etbi/ai,j≥br/ar,j (pour lesitel queai,j>0.)
3.3.3Am´eliorationdelafonctionobjectif Onrajouteauxcalculspr´ece´dentslafonctionobjectif. A=B+NavecB(m, m) de rangmetc= (cB, cN). ce qui donne
M ax z xB
=cBxB+cNxN −1−1 =B b+B N(−xN)
Apr`esremplacement −1−1 M ax z=cBB b−B N xN+cNxN −1 Lepremiertermes’e´critz0=cBB beΣemmocemretdonecestlriecn´toj6∈B(zj−cj)(−xj). On a la forme tableau
Exemple:
z x1 . . xm
=
z0 b1 . . bm
−xm+1
. .
−xj zj−cj α1,j
αm,j
. . . . . .
−xn . . . . .
Lepivotageconsiste`a 1.Choisirunevariable`afairerentrerdansB(unecolonnej) 2.Choisirunevariable`afairesortirdeB(uneligner) 3. Effectuer le pivotage Il faut de plus * Garder l’admissibilite de la base *Ameliorerlafonctionobjectif(aumoinsnepaslade´grader).