Linear, integer, and goal programming all assume that a problem’s objective function and constraints are linear. That means that they contain no nonlinear terms such as , or . Yet in many mathematical programming problems, the objective function and/or one or more of the constraints are nonlinear.
Unlike with linear programming methods, computational procedures for solving many nonlinear programming (NLP) problems do not always yield an optimal solution. In many NLP problems, a particular solution may be better than any other point nearby, but it may not be the overall best point. This is called a local optimum, and the overall best solution is called the global optimum. Thus, for a particular problem, a solution technique may indicate that an optimum solution has been found, but it is only a local optimum, so there may be a global optimum that is better. The mathematics involved in solving these problems is beyond the scope of this text. We will rely on Solver in Excel to solve the nonlinear problems presented in this section.
In this section, we examine three categories of NLP problems and illustrate how Excel can be used to search for the solutions to these problems. In Solved Problem 10–3, we will see how NLP in Excel can help find the best parameter to use in an exponential smoothing forecasting model.
The Great Western Appliance Company sells two models of toaster ovens, the Microtoaster and the Self-Clean Toaster Oven . The firm earns a profit of $28 for each Microtoaster, regardless of the number sold. Profits for the Self-Clean model, however, increase as more units are sold because of fixed overhead. Profit on this model may be expressed as .
Hence, the firm’s objective function is nonlinear:
Great Western’s profit is subject to two linear constraints on production capacity and sales time available:
When an objective function contains squared decision variables (such as ) and the problem’s constraints are linear, it is called a quadratic programming problem. A number of useful problems in the field of portfolio selection fall into this category. Quadratic programs can be solved by a modified form of the simplex method. Such work is outside the scope of this book but can be found in sources listed in the Bibliography.
The solution to the Great Western Appliance nonlinear programming problem is shown in Program 10.9. This was found using Solver in Excel 2016, and there are two important features of this spreadsheet that are different from the previous linear and integer programming examples. First, the solving method used for this in Solver is GRG Nonlinear instead of Simplex LP. The second change involves the objective function and the changing cells. For the sake of consistency, values for both (cell C4) and (cell D7) are shown in Program 10.9. However, cell D7 is simply cell C4 squared. Thus, when cell C4 changes, D7 will automatically change, and the Changing cells specified in Solver are B4:C4, while D7 is not included.
Solver Parameter Inputs and Selections | Key Formulas |
---|---|
Set Objective: E8 | |
By Changing cells: B4:C4 | |
To: Max | |
Subject to the Constraints: | |
E11:E12 <= G11:G12 | |
Solving Method: GRG Nonlinear | |
☑ Make Variables Non-Negative |
The annual profit at a medium-sized (200–400 beds) Hospicare Corporation–owned hospital depends on the number of medical patients admitted and the number of surgical patients admitted . The nonlinear objective function for Hospicare is
The corporation identifies three constraints, two of which are also nonlinear, that affect operations. They are
Excel’s Solver is capable of formulating such a problem. The optimal solution is provided in Program 10.10.
Solver Parameter Inputs and Selections | Key Formulas |
---|---|
Set Objective: H8 |
Copy H8 to H11:H13 |
By Changing cells: B4:C4 | |
To: Max | |
Subject to the Constraints: | |
H11:H13 <= J11:J13 | |
Solving Method: GRG Nonlinear | |
☑ Make Variables Non-Negative |
Thermlock Corporation produces rubber washers and gaskets like the type used to seal joints on the International Space Station. To do so, it combines two ingredients: rubber and oil . The cost of the industrial-quality rubber used is $5 per pound, and the cost of the high-viscosity oil is $7 per pound. Two of the three constraints Thermlock faces are nonlinear. The firm’s objective function and constraints are
To solve this nonlinear programming problem, we turn again to Excel. The output is provided in Program 10.11.
Solver Parameter Inputs and Selections | Key Formulas |
---|---|
Set Objective: D5 |
Copy G10 to G11:G12 |
By Changing cells: B4:C4 | |
To: Min | |
Subject to the Constraints: | |
G10:G12 >= I10:I12 | |
Solving Method: GRG Nonlinear | |
☑ Make Variables Non-Negative |