Linear Programming Problem

Question

A chemical plant makes three major products on a weekly basis. Each of these products requires a certain quantity of raw chemical and different production times, and yields different profits. The pertinent information is given in Table 1. Note that there is sufficient warehouse space at the plant to store a total of 450kg/week.

                         Product I  Product II  Product III  Resource Availability
Raw Chemical        7kg          5kg           5kg               3000kg
Production Time   0.05h/kg   0.1h/kg     0.2h/kg          55h/week
Profit                   $30/kg      $30/kg      $35/kg


Table I: Datasheet of the three major products of the company.

Set up a linear programming problem to maximize profit and solve it using Simplex Method (manually), along with a graph and a MATLAB code to solve the problem using Simplex Method (with comments), with implementation in any one of these mathematical softwares: MAPLE/Mathcad/Mathematica, and an algorithm/pseudocode for the same.

Answer 1

Here your problem formulated as an LP would be to

Maximize Z = 30x1 + 30x2 + 35x3

subject to 7x1 + 5x2 + 5x3 <= 3000

0.05x1 + 0.1x2 + 0.2x3 <= 55

x1 + x2 + x3 <= 450

x1>=0, x2>= 0, x3>=0

where x1,x2,x3 contains the number of kg per product respectively. Now to cast it as LP with no inequality constraints we add slack variables x4,x5,x6 as

Maximize Z = 30x1 + 30x2 + 35x3 +0x4 + 0x5 + 0x6

subject to 7x1 + 5x2 + 5x3 + x4 = 3000

0.05x1 + 0.1x2 + 0.2x3 + x5 = 55

x1 + x2 + x3 + x6 = 450

x1>=0, x2>= 0, x3>=0

=================================================================================

main.m

clc

clear all

c = [30 30 35 0 0 0];

A = [7 5 5 1 0 0;

  0.05 0.1 0.2 0 1 0;

  1 1 1 0 0 1];

b = [3000;55;450];

[m,n]    = size(A);

 

TABLE = Simplex(A,b,-c);

 

x_opt = zeros(length(c),1); % extract the optimal x from simplex table

for j=1:length(c)

  if length(find(TABLE(:,j)==0))==m

    index= TABLE(:,j)==1;

    x_opt(j)=TABLE(index,end);

  end

end

x_opt

 

 

Simplex.m

function SimplexTable = Simplex(A,b,c)

 

[m,n]       = size(A);

SimplexTable        = zeros(m+1,n+m+1);

SimplexTable(end,n+1:end-1) = 1;

SimplexTable(1:m,1:n)    = A;

SimplexTable(1:m,end)    = b(:);

SimplexTable(1:m,n+1:n+m)  = eye(m);

 

for i = 1:m %now make all entries in bottom row zero

  SimplexTable(end,:) = SimplexTable(end,:)-SimplexTable(i,:);

end

 

SimplexTable = SIMPLEX_LOOP(SimplexTable(1:m,1:n+m),SimplexTable(1:m,end),SimplexTable(end,1:n+m));

 

A = SimplexTable(1:m,1:n);

b = SimplexTable(1:m,end);

SimplexTable  = SIMPLEX_LOOP(A,b,c);

 

end

 

%=================================

function SimplexTable = SIMPLEX_LOOP(A,b,c)

[m,n]    = size(A);

SimplexTable     = zeros(m+1,n+1);

SimplexTable(1:m,1:n) = A;

SimplexTable(m+1,1:n) = c(:);

SimplexTable(1:m,end) = b(:);

FLAG = true;

iterNo = 1;

while FLAG

  disp(['Iteration number = ',num2str(iterNo)])

  if any(SimplexTable(end,1:n)<0)%check if there is negative cost coeff.

    [~,J] = min(SimplexTable(end,1:n)); %yes, find the most negative

    if all(SimplexTable(1:m,J)<=0)

      error('Unbounded') % throw an error in case the problem is unbounded

    else

      ROW_PIVOT = 0;

      MINVAL = inf;

      for i = 1:m

        if SimplexTable(i,J)>0

          tmp = SimplexTable(i,end)/SimplexTable(i,J);

          if tmp < MINVAL

            MINVAL = tmp;

            ROW_PIVOT = i;

          end

        end

      end

      SimplexTable(ROW_PIVOT,:) = SimplexTable(ROW_PIVOT,:)/SimplexTable(ROW_PIVOT,J); % normalize the row

      for i=1:m+1

        if i ~= ROW_PIVOT

          SimplexTable(i,:)=SimplexTable(i,:)-sign(SimplexTable(i,J))*abs(SimplexTable(i,J))*SimplexTable(ROW_PIVOT,:);

        end

      end

    end

  else

    FLAG=false; % stop when optimal is reached

  end

  iterNo=iterNo+1;

end

end

=================================================================================

PRINTS:

Iteration number = 1

Iteration number = 2

Iteration number = 3

Iteration number = 4

Iteration number = 1

Iteration number = 2

Iteration number = 3

Iteration number = 4

x_opt =

233.3333

0

216.6667

283.3333

0

0

=================================================================================

which means that x1 = 233.3333 , x2 = 0, x3 = 216.6667