Linear Programming Problem

Linear Programming Problem Solution in Python

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-
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])
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

  1.  Optimization and Root Finding, Web Link,  https://docs.scipy.org/doc/scipy/reference/optimize.html
  2. Zoutendijk, G., 1960. Methods of feasible directions: a study in linear and non-linear programming. Elsevier.
  3. https://en.wikipedia.org/wiki/Linear_programming
  4. Campbell, H.G., 1965. An introduction to matrices, vectors, and linear programming. Appleton-Century-Crofts.

Leave a Comment

Your email address will not be published. Required fields are marked *

©Postnetwork-All rights reserved.