grupp: 12 namn1: Göran M Johansson namn2: ************************************************************ *********************************** *********************************** INLÄMNING AV RETUR Ändringar berör endast de sista kommenterande textraderna i uppgift 7 och har markerats med ÄNDRAT. Den gamla felaktiga textraderna har markerats FELAKTIGT. Laboration 1 i kursen Tillämpad Optimering TMA945 februari 2002 Göran M Johansson 750601-4955 goran.x.johansson@emw.ericsson.se eller goranjoh@tiscali.se Grupp top02-12 GRUPP 12 *********************************** *********************************** Allmänt: Alla uppgifter har först skrivits om på standardform enligt kursbokens kapitel 4.2. Maximeringsproblemen har skrivits om till minimeringsproblem även om detta ej är nödvändigt: min z=c*x, då A*x=b, x>=0 där c=[cB cN] Koefficienter till målfunktionen cB=koefficienter hos målfunktion som hör till basvariabler cN=koefficienter hos målfunktion som hör till ickebasvariabler b=ickenegativ högerled A=[B N] bivillkorsmatris B=del av bivillkorsmatris som hör till basvariabler N=del av bivillkorsmatris som hör till ickebasvariabler y=cB*inv(B) skuggpriser xB=inv(B)*b basvariabler cN=cN-y*N reducerad kostnad Ai=i:te kolumnen hos A AAi=inv(B)*Ai kolumn för ratiotest (xB./AAi) Variabeln med motsvarande mest negativa reducerad kostnad har valts som inkommande variabel. Kriteriet minratio för val av utgående variabel har tillämpats i alla uppgifter. *********************************** *********************************** Uppgift 1: Maximeringsproblemet i uppgiften kan skrivas om till följande minimeringsproblem: min c*x då A*x, x>=0, c=[ -2 -4 -3 0 0 0 ]; b=[ 30 24 60 ]'; A=[ 1 3 2 1 0 0 ; 1 1 1 0 1 0 ; 3 5 3 0 0 1 ]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=6. Iteration nummer 1 Nuvarande målfunktionsvärde z=0 Index hos basvariabler ( x4 x5 x6 ) Baskoefficienter hos målfunktion cB=[ 0 0 0 ] Index hos ickebasvariabler ( x1 x2 x3 ) Reducerad kostnad ccN=cN-y*N=[-2 -4 -3 ] Välj den mest negativa ccN dvs x2 som inkommande variabel. Kolumnen inv(B)*Ai=[ 3 1 5 ]' Basvariabler xB=inv(B)*b=[30 24 60 ]' Välj en strikt positiv kvot tex x4 (med min kvot=10) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=-40 Index hos basvariabler ( x2 x5 x6 ) Baskoefficienter hos målfunktion cB=[-4 0 0 ] Index hos ickebasvariabler ( x1 x4 x3 ) Reducerad kostnad ccN=cN-y*N=[ -2/3 4/3 -1/3] Välj den mest negativa ccN dvs x1 som inkommande variabel. Kolumnen inv(B)*Ai=[ 1/3 2/3 4/3 ]' Basvariabler xB=inv(B)*b=[ 10 14 10 ]' Välj en strikt positiv kvot tex x6 (med min kvot=7.5) lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=-45 Index hos basvariabler ( x2 x5 x1 ) Baskoefficienter hos målfunktion cB=[ -4 0 -2] Index hos ickebasvariabler ( x6 x4 x3 ) Reducerad kostnad ccN=cN-y*N=[ 1/2 1/2 -1/2 ] Välj den mest negativa ccN dvs x3 som inkommande variabel. Kolumnen inv(B)*Ai=[ 3/4 1/2 -1/4 ]' Basvariabler xB=inv(B)*b=[ 15/2 9 15/2 ]' Välj en strikt positiv kvot tex x2 (med min kvot=10) lämnar basen. Iteration nummer 4 Nuvarande målfunktionsvärde z=-50 Index hos basvariabler ( x3 x5 x1 ) Baskoefficienter hos målfunktion cB=[ -3 0 -2 ] Index hos ickebasvariabler ( x6 x4 x2 ) Reducerad kostnad ccN=cN-y*N=[ 1/3 1 2/3 ] Målfunktionens värde kan inte minskas mer eftersom de reducerade kostnaderna alla är positiva. Basvariabler xB=inv(B)*b=[ 10 4 10]' En optimal lösning har hittats. Funktionsvärdet hos orginalproblemets målfunktion är z_max=-z=50. *********************************** *********************************** Uppgift 2 fas 1: Fas-1-problemet av minimeringsproblemet i uppgiften kan skrivas på formen: min c*x då A*x, x>=0, c=[ 0 0 0 0 0 0 1 1 1]; b=[ 30 10 40]'; A=[ 2 1 1 1 0 0 1 0 0; 1 2 1 0 -1 0 0 1 0; -1 2 3 0 0 1 0 0 1]; Man kan naturligtvis stryka kolumn 7 och 9 i A och sedananvända (x4 x6 x7) som startbas om man föredrar detta. Antal bivillkor m=3. Antal bas- och ickebasvariabler n=9. Iteration nummer 1 Nuvarande målfunktionsvärde z=80 Index hos basvariabler ( x7 x8 x9 ) Baskoefficienter hos målfunktion cB=[ 1 1 1 ] Index hos ickebasvariabler ( x1 x2 x3 x4 x5 x6 ) Reducerad kostnad ccN=cN-y*N=[ -2 -5 -5 -1 1 -1 ] Välj en av de mest negativa ccN tex x2 som inkommande variabel. Kolumnen inv(B)*Ai=[1 2 2]' Basvariabler xB=inv(B)*b=[30 10 40]' Välj en strikt positiv kvot tex x8 (med min kvot=5) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=55 Index hos basvariabler (x7 x2 x9) Baskoefficienter hos målfunktion cB=[ 1 0 1] Index hos ickebasvariabler (x1 x8 x3 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[0.5 2.5 -2.5 -1 -1.5 -1] Välj den mest negativa ccN dvs x3 som inkommande variabel. Kolumnen inv(B)*Ai=[0.5 0.5 2]' Basvariabler xB=inv(B)*b=[25 5 30]' Välj en strikt positiv kvot tex x2 (med min kvot=10) lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=30 Index hos basvariabler (x7 x3 x9) Baskoefficienter hos målfunktion cB=[1 0 1] Index hos ickebasvariabler (x1 x8 x2 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[ 3 5 5 -1 -4 -1] Välj den mest negativa ccN dvs x5 som inkommande variabel. Kolumnen inv(B)*Ai=[ 1 -1 3]' Basvariabler xB=inv(B)*b=[20 10 10]' Välj en strikt positiv kvot tex x9 (med min kvot=3.3333) lämnar basen. Iteration nummer 4 Nuvarande målfunktionsvärde z=16.6667 Index hos basvariabler (x7 x3 x5) Baskoefficienter hos målfunktion cB=[1 0 0] Index hos ickebasvariabler ( x1 x8 x2 x4 x9 x6) Reducerad kostnad ccN=cN-y*N=[-2.3333 1 -0.33333 -1 1.3333 0.33333] Välj den mest negativa ccN dvs x1 som inkommande variabel. Kolumnen inv(B)*Ai=[ 2.3333 -0.33333 -1.3333]' Basvariabler xB=inv(B)*b=[16.6667 13.3333 3.33333]' Välj en strikt positiv kvot tex x7 (med min kvot=7.1429) lämnar basen. Iteration nummer 5 Nuvarande målfunktionsvärde z=0 Index hos basvariabler (x1 x3 x5) Baskoefficienter hos målfunktion cB=[ 0 0 0] Index hos ickebasvariabler (x7 x8 x2 x4 x9 x6) Reducerad kostnad ccN=cN-y*N=[ 1 1 0 0 1 0] Basvariabler xB=inv(B)*b=[7.14286 15.7143 12.8571]' En optimal lösning med z=0 har hittats till fas-1-problemet. Basen som är optimalt i fas-1-problemet är tillåten i fas-2-problemt och kan användas som en startbas. *********************************** *********************************** Uppgift 2 fas 2: Minimeringsproblemet i uppgiften kan skrivas på formen: min c*x då A*x, x>=0, c=[ 1 3 2 0 0 0]; b=[ 30 10 40]'; A=[ 2 1 1 1 0 0; 1 2 1 0 -1 0; -1 2 3 0 0 1]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=6. Iteration nummer 1 Nuvarande målfunktionsvärde z=38.5714 Index hos basvariabler (x1 x3 x5) Baskoefficienter hos målfunktion cB=[1 2 0] Index hos ickebasvariabler (x2 x4 x6) Reducerad kostnad ccN=cN-y*N=[1.4286 -0.71429 -0.42857] Välj den mest negativa ccN dvs x4 som inkommande variabel. Kolumnen inv(B)*Ai=[0.42857 0.14286 0.57143]' Basvariabler xB=inv(B)*b=[7.14286 15.7143 12.8571]' Välj en strikt positiv kvot tex x1 (med min kvot=16.6667) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=26.6667 Index hos basvariabler (x4 x3 x5) Baskoefficienter hos målfunktion cB=[0 2 0] Index hos ickebasvariabler (x2 x1 x6) Reducerad kostnad ccN=cN-y*N=[1.6667 1.6667 -0.66667] Välj den mest negativa ccN dvs x6 som inkommande variabel. Kolumnen inv(B)*Ai=[-0.33333 0.33333 0.33333]' Basvariabler xB=inv(B)*b=[16.6667 13.3333 3.33333]' Välj en strikt positiv kvot tex x5 (med min kvot=10) lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=20 Index hos basvariabler (x4 x3 x6) Baskoefficienter hos målfunktion cB=[0 2 0] Index hos ickebasvariabler (x2 x1 x5) Reducerad kostnad ccN=cN-y*N=[-1 -1 2] Välj en av de mest negativa ccN tex x2 som inkommande variabel. Kolumnen inv(B)*Ai=[-1 2 -4]' Basvariabler xB=inv(B)*b=[20 10 10]' Välj en strikt positiv kvot tex x3 (med min kvot=5) lämnar basen. Iteration nummer 4 Nuvarande målfunktionsvärde z=15 Index hos basvariabler (x4 x2 x6) Baskoefficienter hos målfunktion cB=[0 3 0] Index hos ickebasvariabler (x3 x1 x5) Reducerad kostnad ccN=cN-y*N=[0.5 -0.5 1.5] Välj den mest negativa ccN dvs x1 som inkommande variabel. Kolumnen inv(B)*Ai=[1.5 0.5 -2]' Basvariabler xB=inv(B)*b=[25 5 30]' Välj en strikt positiv kvot tex x2 (med min kvot=10) lämnar basen. Iteration nummer 5 Nuvarande målfunktionsvärde z=10 Index hos basvariabler (x4 x1 x6) Baskoefficienter hos målfunktion cB=[0 1 0] Index hos ickebasvariabler (x3 x2 x5) Reducerad kostnad ccN=cN-y*N=[1 1 1] Basvariabler xB=inv(B)*b=[10 10 50]' En optimal lösning har hittats. Slackvariablerna x4 och x6 finns i den optimala basen. Detta betyder att första och sista bivilkoren är olikheter och inte likheter. Målfunktionskoefficienterna cB för slackvariablerna x4 och x6 har värde 0 så de påverkar inte målfunktionens värde. Variablerna x2, x3 och x5 har också värde 0. *********************************** *********************************** Uppgift 3 inget tillåtet område: Om man studerar bivillkoren ser man att inget tillåtet område finns. Detta kan man tex se om man plottar bivillkoren i matlab: x1=linspace(0,1.5,20); x2=linspace(0,1.5,20); surf(x1,x2,zeros(20,20)); hold on x1=0; x2=1.5; v1=[x1 x2 x2 x1]; y1=0; y2=1.5; v2=[y1 y1 y2 y2]; patch(v1,v2,(2+2*v1-v2),[1 0 0]), disp('under rött plan, 1a biv') patch(v1,v2,(1+3*v1),[.5 1 .5]), disp('över grönt plan, 2a biv') patch(v1,v2,(-1+v2),[0 0 1]), disp('under blått plan, 3e biv') xlabel('x1'), ylabel('x2'), zlabel('x3') Uppgift 3 fas 1: Ett annat sätt att se att inget tillåtet område finns är att lösa fas-1-problemet och få en optimal målfunktion som är skild från noll (dvs att den optimala baslösningen innehåller artificiella variabler): Fas-1-problemet kan skrivas på formen: min c*x då A*x, x>=0, c=[ 0 0 0 0 0 0 1 1 1]; b=[ 2 1 1]'; A=[ -2 1 1 1 0 0 1 0 0; -3 0 1 0 -1 0 0 1 0; 0 1 -1 0 0 -1 0 0 1]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=9. Iteration nummer 1 Nuvarande målfunktionsvärde z=4 Index hos basvariabler (x7 x8 x9) Baskoefficienter hos målfunktion cB=[ 1 1 1] Index hos ickebasvariabler (x1 x2 x3 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[ 5 -2 -1 -1 1 1] Välj den mest negativa ccN dvs x2 som inkommande variabel. Kolumnen inv(B)*Ai=[1 0 1]' Basvariabler xB=inv(B)*b=[2 1 1]' Välj en strikt positiv kvot tex x9 (med min kvot=3) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=2 Index hos basvariabler (x7 x8 x2) Baskoefficienter hos målfunktion cB=[ 1 1 0] Index hos ickebasvariabler (x1 x9 x3 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[ 5 2 -3 -1 1 -1] Välj den mest negativa ccN dvs x3 som inkommande variabel. Kolumnen inv(B)*Ai=[2 1 -1]' Basvariabler xB=inv(B)*b=[1 1 1]' Välj en strikt positiv kvot tex x7 (med min kvot=0.5) lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=0.5 Index hos basvariabler (x3 x8 x2) Baskoefficienter hos målfunktion cB=[ 0 1 0] Index hos ickebasvariabler (x1 x9 x7 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[2 0.5 1.5 0.5 1 0.5] Basvariabler xB=inv(B)*b=[0.5 0.5 1.5]' En optimal lösning har hittats till fas-1-problemet. Dessvärre är målfunktionen skild från noll vilket betyder att inget tillåtet område finns för originalproblemet. *********************************** *********************************** Uppgift 4 fas 1: Corollary 6.1 på sidan 151 i kursboken säger: Om området tillhörande det duala problemet är obegränsat då är området tillhörande det primala problemet ej tillåtet. Fas-1-problemet till dualen av problemet i uppgift 3 kan skrivas på formen: min c*x då A*x, x>=0, c=[ 0 0 0 0 0 0 1 1 1] A=[ 2 -3 0 1 0 0 1 0 0 -1 0 1 0 1 0 0 1 0 1 -1 1 0 0 -1 0 0 1] b=[ 4 10 4]' Antal bivillkor m=3. Antal bas- och ickebasvariabler n=9. Iteration nummer 1 Nuvarande målfunktionsvärde z=18 Index hos basvariabler (x7 x8 x9) Baskoefficienter hos målfunktion cB=[1 1 1] Index hos ickebasvariabler (x1 x2 x3 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[-2 4 -2 -1 -1 1] Välj den mest negativa ccN dvs x1 som inkommande variabel. Kolumnen inv(B)*Ai=[2 -1 1]' Basvariabler xB=inv(B)*b=[4 10 4]' Välj en strikt positiv kvot tex x7 (med min kvot=2) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=14 Index hos basvariabler (x1 x8 x9) Baskoefficienter hos målfunktion cB=[0 1 1] Index hos ickebasvariabler (x7 x2 x3 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[1 1 -2 0 -1 1] Välj den mest negativa ccN dvs x3 som inkommande variabel. Kolumnen inv(B)*Ai=[0 1 1]' Basvariabler xB=inv(B)*b=[2 12 2]' Välj en strikt positiv kvot tex x9 (med min kvot=2) lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=10 Index hos basvariabler (x1 x8 x3) Baskoefficienter hos målfunktion cB=[0 1 0] Index hos ickebasvariabler (x7 x2 x9 x4 x5 x6) Reducerad kostnad ccN=cN-y*N=[ 0 2 2 -1 -1 -1] Välj en av de mest negativa ccN tex x4 som inkommande variabel. Kolumnen inv(B)*Ai=[0.5 1 -0.5]' Basvariabler xB=inv(B)*b=[2 10 2]' Välj en strikt positiv kvot tex x1 (med min kvot=4) lämnar basen. Iteration nummer 4 Nuvarande målfunktionsvärde z=6 Index hos basvariabler (x4 x8 x3) Baskoefficienter hos målfunktion cB=[0 1 0] Index hos ickebasvariabler (x7 x2 x9 x1 x5 x6) Reducerad kostnad ccN=cN-y*N=[1 -1 2 2 -1 -1] Välj en av de mest negativa ccN tex x2 som inkommande variabel. Kolumnen inv(B)*Ai=[-3 1 -1]' Basvariabler xB=inv(B)*b=[4 6 4]' Välj en strikt positiv kvot tex x8 (med min kvot=6) lämnar basen. Iteration nummer 5 Nuvarande målfunktionsvärde z=0 Index hos basvariabler (x4 x2 x3) Baskoefficienter hos målfunktion cB=[0 0 0] Index hos ickebasvariabler (x7 x8 x9 x1 x5 x6) Reducerad kostnad ccN=cN-y*N=[1 1 1 0 0 0] Kolumnen inv(B)*Ai=[-4 -2 -1]' Basvariabler xB=inv(B)*b=[22 6 10]' Region är obegränsad och inget begränsat minimum finns ty komponenterna hos AAi=inv(B)*Ai är alla negativa. Men vi har hittat en tillåten startbas (x2 x3 x4) till fas-2-problemet så vi fortsätter. *********************************** *********************************** Uppgift 4 fas 2: Fas-2-problemet till dualen av problemet i uppgift 3 kan skrivas på formen: min c*x då A*x, x>=0, c=[ 2 -1 -1 0 0 0]; b=[ 4 10 4]'; A=[ 2 -3 0 1 0 0; -1 0 1 0 1 0; 1 -1 1 0 0 -1]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=6. Iteration nummer 1 Nuvarande målfunktionsvärde z=-16 Index hos basvariabler (x2 x3 x4) Baskoefficienter hos målfunktion cB=[-1 -1 0] Index hos ickebasvariabler (x1 x5 x6) Reducerad kostnad ccN=cN-y*N=[-1 2 1] Man kan välja x1 som inkommande men det en inte så mycket gladare. Kolumnen inv(B)*Ai=[-2 -1 -4]' Basvariabler xB=inv(B)*b=[6 10 22]' Region är obegränsad och inget begränsat minimum finns ty komponenterna hos AAi=inv(B)*Ai är alla negativa. Corollary 6.1 på sidan 151 i kursboken överensstämmer med detta. *********************************** *********************************** Uppgift 5: Maximeringsproblemet i uppgiften kan skrivas om till följande minimeringsproblem: min c*x då A*x, x>=0, c=[-6 -4 -7 0 0 0]; b=[8 5 10]'; A=[1 2 3 1 0 0; 2 1 2 0 1 0; 3 3 4 0 0 1]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=6. Iteration nummer 1 Nuvarande målfunktionsvärde z=0 Index hos basvariabler (x4 x5 x6) Baskoefficienter hos målfunktion cB=[0 0 0] Index hos ickebasvariabler (x1 x2 x3) Reducerad kostnad ccN=cN-y*N=[-6 -4 -7] Välj en av de mest negativa ccN tex x3 som inkommande variabel. Kolumnen inv(B)*Ai=[3 2 4]' Basvariabler xB=inv(B)*b=[8 5 10]' Välj en strikt positiv kvot tex x5 (med min kvot=2.5) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=-17.5 Index hos basvariabler (x4 x3 x6) Baskoefficienter hos målfunktion cB=[0 -7 0] Index hos ickebasvariabler (x1 x2 x5) Reducerad kostnad ccN=cN-y*N=[1 -0.5 3.5] Välj en av de mest negativa ccN tex x2 som inkommande variabel. Kolumnen inv(B)*Ai=[0.5 0.5 1]' Basvariabler xB=inv(B)*b=[0.5 2.5 0]' Välj en positiv kvot tex x6 (med min kvot=0) lämnar basen. Problemet kan vara degenererat eftersom inv(B)*b har en komponent som är noll. Se sidan 134 i kursboken. Iteration nummer 3 Nuvarande målfunktionsvärde z=-17.5 Index hos basvariabler (x4 x3 x2) Baskoefficienter hos målfunktion cB=[0 -7 -4] Index hos ickebasvariabler (x1 x6 x5) Reducerad kostnad ccN=cN-y*N=[0.5 0.5 2.5] Basvariabler xB=inv(B)*b=[ 0.5 2.5 0]' En optimal lösning har hittats. Funktionsvärdet hos orginalproblemets målfunktion är z_max=-z=17.5. Slackvariabeln x4 finns kvar i basen vilket betyder att andra bivilkoret är en olikhet och inte en likhet. Målfunktionskoefficienten för x4 är noll och bidrar inte till z. *********************************** *********************************** Uppgift 6: Det fanns ingen optimal bas för problemet i uppgift 4 eftersom det var obegränsat så den optimala basen för problemet i uppgift 5 väljes istället. Man kan använda den optimala basen för problemet i uppgift 5 som startbas xB=(x2 x3 x5). Maximeringsproblemet i uppgiften kan skrivas om till följande minimeringsproblem: min c*x då A*x, x>=0, c=[ -6 -4 -7 -2 0 0 0]; b=[ 8 5 10]'; A=[ 1 2 3 3 1 0 0; 2 1 2 0 0 1 0; 3 3 4 1 0 0 1]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=7. Iteration nummer 1 Nuvarande målfunktionsvärde z=-17.5 Index hos basvariabler (x2 x3 x5) Baskoefficienter hos målfunktion cB=[-4 -7 0] Index hos ickebasvariabler (x1 x4 x6 x7) Reducerad kostnad ccN=cN-y*N=[0.5 -1.5 2.5 0.5] Den reducerade kostnaden för den nya variabeln x4 i basen (x2 x3 x5) är -3/2. Detta är den enda negativa ccN och måste väljas som inkommande variabel. Målfunktionsvärdet är nu samma som för den optimala basen i uppgift 5. Anledningen till att vi nu kan fortsätta med att förbättra målfunktionens värde är att vi nu fått en ny frihetsgrad att röra oss i. Dvs det tillåtna området har utökats och medför nya möjligheter. Kolumnen AAi=B\Ai=[1 0.5 2.5]' Basvariabler xB=inv(B)*b=[0 2.5 0.5]' Problemet är degenererat eftersom inv(B)*b har en komponent som är noll. Se sidan 134 i kursboken. Dvs vi har kommit till en punkt där fler än två bivillkor korsar varandra. Välj en strikt positiv kvot tex x2 (med min kvot=0) lämnar basen. Iteration nummer 2 Nuvarande målfunktionsvärde z=-17.5 Index hos basvariabler (x4 x3 x5) Baskoefficienter hos målfunktion cB=[-2 -7 0] Index hos ickebasvariabler (x1 x2 x6 x7) Reducerad kostnad ccN=cN-y*N=[-1 1.5 -0.5 2] Välj en av de mest negativa ccN tex x1 som inkommande variabel. Kolumnen AAi=B\Ai=[-1 1 1]' Basvariabler xB=inv(B)*b=[0 2.5 0.5]' Välj en strikt positiv kvot tex x5 lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=-18 Index hos basvariabler (x4 x3 x1) Baskoefficienter hos målfunktion cB=[-2 -7 -6] Index hos ickebasvariabler (x5 x2 x6 x7) Reducerad kostnad ccN=cN-y*N=[1 -1 4 -1] Välj en av de mest negativa ccN tex x2 som inkommande variabel. Kolumnen AAi=B\Ai=[-1.5 3 -2.5]' Basvariabler xB=inv(B)*b=[0.5 2 0.5]' Välj en strikt positiv kvot dvs x3 lämnar basen. Iteration nummer 4 Nuvarande målfunktionsvärde z=-18.6667 Index hos basvariabler (x4 x2 x1) Baskoefficienter hos målfunktion cB=[-2 -4 -6] Index hos ickebasvariabler (x5 x3 x6 x7) Reducerad kostnad ccN=cN-y*N=[0.66667 0.33333 2.6667 0] Basvariabler xB=inv(B)*b=[1.5 0.66667 2.1667]' En optimal lösning har hittats. Funktionsvärdet hos orginalproblemets målfunktion är z_max=-z=18.6667. *********************************** *********************************** Uppgift 7: Skuggpriset y=inv(B')*cB för andra bivillkoret i den optimala basen för uppgift 5 är 2.5. Om begränsningen dvs bivillkorets högerled för andra villkoret ökas en enhet kan vi tjäna 2.5 enheter om basen är fortsatt tillåten efter ändringen. Målfunktionens värde skulle då bli 17.5+2.5=19. Den optimala basen för uppgift 5 är (x4 x3 x2) men det är bara x3 som bidrar till optimala målfunktionsvärdet 17.5eftersom x2=0 och x4 är en slackvariabel. Minimeringsproblemet i uppgiften kan skrivas på formen: min c*x då A*x, x>=0, c=[ -6 -4 -7 0 0 0]; b=[ 8 6 10]'; A=[ 1 2 3 1 0 0; 2 1 2 0 1 0; 3 3 4 0 0 1]; Antal bivillkor m=3. Antal bas- och ickebasvariabler n=6. Iteration number 1 Nuvarande målfunktionsvärde z=0 Index hos basvariabler (x4 x5 x6) Baskoefficienter hos målfunktion cB=[0 0 0] Index hos ickebasvariabler (x1 x2 x3) Reducerad kostnad ccN=cN-y*N=[-6 -4 -7] Välj en av de mest negativa ccN tex x3 som inkommande variabel. Kolumnen inv(B)*Ai=[3 2 4]' Basvariabler xB=inv(B)*b=[8 6 10]' Välj en strikt positiv kvot tex x6 (med min kvot=2.5) lämnar basen. Iteration number 2 Nuvarande målfunktionsvärde z=-17.5 Index hos basvariabler (x4 x5 x3) Baskoefficienter hos målfunktion cB=[0 0 -7] Index hos ickebasvariabler (x1 x2 x6) Reducerad kostnad ccN=cN-y*N=[-0.75 1.25 1.75] Välj en av de mest negativa ccN tex x1 som inkommande variabel. Kolumnen inv(B)*Ai=[-1.25 0.5 0.75]' Basvariabler xB=inv(B)*b=[ 0.5 1 2.5]' Välj en strikt positiv kvot tex x5 (med min kvot=2) lämnar basen. Iteration nummer 3 Nuvarande målfunktionsvärde z=-19 Index hos basvariabler (x4 x1 x3) Baskoefficienter hos målfunktion cB=[0 -6 -7] Index hos ickebasvariabler (x5 x2 x6) Reducerad kostnad ccN=cN-y*N=[1.5 0.5 1] Basvariabler xB=inv(B)*b=[3 2 1]' En optimal lösning har hittats. Funktionsvärdet hos orginalproblemets målfunktion är z_max=-z=19. Skuggpriserna y=inv(B')*cB (variablerna hos det duala problemet) är ett mått på de indirekta kostnaderna som hör till bivillkoren. Vi ökade högerledskoefficienten för andra bivilkoret med en enhet. FELAKTIGT: och tjänade 2.5 enheter på målfunktionen vilket var förväntat. ÄNDRING VID RETUR: Optimala målfunktionsvärdet i upp 5 var 17.5 och skuggpriset för andra bivillkoret var 2.5. skillnaden mellan upp5 och upp 7 är att högerledet för andra bivillkoret ökats en enhet i upp 7 jämfört med upp 5. Optimala målfunktionsvärdet i upp 7 blev 19. Anledningen till att vi bara tjänade 19-17.5=1.5 enheter istället för 2.5 som skuggpriset för upp 5 anger är att våra övriga två bivillkor inte tillåter detta.