grupp: 47
namn1: Tobias Sjögreen
namn2: 
************************************************************
TMA945 Tillämpad optimeringslära: Laboration 1

Tobias Sjögreen, f98tosj@dd.chalmers.se

1.

Optimal bas: x1,x3,x5 (x5 slackvariabel för bivillkor 2), ger:

z=50
x1=10
x2=0
x3=10

2.
Fas 1:
Jag ställer först upp problemet på standardform (med slackvariabler x4,x5,x6). För att hitta tillåten bas, inför jag en artificiell variabel, x7.
Jag minimerar sedan målfunktionen z=x7. Detta ger en optimal bas: x2,x4,x6 som jag använder som startbas i fas 2.

Fas 2:
Nu löser jag problemet på vanligt sätt och får optimalbas> x1,x4,x6, vilket ger:
z=10
x1=10
x2=x3=0

3.

Jag gör på samma sätt som ovan men kan här inte hitta en tillåten bas som minimerar målfunktionen z=x7. Detta innebär att det inte finns någon tillåten bas i det givna problemet, vilket i sin tur innebär att problemet är olösligt.

4.

Dualen till problemet är

max w = 2y1 + 1y2 + 1y3
då -2y1 - 3y2      >=  4
     y1       + y3 <=  10
     y1 +  y2 - y3 <= -4
          y1,y2,y3 >= 0
Vid lösande av problemet hittar jag en tillåten bas som dock inte ger optimal lösning. Problemet är obegränsat vilket är i högsta grad konsistent med att problemets primal inte har någon tillåten lösning.

5.
Jag löser problemet på samma sätt som ovan.

Optimal bas: x1,x3,x4, vilket ger:
z=35/2
x1=0
x2=0
x3=5/2

En av basvariablerna är noll, vilket innebär att det finns en degeneration i problemet.

6.

Jag lägger till den nya variabeln och får den reducerade kostnaden -1.
Efter optimering som ovan får vi optimal bas: x1,x2,x7, vilket ger:

z=56/3
x1=13/6
x2=2/3
x3=0
x7=3/2

Eftersom jag nu har fler variabler än bivillkor har jag ett underbestämt ekvationssystem och jag ser att jag får samma maximala z om jag byter till basen x1,x6,x7, vilket ger:
x1=5/2
x2=0
x3=0
x7=11/6

7.

När jag ändrar högerledet för bivillkor 2 till 6 och optimerar får jag nya maximala z=19 (samma optimala basvariabler som i uppgift 5).

Skuggpriset blir då delta{z}/delta{b}=1.5