Mathematics · 12th Grade · Vectors, Matrices, and Systems · Weeks 10-18

Applications of Systems: Linear Programming

Using systems of inequalities and matrices to solve optimization problems with constraints.

• Common Core State Standards
• CCSS.Math.Content.HSA.CED.A.3

About This Topic

Linear programming is the process of optimizing a linear objective function subject to a set of linear inequality constraints. In 12th grade, this topic brings together multiple algebraic skills: writing inequality systems, graphing feasible regions, identifying corner points, and evaluating an objective function at each vertex. Its real-world applications are immediate and varied -- businesses use it to minimize costs, logistics companies to maximize delivery efficiency, and engineers to allocate resources across competing demands.

Common Core standard CCSS.Math.Content.HSA.CED.A.3 requires students to represent constraints with systems of inequalities and to interpret solutions in context. The Fundamental Theorem of Linear Programming, which states that the optimal solution always occurs at a corner point of the feasible region, is the key result students apply. Verifying this theorem through examples before using it gives students confidence that the corner-point method is principled, not arbitrary.

Active learning works especially well here because students can take ownership of translating a verbal scenario into constraints. When students design the inequality system themselves from a realistic context, they develop a much clearer sense of what the variables, the feasible region, and the objective function each represent -- compared to students who only solve pre-built problems with the structure already in place.

Key Questions

1. Design a system of inequalities to represent constraints in a real-world optimization problem.
2. Analyze how the feasible region determines the possible solutions in linear programming.
3. Justify the use of corner points to find optimal solutions in linear programming.

Learning Objectives

• Design a system of linear inequalities to model real-world resource allocation constraints for a small business.
• Analyze the graphical representation of a feasible region to identify all possible production levels that satisfy given constraints.
• Evaluate the objective function at each vertex of the feasible region to determine the optimal solution for maximizing profit or minimizing cost.
• Justify the selection of a specific corner point as the optimal solution by relating it back to the context of the problem and the objective function.

Before You Start

Graphing Linear Equations and Inequalities

Why: Students need to be able to graph lines and shade regions to represent inequalities and identify the feasible region.

Solving Systems of Linear Equations

Why: Finding the corner points of the feasible region requires solving systems of linear equations that represent the boundary lines.

Functions and Evaluating Expressions

Why: Students must be able to substitute values into an expression (the objective function) and calculate the result.

Key Vocabulary

Objective Function	A linear expression that represents the quantity to be maximized or minimized, such as profit or cost.
Constraints	Linear inequalities that represent limitations or restrictions on the variables in a problem, such as available resources or time.
Feasible Region	The set of all possible solutions that satisfy all the constraints of a linear programming problem, typically represented as a polygon on a graph.
Corner Point (Vertex)	A point where two or more boundary lines of the feasible region intersect; these points are candidates for the optimal solution.

Watch Out for These Misconceptions

Common Misconception

The optimal solution can occur anywhere inside the feasible region.

What to Teach Instead

The Fundamental Theorem of Linear Programming guarantees that the optimal value of a linear objective function occurs at a vertex (corner point) of the feasible region. Interior points are always between two corners and can never be strictly better than both. A visual demonstration on a graphing calculator, sliding the objective function line across the feasible region until it just touches a corner, makes this clear.

Common Misconception

There is always exactly one optimal corner point.

What to Teach Instead

If the objective function is parallel to one of the constraint boundaries, the entire edge between two corners is optimal, giving infinitely many optimal solutions. This case is relatively rare in textbook problems, but students who encounter it on assessments are often caught off guard. A think-pair-share on such an edge case, before it appears on a test, prevents confusion.

Active Learning Ideas

Inquiry Circle: School Supplies Optimization

Groups receive a scenario: a school store sells pencils and notebooks with specific profit margins and has limited shelf space and budget constraints. Each group writes the system of inequalities, graphs the feasible region, identifies corner points, and finds the combination that maximizes profit. Groups compare optimal solutions and discuss any discrepancies in their constraint setups.

45 min·Small Groups

Think-Pair-Share: Constraint Writing from Text

Students are given a real-world scenario (a bakery with two products, limited flour and sugar, minimum daily quotas) and must individually write all constraints as inequalities. Partners compare their inequalities, resolve missing or redundant constraints, and graph the feasible region together before identifying corner points.

25 min·Pairs

Gallery Walk: Feasible Region Analysis

Stations show pre-graphed feasible regions with labeled corner points. Students evaluate the given objective function at each corner, identify the optimal solution, and describe a plain-language interpretation of the answer. They also predict how the optimal solution would shift if one constraint changed.

30 min·Small Groups

Error Analysis: The Broken Corner

Groups review four worked linear programming problems: two with correct optimal solutions and two that mistakenly evaluated an interior point instead of a corner point. Students identify the errors, explain why interior points are never optimal for a linear objective function, and post corrected solutions.

25 min·Pairs

Real-World Connections

• A bakery uses linear programming to determine the optimal number of cakes and pies to bake daily, considering constraints on ingredients like flour and sugar, and oven time, to maximize profit.
• A shipping company might use linear programming to plan delivery routes, minimizing fuel costs and driver hours while ensuring all packages are delivered within specified time windows.
• A farmer can use linear programming to decide how many acres of different crops to plant, balancing constraints on water availability, labor, and market demand to achieve the highest possible yield value.

Assessment Ideas

Exit Ticket

Provide students with a scenario involving two variables and two constraints (e.g., producing two types of furniture with limited wood and labor). Ask them to write the objective function and two inequalities representing the constraints. Then, have them identify one point within the feasible region and one point outside it, explaining why each is or is not a valid solution.

Quick Check

Present students with a pre-graphed feasible region and an objective function. Ask them to list the coordinates of all corner points. Then, have them calculate the value of the objective function at each corner point and identify which point yields the maximum (or minimum) value.

Discussion Prompt

Pose the question: 'Why is it sufficient to only check the corner points of the feasible region to find the optimal solution in linear programming?' Facilitate a discussion where students explain the Fundamental Theorem of Linear Programming and its implications for problem-solving.

Frequently Asked Questions

What is the feasible region in a linear programming problem?

The feasible region is the set of all points that satisfy every constraint simultaneously. It is the intersection of all the half-planes defined by the constraint inequalities and is typically a convex polygon when there are a finite number of constraints. Only points inside or on the boundary of this region are valid solutions.

Why do we only check corner points for the optimal solution?

The Fundamental Theorem of Linear Programming proves that because the objective function is linear (a flat surface over the variable space), its maximum and minimum values over a bounded polygonal region always occur at vertices. This eliminates the need to test every point in the region.

How do you know if a linear programming problem has no solution or is unbounded?

A problem has no solution if the feasible region is empty (the constraints are mutually contradictory). It is unbounded if the feasible region extends infinitely in the direction of optimization with no limiting constraint. Graphing the constraints first makes both situations visible before any algebra is attempted.

How does active learning support linear programming instruction?

When students write the constraints themselves from a verbal scenario, they must translate real-world conditions (budget limits, storage capacity, minimum quotas) into mathematical inequalities. That translation step, often skipped when problems are pre-formulated, is exactly the skill that real applications demand. Collaborating on constraint setup also surfaces implicit assumptions that solo work misses.