grupp: top02-39
namn1: Robert Olsson
namn2: 
************************************************************
Title: Laboration 1
Date:  2001-02-19 04:53
Name:  Robert Olsson, 800619-4610, md9olsro
Group: top02-39
Handin: Number two, corrected my mistakes from the report I sent in 
        a few hours ago.
=======================================================================

1)
	Answear: The optimal value is 50 with x3=10, x5=4, x1=10.

2)
	First we write the problem in standard form,
	
	min z = x1 + 3*x2 + 2*x3
	s.t	2*x1 + x2 + x3 + s1 = 30
		x1 + 2*x2 + x3 -e2 = 10
		-x1+ 2*x2 + 3*x3 + s3 = 40
		x1, x2, x3, s1, e2, s3 => 0.

	We have to use artificial variables in phase one, so let us 
	find the basis for,

	min z = a1
	s.t	2*x1 + x2 + x3 + s1 = 30
		x1 + 2*x2 + x3 -e2 + a1 = 10
		-x1+ 2*x2 + 3*x3 + s3 = 40
		x1, x2, x3, s1, e2, s3, a1 => 0.
		
	The basis for the optimal solution is x4, x6, x2. So in phase 
	two we start with the basis above and reach the solution 
	pretty quick.
	
	Answear: The optimal value is 10 with x1=10, x4=10, x6=50.

3)
	As in problem 2 above we have to start with phase 1 and find 
	the basis for, 

	min z = a1 + a2
	s.t	-2*x1 + x2 + x3 + s1 = 2
		-3*x1 + x3 -e2 + a1 = 1
		x2 - x3 -e3 + a2 = 1
		x1, x2, x3, s1, e2, e3, a1, a2 => 0.

	But after a few iterations with the simplex software we find 
	that a1 is included in the optimal basis and a1=1/2!=0. So due 
	to "Linear and Nonlinear Programming" page 126 there is no 
	feasible solution to the constrains, i.e the problem can not 
	be solved.

4)
	Phase one went well but in phase two we ran into trouble 
	(which was great). After a few iterations with the software we
	are facing the following situation,
	
	Optimal value: -16
	Basis: x4=22, x3=10, x2=6
	Reduced costs: x1=-1, x5=2, x6=1.
	
	If we choose x1 as the entering variable we only get negative 
	values in B^-1 * A(:,i), i.e we can not proceed.
	
	But by "Linear and Nonlinear Programming" page 104 this means 
	that the entering variable can be decreased without limit, i.e
	there is no finite solution.
	
	By Corollary 6.1 at page 151 this is perfectly correct since a
	problem in dual form is unbounded, as above, then the problem 
	in primal form has no feasible solutions, as in problem 3.
	
5)
	Written in standard form, the problem is to solve, 
	
	min z = -6*x1 - 4*x2 - 7*x3
	s.t	x1 + 2*x2 + 3*x3 + s1 = 8
		2*x1 + x2 + 2*x3 + s2 = 5
		3*x1 + 3*x2 + 4*x3 + s3 = 10
		x1, x2, x3, s1, s2, s3 => 0.
	
	Using the software and starting with basis s1, s2, s3 we have 
	to deal with a few issues. 
	
	First after choosing x3 as the entering variable we have to 
	make a choice between x5 and x6 as the leaving variable 
	since 5/2=10/4. Let us choose x5. (*)
	
	Then we choose x2 as the entering variable resulting in that 
	x6/1, x6 still is in the basis and equal to zero, is equal 
	to zero. After we have changed x6 into x2, x2 is zero in the 
	basis and we are done. The optimal solution is -35/2.
	
	If we instead of choosing x5 had choosed x6 in (*), the same 
	optimal value had been reached but now we have had x4=1/2, 
	x1=0, x3=5/2 in the basis.
	
	In fact any basic including the variables x3, x4 and a third 
	variable set to zero represents the optimal solution.
	
	Answear: The optimal value is 35/2 with x3=5/2, x4=1/2 and 
	a third variable set to zero.
	
6)
	The reduced cost of the new variable, x7, is equal to 
	-3/2 in the basis x3, x4, x2,
	-1 in the basis x3, x4, x1,
	-1/4 in the basis x3, x4, x5,
	-2 in the basis x3, x4, x6.

	The optimal value will change since there were some, in fact 
	all, reduced costs of x7, not greater than zero.

	After re-optimization, the new optimal value is 56/3 with basis
	x2=2/3, x7=3/2, x1=13/6. There are other optimal bases since 
	x6, a non basis variable, has reduced cost equal to zero.
	
7)
	If we have the optimal basis from problem 6 we can find the
	shadow price for the second constrain by using the fact that,
	y = (cB)*B^-1 = [-2/3 -8/3 0], where y=[+-y1 +-y2 +-y3] 
	represents the variables in the dual problem. So y2 is equal 
	to 8/3 or -8/3. 
	
	Suppose y2 = 8/3 and y1 = 2/3 then the optimal value of the 
	dual, which corresponds to the primal solution, is 
	8*2/3 + 5*8/3 = 56/3. If we increase the second constrain in 
	the primal problem to 6, we get 8*2/3 + 6*8/3 = 64/3 in the 
	dual, but is that kind of operation allowed in our case?
	
	In the book at chapter 6.4 an easy test is presented.
	
	We have to check 
		if B^-1*b => -B^-1*[0; 1; 0].
			Then the new optimal value is equal to the 
			old optimal value plus (cB)*B^-1*[0; 1; 0], 
			i.e -56/3 - 8/3 = -64/3.
		Else
			we have to use additional simplex iterations.
	
	But since
	B^-1*b = [13/6; 2/3; 3/2] (**) and 
	-B^-1*[0; 1; 0] = [-7/6; 4/3; -1/2] (***)
	we find that (**) is not greater or equal (***), i.e we have
	to use the simplex method again to find the optimal value. 
	
	By using the simplex software we find that the new optimal 
	value is 20, which is not equal to 64/3.