Simplex Method

Introduction 

The Simplex method is an approach to solving linear programming models by hand using slack variables, tableaus, and pivot variables to find the optimal solution to an optimization problem. The Simplex method was developed by Dr. George Dantzig in 1947. A linear program is a method of achieving the best outcome given a maximum or minimum equation with linear constraints.  Most linear programs can be solved using an online solver such as MATLAB, but the Simplex method is a technique for solving linear programs by hand.  To solve a linear programming model using the Simplex method, the following steps are necessary:

●  Standard form

●  Introducing slack variables

●  Creating the tableau

●  Pivot variables

●  Creating a new tableau

●  Checking for optimality

●  Identify optimal values

Some of the most important points in studying the simplex method are given below.

• • • • •  Basic variables are variables that are non-negative in terms of the optimal solution.

• • • • •  Constraints are a series of equalities and inequalities that are a set of criteria necessary to satisfy when finding the optimal solution.

• • • • •  Non-basic variables are variables that are zero in terms of the optimal solution.

• • • • • The optimal solution of a maximization linear programming model is the values assigned to the variables in the objective function to give the largest zeta value.  The optimal solution would exist on the corner points of the graph of the entire model.

• • • • • The pivot variable is used in row operations to identify which variable will become the unit value and is a key factor in the conversion of the unit value.

• • • • •  Simplex tableau is used to perform row operations on the linear programming model as well as for checking optimality.

• • • • •  Slack variables are additional variables that are introduced into the linear constraints of a linear program to transform them from inequality constraints to equality constraints.

Let us see the Simplex method with an example.

Example:

         Maximize    Z = 6x1+ 8x2

         Subject to:   5x1 + 10x2 ≤ 60

                                 4x1 + 4x2     40

                                 x1 ≥ 0, x2 ≥0

STEP 01: Standard Form

       The standard form is the baseline format for all linear programs before solving the optimal solution

       Maximize   6x1+ 8x2 – Z = 0

         Subject to:   5x1 + 10x2 + S1 = 60

                                 4x1 + 4x2   + S2    = 40

                                 x1 ≥ 0, x2 ≥0, S1 ≥0, S2 ≥0

S1 and S2 are Slack Variables.

STEP 02: Construct the Initial Simplex Tableau

•   Each inequality constraint appears in its row.

•   But non-negativity constraints do not appear as rows in the simplex tableau.

•   Write the objective function in the bottom row.

Initial Table

Min Ratio = (6, 10) = 6

• The most positive entry in the bottom row identifies the pivot column. [Pivot Column = x2 Column]

• After that, Calculate the quotients.

•  The smallest quotient identifies a row. [Pivot Row = S1 Row]

•  The intersection of the row with the smallest non-negative indicator and the largest positive value in the bottom row will become the pivot element. [Pivot Element = 10]

STEP 05: Create the New Tableau

•  Pivoting is a process of obtaining a 1 in the location of the pivot element, and then making all other entries zeros in that column. So, the task is to make the pivot element a 1 by dividing the entire first row by 10.

•  After the unit value has been determined, the other values in the column containing the unit value will become zero.

•  To keep the tableau equivalent, the other variables not contained in the pivot column or pivot row must be calculated by using the new pivot values.

•  New pivot values can be obtained by using the following formula.

b      c

a      d

         Pivot Element = a

         After pivot the new value of c = c – (b × d) / a

        Example:

                     New value = 4 – (5 × 4) / 10 = 2

•   After pivot, we obtain the new table.

• After getting the new table, we apply step 03 again.

• When we apply step 03 we can see this is not the optimal table as evidenced by the presence of a positive number (2) in the index row.

• Therefore, we apply step 04.

•  Then we can obtain the following table.

Min Ratio (12, 8) = 8                      Pivot Element = 2

After considering step 05, we obtain the next table.

• We consider step 03 again.

• Since there are no positive entries in the index row, we can see this is the optimal table.

• So, an Optimal Solution has been reached.

x1* = 8         x2* = 2         max Z = 64

Basic Variables = x1, x2

Non-Basic Variables = S1, S2