Lesson 54: Using Linear Programming

New Concept

In linear programming, you are looking for the maximum or minimum value of an objective function, subject to certain constraints.

Why it matters

Linear programming is where algebra transforms from a tool for finding single answers into a powerful system for making strategic decisions. Mastering this allows you to model and optimize real-world problems in fields like business, engineering, and logistics, a skill highly valued in competitive environments.

What’s next

Next, you'll define objective functions and constraints to find the optimal solution by testing the vertices of a graphed feasible region.

In linear programming, the objective function is the function whose maximum or minimum value you need to find. Think of it as your main goal in a game—get the highest score (profit) or use the fewest resources (cost). It is the primary equation you are trying to max out or shrink down!

Example 1: A company wants to maximize profit from two products. The objective function is Profit = 15x + 10y, where x and y are the number of units for each product.
Example 2: A delivery service wants to minimize fuel costs. The objective function is Cost = 2.50d₁ + 1.75d₂, where d₁ and d₂ represent distances on two different routes.

This function represents the main goal of your problem, like maximizing profit or minimizing expenses. It's the mathematical expression you will evaluate at different points to see which one gives you the best possible outcome according to your goal.

The constraints are the set of linear equations or inequalities that limit the possible solutions. These are the rules of the game! You cannot spend more money than you have or use more materials than are available. They fence in your possible moves, defining the boundaries of what is achievable in the problem.

Example 1: A factory has at most 400 hours for labor and 500 pounds of material. The constraints are 2x + 5y ≤ 400 and 4x + 3y ≤ 500.

Example 2: A diet requires at least 50 grams of protein and no more than 20 grams of fat. The constraints are 10p₁ + 5p₂ ≥ 50 and 2f₁ + 4f₂ ≤ 20.

The feasible region is the shaded area on a graph that contains all the possible solutions satisfying the constraints. This is your playground! It’s the area on the graph containing all the valid moves that do not break any rules. Any point inside this zone is a possible, 'legal' solution to your problem.

Example 1: For the constraints x ≥ 0, y ≥ 0, and x + y ≤ 8, the feasible region is a triangle with vertices at (0,0), (8,0), and (0,8).

Example 2: For constraints x ≤ 10, y ≤ 15, and x + y ≥ 20, the feasible region is the area bounded by those three lines.

The minimum or maximum value of the objective function always occurs at a vertex of the feasible region. Why check the whole playground when the treasure is always buried in the corners? The best and worst outcomes are always at the vertices. Just test those points to find the optimal solution efficiently.

Example 1: To maximize P = 5x + 3y with vertices at (0,0), (0,10), (5,5), and (8,0), we test each point. The maximum profit of 40 occurs at the vertex (8,0).
Example 2: To minimize C = 2x + 4y with vertices at (0,20), (10,5), and (30,0), we check each vertex. The minimum cost of 40 is found at the vertex (10,5).

This is the ultimate shortcut in linear programming! Instead of checking infinite points in the feasible region, you only need to check the corner points (vertices). Plug the coordinates of each vertex into your objective function, and the biggest or smallest result is your answer.