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.
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”
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.
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:
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.
The graphical solution for an LP maximization problem with a single optimal solution will be illustrated through Example 17.1.
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:
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).
A linear programming problem can have more than one optimal solution. In this case, considering a problem with two decision variables, different values of x1 and x2 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.
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.
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.
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).
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:
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.
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.
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.
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= c1x1 + c2x2 + … + cnxn = 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.
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:
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 − c1x1 −c2x2 − … − cnxn = 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.
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.
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:
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:
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.
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:
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).
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.
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.
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.
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.
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.
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.
Having selected the Solver command, the Solver Parameters dialog box will appear (Fig. 17.20). Let’s now discuss each one of its cells.
The objective cell (target cell in earlier Excel versions) is the one that contains the value of the objective function.
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.
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.
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.
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.
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).
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.
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.
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.
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).
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,25x1 + 0,5x2 ≤ 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,25x1 + 0,5x2 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: x1 = 0, x2 = 0, and z = 0.
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.
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.
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.
Therefore, we can see that the model’s optimal solution is x1 = 70 and x2 = 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.45 shows the optimal solution for the diet 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.
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.
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.49 shows the optimal solution for the farmer’s problem.
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.
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.
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.53 shows the optimal solution for the portfolio selection problem.
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).
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 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).
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 Iit = Ii,t − 1 + xit − Dit, 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.
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.
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 Rt from July to December become 5,000 (Rt = Rt − 1 + Ht − Ft). Applying the formula It = It − 1 + Rt + Ot + St − Dt, 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.
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.
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:
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.
For the maximization problem (max z = 4x1 + 3x2) 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.
For the maximization problem (max z = x1 + x2) 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).
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.
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 x1 = 70 and the optimal number of tricycles to be produced is x2 = 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 (x1 = 70 and x2 = 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.
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 (x1 = 0), and by maintaining the other constants (x2 = 20), we obtain a feasible solution with z = 1,200 (cell G13). In contrast, if x1 = 70 and x2 = 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.