Introduction to Linear Programming

Lesson 1 of 10: Recognising LP Problems

In this lesson:

• Recognise an LP problem by its three features
• Distinguish LP problems from other word problems

What You Will Learn Today

By the end of this lesson:

1. Recognise an LP problem by its three structural features
2. Identify the decision variables and the objective in a worded scenario
3. Distinguish LP problems from word problems that look similar

Monday Morning at the Workshop

The carpenter has 12 hours of cutting time, 12 hours of finishing. Tables earn more, chairs are quicker. What's the best mix?

Three Plans That All Fit the Hours

Which is best — or is there a better one we haven't tried?

"Can It Work?" vs. "What Works Best?"

Two different kinds of question:

• Feasibility: does this plan fit the limits? (yes / no)
• Optimization: of all the plans that fit, which is best?

LP answers the second kind — only the second.

Linear Programming: A Method With a Name

Linear programming (LP) is the method for finding the best allocation of limited resources to competing activities, when all the relationships are linear.

• "Linear" — the relationships are sums of quantities, no powers, no products
• "Programming" — historical word meaning "planning," not computer code

Which of These Are LP Problems?

Sort each into LP or Not LP:

1. Tailor: shirts vs. dresses, maximise profit, limited cloth and time
2. Rectangle's area given perimeter 20 m and length 6 m
3. Farmer: maize vs. beans, maximise harvest, limited land and seed
4. School timetable, minimise empty teaching rooms

Why the Rectangle Isn't LP

Given perimeter 20 m and length 6 m, the width must be 4 m. Area = 24 m².

• One answer, no choice
• Nothing to optimise — the rectangle is fully determined
• LP needs both a choice and a goal, not just numbers

Back to the Carpenter's Situation

Look again at the carpenter's situation:

• What did she get to choose?
• What was limited that bounded her choice?
• What was the goal she was reaching for?

Answer in your own words before the next slide.

Every LP Problem Has Three Features

Every LP problem contains all three:

1. Decision variables — what the decision-maker chooses
2. Constraints — the limits that bound the choices
3. Objective — the goal (maximise or minimise something)

If you can name all three, it's LP. If any is missing, it isn't.

The Carpenter's Three Features Labelled

A Farmer in Eastern Uganda

A farmer plants maize and beans on 10 hectares, with 80 kg of seed available, to maximise harvest value.

• Decision variables: hectares of maize, hectares of beans
• Constraints: 10 hectares total, 80 kg seed
• Objective: maximise harvest value

A Transport Company With Two Vehicles

A company uses minivans and lorries to move goods, with fuel and capacity limits, to minimise cost.

• Decision variables: number of minivans, number of lorries
• Constraints: fuel available, total capacity required
• Objective: minimise total cost

Your Turn: A School Timetable

A school decides how many hours per week to assign mathematics and English, given limited teacher-hours and required minimum hours per subject, to balance the timetable.

Name the decision variables, constraints, and objective in your own words.

Same Word in Two Opposite Roles

Read both of these out loud:

• "No more than 12 hours of cutting time available" → limit (constraint)
• "Maximise profit" → goal (objective)

Both can contain the word "maximum." The role — limit or goal — is the meaning.

What's True That Nobody Wrote Down?

The carpenter scenario states two limits: cutting hours and finishing hours. What's true that nobody wrote down?

• You cannot make a negative number of tables
• You cannot make a negative number of chairs

These are implicit constraints: and — always check.

Vocabulary: A Reference for the Unit

• Decision variables — what the decision-maker chooses
• Constraints — the limits (algebraic inequalities later)
• Objective function — the expression being optimised
• Feasible solution — any plan satisfying all constraints
• Optimal solution — the feasible plan that wins

Find the Error in This Decomposition

A student wrote this for the transport scenario:

• Decision variables: number of minivans, number of lorries ✓
• Constraints: fuel ≤ 100 L, capacity ≥ 500 kg, minimise cost ✗
• Objective: (left blank)

Which feature is misplaced? Move it.

Exit Task: The Baker's Problem

A baker has 5 kg flour and 3 kg sugar. Bread uses 0.5 kg flour; cake uses 0.3 kg flour + 0.2 kg sugar. Maximise earnings (bread 2,000 UGX; cake 5,000 UGX).

Answer in your notebook:

1. Is this LP?
2. Decision variables?
3. Constraints?
4. Objective?

Key Takeaways From Today's Lesson

✓ LP = chooser + limits + linear goal
✓ Two variables alone is not LP
✓ "Max hours" is a limit; "max profit" is a goal
✓ Always add non-negativity: ,

Watch out: one forced answer means not LP.

Where We're Going in This Unit

• Today: Recognise LP problems
• Next 9 lessons: translate → graph → optimise → apply