grupp: 19 namn1: Tomas Karlsson namn2: ************************************************************ Lab1 Grupp 19 Tomas Karlsson Rättning av uppg7 Felet var att jag utgick från uppg5 istället för uppg6. Men man gör på precis samma sätt. optmal lösning fför uppg6 är -56/3~=-18.6 med båda baserna (x1 x2 x7)och (x1 x6 x7) är värdet på red kostn för x5=8/3 dvs målfunktionsvärdet borde bli -56/3-8/3=-64/3~=-21.3 Det blir i verkligheten -20. Detta med baserna (x1 x4 x7) Nedan följer gamla inlämningen######################################### Uppg 1-------------------------------------------------------------- c = -2 -4 -3 0 0 0 A = 1 3 2 1 0 0 1 1 1 0 1 0 3 5 3 0 0 1 b = 30 24 60 z=-50 -> orginalproblemets lösning z= 50. med baserna x1,x3,x5 Uppg2----------------------------------------------------------------- ursprungligt problem i stdform: c = 1 3 2 0 0 0 A = 2 1 1 1 0 0 1 2 1 0 -1 0 -1 2 3 0 0 1 b = 30 10 40 fas1: lägg till varabel på rad 2, samt ändra målfunktionen. c = 0 0 0 0 0 0 1 A = 2 1 1 1 0 0 0 1 2 1 0 -1 0 1 -1 2 3 0 0 1 0 ändra målfunktion mha radoperation c = -1 -2 -1 0 1 0 0 välj x4,x6,x7 som basvar. ta x2 som ink. ->x7 byts ut pga lägs kvot. nu kan den sista kolumen tas bort.. och målfunktionen återställas. dvs: c = 1 3 2 0 0 0 A = 2 1 1 1 0 0 1 2 1 0 -1 0 -1 2 3 0 0 1 basvariabler: x2,x4,x6 endast x1 har neg. red. kostn.->ta som ink.var. x2 lägst kvot-> välj bort x2 inga neg. red. kostn->opt.lösn. z=10 basvar:x1,x4,x6 uppg3------------------------------------------------------------ fas 1 med extra var.: c = 3 -1 0 0 1 1 0 0 A = -2 1 1 1 0 0 0 0 -3 0 1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 b = 2 1 1 basv.x4,x7,x8 ink:x2 utg:x8 ink:x3 utg:x4 -> inga fler neg red. kostn. -> ingen lösning kan finnas. uppg4--------------------------------------------------------------------- dualen: max w = 2y1 + y2 + y3 då - 3y2 - 2y3 >=4 y1 + y3 >=10 -y1 + y2 + y3 >=-4 y1 >= 0 ; y2, y3 <= 0 var subst.y2=-y2, y3=-y3 samt mult. med -1 på nedersta raden=> max w = 2y1 - y2 - y3 då + 3y2 + 2y3 >=4 y1 - y3 >=10 y1 + y2 + y3 >=4 y1, y2, y3 >= 0 med extra var.: c = -1 -3 -1 1 1 0 0 0 A = 0 3 2 -1 0 0 1 0 1 0 -1 0 -1 0 0 1 1 1 1 0 0 1 0 0 b = 4 10 4 baser:x6,x7,x8 ink:x2 => 0 i nämn. för x8... ta x7 ink x1 => 0 i nämn. för x2... ta x6 inga fler negativa red. kostn. dvs inga lösningar går att hitta efersom alla extra variabler inte går att ta bort. uppg5----------------------------------------------------------------- För det här probletet blir det bed slackvariabler: c = -6 -4 -7 0 0 0 A = 1 2 3 1 0 0 2 1 2 0 1 0 3 3 4 0 0 1 b = 8 5 10 bas:x4,x5,x6 ink:x3 välj x5 eller x6 jag tar x5 som utg. ink:x2 utg x6 opt. bas: x2,x3,x4 z=-35/2 dvs i org prob. z=35/2 om man väljer x6 i början får man istället basvariabler x1,x3,x4 Värt att anmärka är att red. kostnaden är positiv om man tittar på baserna x1 och x2 i de olika fallen... men det funkar åt båda hållen. Det beror väl på att B^-1*b är 0 för den basen. uppg6------------------------------------------------- c = -6 -4 -7 0 0 0 -2 A = 1 2 3 1 0 0 3 2 1 2 0 1 0 0 3 3 4 0 0 1 1 samma b som tidigare. med baser x2,x3,x4 fås red. kostn. -3/2 ink:x7 utg:x2 ink: x1 utg: x4 ink:x2 utg: x3 opt. provar med x6 som ink. ändå... => x2 utg. dvs x1,x6,x7 eller x1,x2,x7 baser. z=56/3 Kommentar: Eftersom det blir ett helt annat system så är det inte konstingt att det blir annorlunda lösning. Värt att lägga märke till är att när den nya variabeln är 0, så har man samma värde på z som tidigare, OCH det är en giltig lösning. därför kan man veta att det inte skulle bli en sämre lösning än vad man hade tidigare. uppg7------------------------------------------------------- om man ser på x5:s red. kostnad. så beror det på vilken av mina två lösningar man använder. Jag fick ju två olika lösningar. den ena var x1,x3,x4 då har x5 red. kostn 3/5 dvs den maximala lösningen borde bli 35/2+3/2=19 vilket det blir. Om man däremot använder den andra basen x2,x3,x4 så har x5 red. kostn 5/2 vilket skulle ge en lösning på 35/2+5/2=20 Det blir det också, men den lösning är dock inte tillåten, så max är även här 19.