In this post, we’ll talk about the Python Scipy module and the idea of linear programming problems, including how to maximize the objective function and obtain the best solution.
Linear Programming
Linear Programming consists of an objective function (Z) and some constraints. According to the situation, the mode will be either maximum or minimum. In a business example, let’s say you want to make the most money possible, so you would maximize the objective function, and when you had to pay employees’ costs or salaries, you would aim to decrease the objective function.
Maximize: Z = 3x1 + 2x2
Constraints:
- x1 + 2x2 ≤ 4,
- 3x1 + 2x2 ≥ 6,
- x1 + 4x2 ≤ 2,
- x1 ≥ 0 and x2 ≥ 0
A Real-world Linear Programming Problem:
A company manufactures two products X and Y, which require, the following resources. The resources are the capacities machine M1, M2, and M3. The available capacities are 50, 25, and 15 hours respectively in the planning period. Product X requires 1 hour of machine M2 and 1 hour of machine M3. Product Y requires 2 hours of machine M1, 2 hours of machine M2 and 1 hour of machine M3. The profit contribution of products X and Y are Rs.5/- and Rs.4/- respectively.
Here, depending on the provided data, we will first create the mathematical model of the problem.
Formulation:
Future will write the LPP in the format of the Linear Equations
Maximize: Z = 5x + 4y
Constraints:
- 2y ≤ 50
- x + 2y ≤ 25
- x + y ≤ 15
- x ≥ 0 and y ≥ 0
As you can see, product x offers a profit of 5 rupees per unit, whereas product y offers a profit of 4 rupees per unit. Given that this problem involves maximizing profit, we must determine the company’s highest profit. We can solve this linear programming issue either by the graphical approach, the simplex method, or other methods in order to determine the highest profit for the company.
You could use paper and pencil to compute the profit by following a step-by-step process, but in this post, we’ll focus on how Python programming can help us solve our problem. Scipy is a module for the Python programming language that lets you use the collection of LPP methods to solve linear programming problems.
Step-by-Step Implementation:
Import the linear programming package of scipy module by using the following line of code.
Python
from scipy.optimize import linprog |
We’ll keep a list of the x and y coefficients for the objective function. Our problem is of type maximization type so we will convert the problem into minimization form because scipy accepts problems in minimization form only. To minimize the problem we will multiply the objective function by the negative sign.
- Minimized objective function min.(Z) = – 5x – 4y
Python
obj = [-5, -4]# ─┬ ─┬# │ └┤ Coefficient for y# └───┤ Coefficient for x |
The left-side coefficients of the x and y in the constraints equations will now be stored in a matrix <lhs_ineq>.
Python
# Constraints Left side x and y Coefficient matrixlhs_ineq = [[0, 2], # 0x1 + 2x2 [1, 2], # x1 + 2x2 [1, 1] ] # 1x1 + 1x2 |
Storing the Right side values into a matrix called < rhs_ineq >
Python
# right side values matrixrhs_ineq = [50, # ......<= 50 25, # ......<= 25 15] # ..... <= 15 |
Now We will pass all these matrices to a function called <linprog> by specifying the method as <highs>. This function will return an object that contains the final optimal solution.
The method was described by its name in earlier versions of the script module. such as method=”revised simplex” or method=”simplex”. We now define method = “highs” in the most recent version.
Python
# importing the linear programming packagefrom scipy.optimize import linprog# Objective function's Coefficient matrixobj = [-5, -4]# ─┬ ─┬# │ └┤ Coefficient for y# └────┤ Coefficient for x# Constraints Left side x and y Coefficient matrixlhs_ineq = [[0, 2], # 0x1 + 2x2 [1, 2], # x1 + 2x2 [1, 1] ] # 1x1 + 1x2# right side values matrixrhs_ineq = [50, # ......<= 50 25, # ......<= 25 15] # ..... <= 15# Inbuilt function <linprog> will solve the problem optimally# passing the each coefficient's Matricesopt = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq,method="highs")# printing the solutionprint(opt) |
Output:
con: array([], dtype=float64)
crossover_nit: 0
eqlin: marginals: array([], dtype=float64)
residual: array([], dtype=float64)
fun: -75.0
ineqlin: marginals: array([-0., -0., -5.])
residual: array([50., 10., 0.])
lower: marginals: array([0., 1.])
residual: array([15., 0.])
message: 'Optimization terminated successfully. (HiGHS Status 7: Optimal)'
nit: 1
slack: array([50., 10., 0.])
status: 0
success: True
upper: marginals: array([0., 0.])
residual: array([inf, inf])
x: array([15., 0.])
Here as you can see the objective function value is -75, so the final optimal value of max. Z = -(Z) => 75 so, the corresponding values are X = 15 and Y = 0 are the units of products where the objective function is maximized. Thus, the company will make a maximum profit of 75 rupees.
