Methods of solving LPP: a graphical method

After formulating a Linear Programming Problem (LPP), the next step is to solve it by finding the optimal solution. In this topic, we will discuss the graphical approach to solving LPPs with two decision variables.

In the graphical approach, LPPs are solved on two-dimensional planes. When there are more than two variables, planar graphs are inadequate. 3D graphs are required for LPPs with three variables and advanced graphical visualization techniques for higher-dimensional problems. Analyzing surface and higher dimensional plots for the optimal solution is difficult. The simplex method applies the same geometric principles that would be discussed in this topic to solve simple and complex LPPs.

Geometric interpretation of LPP

A LPP with two decision variables can be solved graphically. We will use the following LPP as an exapmle to draw geometric analogies.

Example 1:

$$Maximize \ z = 4x_1 + 3x_2$$Subject to the following constraints:

$$x_1 + x_2 \le 60 \\ 2x_1 + x_2 \le 80 \\ 3x_1 + x_2 \le 120 \\ x_1, x_2 \ge 0$$

The above LPP has two variables and its solution can be shown on a two-dimensional real space, $R^2$. If each inequality is plotted on a separate graph, we get the following plots:

The half-planes that are shaded satisfy the inequality constraints, while the other half-planes do not. Since the inequalities are not strict, the boundaries of the half-planes also satisfy the inequality constraints.

The intersection of finitely many half-planes is depicted by the term polyhedron. The figure above shows the intersection of half-planes that satisfy the inequality constraints: $x_1 \ge 0, x_2 \ge 0, x_1 + x_2 \le 60, 2x_1+x_2 \le 80$, and $3x_1 + x_2 \le 120$. The region of the graph where all the unique half-planes that satisfy the inequality constraints intersect is called the feasible region. The feasible region is a convex set and a polyhedron, and it is shown in the figure below:

In the above figure, we can remove the line representing the constraint: $3x_1 + x_2 \le 120,$ and this does not change the shape of the feasible region. The constraint is therefore redundant. Next, let's consider an unbounded LPP.

Example 2:

$$Maximize \ z = 2x_1 + 4x_2$$Subject to the following constraints:

$$x_1 - 2x_2 \le 1 \\ x_1 + 2x_2 \ge 3 \\ x_1, x_2 \ge 0$$The constraints to the LPP are shown in the graph below. The feasible region is unbounded and the objective function can be made infinitely large without violating any of the constraints. The unbounded LPP does not have a maximum.

Next, let's consider a LPP with no feasible solution.

Example 3:

$$Minimize \ z = x_1 + x_2$$Subject to the following constraints:

$$x_1 + x_2 \le 4 \\ x_1 \ge 4 \\ x_2 \ge 4 \\ x_1, x_2 \ge 0$$The graph below shows the constraints to the LPP. The three half-planes defined by the constraints do not intersect. Therefore, there is no feasible region in this problem. The LPP is infeasible and does not contain a solution.

We have seen examples of linear programming problems with bounded and unbounded feasible regions, as well as the case when a feasible region does not exist. If there is a feasible region for LPP, then all points lying within the feasible region can potentially be a solution to the problem. Our task is to find the values of $x_1$ and $x_2$ that maximize or minimize the objective function. Let's now discuss the corner point method.

The corner point method

In this method, corner points values are substituted into the objective function. The corner point principle states that if the feasible region of the graphical solution has corner points, the optimal solution is at one of the corner points.

Steps for the corner point method:

1. Construct a graph and plot the constraint inequalities, and identify the feasible region;
2. Determine corner points and their coordinates;
3. Evaluate the objective function at each corner point;
4. Find the optimal solution

Consider the following LPP:

Example 4:

$$Minimize \ z =10 x_1 +8 x_2$$Subject to the following constraints:

$$15x_1 + 9x_2 \ge 270 \\ 10x_1 + 16x_2 \ge 280 \\ x_1, x_2 \ge 0$$

Step 1.

If we plot the constraint: $15x_1 + 9x_2 \ge 270$, we obtain the following graph:

The area shaded light red is the half-plane satisfying the constraint: $15x_1 + 9x_2 \ge 270$. When we plot the constraint: $10x_1 + 16x_2 \ge 280$ on the same graph, we obtain the following plot:

The area shaded light-green is the half-plane satisfying the constraint: $10x_1 + 16x_2 \ge 280$, and the area shaded light-orange is the region where both half-planes satisfying both constraints intersect. If we introduce the trivial non-negativity constraints, we obtain the following graph:

When we consider only the region where the four half-planes that satisfy the constraints all intersect in the above graph, we get the graph below:

Step 2.

Points A, B, and C are the corner points on the boundary of the feasible region. For some points, the coordinates are easy to determine from the graph. For example, point A. To find the coordinates of other corner points, we can use the following corner point definition.

Definition: Point P lying at the intersection of the boundaries of several linearly independent constraints is called a corner point.

For example, point B is formed by the intersection of two straight lines $15x_1 + 9x_2 = 270$, and $10x_1 + 16x_2 = 280$, which are the boundaries of the corresponding constraints of the LPP. To find the coordinates of point B, we need to solve a system of linear equations:$$\begin{cases} 15x_1 + 9x_2 = 270 \\ 10x_1 + 16x_2 = 280 \end{cases}$$ as a result, we get the coordinates of $B(12; 10)$.

To find the coordinates of point C, we need to solve a system of linear equations:

$$\begin{cases} 10x_1 + 16x_2 = 280 \\ x_2 = 0 \end{cases}$$by solving the system we get the coordinates of $C(28; 0)$.

Step 3.

The coordinates at these corner points are substituted into the objective function. Because we want to minimize the objective function, we know that the coordinates of a corner point would give us the minimum value when we plug them into the objective function.

Step 4.

The corner point that minimizes the objective function is point $B$.

A LPP may have many constraints. Computing the values of the coordinates of all corner points and then substituting them into the objective function to calculate their values can be cumbersome. We will introduce a simpler method of finding the optimal solution of a LPP in the next section.

Iso-cost (or Iso-profit) method

The second method of finding the optimal solution graphically is by drawing iso-cost (or iso-profit) lines. It is called iso-cost for minimization problems and iso-profit for maximization problems. It is called an iso-line because points along the line produce the same value for the objective function. Let's use the graph below to illustrate this point. The points $A, B$, and $C$ are on the iso-line: $x_1+2x_2 = 2$. When you substitute the coordinates of $A, B$, and $C$ into the iso-line equation, we get a value of $2$.

The general principle of the iso-cost (or iso-profit) method states that the iso-cost (or iso-profit) line closest to (or farthest from) the origin minimizes (or maximizes) the objective function. In the Iso-cost (or Iso-profit) method, you substitute a value for the objective function $z=p$ and plot on the same graph in which the plots of the constraints have been made. After that, you determine the optimal position of the iso-value (or iso-profit) line, which minimizes (or maximizes) the objective function in the feasible region.

Steps for the Iso-cost (or Iso-profit) method:

1. Construct a graph and plot the constraint inequalities, and identify the feasible region;
2. Draw an Iso-cost (or Iso-profit) line with the objective function for some value $z=p$;
3. Mentally move the Iso-cost (Iso-profit) line in parallel (keeping the slope) until you get an Iso-cost (Iso-profit) line within the feasible region that is closest to (farthest from ) the origin. The resulting Iso-cost (Iso-profit) line can: intersect at one corner point with the feasible region, or coincide with one of the boundary lines of the feasible region;
4. Find the optimal solution.

Let's graphically illustrate how this method works with two examples. First, let us use the LPP given in example 4.

Steps 1.

We have shown how to plot the inequality constraints and identify the feasible region for this problem when we discussed step 1 of the corner point method.

Step 2.

The objective function for Example 4 is $10x_1 + 8x_2 = z$. If we make an initial guess of $z = 400$, we get the following plot:

The Iso-cost line $10x_1 + 8x_2=400$ is inside the feasible region. Although $z=400$ is a feasible solution, it does not minimize the objective function. From the general Iso-cost principle, we want an iso-line in the feasible region that is closest to the origin. We will try smaller $z$ values until we get the one that minimizes the objective function.

Step 3.

When we use the iso-cost line $10x_1 + 8x_2=300$, we get the line as in the plot below. The iso-cost line when $z = 300$ is smaller than our initial guess and is within the feasible region; but it still does not minimize the objective function since more Iso-cost lines with smaller z values can still fit into the space between $10x_1 + 8x_2=300$ and the feasible region boundary A-B-C.

We will try a smaller value of z. When we use the iso-cost line $10x_1 + 8x_2=200$, we get the following plot:

This time the Iso-cost line cuts through the lowest part of the feasible region boundary A-B-C. There is no more space for more Iso-cost lines in the feasible region. Therefore, $10x_1 + 8x_2=200$ is the iso-cost line in the feasible region that is closest to the origin. The points in the feasible region that lie along this line minimize the objective function. There is only one point, $B$, that lies in the feasible region that is along the iso-cost line $10x_1 + 8x_2=200$.

Step 4.

After determining the optimal Iso-cost line, we can proceed to obtain the decision variables that optimize the objective function. This is the point of intersection between the Iso-cost line and the feasible region and it is at point $B$ with coordinates $(12,10)$.

An attentive learner would have noticed that as we move bottom-left (closer to the origin), the value of z decreases. Similarly, as we move top-right (away from the origin), the value of z increases. We have used multiple Iso-cost (or Iso-profit) lines to illustrate how to search for the optimal solution within the feasible region. In practice, we search for the optimal solution by mentally moving only one iso-line to the extreme points enclosed by the feasible region.

Let's solve the maximization problem in Example 1 with this approach. Recall the LPP formulation for this example.

$$Maximize \ z = 4x_1 + 3x_2$$Subject to the following constraints:

$$x_1 + x_2 \le 60 \\ 2x_1 + x_2 \le 80 \\ 3x_1 + x_2 \le 120 \\ x_1, x_2 \ge 0$$Step 1.

We have shown how to plot the inequality constraints and identify the feasible region for this problem in the section "Geometric interpretation of LPP". Since it is a maximization problem, we would be dealing with Iso-profit lines instead of Iso-cost lines.

Step 2.

Let's put the value $z=30$. This value corresponds to the objective function $4x_1 + 3x_2 = 30$. It is shown in the animation with a red dotted line. We built it to determine the slope of the objective function. There is no specific meaning or rule as to why we chose the value $30$, we could have chosen any other value.

Step 3.

Since we are dealing with a maximization problem, we need an Iso-profit line that is farthest from the source within the feasible region. We will mentally move it in parallel until it reaches the extreme position. This process is depicted in the animation.

Step 4.

In our example, in the extreme position, the iso-line intersects the feasible region only at one point $B$. To find the coordinates of this point, we need to solve a system of linear equations:$$\begin{cases} x_1 + x_2 = 60 \\ 2x_1 + x_2 = 80 \end{cases}$$We get the coordinates of $B(20; 40)$. Substitute the coordinates of point $B$ into the objective function and get the maximum value of the objective function:

$$z(20,40) = 4 \cdot 20 + 3 \cdot 40 = 200.$$In addition: It is possible that the iso-line in the extreme position coincides with one of the boundaries of the feasible region. In this case, any of the points of this boundary can be taken as the optimal point. Usually, one of the corner points of this border is chosen.

Conclusion

In this topic, we learned about the geometric interpretation of a linear programming problem and discussed the following terms: polyhedron, feasible region, half-plane, corner point, and iso-line.

Furthermore, we learned how to:

• Construct the feasible region of a linear programming problem.
• Find the corner points of the feasible region.
• Solve the linear programming method graphically with the corner point and iso-cost (or iso-profit) methods.