Abhranti.ai
Explore
Start free

Teach Linear Programming in five steps.

For each idea: show it, ask before you tell, then say one line.

Gather paper, squared paper, a pencil and a ruler.

Common misconceptions & worked visual for this chapter · 15 practice questions with answers

Why it matters

  • A drink seller balances limited fridge space against the profit each drink earns.
  • A canteen keeps meal costs down while meeting food requirements.
  • A workshop divides limited materials between products to earn more.

What to teach

Set up the problem

Linear Programming Problem and its Mathematical FormulationFind the best permitted choice using linear expressions.Feasible RegionThe overlap containing every choice that meets all restrictions.

Find the best value

Corner Point MethodCompare corner values to find the largest and smallest results.Corner Point Method for an Unbounded Feasible RegionCheck whether allowed points improve the best corner value.Multiple Optimal SolutionsA whole segment can share the best value.

How to teach it

Set up the problem

Maximise Z=x+2y\text{Maximise } Z=x+2y

x+y≤4x+y\leq4

x≥0x\geq0

1. Linear Programming Problem and its Mathematical Formulation

Find the best permitted choice using linear expressions.

Show
Write these lines for two juices sharing four litres of storage. Say all stocked juice sells. Let x and y be litres, earning one and two rupees per litre respectively. Call total profit Z.
Ask
Without a lower limit, could our profit search include a negative volume of the second juice?
Say
The second volume cannot be negative.
Used in
Bakeries plan production to increase profit within flour and oven-time limits.
If your child says…“The profit formula is the constraint.”
Ask
Which describes the reward, and which describes the available space?
What’s true
The objective measures what you optimise; constraints limit your choices.
Storage triangle with labelled corners, rejected regions, an outside point and an enclosing circle.

2. Feasible Region

The overlap containing every choice that meets all restrictions.

Show
In the diagram, find the solid storage boundary, hatched rejected regions, and three allowed corners. Test the origin against the storage limit to explain which side remains. Notice that the circle encloses the whole allowed region.
Ask
Will the choice (3,2)(3,2) meet every restriction?
Say
Those amounts exceed storage despite being non-negative. The remaining overlap is bounded because it fits inside a circle.
Used in
Delivery loads must meet both weight and space limits to fit safely.
If your child says…“Meeting one restriction makes a choice allowed.”
Ask
Do non-negative amounts guarantee that both drinks fit?
What’s true
Each allowed point must pass every restriction together.

Find the best value

Ruler touching the labelled triangle’s upper-left corner, parallel to two profit lines.

3. Corner Point Method

Compare corner values to find the largest and smallest results.

Show
In the diagram, find both profit lines and the ruler touching the triangle’s upper-left corner. Trace where a parallel profit line first and last touches the triangle. Compare the corner profits.
Ask
Would moving beyond the last contact allow greater profit?
Say
Maximum profit is eight at (0,4)(0,4); minimum profit is zero at (0,0)(0,0). Beyond these contacts, no allowed points remain.
Used in
Furniture workshops compare feasible production mixes to find the most profitable one.
If your child says…“The corner furthest right must earn most.”
Ask
Which earns more here: four litres of the first drink or four of the second?
What’s true
For a nonempty, closed, bounded region, comparing every corner finds both extremes.
Unbounded feasible region separated from the region where profit falls below two.

4. Corner Point Method for an Unbounded Feasible Region

Check whether allowed points improve the best corner value.

Show
In the diagram, find non-negative volumes totalling at least two litres. Compare corner profits.
Ask
Can this endless region still have a smallest profit?
Say
The minimum is two, at (2,0)(2,0).
Used in
Feed mixtures can meet nutrition targets at minimum cost without a stated maximum quantity.
If your child says…“An endless region cannot have a minimum.”
Ask
Where does the region with profit below two overlap the allowed region?
What’s true
Test below the smallest corner value for minima, above the largest for maxima.
Parallel profit lines approach a highlighted edge containing two optimal corners and their midpoint.

5. Multiple Optimal Solutions

A whole segment can share the best value.

Show
Replace the two-litre minimum with the four-litre storage cap, keeping both volumes non-negative. Both juices now earn one rupee per litre. In the diagram, follow profit lines towards the storage boundary, then find its endpoints and midpoint.
Ask
Can the endpoints and midpoint all earn the same highest profit?
Say
Every point on that edge earns four rupees. Each uses all four litres, and no permitted choice can earn more.
Used in
Tied production plans let factories change their product mix without losing profit.
If your child says…“Only the two corners give the maximum.”
Ask
How much does the marked midpoint earn compared with either endpoint?
What’s true
Every point on the segment joining these optimal corners gives the same maximum.

A real problem

Planning train capacity made more confirmed seats available.

A research report on this railway project was published in 2010.

Researchers used linear programming to allocate train capacity optimally across route segments.

The model increased confirmed-seat availability for passengers travelling along intermediate sections of several train routes.

IIT BombayINFORMSDe Gruyter — Managerial Decision Modeling

Empty reserved seats inside an Indian passenger train.

Concept Lab · Common misconception

The tempting mistake in Linear Programming

Open standalone misconception page →

Can you optimise using just one constraint at a time?

Wrong

A point is feasible if it satisfies at least one constraint.

Why it feels right. Each inequality separately describes allowed points, so I combine the regions as an either-or.

Right

A feasible point satisfies every constraint simultaneously.

Worked example

The shaded polygon is the overlap of all constraints. (3, 1) lies outside x ≤ 2 even though it is below x + y = 5.
  1. With x + y ≤ 5, x ≤ 2 and x,y ≥ 0, (3,1) passes the first inequality but fails x ≤ 2.
  2. The point (2,3) passes all the inequalities.

Ask your child five quick questions.

One per step. The answer and the reason are given.

  1. Which is the objective here: total profit or the storage limit?

    Total profit. Profit is what we maximise; storage restricts the choices.

  2. Which restriction excludes (3,2)(3,2)?

    x+y≤4x+y\leq4. The amounts total five litres, exceeding the four-litre capacity.

  3. Which corner earns most with these profit rates?

    (0,4)(0,4). Compare profits: the corner values are zero, four and eight.

  4. What is the minimum on this endless region?

    Two. Every allowed point gives at least two, and (2,0)(2,0) gives exactly two.

  5. Which points on the highlighted edge give the maximum?

    Every point on it. Each point totals four litres, earning four rupees at the equal profit rates.

15 more questions with answers, 2 with pictures