Chapter 8 – Evolutionary Solver: An Alternative Optimization Procedure
1. Evolutionary Solver is primarily used to solve models where:
a.
some or all of the changing cells are restricted to be binary and/or integer
b.
the objective cell and constraints are “smooth” functions of the changing cells
c.
there are numerous constraints
d.
the objective call and constraints are “nonsmooth” functions of the changing cells
d
1
2. Which of the following is not one of the Excel functions that necessitate the use of Evolutionary Solver to obtain
solutions?
a.
b.
c.
d.
a
1
3. The objective function in a genetic algorithm is called a:
a.
chromosome
b.
fitness function
c.
population
d.
generation
b
1
4. Which of the following is not a step in a genetic algorithm?
a.
Generating a population
b.
Creating a new generation
c.
Culling the population
d.
Evaluating a stopping condition
c
1
5. Which of the following is true regarding Evolutionary Solver?
a.
It is efficient at handling constraints
b.
A good starting is critical to the success of it finding a solution
c.
It places more of a burden on you to specify certain parameters of the algorithm
d.
Running it a second time for a problem should yield the same solution
c
1
6. The Evolutionary Solver setting that helps the algorithm explore a completely different area of the feasible region is:
a.
convergence
b.
mutation rate
c.
population size
Chapter 8 – Evolutionary Solver: An Alternative Optimization Procedure
d.
random seed
b
1
7. Which of the following is not a form of non-linear pricing?
a.
Two-part tariff
b.
Surplus value
c.
Selling only single item packs or packs of n items
d.
Charging one price for the first n items and another price for the rest
b
1
8. Evolutionary Solver works best when constraints are applied as:
a.
penalties
b.
shortages
c.
capacities
d.
targets
a
1
9. The data used to classify members in a discriminant analysis is called a:
a.
group
b.
cluster
c.
training sample
d.
population
c
1
10. The number of possible paths in a shortest path problem with n locations is:
a.
n
b.
n − 1
c.
n2
d.
n!
d
1
11. The initial set of chromosomes generated by a genetic algorithm is called the population.
a.
True
b.
False
True
1
12. Crossovers are rare as a genetic algorithm is generating chromosomes for the next generations.
a.
True
b.
False
Chapter 8 – Evolutionary Solver: An Alternative Optimization Procedure
False
1
13. Mutations are useful for getting a genetic algorithm “unstuck”.
a.
True
b.
False
True
1
14. If you let a genetic algorithm run long enough, it is guaranteed to find the solution to any optimization problem.
a.
True
b.
False
True
1
15. In Evolutionary Solver, the initial population is chosen randomly, so the starting solution you enter in the changing
cells is irrelevant.
a.
True
b.
False
False
1
16. Combinatorial problems have only a finite number of feasible solutions.
a.
True
b.
False
True
1
17. In cluster analysis, the number of clusters is usually assigned ahead of time.
a.
True
b.
False
False
1
18. A discriminant score is a weighted combination of the data for each member of a population, which is used to classify
the members into groups.
a.
True
b.
False
True
1
19. If the classification matrix from a discriminant analysis shows a high percentage of correct classification, then we can
be confident that the classification will work well for other populations.
a.
True
b.
False
False
20. A traveling salesman problem with a starting city and 10 other cities that must be visited has 1,826,800 possible
solutions.
a.
True
b.
False
False
1
Exhibit 8-1
Six storage bins on a railroad train are available for shipment of grain from Kansas City to Dallas. Three of the bins can
hold 1500 bushels of grain each, while the other three can hold 750 bushels each. There are four types of grain that can be
shipped, and the amount demanded, unit shortage cost and maximum allowable shortage for each are:
If the maximum allowable shortage is exceeded for any grain, a $100/bushel penalty is incurred.
21. Refer to Exhibit 8-1. This is an example of what type of optimization problem?
22. Refer to Exhibit 8-1. How should the train be loaded to minimize shortage and penalty costs?
1
Exhibit 8-2
1
Chapter 8 – Evolutionary Solver: An Alternative Optimization Procedure
A television station has commercials of the following lengths (in seconds): 15, 20, 25, 30, 40, 45, 50, and 60. The
commercials must be assigned to 90-second breaks. If a commercial break exceeds 90 seconds, a penalty cost is incurred.
Station managers have established a penalty of $100 (per second) if the maximum limit is exceeded. Moreover, station
owners want commercial breaks that are at least 65 seconds in duration. If any break fails to achieve this minimum
duration, then a $1000 penalty (per occurrence) is charged.
23. Refer to Exhibit 8-2. What is the fewest number of breaks that are needed to air all eight of the commercials?
24. Refer to Exhibit 8-2. Explain why this problem typically requires Evolutionary Solver to obtain a solution.
There are different ways to formulate this problem, but all formulations are likely to use the SUMIF, IF, and
MAX or MIN functions. Evolutionary Solver is able to handle the nonlinear and non-smooth conditions
resulting from the use of these functions.
Exhibit 8-3
A standardized testing agency would like to understand the role of tests in admission decisions at top business schools. It
is particularly interested in the relative roles played by the GRE and the undergraduate GPA in the admissions process. It
has gathered the following data for 50 randomly sampled applicants (which has been sorted by Admitted):
25. Refer to Exhibit 8-3. Use a discriminant analysis to develop a classification model. What is the best percentage
correctly classified obtained with your model?
26. Refer to Exhibit 8-3. Write out your model and interpret your results. Do the results make sense?
27. Refer to Exhibit 8-3. Test your model against another randomly drawn sample of 50 students (data shown below).
Does your model work as well for this sample? Can you explain your findings?
Chapter 8 – Evolutionary Solver: An Alternative Optimization Procedure
Exhibit 8-4
Chapter 8 – Evolutionary Solver: An Alternative Optimization Procedure
Steve the salesman must travel along a route from his home in Denver that visits all of the cities shown below exactly
once before returning home. The mileage between each city on the route is also listed below:
28. Refer to Exhibit 8-4. Formulate and solve a shortest-path model using Evolutionary Solver. What is the shortest
distance Steve can travel and visit all cities? What is the route?
29. Refer to Exhibit 8-4. Suppose Steve moves to Los Angeles. What is the shortest distance in this case?
30. Refer to Exhibit 8-4. Suppose Steve’s company decides to locate a second salesperson in the region. Steve will now
cover only Denver, Albuquerque, El Paso, Phoenix and Salt Lake City. The second salesperson will cover Los Angeles,
San Diego, San Francisco, Portland, Seattle and Las Vegas. Formulate and solve shortest-path models for both
salespersons. Is the total mileage for both salespersons more or less than in the case where Steve is the only salesperson?