grupp: 10 namn1: Andreas Holmström namn2: Erik Jonsson ************************************************************ Optimeringslab 1, 13/2 2002 ---------------------------------- Erik Jonsson, 800902-4814 Andreas Holmström, 781021-4853 Vi har sammarbetat fast vi inte var i samma grupp från början. Vi var grupp 10 och 33. Redovisar nu och i fortsättningen under 10. Vi använder genomgående x4, x5 och x6 som slackvariabler för de tre bivillkoren. Vi redovisar alla uppgifter genom att ange vilken sekvens av basvariabler vi fick, samt vilket optimalt värde och tillhörande värden på x1, x2 och x3 vi fick. Uppgift 1 --------- Basvariabelsekvens: x4,x5,x6 -> x2,x5,x6 -> x1,x2,x5 -> x1,x3,x5 Lösning: x1 = 10, x2 = 0, x3 = 10 Optimalt värde: 50 Uppgift 2 --------- Det gick inte att hitta en bas direkt, så vi införde en artificiell variabel x7 till bivillkor 2, och löste problemet min z = x7 istället, för att hitta en tillåten bas. Basvariabelsekvens, fas1: x4,x6,x7 -> x2, x4, x6 För denna bas fick vi z = 0, så (x1,x4,x6) är en tillåten bas. Nu kunde vi utgå från denna bas och lösa det verkliga problemet. Basvariabelsekvens, fas2: x2,x4,x6 -> x1,x4,x6 Lösning: x1 = 10, x2 = 0, x3 = 0 Optimalt värde: 10 Uppgift 3 --------- Det gick inte att hitta en bas direkt, så vi införde två artificiella variabler x7,x8 till bivillkor 2, 3 och löste problemet min z = x7 +x8 istället, för att hitta en tillåten bas. Basvarbelsekvens, fas1:x4,x7,x8 -> x2,x4,x7 -> x2,x3,x7 För denna bas fick vi z=1/2 så det finns ingen tillåten bas till problemet alltså är problemet olösbart. Uppgift 4 --------- Duala problemet är max z= -2y1 + y2 + y3 då 2y1 - 3y2 <= 4 -y1 + y3 <= 10 -y1 + y2 - y3 <= -4 Det duala problemet är obegränsat. Uppgift 5 --------- Basvariabelsekvens: x4,x5,x6 -> x3,x4 x6 -> x2,x3,x4 Lösning: x1 = 0, x2 = 0, x3 = 5/2 Maximala värdet: 35/2 Uppgift 6 --------- Reducerad kostnad för ny variabel 3/2. Ny optimal bas x1,x2,x7 Lösning: x1 = 13/6, x2 = 2/3, x3 = 0, x7 = 3/2 Optimalt värde: 56/3 Vi kunde förbättra det optimal värdet när x7 infördes eftersom den nya variabeln hade en possitiv reducerad kostnad. Uppgift 7 --------- Vi tittar på reducerade kostnaden för variabeln x5, eftersom x5 är den slackvariabel som svarar mot bivillkor 2. Den reducerade kostnaden är -5/2, så skuggpriset är 5/2. Detta betyder att det optimala värdet ökas med 5/2 för varje enhetsökning av högerledet i bivillkoret, så länge inget basbyte sker. Vi kan misstänka att det optimala värdet ökar från 35/2 till 40/2 när femman i bivillkoret ändras till 6. Men när vi löste problemet i simplex-programmet såg vi att så inte var fallet, eftersom vi inte kunde gå ett enhetssteg i x5-riktningen. Istället fick vi ett basbyte till den nya basen (x1,x3,x4) och ett optimalt värde z = 19.