Linear Programming definition
Linear programming finds the largest or smallest possible value of a linear objective subject to linear constraints.
Linear Programming in a picture
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 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.
