how can I solve an optimization problem by simplex method in matlab?
75 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Respuestas (3)
Tanvi
el 1 de Mzo. de 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 comentarios
Ver también
Categorías
Más información sobre Multiobjective Optimization en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!