CMClearMathAcademy

Linear Programming

A free College Algebra lesson from the “Systems, Matrices, and Linear Programming” unit, with a worked example and practice problems including step-by-step solutions.

Linear programming optimizes a linear objective subject to linear inequality constraints. Graph the constraints and identify their overlap, the feasible region. For a nonempty bounded polygon, evaluate the objective at every vertex: at least one vertex attains each optimum. If adjacent vertices tie, their entire connecting edge is optimal. An empty region has no feasible solution; an unbounded region requires checking whether a finite optimum exists.

What you'll learn

Why it matters: Business resource allocation (maximize profit subject to budget and labor), diet planning (minimize cost subject to nutrient minimums), and operations research all use linear programming.

Worked example

Problem. A feasible region has vertices (0, 0), (4, 0), (3, 2), and (0, 4). Maximize P = 5x + 3y. Enter the maximum P.

  1. Evaluate P at each vertex: (0,0) -> 0; (4,0) -> 20; (3,2) -> 15 + 6 = 21; (0,4) -> 12.
  2. Maximum is 21 at (3, 2).

Answer: 21

Lesson preview: this page shows 5 practice items. The interactive activity contains 28 practice items and 15 quiz items (typed response and multiple choice). Counts include repeated prompts and variants.

Practice problems

1. Feasible region vertices (0, 0), (3, 0), (0, 2). Maximize P = 2x + 5y. Enter the maximum P.

Show solution
  1. P(0,0)=0; P(3,0)=6; P(0,2)=10. Max is 10.

Answer: 10

2. Same region. Minimum P?

Show solution
  1. Min at (0, 0).

Answer: 0

3. Feasible region vertices (0,0), (4,0), (2,3), (0,5). Maximize P = 3x + 4y.

Show solution
  1. Evaluate the objective at every vertex: P(0,0)=0, P(4,0)=12, P(2,3)=18, and P(0,5)=20.
  2. Compare all four values; 20 is the largest.
  3. The maximum is 20, attained at (0,5).

Answer: 20

4. Vertices (0,0), (4,0), (3,2), (0,4). Maximize P = 5x + 3y.

Show solution
  1. (4,0)=20; (3,2)=15+6=21; (0,4)=12; (0,0)=0. Max 21.

Answer: 21

5. Same region. Maximize P = x + 4y.

Show solution
  1. (0,0)=0; (4,0)=4; (3,2)=3+8=11; (0,4)=16. Max 16.

Answer: 16

Practice this interactively with instant feedback and an AI tutor.

Practice Linear Programming Take the free placement check

More College Algebra lessons