Linear Programming

Syllabus Identity

Curriculum: Mathematics
Topic ID: topic-csee-basic-mathematics-2005-linear-programming
Form: Form IV
Hub: Algebra and Functions
Competence grouping: Algebra, relations and functions

This is a current Mathematics syllabus topic. It preserves the 2005 Basic Mathematics identity and order for exam-facing mapping. Do not merge it into the 2023 Mathematics transition topic page even when the learning idea overlaps.

Official Scope

Current Mathematics syllabus topic covering simultaneous equations; inequalities; objective function; maximum and minimum values.

Subtopics

Core Concepts

Linear Programming is a mathematical method used to determine the best possible outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.

Simultaneous Equations

Simultaneous equations are a set of two or more equations, each containing two or more variables, whose values can simultaneously satisfy all equations in the set. In the context of linear programming, simultaneous equations often represent the boundary lines of the constraints. Solving them allows us to find the exact coordinates of the intersection points, which are the vertices (corner points) of the feasible region.

A system of two linear equations in two variables, $x$ and $y$, takes the form: $$a_1x + b_1y = c_1$$ $$a_2x + b_2y = c_2$$

These can be solved using substitution, elimination, or graphical methods. At the intersection point of two boundary lines, both equations hold true.

Inequalities

In linear programming, real-world constraints (like budget limits, maximum capacity, or minimum required nutrients) are modeled using linear inequalities. Unlike an equation that represents a line, a linear inequality represents a half-plane.

A linear inequality in two variables can be written as: $$ax + by \leq c \quad \text{or} \quad ax + by \geq c$$

When graphing inequalities:

Replace the inequality sign with an equal sign to graph the boundary line. Use a solid line for $\leq$ or $\geq$, and a dashed line for $<$ or $>$.
Choose a test point (often the origin $(0,0)$ if the line does not pass through it).
If the test point satisfies the inequality, shade the region containing the test point. If not, shade the opposite region. (Note: It is a common convention in some curricula to shade the unwanted region so that the feasible region is left blank).

The intersection of all the valid regions for a set of inequalities forms the feasible region, which represents all possible solutions that satisfy every constraint.

Objective Function

The objective function is the linear equation that we want to optimize (either maximize or minimize). It represents the goal of the problem, such as profit, cost, or time.

It is typically written in the form: $$f(x, y) = px + qy$$ where $p$ and $q$ are constants representing the contribution per unit of $x$ and $y$, respectively.

Maximum and Minimum Values

The fundamental theorem of linear programming states that if the objective function has a maximum or minimum value in the feasible region, it must occur at one of the vertices (corner points) of the feasible region.

Steps to find maximum/minimum values:

Define the decision variables ($x$ and $y$).
Formulate the objective function.
Formulate the linear inequalities (constraints) based on the given conditions, including non-negativity constraints ($x \geq 0$, $y \geq 0$).
Graph the inequalities and identify the feasible region.
Determine the coordinates of all the vertices of the feasible region. This may require solving simultaneous equations for the intersecting boundary lines.
Evaluate the objective function at each vertex. The highest value gives the maximum, and the lowest gives the minimum.

Worked Examples

Example 1: Formulating a Linear Programming Model A tailor has $150 \text{ m}^2$ of cotton material and $90 \text{ m}^2$ of wool material. He wants to make two types of clothes. A suit requires $1 \text{ m}^2$ of cotton and $2 \text{ m}^2$ of wool while a gown requires $3 \text{ m}^2$ of cotton and $1 \text{ m}^2$ of wool. If a suit is sold at Tsh 40,000 and a gown at Tsh 60,000; formulate the objective function and the linear inequalities representing this information.

Solution: Let $x$ be the number of suits to be made. Let $y$ be the number of gowns to be made.

Objective Function: The goal is to maximize the sales revenue. $$f(x, y) = 40,000x + 60,000y$$

Constraints: Cotton constraint: $1x + 3y \leq 150$ Wool constraint: $2x + 1y \leq 90$ Non-negativity constraints: $x \geq 0, y \geq 0$

Example 2: Minimization Problem Formulation A cook wishes to mix two types of foods, I and II in such a way that the mixture contains at least 10 units of vitamin A, 12 units of vitamin B and 8 units of vitamin C. The vitamin contents of one kilogram of food are given in the table below. One kilogram of Food type I costs Tsh 6,000 and one kilogram of Food type II costs Tsh 10,000. Formulate the linear programming model to minimize the cost.

| Food type | Vitamin A | Vitamin B | Vitamin C | | --- | --- | --- | --- | | Food type I | 1 | 2 | 3 | | Food type II | 2 | 2 | 1 |

Solution: Let $x$ be the kilograms of Food type I. Let $y$ be the kilograms of Food type II.

Objective Function: Minimize Cost, $C(x, y) = 6,000x + 10,000y$

Constraints: Vitamin A constraint: $x + 2y \geq 10$ Vitamin B constraint: $2x + 2y \geq 12$ Vitamin C constraint: $3x + y \geq 8$ Non-negativity constraints: $x \geq 0, y \geq 0$

Example 3: Graphical Method and Finding Vertices Find the maximum value of $f(x, y) = 3x + 4y$ subject to the constraints: $x + 2y \leq 14$ $3x - y \geq 0$ $x - y \leq 2$ $x \geq 0, y \geq 0$

Solution: Step 1: Identify the boundary lines. Line 1: $x + 2y = 14$. Intercepts: $(14, 0)$, $(0, 7)$. Line 2: $3x - y = 0 \implies y = 3x$. Passes through $(0,0)$ and $(2,6)$. Line 3: $x - y = 2$. Intercepts: $(2, 0)$, $(0, -2)$.

Step 2: Find the vertices of the feasible region by finding intersection points of boundaries enclosing the valid area.

Intersection of $x - y = 2$ and the $x$-axis ($y=0$): $(2, 0)$.
Intersection of $x - y = 2$ and $x + 2y = 14$:

Substitute $x = y + 2$: $(y + 2) + 2y = 14 \implies 3y = 12 \implies y = 4$. Then $x = 6$. Point: $(6, 4)$.

Intersection of $3x - y = 0$ and $x + 2y = 14$:

Substitute $y = 3x$: $x + 2(3x) = 14 \implies 7x = 14 \implies x = 2$. Then $y = 6$. Point: $(2, 6)$.

The origin $(0,0)$ is a vertex since $3x - y \geq 0$ holds as equality, $x-y \leq 2$ holds, and $x+2y \leq 14$ holds.

Vertices of the feasible region are $(0,0)$, $(2,0)$, $(6,4)$, and $(2,6)$.

Step 3: Evaluate the objective function $f(x, y) = 3x + 4y$. At $(0,0)$: $3(0) + 4(0) = 0$ At $(2,0)$: $3(2) + 4(0) = 6$ At $(6,4)$: $3(6) + 4(4) = 18 + 16 = 34$ At $(2,6)$: $3(2) + 4(6) = 6 + 24 = 30$

The maximum value is 34, which occurs at $(6,4)$.

Example 4: Full Optimization Problem (Space Constraint) A trader has a space for 5 refrigerators. The trader plans to spend 2,400,000 shillings to buy refrigerators of two brands, Hitachi and Sony. Each Hitachi refrigerator costs 600,000 shillings whereas each Sony refrigerator costs 400,000 shillings. The unit profits for Hitachi and Sony refrigerators are 200,000 shillings and 150,000 shillings respectively. Denoting $x$ and $y$ as the number of Hitachi and Sony refrigerators respectively, determine the number of refrigerators for each brand that maximizes profit.

Solution: Let $x$ = number of Hitachi refrigerators. Let $y$ = number of Sony refrigerators.

Objective Function: Maximize Profit $P(x, y) = 200,000x + 150,000y$

Constraints: Space constraint: $x + y \leq 5$ Cost constraint: $600,000x + 400,000y \leq 2,400,000 \implies 3x + 2y \leq 12$ Non-negativity constraints: $x \geq 0, y \geq 0$

Vertices of the feasible region: Boundary lines:

$x + y = 5 \implies$ intercepts are $(5,0), (0,5)$
$3x + 2y = 12 \implies$ intercepts are $(4,0), (0,6)$

Intersection of $x + y = 5$ and $3x + 2y = 12$: Multiply the first by 2: $2x + 2y = 10$ Subtract from the second: $(3x + 2y) - (2x + 2y) = 12 - 10 \implies x = 2$ Substitute $x = 2$ into $x + y = 5 \implies 2 + y = 5 \implies y = 3$. Intersection point: $(2, 3)$.

Valid vertices: $(0,0)$, $(4,0)$, $(0,5)$, $(2,3)$.

Evaluating Profit: At $(0,0)$: $P = 0$ At $(4,0)$: $P = 200,000(4) + 150,000(0) = 800,000$ At $(0,5)$: $P = 200,000(0) + 150,000(5) = 750,000$ At $(2,3)$: $P = 200,000(2) + 150,000(3) = 400,000 + 450,000 = 850,000$

The trader should buy 2 Hitachi and 3 Sony refrigerators to maximize profit.

Example 5: Specific Range Constraints and Integer Coordinates A farmer needs to buy up to 25 cows for a new herd. He can buy either brown cows at 50,000/= each or black cows at 80,000/= each and he can spend a total of not more than 1,580,000/=. He must have at least 9 cows of each type. On selling the cows he will make a profit of 5,000/= on each brown cow and 6,000/= on each black cow. How many of each type he should buy to maximize profit?

Solution: Let $x$ = number of brown cows. Let $y$ = number of black cows.

Objective Function: Maximize $P(x, y) = 5,000x + 6,000y$

Constraints: Total cows constraint: $x + y \leq 25$ Cost constraint: $50,000x + 80,000y \leq 1,580,000 \implies 5x + 8y \leq 158$ Minimum cows constraint: $x \geq 9$, $y \geq 9$

Vertices of the feasible region: Intersection of $x = 9$ and $y = 9$: $(9, 9)$ Intersection of $x = 9$ and $5x + 8y = 158$: $45 + 8y = 158 \implies 8y = 113 \implies y = 14.125$. The closest integer inside the boundary is $y = 14$. Point: $(9, 14)$. Intersection of $x + y = 25$ and $5x + 8y = 158$: $5(25 - y) + 8y = 158 \implies 125 + 3y = 158 \implies 3y = 33 \implies y = 11$, and $x = 14$. Point: $(14, 11)$. Intersection of $y = 9$ and $x + y = 25$: $x + 9 = 25 \implies x = 16$. Point: $(16, 9)$.

Evaluating Profit at valid integer vertices: At $(9,9)$: $P = 5,000(9) + 6,000(9) = 45,000 + 54,000 = 99,000/=$ At $(9,14)$: $P = 5,000(9) + 6,000(14) = 45,000 + 84,000 = 129,000/=$ At $(14,11)$: $P = 5,000(14) + 6,000(11) = 70,000 + 66,000 = 136,000/=$ At $(16,9)$: $P = 5,000(16) + 6,000(9) = 80,000 + 54,000 = 134,000/=$

The maximum profit is 136,000/=, obtained by buying 14 brown cows and 11 black cows.

Common Pitfalls & Misconceptions

Reversing Inequality Signs: A very common error is misinterpreting phrases like "at least" ($\geq$), "not more than" ($\leq$), "at most" ($\leq$), and "a minimum of" ($\geq$). Students often use $<$ instead of $\leq$, omitting the boundary line entirely.
Incorrect Shading: Students sometimes guess the region without using a test point. This leads to identifying the wrong feasible region. Always pick a test point, usually the origin $(0,0)$, and test it in the inequality.
Forgetting Non-Negativity Constraints: In most real-world problems, quantities cannot be negative. Failing to explicitly state and graph $x \geq 0$ and $y \geq 0$ leads to unbounded, incorrect regions.
Rounding Before Optimization: When vertices yield decimal coordinates in discrete variable problems (like the number of cows or refrigerators), students often round arbitrarily. The correct method is to identify the integer coordinates that lie strictly inside or on the boundaries of the feasible region and test those in the objective function.
Misidentifying the Objective Function: Students sometimes confuse a constraint equation with the objective function. The objective function is always the quantity to be maximized or minimized (like profit, cost, or time) and does not have a predefined limit (unlike a constraint).

NECTA Exam Focus

Linear Programming is a major, predictable topic in NECTA Basic Mathematics CSEE, typically appearing in Section B (which carries more marks).

Formulation: Students are almost always required to translate a word problem into mathematical language. This involves explicitly defining variables, formulating the objective function, and writing down all constraints (inequalities).
Graphing: Candidates must accurately draw the constraints on the $x-y$ plane, clearly shading the unwanted region (as per standard conventions) to leave the feasible region clean.
Optimization: The final step consistently requires extracting the vertices from the graph or solving simultaneous linear equations to identify intersection points, and substituting these coordinates into the objective function to find the maximum profit or minimum cost.
Qualitative Questions: Occasionally, NECTA includes brief theoretical questions, such as asking for the importance of studying linear programming (e.g., maximizing profit, minimizing cost, resource allocation).

Practice Problems

Level 1: Basic Formulation

What is the importance of studying linear programming? Give 2 points.
Formulate the objective function and the linear inequalities for the following: A tailor has $150 \text{ m}^2$ of cotton material and $90 \text{ m}^2$ of wool material. He wants to make two types of clothes. A suit requires $1 \text{ m}^2$ of cotton and $2 \text{ m}^2$ of wool while a gown requires $3 \text{ m}^2$ of cotton and $1 \text{ m}^2$ of wool. If a suit is sold at Tsh 40,000 and a gown at Tsh 60,000.

Level 2: Intermediate Minimization

A cook wishes to mix two types of foods, I and II in such a way that the mixture contains at least 10 units of vitamin A, 12 units of vitamin B and 8 units of vitamin C. The vitamin contents of one kilogram of food are given in the following table. One kilogram of Food type I costs Tsh 6,000 and one kilogram of Food type II costs Tsh 10,000. Formulate the linear programming model to minimize the cost.