grupp: top02-39
namn1: Robert Olsson
namn2: 
************************************************************
Title: Laboration 1
Date:  2001-02-18
Name:  Robert Olsson, 800619-4610, md9olsro
Group: top02-39
=======================================================================

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, which 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 with the basis x3, x4, x2, 
	-1 with the basis x3, x4, x1, 
	-1/4 with the basis x3, x4, x5, 	
	-2 with the basis x3, x4, x6.

	After re-optimization the new optimal value is 56/3 with the 
	basis x2=2/3, x1=13/6, x7=3/2.
	
7)
	My idea was to solve the dual of problem 6 and then the shadow
	price for constrain 2 in the primal would be equal to y2 in the 
	dual. If you do so you will get a problem with two phases and 
	finally	the value 2 of y2 in the optimal basis.
	
	I suppose you could get this information without creating the 
	dual and instead looking at the lowest reduced cost, -2, for 
	all optimal bases in problem 6 above.
	
	The new optimal value ought to be 20, that is 18+2, which is 
	correct if you got problem 6 to has the optimal value 18 but I 
	got a little more. I have had some mistake...