Matlab
unknown
plain_text
2 years ago
9.6 kB
5
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
clc
clear all
format short
%Min. z = 3x1 + 5x2,
%S.T. x1 + 3x2 ≥ 3
% x1 + x2 ≥ 2
%convert to max
%Max. z = -3x1 - 5x2,
%S.T. - x1 - 3x2 + s1 + 0s2 = -3
% - x1 - x2 + 0s1 + s2 = -2
c=[-3 -5 0 0]
A= [-1 -3 1 0; -1 -1 0 1]
b= [-3; -2]
BV=[3 4]
n=2
m=4
for i=1:50
B=A(:,BV)
cb=c(BV)
Xb=inv(B)*b
z=cb*Xb
Y=inv(B)*A
zjcj=cb*Y-c
if(Xb>=0)
disp('Feasibility Achieved')
break
else
[a,LV]=min(Xb)
for j=1:m
if(Y(LV,j)<0)
ratio(j)=zjcj(j)/Y(LV,j)
else
ratio(j)=inf
end
end
[l,EV]=min(abs(ratio))
BV
BV(LV)
LV
EV
BV(LV)=EV
end
end
disp('Basic Variables: ')
BV
%fprintf("fxn: \n")
cb
disp('Cost ')
Xb
disp('optimal value ')
z
zjcj=[inf zjcj z; BV' Y Xb]
clc
clear all
format short
cost = [2 10 4 5; 6 12 8 11;3 9 5 7]
supply=[12 25 20]
demand=[25 10 15 5]
n=size(cost,1)
m=size(cost,2)
if(sum(supply)==sum(demand))
disp('Balanced Problem')
elseif(sum(supply)>sum(demand))
disp('Unbalanced Problem')
demand = [demand sum(supply)-sum(demand)]
cost = [cost zeros(n,1)]
else
disp('Unbalanced Problem')
supply = [supply sum(demand)-sum(supply)]
cost = [cost; zeros(1,m)]
end
cc = cost
n=size(cost,1)
m=size(cost,2)
X=zeros(n,m)
for i=1:n
for j=1:m
temp=min(cost(:))
[r,c]=find(temp==cost)
y=min(supply(r),demand(c))
[val,index]=max(y)
pos_row=r(index)
pos_col=c(index)
X(pos_row,pos_col)=val
supply(pos_row)=supply(pos_row)-val
demand(pos_col)=demand(pos_col)-val
cost(pos_row,pos_col)=inf
end
end
cc
fc=cc.*X
final_cost=sum(fc(:))