Linear programming: the best plan in a feasible region – Simultaneous Linear Inequalities (Senior 3 Mathematics) | Ganzaa

Simultaneous Linear Inequalities

Lessons

Senior 3 · Mathematics

Simultaneous Linear Inequalities

4 lessons

Lesson 4 of 4

Linear programming: the best plan in a feasible region

25 min

Baskets or mats?

A weaving cooperative in Gisagara makes two products: baskets and table mats. Each week the members have a fixed number of weaving hours and a fixed stock of dyed sisal, and they want to earn as much as possible. Making more baskets means making fewer mats. How many of each should they make?

Questions like this are called linear programming problems. Every condition is a linear inequality, so the possible plans form a feasible region, which you learned to draw in Lesson 3. The best plan is then found at one of its corners.

Definition

Linear programming: a method for finding the largest or smallest value of a linear expression when the unknowns must satisfy a system of linear inequalities.

The decision variables are the unknowns you choose, such as $x$ baskets and $y$ mats.
The constraints are the inequalities they must satisfy, including $x \ge 0$ and $y \ge 0$ .
The objective function is the quantity to maximise (profit) or minimise (cost), such as $P = 3000 x + 4000 y$ .
An optimal solution is a point of the feasible region that gives the best value of the objective function.

Important

The corner-point rule. If a linear programming problem has an optimal solution, then one is found at a vertex (corner) of the feasible region.

Why: all the points with the same profit, $3000 x + 4000 y = k$ , lie on a straight line. Changing $k$ moves this line parallel to itself. Slide it across the region in the direction that increases $k$ : the last point of the region it touches, just before it leaves, is a corner (or a whole edge, which includes corners).

Solving a linear programming problem

Name the decision variables and state what each one counts.
Write every condition as an inequality; add $x \ge 0$ and $y \ge 0$ when the variables count things.
Write the objective function.
Draw the feasible region and find the coordinates of every vertex by solving pairs of boundary equations.
Work out the objective at each vertex and choose the largest (or smallest).
Answer the question in words, with units.

Worked example 1: the cooperative's best week

A basket takes 2 hours to weave and a mat takes 3 hours; the members have 60 hours in a week. Each item uses one bundle of dyed sisal, and 25 bundles are in stock. A hotel has ordered at least 5 mats. The profit is 3,000 Frw on a basket and 4,000 Frw on a mat. How many of each should they make to earn the greatest profit? (All figures are illustrative.)

Solution Let $x$ be the number of baskets and $y$ the number of mats.

Condition	Inequality
Weaving time	$2x + 3y \le 60$
Sisal bundles	$x + y \le 25$
The hotel order	$y \ge 5$
Numbers of items	$x \ge 0$

Maximise $P = 3000 x + 4000 y$ .

x = number of baskets, y = number of mats. The green region is the set of possible weekly plans. The dashed line joins all the plans that earn 60,000 Frw.

Vertex C is where $2 x + 3 y = 60$ meets $x + y = 25$ . From the second, $x = 25 - y$ ; substitute: $50 - 2 y + 3 y = 60$ , so $y = 10$ and $x = 15$ . The other vertices come from the axes and $y = 5$ : for D, $x + 5 = 25$ gives $x = 20$ , and $2(20) + 3(5) = 55 \le 60$ ✓.

Vertex	$x$	$y$	Value of the objective
A	$0$	$5$	$3000(0) + 4000(5) = 20\,000$
B	$0$	$20$	$80\,000$
C	$15$	$10$	$45\,000 + 40\,000 = 85\,000$
D	$20$	$5$	$60\,000 + 20\,000 = 80\,000$

The greatest profit is 85,000 Frw, at C. The cooperative should weave 15 baskets and 10 mats a week. It then uses all 60 hours and all 25 bundles.

Worked example 2: the cheapest feed mix

A dairy farmer in Nyagatare mixes two feeds for a calf. Each kilogram of feed A gives 2 units of protein and 1 unit of energy; each kilogram of feed B gives 1 unit of protein and 2 units of energy. The calf needs at least 8 units of protein and 10 units of energy a day. Feed A costs 300 Frw per kg and feed B costs 400 Frw per kg. Find the cheapest daily mix. (Illustrative figures.)

Solution Let $x$ kg of A and $y$ kg of B be used. Minimise $C = 300 x + 400 y$ subject to

2x + y \ge 8, \qquad x + 2y \ge 10, \qquad x \ge 0, \qquad y \ge 0.

x = kg of feed A, y = kg of feed B. This region is unbounded: it goes on for ever up and to the right, so there is no greatest cost, only a least one.

Vertex Q: from $2 x + y = 8$ , $y = 8 - 2 x$ ; then $x + 16 - 4 x = 10$ , so $x = 2$ and $y = 4$ .

Vertex	$x$	$y$	Value of the objective
P	$0$	$8$	$300 (0) + 400 (8) = 3200$
Q	$2$	$4$	$600 + 1600 = 2200$
R	$10$	$0$	$3000$

The cheapest mix is 2 kg of feed A and 4 kg of feed B, costing 2,200 Frw a day. The dashed line $300 x + 400 y = 2200$ touches the region only at Q, which confirms it.

Warning

Check every vertex against every constraint. Where two boundary lines cross outside the region, that point is not a vertex. In Worked example 1, $2 x + 3 y = 60$ meets $y = 5$ at $(22.5, 5)$ , but $22.5 + 5 = 27.5 > 25$ breaks the sisal limit, so it is not a possible plan.

Whole numbers. You cannot weave half a basket. If the best vertex has fractions, test the whole-number points inside the region near it.

Tip

A vertex table earns the marks. List every vertex with its coordinates and the value of the objective, then state the answer in words: "15 baskets and 10 mats, profit 85,000 Frw". Examiners look for the table and the sentence.

Joshua Emmanuel: Linear Programming 1, maximisation at the corner points. Watch how the problem is written as variables, constraints and an objective, how the feasible region is drawn, and how each corner point is tested.

✦

Practice

Draw the feasible region for each problem. The last three are harder.

Find the greatest value of $P = 2 x + 5 y$ subject to $x \ge 0$ , $y \ge 0$ , $x + y \le 6$ , $y \le 4$ .
Find the least value of $C = 4 x + 3 y$ subject to $x + y \ge 5$ , $x \ge 1$ , $y \ge 1$ , $x \le 6$ , $y \le 6$ .
Maximise $P = 3 x + 2 y$ subject to $x \ge 0$ , $y \ge 0$ , $x + 2y \le 10$ , $3x + y \le 15$ .
A tailor in Kigali makes shirts and dresses. A shirt needs 2 m of cloth and a dress 3 m; she has 24 m. She can sew at most 10 items a week. Profit: 2,000 Frw per shirt and 5,000 Frw per dress. Write the constraints and the objective.
Solve the tailor's problem in question 4.
A school hires minibuses (30 seats, 60,000 Frw a day) and cars (5 seats, 15,000 Frw a day) to carry at least 150 people. At most 6 minibuses and at least 1 car are available. Show that 5 minibuses and 1 car is a possible plan, and find its cost.
In question 1, a pupil says the greatest value is at $(6, 0)$ because $x$ can be as large as 6 there. Explain the mistake.

Show answersHide answers

Vertices $(0, 0)$ , $(6, 0)$ , $(2, 4)$ , $(0, 4)$ ; $P$ is 0, 12, 24, 20. Greatest $P = 24$ at $(2, 4)$ .
Vertices $(4, 1)$ , $(6, 1)$ , $(6, 6)$ , $(1, 6)$ , $(1, 4)$ ; $C$ is 19, 27, 42, 22, 16. Least $C = 16$ at $(1, 4)$ .
Vertices $(0, 0)$ , $(5, 0)$ , $(4, 3)$ , $(0, 5)$ ; $P$ is 0, 15, 18, 10. Greatest $P = 18$ at $(4, 3)$ .
Let $x$ shirts and $y$ dresses: $2x + 3y \le 24$ , $x + y \le 10$ , $x \ge 0$ , $y \ge 0$ . Maximise $P = 2000 x + 5000 y$ .
Vertices $(0, 0)$ , $(10, 0)$ , $(6, 4)$ , $(0, 8)$ ; $P$ is 0, 20,000, 32,000, 40,000 Frw. Best: 8 dresses and no shirts, 40,000 Frw.
Seats: $30(5) + 5(1) = 155 \ge 150$ ✓; 5 minibuses $\le 6$ ✓; 1 car $\ge 1$ ✓. Cost: $5(60\,000) + 15\,000 = 315\,000$ Frw.
The objective depends on both $x$ and $y$ , not on $x$ alone. At $(6, 0)$ , $P = 12$ , but at $(2, 4)$ , $P = 24$ . Every vertex must be tested.

1Baskets or mats?

2Solving a linear programming problem

Baskets or mats?

Solving a linear programming problem