how can I solve an optimization problem by simplex method in matlab?

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?

Answer 1

[Matt J]

LINPROG, if you have it, has a simplex algorithm option.

[vatankhah]

can u explain how to use LINPROG to solve this example?(by matlab code please)

[Matt J]

Nope. But

 >> doc linprog

will give useful material and examples.

Answer 2

[behnam tj]

hi you can use linprog like this:

c=[-2 4];
A=[1 -5;2 1];
b=[3;1];
Aeq=[];
Beq=[];
x0=0;
lb=[0,0];
ub=[inf,inf];
ans=linprog(c,A,b,Aeq,Beq,lb,ub,x0)

Answer 3

[Tanvi]

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

%-------------------------------------------------------------------------