grupp: 34
namn1: Freyr Hermannsson
namn2: Jonas Andersson
************************************************************
Uppgift 1

Svar: z*=50

Uppgift 2

Svar: z*=10. Vi har en unik optimal lösning, ty den reducerade kostnadsvektorn är strikt större än 0.

Uppgift 3

Svar: När det artificiella LP-problemet löses fås w*=1/2. Detta innebär att det inte existerar någon tillåten baslösning i det ursprungliga problemet. För att det ska finnas en tillåten baslösning till det ursprungliga problemet måste w*=0. Det som sker i fas1, dvs när man itererar fram w*, är att man minimerar avståndet till en tillåten punkt i det ursprungliga problemet. Om w*=0 så är således den framitererade baslösningen en tillåten baslösning i det ursprungliga problemet. Om w* är skilt från noll så saknar det ursprungliga problemet lösning, ty vi hittar ingen tillåten startbaslösning. 

Uppgift 4

Svar: Eftersom B^-1*A(:,i) är negativ för alla element så har vi inga "kandidater" för "ratiotestet". Den inkommande variabeln x1 kan ökas obegränsat och målfunktionsvärdet går mot plus oändligheten, eftersom vi har ett maxproblem. Såleses finns ingen ändlig lösning utan lösningen är obegränsad. Det duala problemets optimallösning hör ihop med det primala problemets tillåtna baslösning. Eftersom det inte finns någon tillåten baslösning till det primala problemet, så kan det inte existera någon ändlig optimal lösning till det duala problemet, enligt satsen om stark dualitet.

Uppgift 5

Svar: z*=35/2. Den reducerade kostnaden är strikt mindre än noll, vilket innebär att vi har ett unikt optimum. Om det finns ett i sådant att (B^-1*b)(i)=0 så är lösningen degenererad. Detta gäller i vårt fall. Således har vi två degenererade optimala baslösningar. De två tillåtna baslösningarna är (x1,x3,s1) och (x2,x3,s1).

Uppgift 6

Svar: Den nya variabelns reducerade kostnad i den bas som var optimal för uppgift 5 är 3/2. Således kan vi öka målfunktionsvärdet genom att välja den nya variabeln som inkommande variabel. Den nya optimala lösningen blir z*=56/3.

Uppgift 7

Svar: Skuggpriset för bivillkor 2 är 8/3. Skuggpriserna är den optimala lösningen till det duala problemet. (y*)^T=(cB)^T*B^-1, där B är den optimla basen för det primala problemet. Tolkningen av skuggpriset är hur mycket målfunktionsvärdet ändras vid en enhetshöjning av högerledskoefficienten i bivillkoret. Således bör det nya målfunktionsvärdet bli 56/3+8/3=64/3. Men om man löser problemet får man z*=20. Detta beror på att det sker ett basbyte eftersom den gamla optimala basen inte är tillåten då vi ändrar högerledet med en enhet. Man har ett bivillkor som begränsar så att man inte kan utnyttja hela höjningen i högerledet.