Linear Programming Problem
The problem of formulating an objective function and constraints an establishing relationship between variables is called a programming problem (LPP).
If objective function and constraints are linear then the problem is called linear programming problem.
Example-
Sometimes, you come across the situation when you need to optimize your algorithm. If you can formulate your problem as a linear programming problem
then you can use linprog() function of scipy.optimize library in Python and can get optimize solution. scipy.optimize library of Python provides a variety of functions to solve optimization problems.
The simple problem which I have mentioned above I will solve using linprog() function from scipy.optimize library.
LPP Solution in Python
from scipy.optimize import linprog
c = [4, 2] # The coefficients of x and y in objective function
A = [[1, -3], [-4, -1]] # The coefficients of contraints in term of a matrix
b = [-6, -8] # Bounds on constraints
x_bounds = (0, None)
y_bounds = (0, None)
res = linprog(c, A_ub=A, b_ub=b, bounds=[x_bounds, y_bounds])
print(res)
Output:
fun: 10.461538461538463
message: ‘Optimization terminated successfully.’
nit: 2
slack: array([0., 0.])
status: 0
success: True
x: array([1.38461538, 2.46153846])
Which means for x=1.38461538 and y= 2.46153846 the objective function z will be maximum which is
z=10.461538461538463
References
- Optimization and Root Finding, Web Link, https://docs.scipy.org/doc/scipy/reference/optimize.html
-
Zoutendijk, G., 1960. Methods of feasible directions: a study in linear and non-linear programming. Elsevier.
- https://en.wikipedia.org/wiki/Linear_programming
-
Campbell, H.G., 1965. An introduction to matrices, vectors, and linear programming. Appleton-Century-Crofts.