grupp: top02-54 namn1: Love Lindholm namn2: ************************************************************ %UPPGIFT 1 %%%%%%%%%% * Den optimala basen är (x1,x3,x5) med optimalvärde 50. %UPPGIFT 2 %%%%%%%%%% * Vi adderar slack-variabler och erhåller: min z = x1 + 3x2 + 2x3 då 2x1 + x2 + x3 + x4 = 30 x1 + 2x2 + x3 -x5 = 10 -x1 + 2x2 + 3x3 + x6 = 40 x1,x2,x3,x4,x5,x6 => 0 * Här finns ingen uppenbar kandidat till bas; i villkor 2 kan vi ej välja x5, ty då skulle x5 = -10 < 0. Vi lägger till en artificiell variabel till villkor 2 och erhåller fas 1 problemet: min z = a1 då 2x1 + x2 + x3 + x4 = 30 x1 + 2x2 + x3 -x5 +a1 = 10 -x1 + 2x2 + 3x3 + x6 = 40 x1,x2,x3,x4,x5,x6,a1 => 0 * Vår initiala bas blir (x4,a1,x6). Efter en iteration har vi en ny bas (x2,x4,x6) som är optimal med optimalvärdet 0. a1 är nu överflödig i villkor 2, och vi kan lyfta bort vår artificiella variabel. * Vi kan nu lösa fas 2 problemet med (x2,x4,x6) som initial bas. Efter en iteration finner vi att (x1,x4,x6) är en optimal bas med optimalvärde 10. %UPPGIFT 3 %%%%%%%%%% * Vi adderar slack-variabler och erhåller: min z = 4x1 + 10x2 - 4x3 då -2x1 + x2 + x3 + x4 = 2 -3x1 x3 - x5 = 1 x2 - x3 - x6 = 1 x1,x2,x3,x4,x5,x6 => 0 * Här får vi addera artificiella variabler till villkor 2 och 3 och erhåller fas 1 problemet: min z = a1 + a2 då -2x1 + x2 + x3 + x4 = 2 -3x1 x3 - x5 + a1 = 1 x2 - x3 - x6 + a2 = 1 x1,x2,x3,x4,x5,x6,a1,a2 => 0 * Den initiala basen blir (x4,a1,a2) * x2 har nu negativ reducerad kostnad och kommer in i basen medan a2 försvinner ut. Med den nya basen (x2,x4,a1) blir a2 överflödig. * x3 kommer nu in i basen och x4 försvinner ut. Med den nya basen (x2,x3,x7) är alla reducerade kostnader större än 0, varför basen är optimal. Optimalvärdet är 1/2 > 0 och a1 har värdet 1/2. Således kan vi inte eliminera de artificiella variablerna ur basen och vårt ursprungsproblem, fas 2 problemet, saknar lösning. %UPPGIFT 4 %%%%%%%%%% * Genom att multiplicera villkor 1 i problemet i uppgift 3 med -1 får vi det på kanonisk form: min z = 4x1 + 10x2 - 4x3 då 2x1 - x2 - x3 => -2 -3x1 x3 => 1 x2 - x3 => 1 x1,x2,x3 => 0 * Dualen blir då max w = -2y1 + y2 + y3 då 2y1 - 3y2 =< 4 - y1 + y3 =< 10 - y1 + y2 - y3 =< 4 y1,y2,y3 => 0 * Vi multiplicerar målfunktionen med -1 och lägger till slackvariabler för att få dualen på standardform: min -w = 2y1 - y2 - y3 då 2y1 - 3y2 + y4 = 4 - y1 + y3 + y5 = 10 - y1 + y2 - x3 + y6 = 4 y1,y2,y3,y4,y5,y6 => 0 * Här är (y4,y5,y6) en uppenbar möjlig bas. De reducerade kostnaderna är negativa för y2 och y3. Vi låter y2 gå in i basen varvid y6 går ut. * Nu har y3 negativ reducerad kostnad och går in i basen varvid y5 går in. Vi har alltså basen (y2,y3,y4). * y1 har negativ reducerad kostnad, men nu är alla komponenter i första kolonnen av matrisen B^(-1)*N negativa, vilket innebär att y1 kan ökas obegränsat utan att någon av basvariablerna minskar. Samtidigt kommer målfunktionens värde att sjunka obegränsat. Det duala problemet är alltså obegränsat - d = (1,2,1,4,0,0) är en "direction of unboundedness" och uppfyller A*d = 0, d => 0. * Enligt satsen om svag dualitet har vi, om x är en möjlig punkt för det primära (primala??) problemet och y en möjlig punkt för det duala, att z = C(^T)*x => b^(T)*y = w. I vårt fall har vi alltså att w är obegränsad vilket medför att det saknas möjliga punkter x som kan uppfylla olikheten i den svaga dualiteten. Det primära problemet saknar lösning, som vi kom fram till i uppgift 3. %UPPGIFT 5 %%%%%%%%%% * Vi har, efter att ha multiplicerat målfunktionen med -1 och lagt till slackvariabler. min z = -6x1 - 4x2 - 7x3 då x1 + 2x2 + 3x3 + x4 = 8 2x1 + x2 + 2x3 + x5 = 5 3x1 + 3x2 + 4x3 + x6 = 10 x1,x2,x3,x4,x5,x6 => 0 * Problemet är degenererat (x3,x4,xi) är möjliga optimala punkter för i = 1,2,5,6 med x3=5/2, x4=1/2, xi=0. Dessa ger alla att lösningen till det ursprunliga maximeringsproblemet är z=35/2. %UPPGIFT 6 %%%%%%%%%% * Med det nya bivillkoret får vi min z = -6x1 - 4x2 - 7x3 - 2x7 då x1 + 2x2 + 3x3 + x4 + 3x7 = 8 2x1 + x2 + 2x3 + x5 = 5 3x1 + 3x2 + 4x3 + x6 + x7 = 10 x1,x2,x3,x4,x5,x6,x7 => 0 * Med en av de optimala baserna till problemet i uppgift 5 - (x1,x3,x4), erhåller vi att den reducerade kostnaden för vår nya variabel x7 är -1. * Vi finner att den nya optimala basen är (x1,x2,x7), och optimum för maximeringsproblemet är 56/3. * Genom att utöka antalet variabler ökar vi dimensionen på det rum där de möjliga lösningarna ligger - från en delmängd av R^6 till R^7. Då området blir större kan optimum inte bli sämre. %Uppgift 7 %%%%%%%%%% * Skuggpriserna är optimalvärdena för variablerna i det duala problemet. Dessa kan (Nash, Sofer, s 152) skrivas som y_opt = cb^T*B^(-1). För basen (x1,x2,x7) har vi för maximeringsproblemet i 6 6 1/6 7/6 -1/2 cb= 4 B^(-1) = -1/3 -4/3 1 2 1/2 1/2 -1/2 2/3 varför vi för y_opt = 8/3 0 * Skuggpriset för bivillkor 2 blir alltså 8/3. * Målfunktionsvärdet skall alltså öka från 56/3 till 64/3 då högerledet i bivillkor 2 ökas från 5 till 6. * Mycket riktigt får vi värdet 64/3 med basen (x1,x2,x7) med det nya värdet för bivillkor 2. Emellertid är denna bas inte en möjlig bas för problemet, eftersom det krävs att x2 = -2/3 < 0 för att uppfylla de nya bivillkoren. * Det nya optimala värdet blir istället 20 med basen (x1,x4,x7)