Simplex Method for Optimization Problems with Python
As an analyst, we often face optimization problems on our daily basis such as maximizing our profit, maximizing manufacturing capacity, etc. Before we are going too far, we need to know what is an optimization problem.
By definition optimization problem is the problem of finding the maximum solution from all feasible solutions.
Real life example of this is a carpenter problem. Suppose a carpenter asks your advice to optimize his sales. The carpenter sells tables and chairs for $8 and $5 respectively. From the carpenter, you know that in order to make a table he needs 9 units of lumber and 1 hour of work. While for a chair he needs 5 units of lumber and 1 hour of work. He only works 6 hours a day and there are only 45 units of lumber available each day.
We can summarize the story into the following tables with z as the maximum value he can get each day.
We can solve this problem using the simplex method.
SIMPLEX METHOD STEP BY STEP
Simplex method is an approach to solve linear programming models with the objective to find the optimal solution. While linear programming is a method to obtain the maximum outcome with linear constraints.
1. Converting real work problem into a mathematical problem
To solve the carpenter problem first we need to convert the real work problem into a mathematical problem. Let’s let x denotes the number of tables and y denotes the number of chairs.
Next, we need to define the objective function. For this case, we need to know the number of tables (x) and the number of chairs (y) the carpenter need to build in a day to optimize the profit. Since we already know the price of a table is $8.00 and the price of a chair is $5.00, we can write the objective function as:
Maximize:
z = 8x + 5y
After that, we need to define the constraints of our problem. The first constraint we know is the amount of time to make each table and chair is 1 hour, and he only works 6 hours a day. The second constraint is that there are only 45 units of lumber available each day, while it takes 9 units of lumber to make a table and 5 units of lumber to make a chair. Lastly, we know the number of tables and chairs the carpenter produce can’t be negative. From this, we can create the mathematical equations from our constraints:
Constraints:
x + y ≤ 6
9x + 5y ≤ 45
x, y ≥ 0
Now we are done converting real work problem into a mathematical problem (also commonly called standard form).
2. Defining Slack variables
Notes that our constraints are still in inequality form. Slack variables are additional variables that are used in linear constraints to transform inequality constraints into an equality constraint.
Since we have 2 variables x and y, we will need to slack variables namely s₁ and s₂. The canonical form will become:
Note: after adding slack variables, our constraints that previously use inequality (≤) are converted into equality (=).
3. Setting up the Tableau
A simplex tableau is used to perform row operations on the linear programming as well as to check the optimal solution. The tableau consists of the coefficient corresponding to constraint variables and the coefficients of the objective function.
To do this, first, we need to convert our objective function equal to zero:
z = 8x + 5y
— 8x — 5y + z = 0
Next we can start setting up our tableau based on variables in our objective function and constraints. First, put all variables into the column name, and the result will be put in column named right hand side (rhs). Then, put the coefficient of every function as a row (if the function doesn’t have specific variables, the value will be set as 0).
x + y + s₁ = 6
9x + 5y + s₂ = 45
— 8x — 5y + z = 0
Our tableau will be:
4. Check Optimality
Once the tableau has been completed, the model can be checked for optimality. To check the optimality using tableau, all values in the last row must contain values greater-than-or-equal-to (≥) zero.
Since the last row still have values -8 and -5, this means that our solution has not reached its optimal value. The next step is to identify the pivot variable.
5. Identify Pivot Variable
Pivot variable is used in row operations to check which variable will become the unit value and is a key factor in the unit value conversion. To do this, we need to find the key column by checking the minimum negative value in our objective function. In this case -8 is the minimum negative value, thus column x will be the pivot column in this iteration.
Column with the minimum values indicates that the pivot variables is in the column. Since the minimum value lies in column x, we will transform this column so that it will be greater-than (>) zero.
Next, we must look for the key row. To do this we need to find the minimum ratio between the rhs and x. In this case, 5 is the minimum value, thus, the second row will be the pivot row.
Since we already have the pivot column and pivot rows next we will find the pivot variable. Pivot variable is located at the intersection of pivot column and pivot row. In this example, 9 will be our pivot variable.
The next objective is to transform the tableau so that the pivot variable will be equal 1 and the rest rows in column x will equal 0.
6. Create the New Tableau
Since we already know that the previous tableau is not optimal. We will try to create new tableau to find new feasible optimal solution.
To make new tableau, we need to perform row operations to optimize the pivot variable while keeping the rest value in the tableau still equivalent.
1. To optimize the pivot variable, the pivot variable needs to be transformed into a unit value (value of 1). This can be done by dividing all values in pivot rows by the value of pivot variable. In this example, since the pivot variable is 9, then all values in pivot row will be divided by 9.
Note that the previous pivot variable is now equal to 1.
2. After the pivot variable is set to 1, next the rest of values in pivot column should be set to 0.
new first row = first row — new second row
new third row = third row + 8*new second row
Now we have created our 2nd tableau. Note that in our new tableau column x is already has a row which value equal to 1, and the rest rows equal to 0.
7. Recheck optimality
Next, we need to check the optimality just like we did in step 4.
Since the last row still contains negative value, we need to repeat step 5 to find pivot variable and recreate our tableau based on the new pivot variable.
8. Identify pivot variable
Since there’s only 1 column with with negative value, then it is certain that column y is our pivot column.
Next, we need to identify our pivot row by finding the smallest ratio between rhs and y. In this case, the 1st row will be our pivot row.
Finally, we need to define the pivot variable which is located at the intersection of the pivot row and pivot column. In the below example, the pivot variable is 4/9.
9. Create the new tableau
Just like in step 6,
1. Transform the pivot variable into unit value by dividing all values in pivot rows by the value of the pivot variable. In this example, since the pivot variable is 4/9, then all values in pivot row will be multiplied by 9/4.
2. After the pivot variable is set to 1, next the rest of values in the pivot column should be set to 0.
new second row = second row — 5/9*new first row
new third row = third row + 5/9*new first row
Now we have created our 3rd tableau. Note that in this tableau the column x and y already have a row which value equal to 1, and the rest rows equal to 0.
10. Check Optimality
Next, we need to recheck the optimality just like step 4 and 7.
Now the last row no longer have last row no longer have negative value. This implies that our tableau is already optimal.
11. Interpret the result
Interpreting the result is as easy as to find value = 1 in column x, y and z and then find the rhs value in the same row. Well now we can get rid of slack variable s₁ and s₂.
For this example:
0x + y + 0z = 9/4
y = 9/4 = 2.25x + 0y + 0z = 15/4
x = 15/4 = 3.750x + 0y + z = 41/4
z = 165/4 = 41.25
So the optimal solution for the carpenter is he needs to build 3.75 tables, and 2.25 chairs to gain an average profit $ 41.25 daily.
Simplex Method with Python
In this part, we will give an example of how to implement the simplex method using python. For this tutorial, we will use the scipy library called linprog which stands for linear programming.
Linprog library minimizes a linear objective function based on linear equality and inequality constraints. Since our carpenter’s problem is to optimize the profit while the linprog library only minimizes the objective function, there needs to be a slight adjustment in our objective function and our constraints.
The adjustment is simple as negating our objective function:
from:
Maximizes: z = 8x + 5yinto:
Minimizes: — z = — 8x — 5y
After we adjust the objective function, next we define our constraints.
x + y — s₁ — 0s₂= 6
9x + 5y —0s₁ — s₂ = 45
Notes that we add 0s₂ to the first equation and 0s₁ to the second equation so that both equations consistently have 4 variables in it. Next we are ready to code.
# import required library
import numpy as np
from scipy.optimize import linprogNext, we define the variables needed for the algorithm. There are at least 3 variables needed by the library.
- Inequality constraint matrix denotes as A. Each row specifies the coefficients of linear inequality constraint.
- Inequality constraint vector denotes as b. This tells us the upper limit of our resources.
- Linear objective function denotes as c that will be minimized.
A = np.array([[1, 1], [9, 5], [-1, 0], [0, -1]])
b = np.array([6, 45, 0, 0])
c = np.array([-8, -5])Finally, we can feed our variable into the library and add method = ‘simplex’ so that it will use the simplex method.
res = linprog(c, A_ub=A, b_ub=b, method='simplex')
resThe result shows as follows:
Attributes in x are the values of variables that minimize the objective function while satisfying the constraints. Attribute fun returns the optimal value of the objective function. Notes since the objective function is still in negation form, we need to multiply it with — 1 to get the actual result. So the optimal solution for the objective function is:
— ( — 41.25) = 41.25.
Conclusion
The simplex method is one of the most basic approaches to solve optimization problems. The limitation of this method is that it only works for a linear model.
This method is relatively easy to understand, and can also be done by only using hand. Though, there’s already a library that eases us to perform the procedure.
