To find the optimal solution to an LP problem, we must first identify a set, or region, of feasible solutions. The first step in doing so is to plot each of the problem’s constraints on a graph. The variable T (tables) is plotted as the horizontal axis of the graph, and the variable C (chairs) is plotted as the vertical axis. The notation $\left(T,C\right)$ is used to identify the points on the graph. The nonnegativity constraints mean that we are always working in the first (or northeast) quadrant of a graph (see Figure 7.1).

Figure 7.1 Quadrant Containing All Positive Values

To represent the first constraint graphically, $4T+3C\le 240,$ we must first graph the equality portion of this, which is

As you may recall from elementary algebra, a linear equation in two variables is a straight line. The easiest way to plot the line is to find any two points that satisfy the equation and then draw a straight line through them.

The two easiest points to find are generally the points at which the line intersects the T and C axes.

When Flair Furniture produces no tables—namely, T = 0—it implies that

or

or

In other words, if all of the carpentry time available is used to produce chairs, 80 chairs could be made. Thus, this constraint equation crosses the vertical axis at 80.

To find the point at which the line crosses the horizontal axis, we assume that the firm makes no chairs; that is, $C=0.$ Then

or

or

Hence, when $C=0,$ we see that $4T=240$ and that $T=60.$

The carpentry constraint is illustrated in Figure 7.2. It is bounded by the line running from point $\left(T=0,C=80\right)$ to point $\left(T=60,C=0\right).$

Recall, however, that the actual carpentry constraint was the inequality $4T+3C\le 240.$ How can we identify all of the solution points that satisfy this constraint? It turns out that there are three possibilities. First, we know that any point that lies on the line $4T+3C=240$ satisfies the constraint. Any combination of tables and chairs on the line will use up all 240 hours of carpentry time.2 Now we must find the set of solution points that would use less than the 240 hours. The points that satisfy the $<$ portion of the constraint (i.e., $4T+3C<240$) will be all the points on one side of the line, while all the points on the other side of the line will not satisfy this condition. To determine which side of the line this is, simply choose any point on either side of the constraint line shown in Figure 7.2 and check to see if it satisfies this condition. For example, choose the point (30, 20), as illustrated in Figure 7.3:

Since $180<240,$ this point satisfies the constraint, and all points on this side of the line will also satisfy the constraint. This set of points is indicated by the shaded region in Figure 7.3.

To see what would happen if the point did not satisfy the constraint, select a point on the other side of the line, such as (70, 40). This constraint would not be met at this point as

Since $400>240,$ this point and every other point on that side of the line would not satisfy this constraint. Thus, the solution represented by the point $\left(70,40\right)$ would require more than the 240 hours that are available. There are not enough carpentry hours to produce 70 tables and 40 chairs.

Next, let us identify the solution corresponding to the second constraint, which limits the time available in the painting and varnishing department. That constraint was given as $2T+1C\le 100.$ As before, we start by graphing the equality portion of this constraint, which is

To find two points on the line, select $T=0$ and solve for C:

So one point on the line is $\left(0,100\right).$ To find the second point, select $C=0$ and solve for T:

The second point used to graph the line is (50, 0). Plotting this point, (50, 0), and the other point, (0, 100), results in the line representing all the solutions in which exactly 100 hours of painting and varnishing time are used, as shown in Figure 7.4.

To find the points that require less than 100 hours, select a point on either side of this line to see if the inequality portion of the constraint is satisfied. Selecting (0, 0) gives us

This indicates that this and all the points below the line satisfy the constraint, and this region is shaded in Figure 7.4.

Now that each individual constraint has been plotted on a graph, it is time to move on to the next step. We recognize that to produce a chair or a table, both the carpentry and the painting and varnishing departments must be used. In an LP problem, we need to find that set of solution points that satisfies all of the constraints simultaneously. Hence, the constraints should be redrawn on one graph (or superimposed one upon the other). This is shown in Figure 7.5.

The shaded region now represents the area of solutions that do not exceed either of the two Flair Furniture constraints. It is known by the term area of feasible solutions or, more simply, the feasible region. The feasible region in an LP problem must satisfy all conditions specified by the problem’s constraints, and is thus the region where all constraints overlap. Any point in the region would be a feasible solution to the Flair Furniture problem; any point outside the shaded area would represent an infeasible solution. Hence, it would be feasible to manufacture 30 tables and 20 chairs $\left(T=30,C=20\right)$ during a production period because both constraints are observed:

But it would violate both of the constraints to produce 70 tables and 40 chairs, as we see here mathematically:

The constraints are as follows.

Carpentry constraint

• Sum of 4 times “T” and 3 times “C” is less than or equal to 240 hours available

• Sum of 4 times 70 and 3 times 40 equals 400 hours used

Painting constraint

• Sum of 2 times “T” and 1 times “C” is less than or equal to 100 hours available

• Sum of 2 times 70 and 1 times 40 equals 180 hours used

The image shows cross marks against each of the equations.

Furthermore, it would be infeasible to manufacture 50 tables and 5 chairs $\left(T=50,C=5\right).$ Can you see why?

The constraints are as follows.

Carpentry constraint

• Sum of 4 times “T” and 3 times “C” is less than or equal to 240 hours available

• Sum of 4 times 50 and 3 times 5 equals 215 hours used

Painting constraint

• Sum of 2 times “T” and 1 times “C” is less than or equal to 100 hours available

• Sum of 2 times 50 and 1 times 5 equals 105 hours used

The image shows a tick mark against the carpentry equation and a cross mark against the painting equation.

This possible solution falls within the time available in carpentry but exceeds the time available in painting and varnishing and thus falls outside the feasible region.

Now that the feasible region has been graphed, we may proceed to find the optimal solution to the problem. The optimal solution is the point lying in the feasible region that produces the highest profit. Yet there are many, many possible solution points in the region. How do we go about selecting the best one, the one yielding the highest profit?

There are a few different approaches that can be taken in solving for the optimal solution when the feasible region has been established graphically. The speediest one to apply is called the isoprofit line method.

We start the technique by letting profits equal some arbitrary but small dollar amount. For the Flair Furniture problem, we may choose a profit of $2,100. This is a profit level that can be obtained easily without violating either of the two constraints. The objective function can be written as $\$2,100=70T+50C.$

This expression is just the equation of a line; we call it an isoprofit line. It represents all combinations of $\left(T,C\right)$ that would yield a total profit of $2,100. To plot the profit line, we proceed exactly as we did to plot a constraint line. First, let $T=0$ and solve for the point at which the line crosses the C axis:

Then, let $C=0$ and solve for T:

We can now connect these two points with a straight line. This profit line is illustrated in Figure 7.6. All points on the line represent feasible solutions that produce a profit of $2,100.3

Now, obviously, the isoprofit line for $2,100 does not produce the highest possible profit to the firm. In Figure 7.7, we try graphing two more lines, each yielding a higher profit. The middle equation, $\$2,800=\$70T+\$50C,$ was plotted in the same fashion as the lower line. When $T=0,$

When $C=0,$

We draw a series of parallel isoprofit lines until we find the highest isoprofit line—that is, the one with the optimal solution.

Again, any combination of tables (T) and chairs (C) on this isoprofit line produces a total profit of $2,800. Note that the third line generates a profit of $3,500, even more of an improvement. The farther we move from the origin, the higher our profit will be. Another important point is that these isoprofit lines are parallel. We now have two clues as to how to find the optimal solution to the original problem. We can draw a series of parallel lines (by carefully moving our ruler in a plane parallel to the first profit line). The highest profit line that still touches some point of the feasible region pinpoints the optimal solution. Notice that the fourth line ($4,200) is too high to be considered.

The last point that an isoprofit line would touch in this feasible region is the corner point where the two constraint lines intersect, so this point will result in the maximum possible profit. To find the coordinates of this point, solve the two equations simultaneously (as detailed in the next section). This results in the point (30, 40), as shown in Figure 7.8. Calculating the profit at this point, we get

So producing 30 tables and 40 chairs yields the maximum profit of $4,100.