Making Chappie¶
Try me¶
Problem definition¶
The company Tetravaal located in Johannesburg manufactures two types of robots, Model \(P_{1}\) and Model \(P_{2}\). The production plant is consisted of four different sections: metal machining, plastic moulding, electrical work and assembly. The metal machining section has a capacity of 7500 units of \(P_{1}\) or 6000 units of \(P_{2}\) per month.
Plastic moulding can process 5000 units of \(P_{1}\) or 9000 units of \(P_{2}\) per month.
Electrical work can process 6000 units of \(P_{1}\) or 7000 units of \(P_{2}\) per month.
In Assembly, there are two assembly lines that work in parallel, one per each robot model.
The first assembly line can process 4000 units of \(P_{1}\) per month
The second assembly line can process 5000 units of \(P_{2}\) per month
Knowing that the unitary profit of \(P_{1}\) is 500€ and that the unitary profit of \(P_{2}\) is 600€, and that both robots have a great demand and therefore all manufactured robots are sold, Michelle Bradley, CEO of Tetravaal, asks his engineering team:
Calculate the number of units of each robot that needs to be manufactured to maximise profit for the company.
Model¶
We want to maximise the company profits:
\(\max z = 500x_{1} + 600x_{2}\)
where z represents the profits (€). The decision variables are:
\(x_{1}:\) units of \(P_{1}\) per month \(x_{2}:\) units of \(P_{2}\) per month
The objective function is subject to the following constraints:
\(x_{1}/7500+x_{2}/6000 \leq 1\) Metal machining constraint
\(x_{1}/5000+x_{2}/9000 \leq 1\) Plastic moulding constraint
\(x_{1}/6000 + x_{2}/7000 \leq 1\) Electrical work constraint
\(x_{1} \leq 4000\) First assembly line constraint
\(x_{2} \leq 5000\) Second assembly line constraint
Solution using Linprog¶
Reformulating the problem¶
First we need to define the problem model to the format expected by Linprog. Recall that we need to express our problem as: linear programming problems expressed in the form:
\(\min z = c^T*x\)
s.t. \(A_{ub}*x \leq b_{ub}\)
\(A_{uc}*x = b_{uc}\)
\(l \leq x \leq u\)
The vector \(c\) is:
That is, since our objective function is of type maximize, we use the equivalent minimization problem and the solution will be the negative of our original objective variable.
The matrix \(A_{ub}\) is:
\(A_{ub} = \begin{bmatrix} \frac{1}{7500} & \frac{1}{6000}\\ \frac{1}{5000} & \frac{1}{9000}\\ \frac{1}{6000} & \frac{1}{7000}\\ \end{bmatrix}\)
The vector \(b_{ub}\) is:
\(b_{ub} = [1, 1, 1]^T\)
Now, \(l\) is going to contain the minimum values of the decision variables, or lower bound. Since both variables need to be non-negative:
\(l^T = [0, 0]^T\)
and finally, \(u\) is going to contain the maximum values or upper bound, since x cannot be higher than 12, the upper bounds are:
\(u^T = [4000, 5000]^T\)
[1]:
# Let's start importing the linprog function of the optimize package of SciPy
from scipy.optimize import linprog
# We are going to use panda to display the results as tables using Panda
import pandas as pd
#And we will use numpy to perform array operations
import numpy as np
#We will use display and Markdown to format the output of code cells as Markdown
from IPython.display import display, Markdown
# Objective function coefficient vector
c = np.array([-500, -600])
# And the constraints, the Matrix A. Since all constraints are of type less or equal
A=np.array([[1/7500, 1/6000], #Coefficients of the first constraint
[1/5000, 1/9000], #Coefficients of the second constraint
[1/6000, 1/7000],
[1/4000, 0],
[0, 1/5000]]) #Coefficients of the third constraint
# And vector b
b = np.array([1, 1, 1, 1, 1]) #limits of the three constraints
#Bounds for x1
x1_bounds = (0, None) # Here we could as well use 4000 limit, but if we do so, the shadow price would be more difficult to find within the provided solution
# Bounds for x2
x2_bounds = (0, None)
res = linprog(c, A_ub=A, b_ub=b, bounds=[x1_bounds, x2_bounds])
print(res.message)
print(f"result of the objective function is: {-res.fun}")
var_df = pd.DataFrame(index=['x_1', 'x_2'])
var_df['solution'] = res.x
var_df['coefficients'] = -c
var_df['reduced costs'] = res.lower.marginals
display(var_df)
con_df = pd.DataFrame(index=['Metal Machining', 'Plastic Moulding', 'Electrical Work', 'Assembly 1', 'Assembly 2'])
con_df['RHS'] = b
con_df['slacks'] = res.slack
# Since the objective function is of type maximize, we need to change the sense of the marginals
con_df['shadow_prices'] = -res.ineqlin.marginals
display(con_df)
Optimization terminated successfully. (HiGHS Status 7: Optimal)
result of the objective function is: 3654545.454545455
| solution | coefficients | reduced costs | |
|---|---|---|---|
| x_1 | 2727.272727 | 500 | 0.0 |
| x_2 | 3818.181818 | 600 | 0.0 |
| RHS | slacks | shadow_prices | |
|---|---|---|---|
| Metal Machining | 1 | 0.000000 | 3.272727e+06 |
| Plastic Moulding | 1 | 0.030303 | 0.000000e+00 |
| Electrical Work | 1 | 0.000000 | 3.818182e+05 |
| Assembly 1 | 1 | 0.318182 | 0.000000e+00 |
| Assembly 2 | 1 | 0.236364 | 0.000000e+00 |