Previously I have written an article on how to rate sports team using GRG Nonlinear engine, today I’d like to continue to discuss GRG Nonlinear Multistart and Excel evolutionary solver engine in more detail.
1. Understand GRG Nonlinear Engine
If the references to changing cells in both target cell and constraints are in the (Changing cell)*(Constant) form, you have a linear model. Otherwise, you have a nonlinear model. For example, if x and y are changing cells, references like those in Figure 1 in your target cell or constraint can make your model nonlinear and you can choose GRG Nonlinear engine.
The first two graphs in Figure 1.2 are for functions y = -x^2+4x+2 and y = x^2 respectively. For the left panel, you can see that there is a point (x = 2) at which the slope of the function is 0. And for the middle panel, there is also a point at which the slope of the function is 0. You can see that when the slope of the function is 0, the function will be maximized (left panel) or minimized (middle panel). In fact, this is how the GRG Nonlinear engine solves the problem – try to find a point at which the slope of the function is 0.Unfortunately, many functions cannot be maximized or minimized simply by locating a point where the function’s slope is 0. Let’s look at the right panel of Figure 1.2. The function has more than one peak and there are 7 points at which the slope of the function is 0. If Excel starts near x = 5, Excel will return a solution of x = 5. Obviously, this is incorrect. Similarly, x = -15 is also not the right solution. Only when Excel starts near x = 1, you will get the right solution.
In most problems with more than one changing cell, Excel does not know which point is the good starting point. Fortunately, Excel provides a Multistart option. You can select Multistart after choosing Options and then clicking the GRG Nonlinear tab. When the Multistart option is selected, Excel chooses many starting points and finds the best solution.And there are also some problems in which target cells, constraints, or both use a non-smooth function such as MAX, MIN, ABS, IF, SUMIF, COUNTIF, SUMIFS, COUNTIFS, GRG engine cannot be used. Look at both the left panel and right panel of Figure 1.4, there are no points at which the function’s slope is 0. For this kind of problem, we need to use the Evolutionary engine.
2. Problem 1: How to locate a single warehouse to minimize the total distance that packages are shipped?
Suppose that an internet shipping company wants to build a single warehouse, where the warehouse should be located so that the total distance that packages are shipped can be minimized? The number of shipments (in thousands) made each year to various cities is shown in the following table.
|City||Latitude||Longitude||Shipments (in thousands)|
|Salt Lake City||40.8||112||10|
2.1 Equation to compute the approximate distance between two sites
Figure 2.1 shows the formula which gives the approximate distance between two US cities having a latitude and longitude given by (Lat1, Long1) and (Lat2, Long2).
2.2 Set up Model
Let’s take cells J2 and J3 as By Changing cells and they include latitude and longitude of the warehouse respectively. The distance between New York and the warehouse can be calculated by entering the formula “=69*SQRT((C3-$J$2)^2+(D3-$J$3)^2)” into cell F3. By copying this formula into cells from F4 through F23, we can get distances between the warehouse and other cities. The formula “=E3*F3” in cell G3 can be used to compute shipped distances between New York and Warehouse. Similarly, copying this formula into range G4: G23, we can calculate shipped distances for other cities. Sum all the shipped distances by filling formula “=SUM(G3: G23)” in cell J4, our objective – total shipped distances – can be computed. Thus, cell J4 is our Target cell.
2.3 Use Excel Solver to solve a problem
Click on Solver in Analysis group to open Solver Parameters dialog box. Fill the Solver Parameters dialog box as shown in Figure 2.3. Per the equation in section 2.1, GRG Nonlinear engine should be selected for this problem. In order to make sure that the warehouse is north of the equator, west of Greenwich, England, and east of Anchorage, Alaska, we need to set up two constraints. Latitude should be between 0 and 90 degrees while longitude should be between 0 and 150.
After you click Solve, you’ll find that the warehouse should be located at 36.90 degrees latitude and 92.48 degrees longitude.
3. Problem 2: How to locate two warehouses to minimize the total distance that packages are shipped?
Still for the above same problem, what if the company would like to build two warehouses? How should the company locate those two warehouses?
3.1 Set up Model
There are two warehouses now. Cells L2 and M2 are for the latitude of warehouse 1 and warehouse 2. Cells L3 and M3 include the longitude of warehouse 1 and warehouse 2. These 4 cells are our By Changing Cells.
We can use the same way as that in section 2.2 to compute distances between each city and each warehouse. For example, formula “=69*SQRT((C4-$L$2)^2+(D4-$L$3)^2)” in cell F4 returns the distance between Boston and Warehouse 1 while formula “=69*SQRT((D4-$M$2)^2+(E4-$M$3)^2)” in cell G4 returns the distance between Boston and Warehouse 2. Because the shipments to each city will be sent from the closer warehouse, we need to compute the distance of each city to the closer warehouse by copying the formula “=MIN(F3, G3)” from H3 to H84: H23. Next, use the similar method as that in section 2.2 to get the total distance traveled by shipments for each city. Our target cell L4 displays total distances returned by formula “=SUM(I3: I23)”.
3.2 use Excel Solver to solve the problem
Click on Solver in Analysis group to open Solver Parameters dialog box. Fill the Solver Parameters dialog box as shown in Figure 3.2. Since we suspect that there are multiple peaks for the function, I selected GRG MultiStart option. Please note that bounds (constraints) for By Changing Cells should always be set if you use GRG MultiStart. The bounds here for this case are the same as that in section 2.
After clicking on Solve, latitude, and longitude for Warehouse 1 returned by Excel is 38.1 and 84.0. Latitude and longitude for Warehouse 2 are 35.7 and 115.7.
To confirm that Solver found the optimal solution, you can select Evolutionary engine and run Solver again. In our case, you will find that the current solution is already the best one.
Suppose that Solver recommends a longitude near 150 degrees, you should relax the bound to avoid a mistake.
Download working file
Download the working file from the link below.