Linear Programming Worked Examples (KBAT)

What these examples cover

These hard Linear Programming examples ask you to hold two ideas at once. The first is a full modelling problem: read two resource limits and two display rules, turn them into four inequalities, find every corner of the resulting region, then maximise a profit, and confirm the answer is a whole number, as the context demands.

The second and third add a genuine KBAT twist: one shows what happens when the objective runs parallel to an edge, so the maximum is shared along a whole edge rather than pinned to a single corner; the other treats a coefficient as unknown and asks for the range that keeps the optimum at one particular vertex. Attempt each fully before reading on.

Worked examples

Work through all three. The method is the same as ever, boundaries, corners, objective, but each example presses on it a little harder, so keep your working neat enough to defend every corner and every comparison.

Q1[7 marks]

A craftsman makes $x$ bracelets and $y$ necklaces each week. Each item uses 1 unit of silver wire, and at most 10 units are available.

Each bracelet uses 1 pack of beads and each necklace uses 2 packs, with at most 14 packs available. For display, he keeps at least 2 bracelets and at least 1 necklace.

The profit is $P=3x+5y$ ringgit. (a) Write the four inequalities.

(b) Find the vertices of the region. (c) Find the number of each item for maximum profit, and state that profit.

Show worked solution

(a) Read each limit as an inequality. Silver wire: each item uses 1 unit, at most 10 units, so $x+y\le 10$ .

Beads: $1$ pack per bracelet and $2$ per necklace, at most 14, so $x+2y\le 14$ . The display rules give $x\ge 2$ and $y\ge 1$ .

x+y\le 10,\quad x+2y\le 14,\quad x\ge 2,\quad y\ge 1

(b) The boundaries are $x+y=10$ , $x+2y=14$ , $x=2$ and $y=1$ . Solve them in pairs and keep the crossings that satisfy the whole set.

x=2,\; y=1 \;\Rightarrow\; (2,1)

y=1,\; x+y=10 \;\Rightarrow\; x=9,\quad (9,1)

(x+2y)-(x+y)=14-10 \;\Rightarrow\; y=4,\; x=6,\quad (6,4)

x=2,\; x+2y=14 \;\Rightarrow\; 2y=12,\; y=6,\quad (2,6)

So the region is the quadrilateral with vertices $(2,1)$ , $(9,1)$ , $(6,4)$ and $(2,6)$ .

\text{At }(2,1):\; P=3(2)+5(1)=6+5=11

\text{At }(9,1):\; P=3(9)+5(1)=27+5=32

\text{At }(6,4):\; P=3(6)+5(4)=18+20=38

\text{At }(2,6):\; P=3(2)+5(6)=6+30=36

Answer

The maximum profit is $P=\text{RM}\,38$ , from making $6$ bracelets and $4$ necklaces. Both are whole numbers, so no rounding is needed.

It is worth checking the two closest rivals, $(2,6)$ gives $36$ and $(9,1)$ gives $32$ , because a single arithmetic slip could otherwise crown the wrong corner.

Q2[6 marks]

A feasible region is defined by $x\ge 1$ , $y\ge 2$ and $x+y\le 8$ . The objective function is $k=5x+5y$ .

Find the maximum value of $k$ , and describe fully where in the region it is attained.

Show worked solution

First pin down the corners. The boundaries are $x=1$ , $y=2$ and $x+y=8$ ; solve them in pairs.

x=1,\; y=2 \;\Rightarrow\; (1,2)

x=1,\; x+y=8 \;\Rightarrow\; y=7,\quad (1,7)

y=2,\; x+y=8 \;\Rightarrow\; x=6,\quad (6,2)

So the region is the triangle with vertices $(1,2)$ , $(1,7)$ and $(6,2)$ . Evaluate $k=5x+5y$ at each:

\text{At }(1,2):\; k=5(1)+5(2)=5+10=15

\text{At }(1,7):\; k=5(1)+5(7)=5+35=40

\text{At }(6,2):\; k=5(6)+5(2)=30+10=40

Two corners tie at the top with $k=40$ . That is the clue that the objective is parallel to the edge joining them.

Rewrite the objective as $k=5(x+y)$ : it depends only on $x+y$ , and the edge from $(1,7)$ to $(6,2)$ is exactly the line $x+y=8$ , the largest value $x+y$ can reach in the region.

Answer

The maximum value is $k=40$ . Because $k=5(x+y)$ is constant along the line $x+y=8$ , it is attained not just at one corner but at every point on the whole edge from $(1,7)$ to $(6,2)$ .

Any point on that edge, for instance $(3,5)$ , where $k=5(8)=40$ , is an equally valid optimal answer.

Q3[7 marks]

A feasible region is defined by $x\ge 0$ , $y\ge 0$ , $x+2y\le 10$ and $3x+2y\le 18$ . The objective function is $k=px+y$ , where $p>0$ .

(a) Find the four vertices of the region. (b) Find the range of values of $p$ for which the maximum of $k$ occurs at the vertex on the positive $x$ -axis.

Show worked solution

(a) Solve the boundaries in pairs. The origin, the two relevant axis-crossings, and the intersection of the two slanted lines give the four corners.

x=0,\; y=0 \;\Rightarrow\; O(0,0)

x+2y=10,\; x=0 \;\Rightarrow\; y=5,\quad A(0,5)

3x+2y=18,\; y=0 \;\Rightarrow\; x=6,\quad C(6,0)

For the last corner, subtract the first slanted equation from the second:

(3x+2y)-(x+2y)=18-10 \;\Rightarrow\; 2x=8,\; x=4,\; \text{then } 4+2y=10 \;\Rightarrow\; y=3

so $B(4,3)$ . The four vertices are $O(0,0)$ , $A(0,5)$ , $B(4,3)$ and $C(6,0)$ , with $C$ the vertex on the positive $x$ -axis.

(b) Evaluate $k=px+y$ at each vertex, treating $p$ as an unknown:

k_O=0,\quad k_A=5,\quad k_B=4p+3,\quad k_C=6p

For the maximum to occur at $C$ , the value $k_C=6p$ must be at least as large as the value at every other vertex. Since $p>0$ , $6p$ already exceeds $k_O=0$ .

Compare it with $A$ and $B$ :

6p\ge 5 \;\Rightarrow\; p\ge \tfrac{5}{6}

6p\ge 4p+3 \;\Rightarrow\; 2p\ge 3 \;\Rightarrow\; p\ge \tfrac{3}{2}

The stronger of the two conditions is $p\ge\tfrac{3}{2}$ , and it automatically satisfies $p\ge\tfrac{5}{6}$ as well.

Answer

The maximum of $k$ occurs at $C(6,0)$ when $p\ge \dfrac{3}{2}$ . At exactly $p=\tfrac{3}{2}$ the corners $B$ and $C$ tie, both give $9$ , so the maximum is then shared along the edge $BC$ ; for any $p>\tfrac{3}{2}$ , $C$ alone wins.

Q4[6 marks]

A stationery supplier restocks $x$ boxes of pens and $y$ boxes of pencils. Delivery is only arranged once an order reaches at least 12 boxes in total, so $x+y\ge 12$ .

Past sales show pencil boxes should never exceed twice the number of pen boxes, so $y\le 2x$ . Each box of pens costs RM8 and each box of pencils costs RM5, giving a total cost $C=8x+5y$ .

Find the minimum possible cost, and state how many boxes of each the supplier should order.

Show worked solution

Unlike a maximum profit over a closed shape, this region has no upper bound on $x+y$ , so start by finding where the two boundaries $x+y=12$ and $y=2x$ meet, that corner is the natural place to look for a minimum, since moving further out along either boundary can only add cost.

x+y=12,\; y=2x \;\Rightarrow\; x+2x=12,\; x=4,\; y=8

The line $x+y=12$ also meets the pure-pens edge $y=0$ at a second corner:

x+y=12,\; y=0 \;\Rightarrow\; x=12,\quad (12,0)

So the two finite corners of the region are $(4,8)$ and $(12,0)$ ; everywhere else the region runs off to infinity along $y=2x$ (increasing $x$ ) or along $y=0$ (increasing $x$ beyond 12). Evaluate the cost at the two corners, and check what happens along each direction.

\text{At }(4,8):\; C=8(4)+5(8)=32+40=72

\text{At }(12,0):\; C=8(12)+5(0)=96

\text{Along }y=2x\text{ for }x\ge 4:\; C=8x+5(2x)=18x,\text{ increasing in }x

\text{Along }y=0\text{ for }x\ge 12:\; C=8x,\text{ increasing in }x

Both directions only push the cost higher as $x$ grows, so neither corner is beaten by running further out; the minimum must sit at the cheaper of the two corners.

Answer

The minimum cost is $C=\text{RM}\,72$ , ordering $4$ boxes of pens and $8$ boxes of pencils. Moving instead to $(12,0)$ , all pens, no pencils, raises the cost to RM96, confirming $(4,8)$ is the cheaper corner.

Q5[6 marks]

A café's staff can prepare $x$ cups of tea and $y$ cups of coffee each hour, limited to $x+y\le 20$ cups. Milk stock limits production too: tea uses 2 units of milk per cup and coffee uses 1 unit, with at most 30 units available each hour, so $2x+y\le 30$ .

The kitchen can also heat enough water for at most 15 cups of tea an hour, so $x\le 15$ . The profit is $P=3x+2y$ ringgit.

(a) Show that the constraint $x\le 15$ does not actually change the feasible region. (b) Find the vertices of the region.

Show worked solution

(a) Combine the milk limit with the non-negativity condition $y\ge 0$ : since $y$ can never be negative, $2x$ can never exceed $2x+y$ , so the milk limit already forces $x\le 15$ on its own.

y\ge 0 \text{ and } 2x+y\le 30 \;\Rightarrow\; 2x\le 2x+y\le 30 \;\Rightarrow\; x\le 15

So the water-heating limit adds nothing new; the region is fully described by $x+y\le 20$ , $2x+y\le 30$ , $x\ge 0$ and $y\ge 0$ alone. (b) Find each vertex from these four boundaries.

x=0,\; y=0 \;\Rightarrow\; O(0,0)

2x+y=30,\; y=0 \;\Rightarrow\; x=15,\quad A(15,0)

(2x+y)-(x+y)=30-20 \;\Rightarrow\; x=10,\; y=10,\quad B(10,10)

x+y=20,\; x=0 \;\Rightarrow\; y=20,\quad C(0,20)

Check $C(0,20)$ against the milk limit: $2(0)+20=20\le 30$ , so it is genuinely a corner of the region. The four vertices are $O(0,0)$ , $A(15,0)$ , $B(10,10)$ and $C(0,20)$ .

\text{At }O:\;P=0,\quad\text{At }A:\;P=3(15)=45

\text{At }B:\;P=3(10)+2(10)=30+20=50,\quad\text{At }C:\;P=2(20)=40

Answer

The maximum hourly profit is $P=\text{RM}\,50$ , from $10$ cups of tea and $10$ cups of coffee. The water-heating limit $x\le 15$ never comes into it, always check whether a stated limit is actually active before leaning on it.

Q6[6 marks]

A tailor makes $x$ shirts and $y$ pairs of trousers each day, where $x\ge 1$ and $y\ge 1$ . Fabric limits the total number of garments to at most 9 a day, so $x+y\le 9$ .

Each shirt needs 2 buttons and each pair of trousers needs 1 button, and at most $m$ buttons are available each day, so $2x+y\le m$ , where $m$ is a positive constant. The profit is $P=4x+3y$ ringgit.

The maximum profit is achieved by making $4$ shirts and $5$ pairs of trousers, using all the fabric and all the buttons available that day. (a) Find the value of $m$ .

(b) Find the other vertices of the feasible region, and confirm that this plan really does give the maximum profit.

Show worked solution

(a) 'Using all the fabric and all the buttons' means both limits hold with equality at $(4,5)$ . Check the fabric first: $4+5=9$ , which matches $x+y\le 9$ exactly, as expected.

Substitute the point into the button equation to find $m$ .

2(4)+5=m \;\Rightarrow\; m=13

(b) With $m=13$ , the region's four boundaries are $x=1$ , $y=1$ , $x+y=9$ and $2x+y=13$ . Solve them in pairs for the remaining corners.

x=1,\; y=1 \;\Rightarrow\; (1,1)

y=1,\; 2x+y=13 \;\Rightarrow\; 2x=12,\; x=6,\quad (6,1)

Check $(6,1)$ against the fabric limit: $6+1=7\le 9$ , so it is a genuine corner.

x=1,\; x+y=9 \;\Rightarrow\; y=8,\quad (1,8)

Check $(1,8)$ against the button limit: $2(1)+8=10\le 13$ , also genuine. The four corners are $(1,1)$ , $(6,1)$ , $(4,5)$ and $(1,8)$ .

Evaluate $P=4x+3y$ at each to confirm the given plan wins.

P(1,1)=4+3=7,\quad P(6,1)=24+3=27

P(4,5)=16+15=31,\quad P(1,8)=4+24=28

Answer

The button stock is $m=13$ , and the maximum profit is $P=\text{RM}\,31$ from $4$ shirts and $5$ pairs of trousers, comfortably ahead of the next-best corner, $(1,8)$ , at RM28.

Q7[6 marks]

A gift shop packs $x$ Standard hampers and $y$ Deluxe hampers for a festival. Wrapping time limits the total to at most 20 hampers, so $x+y\le 20$ .

A corporate order requires at least 3 Standard hampers, so $x\ge 3$ . Stock rules also require at least 40% of the hampers packed to be Deluxe.

The profit is $P=6x+4y$ ringgit, since Standard earns RM6 and Deluxe earns RM4 per hamper. (a) Show that the 40% rule can be written as $y\ge \tfrac{2}{3}x$ .

(b) Find the vertices of the feasible region. (c) Find the maximum profit.

Show worked solution

(a) 'At least 40% Deluxe' means $y$ is at least 40% of the total number of hampers, $x+y$ .

y\ge 0.4(x+y)

Expand and collect the $y$ terms on one side.

y\ge 0.4x+0.4y \;\Rightarrow\; 0.6y\ge 0.4x \;\Rightarrow\; y\ge \tfrac{0.4}{0.6}x=\tfrac{2}{3}x

(b) The three boundaries are $x=3$ , $x+y=20$ and $y=\tfrac{2}{3}x$ (equivalently $3y=2x$ ). The non-negativity condition $y\ge 0$ never becomes active here, since $y\ge\tfrac{2}{3}x\ge 2$ whenever $x\ge 3$ .

Solve the three boundaries in pairs.

x=3,\; y=\tfrac{2}{3}(3)=2,\quad (3,2)

x=3,\; x+y=20 \;\Rightarrow\; y=17,\quad (3,17)

x+y=20,\; 3y=2x \;\Rightarrow\; 3y=2(20-y) \;\Rightarrow\; 5y=40,\; y=8,\; x=12,\quad (12,8)

The three vertices are $(3,2)$ , $(3,17)$ and $(12,8)$ . (c) Evaluate $P=6x+4y$ at each:

P(3,2)=18+8=26,\quad P(3,17)=18+68=86,\quad P(12,8)=72+32=104

Answer

The maximum profit is $P=\text{RM}\,104$ , from $12$ Standard and $8$ Deluxe hampers. Check the stock rule: $8$ out of $20$ hampers is exactly $40\%$ Deluxe, so the optimum sits right on that boundary, as it should.

Q8[7 marks]

A workshop assembles $x$ standard toolkits and $y$ deluxe toolkits each day, where $x$ and $y$ are whole numbers. Assembly time limits the total to at most 9 toolkits a day, so $x+y\le 9$ .

Screws limit production further: each standard toolkit uses 3 screws and each deluxe toolkit uses 5, with at most 30 screws available, so $3x+5y\le 30$ . The profit is $P=4x+5y$ ringgit.

Find the number of each toolkit that gives the maximum profit, and state that profit.

Show worked solution

First find the corners of the region in the usual way, treating $x$ and $y$ as if they could be any non-negative number.

x+y=9,\; y=0 \;\Rightarrow\; x=9,\quad (9,0)

3x+5y=30,\; x=0 \;\Rightarrow\; y=6,\quad (0,6)

Subtract three times $x+y=9$ from $3x+5y=30$ to find where the two slanted boundaries actually meet.

(3x+5y)-3(x+y)=30-27 \;\Rightarrow\; 2y=3,\; y=1.5,\; x=7.5,\quad (7.5,1.5)

Evaluate $P=4x+5y$ at all four corners, including the origin:

P(0,0)=0,\quad P(9,0)=36,\quad P(7.5,1.5)=30+7.5=37.5,\quad P(0,6)=30

The highest value, RM37.50, sits at $(7.5,1.5)$ , but toolkits come as whole units, so this corner cannot be built exactly. The true best plan must be a whole-number point close to it, so check the nearby possibilities directly.

(8,1):\; 3(8)+5(1)=29\le 30,\; 8+1=9\le 9 \;\Rightarrow\; \text{feasible},\; P=32+5=37

(7,1):\; 3(7)+5(1)=26\le 30 \;\Rightarrow\; \text{feasible},\; P=28+5=33

(6,2):\; 3(6)+5(2)=28\le 30 \;\Rightarrow\; \text{feasible},\; P=24+10=34

Among the whole-number points, $(8,1)$ gives the highest profit, better even than the whole-number corner $(9,0)$ , which gives only RM36.

Answer

The maximum profit with a whole number of toolkits is $P=\text{RM}\,37$ , from $8$ standard toolkits and $1$ deluxe toolkit. It falls just short of the RM37.50 found at $(7.5,1.5)$ , which is exactly what should happen once the answer is pulled back onto whole numbers.

Hard questions in this chapter rarely need harder arithmetic; they need clearer thinking about what a corner is, when several corners tie, and how the objective's coefficients steer the answer. Keep those three ideas in view and the marks follow.

Key method points

These three examples stretch the same core skill in three directions: careful modelling, spotting a shared maximum, and reasoning with an unknown coefficient. Keep the following in mind.

Model carefully: each resource limit becomes one $\le$ inequality, and each minimum requirement becomes one $\ge$ inequality.
A region bounded by four lines can have four corners; find each by solving the right pair of boundaries and checking it against the rest.
When two corners give the same objective value, the objective is parallel to the edge between them, and every point on that edge is optimal.
Rewriting an objective, for example $k=5x+5y=5(x+y)$ , can reveal at a glance which constraint it runs parallel to.
With an unknown coefficient, compare the target vertex's value against every other and combine the resulting inequalities; the strictest one gives the range.
Always confirm the winning corner obeys every constraint, and give whole-number answers when the quantities are physical counts.

How a teacher helps

Hard Linear Programming questions reward a calm, orderly hand more than raw speed. Students who lose marks usually rush the comparison at the end, declaring a winner before checking the near-ties, or missing that two corners are level.

In a one-to-one lesson our teacher builds the habit of laying every corner's value in a row and reading them side by side, so a tie or a parallel edge is spotted rather than overlooked. Because our teachers are experienced, you learn to defend each step.

Lessons are taught in English, while SPM papers are set in both Malay and English, so the notation reads the same to you either way.

Get 1-to-1 help.

Book a Trial Class

Frequently asked questions

What does it mean when two corners give the same maximum?

It means the objective line is parallel to the edge joining those two corners, so every point along that edge gives the same optimal value. You may report either corner, or note that the whole edge is optimal; the value is what the mark depends on.

How do I handle an objective with an unknown coefficient?

Write the objective's value at each vertex, leaving the unknown in place. To keep the maximum at a chosen vertex, that vertex's value must be at least every other's; solve each comparison and take the strictest inequality as your range.

My region has four sides. How many corners should I expect?

A convex region bounded by four lines usually has four corners, one at each pair of adjacent boundaries. Find them by solving the correct pairs, and discard any intersection that breaks a constraint, it lies outside the region.

Do hard questions need harder calculation?

Rarely. The numbers stay clean by design.

What is harder is the reasoning, proving a corner belongs to the region, noticing a tie, or tracking how a coefficient changes the winner. Neat, labelled working is what protects the method marks.

Source:SRC-DSKP-EN

Written by the spmaddmath.com.my editorial team.· Last updated 5 September 2026

Linear Programming, Worked Examples (KBAT)

What these examples cover

Worked examples

Key method points

How a teacher helps

Frequently asked questions

Ready to get started?