grupp: top02-21 namn1: TRONDSEN EINAR 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 1 0 0 1 2 1 2 0 1 0 0 3 3 4 0 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: Med optimal basis som i oppgave 5 er skuggpriset 3/2 for bivilkår 2. Med höyreleddskoeffisienten til bivilkår 2 endret fra 5 til 6, vil vi forvente å få en ny optimalverdi. ``Skuggpriset'' angir kostnaden for en endring på en enhet i betingelsene. Dette gir, siden vi har et maksmumsproblem; z= 35/2 + 3/2 = 38/2 = 19 Kontrollert med matlab 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 6 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 = [2 1 3]T Optimalverdi z = 19