grupp: 41 namn1: Adam Hahne namn2: Carl Josefsson ************************************************************ 41 Adam Hahne 8011056614 Carl Josefsson 7803264899 Retur 1: vi har rättat till uppgift 4 & 7. --------- Uppgift 1 Optimalvärdet: 50 --------- Uppgift 2 Introducerar slackvariabler, x4,x6 och excessvariabel x5. Vi lägger till en artificiell variabel, x7 till det bivillkor som har excessvariabel, och tar de tre linjärt oberoende kolumner som bas, x4, x6, x7. Ändrar målfunktionen till att vara: mininimera zprim, zprim = x7 Och får med denna bas en reducerad kostnad som har största negativa värde i x2 och byter därför ut x7 med x2 i basen eftersom x7 är den artificiella variabeln, och får ett optimalvärde zprim=0 Vi har alltså en feasibel-initial-bas att börja lösa vårat problem med. Med x2,x4,x6 som bas i problemet har reducerade-kostnads-vektorn ett negativt element i x1 och värdet tillhörande x2 är minst så de får byta plats -> x1,x4,x6 som bas och som är optimal. Reducerade-kostnads-vektorn är ickenegativ och extrempunkten (10,0,0,10,0,50) är godkänd och optimal. Optimalvärde: 10 --------- Uppgift 3 Introducerar slackvariabler, x4 och excessvariabel x5, x6. Vi lägger till två artificiella variabler, x7, x8 till det bivillkor som har excessvariabel, och tar de tre linjärt oberoende kolumnerna som bas, x4, x7, x8. Ändrar målfunktionen till att vara: mininimera zprim, zprim = x7+x8 Och får med denna bas en reducerad kostnad som har största negativa värde i x2 och byter därför ut x8 med x2 i basen p.g.a kvottest, och får inget optimalvärde eftersom x3 är negativ p.s.s. byts x3 <-> x4 och får en reducerad-kostnads-vektor som är icke negativ men zprim = 0,5 > 0 och därför finns ingen optimallösning till problemet! Vi har alltså ingen feasibel-initial-bas att börja lösa vårat problem med. Optimallösning: Saknas Uppgift: 4 max -2y1' + y2 + y3 2y1' -3y2 0 <= 4 A= -y1' 0 y3 <= 10 y1' -y2 y3 >= 4 y1', y2, y3 >= 0 Problemet är obegränsat vilket stämmer överens med teorin som säger att om det Primala problemet är infeasible så är det Duala problemet obegränsat, som här, eller infeasible. Uppgift 5 Introducerar slackvariabler, x4, x5, x6 och tar deras tre kolumner x4, x5, x6 som linjärt oberoende bas. Vi får med denna bas en reducerad kostnad som har största negativa värde i x3 och byter denna med x5 eller x6 eftersom dom ger samma resultat efter kvottest. Vi väljer x6. Vi får med denna bas en reducerad kostnad som har största negativa värde i x1 och byter därför ut x1 med x5 i basen p.g.a kvottest, och får ett optimalvärde eftersom den reducerade-kostnads-vektorn är positiv och punkten är feasible. Med basen x1, x3, x4. Optimallösning: 35/2 i (0,0,5/2,1/2,0,0) Uppgift 6 Vi lägger den nya variabeln som x4. Den nya variabelns reducerade kostnad i basen x1, x3, x5 blir -1. Vilket innebär att vi kommer att få en annan optimallösning än i föregående uppgift. Optimallösning: 56/3 i (13/6,2/3,0,3/2,0,0,0) Vi får en helt annan lösning med alla slackvariabler=0 alltså är bivillkoren precis uppfyllda. Uppgift 7 optimalbas i uppgift 5: x1, x3, x4 skuggpriset blir 8/3. Detta får vi fram genom att lösa det duala problemet. min 8y1 + 5y2 + 10y3 y1 + 2y2 + 3y3 >= 6 2y1 + y2 + 3y3 >= 4 3y1 + 2y2 + 4y3 >= 7 3y1 + + y3 >= 2 y1, y2, y3 >= 0 som ger samma optimalvärde: 56/3 i punkten (2/3,8/3,0,0,0,1/3). Skuggpriset för bivilkor 2 är därmed 8/3 och vi bör därför få 56/3 + 8/3 = 64/3 som optimalvärde om vi ökar bivilkor 2 från 5 till 6. Kontroll i matlab ger inte detta resultat utan istället 20 ( < 64/3 ) i (3,0,0,1,2,0,0). Anledningen till att vi inte når till 64/3 är att det är ett teoretiskt max - det tar inte hänsyn till att extrempunkterna flyttas (dvs skärningarna mellan bivillkoren.) Så därför får vi inte ett lika högt värde.