Contents

% hw2p4.m
% solve standard form LP with m = 1.

function hw2p4

problem data

b = 1;
c = [ 1; 2;-3; -4; 5; 6; -7; -8; -9; 10];

a1 = [ -1; 2; 1; -2; 1; -3; -1; -4; 1; 2];
a2 = -ones(10,1);
a3 = +ones(10,1);
A = [a1 a2 a3];

check 3 vectors of a

for j = 1:3
    a = A(:,j);
    [x, flag] = solve_simpleLP(a,b,c);
    fprintf('vector a #%i: %s\n',j,flag)
    if ~isempty(x);
        fprintf('optimal value: %g\n',c'*x)
        fprintf('optimal x = '); fprintf('%g ',x); fprintf('\n')
    end
end

function [x,flag] = solve_simpleLP(a,b,c)

vector a must not be all 0

if all(a == 0); error('a is all 0'); end
n = length(a);
ind = 1:n;
x = [];

case 1: check infeasibility

inz = ind(a ~= 0);  % indices for nonzeros
b_over_a = b ./ a(inz);
if all(b_over_a < 0)
    flag = 'infeasible'; return
end

vector a #2: infeasible

case 2: check unboundedness

% indices for BFPs
ibfp = inz(b_over_a >= 0);

% index of "lowest" BFP
[~,imin_local] = min(c(ibfp).*b_over_a(ibfp));
imin = ibfp(imin_local);

% nonbasic indices
Nbs = ind(ind ~= imin);
y = c(imin)/a(imin);
sN = c(Nbs) - a(Nbs)*y;
if any(sN < 0)
    flag = 'unbounded'; return
end

vector a #1: unbounded

case 3: an optimum exists

flag = 'optimum found';
x = zeros(n,1);
x(imin) = b/a(imin);

vector a #3: optimum found
optimal value: -9
optimal x = 0 0 0 0 0 0 0 0 1 0 

Published with MATLAB® R2013b