Untitled
unknown
plain_text
2 years ago
7.8 kB
8
Indexable
%% 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