Algebra

Linear Programming

Students plan two kinds of craft kits using a graph and a limited supply of tokens.

Linear Programming definition

Linear programming finds the largest or smallest possible value of a linear objective subject to linear constraints.

In Spanish
programación lineal
Topic
Optimization and constraints

Linear Programming in a picture

Linear Programming diagramOn this rectangle, 3x + 2y is largest at (4, 3) and smallest at (0, 0).xy4300 ≤ x ≤ 4 and 0 ≤ y ≤ 3
On this rectangle, 3x + 2y is largest at (4, 3) and smallest at (0, 0).

How it works

Choose decision variables, write the objective function, and describe the allowed choices with linear equations or inequalities. For two variables, a graph can show the feasible region. If that region is a nonempty bounded polygon, at least one corner attains the best value.

Worked examples

For 0 ≤ x ≤ 4 and 0 ≤ y ≤ 3, maximize 3x + 2y.

Both coefficients are positive. At (4, 3), the value is 12 + 6 = 18.

For the same limits, minimize x + y.

At (0, 0), the value is 0, and neither coordinate may be negative.

Is maximizing x² + y under linear constraints a linear program?

No. The objective is nonlinear in x.

Common mistake

Check feasibility before comparing objective values. If the variables must be whole numbers, that adds an integer restriction.

Quick check

What type of objective does a linear program use?

What is the set of all allowed choices called?

Show answer

The feasible region.

Can a linear program have more than one best solution?

Show answer

Yes. For instance, a full edge can share the best value.

Sources

Flashcard

Linear Programming

Reveal the definition

Linear programming finds the largest or smallest possible value of a linear objective subject to linear constraints.

Effortless Math. “Linear Programming.” Math Dictionary.