Cours sur l'algorithme du simplexe

Description

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 ...

Informations

• Publié par: Shiem
• Nombre de lectures: 54
• Langue: Français

Extrait

Chapitre

3

Algorithme

3.1

du

simplexe

Solution de base admissible

P en forme standard. 1n A= (a , . . . , a) Hypoth`ese:n≥m(g)Am=p(oisne)rtationasd’´equpl(rivadeuseuqselbatauqe´’d inutile). Doncapre`srearrangementdesvecteursonpeute´crire i 1 i m i m+1 i n A= (a , . . . , a , a , . . . , a) avec lesmadnecstnd.a..iveeermsepurctinrsepd´ A=B+NavecB(m, m) de rangm.’D`ou  ! x B Ax=biff(B+N) =b x N

ce qui donne

−1−1 x B =B b+B N(−x N )

−1 Definition 1Btspaeeenuep´lsabeteex B =B blasolution de baseaasosice´`eB

Six B ≥0 alors (x B ,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

Onconsid`erequedespolyhe`dressitu´edansl’orthantpositif(x i ≥0 pouri= 1, . . . , n). Les´equationsded´efinitionssontdonc:des´equationsd’hyperplansetlescontraintesx i ≥0.

1

2

CHAPITRE 3.

ALGORITHME DU SIMPLEXE

Premierre´sultat:onsupposequeAx=b, x≥0 avecrang(A) =msemblefinitunene´d n−m borne´.Alorsc’estunpolytopedeR. Deuxie`mere´sultat:x B est une solution de base admissible ssix B un`andopserroc sommetdupolytopeassocie´. Lepolytopeassocie´a` Ax=b x≥0 −1−1 donnex B =B b+B N(−x N ) avecx B , x N ≥0, c.a.d.

−1−1 B N(x N )≤B b x N ≥0

n−m ce qui donne bien un polytope deR. n−m R´eciproquement,e´tantdonne´unpolytopedeReiortrahsnelrpmee´ses,tdnasnoitauq dede´finitionsont: x l ≥0 pourl= 1, . . . , n−m l=n−m a Σ l=1 i,l x l ≤b i pouri= 1, . . . , n. d’ou x k ≥0 pourk= 1, . . . , m l=n−m Σa i,l x l +x n =b i pouri= 1, . . . , n. l=1 n−m B´neeo,ansscoeia`donxle ˆxdeRobtenu en ne gardant que les valeursx i 6∈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´thodedeGaussJordan

3.3.1 Principe du pivotage Lam´ethodedupivot(GaussJordan)pourre´soudreunsyst`emed’´equationline´aire consiste`ait´ererles´etapessuivantes: 1.a`l’e´tapep, choisir une variablex j et une lignertel que le coefficienta r,j soit nonnul 2.gardercetteligneapr`esl’avoirdivis´eeparlecoefficienta r,j (pour que le nouveau coefficient dex j soit 1) ligne r←(ligne r)/a r,j 3.Ajoutercetteligneauxautreslignesapr`esmultiplicationparlecoefficientquipermet de faire disparaitrex j .

ligne i←ligne i−a i,k /a r,j ligne r

3.3.

´ METHODE DE GAUSSJORDAN

3

ieme 4.onre´arrangelesvariablesdemani`erea`cequex j soit lapvariable. Enit´erantetregroupantlesvariablescorrespondantauxpivotsonobtientunematrice ′ (I m , A) avecIlbseraairoeruqcidentspon`aamalediecirt(m´eitntsvLe).,mI m ssintned´efi une base.

3.3.2Maintenirl’admissibilit´edelabase Leprincipedusimplexeestd’appliquerlam´ethodedepivotagesurunematricequiest ′ d´eja`delaforme(I m , 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

 ! x B x N

=

  b 1 .    . b m

etou`b i ≥0 pouri= 1, . . . , m(sinon la base n’est pas admissible).

Formetableau

Lese´quationspeuvents’e´crire:

x 1 1 0 . 0

. 0 1 . 0

. . 0 . .

. . . . .

. 0 0 . 0

x m 0 0 . 1

x m+1

.

′ A

.

x n

=

b 1 . . b m

Cese´quationsde´finissentlesmelesotpnseavirbapremi`ere:ircr´eestleu

x 1 . . x m

=

b 1 . . b m

−x m+1

.

′ A

.

−x n

Les variablesx 1 , . . . , x m sont les variables de bases et les variablesx m+1 , . . . , x n sont les variableshorsbase.Pouravoirlabaseadmissible,onmetlesvariableshorsbasese´gales`a 0 et la valeur des variables de base se lit sur le tableau :x i =b i . La base est admissible ssi b i >0. Par abus de language, on identifiera la base et ses variables de base. Lepivotageconsistea`choisirunevariablex j ishoirsnadabald(esccnoafai`trerreen une colonnejeasabelrdtiriable`afairesor)a`hcioisurenavx r (donc choisir une ligner) cequicorresponda`unpivota r,j q.luentrnondouiˆeit Le pivotage donne un tableau tel que :

4

CHAPITRE 3.

ALGORITHME DU SIMPLEXE

1.ligne r←ligne r/a r,j 2.ligne i←ligne i+ligne r(−a i,j /a r,j ) pouri6=r 3. les variablesx j etx r nentsoch´eeeesna´glonoltcajstreec´eemplalocalrapsedenno coefficients multiplicateurs : 1/a r,j sur la ligneret (−a i,j /a r,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 : *b r /a r,j pour la ligner *b i −b r (a i,j /a r,j ) Silabasepr´ece´denteestadmissiblelanouvellel’estssi:a r,j >0 etb i /a i,j ≥b r /a r,j (pour lesitel quea i,j >0.)

3.3.3Am´eliorationdelafonctionobjectif Onrajouteauxcalculspr´ece´dentslafonctionobjectif. A=B+NavecB(m, m) de rangmetc= (c B , c N ). ce qui donne

M ax z x B

=c B x B +c N x N −1−1 =B b+B N(−x N )

Apr`esremplacement −1−1 M ax z=c B B b−B N x N +c N x N −1 Lepremiertermes’e´critz 0 =c B B beΣemmocemretdonecestlriecn´to j6∈B (z j −c j )(−x j ). On a la forme tableau

Exemple:

z x 1 . . x m

=

z 0 b 1 . . b m

−x m+1

. .

−x j z j −c j α 1,j

α m,j

. . . . . .

−x n . . . . .

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).