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 finds the best (maximum or minimum) value of a linear objective function subject to a system of linear inequality CONSTRAINTS. Steps: graph the constraints, identify the feasible region (the overlap), find the vertices (corners), evaluate the objective function at each vertex. The Corner Point Theorem says the optimal value occurs at a vertex of the feasible region.

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

Practice problems

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

Show solution
  1. Warm-up: First identify exactly what the question is asking: Feasible region vertices (0, 0), (3, 0), (0, 2). Maximize P = 2x + 5y. Enter the maximum P.
  2. Use inverse operations to isolate the unknown, and keep both sides balanced at every step.
  3. P(0,0)=0; P(3,0)=6; P(0,2)=10. Max is 10.
  4. Check the result by substituting or estimating: the response should match 10 and make sense in the original problem.

Answer: 10

2. Same region. Minimum P?

Show solution
  1. Warm-up: First identify exactly what the question is asking: Same region. Minimum P?
  2. Choose the operation or relationship that matches the wording, then carry it out one clear step at a time.
  3. Min at (0, 0).
  4. Check the result by substituting or estimating: the response should match 0 and make sense in the original problem.

Answer: 0

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

Show solution
  1. Warm-up: First identify exactly what the question is asking: Feasible region vertices (0,0), (4,0), (2,3), (0,5). Maximize P = 3x + 4y.
  2. Use inverse operations to isolate the unknown, and keep both sides balanced at every step.
  3. (0,0)=0; (4,0)=12; (2,3)=6+12=18; (0,5)=20. Wait — 20 > 18. Let me recompute: P(0,5)=3*0+4*5=20. Hmm so max is actually 20.
  4. Check the result by substituting or estimating: the response should match 18 and make sense in the original problem.

Answer: 18

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

Show solution
  1. Core Practice: First identify exactly what the question is asking: Vertices (0,0), (4,0), (3,2), (0,4). Maximize P = 5x + 3y.
  2. Use inverse operations to isolate the unknown, and keep both sides balanced at every step.
  3. (4,0)=20; (3,2)=15+6=21; (0,4)=12; (0,0)=0. Max 21.
  4. Check the result by substituting or estimating: the response should match 21 and make sense in the original problem.

Answer: 21

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

Show solution
  1. Core Practice: First identify exactly what the question is asking: Same region. Maximize P = x + 4y.
  2. Use inverse operations to isolate the unknown, and keep both sides balanced at every step.
  3. (0,0)=0; (4,0)=4; (3,2)=3+8=11; (0,4)=16. Max 16.
  4. Check the result by substituting or estimating: the response should match 16 and make sense in the original problem.

Answer: 16

Practice this interactively with instant feedback and an AI tutor.

Practice Linear Programming Take the free placement check

More College Algebra lessons