grupp: 22
namn1: Gilgamesh Moussa
namn2: Victor Kouzmine; Eric Åkervall
************************************************************
Uppgift 1

maximering ger det optimala målvärdet z = 50 med basen x3, x5, x1
x3 = 10
x5 = 4
x1 = 10



Uppgift 2

Lägger till slackvariabler till bivillkoren så att vi får:

2x1 +  x2 +  x3 +  x4  = 30
 x1 + 2x2 +  x3 -  x5  = 10
-x1 + 2x2 + 3x3 +  x6  = 40

Fas I

Lägg till en artificiell variabel a1 till bivillkor 2 för att kunna välja en bas
som enhetsmatrisen. Sätt målfunktionsvärdet z' = a1  och minimera z' tills a1
försvinner från basen. Sedan tar vi bort a1 kolumnen och löser problemet med den
erhållna optimala basen. Vi fick basen x2, x4, x6.

Fas II

med z = x1 + 3x2 + 2x3 erhölls optimala lösningen z = 10 för:
x1 = 10
x4 = 10
x6 = 50



Uppgift 3

Lägger till slackvariabler och försöker hitta en bas som inte innehåller några
artificiella variabler med tvåfasmetoden men misslyckas. Problemet har ingen lösning.



Uppgift 4

Vi formulerar dualen till problemet:

max w = -2y1 + y2 + y3

2y1 - 3y2       <=  4
-y1       + y3  <= 10
 y1 -  y2 + y3  >=  4

Vi använder tvåfasmetoden för att hitta en bas. Problemet visar sig vara
obegränsat vilket medför att det primala måste sakna lösning.
Detta är helt konsistent med vad vi kom fram till ovan.



Uppgift 5

Vi lägger in tre slackvariabler och väljer dom som bas. Efter några iterationer
får vi fram svaret z = 35/2 med basen:
x2 = 0
x3 = 5/2
x4 = 1/2

Vi ser att problemet är degenererat, eftersom x2 ingår i basen och är lika med
noll. Detta betyder att vi får samma optimalvärde med en annan bas än x2.



Uppgift 6

På den nya variabeln får vi den reducerad kostnaden 3/2. Detta innebär att lösningen
inte är optimal utan kan öka lite till.
Efter några iterationer faller x3 ut från basen och den nya basen fås av:
x1 = 13/6
x2 = 2/3
x7 = 3/2

Problemet är numera icke degenererat.
Det nya målfunktionsvärdet blev z' = 56/3 > 35/2



Uppgift 7

Då vi har en komplett uppsättning slackvariabler så fås den reducerade kostnaden
av:
  T   T  -1
y* = c  B     = [0 2.5 0.5]
      B

Den reducerade kostnaden för det andra bivillkoret är alltså 2.5. Då bör
målfunktionsvärdet öka med 2.5 om vi ökar bivillkoret med ett. Detta skulle ge
z' = 17.5 + 2.5 = 20

Med den optimala basen från uppgift 5 får vi också detta värde när vi ändrar
bivillkoret, men lösningen är ogiltig då x2 får ett negativt värde. Detta
innebär att ett annat bivillkor inte tillåter området som lösningen ligger i och
vi måste byta bas.