grupp: top02-21 namn1: Einar Trondsen namn2: ************************************************************ oppgave1: Maximer z=2x(1)+4x(2)+3x(3) A= 1 3 2 1 0 0 1 1 1 0 1 0 3 5 3 0 0 1 b= [ 30 24 60]T x(1), x(2), x(3) er lik eller större enn null gir for basen 1 3 5 ; Redusert kostnad 0 -2/3 0 -1 0 -1/3 1/B*b = [10 4 10]T Optimalverdi z = 50 oppgave2: Minimer z=1x(1)+3x(2)+2x(3) A= 2 1 1 1 0 1 1 2 1 0 -1 0 -1 2 3 0 0 1 b= [30 10 40]T x(1), x(2), x(3) er lik eller större enn null gir for basen 1 4 6 ; Redusert kostnad 0 1 1 0 1 0 1/B*b = [10 10 50]T Optimalverdi z = 10 oppgave3: For primalen Minimer z= 4x(1)+10x(2)-4x(3) A = -2 1 1 1 0 0 0 -3 0 1 0 -1 0 1 0 1 -1 0 0 -1 0 b= [2 1 1]T x(1), x(2), x(3) er lik eller större enn null I tofasemetoden er tileggsvariabler brukt for å danne fase 1 proble- met, hvis formäl er å bestemme en tilatt base for lösningen av det opp- rinnelige settet av betingelser. Hvis betingelsene for det oprinnelige lineäre programmet er tillatt, så vil fase 1 problemet ha en optimalverdi; z'=0. Om de opprinnelige betingelser ikke er tillatt så er z'>0. Fase en for minimeringsproblemet blir: minimer z'= a(1)+a(2)+a(3) A= -2 1 1 1 0 0 -3 0 1 0 1 0 0 1 -1 0 0 1 b= [2 1 1] gir for basen 2 3 5 ; Redusert kostnad 2 0 0 3/2 0 1/2 1/B*b = [1/2 3/2 1/2]T Optimalverdi z' = 1/2 Lösningen av et fase ett problem gir kun en base for en gyldig lös- ning for det opprinnelige problem. Lösningen er ikke optimal. Her er z'>0 hvilket betyr at bivilkårene ikke er forenelig med det opprin- nelige problem. oppgave4: For dualen Maximer z = 2y(1)+y(2)+y(3) A= -2 -3 0 1 0 0 1 0 1 0 1 0 1 1 -1 0 0 1 b= [4 10 -4]T x(1) mindre eller lik null, x(2), x(3) er lik eller större enn null Fase 1 problem blir: maximer z*= a(1)+a(2)+a(3) A= -2 -3 0 1 0 0 1 0 1 0 1 0 1 1 -1 0 0 1 b= [4 10 -4]T gir for basen [2 3 4] redusert kostnad: -4 0 0 0 -2 -2 1/B*b= [10 22 6]T Optimalverdi z*=22 Resultatet for dualen bekrefter resultatet for primalen. Dette betyr at problemet ikke lar seg optimalisere selv om man kan finne en gyldig base. oppgave5: Maximer z= 6x(1)+4x(2)+7x(3) A= 1 2 3 1 0 0 2 1 2 0 1 0 3 3 4 0 0 0 b= [8 5 10]T x(1), x(2),x(3) större eller lik null gir for basen 1 3 4 ; Redusert kostnad 0 -1/2 0 0 -3/2 -1 1/B*b = [0 5/2 1/2]T Optimalverdi z = 35/2 oppgave6: Maximer z= 6x(1)+4x(2)+7x(3)+2x(4) A= 1 2 3 3 1 0 0 2 1 2 0 0 1 0 3 3 4 1 0 0 1 b= [8 5 10]T x(1), x(2),x(3) x(4)större eller lik null Tillagt den nye variabel gis i basen 1 3 4; redusert kostnad 0 1 0 0 -1 -4 1 Den nye variabelens reduserte kostnad i den basis som var optimal for problem 5, er ikke lenger et gyldig optimum. Vi kan se dette i raden for redusert kostnad hvor en ökning i x(n) (her = x(1) eller x(7)), vil före til en ökning i målfunksjonens verdi (siden vi har et maksi- mumproblem) Optimert om får vi: for basen 1 2 4 ; Redusert kostnad 0 0 -1/3 0 -2/3 -8/3 0 1/B*b = [13/6 2/3 3/2]T Optimalverdi z = 56/3 oppgave7: Om det lineäre problem har et komplett sett med slakkvariabler, så er störrelsen av de optimerte dualvariablene de samme som de reduserte kostnadene for slakkvariablene - med motsatt fortegn. For hvert bi- vilkår i primalen er det et bivilkår i dualen. Variablene i dualpro- blemet kalles ``skuggpriser''siden de måler den implisitte kostnaden assosiert med bivilkårene. Fra raden for reduserte kostnader i oppgave 6 kan man finne ``skugg- priset'' som den kostnad som endrer bivilkår 2 fra 5 til 6. Dette ``skuggpriset'' blir 8/3. Med höyreleddskoeffisienten til bivilkår 2 endret fra 5 til 6, vil vi forvente å få en ny optimalverdi. Med base angitt som x(1), x(2), x(4) ser vi at denne ikke lenger er gyldig. Fra rad 2 har vi for inversmatrisen i ugyldig base: [-1/3 -4/3 1] og tilsvarende (1/B)*b element = -2/3 For reduserende kostnad har vi negative elementer og elementer med nuller; [0 0 -1/3 0 -2/3 -8/3 0] Slakken viser oss hvor mye ``luft'' det er i bivilkåret. I denne sammenheng vil slakkvariabelen for bivilkår 2 vise oss hvor langt utenfor optimal base vi befinner oss - hvor mye vi må endre for å nå optimal base. Multiplikatoren for å bringe x(6) inn i bsen er -3/4 som for rad 2 og basen x(1), x(6) og x(4) gir: [1/4 1 -3/4] og tilsvarende (1/B)*b element = 2/3. Det betyr at slakkvariabelen er -4/3. Vi må legge til 4/3 for å nå optimal base. Z= 56/3 + 4/3 = 60/3 Kontrollert med matlab Maximer z= 6x(1)+4x(2)+7x(3)+2x(3) A= 1 2 3 3 1 0 0 2 1 2 0 0 1 0 3 3 4 1 0 0 1 b= [8 6 10]T x(1), x(2),x(3) större eller lik null gir for basen 1 6 4 ; Redusert kostnad 0 -2 -1 0 0 0 -2 1/B*b = [11/4 1/2 7/4]T Optimalverdi z = 20