Linear programming

Overview

Linear programming is a method for choosing the best possible outcome when resources are limited and the conditions can be written using linear inequalities.

It is useful in production, transport, diet, business, farming, and planning problems. In Form III, learners mainly need to translate a word problem into variables, constraints, and an objective function, then use the feasible region or corner points to make a decision.

The word "programming" here does not mean computer programming. It means planning. A linear programming problem asks, "What plan gives the best result while still obeying all the limits?"

Most learner difficulty comes before any graph is drawn. The key step is translating words into mathematics: quantities become variables, limits become inequalities, and the target becomes an objective function.

Prerequisites

• Algebraic expressions and equations - Constraints and objectives are built from linear expressions.
• Inequalities in one unknown - Linear programming uses inequality signs such as $\le$ and $\ge$.
• Linear simultaneous equations - Corner points are often found by solving pairs of boundary lines.
• Coordinate geometry: gradient and straight-line equations - Feasible regions are drawn on coordinate axes.
• Relations and functions - Objective functions connect decision variables to profit, cost, or other quantities.

Learning Scope

This chapter covers the meaning of linear programming, decision variables, objective functions, constraints, non-negativity restrictions, feasible regions, corner points, maximisation, minimisation, and formulation from word problems.

This page does not fully teach graph drawing from first principles or advanced optimisation. It gives the Form III structure needed to model and solve common two-variable linear programming problems.

Subtopics

Decision Variables

Decision variables represent the quantities to be chosen.

For example, if a tailor makes suits and gowns, we may let:

$$ x=\text{number of suits} $$

and:

$$ y=\text{number of gowns} $$

Key insight: Define variables before writing inequalities. A clear definition makes the whole model easier to check.

Why this works: every expression in the model depends on what $x$ and $y$ mean. If $x$ is "number of suits", then $2x$ means "two units for each suit." If $x$ is not defined, the inequality may look correct but have no clear meaning.

Good variable definitions include:

• what the variable represents;
• the unit, if needed;
• the time period, if the problem uses one.

For example:

$$ x=\text{number of chairs made per day} $$

is clearer than:

$$ x=\text{chairs} $$

Objective Function

The objective function is the expression to maximise or minimise.

If each suit gives Tsh $40,000$ and each gown gives Tsh $60,000$, the income can be written as:

$$ P=40000x+60000y $$

If the problem asks for maximum income, then $P$ is maximised. If it asks for minimum cost, then the objective is minimised.

The objective function is not a limit. It is the score being tested for each possible plan. In a profit problem, a larger score is better. In a cost problem, a smaller score is better.

To build an objective function:

1. Identify what must be maximised or minimised.
2. Find the contribution from one unit of each item.
3. Multiply each contribution by its variable.
4. Add the terms.
5. Name the objective, such as $P$, $C$, or $Z$.

Constraints

Constraints are limits written as inequalities. They come from available materials, time, money, nutrition requirements, or other conditions.

If a suit uses $1$ unit of cotton and a gown uses $3$ units of cotton, and only $150$ units are available, then:

$$ x+3y \le 150 $$

If a suit uses $2$ units of wool and a gown uses $1$ unit of wool, and only $90$ units are available, then:

$$ 2x+y \le 90 $$

Why this works: a resource constraint compares "amount used" with "amount available." If the resource is limited, the amount used must not be more than the available amount.

| Wording in problem | Common inequality | | --- | --- | | at most, not more than, no more than, maximum, available | $\le$ | | at least, not less than, minimum, required | $\ge$ | | exactly, equal to | $=$ |

The left side usually represents what the chosen plan uses or provides. The right side usually represents the limit or requirement.

Non-Negativity Restrictions

Most real-life quantities cannot be negative. If $x$ and $y$ represent numbers of items, then:

$$ x \ge 0,\quad y \ge 0 $$

These restrictions are part of the model, not an optional extra.

Without these restrictions, a graph may include points such as $(-4,10)$, which have no real meaning if $x$ represents a number of items. Non-negativity keeps the model in the meaningful part of the coordinate plane.

Feasible Region

The feasible region is the set of all points that satisfy every constraint at the same time.

To find it:

1. Draw each boundary line.
2. Shade the side that satisfies the inequality.
3. Keep only the overlap of all shaded regions.

Every point in the feasible region is possible. Points outside it break at least one condition.

Why overlap matters: satisfying one constraint is not enough. A plan must obey every limit at the same time. The feasible region is the shared safe area for all constraints.

Boundary-line routine:

1. Replace the inequality sign with an equals sign.
2. Find two points on the boundary line, often by using intercepts.
3. Draw the boundary line.
4. Test a simple point such as $(0,0)$ if it is not on the line.
5. Shade the side that makes the inequality true.
6. Repeat for every constraint and keep only the common overlap.

Corner Points And Optimal Solutions

For a two-variable linear programming problem, the best value of a linear objective function occurs at a corner point of the feasible region, when an optimum exists.

The usual method is:

1. List the corner points.
2. Substitute each corner point into the objective function.
3. Choose the largest value for maximisation or the smallest value for minimisation.

Why corner points are enough: a linear objective changes steadily across a straight-line direction. Over a polygon-shaped feasible region, the highest or lowest value is reached at an edge endpoint, which is a corner point, unless there are equal best values along an entire edge.

Corner-point checking routine:

1. Include axis intercept corners where the feasible region touches the axes.
2. Include intersection points where boundary lines cross.
3. Substitute each corner into every constraint if there is any doubt.
4. Evaluate the objective at every feasible corner.
5. State both the best objective value and the decision variables that produce it.

Formulation Before Solving

Many exam-style items ask only for formulation. That means the learner should write:

• variable definitions;
• objective function;
• constraints;
• non-negativity restrictions.

No graph is needed unless the question asks for a solution or optimum value.

Formulation routine:

1. Read the question once for context.
2. Underline the quantities to be chosen.
3. Define variables.
4. Identify whether the target is maximum or minimum.
5. Write the objective function.
6. Convert each resource, requirement, or limit into a constraint.
7. Add non-negativity restrictions.
8. Check that all units match.

If the question asks "formulate", stop after the model unless it also asks to solve.

Key Terms

• Linear programming: A method for optimising a linear objective subject to linear constraints.
• Decision variable: A symbol representing a quantity to be chosen.
• Objective function: The expression to maximise or minimise.
• Constraint: A condition written as an equation or inequality.
• Feasible region: The set of points satisfying all constraints.
• Corner point: A vertex of the feasible region.
• Maximisation: Choosing the greatest possible value of the objective.
• Minimisation: Choosing the smallest possible value of the objective.
• Non-negativity restriction: A condition such as $x \ge 0$ and $y \ge 0$.

Worked Examples

Example 1: Formulate A Production Problem

A tailor has $150$ units of cotton and $90$ units of wool. A suit uses $1$ unit of cotton and $2$ units of wool. A gown uses $3$ units of cotton and $1$ unit of wool. A suit sells for Tsh $40,000$ and a gown sells for Tsh $60,000$.

Let:

$$ x=\text{number of suits},\quad y=\text{number of gowns} $$

Cotton constraint:

$$ x+3y \le 150 $$

Wool constraint:

$$ 2x+y \le 90 $$

Non-negativity:

$$ x \ge 0,\quad y \ge 0 $$

Objective function:

$$ P=40000x+60000y $$

The model is:

$$ \begin{aligned} \text{Maximise } P &= 40000x+60000y \\ \text{subject to } x+3y &\le 150 \\ 2x+y &\le 90 \\ x &\ge 0,\quad y \ge 0 \end{aligned} $$

Check:

• Cotton terms match cotton use: $1$ per suit and $3$ per gown.
• Wool terms match wool use: $2$ per suit and $1$ per gown.
• Both resource limits use $\le$ because only a limited amount is available.
• The objective uses selling values, not resource amounts.

Example 2: Test A Feasible Point

For the constraints:

$$ x+3y \le 150,\quad 2x+y \le 90,\quad x \ge 0,\quad y \ge 0 $$

test whether $(30,20)$ is feasible.

Substitute $x=30$ and $y=20$:

$$ 30+3(20)=90 \le 150 $$

and:

$$ 2(30)+20=80 \le 90 $$

Both non-negativity restrictions are also satisfied. Therefore $(30,20)$ is feasible.

Check:

• A feasible point must pass every constraint.
• Passing one resource constraint is not enough.
• The point $(30,20)$ means $30$ units of the first item and $20$ units of the second item in this model.

Example 3: Choose The Best Corner Point

Suppose the corner points of a feasible region are:

$$ (0,0),\ (45,0),\ (24,42),\ (0,50) $$

and the objective function is:

$$ P=40000x+60000y $$

Evaluate:

| Corner point | $P=40000x+60000y$ | |---:|---:| | $(0,0)$ | $0$ | | $(45,0)$ | $1,800,000$ | | $(24,42)$ | $3,480,000$ | | $(0,50)$ | $3,000,000$ |

The maximum value is Tsh $3,480,000$ at $(24,42)$.

Therefore the best choice is $24$ suits and $42$ gowns, if the variables represent whole items and this point is allowed by the problem.

Check:

• The objective was evaluated at all listed corner points.
• Since this is a maximisation problem, the largest value is selected.
• The final answer interprets $(24,42)$ using the original variable definitions.

Example 4: Build A Constraint From A Minimum Requirement

A school meal must contain at least $18$ units of energy. Food $A$ provides $3$ units per packet and food $B$ provides $2$ units per packet.

Let:

$$ x=\text{number of packets of food A},\quad y=\text{number of packets of food B} $$

Energy provided:

$$ 3x+2y $$

Since the meal must contain at least $18$ units:

$$ 3x+2y \ge 18 $$

Check:

• "At least" means the amount can be $18$ or more, so use $\ge$.
• The coefficients $3$ and $2$ come from energy per packet.
• The variables count packets, so include $x\ge0$ and $y\ge0$ in a full model.

Example 5: Find A Corner Point By Solving Two Boundary Lines

Find the intersection of the boundary lines:

$$ x+3y=150 $$

and:

$$ 2x+y=90 $$

From the second equation:

$$ y=90-2x $$

Substitute into the first equation:

$$ \begin{aligned} x+3(90-2x)&=150\\ x+270-6x&=150\\ -5x&=-120\\ x&=24 \end{aligned} $$

Then:

$$ y=90-2(24)=42 $$

So the intersection point is:

$$ (24,42) $$

Check:

• Substitute into $x+3y=150$: $24+3(42)=150$.
• Substitute into $2x+y=90$: $2(24)+42=90$.
• The point lies in the first quadrant, so it is possible for non-negative quantities.

Example 6: Formulate A Minimisation Problem

A diet uses foods $X$ and $Y$. One unit of $X$ costs Tsh $500$ and gives $4$ units of protein. One unit of $Y$ costs Tsh $800$ and gives $5$ units of protein. The diet must provide at least $40$ units of protein.

Let:

$$ x=\text{units of food X},\quad y=\text{units of food Y} $$

Objective function:

$$ C=500x+800y $$

Since the aim is to spend as little as possible:

$$ \text{Minimise } C=500x+800y $$

Protein constraint:

$$ 4x+5y \ge 40 $$

Non-negativity:

$$ x\ge0,\quad y\ge0 $$

Full model:

$$ \begin{aligned} \text{Minimise } C&=500x+800y\\ \text{subject to } 4x+5y&\ge40\\ x&\ge0,\quad y\ge0 \end{aligned} $$

Check:

• Cost is minimised, not protein.
• Protein is a requirement, so it becomes a constraint.
• "At least $40$" uses $\ge$.

Common Mistakes

• Writing variables after constraints. Correction: define each variable first. Warning sign: the model has $x$ and $y$ but the reader cannot tell what they represent.
• Defining variables too vaguely. Correction: include the quantity and unit or time period when needed. Warning sign: $x=\text{maize}$ instead of $x=\text{hectares of maize}$.
• Reversing inequality signs. Correction: "at most" and "not more than" usually use $\le$; "at least" usually uses $\ge$. Warning sign: an available resource is written with $\ge$.
• Forgetting $x \ge 0$ and $y \ge 0$. Correction: include non-negativity restrictions for real quantities. Warning sign: the graph allows negative numbers of products, animals, packets, or hours.
• Treating the objective function as a constraint. Correction: the objective is what is being optimised; constraints are the limits. Warning sign: the profit expression is written with $\le$ even though no profit limit is given.
• Mixing units in one inequality. Correction: keep hours with hours, kilograms with kilograms, and money with money. Warning sign: a left side adds hours and shillings in the same expression.
• Shading the wrong side of a boundary line. Correction: test a point and check the inequality before shading. Warning sign: the chosen region does not include an obvious possible point such as $(0,0)$ when it should.
• Listing corner points without checking feasibility. Correction: substitute doubtful points into every constraint. Warning sign: an intersection point is outside the shaded region but still appears in the objective table.
• Choosing a point inside the region without checking corner points. Correction: evaluate the objective at all relevant corner points. Warning sign: the answer says "any point near the middle" for a maximum or minimum problem.
• Giving only the maximum or minimum value without the plan. Correction: state both the objective value and the values of $x$ and $y$. Warning sign: the final answer gives "Tsh $3,480,000$" but not "24 suits and 42 gowns."
• Ignoring whole-number context. Correction: if variables count whole items, check whether fractional corner points are allowed. Warning sign: the answer recommends $3.5$ cows, desks, or people.

Practice Tasks

Foundation

1. State the decision variables for a farmer who plants maize and beans.
2. Explain the difference between an objective function and a constraint.
3. Choose the correct sign: "not more than $50$ kg", "at least $20$ units", and "exactly $12$ hours".
4. Write the non-negativity restrictions for variables $x$ and $y$ representing numbers of tables and chairs.

Skill-Building

1. A product $A$ gives a profit of Tsh $2,000$ and product $B$ gives Tsh $3,500$. Write the objective function for maximum profit.
2. A workshop has $80$ hours available. Item $A$ uses $2$ hours and item $B$ uses $5$ hours. Write the time constraint.
3. A diet must contain at least $12$ units of protein. Food $X$ gives $3$ units and food $Y$ gives $2$ units. Write the protein constraint.
4. Test whether $(10,6)$ satisfies $2x+3y \le 40$, $x+y \le 20$, $x\ge0$, and $y\ge0$.
5. Draw the boundary line $2x+y=10$ using intercepts, then decide which side satisfies $2x+y\le10$.

Exam-Style

1. Formulate a full model for two products using two resources and a profit objective. Include variables, constraints, non-negativity restrictions, and objective function.
2. A carpenter makes tables and chairs. A table needs $4$ hours and a chair needs $2$ hours. At most $48$ hours are available. A table gives Tsh $15,000$ profit and a chair gives Tsh $8,000$ profit. Write the time constraint and profit objective.
3. Given corner points $(0,0)$, $(8,0)$, $(5,4)$, and $(0,6)$, maximise $Z=7x+5y$ and state the best point.
4. For constraints $x+2y\le12$, $3x+y\le15$, $x\ge0$, and $y\ge0$, test whether $(4,3)$ and $(2,5)$ are feasible.

Challenge

1. A minimisation problem has objective $C=6x+9y$ and corner points $(0,8)$, $(3,4)$, and $(10,0)$. Find the minimum value and the point where it occurs.
2. Find the intersection of $x+2y=14$ and $3x+y=18$, then test whether the point satisfies $x\ge0$ and $y\ge0$.
3. Explain why the optimum is checked at corner points rather than at every point inside the feasible region.
4. Create a full linear programming model for a diet problem with two foods, one minimum nutrient requirement, one maximum budget limit, and a cost or nutrition objective.

Generated Question Layer

• Vocabulary questions: identify variables, constraints, objective functions, and feasible regions.
• Formulation questions: translate word problems into mathematical models.
• Inequality questions: choose the correct inequality sign from wording.
• Feasibility questions: test whether a point satisfies all constraints.
• Optimisation questions: evaluate objective functions at corner points.
• Interpretation questions: state the meaning of the optimal point in the original context.

Learner Aid Opportunities

• chart: Create a formulation checklist table with columns for word phrase, mathematical role, expression, inequality sign, and units.
• graph: Create a feasible-region asset showing two resource constraints, non-negativity axes, shaded overlap, and labelled corner points.
• interactive: Build a constraint-shading activity where learners toggle $\le$ and $\ge$, test $(0,0)$, and see the feasible region update.
• chart: Create an objective-value table template that forces learners to list all corner points before choosing the optimum.
• LLM tutor: Prompt learners to identify variables, classify each sentence as objective or constraint, choose the inequality sign, and explain the final plan in words.

Exam-Derived Signals

These signals are assessment leads, not verified official past-question links. They should be checked against original papers and marking schemes before being used as final learner-facing references.

| Source | Current Signal | Review Status | Use Carefully As | | --- | --- | --- | --- | | data/exam_format_topic_crosswalk_2022.jsonl | Official 2022 format group Linear Programming/Functions/Relations maps to this topic and sibling pages; one item; weight 7.14. | Official format mapping; topic-page use still unreviewed. | Evidence that linear programming belongs to a tested format group. | | data/topic_frequency_2021_2025.json | topic-linear-programming has total count 3 in the 2021-2025 extraction set. | Unreviewed aggregate. | Rough retrieval priority, not a final frequency claim. | | data/question_map_2021_2025.jsonl | Examples include a 2021 conceptual item on importance, a 2024 diet or mixture minimisation formulation, and a 2025 tailor production formulation. | mapped_unreviewed. | Leads for future reviewed past-question linking. | | data/question_map_2021_2025.jsonl | Several mappings are marked needs_manual_review, especially where tables or secondary topics are involved. | Needs manual review. | Warning not to treat the extracted links as reviewed evidence yet. |

Source And Review Notes

• Topic registry status: official in data/curriculum_map.json.
• Learner expansion status: original prose drafted from the official syllabus topic and local assessment signals.
• Exam mapping status: unreviewed except for the official exam-format crosswalk group.
• Review risk: future review should check table-dependent extracted questions against the original papers before using their figures in learner-facing worked solutions.