Contents

% Chair-Table Example:
% For all basic feasible points (BFPs), compute sN
% and determine optimality.  Required inputs are
%      3 matrices: A, Bas, Nbs
%      2 vectors:  b, c

generate A, b, all BFPs

check_bfp is a modified code from HW1, saves all relevant partitions in Bas and Bbs

check_bfp;
nbfp = size(Bas,1);
disp(' ')

 index set B = { 3, 4, 5 } 
 basic feasible point ... x = (0.0, 0.0, 1000.0, 400.0, 100.0)

 index set B = { 2, 4, 5 } 
 nonnegativity fails

 index set B = { 2, 3, 5 } 
 non-singularity fails

 index set B = { 2, 3, 4 } 
 basic feasible point ... x = (0.0, 100.0, 600.0, 400.0, 0.0)

 index set B = { 1, 4, 5 } 
 nonnegativity fails

 index set B = { 1, 3, 5 } 
 basic feasible point ... x = (400.0, 0.0, 200.0, 0.0, 100.0)

 index set B = { 1, 3, 4 } 
 non-singularity fails

 index set B = { 1, 2, 5 } 
 basic feasible point ... x = (400.0, 50.0, 0.0, 0.0, 50.0)

 index set B = { 1, 2, 4 } 
 basic feasible point ... x = (300.0, 100.0, 0.0, 100.0, 0.0)

 index set B = { 1, 2, 3 } 
 nonnegativity fails

 There are 5 basic feasible points.
 

generate objective vector c

[m,n] = size(A);
c = zeros(n,1);
c(1) = -20;
c(2) = -30;

Loop through all BFPs

for i = 1:nbfp

get basic and nonbasic indices

    B = Bas(i,:);
    N = Nbs(i,:);
    fprintf('basis: (%i, %i, %i)\n',B);

basis: (3, 4, 5)

basis: (2, 3, 4)

basis: (1, 3, 5)

basis: (1, 2, 5)

basis: (1, 2, 4)

get basic variables

    x = zeros(n,1);
    x(B) = A(:,B)\b;

compute y and sN

    y = A(:,B)' \ c(B);
    sN = c(N) - A(:,N)'*y;

Check optimality

    if all(sN >= -eps)
        fprintf('*** optimal B.F.P.: (%i,%i,%i,%i,%i)) <--> (%i,%i)\n\n',...
        x,x(1:n-m))
    else
        fprintf('non-optimal B.F.P.: (%i,%i,%i,%i,%i)\n\n',x)
    end

non-optimal B.F.P.: (0,0,1000,400,100)

non-optimal B.F.P.: (0,100,600,400,0)

non-optimal B.F.P.: (400,0,200,0,100)

*** optimal B.F.P.: (400,50,0,0,50)) <--> (400,50)

non-optimal B.F.P.: (300,100,0,100,0)

loop end

end

Published with MATLAB® R2013b