On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

Math · Algebra Fundamentals · Grade 9-12

Linear Programming

Linear programming finds the maximum or minimum of a linear objective (like profit or cost) subject to linear inequality constraints.

max⁡/min⁡  cTx  subject to  Ax≤b

Quick Answer

Linear programming finds the maximum or minimum of a linear objective (like profit or cost) subject to linear inequality constraints. Use it when a business, diet or schedule has several limits, such as hours, materials or a budget, that must all hold at once, and you want the best value of one quantity. Graphing the limits gives the feasible region, a polygon of all allowed choices. Because the objective is linear, its best value, when there is one, occurs at a corner of that polygon, so you test the corners instead of every point.

Why This Matters

Airlines, factories and farms use linear programming to decide how many of each product to make, which planes fly which routes, and how to mix animal feed at the lowest cost. The corner principle turns infinitely many choices into a short list to check. Without it, people guess at a good mix, or pick the point where the main constraints cross, and can miss a corner that earns more.

Intuitive Explanation

A bakery makes cakes and pies. A cake needs 2 hours of oven time and a pie 1 hour, and the oven is free for 10 hours a day; there is fruit for at most 6 pies. Profit is $5 per cake and $4 per pie. With x cakes and y pies, the limits are 2x+y≤10, y≤6, x≥0 and y≥0, and the goal is to maximize P=5x+4y.

Each limit cuts the plane along a line and keeps one side. Together they leave a polygon, the feasible region, with corners (0,0), (5,0), (2,6) and (0,6); the corner (2,6) is where 2x+y=10 meets y=6. Every point of the region is an allowed plan, and there are infinitely many of them.

Now picture the profit lines 5x+4y=P for larger and larger P. They are all parallel, so as one slides across the region, the last point it touches is a corner, or occasionally a whole edge. Test the corners: P=0 at (0,0), 25 at (5,0), 10+24=34 at (2,6), and 24 at (0,6). The best plan is 2 cakes and 6 pies, for $34.

Solving a system of equations finds where lines cross, with no goal; here (2,6) matters only because it is the corner that wins. Graphing inequalities shades the region and stops. Linear programming adds the objective and the corner test, and it needs everything to be linear: a profit like 5x2 could peak in the middle of the region.

Think of it like this. Finding the optimum is like pushing a ruler across a polygon cut from paper, keeping it parallel to the profit line. The last bit of paper the ruler touches before it leaves is a corner, because the ruler and the polygon's edges are all straight. If the profit rule were curved, the last point touched could be in the middle of a side.

Core idea. Linear programming maximizes or minimizes a linear objective over a region cut out by linear constraints, and the optimum always sits at a corner of that region.


When to Use

Use it when a problem asks you to maximize or minimize one quantity, such as profit, cost or time, subject to several limits written as linear inequalities. Look for two or more decision variables and phrases like at most 40 hours or at least 30 g of protein. If there is no quantity to optimize, you only need to graph the inequalities. If the objective contains squares or products of the variables, the corner rule no longer applies.

Tip. Ask: Am I optimizing a linear objective over a region bounded by linear inequalities, with the answer expected at a corner?

How to Recognize It

Before setting up a linear program, find the one quantity to make as large or as small as possible and list every limit on the choices.

  1. Is there one quantity, such as profit or cost, that the problem wants as large or as small as possible?

    That quantity becomes the objective. If the problem only asks which choices are allowed, graphing the inequalities is enough and no best point is needed.

  2. Are the limits inequalities, such as at most 40 hours, rather than exact equations?

    Inequalities give a region with corners to test. If every condition is an exact equation, there is just one point that fits, and solving a system of equations finds it.

  3. Is every expression a sum of numbers times variables, like 3x+5y?

    Then the corner rule holds. A term like xy or x2 in the objective, as when revenue is price times quantity, makes the problem nonlinear, and the best point may sit partway along an edge or inside the region.

  4. Must the answers be whole numbers, such as numbers of buses?

    Then the best corner may be a fraction, like 3.5 buses, and the true answer is a whole-number point inside the region, usually close to that corner, found by testing the candidates. This version is called integer programming.

Linear Programming compared with Systems of equations, Graphing inequalities, and Single-variable optimization

These rows share the same lines and inequalities, so their problems look alike on the page. Ask whether there is a quantity to make as large or small as possible, and whether the conditions are inequalities on several variables, exact equations, or a curve in one variable.

Linear Programming

Meaning
Use this when you must maximize or minimize one linear quantity while several linear inequality constraints hold simultaneously.
Key test
Am I optimizing a linear objective over a region bounded by linear inequalities, with the answer expected at a corner?
Formula
max⁡/min⁡  cTx  subject to  Ax≤b
Example
Maximize P=3x+2y subject to x+y≤4, x≥0, y≥0.

Systems of equations

Meaning
Finds the single point where lines meet (intersection), with no objective to optimize.
Key test
Use when you just need where conditions are equal, not the best value.
Example
Solve {x+y=5,  x−y=1}

Graphing inequalities

Meaning
Shades the solution region but does not pick a best point.
Key test
Use when you only need to show where a constraint is satisfied.
Example
Shade y≤2x+1

Single-variable optimization

Meaning
Maximizes/minimizes a function of one variable, often with calculus.
Key test
Use when there is one variable and a curve, not linear constraints.
Formula
set f′(x)=0
Example
Max of −x2+4x

Formula & Notation

max⁡/min⁡  cTx  subject to  Ax≤b
Find x∈Rn that optimizes cTx over a polyhedral feasible set {x∣Ax≤b}.

How to read it: max⁡z or min⁡z with linear constraints.

Worked Examples

Example 1 — Maximize profit

Easy

Maximize P=3x+2y subject to x+y≤4, x≥0, y≥0.
Show the steps and the answer
  1. Graph the constraints: the line x+y=4 with the side containing the origin, together with x≥0 and y≥0.

    The three inequalities together cut out a triangle of allowed points.

  2. List the corners: (0,0), (4,0) and (0,4).

    Each corner is where two boundary lines meet, and a linear objective takes its best value at one of them.

  3. Evaluate P at each: 3(0)+2(0)=0, 3(4)+2(0)=12, 3(0)+2(4)=8.

    Comparing three corners replaces checking infinitely many points.

  4. Pick the largest: P=12 at (4,0).

    Each unit of x earns 3 and each unit of y only 2, and both use up the same limit equally, so spending it all on x wins.

Answer: Maximum P=12 at (4,0)

Takeaway: Find the corners of the feasible region, evaluate the objective at each, and take the largest (or smallest).

Example 2 — Just an intersection

Standard

Where do x+y=4 and x−y=0 cross?
Show the steps and the answer
  1. Notice there is no objective and no inequality: two equations must both hold.

    Nothing is being maximized, so there are no corners to compare.

  2. Add the equations: (x+y)+(x−y)=4+0, so 2x=4 and x=2.

    Adding cancels the y terms.

  3. Substitute back: 2+y=4, so y=2.

    Either equation gives y once x is known.

  4. Check: 2+2=4 and 2−2=0.

    The single point (2,2) lies on both lines.

Answer: (2,2)

Takeaway: Equations with no goal give an intersection point; linear programming needs inequalities and something to optimize.

Example 3 — Find the mistake: checking only one corner

Application

A farmer has 100 acres for wheat (x acres) and corn (y acres), so x+y≤100, and labor limits give x+2y≤160. Profit is P=40x+30y dollars. Jo solves x+y=100 and x+2y=160, gets (40,60), and reports P=3400 as the maximum. Find the mistake and correct it.
Show the steps and the answer
  1. List every corner, including those on the axes from x≥0 and y≥0: (0,0), (100,0), (40,60) and (0,80).

    Acres cannot be negative, and those hidden limits create corners of their own.

  2. Confirm (100,0) is allowed: 100+0≤100 and 100+2(0)=100≤160.

    A corner must satisfy every constraint, not only the two lines that meet there.

  3. Evaluate P at each corner: 0, 40(100)=4000, 40(40)+30(60)=3400, and 30(80)=2400.

    The optimum is at a corner, but not necessarily the one where the two main lines cross.

  4. Choose the largest: P=4000 at (100,0).

    Wheat earns more per acre, and planting only wheat still fits within the labor limit.

Answer: Maximum P=4000 at (100,0): plant all 100 acres with wheat.

Takeaway: Test every corner of the feasible region, including those on the axes; the crossing of the two main constraints is only one candidate.

Where You'll See It

  • Mixing animal feed at lowest cost

    Feed A costs $0.30/kg and is 20% protein; feed B costs $0.50/kg and is 40% protein. A farm needs at least 100 kg of feed with at least 30 kg of protein: minimize 0.3a+0.5b with a+b≥100 and 0.2a+0.4b≥30. The corners cost $45 at (150,0), $40 at (50,50) and $50 at (0,100), so 50 kg of each is cheapest.

  • Planning a furniture workshop's week

    Tables earn $60 and take 3 hours of labor; chairs earn $25 and take 1 hour. With 36 labor hours and wood for at most 20 pieces, the corners (12,0), (8,12) and (0,20) earn $720, $780 and $500, so 8 tables and 12 chairs make the most money.

  • Assigning planes and crews

    Airlines solve linear programs with thousands of variables, one for each possible plane-route or crew-flight pairing, to cover every flight at the lowest cost. Limits such as seats, fuel and required crew rest hours are the linear constraints, and the cheapest schedule sits at a corner of a huge feasible region.

Common Mistakes

  1. The slip: Searching the interior for the best value

    Instead: the optimum of a linear objective lies at a vertex of the feasible region; evaluate the objective at each corner

  2. The slip: Forgetting hidden constraints like x≥0

    Instead: real quantities are often nonnegative, which changes the corners

  3. The slip: Mixing up maximize and minimize

    Instead: read whether you want the largest or smallest objective value before comparing corners


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Find the corner points of the region x≥0, y≥0, x+2y≤8.

    Hint: Find where the line x+2y=8 meets each axis.

  2. Maximize P=2x+5y subject to x≥0, y≥0, x+2y≤8.

    Hint: Test P at every corner of the region.

  3. Minimize C=4x+3y subject to x+y≥5, x≥1, y≥1.

    Hint: Find where x+y=5 meets x=1 and y=1.

  4. A baker makes x cakes and y pies. A cake takes 2 hours and a pie 1 hour, with 10 hours available, and at most 6 items fit in the oven. Profit is $8 per cake and $5 per pie. Find the best plan.

    Hint: Constraints: 2x+y≤10, x+y≤6, x,y≥0. Test each corner.

  5. Maximize A=x(10−x) for 0≤x≤10. Is this a linear programming problem?

    Hint: Expand A. Is it linear in x?

  6. To maximize P=x+3y subject to x+y≤4, x≥0, y≥0, a student tests only the inside point (2,2) and reports P=8. Find the mistake.

    Hint: Where does a linear objective reach its best value?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Can a linear programming problem have no best answer?

Yes, in two ways. If the constraints contradict each other, such as x+y≤4x+y\le4 and x+y≥10x+y\ge10, the feasible region is empty and no choice is allowed. If the region is unbounded, stretching forever in some direction, the profit can grow without limit, so there is no maximum. In real problems an unbounded answer usually means a constraint was left out, such as a limit on how many items can be sold.

What if two corners give the same best value?

Then every point on the edge between them is also best. This happens when the profit line runs parallel to that edge, so the sliding ruler touches the whole edge at once. If profit is 2x+2y2x+2y and the edge lies on x+y=10x+y=10, every point along it earns the same profit of 20. The business can then choose any mix on that edge for other reasons.

Where is linear programming actually used?

It grew out of military supply planning around the Second World War. Today airlines use it to assign planes and crews, refineries to choose product mixes, and farms to pick feed blends that meet nutrition targets at the lowest cost. Real problems can have thousands of variables, far too many to graph, so computers use the simplex method, which walks from corner to corner, improving each time, until no neighbouring corner is better.

How do I find the corners without a perfect graph?

Each corner is where two boundary lines cross, so solve those two equations together. A sketch tells you which pairs of lines meet at the edge of the region; the algebra then gives exact coordinates. Always check that the crossing point satisfies every other constraint too, because two boundary lines can also cross outside the region, and that point does not count.

Learning Path

Linear Programming

You are here

Next →

Nothing after this yet
You need Inequalities, Systems of Equations (to find where two boundary lines cross) and Constraint System (several conditions holding at once) first. This concept adds an objective to optimize and the rule that its best value sits at a corner of the feasible region. It leads to planning problems with hundreds of variables, solved by the simplex method in operations research, and to integer programming when answers must be whole numbers.

See Also