grupp: top02-29
namn1: Claes-Göran Filander
namn2: 
************************************************************
Uppgift 1

Att maximera Z = 2X1 + 4X2 + 3X3 är det samma som att minimera 
-Z = -2X1 - 4X2 - 3X3

Bivillkoren i standardform:

 X1 + 3X2 + 2X3 + X4           = 30
 X1 +  X2 +  X3 +      X5      = 24
3X1 + 5X2 + 3X3 +           X6 = 60

Vi använder startbasen X4,X5,X6.

Vi erhåller lösningen: min -Z = -50 för X1=10,X2=0,X3=10,X4=0,X5=4,X6=0

Alltså max Z = 50. 


Uppgift 2

minimera Z = X1 + 3X2 + 2X3, då

2X1 +  X2 +  X3 + X4           = 30
 X1 + 2X2 +  X3      - X5      = 10
-X1 + 2X2 + 3X3           + X6 = 40


Måste först hitta en baslösning och löser därför fas 1 problemet.

Fas 1 problem: minimera Z=X7, då

2X1 +  X2 +  X3 +  X4                = 30
 X1 + 2X2 +  X3 -       X5 +    + X7 = 10
-X1 + 2X2 + 3X3 +            X6      = 40

Startbas X4,X5,X7

Lösningen blir: Z=X7=0, då X1=0,X2=5,X3=0,X4=25,X5=0,X6=30. Kan alltså
lösa det ursprungliga problemet med X2,X4 och X6 som startbas.

Den optimala lösningen blir nu: Z=10 då X1=10,X4=10 och X6=50.


Uppgift 3

minimera Z = 4X1 + 10X2 -4X3 då,

-2X1 + X2 + X3 + X4           = 2
-3X1 +    + X3 -    - X5      = 1
       X2 - X3           - X6 = 1

Måsta använda fas 1 och lägger till slack X7 och X8 och minimerar Z=X7+X8.
Minimum för Z blir nu 1/2 och vi kan alltså inte finna en baslösning.
Problemet går ej att lösa.


Uppgift 4

Dualen till ovanstående problem borde enligt teorin ha en obegränsad lösning.

Formulerar dualen till problemet i uppgift 3 på standardform enligt:

minimera W = 4Y1 - 10Y2 + 4Y3 då,

2Y1 - 3Y2 +    + Y4           = 4
-Y1 +       Y3 +    + Y5      = 10
 Y1 -  Y2 + Y3           - Y6 = 4

Löser enligt fas 1 och fas 2. Lösningen blir obegränsad vilket stämmer
med teorin.


Uppgift 5

minimera -Z = -6X1 - 4X2 - 7X3 då

 X1 + 2X2 + 3X3 + X4           = 8
2X1 +  X2 + 2X3      + X5      = 5
3X1 + 3X2 + 4X3           + X6 = 10

Detta problem är degenererat. En optimallösning är -35/2 då 

X1=0,X2=0,X3=5/2,X4=1/2,X5=0,X6=0


Uppgift 6

Lägger vi nu till en variabel till problemet i uppgift 5 blir den
reducerade kostnaden för denna -3/2. Löser vi problemet erhåller vi:
Z=56/3 då X1=13/6,X2=2/3,X3=0,X4=0,X5=0,X6=0,X7=3/2. Problemet är inte
längre degenererat vilket beror på att den extra variabeln gjorde
att bivillkoren blev linjärt oberoende.


Uppgift 7

Skuggpriset till bivillkor 2 löses genom att lösa det duala problemet
och resultatet är 8/3. Om vi vändrade högra ledet till bivillkor 2 från
5 till 6 borde alltså Z öka med 8/3. Vi verifierar detta i Matlab men ser
att Z blir 20 istället för 64/3. Men vi ser också att detta är fallet
då vi istället höjer från 5 till 6. Skuggpriset gäller bar i ett mycket
litet intervall.