Analytics Vidhya
Published in

Analytics Vidhya

Optimization: Simplex Method for Maximization.

Photo taken from Wikipedia

Introduction

The Simplex method is an approach to solving linear programming models by hand using slack variables, tableaus, and pivot variables as a means to finding the optimal solution of an optimization problem. 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

This document breaks down the Simplex method into the above steps and follows the example linear programming model shown below throughout the entire document to find the optimal solution.

Maximize:

To Identify Maximize we must follow below steps.

Steps:

  1. Convert all inequality subject equations by adding slack variables. Also create objective function equal to zero by moving all values on one side.
    Equations after adding slack variable (u,v,w)
    Where u,v,w≥0

2. A Simplex tableau is used to perform row operations on the linear programming model as well as to check a solution for optimality. The tableau consists of the coefficient corresponding to the linear constraint variables and the coefficients of the objective function. In the tableau below, the bolded top row of the tableau states what each column represents. The following two rows represent the linear constraint variable coefficients from the linear programming model, and the last row represents the objective function variable coefficients.

Now create simplex tableau by creating coefficients of all subject equation and add Object equation at the bottom.

3. To calculate ratio, we can select the minimum value from the last row and follow below steps.

How to identify Pivot column:

In the above table, -6 is the smallest negative in the last row. This will designate the z column to contain the pivot variable which is highlighted by yellow.

How to identify Pivot row:

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. The pivot variable can be identified by looking at the bottom row of the tableau and the indicator. Assuming that the solution is not optimal, pick the smallest negative value in the bottom row. One of the values lying in the column of this value will be the pivot variable. To find the indicator, divide the beta values of the linear constraints by their corresponding values from the column containing the possible pivot variable. The intersection of the row with the smallest non-negative indicator and the smallest negative value in the bottom row will become the pivot variable.

Divide the pivot column with constant in corresponding row and identify the values.

Solving for the ratio gives us a value of (900/1 = 900) for the first constraint, a value of (350/1 = 350) for the second constraint, and value of third constraint (400/1 = 400). Due to 350 being the smallest non-negative ratio, the pivot value will be in the second row which is highlighted in green and intersection for pivot row and column will be pivot element which has a value of 1 which is highlighted in Red color.

Now that the pivot variable has been identified, we can work on further solution to make it optimize.

4. To optimize the pivot variable, it will need to be transformed into a unit value (value of 1). As, the pivot element is already 1 here we do not have to make it unit value.

5. After the unit value has been determined, Work on formula which will make the other values in the column containing the unit value will become zero. This is because slack variable and other variable value can be identified, and solution is being optimized.

Formulas: R1=R1-R2 , R3=R3-R2 and R4=R4+6R2

Applying above formulas on our simplex tableau will result into below table.

The optimal solution is obtained because all values in the bottom row are greater than or equal to zero.

Here, basic variables are u, z, w, and p.
Non basic variables are x, v and y.

From this we can obtain variable values as below,

x=0, y=0, v=0, u=550, w = 50, p = 2100, z = 350.

Now to validate the equation,

The maximum optimal value is 2100 and found at (0,0, 350) of the objective function.

Conclusion

The Simplex method is an approach for determining the optimal value of a linear program by hand. The method produces an optimal solution to satisfy the given constraints and produce a maximum zeta value. To use the Simplex method, a given linear programming model needs to be in standard form, where slack variables can then be introduced. Using the tableau and pivot variables, an optimal solution can be reached.

Glossary

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.

Inequality is an expression that does not have one definite solution and is distinguishable by its ‘greater than’ or ‘less than’ symbols in the place of a traditional equal sign.

Linear program is a model used to achieve the best outcome given a maximum or minimum equation with linear constraints.

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

Optimal solution of a maximization linear programming model are 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.

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 method is an approach to solving linear programming models by hand using slack variables, tableaus, and pivot variables as a means to finding the optimal solution of an optimization problem.

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.

Standard form is the baseline format for all linear programs before solving for the optimal solution.

Reference: libretexts, Book: Blitzer, Thinking Mathematically | Pearson.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store