Linear Programming: Build the Feasible Region and Test the Vertices

Linear programming turns a word problem into a collection of allowed choices and a quantity to maximise or minimise. A feasible point satisfies every constraint simultaneously. A point can look attractive for profit and still be impossible because it uses too much of one resource. Establish feasibility before comparing objective values.

These linear programming worked examples use invented classroom production figures. Prices, capacities and predicted returns are assumptions for the questions, not current market information or business advice. The distinction matters: the mathematical optimum answers the stated model, which may omit uncertainty, unsold stock and other real-world costs.

Subject references: OpenStax: Linear programming; OpenStax: Graphing systems of linear inequalities. These support the concepts; the questions, datasets, calculations and diagrams here are original.

Worked analysis 1: translate a small-production model

A school craft group prepares two types of display pack for a fictional event. Let x be the number of standard packs and y the number of deluxe packs completed in one session. The table gives the resource use and the assumed contribution after variable costs. Each pack must be complete.

There is also capacity for no more than seven standard packs. Card use is 2x + y, so the first constraint is 2x + y ≤ 18. Assembly use is x + 2y, giving x + 2y ≤ 18. The other restrictions are x ≤ 7, x ≥ 0, y ≥ 0, with x and y integers for completed packs. The objective is P = 80x + 110y, measured in Kenyan shillings.

“Available” provides an upper limit, not a requirement to use every unit. Replacing both inequalities by equalities immediately would discard possible plans without justification. The objective coefficients are the supplied contributions, whereas the constraint coefficients describe resource use; interchanging the two produces a different model.

Draw the allowed overlap, then calculate its corners

Temporarily allow nonnegative real values to draw the continuous feasible region. The boundary 2x + y = 18 passes through (0, 18) and (9, 0). The boundary x + 2y = 18 passes through (0, 9) and (18, 0). Draw x = 7 as a vertical boundary and use solid lines because equality is allowed.

Testing (0, 0) in each resource inequality gives a true statement, so retain the side containing the origin for those two lines. Retain the left side of x = 7 and the first quadrant. Only their common overlap is feasible. Shade the allowed overlap clearly and label what the shading means; do not leave the reader guessing whether shading represents accepted or rejected points.

The shaded polygon has vertices (0, 0), (7, 0), (7, 4), (6, 6) and (0, 9), in boundary order. Its top-right edges lie on 2x + y = 18 and x + 2y = 18. The full graph includes both resource lines, x = 7, labelled axes and all five vertices. These coordinates and equations completely define the diagram.

At the crossing of the resource lines, subtract x + 2y = 18 from twice the first equation, 4x + 2y = 36. This gives 3x = 18, so x = 6 and y = 6. Where x = 7 meets the card boundary, y = 4. The point where x = 7 meets the assembly boundary is (7, 5.5), but it needs 19.5 card units and is outside the feasible region. Not every pair of boundary lines creates a feasible vertex.

Worked analysis 2: verify vertices and compare the objective

All listed coordinates also satisfy x ≤ 7 and nonnegativity. For a linear objective on this nonempty, closed, bounded polygon, an optimum occurs at a vertex. Comparing all five gives the maximum at six standard and six deluxe packs, with contribution KSh 1,140. The point is integral, so it is also an allowed completed-pack plan.

This plan uses both resources fully but leaves capacity for one additional standard pack unused. That spare capacity is not a mistake: the other resources prevent its use. Choosing only deluxe packs because KSh 110 exceeds KSh 80 would yield KSh 990. A larger contribution per item alone does not account for the combination of resource requirements.

Vertex testing works here because of the stated continuous linear model and its bounded feasible polygon. An empty region has no feasible answer. An unbounded region requires separate analysis; it does not automatically mean that every objective is unbounded. The whole-number restriction also needs its own check.

Worked analysis 3: a fractional vertex cannot be rounded blindly

Consider a second independent workshop model: whole-number items x and y satisfy 3x + 2y ≤ 16, x + 2y ≤ 11 and x, y ≥ 0. Maximise S = 4x + 5y contribution units. The continuous vertices are (0, 0), (16/3, 0), (5/2, 17/4) and (0, 11/2).

The objective values are 0, 64/3, 125/4 and 55/2 respectively. Thus the continuous maximum is 31.25 at (2.5, 4.25). This point cannot represent complete items. Rounding to (3, 4) uses 17 units in the first constraint and is infeasible. Rounding down to (2, 4) gives 28, but it is not the best integer solution.

Because x cannot exceed 5, test each possible integer x and choose its largest allowable integer y. This is exhaustive here because the coefficient of y in the objective is positive: for fixed x, increasing an allowed y improves S.

The integer optimum is x = 1, y = 5, giving S = 29. It satisfies 3 + 10 = 13 ≤ 16 and 1 + 10 = 11. The continuous maximum remains a useful upper bound, but nearby rounding is not a proof of the best whole-number choice.

Three solved practice tasks

Practice 1: feasibility comes before contribution

For the display-pack model, compare plans (7, 4) and (7, 5). The first uses 18 card and 15 assembly units, so it is feasible and yields KSh 1,000. The second uses 19 card units, exceeding 18. Its apparent KSh 1,110 contribution is irrelevant because that plan cannot be produced under the model.

Practice 2: recognise more than one optimal point

Keep the display-pack constraints but change the objective to P = 100x + 50y. Vertex values are 0, 700, 900, 900 and 450. The maximum is KSh 900 at both (7, 4) and (6, 6). In the continuous model, every point on the joining edge is optimal because P = 50(2x + y) = 900 there. For complete packs, those two endpoints are the only integer points on that short edge.

Practice 3: minimise rather than maximise

For nonnegative x and y, minimise C = 30x + 20y subject to x + y ≥ 6 and 2x + y ≥ 8. The lower boundary vertices are (0, 8), (2, 4) and (6, 0). Their costs are 160, 140 and 180. Increasing either variable along the unbounded outer directions increases cost, so the minimum is C = 140 at (2, 4). Both requirement inequalities are equalities there.

Frequently asked questions

What makes a point feasible?

It satisfies every constraint at the same time, including nonnegativity and any whole-number restriction. Satisfying only the resource with the largest numerical limit is insufficient.

Why are the boundary lines solid here?

The inequalities allow equality. Points on the relevant boundary can therefore be feasible, provided they also satisfy all the other constraints.

Is every boundary-line intersection a vertex of the feasible region?

No. An intersection may violate another constraint. Substitute each candidate into every inequality before retaining it in the vertex table.

Why check vertices for the continuous model?

For a linear objective on a nonempty closed bounded polygon, a maximum and minimum occur at vertices. More than one point can tie, including an entire edge.

Does the highest return per item identify the best product mix?

No. Products can consume different amounts of limited resources. Compare feasible combinations through the full objective rather than the unit return alone.

Can I round a fractional optimum to whole items?

Not without further checking. Rounding can make a point infeasible or miss a better integer point. The second worked model demonstrates both problems.

Does an unbounded region always mean no minimum?

No. The answer depends on the objective and directions in which the region extends. The minimisation practice task has an unbounded region but a finite minimum.

Continue with targeted practice

Use the existing Mathematics topical revision collection to find further resources. Some contents may require membership. This link does not promise a specific downloadable file or an official answer key for this lesson.