Linear programming code not showing the solution

I extracted the following code from an online pdf that solves basic feasible solution of linear programming problems.

function vert = feassol(A, b)
% Basic feasible solutions vert to the system of constraints
% Ax = b, x >= 0.
% They are stored in columns of the matrix vert.

[m, n] = size(A);
warning off
b = b(:);
vert = [];
if (n >= m)
t = nchoosek(1:n,m);
nv = nchoosek(n,m);
for i = 1:nv
    y = zeros(n,1);
    x = A(:,t(i,:))\b;
    if all(x >= 0 & (x ~= inf & x ~= -inf))
        y(t (i, :)) = x;
    end
end
else
    error('Nuber of equations is greater than th neumber of variables.')
end
if ~isempty(vert)
    vert = delcols(vert);
else
    vert = [];
end
end

To test the code, the author used the system

A = [1 1 1 0; 0 1 0 1];
b = [6; 3];

and obtain the results

vert = feassol(A, b)
vert =
0 0 3 6
0 3 3 0
6 3 0 0
3 0 0 3

But whenever I run the code, I get

>> vert = feassol(A,b)
vert =
     []

What am I not doing right with the code? Any help will be much appreciated. Thanks in advance!

Answer 1

[Walter Roberson]

Where do you assign something nonempty to vert?

Why do you calculate y since you never use it?

[Hmm!]

You are right. But as I said the author just used the code to illustate the example I gave. The author never made mention of y. The question is a LP program in the form Ax = b, x>=0

Could you help fix this for me?

[Walter Roberson]

vert(:, end+1) = y;

[Hmm!]

>> vert = feassol(A,b)
Unrecognized function or variable 'y'.
Error in feassol (line 27)
    vert(:, end+1) = y; 
    
    %this error showed up after I pasted vert(:, end+1)=y; after "vert = [];"
    
    %where do I paste vert(:, end+1) = y;?

[Walter Roberson]

function vert = feassol(A, b)
% Basic feasible solutions vert to the system of constraints
% Ax = b, x >= 0.
% They are stored in columns of the matrix vert.

[m, n] = size(A);
warning off
b = b(:);
vert = [];
if (n >= m)
t = nchoosek(1:n,m);
nv = nchoosek(n,m);
for i = 1:nv
  y = zeros(n,1);
  x = A(:,t(i,:))\b;
  if all(x >= 0 & (x ~= inf & x ~= -inf))
      y(t (i, :)) = x;
      vert(:, end+1) = y;
  end
end
else
  error('Nuber of equations is greater than th neumber of variables.')
end
if ~isempty(vert)
  vert = delcols(vert);
else
  vert = [];
end
end

[Walter Roberson]

note that you test x>=0 but you also test about negative infinity. A nonnegative value cannot be negative infinity.

[Walter Roberson]

Also if you got that error message then you passed in an array with more rows than columns.

[Hmm!]

Another heckle...

>> feassol
Unrecognized function or variable 'delcols'.

Error in feassol (line 27)
  vert = delcols(vert);
  
  % How to do with delcols?

[Walter Roberson]

I do not know. You called decols in the code you supplied; no documentation has been supplied as to its purpose or its implementation.

But if I were to guess... I would guess it probably isn't needed.

[Hmm!]

Sorry. It is another written function that I had to called. I have just figure it out.

Answer 2

[Matt J]

As long as your feasible set is bounded, you can use this FEX submission instead,

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-polyhedra-in-terms-of-vertices-or-in-equalities

A = [1 1 1 0; 0 1 0 1];
b = [6; 3];

[args{1:4}]=addBounds([],[],A,b,[0;0;0;0]);
vert=lcon2vert(args{:}).'

for which I get the result,

vert =

    6.0000    3.0000   -0.0000   -0.0000
    0.0000    3.0000    3.0000   -0.0000
   -0.0000         0    3.0000    6.0000
    3.0000         0         0    3.0000

Answer 3

[ANURAG]

A=[ 2 3 -1 4;1 2 6 -7 ];

b=[8;-3];

c=[2 3 4 7];

n=size(A,2);

m=size(A,1);

if n>m

nCm = nchoosek(n,m);

p =nchoosek(1:n,m);

end

s=[];

for i=1: nCm

y=zeros(n,1);

A1=A(:,p(i,:));

X =inv(A1)*b;

if all(X>=0 & X~=inf & X~=-inf)

y(p(i,:))=X;

s=[s y];

end

error('Nuber of equations is greater than th neumber of variables.')

end

z=c*s;

[,index]=max(z);

BFS=s(:,index);

optval=[BFS,obj];

OPTIMAL_BFS=array2table(optval);

[DGM]

Is this supposed to be an answer? Is this a question?

Why are you posting multiple chunks of unexplained, unformatted code from different sources? Why would a reader choose one and not the other? Which one best addresses the original question?

Answer 4

[ANURAG]

[16:58, 25/02/2024] HEMANG SEN101: c=[5 3];

A=[3 5 ; 5 2];

b=[15;10];

x=0:1:max(b);

y1=(b(1,1)-A(1,1)*x)/A(1,2);

y2=(b(2,1)-A(2,1)*x)/A(2,2);

y1=max(0,y1);

y2=max(0,y2);

plot(x,y1,'red',x,y2,'blue')

title('Max')

xlabel('X axis')

ylabel('Y axis')

legend('3x+5y<=15','5x+2y<=10')

grid on

py1=find(y1==0); %% y-axis

py2=find(y2==0); %% x-axis

px=find(x==0);%%always 1

line1=[x(:,[py1,px]);y1(:,[py1,px])]';

line2=[x(:,[py2,px]);y2(:,[py2,px])]';

corpt=unique([line1;line2],'rows');

%find points of intersection

pt=[0;0];

for i=1:size(A,1)

A1=A(i,:);

B1=b(i,:);

for j=i+1:size(A,1)

A2=A(j,:);

B2=b(j,:);

A4=[A1;A2];

B4=[B1;B2];

%X4= A4/B4;

X= inv(A4)*B4;

pt=[pt X];

end

end

ptt=pt';

%phase 5: all cornor points

allpt = [ptt;corpt];

points=unique(allpt,"rows");

%Phase 6: cornor pts of feasible region

PT= constraint(points);

P= unique(PT,"rows");

% compute objective FXn

FX =sum(P.*c,2);

Vert_funs=[P,FX];

%find optimal value

[fxval,indfx]= max(FX);

optval = Vert_funs(indfx,:);

[16:59, 25/02/2024] HEMANG SEN101: Graphical

[17:01, 25/02/2024] HEMANG SEN101: %CONSTRAINT

function out = constraint(X)

x1 = X(:,1);

x2 = X(:,1);

cons1 = 3*x1 + 5*x2 - 15;

h1 = cons1>0;

X(h1,:) = [];

cons2 = 5*x1 + 2*x2 - 10;

h2 = cons2>0;

X(h2,:) = [];

out = X;

end

Answer 5

[ANURAG]

[03:39, 27/02/2024] Rachit: C=[40,24];

A=[20 50;80 50];

b=[4800;7200];

x=0:1:250;

y1=(b(1)-A(1,1).*x)./A(1,2);

y2=(b(2)-A(2,1).*x)./A(2,2);

y1=max(y1,0);

y2=max(y2,0);

plot(x,y1,'r',x,y2,'b');

xlabel('x');

ylabel('y');

title('Max Graph');

legend('y1','y2');

px=find(x==0);

py1=find(y1==0);

py2=find(y2==0);

Line1=[x(:,[py1 px]);y1(:,[py1 px])]'

Line2=[x(:,[py2 px]);y2(:,[py2 px])]'

corpt=unique([Line1;Line2],'rows');

pt=[0;0]

for i=1:size(A,1)

A1=A(i,:);

b1=b(i,:);

for j=i+1:size(A,1)

A2=A(j,:);

b2=b(j,:);

A4=[A1;A2];

b4=[b1;b2];

X=inv(A4)*b4;

pt=[pt X];

end

end

ptt=pt';

allpt=[ptt;corpt];

points=unique(allpt,'rows');

PT=constraints(points);

P=unique(PT,'rows');

FX=sum(P.*C,2);

VF=[P,FX];

[fxval,indfx]=max(FX);

optval= VF(indfx,:);

OPTIMAL_BFS = array2table(optval,'VariableNames',{'x1','x2','Value'});

OPTIMAL_BFS

fxval

[03:40, 27/02/2024] Rachit: function out = constraints(X)

x1=X(:,1);

x2=X(:,2);

cons1= 20*x1 + 50*x2 - 4800;

h1=find(cons1<0);

X(h1,:)=[];

cons2= 80*x1 + 50*x2 - 7200;

h2=find(cons2<0);

X(h2,:)=[];

out=X

end

Answer 6

[ANURAG]

=[1 1 1 0 0];

A=[2 3 -1 1 0; 3 -2 2 0 -1];

b=[4;1];

m=size(A,1);

n=size(A,2);

if n>m

ncm=nchoosek(n,m);

t=nchoosek(1:n,m);

sol=[];

for i=1:ncm

y=zeros(n,1);

A1=A(:,t(i,:));

X=inv(A1)*b;

if all (X>=0 & X~=inf)

y(t(i,:))=X;

sol=[sol y];

end

end

else error('No. of variables are less than constraints');

end

Z=C*sol;

[val,opt_idx]=max(Z);

bfs=sol(:,opt_idx);

optval=[bfs' val];

OPTSOL=array2table(optval,"VariableNames",{'x1','x2','x3','s1','s2','Value'});

OPTSOL