10. Linear Programming#
Linear Programming (LP) is a mathematical method used to optimize a linear objective function, such as maximizing profit or minimizing costs, while satisfying a set of linear constraints. These constraints, expressed as inequalities or equations, define the feasible region where solutions are valid. Decision variables are adjusted to find the best outcome within this region. LP is widely used in fields like economics, business, transportation and engineering to solve problems involving resource allocation and operational efficiency. Its simplicity and effectiveness make it a fundamental tool in optimization and decision-making.
For example, a manufacturer may seek to identify the optimal production levels for different combination of products in order to maximize profits while staying within the limits of available resources like labor, transportation, materials, and machinery. Here, the objective function would reflect the profit to be maximized, and the constraints would represent the resource limitations.
Key components in Linear Programming
Objective Function: A linear expression to maximize or minimize.
Decision Variables: The unknowns that are determined to optimize the objective function.
Constraints: Linear inequalities or equations restricting the decision variables.
Non-negativity: Ensures variables are non-negative where required.
Feasible Region: The solution set satisfying all constraints, containing the optimal point.
Despite its utility, linear programming (LP) has inherent limitations. It operates under the assumption of linearity in all relationships, which may not always accurately capture real-world complexities. Moreover, LP requires precise specification of coefficients and constants, a task that can be difficult due to estimation challenges.
10.1. Useful links#
Here are some extra resources you can find in the web that talk about this topic.
These links are external and we don’t take responsibility for any downtime or incovenient caused by them.
10.2. LP Theory#
10.2.1. Mathematical Formulation#
Comments:
Mixed-Integer Linear Programming (MILP):
Integer Linear Programming (ILP):
Computational Tools:
10.2.2. Simplex Method#
10.2.3. Iterior-Point Method#
10.2.4. Duality#
10.3. Sensitivity Analysis:#
10.3.1. Scipy Example#
# Solve a general Problem without mathematical interpretation
import pandas as pd ## Maybe create an imports.py?
from scipy.optimize import linprog
10.4. Applications#
10.4.1. Application 1#
10.4.1.1. Implementation#
10.4.2. Application 2#
10.4.2.1. Implementation#
10.4.3. Application 3#
10.4.3.1. Implementation#
10.5. Initial References#
Internet: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html
https://coin-or.github.io/pulp/main/the_optimisation_process.html
https://realpython.com/linear-programming-python/
https://intro.quantecon.org/lp_intro.html
https://www.uky.edu/~dsianita/300/online/LP.pdf
https://math.mit.edu/~goemans/18310S15/lpnotes310.pdf
https://www.udemy.com/course/linear-programming-for-machine-learning/
Books: