Cours sur le simplexe - Chapitre 4

Publié par

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 ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 18
Nombre de pages : 7
Voir plus Voir moins
Chapitre 4
Compl´ementssurlesimplexe
4.1 Calculd’une Solution de base admissible 4.1.1 Principe Sileprobl`emenedonnepasunebaseadmissiblenaturellementquefaire?Onenfabrique uneavecdesvariablesarticiellesquinecorrespondent`arienmaispermetdede´marrerle simplexemaissurunprobl`emeauxiliairequiaunesolutionannulantlesvariablesarticiellessietseulementsileproble`meinitialaunesolution. Onpartdunproble`meenformestandardaveclescoecientsbiis´ncesesaire(0 multiplierle´quationpar1).Pourchaquee´quationonrajouteunevariableaiet on va mi nimiser la somme desaiuieqe´eremntlevaresimixatage´nasion).Sileprobl`eemo(na`idume initialaunesolutionadmissiblealorsleprobl`emeauxiliaireaunesolutionquidonne0 pour chaqueai. M axz=c.x A.x=b x0 demandea`r´esoudreP M axω=a1a2. . .am z=c.x I.a+A.x=b x, a0 Cas 1 :prleel`eombPa une solution optimale avecω <0. AlorsPn’a pas de solution. Cas 2 :blrome`elpePa une solution optimale avecω= 0. AlorsPa une base admissible. Oneectuelesimplexepour´eliminerlesai. Deux souscas : 1. onobtient une base admissible ne contenant pas de variableaiciineceuxo:´nlemi etonauntableaupourd´emarrerlesimplexeaveclesvariablesinitiales. 1
2
´ CHAPITRE 4.COMPLEMENTS SUR LE SIMPLEXE
2. labase admissible contient encore desai: ils valent 0 et alors la ligne correspondante estredondante.Onle´limineetonaunetableaupourd´emarrerlesimplexeavecles variablesinitiales(apr`essuppressiondesvariablesarticielles). Remarque : dans le pivotage on ne fait jamais rentrer deai. De plus il est inutile de calculer les coefficients d’unaiqu’on fait sortir.
4.2 Algorithmedual 4.2.1 Principe Onconsid`erelesdeuxproble`mes: primal dual M axz=in ωcx M=yb Ax=b yAc x0y quelconques Si on a une baseBalors y(B+N)(cB, cN) c.a.d yBcBet yNcN 1 On peut choisirytel queyB=cBen prenanty=cBB. De plus on a : 1 cBB NcN cest`adirezjcj0 pour toutjindice de variable horsbase. Ca signifie donc queB re´aliseloptimumSIBest admissible. Cetteremarquedonnelieu`alalgorithmedualdusimplexequipartdunesituationou` zjcjmiadibss(dleesastpesnsebala`uosiam0bisont<thmeconsiste`a.)0laLirog chosir un pivot qui rendent lesbi0 tout en maintenant leszjcj0 (situation duale de l’algorithme du simplexe).
4.2.2 Algorithme Choix du pivot : choisir une ligneitel quebr<0 et une colonnektelle que (i)ar,k<0, (ii) (zkck)/ar,k=M ax{(zjcj)/ar,j|ar,j<0} 1. Partird’un tableau aveczjcj0 pour toutjhors base. 2.Chercher`aeectuerunpivotage (a)r0tel quebr0<0 maisar,j0 pour toutjindice de variable horsbase, alors pas d’optimum fini pour le dual donc pas de solution pour le primal, STOP.
4.3. ANALYSEDE L’ALGORITHME DUAL
3
(b)r, br0, alors la base actuelle donne l’optimum qui est fini, STOP. (c)unpivotexisteaveclescrite`resdechoixdonne´spr´ece´demment,eectuerle pivotage et aller en 2. Preuve de correction :
Cas de pivotage.Commear,k<0 la nouvelle valeur debrdevient0 (mais d’autres peuvent changer de signe). Il faut montrer quezjcjreste0 pour toutj. Le coefficient apre`spivotageest (zjcj)(aj,k/ar,k)(zkck) quidoitˆetre0. 1. siai,k0 on a bien une valeur0. 2. siai,k>0 on obtient (zjcj)/aj,k(zkck)/ar,k cequidonnelere´sultat.
Casdoptimuminni.A faire.
Terminaison.unse`eernuioliticelgemmorquelalutmontreetmrniseogirhtempeon lar`egledeBland.
4.3 Analysede l’algorithme dual 4.3.1 Lecturedes variables duales Onpeutde´terminerlesvariablesdunesolutionoptimaledudualeneectuantlesimplexe. Onpartdunproble`meenformecanonique: M axz=cx Axb x0 1n La matrice A est une suite de vecteurs colonne. . . , aa ,. Onobtientunproble`meenformestandardparajoutdevariabled´ecarteiet chaque eis´eiaetesscoavira`alableyidu dual.
M axz=cx+ 0.e Ax+Ie=b x, e0
4
´ CHAPITRE 4.COMPLEMENTS SUR LE SIMPLEXE
1n ce qui donne une nouvelle matriceA=A, Ide vecteurs colonne. . . , aa ,, e1, . . . , emqu’on ′ ′ 1n+m peut´ecrire. . . , aa ,te,abaldaesssimibleded´eparteste1, . . . , em. Pour la baseBon a une forme tableau qui correspond pourz`a: 1 z=zO+ (cBB NcN)(xN) Les coefficients dexjdanszsont de la formezjcj(et valent 0 pour les variables de 1 base). Pourejtracabled´eunevaricj= 0 et le coefficient vautzj. De plus on azj=cBB ej dans ce cas. 1 cBBest un vecteury= (y1, . . . , ym) avec de plusyj=yej(carejvaut 0 partout sauf eme sur sajcodoor´enniuqe1tse.) 1eme A l’optimumy=cBB´nE.ntvariecy= (y1, . . . , ym) on a que la valeur de laj 1 composante estyj=cBB ej`uosdle.Duecxsa: 1. Siejest dans la base alorsyj= 0 2. Siejest hors baseyj=zjcj
Exemple.Leel`emprob M axz= 400x1+ 1200x2 10x1+ 20x21100 x1+ 4x2160 x1+x2100 xi, ei0 introduit trois variables d’ecarte1, e2, e3etapr´escalculs,atelaelbu e1e2 z20054000 20 x1= 601/51 x2251/20 1/2 e3153/20 1/2 donne l’optimum. Si (y1, y2, y3abtles)oeanassoci´easedualey3= 0 care3est dans la base ety1= 20, y2= 200.
4.3.2Interpr´etatione´conomiquedelalgorithmedual Dans un tableauxi=bi+. . .+ (zkck)(xk) sioneectuelactivite´dexka`ahtueurde1unit´e: zz(zkck) =z+ (ckzk) ckce que rapportek,zkce que coutek. Δz=ckzklecoestldnaaeltmˆugiarvitce´tik Pourkantunevarresponde´actra,irbaeldeet´vitiaclrsloocteevitctsck= 0 et Δz=zk
´ 4.4. ANALYSEDE SENSIBILITE ET POSTOPTIMISATION5 4.4Analysedesensibilite´etPostoptimisation Souventonestamen´e`arecalculerunesolutioncaronmodielesressourcesoules couts.Plutotquetoutrefaireonpartdelasolutiond´ej`aobtenue.
4.4.1 Modificationdes ressources Onacalcule´unebaseBqui donne l’optimum : 11 z=cBB b+ (cBB NcN)(xN) 1 xb=B b Si on modifiebenb+ Δb, l’expression dexbnodi´eeeestm 1 xb=B(b+ Δb) et la fonction objectif devient 11 z=cBB(b+ Δb) + (cBB NcN)(xN) Deux cas : 1. soitla base reste admissible et on a l’optimum, 2. soit la base n’est plus admissible, alors on peut utiliser l’algorithme dual (car les zjcjncilssonhang´edootnapcstn0. 1 Seulepetitedicult´e:calculerB. 1m Labaseadmissibleded´epartdusimplexecorrespond`adesvecteurs. . . , aa ,. La 1 baseBespocorrdaund`aevtcrtseuesrltnannodmumitpoai1, . . . , aim.Bnopsa`dcreor l’expression des vecteurs de la nouvelle base dans l’ancienne : si un vecteur est dans les deuxbasesalorsonalacolonnecorrespondantedelamatriceidentit´e.sinononprendla colonnequicorrespond`auvecteur. Exemple. M axz= 400x1+ 1200x2 10x1+ 20x2+e1= 1100 x1+ 4x2+e2= 160 x1+x2+e3= 100 xi, ei0 On trouve une baseB={x1, x2, e3}et le tableau e1e2 z54000 20200 x11= 60/51 x2251/20 1/2 e3153/20 1/2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.