CS525 Final Exam Solutions
			Tuesday May 14, 1996


>> %%%%%%%%%%%%%%%%%%%%%Problem 1 Solution%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> Q=[2 -1;-1 1];p=[-3;2];A=[-4 3;5 2];b=[-9; 1];
>> M=[Q -A';A zeros(2,2)];q=[p;-b];
>> H=lemketbl(M,q);
              z1         z2         z3         z4         1    
       -------------------------------------------------------
  w1= |     2.0000    -1.0000     4.0000    -5.0000    -3.0000 
  w2= |    -1.0000     1.0000    -3.0000    -2.0000     2.0000 
  w3= |    -4.0000     3.0000     0.0000     0.0000     9.0000 
  w4= |     5.0000     2.0000     0.0000     0.0000    -1.0000 
>> H=addcol(H,ones(4,1),'z0',5);
              z1         z2         z3         z4         z0         1    
       ------------------------------------------------------------------
  w1= |     2.0000    -1.0000     4.0000    -5.0000     1.0000    -3.0000 
  w2= |    -1.0000     1.0000    -3.0000    -2.0000     1.0000     2.0000 
  w3= |    -4.0000     3.0000     0.0000     0.0000     1.0000     9.0000 
  w4= |     5.0000     2.0000     0.0000     0.0000     1.0000    -1.0000 
>> H=ljx(H,1,5);
              z1         z2         z3         z4         w1         1    
       ------------------------------------------------------------------
  z0= |    -2.0000     1.0000    -4.0000     5.0000     1.0000     3.0000 
  w2= |    -3.0000     2.0000    -7.0000     3.0000     1.0000     5.0000 
  w3= |    -6.0000     4.0000    -4.0000     5.0000     1.0000    12.0000 
  w4= |     3.0000     3.0000    -4.0000     5.0000     1.0000     2.0000 
>> H=ljx(H,1,1);
              z0         z2         z3         z4         w1         1    
       ------------------------------------------------------------------
  z1= |    -0.5000     0.5000    -2.0000     2.5000     0.5000     1.5000 
  w2= |     1.5000     0.5000    -1.0000    -4.5000    -0.5000     0.5000 
  w3= |     3.0000     1.0000     8.0000   -10.0000    -2.0000     3.0000 
  w4= |    -1.5000     4.5000   -10.0000    12.5000     2.5000     6.5000 
>> %Complementary solution: x1=z1=1.5;x2=z2=0
>> %min f(x)=2.25-4.5=-2.25


>> %%%%%%%%%%%%%%%%%%%%%Problem 2 Solution%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> A=[1 -1;1 -2];b=[-1;-4];p=[1;1];q=[0.5 ;-1];
>> H=totbl(A,b,p);
              x1         x2         1    
       ---------------------------------
  x3= |     1.0000    -1.0000     1.0000 
  x4= |     1.0000    -2.0000     4.0000 
       ---------------------------------
   z= |     1.0000     1.0000     0.0000 
>> H=addrow(H,[q' 0],'z0',3);
              x1         x2         1    
       ---------------------------------
  x3= |     1.0000    -1.0000     1.0000 
  x4= |     1.0000    -2.0000     4.0000 
  z0= |     0.5000    -1.0000     0.0000 
       ---------------------------------
   z= |     1.0000     1.0000     0.0000 
>> %1+0.5t>=0, 1-t>=0 imply optimal tableau for 1>=t>=-2
>> %Unbounded objective from below for -2>t
>> H=ljx(H,1,2);
              x1         x3         1    
       ---------------------------------
  x2= |     1.0000    -1.0000     1.0000 
  x4= |    -1.0000     2.0000     2.0000 
  z0= |    -0.5000     1.0000    -1.0000 
       ---------------------------------
   z= |     2.0000    -1.0000     1.0000 
>> %2-0.5t>=0, -1+t>=0 imply optimal tableau for 4>=t>=1
>> H=ljx(H,2,1);
              x4         x3         1    
       ---------------------------------
  x2= |    -1.0000     1.0000     3.0000 
  x1= |    -1.0000     2.0000     2.0000 
  z0= |     0.5000     0.0000    -2.0000 
       ---------------------------------
   z= |    -2.0000     3.0000     5.0000 
>> %-2+0.5t>=0, 3>=0 imply optimal tableau for t>=4.
>> %Summary
>> % t<-2  objective unbounded below
>> % -2=<t=<1 z(t)=0 at x=[0;0]
>> %  1=<t=<4 z(t)=1-t at x=[0;1]
>> %  4=<t    z(t)=5-2t at x=[2,3]

>> %%%%%%%%%%%%%%%%%%%%%Problem 3 Solution%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(a)  False. Because of the cosequent contradiction if it were true:

		0=x'A'u=u'Ax>0

(Alternatively, if statement is true then, max{e'u | A'u=0, u>=0}=infinity, 
hence the dual: min{0'x | Ax >= e} is infeasible, or Ax>0 has no solution, 
contradicting the statement.)

(b) False. For example, for M=-1, q=-1 LCP is infeasible & hence unsolvable.