Solving a linear programming problem with Linprog



In [1]:

    
from scipy.optimize import linprog
import numpy as np

Objective function

$$z(max) = 5x_1 + 4x_2$$

Constraints:

$C_1 = x_1 + x_2 \leq 5$
$C_2 = 10*x_1 + 6*x_2 \leq 45$
$x_1,x_2 \geq 0$

Set objective function.

Objective function is going to be stored in z variable, this variable is going to store coefficients of the objective function.



In [2]:

    
z = np.array([5,4])

After stored our Objective Function, we need to set Constraints.

Constraints values are going to be stored in C variable and must be 2-D Array, this variable is going to store all constraints of the problem.



In [3]:

    
C = np.array([
    [1, 1],          #C1
    [10,6]           #C2
])

Set upper-bounds values for each Constraints.

Upper-bounds values are going to be stored in b variable and must be 1-D Array. In this case we need to store 5 and 45 for each constraint.



In [4]:

    
b = np.array([5,45])

Specify bounds, in this case is $\geq0$ for each variable $x_1$ and $x_2$.



In [5]:

    
x1 = (0, None)
x2 = (0, None)

To solve the problem, we need to call linprog and store the solution in a variable.

The parameters that are going to be used are (z, A_ub, b_ub, bounds, method). More detail here.

This LP problem has a maximize objective function and linprog supports minimize problems. To solve it:

$$ min(z(x)) = max(-z(x)) $$



In [6]:

    
sol = linprog(-z, A_ub = C, b_ub = b, bounds = (x1, x2), method='simplex')



In [7]:

    
sol









    Out[7]:





     fun: -23.75
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([0., 0.])
  status: 0
 success: True
       x: array([3.75, 1.25])

To print the values that we need:



In [8]:

    
print(f"x1 = {sol.x[0]}, x2 = {sol.x[1]}, z = {sol.fun*-1}")









    



x1 = 3.75, x2 = 1.25, z = 23.75

Our LP problem is solved, to check the result just replace the values $x_1$ and $x_2$ into the objective function.

$z(max) = 5x_1 + 4x_2$

$z(max) = 5 \times 3.75 + 4 \times 1.25$

$z(max) = 23.75$