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