Linear programming code not showing the solution

7 views (last 30 days)
Hmm!
Hmm! on 27 Feb 2021
Commented: DGM on 27 Feb 2024
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!

Answers (6)

Walter Roberson
Walter Roberson on 27 Feb 2021
Where do you assign something nonempty to vert?
Why do you calculate y since you never use it?
  9 Comments
Walter Roberson
Walter Roberson on 27 Feb 2021
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!
Hmm! on 28 Feb 2021
Sorry. It is another written function that I had to called. I have just figure it out.

Sign in to comment.


Matt J
Matt J on 27 Feb 2021
Edited: Matt J on 27 Feb 2021
As long as your feasible set is bounded, you can use this FEX submission instead,
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

ANURAG
ANURAG on 26 Feb 2024
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);
  1 Comment
DGM
DGM on 27 Feb 2024
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?

Sign in to comment.


ANURAG
ANURAG on 26 Feb 2024
[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

ANURAG
ANURAG on 26 Feb 2024
[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

ANURAG
ANURAG on 27 Feb 2024
=[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

Categories

Find more on Get Started with Optimization Toolbox in Help Center and File Exchange

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!