Simplex Method MATLAB Program


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:



Subjected to Ax = b , xi  ≥ 0

Where, x = (1, x2, x3, x4 0.. . . .. xn) which are the variables in the problem and  c = ( 1, c2, c3, c4, . . . . cn ) which are the coefficients of the objective function.

A is a p x n matrix and b = ( b1, b2, b3, . . . . , bp ), bj ≥ 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, xi ≥ 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:

Simplex Method Program in Matlab - Tableau Form

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:

Simplex Method in Matlab - Canonical Form

In order to remove the coefficient CTB from objective function, we can apply additional row addition transformation. The result of this pricing out process is:

Simplex Method Program in Matlab - Final Matrix Form

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

Simplex Method MATLAB Code:

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:

Simplex Method Program in Matlab - Output

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.