Untitled

unknown
plain_text
7 months ago
7.8 kB
2
Indexable
Never
```%% Simplexx Method
%% Question:
%               Max Z= 2x1 + 5x2
%                       x1 + 4x2 <= 24
%                      3x1 +  x2 <= 21
%                       x1 +  x2 <= 9
%%
clc
clear all
format short

Noofvariables=2
C = [2 5]
a = [1 4; 3 1; 1 1]
b = [24; 21; 91]

s=eye(size(a,1))
A= [a s b]

cost=zeros(1,size(A,2))
cost(1:Noofvariables)=C
bv = Noofvariables+1:1:size(A,2)-1
zjcj=cost(bv)*A-cost
zcj= [zjcj; A]

simptable=array2table(zcj);
simptable.Properties. VariableNames (1:size(zcj,2))={'x_1','x_2', 's_1', 's_2', 's_3', 'sol'}

RUN=true;
while RUN
if any (zjcj<0); %check for (most) negative value
fprintf( 'current BPS is net optimal \n')
zc=zjcj(1:end-1)
[Enter_val, pvt_col]= min (zc)
if all(A(:,pvt_col)<=0)
error('LPP is unbounded all entries are <=0 in column %d', pvt_col)
else
sol=A(:,end)
column=A(:,pvt_col)
for i=1:size(A,1)
if column(i)>0
ratio(i)= sol(i)./column(i)
else
ratio(i)=inf
end
end
[leaving_var, pvt_row]=min(ratio)
end
bv(pvt_row)=pvt_col;
pvt_key=A(pvt_row, pvt_col);
A(pvt_row,:) = A(pvt_row,:)./pvt_key;
for i=1:size(A, 1)
if i~=pvt_row
A(i,:)=A(i,:)-A(i, pvt_col).*A(pvt_row, :)
end
end
zjcj=zjcj-zjcj(pvt_col).*A(pvt_row, :)
zcj=[zjcj; A]
table=array2table(zcj)
table.Properties.VariableNames(1:size(zcj,2))={'x_1','x_2', 's_1', 's_2', 's_3', 'sol'}
else
RUN=false;
fprintf( 'The current BPS is optimal \n')
end
end

%% Big M Method
% Question:
%           Max Z=-2x1 -  x2
%           S.T.   3x1 +  x2  = 2
%                  4x1 + 3x2 >= 6
%                   x1 + 2x2 <= 3
%                   x1 ,  x2 >= 0
%% Introducing slack and artificial Variables
% Question:
%           Min Z=-2x1 -  x2 + 0s1 + 0s2 -  Ma1 -  Ma2
%           S.T.   3x1 +  x2 + 0s1 + 0s2 +   a1 +  0a2 = 3
%                  4x1 + 3x2 -  s1 + 0s2 +  0a1 +   a2 = 6
%                  1x1 + 2x2 + 0s1 + 1s2 +  0a1 +  0a2 = 3
%                   x1 ,  x2 , s1, s2, a1, a2 >= 0
%% Input
clc
clear all
format short

Cost=[-2 -1 0 0 -10000 -10000 0]
A= [3 1 0 0 1 0 3; 4 3 -1 0 0 1 6; 1 2 0 1 0 0 3]
BV= [5 6 4]

Variables = {'x_1','x_2', 's_1' ,'s_2','A_1', 'A_2', 'Sol'}

ZjCj = Cost(BV)*A - Cost
zcj=[Cost;ZjCj;A];
bigmtable=array2table (zcj);
bigmtable.Properties.VariableNames(1:size(zcj,2))= Variables

%% Start Loop
RUN= true;
while RUN
ZC=ZjCj(1:end-1)
if any (ZC<0)
fprintf(' The current BFS is not optimal\n');
[ent_col,pvt_col] = min(ZC)
fprintf('Entering Col =%d \n', pvt_col)
sol= A(:, end)
Column=A(:,pvt_col)
if Column<=0
error('LPP is unbounded');
else
for i=1:size(A, 1)
if Column(i)>0
ratio(i)=sol(i)./Column(i);
else
ratio(i)= inf
end
end
[MinRatio, pvt_row]= min (ratio);
fprintf('leaving Row=%d \n', pvt_row);
end
BV(pvt_row)=pvt_col;
pvt_key=A(pvt_row, pvt_col);
A(pvt_row, :)= A(pvt_row, :)./ pvt_key;
for i=1:size(A, 1)
if i~=pvt_row
A(i,:)=A(i,:)-A(i,pvt_col).*A(pvt_row,:);
end
end
ZjCj = ZjCj - ZjCj(pvt_col).*A(pvt_row, :);
ZCj = [ZjCj;A]
TABLE=array2table (ZCj);
TABLE.Properties.VariableNames (1:size(ZCj,2))=Variables
else
RUN=false;
fprintf(' Current BFS is Optimal \n');
end
end
%% Two Phase Method
% Question:
%           Min Z= 3x1 + 5x2
%           S.T.    x1 + 3x2 >= 3
%                   x1 +  x2 >= 2
%                   x1 ,  x2 >= 0
%% Introducing slack and artificial Variables
% Question:
%           Min Z= 3x1 + 5x2 + 0s1 + 0s2 -  a1 -  a2
%           S.T.    x1 + 3x2 -  s1 + 0s2 +  a1 + 0a2 = 3
%                   x1 +  x2 + 0s1 - 1s2 + 0a1 +  a2 = 2
%                   x1 ,  x2 , s1, s2, a1, a2 >= 0
%% Input
format short
clear all
clc

Variables = {'x_1', 'x_2', 's_1', 's_2', 'a_1', 'a_2', 'Sol'}
OVariables = {'x_1', 'x_2', 's_1', 's_2', 'Sol'}
OrigC = [ 3 5 0 0 -1 -1 0]
Info = [1 3 -1 0 1 0 3; 1 1 0 -1 0 1 2]
BV = [5 6]

%% Phase I
Cost = [0 0 0 0 -1 -1 0] %%% Cost of Phase I
A= Info
StartBV = find(Cost<0)

%%% Compute Zj - Cj
ZjCj = Cost(BV)*A - Cost
InitialTable = array2table( [ ZjCj;A ]);
InitialTable.Properties.VariableNames (1:size(A,2)) = Variables

fprintf("***************************************\n")
fprintf("*********** PHASE I STARTS ************\n")
fprintf("***************************************\n")

%%%% Start Loop
RUN = true;
while RUN
ZC = ZjCj(:, 1:end-1);
if any(ZC<0)           %%% Check any negative value

%%% Entering Variable
[EnterCOl pvt_col] = min(ZC)
fprintf('Entering Column = %d \n', pvt_col)

%%% Leaving Variable
sol = A(:, end)
Column = A(:, pvt_col)
if Column<0
fprintf('Unbounded Solution\n')
else
for i=1:size(A,1)
if Column(i)>0
ratio(i) =sol(i)./Column(i)
else
ratio(i)=inf
end
end
[MinRatio, pvt_row] = min(ratio)
fprintf('Leaving Row = %d \n', pvt_row)
end
%%% Update the BFS
BV(pvt_row) = pvt_col

%%% Pivot Key
pvt_key = A(pvt_row, pvt_col)

%%% Updating the Entries
A(pvt_row, :) = A(pvt_row,:)./pvt_key
for i=1:size(A,1)
if i~=pvt_row
A(i,:)= A(i,:) - A(i,pvt_col).*A(pvt_row,:)
end
end
ZjCj = ZjCj - ZjCj(pvt_col).*A(pvt_row,:)

%Printing
ZCj = Cost(BV)*A - Cost
InitialTable = array2table( [ ZCj;A ]);
InitialTable.Properties.VariableNames (1:size(ZCj,2)) = Variables

%Loop
BFS(BV)=A(:,end)
else
RUN= false;
fprintf('Current BFS is best\n')
fprintf('Phase end\n')
BFS=BV;
fprintf('Optimal Solution reached \n\n')
end
%else

end

%% Phase II
fprintf("***************************************\n")
fprintf("*********** PHASE II STARTS ***********\n")
fprintf("***************************************\n")

A(:, StartBV)=[]
OrigC(:,StartBV)=[]
Cost = OrigC
BV=BFS
Variables = OVariables
%%%% Start Loop
RUN = true;
while RUN
ZC = ZjCj(:, 1:end-1);
if any(ZC<0)           %%% Check any negative value

%%% Entering Variable
[EnterCOl pvt_col] = min(ZC)
fprintf('Entering Column = %d \n', pvt_col)

%%% Leaving Variable
sol = A(:, end)
Column = A(:, pvt_col)
if Column<0
fprintf('Unbounded Solution\n')
else
for i=1:size(A,1)
if Column(i)>0
ratio(i) =sol(i)./Column(i)
else
ratio(i)=inf
end
end
[MinRatio, pvt_row] = min(ratio)
fprintf('Leaving Row = %d \n', pvt_row)
end
%%% Update the BFS
BV(pvt_row) = pvt_col

%%% Pivot Key
pvt_key = A(pvt_row, pvt_col)

%%% Updating the Entries
A(pvt_row, :) = A(pvt_row,:)./pvt_key
for i=1:size(A,1)
if i~=pvt_row
A(i,:)= A(i,:) - A(i,pvt_col).*A(pvt_row,:)
end
end
ZjCj = ZjCj - ZjCj(pvt_col).*A(pvt_row,:)

%Printing
ZCj = Cost(BV)*A - Cost
InitialTable = array2table( [ ZCj;A ]);
InitialTable.Properties.VariableNames (1:size(ZCj,2)) = Variables

%Loop
BFS(BV)=A(:,end)
else
RUN= false;
fprintf('Current BFS is best\n')
fprintf('Phase end\n')
BFS=BV;
fprintf('Optimal Solution reached \n\n')
end
%else

end

%% Value of optimal Solution
FINAL_BFS=zeros(1,size(A,2));
FINAL_BFS(BFS)=A(:,end);
FINAL_BFS(end)=sum(FINAL_BFS.*OrigC);

OptimalBFS = array2table( FINAL_BFS );
OptimalBFS.Properties.VariableNames (1:size(OptimalBFS,2)) = OVariables```