D1 5.2, D1 5.3 - Solving linear programs

Feasible regions

What if the most profitable point on a graph calls for $2.8$ drums of one product and $3.6$ of another? The graph can solve a continuous model exactly, but a whole-drum requirement changes which points we may choose. First we need to know which plans satisfy the restrictions at all.

The feasible region consists of points satisfying every constraint together. Draw each boundary as an equality, then test which side satisfies its inequality. For $x+y\le8$, the point $(0,0)$ gives $0\le8$, so choose the side containing the origin. If the test point lies on a boundary, choose a different point: equality cannot distinguish the two sides.

Nonnegativity $x\ge0,y\ge0$ restricts us to the first quadrant, including its axes. Non-strict inequalities include the boundary lines; draw them solid. State your shading convention clearly. The diagram below colours the feasible region green; an exam diagram may instead shade excluded regions and leave the feasible region unshaded.

[DIAGRAM: asset_name: A two-variable feasible polygon; asset_slug: linear-feasible-region; caption: The green polygon includes its boundaries and satisfies every inequality.; description: First-quadrant feasible polygon for x+y at most8 and2x+y at most10, with vertices(0,0),(5,0),(2,6),(0,8), both sloping boundaries labelled and solid.]

Change only the second resource limit from $10$ to $12$. The permitted side remains the same, but the vertices move.

Use the equations, rather than a graph reading alone, when exact coordinates are needed.

Vertex and objective-line methods

A linear objective changes at a constant rate, so a straight-edged feasible region allows two equivalent optimisation methods.

For a nonempty bounded polygon, a maximum and minimum occur at vertices. Evaluate the objective at all its vertices and compare. If the objective is constant along an edge at the optimal value, every point on that edge is also optimal; the optimum need not be unique.

The ruler method, or objective-line method, uses the family

For fixed $a,b$, these lines are parallel as $k$ changes. Draw a convenient line, then slide a ruler parallel to it in the direction of increasing $k$ for a maximum, or decreasing $k$ for a minimum. The last feasible contact gives the optimum. Check the direction with a test point: moving away from the origin is not a universal rule when objective coefficients have different signs. With $b\ne0$, the gradient is $-a/b$; a zero coefficient may give horizontal or vertical lines instead.

[DIAGRAM: asset_name: Parallel profit lines; asset_slug: linear-objective-lines; caption: Parallel objective lines increase until their last feasible contact at (2, 6).; description: The original polygon with vertices(0,0),(5,0),(2,6),(0,8), dashed line3x+2y=12 and parallel line3x+2y=18 touching(2,6). An arrow to the upper right indicates increasing objective.]

Change only the objective to $Q=2x+y$. It is now parallel to one of the feasible edges.

A graph locates the optimal corner or edge; simultaneous equations give exact coordinates where required. If a region is unbounded, check whether the objective can improve without limit before claiming a finite optimum.

Integer feasible points

When variables count whole objects, only lattice points with integer coordinates are allowed, even if a fractional point is the continuous optimum.

Consider

and maximise $P=4x+5y$. The sloping boundaries intersect at

where $P=29.2$. Rounding both coordinates gives $(3,4)$, which breaks both constraints. Rounding both down gives a feasible point $(2,3)$, but its value $23$ is not best. Neither rounding rule solves an integer optimisation problem.