Derived by the concept of simplex and suggested by T. S. Motzkin, simplex method is a popular algorithm of mathematical optimization in the field of linear programming. Albeit the method doesn’t work on the principle of simplices (i.e generalization of the notion of a triangle or tetrahedron to arbitrary dimensions), it is interpreted that it operates on simplicial cone and these assume the form of proper simplices with additional constrains.

In this tutorial, we’re going to write a program for **Simplex method in MATLAB**, discussing its theoretical background and working procedure.

## Theoretical Background of Simplex Method:

Consider a standard form of linear program on which the simplex method operates i.e. linear program of form:

Maximize:

c^{T}.x

Subjected to Ax = b , x_{i }≥ 0

Where, x = (_{1}, x_{2}, x_{3}, x_{4 }0.. . . .. xn) which are the variables in the problem and c = (_{ 1, }c_{2}, c_{3}, c_{4}, . . . . c_{n }) which are the coefficients of the objective function.

A is a p x n matrix and b = ( b_{1}, b_{2}, b_{3}, . . . . , b_{p} ), b_{j} ≥ 0 which represent the constants.

The linear form can easily be transformed into standard form without loss of generality due to availability of straight forward process of conversion.

The feasible region of above problem in geometric term is:

Ax ≤ b, x_{i} ≥ 0 which is a convex polytope and probably unbound.

**Simple Tableaux:**

All the linear program in the standard form can be replicated in tableau form. The tableau form of above linear program in standard form is:

In this form, the first row always defines the objective function of the problem and the other remaining rows are defined to represent the constrains of the problem.

This form can be converted into canonical form by arranging the columns of A in such a way that it contains an identity matrix of order p.

When the respective tableau is multiplied by the inverse of the same matrix, the result will tableau in canonical form:

Suppose, the following matrix be tableau in canonical form:

In order to remove the coefficient C_{T}^{B }from objective function, we can apply additional row addition transformation. The result of this pricing out process is:

where, ZB represent the value of objective function at the corresponding feasible solution.

## Simplex Method MATLAB Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
function [ val mat ] = simplex_min(A,C ) % for optimizing given condition 'C' with constraints 'A' % A is an augmented matrix % All the constraints are should be of the form L.H.S. <= R.H.S. % where LHS includes the variable.And the pre-assumed constraint is that all % the variables are +ve A =[1 2 3 4 0 0 0; 0 3 2 1 1 0 10; 0 2 5 3 0 1 15] C = [0 0 0] [ na ma] = size(A); [ nc mc] = size(C); % check for matrix C if nc ~= 1 disp('Pls check the given objective function.It should be row matrix ') return end % check for the no. of variables in constraints and in objective function if ma-1 ~= mc disp('Check the given objective function or augmented matrix') return end %making the initial tebula X = [ A(:,1:ma-1) eye(na) A(:,ma) ]; X(na+1,:) = zeros(1,na+ma); X(na+1,1:mc) = -C;% Indicator row. % initial tebula is ready %CONDITION : All the elements in the indicator row should be -ve in the final tebula while sum(X(na+1,1:na+ma-1) > zeros(1,na+ma-1)) ~= 0 % finding the largest matrix element in the co-efficient matrix xw = X(1:na , 1:na + ma - 1); [ v1 i1 ] = max(xw); [ v2 j ] = max(v1);% determining j and hence the pivot coloumn i = i1(1,j); Y = X(1:na,na+ma)./X(1:na,j);% determining lowest positive ratio for finding pivot row a1 = sign(Y); a1 = a1 + ones(na,1); y1 = Y.*a1/2; [ v3 i ] = min(y1);% finding lowest non -ve no if v3 == 0 ys = sort(y1); k = 1; while ys(k,1) <= 0 k = k + 1; end b = ys(k,1); [ i j1 ] = find( y1 == b ); end X = elimination(X,i,j); % Pls see the function ' elimination ' % finding -ve no in the column matrix ele = find(sign(X(na+1,1:na+ma-1))== -1); [ ne me ] = size(ele); if me == 0 break else j = ele(1,1);% fixing pivot column Y = X(1:na,na+ma)./X(1:na,j); a1 = sign(Y); a1 = a1 + ones(na,1); y1 = Y.*a1/2; [ v3 i ] = min(y1); if v3 == 0 ys = sort(y1); k = 1; while ys(k,1) <= 0 k = k + 1; end b = ys(k,1); [ i j1 ] = find( y1 == b ); X = elimination(X,i,j); end end % for checking boundedness of solution for k = 1:na+ma-1 un = sign(X(:,k)); if un == - ones(na+1,1) disp(' The solution is not bounded') return end end end % Obtaining the solution from Final tebula opt = X( na+1, ma+na); sol = X(1:na , 1:ma-1); for k = 1: ma-1 % looking for the column which forms the rrel for matix A t = roots( [sol(:,k);0] ); [ nt mt ] = size(t); if t == zeros(nt,1) mat(1,k) = X(na - nt +1, na+ma); else mat(1,k) = 0; end end disp('Co-efficient matrix correspond to optimum solution ') mat disp('and optimum value is') opt function X = elimination(X,i,j) % Pivoting (i,j) element of matrix X and eliminating other column % elements to zero [ nX mX ] = size( X); a = X(i,j); X(i,:) = X(i,:)/a; for k = 1:nX if k == i continue end X(k,:) = X(k,:) - X(i,:)*X(k,j); end |

The above Matlab code for Simplex Method doesn’t need any input while running the program. The necessary data of the linear programming are already embedded in the source code. This code solves the following typical problem of linear programming:

Minimization of: Z = -2x – 3y – z

Subjected to:

3x + 2y + z ≤ 10

2x + 2y + z ≤ 15

X, y, z ≥ 0

The sample output of the Matlab program is given below:

If you have any question regarding Simplex method, its Matlab program, or its theory, ask us from the comments section. You can find more Numerical Methods Tutorial using Matlab here.