grupp: 24 namn1: Jaleh Arzani namn2: August Johansson ************************************************************ Grupp 24 Jaleh Arzani August Johansson ---------------- 1. z = 50 2. z = 10 I fas 1 lade vi till extra variabler (a) till samtliga bivillkor, och löste minimeringsproblemet min z = a1+a2+a3. Den bas som gav optimal lösning använde vi sedan som bas i första steget av fas 2, och optimallösningen z = 10 erhölls. 3. Ingen tillåten lösning. Vi lägger till en slackvariabel till bivillkor 1, och drar ifrån två slack- variabler från bivillkoren 2 och 3. Vi har då ingen uppenbar tillåten bas, varför vi måste lägga till extra variabler som i uppgift 2. Efter att ha kört simplexmetoden (fas 1) fick vi att en av de extra variablerna ingick i den optimala basen. Problemet har alltså ingen tillåten lösning. 4. Obegränsad lösning. Studerar vi dualen till problemet i uppgift 3 erhåller vi ett maximerings- problem. Målfunktionen multipliceras således med -1. Eftersom första bi- villkoret är ett för minimeringsproblem onaturligt villkor (mindre eller lika med 2) blir den första variabeln (y1) i det duala problemet också onaturligt, dvs mindre eller lika med noll. Vi byter därför ut y1 mot -y1, och löser det med simplexmetoden. Efter några varv blir alla B^{-1}A(:, i) negativa, vilket innebär att lösningen är obegränsad. Resultaten i uppgifterna 3 och 4 stämmer alltså överens med Corollary 6.1. 5. z = 35/2 Problemet är ett maximeringsproblem, så vi omvandlar det till ett minimerings- problem genom att multiplicera målfunktionen med -1. Detta problem löses som vanligt med simplex-programmet. Resultatet multipliceras med -1 för att vi ska få maximum, vilket här blev 35/2. 6. Nya variabelns reducerade kostnad: -2 z = 56/3 De reducerade kostnaderna cbar i en given bas B ges av cbar = c^T - cB^T B^{-1} A Från uppgift 5 erhölls basvariablerna (x4, x1, x3) vid optimum, dvs matrisen B ges av de kolonner i A som svarar mot just dessa basvariabler. Här har vi 1 1 3 2 0 0 3 A = 0 2 2 1 1 0 0 = (B N) 0 3 4 3 0 1 1 c är de koefficenter i målfunktionen som svarar mot basvariablerna och icke- basvariablerna: c = (cB cN) = (0 -6 -7 -4 0 0 -2) Genom att beräkna cbar fann vi sista elementet till -2, vilket är just den reducerade kostnaden för den nya variabeln. På samma sätt som i uppgift 5 löstes maximeringsproblemet genom att multiplicera målfunktionen med -1, köra simplex-programmet och multiplicera optimala lösningen med -1. Vi erhöll optimalvärdet z = 56/3. 7. Från uppgift 6 fann vi den optimala basen (x1 x2 x7). De reducerade kostnaderna i det duala problemet (skuggpriserna) kan beräknas med y* = (B^{-1})^T cB Med basen ovan och cB = (6 4 2) får vi y* = (2 8 0)/3. Vi sökte skugg- priset för bivillkor två, vilket alltså är 8/3. Ändrar vi högerledet i bi- villkor två i det primala problemet en enhet (från 5 till 6) bör alltså målfunktionen ändras från 56/3 till 56/3+8/3 = 64/3. När vi använder simplexmetoden med det förändrade högerledet får vi dock målfunktionens optimum till 20. Detta beror på att störningen var så stor att vi bytt bas.