CS525 - FINAL EXAM - MAY 12, 2003 - SOLUTIONS

% Q1
p=[4 1]';
A=[2 3 ; 1 1; -1 0];
b=[-2 5 -10]';
T=totbl(A,b,p);
              x1         x2         1   
       ---------------------------------
 x3 = |     2.0000     3.0000     2.0000 
 x4 = |     1.0000     1.0000    -5.0000 
 x5 = |    -1.0000     0.0000    10.0000 
       ---------------------------------
 z  = |     4.0000     1.0000     0.0000 
T=ljx(T,2,2);
              x1         x4         1   
       ---------------------------------
 x3 = |    -1.0000     3.0000    17.0000 
 x2 = |    -1.0000     1.0000     5.0000 
 x5 = |    -1.0000     0.0000    10.0000 
       ---------------------------------
 z  = |     3.0000     1.0000     5.0000 
T=delcol(T,'x4');
              x1         1   
       ----------------------
 x3 = |    -1.0000    17.0000 
 x2 = |    -1.0000     5.0000 
 x5 = |    -1.0000    10.0000 
       ----------------------
 z  = |     3.0000     5.0000 
T=permrows(T,[1 3 4 2]);
              x1         1   
       ----------------------
 x3 = |    -1.0000    17.0000 
 x5 = |    -1.0000    10.0000 
       ----------------------
 z  = |     3.0000     5.0000 
 x2 = |    -1.0000     5.0000 
% optimal tableau! solution: (x1,x2) = (0,5) with objective z=5.
%
% Q2
% a) dual: max b'u   s.t.  A'u <= p,  u >= 0
% b) strong duality => b'u=0 for solution u. Since
%    components of b are all strictly positive, and
%    since u >=0, must have u=0.
% c) since the solution u=0 is feasible, must have 
%    0 = A'u <= p.
%
% Q3
A=[1 -1; -2 1];
p=[1 0]';
q=[-2 -1]';
b=[-2 -4]';
T=totbl(A,b,p);
              x1         x2         1   
       ---------------------------------
 x3 = |     1.0000    -1.0000     2.0000 
 x4 = |    -2.0000     1.0000     4.0000 
       ---------------------------------
 z  = |     1.0000     0.0000     0.0000 
T=addrow(T,[q' 0],'z0',4);
              x1         x2         1   
       ---------------------------------
 x3 = |     1.0000    -1.0000     2.0000 
 x4 = |    -2.0000     1.0000     4.0000 
       ---------------------------------
 z  = |     1.0000     0.0000     0.0000 
 z0 = |    -2.0000    -1.0000     0.0000 

% this tableau is optimal for 1-2t>=0, -t>=0, that is,
% t in (-infty,0]. Solution is (x1,x2)=0 and z(t)=0.
% as t increases above zero, reduced cost for col 2
% becomes negative. Ratio test gives row 1 as pivot row:
T=ljx(T,1,2);
              x1         x3         1   
       ---------------------------------
 x2 = |     1.0000    -1.0000     2.0000 
 x4 = |    -1.0000    -1.0000     6.0000 
       ---------------------------------
 z  = |     1.0000     0.0000     0.0000 
 z0 = |    -3.0000     1.0000    -2.0000 
% this tableau optimal when 1-3t>=0, t>=0, that is, for
% t in [0,1/3]. Solution is (x1,x2)=(0,2) with objective
% z(t) = -2t.
% as t increases above 1/3, first reduced cost goes negative.
% Ratio test indicates that row 2 is the pivot row.
T=ljx(T,2,1);
              x4         x3         1   
       ---------------------------------
 x2 = |    -1.0000    -2.0000     8.0000 
 x1 = |    -1.0000    -1.0000     6.0000 
       ---------------------------------
 z  = |    -1.0000    -1.0000     6.0000 
 z0 = |     3.0000     4.0000   -20.0000 
% this tableau optimal when -1+3t>=0, -1+4t>=0, i.e.
% for t in [1/3,infty). solution is (x1,x2)=(6,8) with
% objective value z(t)=6-20t.
%
%Q4
% a) set (x1,x2,x3) = (-1,0,-2). lhs of constraints is
% [-9, -3]. Introduce slacks x4,x5 as follows:
%
%  x1 + 2*x2 + 4*x3 + x4 = 10,
% -x1 + 3*x2 + 2*x3 - x5 = -5,
%
% with initial values x=(-1,0,-2,19,2)
% bounds are 
% 
% lower=(-1,0,-2,0,0), 
% upper = (2,2,infty,infty,infty)
% 
% objective is x4+x5.
%
% b) initial basic feasible point is (-1,0,-2,19,2)
%
%Q5
% a) min t   s.t.  -te <= Ax-b <= te, x>=0, where e=(1,1)'.
% b) write in standard form as follows:
%   min [0 0 1]'(x;t)    s.t.
%   Ax + te >= b,
%  -Ax + te >= -b,
%  x >=0, t >= 0
A=[1 1; 1 -1]; e=[1 1]'; b=[0 2]';
M=[A e; -A e]; h=[b; -b];
p=[0 0 1]';
T=totbl(M,h,p);
              x1         x2         x3         1   
       --------------------------------------------
 x4 = |     1.0000     1.0000     1.0000     0.0000 
 x5 = |     1.0000    -1.0000     1.0000    -2.0000 
 x6 = |    -1.0000    -1.0000     1.0000     0.0000 
 x7 = |    -1.0000     1.0000     1.0000     2.0000 
       --------------------------------------------
 z  = |     0.0000     0.0000     1.0000     0.0000 
T=ljx(T,2,1);
              x5         x2         x3         1   
       --------------------------------------------
 x4 = |     1.0000     2.0000     0.0000     2.0000 
 x1 = |     1.0000     1.0000    -1.0000     2.0000 
 x6 = |    -1.0000    -2.0000     2.0000    -2.0000 
 x7 = |    -1.0000     0.0000     2.0000     0.0000 
       --------------------------------------------
 z  = |     0.0000     0.0000     1.0000     0.0000 
T=ljx(T,3,3);
              x5         x2         x6         1   
       --------------------------------------------
 x4 = |     1.0000     2.0000     0.0000     2.0000 
 x1 = |     0.5000     0.0000    -0.5000     1.0000 
 x3 = |     0.5000     1.0000     0.5000     1.0000 
 x7 = |     0.0000     2.0000     1.0000     2.0000 
       --------------------------------------------
 z  = |     0.5000     1.0000     0.5000     1.0000 
% optimal with (x1,x2)=(1,0) and optimal objective 1.