Linear Programming

Linear programming (LP) is a mathematical optimization method that targets a linear objective function subject to linear constraints, both equalities and inequalities. A critical component of Operations Research (OR), LP is applied in various fields, including business management, economics, and engineering.

The Role of Linear Programming in Decision-Making

LP serves as a quantitative alternative or supplement to intuition-driven decision making. Traditionally, decision-makers rely on personal experience and judgments to outline the best course of action. However, linear programming offers a systematic, objective approach that employs mathematical models to optimize decisions based on specific criteria. By providing a clear decision making framework, LP can minimize the impact of bias and enhance decision making consistency.

Linear Programming in Real-World Optimization

Through maximizing or minimizing a linear objective function within the boundary of linear constraints, linear programming guides decision-making in real-world challenges. Examples of its application include resource allocation to maximize system profit, cost minimization in production scheduling, and fund distribution across a portfolio to boost returns.

How to Implement Linear Programming

1. Define the problem: Identify the objective function, decision variables, and constraints.
2. Formulate the linear program: Transform the objective function and constraints into linear equations or inequalities.
3. Select a solver: Choose from several software packages, such as Excel Solver, Gurobi, CPLEX, or Python, based on the problem and available resources.
4. Input data: Enter the required data, including objective function coefficients, constraint coefficients, and decision variable bounds, into the solver.
5. Solve the problem: Use the solver to find the optimal solution to the linear program.
6. Interpret the results: After solving, interpret the results to ascertain the optimal values of the decision variables and the optimal objective function value. Validate the results to ensure they align with the problem context.

Example of Linear Programming

Consider a scenario with multiple software teams capable of completing a certain capacity of work each across different types of work. Each type of work contributes a certain amount of customer value, and there's a specific amount of work available for each type. The goal is to maximize the customer value within given constraints.

Here is a breakdown of five software teams (Team A, B, C, D, E) that can do a total of 100 points of work each across five work types (Type 1, 2, 3, 4, 5).

• Type 1 can be done by all teams
• Type 2 can be done by team A and B
• Type 3 can be done by team A, B and C
• Type 4 can be done by Team D and E
• Type 5 can be done only by Team E

Each type of work provides a set amount of customer value

• Type 1 and 2 are worth 3 points of customer value for each point of work.
• Type 3 work is worth 4 points of customer value for each point of work
• Type 4 is worth 1 point of customer value for each point of work
• Type 5 is worth 1 point of customer value for each point of work

There is a certain amount of work available or necessary for each Type

• Type 1 has 100 points of work available
• Type 2 has 150 points of work available
• Type 3 has 150 points of work available
• Type 4 has 100 points of work available
• Type 5 has 75 points of work available and all 75 points must be completed

The goal is to maximize the customer value given the constraints

The solution yields a maximum customer value of 1450 (measured by points) by assigning specific tasks to each team. We get to 1450 maximum customer value points by assigning:

• Team A (50 task 2, 50 task 3)
• Team B (100 task 2)
• Team C (100 task 3)
• Team D (100 task 1)
• Team E (75 task 5, 25 Task 4)

‍

Below is what this looks like in a spreadsheet:

‍

‍

The Future of Linear Programming

Linear programming can solve real-world problems and serve as a valuable tool in the decision-making process. LP models are modular and reusable with configurable input variables, reducing implementation costs for organizations. Advancements in generative artificial intelligence (AI) have simplified the identification of decision variables, objective functions, and constraints. In the foreseeable future, generative AI will be capable of analyzing problems, defining parameters, and providing the optimal solution. Meanwhile, Operations Research Analysts, Data Scientists, Industrial Engineers, and others interested in solving quantitative problems can employ linear programming to reduce uncertainty and maximize efficiency!