how can I solve an optimization problem by simplex method in matlab?
101 views (last 30 days)
Show older comments
I want to solve this optimization problem by simplex method in matlab, for example we have:
min 2x1-4x2
x1-5x2 <=3
2x1+x2 <=1
x1,x2>=0
we want to find min(2x1-4x2) , how can I find this in matlab by simplex method?
0 Comments
Answers (3)
Tanvi
on 1 Mar 2023
function simplex_method(x1,x2,a1,b1,a2,b2,s1,s2,p1,p2)
%------------------------------------------------------------------------------
% Code to solve linear optimization problems using the simplex method to
% maximize an objective function.
%
% Function call: simplex_method(x1,x2,a1,b1,a2,b2,s1,s2,p1,p2)
%
% x1 : coefficient of variable X1 in the objective function
% x2 : coefficient of variable X2 in the objective function
% a1 : coefficient of the variable X1 in the first constraint equation
% b1 : coefficient of the variable X2 in the first constraint equation
% a2 : coefficient of the variable X1 in the second cnostraint equation
% b2 : coefficient of the variable X2 in the second constraint equation
% s1 : slack variable S1
% s2 : slack variable S2
% p1 : RHS of the first constraint equation
% p2 : RHS of the second constraint equation
%
% Author: Abhinav Roy
%------------------------------------------------------------------------------
num_var = 2; % number of variables
if nargin < 10
error('Please enter the required number of arguments. Type help simplex_method to get more imformation about the function');
end
itr = 0;
B = [0 p1 p2]'
disp(['The augmented matrix after iteration: ' num2str(itr)]);
A = [1 -x1 -x2 0 0 0; 0 a1 b1 s1 0 p1; 0 a2 b2 0 s2 p2]
[N,M] = size(A);
disp(['The number of rows of the augmented matrix: ' num2str(N)]);
disp(['The number of columns of the augmented matrix: ' num2str(M)]);
index = 1; % The counter for determining when to stop the iterative process
% Beginning of the iteration for solving
while index == 1
itr = itr + 1;
% code segment for determining the pivot element.
for j = 2:M
if A(1,j) < 0
pivot_column = j;
break;
end
end
var = A(:,M)./A(:,pivot_column);
temp = var(2);
for i = 3:N
if var(i) < temp
temp = var(i);
end
end
for i = 2:N
if var(i) == temp
pivot_row = i;
end
end
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~');
disp(['Pivot Row for this iteration: ' num2str(pivot_row)]);
disp(['Pivot Column for this iteration: ' num2str(pivot_column)]);
% code segment for carrying out the elementary row operations for the
% given iteration step
if A(pivot_row, pivot_column) > 0 % condition if the pivot element is positive
if (pivot_row > 1 || pivot_row < N)
for i = 1:(pivot_row - 1)
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
for i = (pivot_row+1):N
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
elseif pivot_row == 1
for i = 2:N
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
else
for i = 1:(N-1)
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
end
end
if A(pivot_row,pivot_column) < 0 % condition if the pivot element is negative
if (pivot_row > 1 || pivot_row < N)
for i = 1:(pivot_row - 1)
if A(i,pivot_column) < 0
temp = (A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
for i = (pivot_row+1):N
if A(i,pivot_column) < 0
temp = -(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
elseif pivot_row == 1
for i = 2:N
if A(i,pivot_column) < 0
temp = (A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
else
for i = 1:(N-1)
if A(i,pivot_column) < 0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
end
end
for i = 1:num_var
arr1 = A(:,1+i);
arr(i) = nnz(arr1);
end
if sum(arr) == num_var
index = 0;
else
index = 1;
end
disp(['The augmented matrix after iteration: ' num2str(itr)]);
A
if index == 0
P = A(:,M);
[val,idx] = max(P(:));
disp(['The maximum value of the objective function is: ' num2str(val)]);
end
end
%-------------------------------------------------------------------------
function simplex_method(x1,x2,a1,b1,a2,b2,s1,s2,p1,p2)
%------------------------------------------------------------------------------
% Code to solve linear optimization problems using the simplex method to
% maximize an objective function.
%
% Function call: simplex_method(x1,x2,a1,b1,a2,b2,s1,s2,p1,p2)
%
% x1 : coefficient of variable X1 in the objective function
% x2 : coefficient of variable X2 in the objective function
% a1 : coefficient of the variable X1 in the first constraint equation
% b1 : coefficient of the variable X2 in the first constraint equation
% a2 : coefficient of the variable X1 in the second cnostraint equation
% b2 : coefficient of the variable X2 in the second constraint equation
% s1 : slack variable S1
% s2 : slack variable S2
% p1 : RHS of the first constraint equation
% p2 : RHS of the second constraint equation
%
% Author: Abhinav Roy
%------------------------------------------------------------------------------
num_var = 2; % number of variables
if nargin < 10
error('Please enter the required number of arguments. Type help simplex_method to get more imformation about the function');
end
itr = 0;
B = [0 p1 p2]'
disp(['The augmented matrix after iteration: ' num2str(itr)]);
A = [1 -x1 -x2 0 0 0; 0 a1 b1 s1 0 p1; 0 a2 b2 0 s2 p2]
[N,M] = size(A);
disp(['The number of rows of the augmented matrix: ' num2str(N)]);
disp(['The number of columns of the augmented matrix: ' num2str(M)]);
index = 1; % The counter for determining when to stop the iterative process
% Beginning of the iteration for solving
while index == 1
itr = itr + 1;
% code segment for determining the pivot element.
for j = 2:M
if A(1,j) < 0
pivot_column = j;
break;
end
end
var = A(:,M)./A(:,pivot_column);
temp = var(2);
for i = 3:N
if var(i) < temp
temp = var(i);
end
end
for i = 2:N
if var(i) == temp
pivot_row = i;
end
end
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~');
disp(['Pivot Row for this iteration: ' num2str(pivot_row)]);
disp(['Pivot Column for this iteration: ' num2str(pivot_column)]);
% code segment for carrying out the elementary row operations for the
% given iteration step
if A(pivot_row, pivot_column) > 0 % condition if the pivot element is positive
if (pivot_row > 1 || pivot_row < N)
for i = 1:(pivot_row - 1)
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
for i = (pivot_row+1):N
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
elseif pivot_row == 1
for i = 2:N
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
else
for i = 1:(N-1)
if A(i,pivot_column) < 0
temp = abs(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
end
end
if A(pivot_row,pivot_column) < 0 % condition if the pivot element is negative
if (pivot_row > 1 || pivot_row < N)
for i = 1:(pivot_row - 1)
if A(i,pivot_column) < 0
temp = (A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
for i = (pivot_row+1):N
if A(i,pivot_column) < 0
temp = -(A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
elseif A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
elseif pivot_row == 1
for i = 2:N
if A(i,pivot_column) < 0
temp = (A(i,pivot_column)/A(pivot_row,pivot_column));
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
else
for i = 1:(N-1)
if A(i,pivot_column) < 0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) + temp*A(pivot_row,:);
end
if A(i,pivot_column) >0
temp = A(i,pivot_column)/A(pivot_row,pivot_column);
A(i,:) = A(i,:) - temp*A(pivot_row,:);
end
end
end
end
for i = 1:num_var
arr1 = A(:,1+i);
arr(i) = nnz(arr1);
end
if sum(arr) == num_var
index = 0;
else
index = 1;
end
disp(['The augmented matrix after iteration: ' num2str(itr)]);
A
if index == 0
P = A(:,M);
[val,idx] = max(P(:));
disp(['The maximum value of the objective function is: ' num2str(val)]);
end
end
%-------------------------------------------------------------------------
0 Comments
See Also
Categories
Find more on Multiobjective Optimization in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!