Skip to content

Mathematics · Ch 13 — Linear Programming

Graphical Method of Solution

3

Graphical Method of Solution

Once an LPP has been formulated with exactly two decision variables, it can be solved by an exact geometric procedure, because every linear constraint corresponds to a straight line dividing the coordinate plane into two half-planes, and the set of points satisfying ALL the constraints at once is simply the region common to all of these half-planes (intersected with the first quadrant, from x≥0, y≥0x\ge0,\ y\ge0).

Step 1 -- Plot each constraint's boundary line. For a constraint such as px+qy≤Hpx+qy\le H, first replace the inequality by the equality px+qy=Hpx+qy=H and plot this straight line, most easily by finding its two intercepts: setting y=0y=0 gives the xx-intercept x=H/px=H/p, and setting x=0x=0 gives the yy-intercept y=H/qy=H/q. The actual constraint px+qy≤Hpx+qy\le H includes this boundary line itself (since the inequality is not strict), so the line is drawn as a solid line, not a dashed one.

Step 2 -- Decide which half-plane satisfies the inequality. Every straight line divides the plane into two half-planes, and exactly one of them (together with the line itself) satisfies a given ≤\le or ≥\ge inequality. The standard way to decide which is to substitute a convenient test point not on the line -- the origin (0,0)(0,0) is used whenever the line does not pass through it, since substituting x=0,y=0x=0,y=0 is the simplest possible check. If the test point satisfies the inequality, the half-plane containing that test point is the one required; if not, the OTHER half-plane is required. (If the boundary line happens to pass through the origin, any other convenient point not on the line, such as (1,0)(1,0) or (0,1)(0,1), is used instead.)

Step 3 -- Shade the region common to every constraint. Repeating Steps 1--2 for every constraint (including x≥0x\ge0, the region to the right of the yy-axis, and y≥0y\ge0, the region above the xx-axis) and shading only the region that lies within EVERY required half-plane simultaneously gives the feasible region: the set of every point (x,y)(x,y) that satisfies all the constraints of the LPP at once, drawn as a single shaded polygon in the first quadrant (or, for an unbounded region, an open shaded area, Section 4). …

Figure 1Graphical method: constraint lines and the shaded feasible region

What this figure shows. A first-quadrant coordinate grid (x-axis and y-axis only, since x, y >= 0 throughout this chapter) shows two straight boundary lines drawn from their x- and y-intercepts, each labelled with its equation (e.g. one line labelled 'x + 2y = 10' running from a marked point on the x-axis to a marked point on the y-axis, and a second line labelled '3x + y = 15' similarly drawn between its own two intercepts). The region common to both 'less than or equal to' half-planes, together with the first quadrant, is shaded in a single flat shading colour, producing a closed polygon with the origin as one of its corners. Each corner point of this shaded polygon is marked with a solid dot and labelled with its coordinates (e.g. O(0,0), a point on the x-axis, the intersection point of the two lines, and a point on the y-axis). A short arrow or note near one boundary line indicates the test-point check used to decide which side of that line is shaded (typically an arrow point …