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 ...
4.1 Calculd’une Solution de base admissible 4.1.1 Principe Sileprobl`emenedonnepasunebaseadmissiblenaturellementquefaire?Onenfabrique uneavecdesvariablesartificiellesquinecorrespondent`arienmaispermetdede´marrerle simplexemaissurunprobl`emeauxiliairequiaunesolutionannulantlesvariablesartifi ciellessietseulementsileproble`meinitialaunesolution. Onpartd’unproble`meenformestandardaveclescoefficientsbi≥is´ncesesaire(0 multiplierl’e´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 x≥0 ′ demandea`r´esoudreP M axω=−a1−a2. . .−am z=c.x I.a+A.x=b x, a≥0 ′ 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. Oneffectuelesimplexepour´eliminerlesai. Deux souscas : 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.Onl’e´limineetonaunetableaupourd´emarrerlesimplexeavecles variablesinitiales(apr`essuppressiondesvariablesartificielles). 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 yA≥c x≥0y quelconques Si on a une baseBalors y(B+N)≥(cB, cN) c.a.d yB≥cBet yN≥cN −1 On peut choisirytel queyB=cBen prenanty=cBB. De plus on a : −1 cBB N≥cN c’est`adirezj−cj≥0 pour toutjindice de variable horsbase. Ca signifie donc queB re´alisel’optimumSIBest admissible. Cetteremarquedonnelieu`al’algorithmedualdusimplexequipartd’unesituationou` zj−cj≥miadibss(dleesastpesn’sebala`uosiam0bisont<thmeconsiste`a.)0la’Lirog chosir un pivot qui rendent lesbi≥0 tout en maintenant leszj−cj≥0 (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) (zk−ck)/ar,k=M ax{(zj−cj)/ar,j|ar,j<0} 1. Partird’un tableau aveczj−cj≥0 pour toutjhors base. 2.Chercher`aeffectuerunpivotage (a)∃r0tel quebr0<0 maisar,j≥0 pour toutjindice de variable horsbase, 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, br≥0, alors la base actuelle donne l’optimum qui est fini, STOP. (c)unpivotexisteaveclescrite`resdechoixdonne´spr´ece´demment,effectuerle pivotage et aller en 2. Preuve de correction :
Cas de pivotage.Commear,k<0 la nouvelle valeur debrdevient≥0 (mais d’autres peuvent changer de signe). Il faut montrer quezj−cjreste≥0 pour toutj. Le coefficient apre`spivotageest (zj−cj)−(aj,k/ar,k)(zk−ck) quidoitˆetre≥0. 1. siai,k≥0 on a bien une valeur≥0. 2. siai,k>0 on obtient (zj−cj)/aj,k≤(zk−ck)/ar,k cequidonnelere´sultat.
4.3 Analysede l’algorithme dual 4.3.1 Lecturedes variables duales Onpeutde´terminerlesvariablesd’unesolutionoptimaledudualeneffectuantlesim plexe. Onpartd’unproble`meenformecanonique: M axz=cx Ax≤b x≥0 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, e≥0
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 N−cN)(−xN) Les coefficients dexjdanszsont de la formezj−cj(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∗= (y∗1, . . . , y∗m) on a que la valeur de laj −1 composante esty∗j=cBB ej`u’osdle.Duecxsa: 1. Siejest dans la base alorsy∗j= 0 2. Siejest hors basey∗j=zj−cj
Exemple.Leel`emprob M axz= 400x1+ 1200x2 10x1+ 20x2≤1100 x1+ 4x2≤160 x1+x2≤100 xi, ei≥0 introduit trois variables d’ecarte1, e2, e3etapr´escalculs,atelaelbu −e1−e2 z20054000 20 x1= 601/5−1 x225−1/20 1/2 e315−3/20 1/2 donne l’optimum. Si (y∗1, y∗2, y∗3abtles)oeanassoci´easedualey∗3= 0 care3est dans la base ety∗1= 20, y∗2= 200.
4.3.2Interpr´etatione´conomiquedel’algorithmedual Dans un tableauxi=bi+. . .+ (zk−ck)(−xk) sioneffectuel’activite´dexka`ahtueurde1unit´e: z←z−(zk−ck) =z+ (ck−zk) ckce que rapportek,zkce que coutek. Δz=ck−zklecoestldna’aeltmˆugiarvitce´tik Pourkantunevarresponde´actra,irbael’deet´vitiacl’rsloocteevitcfitsck= 0 et Δz=−zk
´ 4.4. ANALYSEDE SENSIBILITE ET POSTOPTIMISATION5 4.4Analysedesensibilite´etPostoptimisation Souventonestamen´e`arecalculerunesolutioncaronmodifielesressourcesoules couts.Plutotquetoutrefaireonpartdelasolutiond´ej`aobtenue.
4.4.1 Modificationdes ressources Onacalcule´unebaseBqui donne l’optimum : −1−1 z=cBB b+ (cBB N−cN)(−xN) −1 xb=B b Si on modifiebenb+ Δb, l’expression dexbnodifi´eeeestm −1 xb=B(b+ Δb) et la fonction objectif devient −1−1 z=cBB(b+ Δb) + (cBB N−cN)(−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 zj−cjncilssonhang´edoo’tnapcstn≥0. −1 Seulepetitedifficult´e:calculerB. 1m Labaseadmissibleded´epartdusimplexecorrespond`adesvecteurs. . . , aa ,. La −1 baseBespocorrd’aund`aevtcrtseuesrltnannodmumitpo’ai1, . . . , 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, ei≥0 On trouve une baseB={x1, x2, e3}et le tableau −e1−e2 z54000 20200 x11= 60/5−1 x225−1/20 1/2 e315−3/20 1/2