Model Solution
The Graphical Method
—Determining the Feasible Region—
LP problems are solved analytically (algebraically). However, in the special case where only two decision variables are involved, we can take advantage of Cartesian coordinate (analytic) geometry to literally visualize the problem. This allows for easier comprehension of the underlying concepts of LP. (René Descartes devised coordinate geometry in 1637, a powerful and elegant representational method that linked geometry and algebra, until then two separate realms of mathematics. It is somewhat ironic that it was Descartes himself who separated the mind from the body with his philosophy of dualism. Pierre de Fermat also devised coordinate geometry independently.)
Each decision variable constitutes a distinct dimension of the problem. A dimension is a clearly definable property of a system that can be measured. The solution space for a two-dimensional problem can be portrayed by means of the Cartesian plane. One can then see where the optimal solution lies. The graph also serves to explain the rationale sustaining sensitivity analysis, as we shall see.
To solve the LP model:
we plot each part of the model from the bottom up.
Part 1. Nonnegativity constraints
First we trace the nonnegativity constraints. The first constraint states that the values assumed by the variable x must be zero or greater. The second constraint requires the same for variable y. In Cartesian geometry, x and y are represented by the axes of the coordinate system, which must be orthogonal (perpendicular to each other). Since both variables are constrained to nonnegative values, the solution space is limited to the first (upper right) quadrant.
Part 2. Structural constraints
Next we plot the structural constraints. Recall that the standard form of the linear equation (in the plane) is:
ax + by = c
where a , b , c are constants ( a , b not both zero). The slope-intercept form of the linear equation is:
y = mx + B
where m is the slope of the line and B is the y -axis intercept. Both forms of the linear equation encode the same information, though. (For a refresher on linear equations, visit Prof. Gary Hart’s Website.) Solving the standard linear equation for y, we obtain the slope of the line:
m = - a / b, (b ? 0)
and the y -intercept:
B = c / b, (b ? 0).
LP models make use of the standard form of the linear equation. The above formulas allow us to determine slopes and y -intercepts in standard form equations.
Now, our constraints are actually linear inequalities. To graph a linear inequality, first plot its equality component (a line) and then select the appropriate half-plane. For the large-block inequality constraint
2x + y = 6
the corresponding equation is 2x + y = 6. We can plot this line if we find any two points whose coordinates satisfy the equation. The easiest points to find are the axes intercepts. We already know that the y -intercept is c / b. Thus since b = 1 and c = 6, the y -intercept is 6 / 1 = 6, which is the point’s ordinate. Its abscissa is, of course, zero because the point lies on the y -axis (where x = 0). Thus, our first point is (0, 6).
To find the second point, go for the x -intercept, which is given by c / a, (a ? 0). Since the ordinate here is zero (the point lies on the x -axis, where y = 0), the point’s coordinates are (3, 0). We’ve got the two points, so we can trace the line:
We now select the half-plane specified by the original inequality: 2x + y = 6. Clearly, there are only two possibilities: the lower-left triangle and the upper-right unbounded region. One can always determine which half-plane is specified by choosing a point not on the line and checking if its coordinates satisfy the inequality. If they do, the point lies on the required half-plane; if they don’t, then the other half-plane is the one specified. A good check point here is the origin (0, 0). Since the coordinate values satisfy the inequality, the lower-left triangle is the half-plane specified by the constraint. (This half-plane is reduced to a triangle because the nonnegativity constraints apply.)
Comment: Economic interpretation
The light-blue triangle represents the region where production is feasible relative to the large-block availability constraint. The coordinates of any point within the triangle, edges included, represent combinations of tables and chairs (x and y ) that can be produced given the amount of large blocks available. Points outside the triangle are infeasible and thus not candidates for solution. We see here how LP goes about in finding a solution: it first removes from consideration all points (production mixes) that are not feasible.
Note: Rational numbers assumed
Not all of the points in the triangle have integer coordinates. As we shall see when we discuss the LP assumptions, in order for the algorithm to work properly, the decision variables must be allowed to assume non-integer values. Although one would be hard pressed to assemble a marketable fractional chair in the real world, we will accept fractional solutions in principle. The discussion on Integer Programming will deal with the practical issues concerning integer solutions.
We have plotted the first structural constraint. The procedure must be repeated to plot the second, small-block constraint: 2x + 2y = 8. Here the axes intercepts are (4, 0) and (0, 4), and the required half-plane is again to the lower left of the line. This new triangle denotes the feasible region with respect to the small-block constraint. But in order to assemble tables and chairs in the real world, both constraints must be met simultaneously. This means that the feasible region for the overall problem is the area where both triangles intersect (the light blue quadrilateral shown below). The feasible region is the mathematical space that contains all possible solution alternatives —optimal and sub-optimal— to the LP problem. The alternatives are feasible because all applicable constraints are simultaneously satisfied.
Note that feasibility says nothing about optimality. Plotting constraints (structural as well as nonnegativity) only shows the set of solution alternatives where the decision will be made. Feasible regions cannot yield the optimal solution until the objective function is plotted. This is because the optimality criterion is provided by the information encoded in the objective function. We take this up next.
continued
Analytic
Analytic Geometry
Cartesian
Cartesian Coordinates
Cartesian Geometry
Cartesian Plane
Dimension
Line
Linear Equation
Plane
Half-Plane
Abscissa
Ordinate
Orthogonal
Quadrant
Slope
Intercept
Origin
x-Axis
y-Axis
Analytic Geometry
Cartesian Coordinate System
Dimension
Line
Linear Equation
Plane
Point Plotting
Equations of the Straight Line (applet)
Lines and Linear Equations
