D1 5.2 - Solving linear programs graphically
A feasible-region diagram turns a two-variable optimisation problem into geometry. You will use vertices and parallel objective lines, find genuine integer optima, and distinguish finite, multiple and unbounded solutions (D1 5.2).
The region contains every permitted choice
A continuous model gives an optimum at . If the decisions must be integers, is rounding both coordinates down to guaranteed to give the best plan?
It is tempting to treat rounding as the final step. We will see a case where that rounded plan is feasible but loses profit to another integer plan. First make clear which points the model permits.
You already know
From formulation, define the variables and their domains, keep every constraint, and distinguish the objective from the restrictions. An inequality's boundary is found by replacing its sign with equality; a point is feasible only if it satisfies all conditions simultaneously.
Identify all permitted points before deciding which of them gives the best objective value.
Feasible region and feasible solution
The feasible region is the set of points satisfying every constraint, including non-negativity. A feasible solution is one such point. An optimal solution is a feasible solution with the best objective value. If integers are required, only the integer-coordinate points in the region are permitted.
For example, the continuous region
lies in the first quadrant and on the permitted side of both boundary lines. Use an off-boundary test point to decide which side to keep; the origin satisfies both inequalities here. Plot the complete intersection, rather than shading the permitted side of only one constraint.
The boundaries meet where and , giving . The axis intersections completing the region are and , together with the origin.
Key idea
The constraints determine the feasible region. Changing only the objective changes which feasible point is best, without moving the region's boundaries.
Check all inequalities, not merely whether a point looks close to the shaded region.
Find the last contact with an objective line
A linear objective has parallel level lines; slide one in the improving direction until it last touches the feasible region.
For , with , the line has equation , so every level has gradient . If and , the objective lines are vertical, ; do not divide by zero. A horizontal line arises when , .
Vertex and objective-line methods
For a non-empty bounded feasible polygon and a linear objective, a maximum and a minimum occur at vertices. Evaluate the objective at all vertices, or move a parallel objective line to its final feasible contact in the required direction.
If an objective line coincides with an optimal edge, every point of that edge is optimal. These geometric optimisation rules and their objective-line interpretation are not supplied as booklet formulae.
Not in the formula booklet: learn it.
Calculate intersections exactly even if you read their approximate location from a graph. A sketch identifies candidates; simultaneous equations provide the coordinates needed for an exact optimum.
Worked example 1: an optimum where two boundaries meet
Question. Maximise , subject to , , , allowing continuous values.
Plan. Find the polygon's vertices and compare their objective values; check the result with an objective line.
| Vertex | |
|---|---|
The objective line has gradient . Sliding it towards increasing gives its final contact at the intersection of the two sloping boundaries.
Why this step? Testing only the axis vertices would miss , which exceeds both axis objective values.
Answer. The maximum is , at .
Check. Both capacity constraints hold with equality, and . The exact vertex comparison agrees with the objective-line contact.
Worked example 2 changes only the coefficient of in the objective, from to . The feasible region is unchanged, but its best point moves.
Worked example 2: rotating the objective line
Question. For the same continuous feasible region, maximise .
Plan. Keep the same vertices, change the objective-line gradient and recalculate the four values.
| Vertex | |
|---|---|
Why this step? Increasing the reward for rotates the objective line. Its last contact is now the top axis vertex rather than the two-boundary intersection.
Answer. The maximum is , at .
Check. This point satisfies and . It has the largest of all four values, not just a better value than one neighbour.
For minimisation, use the same vertex table and select the smallest value, or slide the objective line in the direction of decreasing value. You do not reverse the constraints when changing from maximisation to minimisation.
Watch out
Wrong: keep the old optimum automatically after the objective changes, or use a rounded intersection in an exact calculation. Right: retain the same feasible vertices but compare the new objective at every one, using exact coordinates.
Increase only the reward for again.
Integer optima require a justified search
The continuous optimum bounds the integer problem, but rounding its coordinates does not solve the integer problem.
For the opening objective , rounding down gives feasible with value . Rounding up to gives , which is infeasible. Even a feasible rounded point still needs comparison with the other permitted integer points.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account