Simplex Method : The Easy Way

An example based approach to understand the simplex optimization method

5 min readNov 20, 2021

Invented by Dantzig in 1946, the simplex method is still one of the most elegant methods to solve linear programming problems (LP). An LP is concerned with finding the optimal solution of a linear function given some linear constraints. It is used in real-world optimization problems across multiple domains. Today let’s try to understand the working of this algorithm in an easy and concise manner using an example to guide us through the way.

The Method

Set up/transform an LP in standard maximization form.
Set up initial simplex tableau
Identify pivot
Find optimal tableau using Gauss-Jordan method
Check optimality of tableau
Find optimal solution

Step 1 : Transform LP into the standard maximization form

Consider the following example :

(Note : In case of a minimization problem, it can be converted into its dual maximization problem, when multiplied by -1.)

The standard form of an LP is where all the constraints are equations and all variables are non-negative. The following transformation steps can be followed to convert all the inequalities into equality constraints.

If a constraint is of type (x + y ≤ c), use a slack variable ‘s’ (where ‘s’ is non-negative), such that x+y+s = c.

2. If a constraint is of type (x + y ≥ c), use a surplus variable ‘s’ (where ‘s’ is non-negative), such that x+y-s = c.

Using this transformation method on our example we get the following system of equations

Step 2 : Set up the initial simplex tableau

We need to create a tableau from the system of equations we just obtained. It looks something like this

Step 4: Identify the pivot

In the simplex tableau, the pivot is identified using the below two conditions

The pivot column is chosen by identifying the most negative entry in the bottom row of the tableau.
The pivot row is identified by dividing the constants (C column in the tableau) by the coefficients of the pivot column. The row containing the smallest quotient would be the pivot row.

(A detailed explanation of this method can be found here.)

In our example, the ‘y’ column is the pivot column since it contains -40 and the pivot row is R3 (row 3), since 12/2 =6 is the smallest coefficient in the pivot column. Hence, our pivot element is 2.

Step 3 : Identify optimal values by performing pivot operations using Gauss-Jordan Elimination Method

After we identified the pivot element, we will perform the Gauss Elimination method (perform row transformations on R1, R2, R3, R4). We will transform the pivot element to a 1 and all of the of other elements in the pivot column as 0. In this case, we will use the following row transforms in order to get our result

R3->R3/2
R1->R1- R3
R2->R2- R3
R4->R4+40R3

Our output tableau will be

Before we proceed two the next steps, there are two terms you need to be familiar with.

Basic-variable : Generally the pivot column is said to represent a basic variable. Although, if you put it simply, the basic variable is any variable in the tableau that has only one non-zero element i.e represents the identity matrix. In Tableau 1.3, y, s1, s2, and P are basic variables. For a mathematical definition please check here.

Non-basic variable : A non-basic variable on the other hand does not represent the identity matrix and has more than one non-zero element. In Tableau 1.3, s3 and x are the non-basic variables.

When we need to determine a basic feasible solution, we will set all the non-basic variables to 0, which will give us the maximum values of the basic variables. Setting s3, x = 0, we get y = 6, s1 = 4, s2 = 1, P = 240.

Now, according to the simplex method, if there is no negative coefficient in the bottom most row (i.e R4) we can stop here. If not then we repeat steps 3 & 4 until we eliminate all negative terms in the bottom row and find our optimal solution. In our tableau, we have -10 in R4, so we need to perform another iteration of step 3 and 4.

Iteration 2

Using the procedure in step 3, we identify our new pivot as 1/2 in R2 and the ‘x’ column.

We will use the following row transformations to make all entries 0 in the pivot 1 in the ‘x’ column.

R2->2R2
R1->R1–3/2R2
R3->R3–1/2R2
R4 ->R4+10R2

Setting the non-basic variables to 0, we get x =2, y=5, s1=1 and P = 260. Hence our optimal values for x and y are 2,5. For those interested in solving such problems using a graphical approach please refer here. This method can be used for solving system of equations that have over a million variables (this can be done using an online solver or a program).

References