Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 17

Solution of Linear Programming Problems

Abstract

While the previous chapter discussed the modeling of linear programming problems, this chapter discusses the possible solution methods. The set of feasible solutions and the optimal solution for a simple linear programming problem can be obtained in a graphical way, through the analytical method, by using the Simplex method, and through software packages. All the real linear programming problems modeled in Chapter 16 will be solved by the Solver in Excel. The special cases that may happen in a linear programming model will be graphically identified through the Simplex method and by using a computer. The sensitivity analysis, which will be studied at the end of this chapter, has as its main objective to analyze how changes in the model parameters impact the optimal solution. These possible changes will be analyzed in a graphical way and by Solver in Excel. The concepts of shadow price and reduced cost will also be discussed in the study of the sensitivity analysis. Through the Sensitivity Report found on Solver in Excel, the special cases “multiple optimal solutions” and “degenerate optimal solution” will be identified.

Keywords

Linear programming; Graphical solution; Analytical solution; Simplex method; Solver in Excel; Special cases; Sensitivity analysis; Shadow price; Reduced cost

There is geometry everywhere. However, it is necessary to have eyes to see it, intelligence to understand it, and a soul to admire it.

Malba Tahan in “The Man Who Counted”

17.1 Introduction

In this chapter, we will discuss several ways of solving a linear programming problem (LP): a) in a graphical way; b) through the analytical method; c) by using the Simplex method; d) by using a computer.

A simple linear programming problem with only two decision variables can be easily solved in a graphical way or through the analytical method. The graphical solution can be applied to solve problems with three decision variables, at the most; however, with greater complexity. Similarly, the analytical solution becomes impractical for problems with many variables and equations, since it calculates all the possible basic solutions. As an alternative to these procedures, we can use the Simplex algorithm or any existing software directly (GAMS, AMPL, AIMMS, software with electronic spreadsheets, such as, Solver in Excel and What’s Best, among others) to solve any linear programming problem. In this chapter, we will solve each one of the management problems modeled in the previous chapter (Examples 16.3 to 16.12) by using Solver in Excel.

Some linear programming problems do not have a single nondegenerate optimal solution. It may fall into one of the four categories: a) multiple optimal solutions; b) unlimited objective function z; c) there is no optimal solution; d) degenerate optimal solution. Throughout this chapter, we will discuss how to identify each one of these special cases in a graphical way, through the Simplex method, and by using a computer.

Many times, the estimation of model parameters is based on future forecasts, and changes may occur until the final solution is implemented in the real world. As examples of changes, we can mention changes in the quantity of resources available, introduction of a new product, variation in a product’s price, increase or decrease in production costs, among others. Therefore, the sensitivity analysis is essential in the study of linear programming problems, since it has as its main goal to investigate the impacts that certain changes in the model parameters would have on the optimal solution.

The sensitivity analysis presented at the end of the chapter discusses the variation that the objective function coefficients and constants, on the right-hand side of each constraint, can assume without changing the initial model’s optimal solution, or without changing the feasibility region. This analysis can be carried out graphically, by using algebraic calculations, or directly through Solver in Excel or other software packages, such as, Lindo, considering one alteration at a time.

17.2 Graphical Solution of a Linear Programming Problem

A simple linear programming problem that has two decision variables can be easily solved in a graphical way. According to Hillier and Lieberman (2005), any LP problem that has two decision variables can be solved graphically. Problems with up to three decision variables can also be solved in a graphical way, but with greater complexity.

In the graphical solution for a linear programming model, first of all, we must determine the feasible solution space or feasible region along a Cartesian axis. A viable or feasible solution is the one that satisfies all the model constraints, including the non-negativity ones. If a certain solution breaches at least one of the model constraints, it is called an unfeasible solution.

The following step consists in determining the model’s optimal solution, that is, the feasible solution that has the best objective function value. For a maximization problem, after the set of feasible solutions is established, the optimal solution is the one that gives the highest value to the objective function within this set. Whereas for a minimization problem, the optimal solution is the one that minimizes the objective function.

The set of feasible solutions for a linear programming problem is represented by K. Subsequently, the first theorem was born:

Theorem 1

The K set is convex.

Definition

A K set is convex when all the line segments that connect any two points of K are included in K. A convex set is bounded if it includes its bounds.

As an illustrative example, the graphical representation of convex and nonconvex sets can be seen in Fig. 17.1.

The graphical solution for a linear programming maximization and minimization problem with a single optimal solution will be illustrated through Examples 17.1 and 17.2, respectively. The special cases will also be presented (multiple optimal solutions, unlimited objective function, unfeasible solution, and degenerate optimal solution), through Examples 17.3, 17.4, 17.5, and 17.6.

17.2.1 Linear Programming Maximization Problem with a Single Optimal Solution

The graphical solution for an LP maximization problem with a single optimal solution will be illustrated through Example 17.1.

Example 17.1

Consider the following LP maximization problem:

$\begin{array}{l} max z = 6 x_{1} + 4 x_{2} \\ subject to : \\ 2 x_{1} + 3 x_{2} \leq 18 \\ 5 x_{1} + 4 x_{2} \leq 40 \\ x_{1} \leq 6 \\ x_{2} \leq 8 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} max z = 6 x_{1} + 4 x_{2} \\ subject to : \\ 2 x_{1} + 3 x_{2} \leq 18 \\ 5 x_{1} + 4 x_{2} \leq 40 \\ x_{1} \leq 6 \\ x_{2} \leq 8 \\ x_{1}, x_{2} \geq 0 \end{array}$

si1_e (17.1)

Determine the set of feasible solutions, in addition to the model’s optimal solution.

Solution

Feasible region

In the Cartesian axes x₁ and x₂, we determine the feasible solution space that represents the constraints of the maximization model being studied. First, for each constraint, we plot the line that represents the equality equation (without considering the signs ≥ or ≤) and, from then on, we determine the direction of the line that satisfies the inequality. Thus, for the first constraint, the line that represents the equation 2x₁ + 3x₂ = 18 can be plotted from two points. If x₁ = 0, then x₂ = 6. Analogously, if x₂ = 0, then x₁ = 9. To determine the solution space or the direction of the line that satisfies the inequality 2x₁ + 3x₂ ≤ 18, we can consider any point outside the line. We usually use the point of origin (x₁, x₂) = (0, 0), due to its simplicity. We can see that the point of origin satisfies the first inequality, because 0 + 0 ≤ 18. Therefore, we can identify the direction of the line that has feasible solutions, as shown in Fig. 17.2.

Fig. 17.2 Feasible region of Example 17.1.

In the same way, for the second constraint, the line that represents equality equation 5x₁ + 4x₂ = 40 is plotted from two points. If x₁ = 0, then x₂ = 10. Analogously, if x₂ = 0, then x₁ = 8. We can also see that the point of origin satisfies the inequality 5x₁ + 4x₂ ≤ 40, because 0 + 0 ≤ 40, representing the direction of the straight line that contains the feasible solutions, consistent with Fig. 17.2.

Similarly, we can determine the feasible solution space for the other constraints x₁ ≤ 6, x₂ ≤ 8, x₁ ≥ 0 and x₂ ≥ 0.

Constraints 5x₁ + 4x₂ ≤ 40 and x₂ ≤ 8 are redundant, that is, if they were excluded from the model, the feasible solution space would not be affected.

The feasible region is represented by the four-sided polygon ABCD. Any point on the surface of the polygon or inside it represents the feasible region. On the other hand, any point outside the polygon does not satisfy at least one of the model constraints.

Optimal solution

The next step tries to determine the model’s optimal solution that maximizes the function z = 6x₁ + 4x₂, within the feasible solution space shown in Fig. 17.2.

Since the solution space contains an infinite number of points, it is necessary to carry out a formal procedure to identify the optimal solution (Taha, 2016). First, we need to identify the correct direction in which the function increases (maximization function). In order to do that, we will draw different straight lines based on the objective function equation, assigning different values to z, by trial and error. Having identified the direction in which the objective function increases, it is possible to identify the model’s optimal solution, within the feasible solution space.

First, we assigned a value of z = 24, followed by z = 36, and obtained equations 6x₁ + 4x₂ = 24 and 6x₁ + 4x₂ = 36, respectively. From these two equations, it was possible to identify the direction, within the feasible solution space, that maximizes the objective function, concluding that point C is optimal. Since vertex C is the intersection of lines 2x₁ + 3x₂ = 18 and x₁ = 6, values x₁ and x₂ can be calculated algebraically from these two equations. Therefore, we have x₁ = 6 and x₂ = 2 with z = 6 × 6 + 4 × 2 = 44. The complete procedure is presented in Fig. 17.3.

Since all the lines are represented by the equation z = 6x₁ + 4x₂, if we only change the value of z, we can conclude, by Fig. 17.3, that the lines are parallel.

Another important theorem states that an optimal solution for a linear programming problem is always associated to a vertex or extreme point of the solution space:

Theorem 2

For linear programming problems with a single optimal solution, the objective function reaches its maximum or minimum point in an extreme point in convex set K.

17.2.2 Linear Programming Minimization Problem With a Single Optimal Solution

Example 17.2

Consider the following minimization problem:

$\begin{array}{l} min z = 10 x_{1} + 6 x_{2} \\ subject to : \\ 4 x_{1} + 3 x_{2} \geq 24 \\ 2 x_{1} + 5 x_{2} \geq 20 \\ x_{1} \leq 8 \\ x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} min z = 10 x_{1} + 6 x_{2} \\ subject to : \\ 4 x_{1} + 3 x_{2} \geq 24 \\ 2 x_{1} + 5 x_{2} \geq 20 \\ x_{1} \leq 8 \\ x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{array}$

si2_e (17.2)

Determine the set of feasible solutions and the model’s optimal solution.

Solution

Feasible region

The same procedure of Example 17.1 is used to obtain the feasible solution space of the minimization problem.

First, we must determine the feasible region from the minimization model constraints. Considering the first 4x₁ + 3x₂ ≥ 24 and the second 2x₁ + 5x₂ ≥ 20 constraints, we can see that the point of origin (x₁, x₂)= (0, 0) does not satisfy any of the inequalities. Thus, the feasible direction of these two lines does not contain this point. Including constraints x₁ ≤ 8 and x₂ ≤ 6, the feasible solution space became limited, as shown in Fig. 17.4. Different from Example 17.1, in this case, we can see that all the constraints are nonredundant, that is, they are responsible for defining the model’s feasibility region. The feasibility region is represented by polygon ABCD that is highlighted in Fig. 17.4.

Fig. 17.4 Feasible region of Example 17.2.

Optimal solution

The same procedure of Example 17.1 is used to find the optimal solution for the minimization problem.

Therefore, we are trying to determine the model’s optimal solution that minimizes the function z = 10x₁ + 6x₂, within the feasible solution space shown in Fig. 17.4.

To analyze the direction in which the objective function decreases (minimization function), different values of z were assigned, by trial and error. Firstly, we assigned a value of z = 72, obtaining equation 10x₁ + 6x₂ = 72, followed by z = 60 where 10x₁ + 6x₂ = 60. Hence, it was possible to identify the direction that minimizes the objective function, concluding that point D represents the model’s optimal solution (see Fig. 17.5).

Fig. 17.5 Optimal solution for Example 17.2.

Coordinates x₁ and x₂ of point D can be calculated algebraically from equations 4x₁ + 3x₂ = 24 and 2x₁ + 5x₂ = 20, because point D is the intersection of these two equations. Thus, we have x₁ = 1.5 and x₂ = 6 with z = 10 × 1.5 + 6 × 6 = 51.

As in the previous example, the LP problem shows a single optimal solution that is associated to an optimal vertex of the solution space (Theorem 2).

17.2.3 Special Cases

Sections 17.2.1 and 17.2.2 presented the graphical solution for a maximization (Example 17.1) and minimization problem (Example 17.2), respectively, with a single nondegenerate optimal solution. The graphical concept of a degenerate solution will be presented in Section 17.2.3.4. However, some linear programming problems do not have a single nondegenerate optimal solution, and they may fall into one of the four cases presented:

1. Multiple optimal solutions
2. Unlimited objective function z
3. There is no optimal solution
4. Degenerate optimal solution

This section aims to identify, in a graphical way, each one of the special cases listed, which may happen in a linear programming problem. We will also study how to identify them through the Simplex method (see Section 17.4.5) and through a computer (cases 2 and 3 in Section 17.5.3, and cases 1 and 4 in Section 17.6.4).

17.2.3.1 Multiple Optimal Solutions

A linear programming problem can have more than one optimal solution. In this case, considering a problem with two decision variables, different values of x₁ and x₂ achieve the same optimal value in the objective function. This case is graphically illustrated through Example 17.3.

According to Taha (2016), when the objective function is parallel to an active constraint, we have a case with multiple optimal solutions. An active constraint is the one responsible for determining the model’s optimal solution.

Example 17.3

Determine the set of feasible solutions and the model’s optimal solutions for the following linear programming problem:

$\begin{array}{l} max z = 8 x_{1} + 4 x_{2} \\ subject to : \\ 4 x_{1} + 2 x_{2} \leq 16 \\ x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} max z = 8 x_{1} + 4 x_{2} \\ subject to : \\ 4 x_{1} + 2 x_{2} \leq 16 \\ x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{array}$

si3_e (17.3)

Solution

The same procedure used in the previous examples to find the optimal solution was applied in this case.

Fig. 17.6 shows the feasible region determined from the constraints of the model analyzed. We can see that the feasible solution space is represented by the four-sided polygon ABCD.

To determine the model’s optimal solution, first of all, we assigned a value of z = 16, and obtained the line presented in Fig. 17.6. Since the objective function is a maximization one, the higher the values of x₁ and x₂, the higher the value of function z, such that the direction in which the function increases can be easily identified. We can see that the lines represented by equations z = 16 = 8x₁ + 4x₂ and 4x₁ + 2x₂ = 16 are parallel. Therefore, this is a case with multiple optimal solutions represented by the segment BC. For example, for point B, x₁ = 4, x₂ = 0, the value of z is 8 × 4 + 4 × 0 = 32. Point C is the intersection of lines 4x₁ + 2x₂ = 16 and x₁ + x₂ = 6. Calculating it algebraically, we obtain x₁ = 2 and x₂ = 4 with z = 8 × 2 + 4 × 4 = 32. Any other point in this segment is an alternative optimal solution and also presents z = 32.

Hence, a new theorem is born:

Theorem 3

For linear programming problems with more than one optimal solution, the objective function assumes this value in at least two extreme points of convex set K and in all the convex linear combinations of these extreme points (all the points of the line segment that join these two extremes, that is, the corner of the polygon that contains these extreme points).

17.2.3.2 Unlimited Objective Function z

In this case, there is no limit for how much the value of at least one decision variable can increase, resulting in a feasible region and an unlimited objective function z.

For a maximization problem, the value of the objective function increases unlimitedly, while for a minimization problem, the value decreases in an unlimited way.

Example 17.4 illustrates a case that shows an unlimited set of solutions, in a graphical way, resulting in an unlimited value of the objective function.

Example 17.4

Determine the feasible solution space and the model’s optimal solution for the following linear programming problem:

$\begin{array}{l} max z = 4 x_{1} + 3 x_{2} \\ subject to : \\ 2 x_{1} + 5 x_{2} \geq 20 \\ x_{1} \leq 8 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} max z = 4 x_{1} + 3 x_{2} \\ subject to : \\ 2 x_{1} + 5 x_{2} \geq 20 \\ x_{1} \leq 8 \\ x_{1}, x_{2} \geq 0 \end{array}$

si4_e (17.4)

Solution

From the constraints in Example 17.4, we obtain the feasible solution space, that in this case is unlimited, because there is no limit for the increase of x₂, as shown in Fig. 17.7. Consequently, objective function z can also increase in an unlimited way. The complete procedure is shown in Fig. 17.7.

Fig. 17.7 Unlimited set of feasible solutions and unlimited maximization function z.

17.2.3.3 There Is No Optimal Solution

In this case, it is not possible to find a feasible solution for the problem being studied, that is, there is no optimal solution. The set of feasible solutions is empty. Example 17.5 illustrates a case in which there is no optimal solution, in a graphical way.

Example 17.5

Consider the following linear programming problem:

$\begin{array}{l} max z = x_{1} + x_{2} \\ subject t o : \\ 5 x_{1} + 4 x_{2} \geq 40 \\ 2 x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} max z = x_{1} + x_{2} \\ subject t o : \\ 5 x_{1} + 4 x_{2} \geq 40 \\ 2 x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{array}$

si5_e (17.5)

Determine the feasibility region and the optimal solution for the linear programming model.

Solution

Fig. 17.8 shows the graphical solution for Example 17.5, considering each one of the model constraints, besides the objective function with an arbitrary value of z = 7.

From Fig. 17.8, we can see that no point satisfies all the problem constraints. This means that the feasible solution space in Example 17.5 is empty, resulting in an unfeasible LP problem that has no optimal solution.

17.2.3.4 Degenerate Optimal Solution

Graphically, we can see a special case of degenerate solution whenever one of the vertices of the feasible region is obtained from the intersection of more than two distinct lines. Therefore, we have a degenerate vertex. If there is degeneration in the optimal solution, we have a case known as degenerate optimal solution.

The concept of degenerate solution and a degeneration problem will be discussed in depth in Sections 17.4.5.4 (identification of a degenerate optimal solution through the Simplex method) and 17.6.4.2 (identification of a degenerate optimal solution through the Sensitivity Report in the Solver in Excel).

Example 17.6

Consider the following linear programming problem:

$\begin{array}{l} min z = x_{1} + 5 x_{2} \\ subject t o : \\ 2 x_{1} + 4 x_{2} \geq 16 \\ x_{1} + x_{2} \leq 6 \\ x_{1} \leq 4 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} min z = x_{1} + 5 x_{2} \\ subject t o : \\ 2 x_{1} + 4 x_{2} \geq 16 \\ x_{1} + x_{2} \leq 6 \\ x_{1} \leq 4 \\ x_{1}, x_{2} \geq 0 \end{array}$

si6_e (17.6)

Determine the feasibility region and the optimal solution for the linear programming model.

Solution

The feasible solution space of Example 17.6 is shown in Fig. 17.9, and it is represented by triangle ABC. We can see that constraint x₁ ≤ 4 is redundant. Since vertex B is the intersection of three lines, we have a degenerate vertex.

The minimization function consists in the equation z = x₁ + 5x₂ that tries to find the minimum point that satisfies all the model constraints. Thus, from a value of z = 50, it is possible to identify the direction of the line that minimizes function z, as shown in Fig. 17.9. Therefore, we can see that point B is the degenerate optimal solution. Since point B is the intersection of lines 2x₁ + 4x₂ = 16 and x₁ + x₂ = 6, coordinates x₁ and x₂ can be calculated algebraically from these equations. So, we have x₁ = 4 and x₂ = 2 with z = 4 + 5 × 2 = 14.

17.3 Analytical Solution of a Linear Programming Problem in Which m < n

The graphical procedure for solving LP problems was presented in Section 17.2. This section discusses the analytical procedure for solving a linear programming problem.

Consider a system Ax = b with m linear equations and n variables, in which m < n. According to Taha (2016), if m = n and the equations are coherent, the system has a single solution. In cases in which m > n, at least m − n equations must be redundant. However, if m < n and the equations are also coherent, the system will have an infinite number of solutions.

To find a solution for the system Ax = b, in which m < n, first, we have to choose a set of variables n − m from x, called nonbasic variables (NBV), to which values equal to zero are assigned. The m remaining variables of the system, called basic variables (BV), are then determined. This solution is called basic solution (BS). The set of basic variables is called base.

If the basic solution meets the non-negativity constraints, that is, the basic variables are non-negative, it is called feasible basic solution (FBS).

According to Winston (2004), a basic variable can also be defined as the one that has coefficient 1 in only one equation, and 0 in the others. All the remaining variables are nonbasic.

To calculate the optimal solution, we just need to calculate the value of objective function z of all the possible basic solutions and choose the best alternative. The maximum number of basic solutions to be calculated is:

$C_{m}^{n} = (\begin{array}{l} n \\ m \end{array}) = \frac{n!}{m! (n - m)!}$ $C_{m}^{n} = (\begin{array}{l} n \\ m \end{array}) = \frac{n!}{m! (n - m)!}$

si7_e (17.7)

Hence, the analytical method applied in this section analyzes all the possible combinations of n variables chosen m by m, choosing the best one. Solving it through a linear equation system is feasible in cases in which m and n are small. However, for high values of m and n, the calculation becomes impractical. As an alternative, we can use the Simplex method that will be studied in Section 17.4.

Example 17.7

Consider the following system with three variables and two equations:

$\begin{array}{l} x_{1} + 2 x_{2} + 3 x_{3} = 28 \\ 3 x_{1} - x_{3} = 4 \end{array}$ $\begin{array}{l} x_{1} + 2 x_{2} + 3 x_{3} = 28 \\ 3 x_{1} - x_{3} = 4 \end{array}$

si8_e

Determine all the basic solutions for this system.

Solution

For a system with three variables and two equations, we have n − m = 3 − 2 = 1 nonbasic variables and m = 2 basic variables. In this example, the total number of possible basic solutions is 3.

Solution 1

NBV = {x₁} and BV = {x₂, x₃}

We assigned the value zero to the nonbasic variable, that is, x₁ = 0. Thus, we calculate the values of variables x₂ and x₃ of the basic solution algebraically, from the equation system seen in the heading of the exercise. So, x₂ = 20 and x₃ = − 4.

Since x₃ < 0, the solution is unfeasible.

Solution 2

NBV = {x₂} and BV = {x₁, x₃}

If x₂ = 0, the basic solution is x₁ = 4 and x₃ = 8. Therefore, we have a feasible basic solution (FBS).

Solution 3

NBV = {x₃} and BV = {x₁, x₂}

If x₃ = 0, the basic solution is x₁ = 1.33 and x₂ = 13.33. As in the previous case, we have an FBS here.

Example 17.8

Consider the following linear programming problem:

$\begin{array}{l} max 3 x_{1} + 2 x_{2} \\ subject to : \\ x_{1} + x_{2} \leq 6 \\ 5 x_{1} + 2 x_{2} \leq 20 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} max 3 x_{1} + 2 x_{2} \\ subject to : \\ x_{1} + x_{2} \leq 6 \\ 5 x_{1} + 2 x_{2} \leq 20 \\ x_{1}, x_{2} \geq 0 \end{array}$

si9_e (17.8)

Solve the problem in an analytical way.

Solution

In order for the analytical solution procedure to be applied, the problem must be in standard form (see Section 16.4.1 of the previous chapter). In order for the inequality constraints to be rewritten as equalities, slack variables x₃ and x₄ must be included. Thus, the original problem rewritten in standard form becomes:

$\begin{array}{l} max 3 x_{1} + 2 x_{2} \\ subject t o : \\ x_{1} + x_{2} + x_{3} = 6 \\ 5 x_{1} + 2 x_{2} + x_{4} = 20 \\ x_{1}, x_{2} x_{3}, x_{4} \geq 0 \end{array}$ $\begin{array}{l} max 3 x_{1} + 2 x_{2} \\ subject t o : \\ x_{1} + x_{2} + x_{3} = 6 \\ 5 x_{1} + 2 x_{2} + x_{4} = 20 \\ x_{1}, x_{2} x_{3}, x_{4} \geq 0 \end{array}$

si10_e (17.9)

The system has m = 2 equations and n = 4 variables. In order for a basic solution to be found, values equal to zero will be assigned to n − m = 4 − 2 = 2 nonbasic variables, such that the values of the m = 2 remaining basic variables can be determined by the equation system represented by Expression (17.9). In this example, the total number of basic solutions is:

$C_{2}^{4} = (\begin{array}{l} 4 \\ 2 \end{array}) = \frac{4!}{2! (4 - 2)!} = 6$ $C_{2}^{4} = (\begin{array}{l} 4 \\ 2 \end{array}) = \frac{4!}{2! (4 - 2)!} = 6$

si11_e

Solution A

NBV = {x₁, x₂} and BV = {x₃, x₄}

First, we assigned value zero to the nonbasic variables x₁ and x₂, such that the values of the basic variables x₃ and x₄ can be calculated algebraically from Expression (17.6). Therefore, we have:

Nonbasic solution: x₁ = 0 and x₂ = 0

Basic solution: x₃ = 6 and x₄ = 20

Objective function: z = 0

The same calculation will be carried out to obtain different basic solutions. At every new solution, a variable from the set of nonbasic variables goes into the set of basic variables (base) and, as a result, one will leave the base.

Solution B

In this case, variable x₁ enters the base instead of variable x₄, which starts to be a part of the set of nonbasic variables.

NBV = {x₂, x₄} and BV = {x₁, x₃}

Nonbasic solution: x₂ = 0 and x₄ = 0

Basic solution: x₁ = 4 and x₃ = 2

Objective function: z = 12

Solution C

In this case, variable x₄ goes into the base instead of variable x₃.

NBV = {x₂, x₃} and BV = {x₁, x₄}

Nonbasic solution: x₂ = 0 and x₃ = 0

Basic solution: x₁ = 6 and x₄ = − 10

Since x₄ < 0, the solution is unfeasible.

Solution D

In this case, variable x₂ goes into the base instead of variable x₄.

NBV = {x₃, x₄} and BV = {x₁, x₂}

Nonbasic solution: x₃ = 0 and x₄ = 0

Basic solution: x₁ = 2.67 and x₂ = 3.33

Objective function: z = 14.7

Solution E

In this case, variable x₄ goes into the base instead of variable x₁.

NBV = {x₁, x₃} and BV = {x₂, x₄}

Nonbasic solution: x₁ = 0 and x₃ = 0

Basic solution: x₂ = 6 and x₄ = 8

Objective function: z = 12

Solution F

In this case, variable x₃ goes into the base instead of variable x₄.

NBV = {x₁, x₄} and BV = {x₂, x₃}

Nonbasic solution: x₁ = 0 and x₄ = 0

Basic solution: x₂ = 10 and x₃ = − 4

Since x₃ < 0, the solution is unfeasible.

Thus, the optimal solution is D, with x₁ = 2.67, x₂ = 3.33, x₃ = 0, x₄ = 0, and z = 14.67.Fig. 17.10

shows the graphical solution for each one of the six solutions obtained from the Cartesian axes x₁ and x₂. Solutions A, B, D, and E correspond to an extreme point of the feasible region. Alternatively, since they are unfeasible, solutions C and F do not belong to the set of feasible solutions. Thus, a new theorem is born:

Theorem 4

Every feasible basic solution for a linear programming problem is an extreme point of convex set K.

17.4 The Simplex Method

As presented in Section 17.2, a graphical solution can be used to solve linear programming problems with two or three decision variables, at the most (greater complexity). In the same way, the analytical solution presented in Section 17.3 becomes impractical for problems with many variables and equations because it calculates all the possible basic solutions, and only afterwards it determines the optimal solution. As an alternative, the Simplex method can be applied to solve any LP problem.

The Simplex method for solving linear programming problems was developed in 1947, with the dissemination of operational research in the United States after World War II, by a team led by George B. Dantzig.

For Goldbarg and Luna (2005), the Simplex algorithm is the most commonly used method for solving linear programming problems.

The Simplex method is an iterative algebraic procedure that starts from an initial feasible basic solution and tries to find, at each iteration, a new feasible basic solution with a better value in the objective function, until the optimal value is achieved. More details of the algorithm will be discussed in the following section.

This section is divided into three parts. The logic of the Simplex method is presented in Section 17.4.1. In Section 17.4.2, the Simplex method is described in an analytical way. The tabular form of the Simplex method is discussed in Section 17.4.3.

17.4.1 Logic of the Simplex Method

The Simplex algorithm is an iterative method that starts from an initial feasible basic solution and tries to find, at each iteration, a new feasible basic solution, called adjacent feasible basic solution, with a better value in the objective function, until the optimal value is achieved. The concept of an adjacent FBS is described.

From a current basic solution, a nonbasic variable goes into the base instead of another basic variable that becomes nonbasic, generating a new solution called adjacent basic solution. For a problem with m basic variables and n − m nonbasic variables, two basic solutions are adjacent if they have m − 1 basic variables in common, and they may even have different numerical values. This also implies that n − m − 1 nonbasic variables are common.

If the adjacent basic solution satisfies the non-negativity constraints, it is called an adjacent feasible basic solution (adjacent FBS).

According to Theorem 4, every feasible basic solution is an extreme point (vertex) of the feasible region. Thus, two vertices are adjacent if they are connected by a line segment called corner, which means that they share n − 1 constraints.

The general description of the Simplex algorithm is presented in Fig. 17.11. Analogous to the analytical procedure, in order for the Simplex method to be applied, the problem must be in the standard form (see Section 16.4.1 of the previous chapter).

The algorithm can also be described through a flowchart, as seen in Fig. 17.12.

17.4.2 Analytical Solution of the Simplex method for Maximization Problems

Each of the steps of the general algorithm described in Figs. 17.11 and 17.12 is rewritten in Fig. 17.13 in a very detailed way, based on Hillier and Lieberman (2005), for the analytical solution for the Simplex method of linear programming problems, in which the objective function z is a maximization one ( max z= c₁x₁ + c₂x₂ + … + c_nx_n = 0).

In Example 17.8 of Section 17.3, to calculate the model’s optimal solution all the possible basic solutions were calculated, and the best of them was chosen. The same exercise is solved in Example 17.9, however, through the analytical solution for the Simplex method.

Example 17.9

Solve the problem by using the analytical solution for the Simplex method.

$\begin{array}{l} max z = 3 x_{1} + 2 x_{2} \\ subject to : \\ x_{1} + x_{2} \leq 6 \\ 5 x_{1} + 2 x_{2} \leq 20 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} max z = 3 x_{1} + 2 x_{2} \\ subject to : \\ x_{1} + x_{2} \leq 6 \\ 5 x_{1} + 2 x_{2} \leq 20 \\ x_{1}, x_{2} \geq 0 \end{array}$

si12_e (17.10)

Solution

Each of the steps of the algorithm will be discussed in depth, based on Hillier and Lieberman (2005).

Beginning: The problem must be in the standard form.

$\begin{array}{l} max z = 3 x_{1} + 2 x_{2} (0) \\ subject to : \\ x_{1} + x_{2} + x_{3} = 6 (1) \\ 5 x_{1} + 2 x_{2} + x_{4} = 20 (2) \\ x_{1}, x_{2} x_{3}, x_{4} \geq 0 (3) \end{array}$ $\begin{array}{l} max z = 3 x_{1} + 2 x_{2} (0) \\ subject to : \\ x_{1} + x_{2} + x_{3} = 6 (1) \\ 5 x_{1} + 2 x_{2} + x_{4} = 20 (2) \\ x_{1}, x_{2} x_{3}, x_{4} \geq 0 (3) \end{array}$

si13_e (17.11)

Step 1: Find an initial FBS for the LP problem.

An initial basic solution can be obtained by assigning values equal to zero to decision variables x₁ and x₂ (nonbasic variables).

Note that the values of the basic variables (x₃, x₄) can be obtained immediately from equation system represented by Expression (17.11), since each equation has only one basic variable with coefficient 1, and each basic variable appears in only one equation. Moreover, since the objective function starts to be written based on each one of the nonbasic variables, the optimality test can easily be applied in step 2. The complete result of the initial solution is:

NBV = {x₁, x₂} and BV = {x₃, x₄}

Nonbasic solution: x₁ = 0 and x₂ = 0

Feasible basic solution: x₃ = 6 and x₄ = 20

Solution: {x₁, x₂, x₃, x₄} = {0, 0, 6, 20}

Objective function: z = 0

This solution corresponds to vertex A of the feasible region shown in Example 17.8 of Section 17.3, as presented in Fig. 17.10.

Step 2: Optimality test

We can say that the initial FBS obtained in step 1 is not optimal, since the coefficients of the nonbasic variables x₁ and x₂ in the objective function of equation system represented by Expression (17.11) are positive. If any of the variables stops taking on value zero and starts taking on a positive value, there will be a positive increase in the value of objective function z. Thus, it is possible to obtain a better adjacent FBS.

Iteration: Determine a better adjacent FBS.

Each of the three steps to be implemented in this iteration is shown.

1. Nonbasic variable that will go into the base.

According to equation system represented by Expression (17.11), we can see that variable x₁ has a greater positive coefficient in the objective function when compared to variable x₂, thus, generating a greater positive increase in z if the same measurement units were considered for x₁ and x₂. So, the nonbasic variable chosen to go into the base is x₁:

NBV = $\{\overset{⇑}{x_{1}}, x_{2}\}$ $\{\overset{⇑}{x_{1}}, x_{2}\}$

2. Basic variable that will leave the base.

To select the basic variable that will leave the base, we must choose the one that limits the increase of the nonbasic variable chosen in the previous step to go into the base (x₁). In order to do that, first, we must assign the value zero to the variables that remained nonbasic (in this case, only x₂) in all the equations. From then on, we can obtain the equations of each one of the basic variables based on the nonbasic variable chosen to go into the base (x₁). Since all the basic variables must take on non-negative values, by inserting the inequality sign ≥ 0 in each one of the constraints, we can identify the basic variable that limits the increase of x₁.

Therefore, by assigning value zero to variable x₂ in Equations (1) and (2) of equation system represented by Expression (17.11), we can obtain the equations of basic variables x₃ and x₄ based on x₁:

$x_{3} = 6 - x_{1}$ $x_{3} = 6 - x_{1}$

$x_{4} = 20 - 5 x_{1}$ $x_{4} = 20 - 5 x_{1}$

Since variables x₃ and x₄ must take on non-negative values, then:

$x_{3} = 6 - x_{1} \geq 0 \Rightarrow x_{1} \leq 6$ $x_{3} = 6 - x_{1} \geq 0 \Rightarrow x_{1} \leq 6$

$x_{4} = 20 - 5 x_{1} \geq 0 \Rightarrow x_{1} \leq 4$ $x_{4} = 20 - 5 x_{1} \geq 0 \Rightarrow x_{1} \leq 4$

We can conclude that the variable that limits the increase of x₁ is variable x₄, since the maximum value that x₁ can reach from x₄ is smaller when compared to variable x₃ (4 < 6). Hence, the basic variable chosen to leave the base is x₄:

BV = $\{x_{3}, \overset{⇑}{x_{4}}\}$ $\{x_{3}, \overset{⇑}{x_{4}}\}$

3. Transform the equation system by using the Gauss-Jordan elimination method and recalculate the basic solution.

As shown in the two previous steps, variable x₁ enters the base instead of variable x₄, and it will generate a better adjacent basic solution. Therefore, the set of nonbasic variables and the set of basic variables becomes:

NBV = {x₂, x₄} and BV = {x₁, x₃}

In this phase, we try to recalculate the values of the new feasible basic solution. Since x₄ represents the new nonbasic variable in the adjacent solution, jointly with x₂ that remained nonbasic, we have x₂ = 0 and x₄ = 0. From then on, the values of basic variables x₁ and x₃ of the adjacent solution must be recalculated, besides the value of objective function z.

First, the equation system must be converted, through basic operations, into a more convenient form, by using the Gauss-Jordan elimination method, such that each equation has only one basic variable (x₁ or x₃) with a coefficient equal to 1, each basic variable appears in only one equation, and such that the objective function can be written based on nonbasic variables x₂ and x₄.

In order to do that, the coefficients of variable x₁ in the current equation system represented by Expression (17.11) must be transformed from 3, 1, and 5 (Equations (0), (1), and (2), respectively) to 0, 0, and 1 (coefficients of variable x₄ in the current equation system). According to Hillier and Lieberman (2005), the two basic algebraic operations to be used are:

(a) Multiply (or divide) an equation by a constant different from zero.
(b) Add (or subtract) a multiple of an equation before (or after) another equation.

First, let’s convert the coefficient of variable x₁ in Equation (2) of Expression (17.11) from 5 to 1. In order to do that, we just need to divide Equation (2) by 5, such that the new Expression (17.12) starts to be written based on a single basic variable (x₁) with coefficient 1:

$x_{1} + \frac{2}{5} x_{2} + \frac{1}{5} x_{4} = 4$ $x_{1} + \frac{2}{5} x_{2} + \frac{1}{5} x_{4} = 4$

si20_e (17.12)

Another transformation must be carried out so that we can convert the coefficient of variable x₁ in Equation (1) of Expression (17.11) from 1 to 0. To do that, we just need to subtract Expression (17.12) from Equation (1) of Expression (17.11), such that the new Expression (17.13) starts to be written based on a single basic variable (x₃) with coefficient 1:

$\frac{3}{5} x_{2} + x_{3} - \frac{1}{5} x_{4} = 2$ $\frac{3}{5} x_{2} + x_{3} - \frac{1}{5} x_{4} = 2$

si21_e (17.13)

Finally, we must convert the coefficient of variable x₁ in the objective function [Equation (0) of Expression (17.11)] from 3 to 0. To do that, we just need to multiply Expression (17.12) by 3 and subtract it from Equation (0) of Expression (17.11), such that new Expression (17.14) starts to be written based on x₂ and x₄:

$z = \frac{4}{5} x_{2} - \frac{3}{5} x_{4} + 12$ $z = \frac{4}{5} x_{2} - \frac{3}{5} x_{4} + 12$

si22_e (17.14)

The complete equation system, obtained after we applied the Gauss-Jordan elimination method, is:

$\begin{array}{l} (0) z = \frac{4}{5} x_{2} - \frac{3}{5} x_{4} + 12 \\ (1) \frac{3}{5} x_{2} + x_{3} - \frac{1}{5} x_{4} = 2 \\ (2) x_{1} + \frac{2}{5} x_{2} + \frac{1}{5} x_{4} = 4 \end{array}$ $\begin{array}{l} (0) z = \frac{4}{5} x_{2} - \frac{3}{5} x_{4} + 12 \\ (1) \frac{3}{5} x_{2} + x_{3} - \frac{1}{5} x_{4} = 2 \\ (2) x_{1} + \frac{2}{5} x_{2} + \frac{1}{5} x_{4} = 4 \end{array}$

si23_e (17.15)

From the new equation system represented by Expression (17.15), it is possible to obtain the new values of x₁, x₃ , and z immediately. The complete result of the new solution is:

NBV = {x₂, x₄} and BV = {x₁, x₃}

Nonbasic solution: x₂ = 0 and x₄ = 0

Feasible basic solution: x₁ = 4 and x₃ = 2

Solution: {x₁, x₂, x₃, x₄} = {4, 0, 2, 0}

Objective function: z = 12

This solution corresponds to vertex B of the feasible region shown in Example 17.8 of Section 17.3 (Fig. 17.10). Thus, there was a movement from extreme point A to point B (A → B).

Therefore, it was possible to obtain a better adjacent FBS, since there was a positive increase in z compared to the current FBS. The adjacent FBS obtained in this iteration becomes the current FBS.

Step 2: Optimality test

The current FBS is not optimal yet, since the coefficient of nonbasic variable x₂ in Equation (0) of Expression (17.15) is positive. If this variable starts to take on any positive value, there will be a positive increase in the value of objective function z. Thus, it is possible to obtain a better adjacent FBS.

Iteration 2: Determine a better adjacent FBS.

The three steps to be implemented to determine a new adjacent FBS are:

1. Nonbasic variable that will go into the base.

According to the new equation system represented by Expression (17.15), we can see that variable x₂ is the only one with a positive coefficient in Equation (0), and it will generate a positive increase in objective function z for any positive value that variable x₂ can assume. So, the variable chosen to go from the set of nonbasic variables to the set of basic variables is x₂:

NBV = $\{\overset{⇑}{x_{2}}, x_{4}\}$ $\{\overset{⇑}{x_{2}}, x_{4}\}$

2. Basic variable that will leave the base.

The basic variable that will leave the base is the one that limits the increase of the nonbasic variable chosen in the previous step to go into the base (x₂). By assigning value zero to the variable that remained nonbasic (x₄ = 0), in each one of Equations (1) and (2) of Expression (17.15), it is possible to obtain the equations of each one of the basic variables x₁ and x₃ of the current basic solution based on the nonbasic variable chosen to go into the base (x₂):

$x_{1} = 4 - \frac{2}{5} x_{2}$ $x_{1} = 4 - \frac{2}{5} x_{2}$

si25_e

$x_{3} = 2 - \frac{3}{5} x_{2}$ $x_{3} = 2 - \frac{3}{5} x_{2}$

si26_e

Since variables x₁ and x₃ must take on non-negative values, then:

$x_{1} = 4 - \frac{2}{5} x_{2} \geq 0 \Rightarrow x_{2} \leq 10$ $x_{1} = 4 - \frac{2}{5} x_{2} \geq 0 \Rightarrow x_{2} \leq 10$

si27_e

$x_{3} = 2 - \frac{3}{5} x_{2} \geq 0 \Rightarrow x_{2} \leq \frac{10}{3}$ $x_{3} = 2 - \frac{3}{5} x_{2} \geq 0 \Rightarrow x_{2} \leq \frac{10}{3}$

si28_e

We can conclude that the variable that limits the increase of x₂ is variable x₃, since the maximum value that x₂ can assume from x₃ is smaller when compared to variable x₁. Therefore, the basic variable chosen to leave the base is x₃:

BV = $\{x_{1}, \overset{⇑}{x_{3}}\}$ $\{x_{1}, \overset{⇑}{x_{3}}\}$

3. Transform the equation system by using the Gauss-Jordan elimination method and recalculate the basic solution.

As shown in the two previous steps, variable x₂ enters the base instead of variable x₃, and it will generate a better adjacent basic solution. Thus, the set of nonbasic variables and the set of basic variables becomes:

NBV = {x₃, x₄} and BV = {x₁, x₂}

Before calculating the values of the new basic solution, the equation system must be converted by using the Gauss-Jordan elimination method.

In this case, the coefficients of variable x₂ in the current equation system represented by Expression (17.15) must be transformed from 4/5, 3/5, and 2/5 (Equations (0), (1), and (2), respectively) to 0, 1, and 0 (coefficients of variable x₃ in the current equation system), through basic algebraic operations.

First, let’s convert the coefficient of variable x₂ in Equation (1) of Expression (17.15) from 3/5 to 1. To do that, we just need to multiply Equation (1) by 5/3, such that the new Expression (17.16) starts to be written based on a single basic variable (x₂) with coefficient 1:

$x_{2} + \frac{5}{3} x_{3} - \frac{1}{3} x_{4} = \frac{10}{3}$ $x_{2} + \frac{5}{3} x_{3} - \frac{1}{3} x_{4} = \frac{10}{3}$

si30_e (17.16)

Analogously, we must convert the coefficient of variable x₂ in Equation (2) of Expresion (17.15) from 2/5 to 0. In order to do that, we just need to multiply Expression (17.16) by 2/5 and subtract it from Equation (2) of Expression (17.15), such that the new Expression (17.17) starts to be written based on a single basic variable (x₁) with coefficient 1:

$x_{1} - \frac{2}{3} x_{3} + \frac{1}{3} x_{4} = \frac{8}{3}$ $x_{1} - \frac{2}{3} x_{3} + \frac{1}{3} x_{4} = \frac{8}{3}$

si31_e (17.17)

Finally, we must convert the coefficient of variable x₂ in the objective function [Equation (0) of Expression (17.15)] from 4/5 to 0. To do that, we just need to multiply Expresion (17.16) by 4/5 and subtract it from Equation (0) of Expression (17.15), such that the new Expression (17.18) starts to be written based on x₃ and x₄:

$z = - \frac{4}{3} x_{3} - \frac{1}{3} x_{4} + \frac{44}{3}$ $z = - \frac{4}{3} x_{3} - \frac{1}{3} x_{4} + \frac{44}{3}$

si32_e (17.18)

The complete equation system is represented in (17.19):

$\begin{array}{l} (0) z = - \frac{4}{3} x_{3} - \frac{1}{3} x_{4} + \frac{44}{3} \\ (1) x_{2} + \frac{5}{3} x_{3} - \frac{1}{3} x_{4} = \frac{10}{3} \\ (2) x_{1} - \frac{2}{3} x_{3} + \frac{1}{3} x_{4} = \frac{8}{3} \end{array}$ $\begin{array}{l} (0) z = - \frac{4}{3} x_{3} - \frac{1}{3} x_{4} + \frac{44}{3} \\ (1) x_{2} + \frac{5}{3} x_{3} - \frac{1}{3} x_{4} = \frac{10}{3} \\ (2) x_{1} - \frac{2}{3} x_{3} + \frac{1}{3} x_{4} = \frac{8}{3} \end{array}$

si33_e (17.19)

From the new equation system represented by Expression (17.19), it is possible to obtain the new values of x₁, x₂ , and z immediately. The complete result of the new solution is:

NBV = {x₃, x₄} and BV = {x₁, x₂}

Nonbasic solution: x₃ = 0 and x₄ = 0

Feasible basic solution: x₁ = 8/3 = 2.67 and x₂ = 10/3 = 3.33

Solution: {x₁, x₂, x₃, x₄} = {8/3, 10/3, 0, 0}

Objective function: z = 44/3 = 14.67

This solution corresponds to vertex D of the feasible region shown in Fig. 17.10. The direction in which z increases, from the initial solution, goes through vertices A → B → D of the graphical solution.

Hence, it was possible to obtain a better adjacent FBS, since there was a positive increase in z compared to the current FBS. The adjacent FBS obtained in this iteration becomes the current FBS.

Step 2: Optimality test

The current FBS is the optimal one, since the coefficients of nonbasic variables x₃ and x₄ in Equation (0) of Expression (17.19) are negative. Therefore, it is no longer possible to have a positive increase in the value of objective function z, concluding the algorithm of Example 17.9 here.

17.4.3 Tabular Form of the Simplex Method for Maximization Problems

The previous section presented the analytical procedure of the Simplex method to solve a linear programming maximization problem. This section shows the Simplex method in tabular form. To understand the logic of the Simplex algorithm, it is important to use the Simplex method in an analytical way. However, when the calculation is done manually, it is more convenient to use the tabular form. The tabular form uses the same concepts presented in Section 17.4.2, however, in a more practical way.

As presented in Section 16.4.1 of the previous chapter, the standard form of a general model of linear programming maximization is:

$\begin{array}{l} max z = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n} \\ subject to: \\ a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ ⋮ ⋮ ⋮ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{mn} x_{n} = b_{m} \\ x_{i} \geq 0, i = 1, 2, \dots, m \end{array}$ $\begin{array}{l} max z = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n} \\ subject to: \\ a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ ⋮ ⋮ ⋮ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{mn} x_{n} = b_{m} \\ x_{i} \geq 0, i = 1, 2, \dots, m \end{array}$

si34_e (17.20)

This same model can be represented in tabular form:

According to Box 17.1, we can see that maximization function z, in tabular form, starts being rewritten as z − c₁x₁ −c₂x₂ − … − c_nx_n = 0. The columns in the middle show the coefficients of the variables on the left-hand side of each equation, in addition to the coefficient of z. The constants on the right-hand side of each equation are represented in the last column.

Box 17.1

General Linear Programming Model in Tabular Form

Equation	Coefficients					Constant
	z	x₁	x₂	…	x_n
0	1	− c₁	− c₂	…	−c_n	0
1	0	a₁₁	a₁₂	…	a_1n	b₁
2	0	a₂₁	a₂₂	…	a_2n	b₂
⋮	⋮	⋮	⋮		⋮	⋮
m	0	a_m1	a_m2	…	a_mn	b_m

Unlabelled Table

Each one of the steps of the general algorithm described in Figs. 17.11 and 17.12 is rewritten in Fig. 17.14, in a very detailed way, for solving linear programming maximization problems through the tabular form of the Simplex method. The logic presented in this section is the same as the analytical solution for the Simplex method, however, instead of using an algebraic equation system, the solution is calculated directly in the tabular form, by using the concepts of pivot column, pivot row, and pivot number that will be defined throughout the algorithm.

Example 17.9 of the previous section presented the solution for a linear programming problem through the analytical solution for the Simplex method. The same exercise will be solved in Example 17.10 through the tabular form of the Simplex method.

Example 17.10

Solve the problem by using the tabular form of the Simplex method.

si35_e (17.21)

Solution

The maximization problem must also be in the standard form:

$\begin{array}{l} max z = 3 x_{1} + 2 x_{2} (0) \\ subject to : \\ x_{1} + x_{2} + x_{3} = 6 (1) \\ 5 x_{1} + 2 x_{2} + x_{4} = 20 (2) \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 (3) \end{array}$ $\begin{array}{l} max z = 3 x_{1} + 2 x_{2} (0) \\ subject to : \\ x_{1} + x_{2} + x_{3} = 6 (1) \\ 5 x_{1} + 2 x_{2} + x_{4} = 20 (2) \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 (3) \end{array}$

si36_e (17.22)

In the tabular form, maximization function z starts to be written as:

$z = 3 x_{1} + 2 x_{2} \Rightarrow z - 3 x_{1} - 2 x_{2} = 0$ $z = 3 x_{1} + 2 x_{2} \Rightarrow z - 3 x_{1} - 2 x_{2} = 0$

Table 17.E.1 shows the tabular form of equation system represented by Expression (17.22):

Table 17.E.1

Initial Tabular Form of Example 17.10
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
z	0	1	− 3	− 2	0	0	0
x₃	1	0	1	1	1	0	6
x₄	2	0	5	2	0	1	20

Unlabelled Table

From Table 17.E.1, we can see that a new column was added when we compare it to Box 17.1. The first column shows the basic variables considered in each phase (the initial basic variables will be x₃ and x₄).

Step 1: Find an initial FBS

Decision variables x₁ and x₂ were selected for the initial set of nonbasic variables, thus, representing the origin of feasible region (x₁, x₂) = (0, 0). On the other hand, the set of basic variables is represented by x₃ and x₄:

NBV = {x₁, x₂} and BV = {x₃, x₄}

The feasible basic solution can immediately be obtained from Table 17.E.1:

Feasible basic solution: x₃ = 6 and x₄ = 20 with z = 0

Solution: {x₁, x₂, x₃, x₄} = {0, 0, 6, 20}

Step 2: Optimality test

Since the coefficients of x₁ and x₂ are negative in row 0, the current FBS is not optimal, because a positive increase in x₁ or x₂ will result in an adjacent FBS better than the current FBS.

Iteration 1: Determine a better adjacent FBS.

Each iteration has three steps:

1. Determine the nonbasic variable that will go into the base.

We have to choose the variable with the highest negative coefficient in Equation (0) of Table 17.E.1. For the problem in question, the variable with the highest unitary contribution to objective function z is x₁ (3 > 2). Therefore, variable x₁ is selected to enter the base, and this variable’s column is the pivot column.

2. Determine the basic variable that will leave the base.

Here, we are trying to select the basic variable that will leave the base (and will become null), which is the one that limits the increase of x₁. The results of the three phases needed to choose the variable, from Table 17.E.1, are shown, and can also be seen in Table 17.E.2:

(a) The positive coefficients selected from the pivot column (column of variable x₁) are coefficients 1 and 5 (Equations (1) and (2), respectively).
(b) For Equation (1), divide constant 6 by coefficient 1 from the pivot column. For Equation (2), divide constant 20 by coefficient 5.
(c) The row with the smallest quotient is Equation (2) (4 < 6). Therefore, the variable chosen to leave the base is x₄.

Step 1 (determining the variable that enters the base) and the three phases of Step 2 listed to determine the variable that leaves the base, are shown in Table 17.E.2.

Table 17.E.2

Determining the Variable that Enters and Leaves the Base in the First Iteration

Quotient 4 of Equation (2) represents the maximum value that variable x₁ can take on in this equation (5x₁ + x₄ = 20), if variable x₄ starts taking on value zero (x₄ = 0). On the other hand, quotient 6 represents the maximum value that variable x₁ can take on in Equation (1) (x₁ + x₃ = 6), considering x₃ = 0. Since we want to maximize the value of x₁, we choose, to leave the base and assume a null value, variable x₄ that limits its increase.

The pivot row and the pivot column are highlighted in Table 17.E.2. The pivot number (intersection of the pivot row and the pivot column) is 5.

3. Transform the current tabular form by using the Gauss-Jordan elimination method and recalculate the basic solution.

In the same way as in the analytical procedure, the coefficients of variable x₁ in the current tabular form (Table 17.E.2) must be transformed from −3, 1, and 5 (Equations (0), (1), and (2), respectively) to 0, 0, and 1 (coefficients of variable x₄ in the current tabular form), through basic operations (Gauss-Jordan elimination method), such that the values of the new basic variables and of objective function z can be obtained directly from the new tabular form.

The new tabular form is obtained after the following basic operations:

(a) New pivot row = current pivot row ÷ pivot number
(b) For the other rows, including z:
$New row = (current row) - (coefficient of the pivot column of the current row) \times (new pivot row)$ $New row = (current row) - (coefficient of the pivot column of the current row) \times (new pivot row)$

By applying the first operation in the current tabular form (divide Equation (2) by 5), we obtain the new pivot row, as shown in Table 17.E.3:

Table 17.E.3

New Pivot Row (iteration 1)

Since variable x₁ entered the base instead of variable x₄, the column of the basic variable in the new pivot row must be altered, as shown in Table 17.E.3.

Phase (b) will be applied to the other lines [Equations (0) and (1)].

We will begin with Equation (1) that has a positive coefficient in the pivot column (+ 1). First, we multiply this coefficient (+ 1) by the new pivot row (Equation (2) from Table 17.E.3). This product is then subtracted from current Equation (1), resulting in new Equation (1):

	x₁	x₂	x₃	x₄	Constant
Equation (1)	1	1	1	0	6
Equation (2) × (+ 1)	1	2/5	0	1/5	4
Subtraction:	0	3/5	1	− 1/5	2

Unlabelled Table

New Equation (1) is rewritten in Table 17.E.4:

Table 17.E.4

Phase (b) for Obtaining New Equation (1) (iteration 1)

Phase (b) is also applied to Equation (0) that has a negative coefficient in the pivot column (− 3). First, we multiply this coefficient’s value (− 3) by the new pivot row (Equation (2) from Table 17.E.3). This product is then subtracted from current Equation (0), resulting in new Equation (0):

	x₁	x₂	x₄	Constant
Equation (0)	− 3	− 2	0	0
Equation (2) × (− 3)	− 3	− 6/5	− 3/5	− 12
Subtraction:	0	− 4/5	3/5	12

Unlabelled Table

The new tabular form, after applying the basic operations described, is presented in Table 17.E.5:

Table 17.E.5

New Tabular Form After the Gauss-Jordan Elimination Method Is Used (Iteration 1)
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
z	0	1	0	− 4/5	0	3/5	12
x₃	1	0	0	3/5	1	− 1/5	2
x₁	2	0	1	2/5	0	1/5	4

Unlabelled Table

From the new tabular form (Table 17.E.5), it is possible to obtain the new values of x₁, x₃, and z immediately.

The new feasible basic solution is x₁ = 4 and x₃ = 2 with z = 12.

The new solution is {x₁, x₂, x₃, x₄} = {4, 0, 2, 0}.

Step 2: Optimality test

As shown in Table 17.E.5, Equation (0) starts being rewritten based on the new nonbasic variables (x₂ and x₄), such that the optimality test can easily be verified.

The current FBS is not optimal yet, because the coefficient of x₂ in Equation (0) in Table 17.E.5 is negative. Any positive increase in x₂ will result in a positive increase in the value of objective function z, such that a better adjacent FBS can be obtained.

Iteration 2: Determine a better adjacent FBS.

The three steps to be implemented in this iteration are:

1. Determine the nonbasic variable that will go into the base.

According to the new tabular form (Table 17.E.5), we can see that variable x₂ is the only one with a negative coefficient in Equation (0). Thus, the variable chosen to go into the base is x₂. The column of variable x₂ becomes the pivot column.

2. Determine the basic variable that will leave the base.

The basic variable chosen to leave the base (and become null) is the one that limits the increase of x₂. The results of the three phases needed to choose the variable, from Table 17.E.5, are shown, and can also be seen in Table 17.E.6:

(a) The positive coefficients selected from the pivot column (column of variable x₂) are coefficients 3/5 and 2/5 (Equations (1) and (2), respectively).
(b) For Equation (1), divide constant 2 by coefficient 3/5. For Equation (2), divide constant 4 by coefficient 2/5.
(c) The row with the smallest quotient is Equation (1) (10/3 < 10). Therefore, the variable chosen to leave the base is x₃.

Step 1 (determining the variable that enters the base) in addition to the three phases of Step 2 listed, to determine the variable that leaves the base, are shown in Table 17.E.6.

Table 17.E.6

Determining the Variable that Enters and Leaves the Base in the Second Iteration

The row of variable x₃ [Equation (1)] becomes the pivot row. The pivot number is 3/5.

3. Transform the current tabular form by using the Gauss-Jordan elimination method and recalculate the basic solution.

The coefficients of variable x₂ in the current tabular form (Table 17.E.6) must be transformed from -4/5, 3/5, and 2/5 (Equations (0), (1), and (2), respectively) to 0, 1, and 0 (coefficients of variable x₃ in the current tabular form), such that the values of the new basic variables and of objective function z can be obtained directly in the new tabular form.

In the same way as in the first iteration, the new tabular form is obtained after the following basic operations:

(a) New pivot row = current pivot row ÷ pivot number
(b) For the other rows, including z:
$New row = (current row) - (coefficient of the pivot column of the current row) \times (new pivot row)$ $New row = (current row) - (coefficient of the pivot column of the current row) \times (new pivot row)$

By applying the first operation in the current tabular form (divide Equation (1) by 3/5), we obtain the new pivot row, as shown in Table 17.E.7:

Table 17.E.7

New Pivot Row (iteration 2)

Since variable x₂ entered the base instead of variable x₃, the column of the basic variable in the new pivot row must be altered, as shown in Table 17.E.7.

Phase (b) will be applied to the other lines [Equations (0) and (2)].

Let’s begin with Equation (2) that has a positive coefficient in the pivot column (2/5). First, we multiply this coefficient (2/5) by the new pivot row (Equation (1) from Table 17.E.7). This product is then subtracted from current Equation (2), resulting in new Equation (2):

	x₁	x₂	x₃	x₄	Constant
Equation (2)	1	2/5	0	1/5	4
Equation (1) × (2/5)	0	2/5	2/3	− 2/5	4/3
Subtraction:	1	0	− 2/3	1/3	8/3

Unlabelled Table

New Equation (2) appears in Table 17.E.8:

Table 17.E.8

Tabular Form With New Equation (2) (iteration 2)

Phase (b) is also applied to Equation (0) that has a negative coefficient in the pivot column (-4/5). First, we multiply the value of this coefficient (-4/5) by the new pivot row (Equation (1) from Table 17.E.7). This product is then subtracted from current Equation (0), resulting in new equation (0):

	x₂	x₃	x₄	Constant
Equation (0)	− 4/5	0	3/5	12
Equation (1) × (− 4/5)	− 4/5	− 4/3	4/15	− 8/3
Subtraction:	0	4/3	1/3	44/3

Unlabelled Table

The new tabular form, after the application of the Gauss-Jordan elimination method, is presented in Table 17.E.9:

Table 17.E.9

New Tabular Form After the Gauss-Jordan Elimination Method Is Used (iteration 2)
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
z	0	1	0	0	4/3	1/3	44/3
x₂	1	0	0	1	5/3	− 1/3	10/3
x₁	2	0	1	0	− 2/3	1/3	8/3

Unlabelled Table

From Table 17.E.9, we can obtain the new values of x₁, x₂, and z immediately.

The new feasible basic solution is x₁ = 8/3 and x₂ = 10/3 with z = 44/3.

The new solution is {x₁, x₂, x₃, x₄} = {8/3, 10/3, 0, 0}.

Step 2: Optimality test

The current FBS is the optimal one, because the coefficients of nonbasic variables x₃ and x₄ in Equation (0) in Table 17.E.9 are positive.

17.4.4 The Simplex Method for Minimization Problems

The Simplex method can also be used for solving linear programming minimization problems. The minimization problems discussed in this section will be solved through the tabular form. There are two ways of solving a minimization problem through the Simplex method:

Solution 1

Transform a minimization problem into a maximization problem and use the same procedure described in Section 17.4.3. As presented in Expression (16.6) in Section 16.4.3 of the previous chapter, a minimization problem can be converted into another maximization problem through the following transformation:

$min z = f (x_{1} x_{2} \dots x_{n}) \Leftrightarrow max - z = - f (x_{1} x_{2} \dots x_{n})$ $min z = f (x_{1} x_{2} \dots x_{n}) \Leftrightarrow max - z = - f (x_{1} x_{2} \dots x_{n})$

(17.23)

Solution 2

Adapt the procedure described in Section 17.4.3 to linear programming minimization problems.

Fig. 17.14 presented the detailed steps for the general algorithm described in Figs. 17.11 and 17.12, for solving linear programming maximization problems in the tabular form. To solve LP minimization problems through the tabular form, Step 2 (optimality test) and Step 1 of each iteration (determining the nonbasic variable that will go into the base) must be adapted from Fig. 17.14, since their decisions are based on Equation (0) of the objective function. Fig. 17.15 shows the adjustments in Step 2 and in Step 1 of each iteration in relation to Fig. 17.14 for solving LP minimization problems through the tabular form. These adjustments can be found in Fig. 17.15.

As shown in Fig. 17.15, except for Step 2 (optimality test) and Step 1 of each iteration (determining the non-basic variable that will go into the base), we can see that the other steps are the same as the ones presented in Fig. 17.14 for maximization problems.

Example 17.11

Consider the following linear programming minimization problem:

$\begin{array}{l} min z = 4 x_{1} - 2 x_{2} \\ subject to : \\ 2 x_{1} + x_{2} \leq 10 \\ x_{1} - x_{2} \leq 8 \\ x_{1}, x_{2} \geq 0 \end{array}$ $\begin{array}{l} min z = 4 x_{1} - 2 x_{2} \\ subject to : \\ 2 x_{1} + x_{2} \leq 10 \\ x_{1} - x_{2} \leq 8 \\ x_{1}, x_{2} \geq 0 \end{array}$

si41_e (17.24)

Determine the optimal solution for the problem.

Solution 1

First, in order for the problem represented by Expression (17.24) to be in the standard form, slack variables must be introduced into each one of the model constraints. The problem can also be rewritten from a maximization function by using Expression (17.23):

$\begin{array}{l} max - z = - 4 x_{1} + 2 x_{2} \\ subject to : \\ 2 x_{1} + x_{2} + x_{3} = 10 \\ x_{1} - x_{2} + x_{4} = 8 \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{array}$ $\begin{array}{l} max - z = - 4 x_{1} + 2 x_{2} \\ subject to : \\ 2 x_{1} + x_{2} + x_{3} = 10 \\ x_{1} - x_{2} + x_{4} = 8 \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{array}$

si42_e (17.25)

The initial tabular form that represents equation system in Expression (17.25) is:

Table 17.E.10

Initial Tabular Form of Equation System Represented by Expression (17.25)
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
z	0	− 1	4	− 2	0	1/3	44/3
x₃	1	0	2	1	5/3	− 1/3	10/3
x₄	2	0	1	− 1	− 2/3	1/3	8/3

Unlabelled Table

The initial set of nonbasic variables is represented by x₁ and x₂, while the initial set of basic variables is represented by x₃ and x₄. Initial solution {x₁, x₂, x₃, x₄} = {0, 0, 10, 8} is not optimal, since the coefficient of nonbasic variable x₂ in Equation (0) is negative.

To determine a better adjacent FBS, variable x₂ enters the base (greatest negative coefficient) instead of variable x₄, which is the only one that limits the increase of x₂, as seen in Table 17.E.11.

Table 17.E.11

Variable That Enters and Leaves the Base in the First Iteration

The new tabular form, after the Gauss-Jordan elimination method is used, is:

Table 17.E.12

New Tabular Form Using the Gauss-Jordan Elimination Method (iteration 1)
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
z	0	− 1	8	0	2	0	20
x₂	1	0	2	1	1	0	10
x₄	2	0	3	0	1	1	18

Unlabelled Table

From Table 17.E.12, we can obtain the new values of x₂, x₄, and z immediately. The results of the new feasible basic solution are x₂ = 10 and x₄ = 18 with z = − 20. The new solution can be represented by {x₁, x₂, x₃, x₄} = {0, 10, 0, 18}.

The new basic solution obtained is the optimal one, since all the coefficients of the nonbasic variables in Equation (0) are non-negative.

Solution 2

In order for the Simplex method to be applied, the initial minimization problem described in Expression (17.24) must be in the standard form:

$\begin{array}{l} min z = 4 x_{1} - 2 x_{2} \\ subject to \\ 2 x_{1} + x_{2} + x_{3} = 10 \\ x_{1} - x_{2} + x_{4} = 8 \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{array}$ $\begin{array}{l} min z = 4 x_{1} - 2 x_{2} \\ subject to \\ 2 x_{1} + x_{2} + x_{3} = 10 \\ x_{1} - x_{2} + x_{4} = 8 \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{array}$

si43_e (17.26)

The initial tabular form of equation system in Expression (17.26) is represented in Table 17.E.13.

Table 17.E.13

Initial Tabular Form of Equation System Represented by Expression (17.26)
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
Z	0	1	− 4	2	0	0	0
x₃	1	0	2	1	1	0	10
x₄	2	0	1	− 1	0	1	18

Unlabelled Table

Analogous to solution 1, the initial set of nonbasic variables is represented by x₁ and x₂, while the initial set of basic variables is represented by x₃ and x₄. For a minimization problem, the solution is optimal if all the coefficients of the nonbasic variables in Equation (0) are nonpositive (≤ 0). Therefore, initial solution {x₁, x₂, x₃, x₄} = {0, 0, 10, 8} is not optimal, since the coefficient of nonbasic variable x₂ in Equation (0) is positive.

As shown in Table 17.E.14, variable x₂ goes into the base (greatest positive coefficient) instead of variable x₄ that is the only one with a positive coefficient in the pivot column.

Table 17.E.14

Variable That Enters and Leaves the Base in the First Iteration

After the Gauss-Jordan elimination method is used, the new tabular form is:

Table 17.E.15

New Tabular Form Using the Gauss-Jordan Elimination Method (iteration 1)
Basic Variable	Equation	Coefficients					Constant
Basic Variable	Equation	z	x₁	x₂	x₃	x₄	Constant
z	0	1	− 8	0	− 2	0	− 20
x₂	1	0	2	1	1	0	10
x₄	2	0	3	0	1	1	18

Unlabelled Table

According to Table 17.E.15, the new adjacent solution is {x₁, x₂, x₃, x₄} = {0, 10, 0, 18} with z = − 20. The basic solution obtained is optimal, because the coefficients of all the nonbasic variables in Equation (0) are nonpositive.

17.4.5 Special Cases of the Simplex Method

As presented in Section 17.2.3, an LP problem may not present a single nondegenerate optimal solution and may be characterized as one of the special cases listed:

1. Multiple optimal solutions
2. Unlimited objective function z
3. There is no optimal solution
4. Degenerate optimal solution

Section 17.2.3 discussed the graphical solution for each one of the special cases listed. This section discusses how to identify the peculiarities of each special case in one of the tabular forms (initial, intermediate, or final).

17.4.5.1 Multiple Optimal Solutions

As discussed in Section 17.2.3.1, in a linear programming problem with infinite optimal solutions, several points reach the same optimal value in the objective function. Graphically, when the objective function is parallel to an active constraint, we have a case with multiple optimal solutions.

Through the Simplex method, we can identify a case with multiple optimal solutions when, in the optimal tabular form, the coefficient of one of the nonbasic variables is null in row 0 of the objective function.

17.4.5.2 Unlimited Objective Function z

As described in 2.3.2, in this case, there is no limit to the increase of the value of at least one decision variable, resulting in a feasible region and an unlimited objective function z. For a maximization problem, the value of the objective function increases unlimitedly, while for a minimization problem, the value decreases in an unlimited way.

Through the Simplex method, we can identify a case whose objective function is unlimited when, in one of the tabular forms, a candidate nonbasic variable is prevented from entering the base because the rows of all the basic variables have nonpositive coefficients in the column of the candidate nonbasic variable.

17.4.5.3 There Is No Optimal Solution

According to Taha (2016), this case never occurs with constraints such as ≤ with non-negative constants on the right-hand side of the constraint, since the slack variables guarantee a feasible solution.

During the implementation of the Simplex algorithm in the tabular form, whenever the basic variables take on non-negative values, we have a feasible basic solution. In contrast, when at least one of the basic variables assume negative values, we have an unfeasible basic solution.

17.4.5.4 Degenerate Optimal Solution

As discussed in Section 17.2.3.4, we can identify a special case of degenerate solution, graphically, when one of the vertices of the feasible region is obtained by the intersection of more than two distinct lines.

Whereas through the Simplex method, we can identify a case with a degenerate solution when, in one of the solutions of the Simplex method, the value of one of the basic variables is null. This variable is called degenerate variable. When all the basic variables take on positive values, we say that the feasible basic solution is nondegenerate. If there is degeneration in the optimal solution, we have a case known as degenerate optimal solution.

The degenerate solution is obtained when there is a tie between at least two basic variables when choosing which one of them must leave the base (lines with the same positive quotient). When this happens, we can choose any one of them randomly. The basic variable that is not chosen remains in the base. However, its value becomes null in the new adjacent solution.

Analogously, during the solution for any linear programming problem through the Simplex method, if there is a tie when choosing the nonbasic variable that will go into the base, we should choose one of the variables randomly.

The degeneration problem is that, in some cases, the Simplex algorithm can go into a loop, resulting in the same basic solutions, since it cannot leave that solution space. In this case, the optimal solution will never be reached.

17.5 Solution by Using a Computer

In this chapter, we will discuss several ways of solving an LP problem: a) graphically, for problems with two decision variables; b) by using the analytical method, for cases in which m < n; c) through the Simplex method. Understanding each one of these methods theoretically is essential, however, to minimize the time spent solving an LP model. The same problems can be solved using a computer without having to manually do calculations and construct charts.

Currently, there are several software packages in the market for solving linear programming problems, such as, GAMS, AMPL, AIMMS, software with electronic spreadsheets (Solver in Excel, What’s Best), among others.

Software packages GAMS, AMPL, and AIMMS are algebraic modeling languages or systems (Algebraic Modeling Language—AML), that is, high-level programming languages used for solving complex and large-scale mathematical programming problems. These languages have an open interface that makes it possible to connect them to several optimization packages or to Solver (LINDO, LINGO, CPLEX, XPRESS, MINOS, OSL, etc.), which find the model’s solution. These optimization packages can also be used separately, but many of them usually run within a development environment. Let’s now discuss the main characteristics of each of these software packages.

LINDO (Linear Interactive and Discrete Optimizer), developed by LINDO Systems (http://www.lindo.com/), solves linear, nonlinear, and integer programming problems. It is very easy to use and also very fast. The complete version of the software does not have limitations regarding the number of constraints, real and integer variables. To solve linear programming problems, the Solver in LINDO uses more than one optimization method, including the Simplex method, revised Simplex, dual Simplex, and interior-point methods. Different from the Simplex algorithm, in the interior-point methods, new solutions can be found in the interior of the feasible region. The Solver in LINDO has interface with the following programming languages: Visual Basic, C, C ++, among others. A free version of the software can be downloaded directly from the website http://www.lindo.com/.

Software LINGO (Language for Interactive General Optimizer), also developed by LINDO Systems, solves linear, nonlinear, and integer programming problems quickly and effectively. The complete version of the software does not have limitations regarding the number of constraints, real and integer variables either. The Solver in LINGO also uses the Simplex method, revised Simplex, dual Simplex, and interior-points method to determine the optimal solution for a linear programming model. All input data can be read directly from LINGO. However, many times, the software uses electronic spreadsheets as interface, such as Excel. The Solver in LINGO also has interface with the following programming languages: Visual Basic, C, C ++, among others. A free version of the software can also be downloaded from the website http://www.lindo.com/.

Also developed by LINDO Systems, software What’s Best! is a module to be installed inside electronic spreadsheets as Excel, and it is used to solve linear, nonlinear, and integer programming problems. The complete version of the software does not have limitations regarding the number of constraints, real and integer variables either. The Solver in What’s Best! uses the same optimization methods as LINDO and LINGO. What’s Best! is also compatible with the VBA (Visual Basic for Applications) in Excel, thus, allowing the application of macros and programming codes. A free version of the software can also be downloaded from the website http://www.lindo.com/.

CPLEX is an optimization package that was originally developed by Robert Bixby at CPLEX Optimization. In 1997, it was purchased by ILOG and, later on (2009), by IBM. CPLEX has been widely used to solve large-scale linear, integer, and nonlinear programming problems, many times, serving as a Solver within algebraic modeling systems, such as, GAMS, AMPL, and AIMMS. The Solver in CPLEX uses the Simplex method and the interior-points method to determine the optimal solution for a linear programming problem. It has interface with the following programming languages C, C ++, C#, and Java. A free version of CPLEX can be downloaded on the website https://www.ibm.com/analytics/cplex-optimizer.

Developed by Dash Optimization Ltd., XPRESS is an optimization software that solves complex linear, nonlinear, and integer programming problems. The Solver in XPRESS allows us to choose a solution method (Simplex, dual Simplex, or interior-points method) to determine the best solution for a linear programming problem. XPRESS has an interface with the following programming languages C, C ++, Java, Visual Basic, and Net. Further information on the software can be found on the website http://www.dashoptimization.com/.

MINOS, developed by Bruce Murtagh and Michael Saunders from Stanford University, is an optimization software that solves large-scale linear and nonlinear programming problems. To solve linear programming problems, MINOS uses the Simplex method. MINOS has also been widely used as a Solver for algebraic modeling languages. It has interface with the following programming languages Fortran, C, and Matlab. Further information on MINOS can be found on the website http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm/.

Software GAMS (General Algebraic Modeling System), developed by GAMS Development Corporation, is a high-level algebraic modeling system that is being used to solve complex and large-scale linear, nonlinear, and integer programming problems. As specified previously, GAMS has an interface that connects to several optimization packages, including CPLEX, MINOS, OSL, XPRESS, LINGO, LINDO, among others. A free version of the software can be downloaded directly from the website http://www.gams.com/.

AMPL (A Mathematical Programming Language) is also an algebraic modeling language, developed by Bell laboratory to solve high complexity linear, integer, and nonlinear programming problems. AMPL has an open interface that makes it possible to connect it to several types of Solver (such as, CPLEX, MINOS, OSL, XPRESS, among others) that find the model’s optimal solution. A free version of AMPL can be downloaded directly from the website http://www.ampl.com/.

AIMMS (Advanced Integrated Multidimensional Modeling Software), developed by Paragon Decision Technology, is also a high-level algebraic modeling language that solves high complexity linear, nonlinear and integer programming problems. It uses optimization packages, such as, CPLEX, MINOS, XPRESS, among others, to determine the optimal solution for a linear programming model. It interfaces with the following programming languages C, C ++, Visual Basic, and Excel. A free version of the software can be downloaded from the website http://www.aimms.com/.

IBM’s OSL (Optimization Subroutine Library) is an optimization software that solves large-scale linear, nonlinear, and integer programming problems. The Solver in OSL uses the Simplex method and interior-point methods to determine the optimal solution for a linear programming problem. It interfaces with the programming languages C and Fortran.

Solver is an add-in in Excel that has been widely used for solving small-scale linear, nonlinear, and integer programming problems, due to its popularity and simplicity. Solver uses the Simplex algorithm to determine the optimal solution for a linear programming model. To solve nonlinear problems, Solver uses the GRG2 (Generalized Reduced Gradient) algorithm. While for integer programming problems, it uses the branch-and-bound algorithm. Solver has an interface with other programming languages, so that the final solution can be exported to another package. In the following section, we will discuss how to use it step by step.

17.5.1 Solver in Excel

Solver is capable of solving problems with up to 200 decision variables and 100 constraints. To use it, it is necessary to activate the add-in Solver in Excel.

First, we may click on the File tab and select Options (Fig. 17.16). From the dialog box Excel Options (Fig. 17.17), choose the option Add-Ins and select the name Solver Add-in. Also in Fig. 17.17, the next step consists in clicking on Go, which will open the Add-Ins dialog box shown in Fig. 17.18. Finally, confirm by clicking on Solver Add-in and OK. Thus, Solver in Excel will become available in the Data tab, in the Analyze column, as shown the Fig. 17.19.

Fig. 17.19 Availability of Solver on the Data tab.

Having selected the Solver command, the Solver Parameters dialog box will appear (Fig. 17.20). Let’s now discuss each one of its cells.

1. Set Objective

The objective cell (target cell in earlier Excel versions) is the one that contains the value of the objective function.

2. To (Equal to in earlier Excel versions)

We must choose if the objective function is a maximization (Max) or a minimization (Min) one. Solver can also use the option Value of. In this case, Solver will search for a solution whose objective function value (objective cell) is the same as or as close as possible to the value stipulated.

3. By Changing Variable Cells

Variable cells (changing cells or adjustable cells in earlier versions) refer to the model’s decision variables. They are the cells whose values vary until the model’s optimal solution is reached.

4. Subject to the Constraints

Each of the model constraints must be included by using the Add button seen in Fig. 17.20, thus, showing the Add Constraint dialog box, as shown in Fig. 17.21.

First of all, in the Cell Reference box, we must select the cell that represents the left-hand side of the constraint to be added. Select the constraint symbol (≤, = or ≥), int (integer variable) or bin (binary variable). In the Constraint box, select a constant, a reference cell or a formula with a numerical value that represents the constraint’s right-hand side. While there are new constraints to be included in the model, click on Add. The non-negativity constraints of the decision variables must also be included in this phase. In the case of the last constraint, press OK to go back to the Solver Parameters dialog box.

As shown in Fig. 17.20, for each constraint that has already been added, it is possible to change or delete it. In order to do that, we just need to select the constraint desired and click on the button Change or Delete.

Additionally, the Reset All button clears all the data regarding the current model.

Another alternative of including the non-negativity constraints is to select the Make Unconstrained Variables Non-Negative check box.

5. Select a Solving Method

For linear programming problems, we must select the Simplex LP engine. Select the GRG Nonlinear engine for smooth nonlinear problems, and select the Evolutionary engine for nonsmooth problems.

6. Options

In the Solver Parameters dialog box, it is also possible to activate the Options button, which makes the Options window available (Fig. 17.22).

From Fig. 17.22, on the All Methods tab, we can change options for all solving methods. In the Constraint Precision box, the degree of precision can be specified. The smaller the number, the higher the precision. If Use Automatic Scaling check box is selected, Solver should internally rescale the values of variables, constraints, and the objective to similar magnitudes, to reduce the impact of extremely large or small values on the accuracy of the solution process. The Show Iteration Results check box displays the values of each trial solution.

In the Solving with Integer Constraints box, if the Ignore Integer Constraints check box is selected, all integer, binary, and all different constraints are ignored. This is known as the relaxation of the integer programming problem. In the Integer Optimality (%) check box, we can type the maximum percentage difference Solver should accept between the objective value of the best integer solution found and the best known bound on the true optimal objective value before stopping.

From Solving Limits box, we can specify the maximum CPU time and the maximum number of iterations, respectively, in the Max Time (Seconds) and Iterations boxes.

Finally, the last two options are used only for problems that include integer constraints on variables, or problems that use the Evolutionary Solving Method. In the Max Subproblems box, we can specify the maximum number of subproblems and in the Max Feasible Solutions box, we can specify the maximum number of feasible solutions (https://www.solver.com/excel-solver-change-options-all-solving-methods).

7. Solve

Going back to the Solver Parameters dialog box, click on Solve, obtaining the Solver Results dialog box.

In cases in which the Solver finds a feasible solution for the problem in question, which satisfies all the model constraints, a corresponding message will appear in the Solver Results dialog box, as seen in Fig. 17.23.

Fig. 17.23 Solver Results dialog box—feasible solution.

In this case, the Solver result will appear automatically in the spreadsheet under analysis, we just need to click on OK to maintain the optimal solution found. To restore the model’s initial values, select the Restore Original Values option and, finally, click on OK. The current scenario can also be saved by using the Save Scenario button.

Solver has 3 types of report: Answer, Sensitivity, and Limits. In order for these reports to be made available in new Excel spreadsheets, we just need to select the option desired before clicking on the OK button in the Solver Results dialog box. The Answer report provides the results of the model’s optimal solution. The Limits report shows the lower and upper limits of each one of the variable cells. The Answer and Limits reports will be discussed in Section 17.5.4 and the Sensitivity analysis report in Section 17.6.4.

17.5.2 Solution of the Examples found in Section 16.6 of Chapter 16 using Solver in Excel

Each of the examples found in Section 16.6 of the previous chapter (modeling of real linear programming problems) will be solved by the Solver in Excel.

17.5.2.1 Solution of Example 16.3 of Chapter 16 (Production Mix Problem at the Venix Toys)

Example 16.3 presented in Section 16.6.1 of the previous chapter, regarding the production mix problem at Venix, a company in the toy sector, will be solved through Solver in Excel. Fig. 17.24 shows how the linear programming model must be edited in an Excel spreadsheet, so that it can be solved by Solver (see file Example3_Venix.xls).

Fig. 17.24 Production mix model at Venix Toys in Excel.

First, we can see that the unit profits of each product are represented by cells B5 and C5. Whereas the decision variables (weekly number of toy cars and tricycles to be manufactured) are represented by cells B14 and C14, respectively. The objective function is represented by cell D14 (see formula in Box 17.2). The labor availability constraints for the machining, painting, and assembly activities are represented in rows 8, 9, and 10, respectively. For instance, the labor availability constraint for the machining activity is represented by the equation 0,25x₁ + 0,5x₂ ≤ 36. In order for it to be added to the Subject to the Constraints box in the Solver Parameters dialog box, the left-hand side of the constraint must be represented in a single cell. Therefore, the term 0,25x₁ + 0,5x₂ starts to be represented by cell D8 (see formula in Box 17.2). We repeat the same procedure for the other constraints. The initial solution has the following values: x₁ = 0, x₂ = 0, and z = 0.

Box 17.2

Formula of the Objective Function and of the Total Number of Hours Used in Each Activity

Cell	Formula
D8	= B8⁎$B$14 + C8⁎$C$14
D9	= B9⁎$B$14 + C9⁎$C$14
D10	= B10⁎$B$14 + C10⁎$C$14
D14	= B5⁎$B$14 + C5⁎$C$14

For complex problems, we can use the SUMPRODUCT function directly, which multiplies the components that correspond to the intervals or matrices provided and returns the sum of these products, as shown in Box 17.3.

Box 17.3

Alternative to Box 17.2 When Using the SUMPRODUCT Function

Cell	Formula
D8	= SUMPRODUCT(B8:C8,$B$14:$C$14)
D9	= SUMPRODUCT(B9:C9,$B$14:$C$14)
D10	= SUMPRODUCT(B10:C10,$B$14:$C$14)
D14	= SUMPRODUCT(B5:C5,$B$14:$C$14)

The problem is ready to be solved by the Solver in Excel. Clicking on the Solver command, we obtain the Solver Parameters dialog box, as shown in Fig. 17.25. First, we must select the objective cell (D14), which is the one that contains the value of the objective function. Since it is a maximization problem, select the option Max. The next step consists in selecting the variable cells (B14:C14) that represent the model’s decision variables. Lastly, we must add each one of the model constraints to the Subject to the Constraints box. Regarding the labor availability constraints for each of the activities, since they are all of the same type, instead of adding them separately, they can be added simultaneously. To do that, first of all, click on the Add button. Select the cell range D8:D10 in the Cell Reference box, the symbol ≤, and the cell interval F8:F10 in the Constraint box, as shown in Fig. 17.26. To conclude the inclusion of the current constraint, let’s click on OK. Nevertheless, since the non-negativity constraint of the model’s decision variables will also be included, click on Add. Once again, the Add Constraint dialog box appears, such that the new model constraint can be included. Therefore, we select the variable cells (B14:C14) in the Cell Reference box, the symbol ≥, and value 0 to be included in the Constraint box, as seen in Fig. 17.27. Since this is the last constraint, conclude by clicking on OK.

Fig. 17.25 Solver Parameters dialog box for Example 16.3.

Fig. 17.26 Adding the labor availability constraint for the three activities.

Fig. 17.27 Adding the non-negativity constraint of the decision variables.

The non-negativity constraints can also be activated by selecting the Make Unconstrained Variables Non-Negative check box.

Since we have a linear programming problem, select the Simplex LP engine in the Select a Solving Method box.

The next step consists in clicking on the Options button, thus, obtaining the Options dialog box (Fig. 17.28). The values regarding the Constraint Precision, Max Time, and Iterations parameters will be kept. If Solver cannot find a viable solution, we must test it with a smaller precision in order to find a feasible solution. Another alternative is to increase the maximum time and the number of iterations. If the problem persists, the model must be unfeasible (Taha, 2016). Finally, click on OK to go back to the Solver Parameters dialog box.

From then on, Solver is ready to be solved. Thus, click on Solve. In case of a feasible solution, we can update the current Excel spreadsheet with the new solution by clicking on Keep Solver Solution. Fig. 17.29 shows the result of the optimal solution for Example 16.3 for Venix Toys.

Fig. 17.29 Optimal solution for the production mix problem for Venix Toys.

Therefore, we can see that the model’s optimal solution is x₁ = 70 and x₂ = 20 with z = 2, 040 ($2,040.00). The same results can be seen, in a more detailed way, in the Answer Report (see Section 17.5.4). The Limits Report of company Venix Toys will also be discussed in Section 17.5.4.

Solution using Names in a Cell or Cell Range

According to Haddad and Haddad (2004), using names in a cell or cell range makes it easier to understand the formula. To name it, we just need to click on a cell or cell range, place the desired name in the Name Box, which appears on the left-hand side of the Formula bar, and conclude by typing ENTER. Hence, the cells will be referenced by name and not by the corresponding columns and rows any longer. For example, the set of cells B5:C5 will be named Unit_profit, as seen in Fig. 17.30. Another way of doing this is by right clicking on Define Name. Thus, the New Name dialog box will appear (Fig. 17.31), such that the desired name must be added in the Name box. A third alternative is to select the Formulas tab and choose the Name Manager option (CTRL + F3), resulting in Fig. 17.32. As shown in Fig. 17.32, we can include a new name by using the New button (once again, the New Name dialog box will appear), or select an already existing cell or set of cells and click on Edit to change the current name or Delete.

Fig. 17.30 Inserting a name into a set of cells.

Note that Fig. 17.32 shows the name of each cell or cell range, its corresponding value, in addition to its(their) respective row(s) and column(s).

Therefore, each cell or cell range included in the Name Manager starts to be referenced by its(their) name(s) instead of its(their) corresponding row(s) and column(s). For example, the formulas in Box 17.3 regarding cells D8, D9, D10, and D15 start being written based on their new names, as shown in Box 17.4.

Box 17.4

Formulas From Box 17.3 Written Based on Their New Names

Cell	Formula
D8	= SUMPRODUCT(B8:C8,Quantities_produced)
D9	= SUMPRODUCT(B9:C9,Quantities_produced)
D10	= SUMPRODUCT(B10:C10,Quantities_produced)
D14	= SUMPRODUCT(Unit_profit,Quantities_produced)

Fig. 17.33 is an adaptation of Fig. 17.25, in which each cell or cell range starts being called by its respective name.

Notice that objective cell D14 starts being referred to as Total_profit, variable cells (B14:C14) and the left-hand side of the second constraint as Quantities_produced, the left-hand side of the first constraint (D8:D10) as Hours_used, and the right-hand side of the second constraint (F8:F10) as Hours_available.

17.5.2.2 Solution of Example 16.4 of Chapter 16 (Production Mix Problem at Naturelat Dairy)

Example 16.4 presented in Section 16.6.1 of the previous chapter, regarding the production mix problem at Naturelat, a dairy product company, will also be solved through the Solver in Excel. Fig. 17.34 illustrates the representation of the model in an Excel spreadsheet (see file Example4_Naturelat.xls).

The formulas used in Fig. 17.34 are shown in Box 17.5.

Box 17.5

Formulas From Fig. 17.34

Cell	Formula
G8	= SUMPRODUCT(B8:F8,$B$24:$F$24)
G9	= SUMPRODUCT(B9:F9,$B$24:$F$24)
G10	= SUMPRODUCT(B10:F10,$B$24:$F$24)
G13	= SUMPRODUCT(B13:F13,$B$24:$F$24)
G16	= SUMPRODUCT(B16:F16,$B$24:$F$24)
G17	= SUMPRODUCT(B17:F17,$B$24:$F$24)
G18	= SUMPRODUCT(B18:F18,$B$24:$F$24)
G19	= SUMPRODUCT(B19:F19,$B$24:$F$24)
G20	= SUMPRODUCT(B20:F20,$B$24:$F$24)
G24	= SUMPRODUCT(B5:F5,$B$24:$F$24)

Analogous to the Venix Toys example, names were assigned to the cells and cell ranges in Fig. 17.34, which will be used in the Solver to facilitate the understanding of the model. Fig. 17.35 shows the names assigned to the respective cells.

Fig. 17.35 Name Manager for the problem at Naturelat Dairy.

The representation of the problem at Naturelat Dairy in the Solver Parameters dialog box is shown in Fig. 17.36. Since names were assigned to the model cells, Fig. 17.36 starts being referred to by their respective names.

In Fig. 17.36, note that the constraints are sorted out in alphabetical order. The same happens with the Name Manager (Fig. 17.35).

Similar to the Venix Toys example, we selected the Make Unconstrained Variables Non-Negative check box and the Simplex LP engine in the Select a Solving Method box. The Options command remained unaltered.

Finally, click on Solve and select the option Keep Solver Solution in the Solver Results dialog box. Fig. 17.37 shows the optimal solution for the production mix model at Naturelat Dairy.

17.5.2.3 Solution of Example 16.5 of Chapter 16 (Mix Problem of Oil-South Refinery)

Example 16.5 presented in Section 16.6.2 of the previous chapter, regarding the mix problem of Oil-South Refinery, will also be solved through the Solver in Excel. Fig. 17.38 illustrates the representation of the model in an Excel spreadsheet (see file Example5_OilSouth.xls).

Rows 6 to 10 represent the constraints of the maximum or minimum percentage allowed of a certain type of oil in the composition of a certain type of gasoline. In order for all the constraints to have the same symbol (≤), the type ≥ inequalities were multiplied by (-1).

The formulas used in Fig. 17.38 are shown in Box 17.6.

Box 17.6

Formulas From Fig. 17.38

Cell	Formula
K6	= SUMPRODUCT(B6:J6,$B$26:$J$26)
K7	= SUMPRODUCT(B7:J7,$B$26:$J$26)
K8	= SUMPRODUCT(B8:J8,$B$26:$J$26)
K9	= SUMPRODUCT(B9:J9,$B$26:$J$26)
K10	= SUMPRODUCT(B10:J10,$B$26:$J$26)
K13	= SUMPRODUCT(B13:J13,$B$26:$J$26)
K14	= SUMPRODUCT(B14:J14,$B$26:$J$26)
K15	= SUMPRODUCT(B15:J15,$B$26:$J$26)
K18	= SUMPRODUCT(B18:J18,$B$26:$J$26)
K19	= SUMPRODUCT(B19:J19,$B$26:$J$26)
K20	= SUMPRODUCT(B20:J20,$B$26:$J$26)
K23	= SUMPRODUCT(B23:J23,$B$26:$J$26)
K26	= SUMPRODUCT(B4:J4,$B$26:$J$26)

In order to facilitate the understanding of the model, names were assigned to the main cells and cell ranges in Fig. 17.38, as seen in Fig. 17.39.

Having assigned the names to the cells or cell ranges of Fig. 17.38, they will be referenced by their respective names. Therefore, the representation of the problem of Oil-South Refinery in the Solver Parameters dialog box is illustrated in Fig. 17.40.

Fig. 17.40 Solver Parameters regarding the problem of Oil-South Refinery.

Note that the non-negativity constraints were activated by selecting the Make Unconstrained Variables Non-Negative check box, and the Simplex LP method was selected. The Options command remained unaltered.

Finally, click on Solve and OK to keep Solver solution. Fig. 17.41 shows the optimal solution for the mix problem of Oil-South Refinery.

17.5.2.4 Solution of Example 16.6 of Chapter 16 (Diet Problem)

Example 16.6 presented in Section 16.6.3 of the previous chapter, regarding a diet problem, will also be solved through the Solver in Excel. Fig. 17.42 represents the model in an Excel spreadsheet (see file Example6_Diet.xls).

The formulas used in Fig. 17.42 are shown in Box 17.7.

Box 17.7

Formulas From Fig. 17.42

Cell	Formula
N8	= SUMPRODUCT(B8:M8,$B$18:$M$18)
N9	= SUMPRODUCT(B9:M9,$B$18:$M$18)
N10	= SUMPRODUCT(B10:M10,$B$18:$M$18)
N11	= SUMPRODUCT(B11:M11,$B$18:$M$18)
N14	= SUMPRODUCT(B14:M14,$B$18:$M$18)
N18	= SUMPRODUCT(B5:M5,$B$18:$M$18)

The names assigned to the main cells and cell ranges of Fig. 17.42 are listed in Fig. 17.43.

Therefore, the Solver Parameters dialog box regarding the diet problem shows the names assigned to the respective cells or cell ranges, as shown in Fig. 17.44.

Fig. 17.44 Solver Parameters related to the diet problem.

Finally, click on Solve and OK to keep Solver solution. Fig. 17.45 shows the optimal solution for the diet problem.

17.5.2.5 Solution of Example 16.7 of Chapter 16 (Farmer’s Problem)

In order for Example 16.7 in Section 16.6.4 of the previous chapter (farmer’s problem) to be solved by Solver in Excel, it must be represented in an Excel spreadsheet, as shown in Fig. 17.46 (see file Example7_Farmer.xls).

Box 17.8 shows the formulas used in Fig. 17.46.

Box 17.8

Formulas Used in Fig. 17.46

Cell	Formula
G8	= SUMPRODUCT(B8:F8,$B$25:$F$25)
G11	= SUMPRODUCT(B11:F11,$B$25:$F$25)
G12	= SUMPRODUCT(B12:F12,$B$25:$F$25)
G13	= SUMPRODUCT(B13:F13,$B$25:$F$25)
G16	= SUMPRODUCT(B16:F16,$B$25:$F$25)
G19	= SUMPRODUCT(B19:F19,$B$25:$F$25)
G20	= SUMPRODUCT(B20:F20,$B$25:$F$25)
G21	= SUMPRODUCT(B21:F21,$B$25:$F$25)
G25	= SUMPRODUCT(B5:F5,$B$25:$F$25)

Fig. 17.47 shows the names assigned to the cells and cell ranges in Fig. 17.46, which will be referenced in the Solver.

Alternatively, Fig. 17.48 shows the parameters of the Solver as regards the farmer’s problem. Note that the cells and cell ranges are represented by their respective names.

Finally, click on Solve and OK to keep Solver solution. Fig. 17.49 shows the optimal solution for the farmer’s problem.

17.5.2.6 Solution of Example 16.8 of Chapter 16 (Portfolio Selection—Maximization of the Expected Return)

Example 16.8 in Section 16.6.5 of the previous chapter will also be solved through the Solver in Excel. Fig. 17.50 shows the representation of the portfolio optimization problem in an Excel spreadsheet (see file Example8_Portfolio.xls).

Box 17.9 shows the formulas used in Fig. 17.50.

Box 17.9

Formulas Used in Fig. 17.50

Cell	Formula
B9	= SUM(B18:K18)
B14	= SUMPRODUCT(B6:K6,B18:K18)
L18	= SUMPRODUCT(B5:K5,B18:K18)

Fig. 17.51 shows the names assigned to the cells and cell ranges in Fig. 17.50.

Whereas Fig. 17.52 shows the Solver parameters regarding the portfolio selection problem (maximization of the return expected), in which each cell or cell range starts being referenced by its respective name.

Finally, click on Solve and OK to keep Solver solution. Fig. 17.53 shows the optimal solution for the portfolio selection problem.

17.5.2.7 Solution of Example 16.9 of Chapter 16 (Portfolio Selection—Minimization of the Portfolio’s Mean Absolute Deviation)

Example 16.9 in Section 16.6.5 of the previous chapter that tries to determine the portfolio’s optimal composition to minimize its mean absolute deviation will be solved through the Solver in Excel. The representation of the problem in an Excel spreadsheet can be seen in Fig. 17.54 (see file Example9_Portfolio.xls).

Fig. 17.54 Representation of Example 16.9 in an Excel spreadsheet.

The calculation of the portfolio’s MAD is shown in Fig. 17.55 and can also be found in the same file Example9_Portfolio.xls. For a portfolio that has 10% of each asset in its composition, row 250 in Fig. 17.55 shows the mean absolute deviation of each asset and of the portfolio. As shown in row 250 or the formula of cell P250 in Box 17.10, the percentage of each asset in the portfolio can be multiplied directly by its mean absolute deviation, since the percentage is constant in all the periods.

Box 17.10

Main Formulas Used in Figs. 17.54 and 17.55

Cell	Formula
B9	= SUM(B18:K18)
B12	= SUMPRODUCT(B5:K5,B18:K18)
O248	= MEAN(O2:O247)
P2	= ABS(O2-$O$248)
P248	= MEAN(P2:P247)
P250	= P248⁎B18
AI250	= SUM(P250:AH250)
L18	= AI250

Box 17.10 shows the main formulas used in Figs. 17.54 and 17.55. From the formulas in cells P248 and P250, we can see the calculation of the mean absolute deviation of the first asset (BBAS3). For the other assets, we can use the same procedure.

Fig. 17.56 shows the names assigned to the cells and cell ranges in Fig. 17.54.

Whereas Fig. 17.57 presents the Solver parameters regarding the portfolio selection problem (minimization of the MAD).

Analogous to previous models, one assumes that the variables are non-negative and that the model is linear. Finally, click on Solve and OK to keep Solver solution. Fig. 17.58 shows the optimal solution for the portfolio selection problem (minimization of the MAD).

Fig. 17.58 Optimal solution for the portfolio selection problem (minimization of the MAD).

17.5.2.8 Solution of Example 16.10 of Chapter 16 (Production and Inventory Problem of Fenix&Furniture)

Example 16.10 in Section 16.6.6 of the previous chapter, regarding the production and inventory problem of Fenix&Furniture, will be solved through Solver in Excel. Fig. 17.59 illustrates the representation of the problem in an Excel spreadsheet (see file Example10_Fenix&Furniture.xls).

Note that, in the initial solution presented in Fig. 17.59, 2,000 units of each product were produced in each period. Applying the formula I_it = I_i,t − 1 + x_it − D_it, we obtain the inventory levels of each product in each period that must take on non-negative values. It is important to mention that this solution is not the optimal one.

Box 17.11 shows the formulas used in Fig. 17.59.

Box 17.11

Formulas Used in Fig. 17.59

Cell	Formula	Cell	Formula	Cell	Formula
C35	= B35 + C42-C18	C37	= B37 + C44-C20	C39	= B39 + C46-C22
D35	= C35 + D42-D18	D37	= C37 + D44-D20	D39	= C39 + D46-D22
E35	= D35 + E42-E18	E37	= D37 + E44-E20	E39	= D39 + E46-E22
F35	= E35 + F42-F18	F37	= E37 + F44-F20	F39	= E39 + F46-F22
G35	= F35 + G42-G18	G37	= F37 + G44-G20	G39	= F39 + G46-G22
H35	= G35 + H42-H18	H37	= G37 + H44-H20	H39	= G39 + H46-H22
C36	= B36 + C43-C19	C38	= B38 + C45-C21
D36	= C36 + D43-D19	D38	= C38 + D45-D21
E36	= D36 + E43-E19	E38	= D38 + E45-E21
F36	= E36 + F43-F19	F38	= E38 + F45-F21
G36	= F36 + G43-G19	G38	= F38 + G45-G21
H36	= G36 + H43-H19	H38	= G38 + H45-H21

Unlabelled Table

Fig. 17.60 shows the names assigned to the main cells and cell ranges in Fig. 17.59.

The Solver parameters regarding the production and inventory problem of Fenix&Furniture are represented in Fig. 17.61. Since names were assigned to the main cells and cell ranges, they start being referred to by their respective names.

Analogous to previous models, one assumes that the variables are non-negative and that the model is linear. Finally, click on Solve and OK to keep Solver solution. Fig. 17.62 shows the optimal solution for the production and inventory problem of Fenix&Furniture.

Fig. 17.62 Optimal solution for Fenix&Furniture.

17.5.2.9 Solution of Example 16.11 of Chapter 16 (Problem of Lifestyle Natural Juices Manufacturer)

Example 16.11 in Section 16.6.7 of the previous chapter, regarding the aggregate planning problem at Lifestyle Natural Juices, will be solved through Solver in Excel. Fig. 17.63 illustrates the representation of the problem in an Excel spreadsheet (see file Example11_Lifestyle.xls).

In the initial solution presented in Fig. 17.63, note that 1,000 additional liters were produced in July after they hired new employees in the previous month, such that the values of R_t from July to December become 5,000 (R_t = R_t − 1 + H_t − F_t). Applying the formula I_t = I_t − 1 + R_t + O_t + S_t − D_t, we obtain the inventory levels in each period. The values of the other decision variables remain null. It is important to mention that this solution is not the optimal one.

Box 17.12 shows the formulas used in Fig. 17.63.

Box 17.12

Formulas Used in Fig. 17.63

Cell	Formula
C22	= B22 + C27 + C28 + C29-C14
D22	= C22 + D27 + D28 + D29-D14
E22	= D22 + E27 + E28 + E29-E14
F22	= E22 + F27 + F28 + F29-F14
G22	= F22 + G27 + G28 + G29-G14
H22	= G22 + H27 + H28 + H29-H14
C23	= B23 + C30-C31
D23	= C23 + D30-D31
E23	= D23 + E30-E31
F23	= E23 + F30-F31
G23	= F23 + G30-G31
H23	= G23 + H30-H31
I26	= SUMPRODUCT(C6:H11,C26:H31)

Fig. 17.64 shows the names assigned to the cells and cell ranges in Fig. 17.63.

The Solver parameters regarding the aggregate planning problem at Lifestyle company are represented in Fig. 17.65. Since names were assigned to the main cells and cell ranges, they start being referenced by their respective names.

Analogous to previous models, one assumes that the variables are non-negative and that the model is linear. Finally, click on Solve and OK to keep Solver solution. Fig. 17.66 shows the optimal solution for the aggregate planning problem of Lifestyle company.

Fig. 17.66 Optimal solution for Lifestyle company.

17.5.3 Solver Error Messages for Unlimited and Infeasible Solutions

Section 17.2.3 and Section 17.4.5 presented how to identify, graphically and through the Simplex method, respectively, each one of the special cases that may happen in a linear programming problem:

1. Multiple optimal solutions
2. Unlimited objective function z
3. There is no optimal solution
4. Degenerate optimal solution

In this section, we will analyze the error messages generated in the Solver Results dialog box for cases 2 and 3 (unlimited objective function z and unfeasible solution). Special cases 1 and 4 will be discussed in Sections 17.6.4.1 and 17.6.4.2, respectively, by using the Solver Sensitivity Report.

17.5.3.1 Unlimited Objective Function z

For the maximization problem (max z = 4x₁ + 3x₂) presented in Section 17.2.3.2 (Example 17.4), the graphical solution was obtained from Fig. 17.67.

Solving the same example through Solver in Excel, an error message appears in the Solver Results dialog box: “The Objective Cell values do not converge.”

Therefore, whenever we come across a problem with an unlimited objective function, the message in Fig. 17.68 will appear.

17.5.3.2 There Is No Optimal Solution

For the maximization problem (max z = x₁ + x₂) presented in Section 17.2.3.3 (Example 17.5), the graphical solution was obtained from Fig. 17.69.

By solving Example 17.5 through the Solver in Excel, a new error message appears in the Solver Results dialog box, since we have a case in which it is not possible to find a feasible solution (see Fig. 17.70).

Fig. 17.70 Error message for a problem with an unfeasible solution.

17.5.4 Result Analysis by Using the Solver Answer and Limits Reports

Section 17.5.2 presented the Solver results for each one of the examples presented in Section 16.6 of the previous chapter (modeling of real linear programming problems), directly in Excel spreadsheets. A detailed analysis of the results can also be done through the Solver Answer, Limits, and Sensitivity Reports. As mentioned before, the Sensitivity Report will be discussed in Section 17.6. Whereas the Answer and Limits Reports will be discussed in this section for the Venix Toys problem (Example 16.3 of the previous chapter). The modeling of and solution for the problem was presented in Section 17.5.2.1 of this chapter in the same Excel spreadsheet.

17.5.4.1 Answer Report

The Answer Report provides the results of the optimal solution found by Solver in a new Excel spreadsheet. Fig. 17.71 shows the Answer Report of the problem faced by Venix Toys.

According to Fig. 17.71, we can see that the results of the Answer Report are divided into three main parts: objective cell, variable cells, and constraints.

As shown in Fig. 17.29 of Section 17.5.2.1, the maximization function z of Venix Toys’ problem is represented by objective cell D14 (Total_profit). Row 8 in Fig. 17.71 shows the original value and the final value (maximum profit) of the objective cell.

The model’s decision variables are represented by variable cells B14 and C14 in Fig. 17.29 of Section 17.5.2.1. Rows 13 and 14 in Fig. 17.71 show the original and final values of each variable cell. From column E, we can see that the optimal number of toy cars to be produced is x₁ = 70 and the optimal number of tricycles to be produced is x₂ = 20.

The machining, painting, and assembly human resources availability constraints are represented by rows 19, 20, and 21, respectively, while the non-negativity constraints of each decision variable, by rows 22 and 23. Cells D8, D9, and D10 represent the total number of hours used or the amount of resources necessary for the machining, painting, and assembly departments, respectively. The value of each cell (column D) can be obtained by substituting the optimal values of each decision variable (x₁ = 70 and x₂ = 20) on the left-hand side of each constraint. Column E shows the formula used to represent each constraint. Conversely, column F presents the status of each constraint: binding or not binding. The Binding Status happens when the total amount of resources used (column D) is equal to the maximum limit available, that is, there is no slack or idleness of resources. As shown in Fig. 17.29 in Section 17.5.2.1, the quantity of resources available for the machining, painting, and assembly activities is represented by cells F8, F9, and F10, respectively. The Not Binding Status indicates that the maximum capacity of resources has not been used. Now, the Slack field suggests the difference between the total amount of resources available and the total amount of resources used, or the amount of idle resources. For example, for the machining sector, from the total amount of resources available (36 hours), only 27.5 hours have been used, what generates an idleness of 8.5 hours (slack). For the painting and machining activities, since the maximum capacity of the resources was used, slack is zero.

17.5.4.2 Limits Report

The main results provided by the Limits Report refer to the lower and upper limits of each variable cell (decision variable). Fig. 17.72 shows the Limits Report for the problem faced by Venix Toys.

According to Fig. 17.72, we can see that the results of the Limits Report are divided into two main parts: objective cell and variable cells.

Analogous to the Answer Report, the Limits Report also provides the optimal value of the objective cell.

Alternatively, the data regarding each one of the variable cells are represented in rows 13 and 14 in Fig. 17.72. Analogous to the Answer Report, the optimal value of each variable cell is also provided by the Limits Report (column D). Column F presents the lower limits of the variable cells that refer to the minimum value each variable can take on. By assigning lower limits to one of the variables (x₁ = 0), and by maintaining the other constants (x₂ = 20), we obtain a feasible solution with z = 1,200 (cell G13). In contrast, if x₁ = 70 and x₂ = 0, we obtain another feasible solution with z = 840 (cell G14). Finally, column I shows the upper limits of the variable cells, that is, the maximum values each variable can achieve. In this case, the value of objective function z is 2,040.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Chapter 17: Solution of Linear Programming Problems

Create new playlist

Sign In

Sign Up

17.1 Introduction

17.2 Graphical Solution of a Linear Programming Problem

17.2.1 Linear Programming Maximization Problem with a Single Optimal Solution

17.2.2 Linear Programming Minimization Problem With a Single Optimal Solution

17.2.3 Special Cases

17.2.3.1 Multiple Optimal Solutions

17.2.3.2 Unlimited Objective Function z

17.2.3.3 There Is No Optimal Solution

17.2.3.4 Degenerate Optimal Solution

17.3 Analytical Solution of a Linear Programming Problem in Which m < n

17.4 The Simplex Method

17.4.1 Logic of the Simplex Method

17.4.2 Analytical Solution of the Simplex method for Maximization Problems

17.4.3 Tabular Form of the Simplex Method for Maximization Problems

17.4.4 The Simplex Method for Minimization Problems

17.4.5 Special Cases of the Simplex Method

17.4.5.1 Multiple Optimal Solutions

17.4.5.2 Unlimited Objective Function z

17.4.5.3 There Is No Optimal Solution

17.4.5.4 Degenerate Optimal Solution

17.5 Solution by Using a Computer

17.5.1 Solver in Excel

17.5.2 Solution of the Examples found in Section 16.6 of Chapter 16 using Solver in Excel

17.5.2.1 Solution of Example 16.3 of Chapter 16 (Production Mix Problem at the Venix Toys)

17.5.2.2 Solution of Example 16.4 of Chapter 16 (Production Mix Problem at Naturelat Dairy)

17.5.2.3 Solution of Example 16.5 of Chapter 16 (Mix Problem of Oil-South Refinery)

17.5.2.4 Solution of Example 16.6 of Chapter 16 (Diet Problem)

17.5.2.5 Solution of Example 16.7 of Chapter 16 (Farmer’s Problem)

17.5.2.6 Solution of Example 16.8 of Chapter 16 (Portfolio Selection—Maximization of the Expected Return)

17.5.2.7 Solution of Example 16.9 of Chapter 16 (Portfolio Selection—Minimization of the Portfolio’s Mean Absolute Deviation)

17.5.2.8 Solution of Example 16.10 of Chapter 16 (Production and Inventory Problem of Fenix&Furniture)

17.5.2.9 Solution of Example 16.11 of Chapter 16 (Problem of Lifestyle Natural Juices Manufacturer)

17.5.3 Solver Error Messages for Unlimited and Infeasible Solutions

17.5.3.1 Unlimited Objective Function z

17.5.3.2 There Is No Optimal Solution

17.5.4 Result Analysis by Using the Solver Answer and Limits Reports

17.5.4.1 Answer Report

17.5.4.2 Limits Report

Table of Contents for
Chapter 17: Solution of Linear Programming Problems