**Submitted By:**
Arnav Barman
3COE15
102053038

**Codes covered:**
- Simplex Method
- BigM Method
- Two Phase Method
- Dual Simplex Method
- Transportation Problem: LCM Method

---

## 1.Simplex Method

### Code

clc
clear all
a=[3 -1 2 1 0 0; -2 4 0 0 1 0; -4 3 8 0 0 1];
b=[7; 12; 10];
A=[a b];
bv=[4 5 6];
cost=[-1 3 -2 0 0 0 0];
zjcj=cost(bv)*A-cost;
var={'x1','x2','x3','s1','s2','s3','Solution'};

sTable=[A; zjcj];
array2table(sTable,'VariableNames',var)

RUN=true;
while RUN
	if any(zjcj(1:end-1)<0)
		fprintf('Current BFS not optimal');
		zc=zjcj(1:end-1);
		[enter,pcol]=min(zc);
	if all(A(:,pcol)<=0)
		fprintf('LPP Unbounded');
	else
		sol=A(:,end);
		col=A(:,pcol);
		for i=1:size(A,1)
			if col(i)>0
				ratio(i)=sol(i)./col(i);
			else
				ratio(i)=inf;
			end
		end
		[exit,prow]=min(ratio);
	end
	bv(prow)=pcol;
	pkey=A(prow,pcol);
	A(prow,:)=A(prow,:)./pkey;
	for i=1:size(A,1)
		if i~=prow
			A(i,:)=A(i,:)-A(i,pcol)*A(prow,:);
		end
	end
	zjcj=cost(bv)*A-cost;
	nTable=[zjcj; A];
	array2table(nTable,'VariableNames',var)

	else
		RUN=false;
		fprintf('Optimal Value: %f \n', zjcj(end));
	end
end

### Output

---

## 2.BigM Method

### Code

clc
clear all

M=1000;
artifical_var=[6];

a=[1 1 1 0 0 0;5 2 0 1 0 0;2 8 0 0 -1 1];
b=[2;10;12];
A=[a b];
bv=[3 4 6];
cost=[5 3 0 0 0 -M 0];
zjcj=cost(bv)*A-cost;
var={'x1','x2','s1','s2','s3','A1','Solution'};

sTable=[zjcj; A];
array2table(sTable,'VariableNames',var)

RUN=true;
while RUN
	if any(zjcj(1:end-1)<0)
		fprintf('Current BFS not optimal');
		zc=zjcj(1:end-1);
		[enter,pcol]=min(zc);
	if all(A(:,pcol)<=0)
		fprintf('LPP Unbounded');
	else
		sol=A(:,end);
		col=A(:,pcol);
		for i=1:size(A,1)
			if col(i)>0
				ratio(i)=sol(i)./col(i);
			else
				ratio(i)=inf;
			end
		end
		[exit,prow]=min(ratio);
	end
	bv(prow)=pcol;
	pkey=A(prow,pcol);
	A(prow,:)=A(prow,:)./pkey;
	for i=1:size(A,1)
		if i~=prow
			A(i,:)=A(i,:)-A(i,pcol)*A(prow,:);
		end
	end
	zjcj=cost(bv)*A-cost;
	nTable=[zjcj; A];
	array2table(nTable,'VariableNames',var)

	else
		RUN=false;
		if any(bv==artifical_var(1))
			error('Infeasible Solution!');
		else
			fprintf('The table is optimal!');
		end
		z=input(' Enter 0 for minimization and 1 for max \n');
		if z==0
			Obj_value=-zjcj(end);
		else
			Obj_value=zjcj(end);
		end
		fprintf('The final optimal value is % f \n',Obj_value);
	end
end

### Output

---

## 3.Two Phase Method

### Code

clc
clear all

Variables={'x1','x2','s1','s2','A1','A2','sol'};
OVariables={'x_ 1','x_ 2','s_ 1','s_ 2','sol'}; 
OrigC=[-3 -5 0 0 -1 -1 0];
a=[1 3 -1 0 1 0; 1 1 0 -1 0 1];
b=[3;2];
A=[a b];

fprintf('********** PHASE-1 ********** \n')

cost=[0 0 0 0 -1 -1 0]
Artifical_var=[5 6]
bv=[5 6];
 
zjcj=cost(bv)*A-cost;
simplex_table=[zjcj;A];
array2table(simplex_table,'VariableNames',Variables)
RUN=true;
while RUN
if any(zjcj(1:end-1)<0)
 fprintf(' the current BFS is not optimal \n')
 zc=zjcj(1:end-1);
 [Enter_val, pvt_col]= min(zc);
 if all(A(:,pvt_col)<=0)
 error('LPP is Unbounded all enteries 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_val, 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=cost(bv)*A-cost;
 next_table=[zjcj;A];
 table=array2table(next_table,'VariableNames',Variables)
else
 RUN=false;
 if any(bv==Artifical_var(1)) || any(bv==Artifical_var(2))
     error('Infeasible solution');
 else
  fprintf('optimal table of phase-1 is achieved \n');
 end
end
end


fprintf('********** PHASE-2 ********** \n')
A(:,Artifical_var)=[]; 
OrigC(:,Artifical_var)=[];
cost=OrigC;
zjcj=cost(bv)*A-cost;
simplex_table=[zjcj;A];
array2table(simplex_table,'VariableNames',OVariables)

RUN=true;
while RUN
if any(zjcj(1:end-1)<0)
 fprintf('The current BFS is not 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_val, 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=cost(bv)*A-cost;
next_table=[zjcj;A];
 table=array2table(next_table,'VariableNames',OVariables)
else
 RUN=false;
  fprintf('The current BFS is optimal \n');
  z=input(' Enter 0 for minimization and 1 for max \n');
    if z==0
        Obj_value=-zjcj(end);
    else
        Obj_value=zjcj(end);
    end
    fprintf('The final optimal value is %f \n',Obj_value);
 end
end

### Output

---

## 4.Dual Simplex Method

### Code

clc
clear all

a=[-1 -1 1 1 0;-1 2 -4 0 1];
b=[-5;-8];
A=[a b];
bv=[4 5];
cost=[-2,0,-1,0,0,0];
zjcj=cost(bv)*A-cost;
var={'x1','x2','x3','s1','s2','Solution'};

sTable=[zjcj; A];
array2table(sTable,'VariableNames',var)

while true
	sol=A(:,end);
	if any(A(:,end)<0)
		fprintf("The current basic variable is not feasible");
        [exit,prow] = min((A(:,end)));
        for i=1:size(A,2)-1
            if(A(prow,i)<0)
                ratio(i) = zjcj(i)./A(prow,i);
            else
                ratio(i) = -inf;
            end
        end
        [enter,pcol]=max(ratio);
        A(prow,:) = A(prow,:)./A(prow,pcol);
        
        for i=1:size(A,1)
            if(i~=prow)
                A(i,:) = A(i,:)-A(i,pcol).*A(prow,:);
            end
        end
        
        bv(prow) = pcol;
        zjcj=cost(bv)*A-cost;
        nTable = [zjcj;A];
        array2table(nTable,"VariableNames",var)
    else
        fprintf("The Current Basic solution is feasible")
        nTable = [zjcj;A];
        array2table(nTable,"VariableNames",var)
        break
    end
end

### Output

---

## 5.Transportation Problem: LCM Method

### Code

clc
clear all
format short
Cost=[11 20 7 8; 21 16 10 12; 8 12 18 9];
A=[50 40 70];
B=[30 25 35 40];
if(sum(A)==sum(B))
	fprintf("The problem is balanced!!");
else
	fprintf("The problem is unbalanced!!");
	if(sum(A)<sum(B))
		Cost(end+1,:)=zeros(1,size(B,2))
		A(end+1)=sum(B)-sum(A)
	elseif(sum(B)<sum(A))
		Cost(:,end+1) = zeros(1,size(A,2))
		B(end+1)=sum(A)-sum(B)
	end
end
ICost = Cost;
X = zeros(size(Cost)); %allocation matrix in different matrix
[m,n] = size(Cost);
for i=1:m
	for j=1:n
		hh = min(Cost(:)); % minimum cost
		if(hh==inf)
			break
		end
		[Row_index,Col_index] = find(hh==Cost)
		% maximum allocation
		x11=min(A(Row_index),B(Col_index))
		[Value,index] = max(x11);
		ii = Row_index(index);
		jj = Col_index(index);
		y11=min(A(ii),B(jj))
		X(ii,jj) = y11
		A(ii)=A(ii)-y11
		B(jj)=B(jj)-y11
		if(B(jj)==0)
			Cost(:,jj) = inf
		end
		if(A(ii) == 0)
			Cost(ii,:) = inf
		end
	end
end
Init_Cost = ICost.*X
temp = sum(sum(Init_Cost));
fprintf("The initial solution of LCM is: %d\n ",temp)

### Output

---