grupp: tp02-42
namn1: Joan Gatari
namn2: Johan Larsson
************************************************************
TMA945:  INFORMATION COUMPUTER LAB1

						Johan Larsson, d96johla@dtek.chalmers.se

						Joan Gatari, md0gatwa@mdstud.chalmers.se

PROBLEM 1

Min z=(-2 -4 -3 0 0 0)x 
s/t (1 3 2 1 0 0) = (30) 
    (1 1 1 0 1 0) (24) 
    (3 5 3 0 0 1) (60)

x>=0

XB=(x4 x5 x6), XN=(x1 x2 x3)

From the results of the program it is clear that z has the optimal value of 50 when (x1 x2 x3) = (10 0 10).  
The optimal basis is {x1,x3,x5}.

PROBLEM 2

Phase 1:  
Min z=X6 
s/t ( 2 1 1 1 0 0 0) = (30) 
    ( 1 2 1 0 -1 1 0)  (10) 
    (-1 2 3 0 0 0 1)   (40)

x>=0

XB=(x4 x6 x7), XN=(x1 x2 x3 x5)

Phase 2:  
Min z=(1 3 2 0 0 0)x 
s/t (2 1 1 1 0 0) = (30)
    (1 2 1 0 -1 0)  (10) 
    (-1 2 3 0 0 1)  (40)

x>=0

XB=(x2 x4 x6), XN=(x1 x3 x5)

This problem was solved using the two phase method.  In the first phase the artificial variable was the leaving variable right in the 
beginning, and the resulting objective function value was zero.  This yielded the basis (x2,x4,x7), which was then applied to the
original problem (with x7 now called x6, since the previous x6 was the artificial variable).  After two pivots in the second
phase we found the solution to be (x1 x2 x3) = (10 0 0) with the objective value z = 10.

PROBLEM 3

Phase 1:
min z=x7+x8
s/t (2 1  1 1  0  0 0 0) = (2) 
    (3 0  1 0 -1  0 1 0)   (1) 
    (0 1 -1 0  0 -1 0 1)   (1)

    x>=0

XB=(x4 x7 x8), XN=(x1 x2 x3 x5 x6)

This problem has a slack variable and two excess variables.  The latter ones can not be used as basic variables, as they would
have a negative value.  For that reason two artificial variables, x7 and x8, are introduced, whereafter the phase-1 objective function z
= x7 + x8 is minimized.  If we find a basis not including the artificial variables which yields the objective value zero, we can use that
basis as a starting basis for the original problem.  This was however not the case, because x7 was a part of the optimal basis for the
phase-1 problem, from which fact it can be concluded that the original problem has no solution.

PROBLEM 4

The dual of the LP problem from the previous task is

max w = [ -2 1 1]y 
s/t ( 2 -3 0) = ( 4) 
    (-1 0 1)y  (10) 
    (-1 1 -1)  (-4) .
As there is a negative value in the b vector in this tableau, we have to apply the dual simplex method.  After iterations the x1 coefficient
in the objective function is greater than zero,(X1=1) i.e.  this is no optimal solution.This is in full agreement with corollary 6.1.  in
Nash-Sofer, which states that when the dual is unbounded, the primal is infeasible, a fact already seen in problem 3.

PROBLEM 5

min z=(-6 -4 -7 0 0 0)
s/t (1 2 3 1 0 0) = (2) 
    (2 1 2 0 1 0)   (1) 
    (3 3 4 0 0 1)   (1)

    x>=0

XB=(x4 x5 x6), XN=(x1 x2 x3)

The calculations yielded that z has the optimal value of 35/2 when (x1 x2 x3) = (0 0 5/2).  The optimal basis is {x1,x3,x4}.

PROBLEM 6

Below are our Matlab calculations of the reduced cost for all the
non-basic variables, i.e.  x2,x4,x6 and x7.  As can be seen, we consider x4 to be a non-basic variable, due to the displacement which was
created when we added the new column before the columns corresponding to the slack variables.

cN =

4 2 0 0

cB =

6 7 0

B =

1.0000 3.0000 1.0000 
2.0000 2.0000 0.0000 
3.0000 4.0000 0.0000

inv(B) =

-0.0000  2.0000  -1.0000 
      0  -1.5000  1.0000 
 1.0000  2.5000  -2.0000

N =

2 3 0 0 
1 0 1 0 
3 1 0 1

>> cN-cB*inv(B)*N

ans =

-0.5000 1.0000 -1.5000 -1.0000

The calculation yields a reduced cost for the new variable of 1.0000, the value of the second column of the ans vector.


The new optimal solution yields z = 56/3, achieved when (x1 x2 x3 x4) = (13/6 2/3 0 3/2). The optimal basis is {x1,x2,x4}.

Comment:  The only variable which had a positive reduced cost was x4, for which reason it was part of the new basis,
seeing as a maximization of the objective function value was sought.

PROBLEM 7

In the optimal tableau of task 6 it could be seen that the shadow price of constraint 2 is 8/3.
The solution of the original dual of the problem in the previous task yields (x1 x2 x3 x4) = (2/3 8/3 0 0).  
These values are the shadow prices of the respective variables.  
Of this one can conclude that the shadow price of constraint 2 is 8/3, which confirms the optimal result from task 6.

Afterchanging the right hand side value of constraint 2 to 6, the new objective function was found to be z = 64/3.

The new optimal value minus the old optimal value of task 6 should be equal to the shadow price of constraint 2 multiplied by the perturbation.  
This is alsoin fact so, since 64/3 - 56/3 = 8/3 and 8/3 * (6-5) = 8/3!