Untitled

mail@pastecode.io avatar
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