Contents

% hw1p1d.m  find all basic feasible points

Matrix A, right-hand side b and size [m, n]

A = [ 1 -1 -1 1 0 0
      1 -1 -3 0 1 0
     -4  4 -1 0 0 1];
b = [3; 1; 0];
[m, n] = size(A);

C contains all combinations of choosing m from n

Each row of C contains a subsets of { 1, 2, 3, 4, 5, 6} with 3 elements. There are 6!/(3!3!)= 20 possible subsets in total.

C = combnk(1:n,m);
nbfp = 0;

Loop through C and check nonsigularity & nonnegativity

for i = 1:size(C,1)
    fprintf('\n index set B = { %d, %d, %d } \n', C(i,:) );
    AB = A(:,C(i,:));
    r = rank(AB);
    if r < m               % AB is singular
        fprintf(' non-singularity fails\n' );
    else
        xB = AB \ b;
        if any( xB < -eps) % eps is a guard for rounding errors
            fprintf(' nonnegativity fails\n' );
        else
            nbfp = nbfp + 1;
            x         = zeros(n,1);
            x(C(i,:)) = max(0,xB);  % get rid of tiny negatives
            fprintf(' basic feasible point ... x = (%2.1f, %2.1f, %2.1f, %2.1f, %2.1f, %2.1f)\n', x);
        end
    end
end
fprintf('\n There are %i basic feasible points.\n',nbfp)

 index set B = { 4, 5, 6 } 
 basic feasible point ... x = (0.0, 0.0, 0.0, 3.0, 1.0, 0.0)

 index set B = { 3, 5, 6 } 
 nonnegativity fails

 index set B = { 3, 4, 6 } 
 nonnegativity fails

 index set B = { 3, 4, 5 } 
 basic feasible point ... x = (0.0, 0.0, 0.0, 3.0, 1.0, 0.0)

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

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

 index set B = { 2, 4, 5 } 
 basic feasible point ... x = (0.0, 0.0, 0.0, 3.0, 1.0, 0.0)

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

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

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

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

 index set B = { 1, 4, 6 } 
 basic feasible point ... x = (1.0, 0.0, 0.0, 2.0, 0.0, 4.0)

 index set B = { 1, 4, 5 } 
 basic feasible point ... x = (0.0, 0.0, 0.0, 3.0, 1.0, 0.0)

 index set B = { 1, 3, 6 } 
 basic feasible point ... x = (4.0, 0.0, 1.0, 0.0, 0.0, 17.0)

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

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

 index set B = { 1, 2, 6 } 
 non-singularity fails

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

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

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

 There are 6 basic feasible points.

Published with MATLAB® R2013b