Mathematics · Ch 13 — Linear Programming
Graphical Method of Solution
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 ).
Step 1 -- Plot each constraint's boundary line. For a constraint such as , first replace the inequality by the equality and plot this straight line, most easily by finding its two intercepts: setting gives the -intercept , and setting gives the -intercept . The actual constraint 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 or inequality. The standard way to decide which is to substitute a convenient test point not on the line -- the origin is used whenever the line does not pass through it, since substituting 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 or , is used instead.)
Step 3 -- Shade the region common to every constraint. Repeating Steps 1--2 for every constraint (including , the region to the right of the -axis, and , the region above the -axis) and shading only the region that lies within EVERY required half-plane simultaneously gives the feasible region: the set of every point 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). …
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 …