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

						Johan Larsson, d96johla@dtek.chalmers.se

						Joan Gatari, md0gatwa@mdstud.chalmers.se

PROBLEM 7

The shadow price of constraint two is given by the second element in the 
vector that results from the calculation of B^-1 * cB, which is actually the 
optimal solution of the dual problem. The second element was -8/3, i.e. the 
shadow price of constraint two is 8/3. When the b-vector is perturbed this can 
affect the feasibility of the current optimal basis. To predict what will 
happen we have to make a sensitivity analysis, to see if the feasibility is 
disturbed. Feasibility is satisfied if B^-1 * bnew >= 0, where bnew is the 
new b vector. In our case we look at the middle column of B^-1, since only 
constraint two is perturbed. We discover that the second basic variable, x2, 
gets the value -2/3, which is infeasible. 
The objective function value in this infeasible point is -64/3. To find a 
feasible minimum we use the dual simplex method, since one basic variable is 
nonpositive. x2 exits the basis and x6 enters, since it yielded the only 
negative denominator of the ratio test. The resulting solution was found to 
be z = 20, which is an optimal point since all the reduced costs of the 
nonbasic variables were nonnegative. I.e. the new basis is (x1 x6 x4) and the 
optimal value increased by 20 - 56/3 = 4/3.

Comment: The largest possible increase in the second constraint b element 
without making the optimal basis found in task 6 infeasible, was found to be 
1/2, since it was then that x2 reached the value zero. The new optimal value 
in the same basis would have been znew = z + yT * db, where y = B^-1 * cB, T 
is the transpose operator and db is the perturbance vector added to b. 
Since only the second element of db is nonzero, only it can contribute to the
increase in the optimum, i.e. in our case znew = z + y2*db2 = 
56/3 + 8/3 * 1/2 = 60/3 = 20. Thus this is the new optimal value, for any 
feasible basis, a fact corroborated by our above calculations using matlab. 
We also found that there were two optimal bases for the new problem, the other 
one being (x1 x5 x4), due to x5 having a reduced cost of zero when (x1 x6 x4) 
was the basis, and vice versa.