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.
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])
message: ‘Optimization terminated successfully.’
slack: array([0., 0.])
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
- 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.
- Campbell, H.G., 1965. An introduction to matrices, vectors, and linear programming. Appleton-Century-Crofts.