MA1508
Linear Algebra with Applications
MATLAB Assignment
4/10/2008
National University of Singapore
Lim Fang Jeng (U076372R)
Total number of pages: 12
This paper contains:
(1) MATLAB Code for Gram-Schmidt Process
a. Text files for problem (i) and (ii) --- Pg 2-5
(2) MATLAB Code for Linear Programming by Simplex Method
a. Text files for problem (i) and (ii) --- Pg 6-12
Page
2
Problem 1: Gram-Schmidt Process
function output=GSProcess format rat
% This function computes the orthogonal basis by Gram-Schmidt Process
%% Selection menu
way=menu('The vectors given are enterd manually or randomly generated?','Enter manually','Randomly generated');
switch way case 1
fprintf('Enter manually\n');
A=input('Please enter the vectors in T as rows the matrix A: '); d=size(A);
row=d(1,1); col=d(1,2); A
fid=fopen('gsprocess_manual.txt','w');
fprintf(fid,'(a) Matrix entered manually\nThe matrix A is: \n'); % Printing Matrix A into file
for i=1:row
fprintf(fid,'%6.1d ',A(i,:)); for j=1:1
fprintf(fid,'\n'); end
end
case 2
fprintf('Randomly generated\n');
row=input('Enter the number of rows of your generated matrix A: '); col=input('Enter the number of columns of your generated matrix A: '); A=round(10*rand(row,col))-5;
A
fid=fopen('gsprocess_rand.txt','w');
fprintf(fid,'(a) Matrix generated randomly.\nThe matrix A is: \n'); % Printing Matrix A into file
for i=1:row
fprintf(fid,'%6.1d ',A(i,:)); for j=1:1
fprintf(fid,'\n'); end
end end
% END of menu
%% Stage 1: Check the linear independence of vectors count=1;
R=rref(A); Rt=rref(A');
if R(row,1:col)==0
fprintf(fid,'The vectors are not linearly independent, but...\n'); fprintf('The vectors are not linearly independent, but...\n'); % Stage 1(b) Choosing of vectors
for i=1:col for j=1:row
if Rt(i,j)==1
fprintf(fid,'Row %d of the matrix A is linearly independent \n',j); fprintf('Row %d of the matrix A is linearly independent \n',j); X(count,:)=[A(j,:)];
B=X;
Page
3
count=count+1; break
else
continue end
end
end
% End of Stage 1(b) else
fprintf(fid,'The vectors are linearly independent\n\n'); fprintf('The vectors are linearly independent\n');
B=A; end
bsize=size(B); B
%% Printing of matrix B
fprintf(fid,'\n(b) The matrix B is: \n'); for i=1:bsize(1,1)
fprintf(fid,'%6.1d',B(i,:)); for j=1:1
fprintf(fid,'\n'); end
end
fprintf(fid,'Dimension, dim(T)= %d\n',rank(B)); fprintf('Dimension, dim(T)= %d\n',rank(B));
% END of stage 1
%% Stage 2: Gram-Schmidt Process - Finding orthonormal basis for S
% M=norm of the vectors ; coef= coeficient (uk.vn)/(||vn||^2)
% CLIMAX!!! Gram-Schmidt Process, here comes.. for i=1:bsize(1,1)
for j=1:i-1
M=norm(B(j,:))^2;
coef=dot(B(i,:),B(j,:))/M; B(i,:)=B(i,:)-coef*B(j,:); C=B;
end end
csize=size(C);
fprintf(fid,'The orthogonal set of S is \n'); disp('The orthogonal set of S is ');
C
%% Printing of matrix C fprintf(fid,'\n(c) C= \n'); for i=1:csize(1,1)
fprintf(fid,'%6.3g ',C(i,:)); for j=1:1
fprintf(fid,'\n'); end
end
%% Check for confirmation of orthogonal sets format short
fprintf(fid,'\n(d) Checking of confirmation of orthogonal sets\n'); for i=1:bsize(1,1)
Page
4
for j=1:i-1
D=dot(C(i,:),C(j,:)); if D<10^-10
D=0; else
fprintf('vectors are not all orthogonal'); return
end
fprintf(fid,'u%d.u%d= %d\n',j,i,D); fprintf('u%d.u%d= %d\n',j,i,D); end
end
% END of Stage 2
% END of GSProcess!!!!!!! fclose(fid);
Page
5
Output Text file
Text file (i):
(a) Matrix entered manually The matrix A is:
1 0 1 0 2 -2 1 1 1
The vectors are linearly independent
(b) The matrix B is: 1 0 1 0 2 -2 1 1 1 Dimension, dim(T)= 3
The orthogonal set of S is
(c) C=
1 0 1 1 2 -1 -0.333 0.333 0.333
(d) Checking of confirmation of orthogonal sets u1.u2= 0
u1.u3= 0 u2.u3= 0
Text file (ii):
(a) Matrix generated randomly. The matrix A is:
0 3 -2 4 2 0 3 -2 2 1 -2 -2
The vectors are not linearly independent, but... Row 1 of the matrix A is linearly independent Row 2 of the matrix A is linearly independent Row 3 of the matrix A is linearly independent
(b) The matrix B is: 0 3 -2 4 2 0 3 -2 2 Dimension, dim(T)= 3
The orthogonal set of S is
(c) C=
0 3 -2 4 0.615 0.923 0.0714 -0.143 -0.214
(d) Checking of confirmation of orthogonal sets u1.u2= 0
u1.u3= 0 u2.u3= 0
Page
6
Problem 2: Linear Programming
Code:
function output=LPSolve format rat
clc
file=fopen('LPSolve_b.txt','w');
%% Input of matrices A C1 and b
A=input('Please input the matrix A: '); C1=input('Please input matrix C1: '); b=input('Please input b in rows: '); b=b';
Asize=size(A);
bsize=size(b); K=b>=0; B=eye(Asize(1,1)); C1size=size(C1); C2=zeros(1,bsize(1,1)); C=[C1 C2];
for i=1:C1size(1,2)
X(3*i-2)='x'; X(3*i-1)=num2str(i); X(3*i)=' '; end
X
for j=1:bsize(1,1)
S(3*j-2)='s'; S(3*j-1)=num2str(j); S(3*j)=' '; end
Xb=S
if (Asize(1,2)==C1size(1,2))&&(Asize(1,1)==bsize(1,1)) if (K==ones(bsize(1,1),1))
fprintf('The dimensions are correct and b>=0\d'); else
return end
else
fprintf('Please insert matrices with correct dimension and ensure that b>=0 !\d');
return end
% Initiate Simplex Table
fprintf('\n\nThe simplex table of your LP is:\n'); fprintf(file,'The simplex table of your LP is:\n'); siminit=[1 -C1 -C2 zeros(1);zeros(Asize(1,1),1) A B b]; disp(siminit);
% Printing of Simplex Table onto text file for i=1:bsize(1,1)+1
fprintf(file,'%6.5g ',siminit(i,:)); for j=1:1
fprintf(file,'\n'); end
end
% END of INPUT
%% Selection for maximization or minimization maxc1=max(-C1);minc1=min(-C1);
mode=menu('What is the objective of your problem?','Maximization','Minimization'); switch mode
case 1
Page
7
fprintf('\nThis is a maximization problem\n'); fprintf(file,'\nThis is a maximization problem\n'); if minc1>=0
fprintf('Optimality has reached, simplex method is not required. Have a nice day!\n');
fprintf(file,'Optimality has reached, simplex method is not required. Have a nice day!\n');
fclose(file); return
else
fprintf('\nProceeding to Simplex method...\n'); fprintf(file,'\nProceeding to Simplex method...\n'); end
case 2
fprintf('\nThis is a minimization problem\n'); fprintf(file,'\nThis is a minimization problem\n'); if maxc1<=0
fprintf('Optimality has reached, simplex method is not required. Have a nice day!\n');
fprintf(file,'Optimality has reached, simplex method is not required. Have a nice day!\n');
fclose(file); return
else
fprintf('\nProceeding to Simplex method...\n'); fprintf(file,'\nProceeding to Simplex method...\n'); end
end
% END of SELECTION
%% Obtaining feasible starting solution AB=[A B]; [m n]=size(AB);
for i=1:n-m
fprintf('x%d=0, ',i); fprintf(file,'x%d=0, ',i); end
fprintf('These are non-basic variables\n'); fprintf(file,'These are non-basic variables\n');
for j=1:m
fprintf('s%d=%d, ',j,b(j,:));
fprintf(file,'s%d=%d, ',j,b(j,:)); end
fprintf('These are basic variables'); fprintf(file,'These are basic variables');
fprintf('\nThis is a feasible starting solution\n'); fprintf(file,'\nThis is a feasible starting solution\n');
% END of Feasible
%% Solving of LP - (INITIALIZATION)
b2=b; Anew=A; ABnew=AB; Cb=C2; Ca=C; p=0;
for iteration=1:inf
fprintf('\nIteration %d: \n',iteration);
fprintf(file,'\n\nIteration %d: \n',iteration);
% Determine of entering and leaving variables
% i=loop variable indicating the position of the entering variable enter=[''];
for i=1:n
if mode==1
Page
8
if Ca(:,i)==-min(-Ca)
fprintf('The entering variable is ');
enter(:,1)='x'; enter(:,2)=num2str(i); enter(:,3)=' '; disp(enter);
fprintf(file,'The entering variable is %s\n',enter); for j=1:bsize(1,1)
c(j,:)=b2(j,:)/ABnew(j,i); end
break else
fprintf('Searching your entering variable..\n'); end
else
if Ca(:,i)==-max(-Ca)
fprintf('The entering variable is ');
enter(:,1)='x'; enter(:,2)=num2str(i); enter(:,3)=' '; disp(enter);
fprintf(file,'The entering variable is %s\n',enter); for j=1:bsize(1,1)
c(j,:)=b2(j,:)/ABnew(j,i); end
break else
fprintf('Searching your entering variable..\n'); end
end end
% Leaving variable selection
% j=loop variable for filtering unwanted rations in determining leaving variable count=1;
d=[]; for j=1:m
if ABnew(j,i)>0
d(count,1)=c(j,1); % New ration matrix after deleting -ve & 0 denominator
count=count+1; else
continue end
end
% k=loop variable for leaving variable position leave=[''];psize=size(p);
for k=1:m
if c(k,:)==min(d)
fprintf('The leaving variable is '); for ps=1:psize(1,2) if k==p(:,ps)
leave(:,1)=S(3*k-2); leave(:,2)=S(3*k-1); break
else
leave(:,1)='s'; leave(:,2)=num2str(k); end
end
leave(:,3)=' '; disp(leave);
fprintf(file,'The leaving variable is %s\n',leave); break
else
continue end
end
Page
9
p(:,iteration)=k;
fprintf('The set of basic variables in current iteration is:\n'); S(3*k-2)=X(3*i-2); S(3*k-1)=X(3*i-1);
Xb=S
fprintf(file,'The set of basic variables in current iteration is: S=( %s)\n',S);
% END of INITIALIZATION
%% Determine Basis, B, Cb, and Update of Simplex table
F=eye(m); F(:,[k])=[inv(B)*AB(:,i)]; B=B*F;
B
% Printing of basis (matrix B) fprintf(file,'The matrix B is:\n'); for basisi=1:m
fprintf(file,'%6.g ',B(basisi,:)); for basisj=1:1
fprintf(file,'\n'); end
end
fprintf('The inverse of B is: \n'); iB=inv(B); disp(iB);
Cb(:,[k])=C(:,i);
Sim=[1 (Cb*iB*A-C1) (Cb*iB-C2) (Cb*iB*b); zeros(m,1) iB*A iB iB*b]; Sim
% Printing of Simplex Table of Current Iteration
fprintf(file,'The simplex table for this iteration is:\n'); for simi=1:m+1
fprintf(file,'%7.3g\t ',Sim(simi,:)); for simj=1:1
fprintf(file,'\n'); end
end
Cnew=[(Cb*iB*A-C1) (Cb*iB-C2)]; if mode==1
if (min(Cnew)>=0)
fprintf('This is the optimal solution. Simplex Method finished!\n'); fprintf(file,'This is the optimal solution. Simplex Method finished!\n'); break
else
fprintf('Optimality not reached yet..\n'); fprintf(file,'Optimality not reached yet..\n');
Ca=-Cnew; b2=iB*b; Anew=iB*A; ABnew=[iB*A iB]; F=eye(m);
end else
if (max(Cnew)<=0)
fprintf('This is the optimal solution. Simplex method finished!\n'); fprintf(file,'This is the optimal solution. Simplex Method finished!\n'); break
else
fprintf('Optimality not reached yet..\n'); fprintf(file,'Optimality not reached yet..\n');
Ca=-Cnew; b2=iB*b; Anew=iB*A; ABnew=[iB*A iB]; F=eye(m);
end end end
Page
1 0
%% Presentation of final results btest=iB*b;
fprintf(file,'The set of decision variables are:\n'); for str=1:(n-m)
fprintf('%s%s= ',X(:,3*str-2),X(3*str-1)); fprintf(file,'%s%s= ',X(:,3*str-2),X(3*str-1));
test=1; % Determine of which decision variable(s) to be set to zero for str2=1:m
if (X(:,3*str-2)==S(:,3*str2-2))&&(X(:,3*str-1)==S(:,3*str2-1)) fprintf('%g\n',btest(str2,:));
fprintf(file,'%g\n',btest(str2,:)); test=0;
break end
end
if test==1
fprintf('%g\n',0); fprintf(file,'%g\n',0); end
end
z=Cb*iB*b; z
fprintf(file,'The objective function value is\nz= %g\n',z); fclose(file);
Page
1 1
Output Files
Text file (i)
The simplex table of your LP is:
1 -3 -2 -0 -0 -0 -0 0 0 1 2 1 0 0 0 6 0 2 1 0 1 0 0 8 0 -1 1 0 0 1 0 1 0 0 1 0 0 0 1 2 This is a maximization problem
Proceeding to Simplex method...
x1=0, x2=0, These are non-basic variables
s1=6, s2=8, s3=1, s4=2, These are basic variables This is a feasible starting solution
Iteration 1:
The entering variable is x1 The leaving variable is s2
The set of basic variables in current iteration is: S=( s1 x1 s3 s4 ) The matrix B is:
1 1 0 0 0 2 0 0 0 -1 1 0 0 0 0 1
The simplex table for this iteration is:
1 0 -0.5 0 1.5 0 0 12 0 0 1.5 1 -0.5 0 -0 2 0 1 0.5 0 0.5 0 -0 4 0 0 1.5 0 0.5 1 -0 5 0 0 1 0 0 0 1 2
Iteration 2:
The entering variable is x2 The leaving variable is s1
The set of basic variables in current iteration is: S=( x2 x1 s3 s4 ) The matrix B is:
2 1 0 0 1 2 0 0 1 -1 1 0 1 0 0 1
The simplex table for this iteration is:
1 0 0 0.333 1.33 0 0 12.7 0 0 1 0.667 -0.333 0 -0 1.33 0 1 0 -0.333 0.667 0 -0 3.33 0 0 0 -1 1 1 -0 3 0 0 0 -0.667 0.333 0 1 0.667
This is the optimal solution. Simplex Method finished! The set of decision variables are:
x1= 3.33333 x2= 1.33333
The objective function value is z= 12.6667
Page
1 2
Text file (ii)
The simplex table of your LP is:
1 -1 -2 1 -0 -0 -0 0 0 2 1 1 1 0 0 14 0 4 2 3 0 1 0 28 0 2 5 5 0 0 1 30 This is a maximization problem
Proceeding to Simplex method...
x1=0, x2=0, x3=0, These are non-basic variables s1=14, s2=28, s3=30, These are basic variables This is a feasible starting solution
Iteration 1:
The entering variable is x2 The leaving variable is s3
The set of basic variables in current iteration is: S=( s1 s2 x2 ) The matrix B is:
1 0 1 0 1 2 0 0 5
The simplex table for this iteration is:
1 -0.2 0 3 0 0 0.4 12 0 1.6 0 0 1 0 -0.2 8 0 3.2 0 1 0 1 -0.4 16 0 0.4 1 1 0 0 0.2 6
Iteration 2:
The entering variable is x1 The leaving variable is s1
The set of basic variables in current iteration is: S=( x1 s2 x2 ) The matrix B is:
2 0 1 4 1 2 2 0 5
The simplex table for this iteration is:
1 0 0 3 0.125 0 0.375 13 0 1 0 0 0.625 0 -0.125 5 0 0 0 1 -2 1 0 0 0 0 1 1 -0.25 0 0.25 4
This is the optimal solution. Simplex Method finished! The set of decision variables are:
x1= 5 x2= 4 x3= 0
The objective function value is z= 13
END of MA1508 MATLAB ASSIGNMENT
