Linear Programming
The optimal solution under a linear objective and linear constraints
How do you find the best result within the resources and constraints you have? Companies try to earn as much profit as possible with limited resources, and organizations try to carry out as many programs as possible on a fixed budget. When production time or budget is limited, you can’t set every option however you like.
What is linear programming?
Linear programming (LP) is an optimization method that finds the choice that best achieves a goal while satisfying the given constraints. It is used when the objective function and the constraints can all be written as first-degree (linear) expressions in the variables. A classic example is a factory making two products that has to decide how much of each to make, within limited working hours, so that profit is as large as possible.
The three components of linear programming
Represent what to choose and how much. Units of product A produced, x; units of product B produced, y.
Expresses the goal you want to maximize or minimize as a formula. Example: maximize total profit.
Conditions that limit the range of choices. Budget, production time, quantity of raw materials and so on.
Once the three elements are clearly defined, a real-world decision problem can be expressed mathematically (Ch. 01).
Understanding it through a production planning problem
| Item | Product A | Product B |
|---|---|---|
| Profit per unit | $60 | $100 |
| Time in process 1 | 1 hour | 2 hours |
| Time in process 2 | 2 hours | 1 hour |
Each process can be used for at most 8 hours a day, and the goal is to maximize total profit while respecting both processes’ time limits. Letting x be the number of units of product A and y the number of units of product B, we have:
s.t. x + 2y ≤ 8 (process 1)
2x + y ≤ 8 (process 2)
x, y ≥ 0
Z: total profit ($) · s.t.: subject to, "while satisfying the following conditions"
Feasible and optimal solutions
Every production combination that satisfies the constraints is a feasible solution, and the one among them with the largest objective value is the optimal solution.
| Product A (x) | Product B (y) | Process 1 use | Process 2 use | Total profit | Result |
|---|---|---|---|---|---|
| 0 | 0 | 0 hours | 0 hours | $0 | Feasible |
| 4 | 0 | 4 hours | 8 hours | $240 | Feasible |
| 0 | 4 | 8 hours | 4 hours | $400 | Feasible |
| 2 | 3 | 8 hours | 7 hours | $420 | Feasible |
| 3 | 3 | 9 hours | 9 hours | $480 | Infeasible |
| 8/3 | 8/3 | 8 hours | 8 hours | about $426.67 | Optimal |
2 of A and 3 of B needs 2 + 2(3) = 8 hours in process 1 and 2(2) + 3 = 7 hours in process 2, so it is feasible. Making 3 each of A and B, on the other hand, needs 9 hours in both processes, so it is infeasible. The optimal solution in this example is to produce 8/3 units each of A and B.
Why look at the vertices?
When the objective function and constraints are all linear, if an optimal solution exists, you can find one at a vertex of the feasible region. Each constraint is a half-plane on one side of a line in the coordinate plane, and the region that satisfies all the constraints at once is the feasible region.
In Figure 1, the feasible region is a quadrilateral with vertices (0, 0), (4, 0), (8/3, 8/3) and (0, 4). The intersection of the two constraint lines is found as follows.
Z = 60(8/3) + 100(8/3) = 1280/3 ≈ 426.67
The profits at the four vertices are $0, $240, $426.67 and $400, so the intersection is optimal. If you slide the iso-profit line joining points of equal profit (red dashed) parallel toward the upper right, the last place it touches the feasible region is exactly this vertex. Because the iso-profit line is straight and the region’s boundary is made of straight lines, the last point of contact is always a vertex (or an entire edge that includes a vertex).
The vertex principle applies only when an optimal solution exists, though. If the constraints contradict each other so that there is no feasible solution, or the objective can keep improving so that there is no maximum, you have to judge those cases separately (Ch. 01).
If products can only be made in whole units, 8/3 units won’t do. As Figure 2 shows, among the integer points inside the feasible region, 2 of A and 3 of B ($420) is best, while (3, 3), the LP optimum simply rounded, violates the constraints. Integer programming (Ch. 04) covers problems like this.
Figure 3 shows what happens when only product B’s profit is changed. While B’s profit is between $30 and $120, the optimal production mix stays at (8/3, 8/3) and only the size of the profit changes. Above $120, making only B, 4 units, becomes optimal; below $30, making only A, 4 units, becomes optimal. Checking the range over which the optimal solution holds as a coefficient changes like this is also part of sensitivity analysis (14 · Ch. 07).
The basic assumptions of linear programming
| Assumption | Meaning | Example |
|---|---|---|
| Proportionality | When a variable changes, the objective and resource use change in proportion | Making 2 units takes twice the time of making 1 |
| Additivity | The total effect is the sum of each variable’s effect | Add up the profits of the two products |
| Divisibility | Decision variables can take continuous values | Producing 2.5 units is allowed in the calculation |
| Certainty | The model’s coefficients are known and fixed | Profit and working time per product are given |
In reality there may be volume discounts, fixed setup costs, uncertain demand and so on. In these situations, rather than applying the basic linear programming model as is, you should consider whether another model is needed, such as integer programming, nonlinear optimization or stochastic optimization.
Problems linear programming can solve
Optimize output and profit with limited equipment and staff
Minimize shipping cost given delivery volumes and the cost of each route
Allocate resources to programs or activities within a limited budget
Assign people given staffing and time limits for each task
Plan operations given each power source’s supply limit and cost
Define the goal and constraints clearly, then find the best within them
Solving a linear programming model constrained by the daily available time of two processes (8 hours each), total profit was maximized at 1280/3 ≈ $426.67 when 8/3 units each of products A and B were produced. Adding the condition that production must be in whole units, 2 of A and 3 of B ($420) was optimal, and the continuous optimal solution did not change as long as product B’s unit profit stayed in the range $30–$120.
If everything is linear, the optimal solution lies at a vertex of the feasible region.
- Linear programming: A way to find the optimal solution with a linear objective function and linear constraints.
- Modeling: The starting point is defining the decision variables, objective function and constraints.
- Feasible and optimal solutions: A solution that satisfies the constraints is feasible, and the one among them with the best objective value is optimal.
- Vertex principle: If an optimal solution exists, one of the feasible region’s vertices is optimal, and you can find it by sliding the iso-profit line.
- Assumptions and limits: Integrality, nonlinear relationships or uncertainty may call for a different optimization model.
Up next: 03 The Simplex Method and Duality. We’ll look at the simplex method, which finds the optimal solution efficiently when there are too many variables to compare vertices one by one, and at duality, which interprets the value of resource constraints.