Nonlinear Optimization

1363025 - Cengage Learning ©

e might be to minimize the probability that the portfolio loses money. This possibility is illustrated in one of the problems.

Problems

Level A

69. In the FPL electricity pricing model, the demand functions have positive and negative coefficients of prices. The negative coefficients indicate that as the price of a product increases, demand for that product decreases. The positive coefficients indicate that as the price of a product increases, demand for the other product increases.

a. Increase the magnitudes of the negative coefficients f rom −0.013 and −0.015 to −0.018 and −0.023, and rerun Solver. Are the changes in the optimal solution intuitive? Explain.

b. Increase the magnitudes of the positive coefficients f rom 0.005 and 0.003 to 0.007 and 0.005, and rerun Solver. Are the changes in the optimal solution intuitive? Explain.

c. Make the changes in parts a and b simultaneously and rerun Solver. What happens now?

70. In the FPL electricity pricing model, we assumed that the capacity level is a decision variable. Assume now that capacity has already been set at 0.65 million of mWh. (Note that the cost of capacity is now a sunk cost, so it is irrelevant to the decision

1363025 - Cengage Learning ©

problem.) Change the model appropriately and run Solver. Then use SolverT-able to see how sensitive the optimal solution is to the capacity level, letting it vary over some relevant range. Does it appear that the optimal prices will be set so that demand is always equal to capacity for at least one of the two periods of the day?

71. For each of the following, answer whether it makes sense to multiply the matrices of the given sizes. In each case where it makes sense, demonstrate an example in Excel, where you can make up the numbers.

a. AB, where A is 3 × 4 and B is 4 × 1 b. AB, where A is 1 × 4 and B is 4 × 1 c. AB, where A is 4 × 1 and B is 1 × 4 d. AB, where A is 1 × 4 and B is 1 × 4 e. ABC, where A is 1 × 4, B is 4 × 4, and C is 4 × 1 f. ABC, where A is 3 × 3, B is 3 × 3, and C is 3 × 1 g. ATB, where A is 4 × 3 and B is 4 × 3, and AT

denotes the transpose of A 72. Add a new stock, stock 4, to the Perlman portfolio

optimization model. Assume that the estimated mean and standard deviation of return for stock 4 are 0.125 and 0.175, respectively. Also, assume the correlations between stock 4 and the original three stocks are 0.3, 0.5, and 0.8. Run Solver on the modified model, where the required expected portfolio return is again 0.12. Is stock 4 in the optimal portfolio? Then run SolverTable as in the example. Is stock 4 in any of the optimal portfolios on the efficient f rontier?

73. In the Perlman portfolio optimization model, stock 2 is not in the optimal portfolio. Use SolverTable to see whether it ever enters the optimal portfolio as its correlations with stocks 1 and 3 vary. Specifically, use

1363025 - Cengage Learning ©

a two-way SolverTable with two inputs, the correlations between stock 2 and stocks 1 and 3, each allowed to vary f rom 0.1 to 0.9. Capture as outputs the three decision variable cells. Discuss the results. (Note: You will have to change the model slightly. For example, if you use cells B10 and C11 as the two SolverTable input cells, you will have to ensure that cells C9 and D10 change accordingly. This is easy. Just enter formulas in these latter two cells.)

74. The stocks in the Perlman portfolio optimization model are all positively correlated. What happens when they are negatively correlated? Answer for each of the following scenarios. In each case, two of the three correlations are the negatives of their original values. Discuss the differences between the optimal portfolios in these three scenarios.

a. Change the signs of the correlations between stocks 1 and 2 and between stocks 1 and 3. (Here, stock 1 tends to go in a different direction f rom stocks 2 and 3.)

b. Change the signs of the correlations between stocks 1 and 2 and between stocks 2 and 3. (Here, stock 2 tends to go in a different direction f rom stocks 1 and 3.)

c. Change the signs of the correlations between stocks 1 and 3 and between stocks 2 and 3. (Here, stock 3 tends to go in a different direction f rom stocks 1 and 2.)

75. The file P14_75.xlsx contains historical monthly returns for 28 companies. For each company, calculate the estimated mean return and the estimated variance of return. Then calculate the estimated correlations between the companies’ returns. Note that “return” here means monthly return.

1363025 - Cengage Learning ©

76. The file P14_76.xlsx includes contains the data f rom the previous problem. It also contains f ractions in row 3 for creating a portfolio. These f ractions are currently all equal to 1/28, but they can be changed to any values you like, so long as they continue to sum to 1. For any such f ractions, find the estimated mean, variance, and standard deviation of the resulting portfolio return.

Level B

77. Continuing the previous problem, find the portfolio that achieves an expected monthly return of at least 0.01(1%) and minimizes portfolio variance. Then use SolverTable to sweep out the efficient f rontier. Create a chart of this efficient f rontier f rom your SolverTable results. What are the relevant lower and upper limits on the required expected monthly return?

78. In many cases you can assume that the portfolio return is at least approximately normally distributed. Then you can use Excel’s NORM.DIST function as in Chapter 5 to calculate the probability that the portfolio return is negative. The relevant formula is = NORM.DIST(0,mean,stdev,TRUE), where mean and stdev are the expected portfolio return and standard deviation of portfolio return, respectively.

a. Modify the Perlman portfolio optimization model slightly, and then run Solver to find the portfolio that achieves at least a 12% expected return and minimizes the probability of a negative return. Do you get the same optimal portfolio as before? What is the probability that the return f rom this portfolio will be negative?

b. Using the model in part a, create a chart of

1363025 - Cengage Learning ©

the efficient f rontier. However, this time put the probability of a negative return on the horizontal axis.

14-9 Conclusion

This chapter has led you through spreadsheet optimization models of many diverse problems. No standard procedure can be used to model all problems. However, there are several keys to most models.

• First, determine the decision variables. For example, in blending problems it is important to realize that the decision variables are the amounts of inputs used to produce outputs, and in employee scheduling problems, it is important to realize that the decision variables are the number of employees who start their five-day shift each day of the week.

• Set up the model so that you can easily calculate what you want to maximize or minimize (usually profit or cost). For example, in the aggregate planning model it is a good idea to calculate total cost by calculating the monthly cost of the various activities in separate rows and then summing the subtotals.

• Set up the model so that the relationships between the cells in the spreadsheet and the constraints of the problem are readily apparent. For example, in the employee scheduling model it is convenient to calculate the number of people working each day of the week adjacent to the minimum required number of people for each day of the week.

• Optimization models do not always fall into ready- made categories. A model might involve a combination of the ideas discussed in the production scheduling, blending, and aggregate planning examples. In fact, many real applications

1363025 - Cengage Learning ©

are not strictly analogous to any of the models we have discussed. However, exposure to the models in this chapter should give you the insights you need to solve a wide variety of interesting problems.

SUMMARY OF KEY TERMS

TERM EXPLANATION PAGES Employee scheduling models

Models for choosing the staffing levels to meet workload requirements

663

Multiple optimal solutions

Situation where several solutions obtain the same optimal objective value

668

Blending models Models where inputs must be mixed in the right proportions to produce outputs

670

Logistics models Models where goods must be shipped from one set of locations to another at minimal cost

676

Flow balance constraint

Constraint that relates the flow into a node and the flow out of the node

682

Aggregate planning models

Models where workforce levels and production levels must be set to meet customer demand

693

Integer programming (IP) models

Models where at least some of the decision variables must be integers

714

Binary variable Integer variable that must be 0 or 1; used to indicate whether an activity takes place

714

Capital budgeting models

Models where a subset of investment activities is chosen from a set of possible activities

714

Fixed-cost models Models where fixed costs are incurred for various activities if they are done at any positive level

720

Set-covering models

Models where members of one set must be selected to cover services to members of another set

729

Nonlinear programming (NLP) models

Models where either the objective function or the constraints (or both) are nonlinear functions of the decision variables

735

Global optimum Solution that is the best in the entire feasible region 735 Local optimal solution

Solution that is better than all nearby solutions (but might not be optimal globally)

735

Portfolio optimization models

Models that attempt to find the portfolio of securities that achieves the best balance between risk and return

740

1363025 - Cengage Learning ©

PROBLEMS

CONCEPTUAL EXERCISES

C.1. The employee scheduling model in this chapter was purposely made small (only seven decision variable cells). What would make a similar problem for a company like McDonald’s much harder? What types of constraints would be required? How many decision variable cells (approximately) might there be?

C.2. Explain why it is problematic to include a constraint such as the following in an LP model for a blending problem:

C.3. “It is essential to constrain all shipments in a transportation problem to have integer values to ensure that the optimal LP solution consists entirely of integer-valued shipments.” Is this statement true or false? Why?

C.4. What is the relationship between transportation models and more general logistics models? Explain how these two types of linear optimization models are similar and how they are different.

C.5. Unlike the small logistics models presented here, real-world logistics problems can be huge. Imagine the global problem a company like FedEx faces each day. Describe as well as you can the types of decisions and constraints it has. How large (number of decision variables, number of constraints) might such a problem be?

C.6. Suppose you develop and solve an integer programming model with a cost-minimization

1363025 - Cengage Learning ©

objective. Assume the optimal solution yields an objective cell value of $500,000. Now, consider the same linear optimization model without the integer restrictions. That is, suppose you drop the requirement that the decision variable cells be integer-valued and reoptimize with Solver. How does the optimal objective cell value for this modified model (called the LP relaxation of the IP model) compare to the original total cost value of $500,000? Explain your answer.

C.7. The portfolio optimization model presented here is the standard model: minimize the variance (or standard deviation) of the portfolio, as a measure of risk, for a given required level of expected return. In general, the goal is to keep risk low and expected return high. Can you think of other ways to model the problem to achieve these basic goals? Is high variability all bad risk?

LEVEL A

79. A bus company believes that it will need the following numbers of bus drivers during each of the next five years: 60 drivers in year 1; 70 drivers in year 2; 50 drivers in year 3; 65 drivers in year 4; 75 drivers in year 5. At the beginning of each year, the bus company must decide how many drivers to hire or fire. It costs $4000 to hire a driver and $2000 to fire a driver. A driver’s salary is $45,000 per year. At the beginning of year 1 the company has 50 drivers. A driver hired at the beginning of a year can be used to meet the current year’s requirements and is paid full salary for the current year.

a. Determine how to minimize the bus company’s salary, hiring, and firing costs over the next five years.

b. Use SolverTable to determine how the total

1363025 - Cengage Learning ©

number hired, total number fired, and total cost change as the unit hiring and firing costs each increase by the same percentage.

80. A pharmaceutical company produces the drug NasaMist f rom four chemicals. Today, the company must produce 1000 pounds of the drug. The three active ingredients in NasaMist are A, B, and C. By weight, at least 8% of NasaMist must consist of A, at least 4% of B, and at least 2% of C. The cost per pound of each chemical and the amount of each active ingredient in one pound of each chemical are given in the file P14_80.xlsx. It is necessary that at least 100 pounds of chemical 2 and at least 450 pounds of chemical 3 be used.

a. Determine the cheapest way of producing today’s batch of NasaMist.

b. Use SolverTable to see how much the percentage of requirement of A is really costing the company. Let the percentage required vary f rom 6% to 12%.

81. A bank is attempting to determine where to invest its assets during the current year. At present, $500,000 is available for investment in bonds, home loans, auto loans, and personal loans. The annual rates of return on each type of investment are known to be the following: bonds, 6%; home loans, 8%; auto loans, 5%; personal loans, 10%. To ensure that the bank’s portfolio is not too risky, the bank’s investment manager has placed the following three restrictions on the bank’s portfolio:

• The amount invested in personal loans cannot exceed the amount invested in bonds.

• The amount invested in home loans cannot exceed the amount invested in auto loans.

• No more than 25% of the total amount invested can be in personal loans.

1363025 - Cengage Learning ©

Help the bank maximize the annual return on its investment portfolio.

82. A fertilizer company blends silicon and nitrogen to produce two types of fertilizers. Fertilizer 1 must be at least 40% nitrogen and sells for $70 per pound. Fertilizer 2 must be at least 70% silicon and sells for $40 per pound. The company can purchase up to 8000 pounds of nitrogen at $15 per pound and up to 10,000 pounds of silicon at $10 per pound.

a. Assuming that all fertilizer produced can be sold, determine how the company can maximize its profit.

b. Use SolverTable to explore the effect on profit of changing the minimum percentage of nitrogen required in fertilizer 1.

c. Suppose the availabilities of nitrogen and silicon both increase by the same percentage f rom their current values. Use SolverTable to explore the effect of this change on profit.

83. Optimization models are used by many Wall Street firms to select a desirable bond portfolio. The following is a simplified version of such a model. A company is considering investing in four bonds; $1 million is available for investment. The expected annual return, the worst-case annual return on each bond, and the duration of each bond are given in the file P14_83.xlsx. (The duration of a bond is a measure of the bond’s sensitivity to interest rates.) The company wants to maximize the expected return f rom its bond investments, subject to three constraints:

• The worst-case return of the bond portfolio must be at least 8%.

• The average duration of the portfolio must be at most 6. For example, a portfolio that invests $600,000 in bond 1 and $400,000 in bond 4

1363025 - Cengage Learning ©

has an average duration of [600,000(3) + 400,000(9)]/1,000,000 = 5.4.

• Because of diversification requirements, at most 40% of the total amount invested can be invested in a single bond. Determine how the company can maximize the expected return on its investment.

84. At the beginning of year 1, you have $10,000. Investments A and B are available; their cash flows are shown in the file P14_84.xlsx. Assume that any money not invested in A or B earns interest at an annual rate of 2%.

a. Determine how to maximize your cash on hand at the beginning of year 4.

b. Use SolverTable to determine how a change in the year 2 return for investment A changes the optimal solution to the problem.

c. Use SolverTable to determine how a change in the year 3 return of investment B changes the optimal solution to the problem.

85. An oil company produces two types of gasoline, G1 and G2, f rom two types of crude oil, C1 and C2. G1 is allowed to contain up to 4% impurities, and G2 is allowed to contain up to 3% impurities. G1 sells for $48 per barrel, whereas G2 sells for $72 per barrel. Up to 4200 barrels of G1 and up to 4300 barrels of G2 can be sold. The cost per barrel of each crude, their availability, and the level of impurities in each crude are listed in the file P14_85.xlsx. Before blending the crude oil into gas, any amount of each crude can be “purified” for a cost of $3.00 per barrel. Purification eliminates half of the impurities in the crude oil.

a. Determine how to maximize profit. b. Use SolverTable to determine how an increase

in the availability of C1 affects the optimal profit.

1363025 - Cengage Learning ©

c. Use SolverTable to determine how an increase in the availability of C2 affects the optimal profit.

d. Use SolverTable to determine how a change in the profitability of G2 changes profitability and the types of gas produced.

86. The government is auctioning off oil leases at two sites: 1 and 2. At each site 10,000 acres of land are to be auctioned. Cliff Ewing, Blake Barnes, and Alexis Pickens are bidding for the oil. Government rules state that no bidder can receive more than 40% of the land being auctioned. Cliff has bid $10,000 per acre for site 1 land and $20,000 per acre for site 2 land. Blake has bid $9000 per acre for site 1 land and $22,000 per acre for site 2 land. Alexis has bid $11,000 per acre for site 1 land and $19,000 per acre for site 2 land.

a. Determine how to maximize the government’s revenue.

b. Use SolverTable to see how changes in the government’s rule on 40% of all land being auctioned affect the optimal revenue. Why can the optimal revenue not decrease if this percentage required increases? Why can the optimal revenue not increase if this percentage required decreases?

87. An automobile company produces cars in Los Angeles and Detroit and has a warehouse in Atlanta. The company supplies cars to customers in Houston and Tampa. The costs of shipping a car between various points are listed in the file P14_87.xlsx, where a blank means that a shipment is not allowed. Los Angeles can produce up to 1100 cars, and Detroit can produce up to 2900 cars. Houston must receive 2400 cars, and Tampa must receive 1500 cars.

a. Determine how to minimize the cost of

1363025 - Cengage Learning ©

meeting demands in Houston and Tampa. b. Modify the answer to part a if shipments

between Los Angeles and Detroit are not allowed.

c. Modify the answer to part a if shipments between Houston and Tampa are allowed at a cost of $5 per car.

88. An oil company produces oil f rom two wells. Well 1 can produce up to 150,000 barrels per day, and well 2 can produce up to 200,000 barrels per day. It is possible to ship oil directly f rom the wells to the company’s customers in Los Angeles and New York. Alternatively, the company could transport oil to the ports of Mobile and Galveston and then ship it by tanker to New York or Los Angeles, respectively. Los Angeles requires 160,000 barrels per day, and New York requires 140,000 barrels per day. The costs of shipping 1000 barrels between various locations are shown in the file P14_88.xlsx, where a blank indicates shipments that are not allowed. Determine how to minimize the transport costs in meeting the oil demands of Los Angeles and New York.

89. Based on Bean et al. (1987). Boris Milkem’s firm owns six assets. The expected selling price (in millions of dollars) for each asset is given in the file P14_89.xlsx. For example, if asset 1 is sold in year 2, the firm receives $20 million. To maintain a regular cash flow, Milkem must sell at least $20 million of assets during year 1, at least $30 million worth during year 2, and at least $35 million worth during year 3. Determine how Milkem can maximize his total revenue f rom assets sold during the next three years.

90. Based on Sonderman and Abrahamson (1985). In treating a brain tumor with radiation, physicians want the maximum amount of radiation possible to bombard the tissue containing the tumors. The

1363025 - Cengage Learning ©

constraint is, however, that there is a maximum amount of radiation that normal tissue can handle without suffering tissue damage. Physicians must therefore decide how to aim the radiation so as to maximize the radiation that hits the tumor tissue subject to the constraint of not damaging the normal tissue. As a simple example, suppose there are six types of radiation beams (beams differ in where they are aimed and their intensity) that can be aimed at a tumor. The region containing the tumor has been divided into six regions: three regions contain tumors and three contain normal tissue. The amount of radiation delivered to each region by each type of beam is shown in the file P14_90.xlsx. If each region of normal tissue can handle at most 60 units of radiation, which beams should be used to maximize the total amount of radiation received by the tumors?

91. A leading hardware company produces three types of computers: Pear computers, Apricot computers, and Orange computers. The relevant data are given in the file P14_91.xlsx. The equipment cost is a fixed cost; it is incurred if any of this type of computer is produced. A total of 30,000 chips and 12,000 hours of labor are available. The company wants to produce at least two types of computers.

a. Determine how the company can maximize its profit.

b. For any computer type not in the optimal product mix, use SolverTable to find how much larger its unit margin would have to be before it would enter the optimal product mix.

92. A food company produces tomato sauce at five different plants. The tomato sauce is then shipped to one of three warehouses, where it is stored until it is shipped to one of the company’s four customers. All

1363025 - Cengage Learning ©

of the inputs for the problem are given in the file P14_92.xlsx, as follows:

• The plant capacities (in tons) • The cost per ton of producing tomato sauce

at each plant and shipping it to each warehouse

• The cost of shipping a ton of sauce f rom each warehouse to each customer

• The customer requirements (in tons) of sauce • The fixed annual cost of operating each plant

and warehouse.

The company must decide which plants and warehouses to open, and which routes f rom plants to warehouses and f rom warehouses to customers to use. All customer demand must be met. A given customer’s demand can be met f rom more than one warehouse, and a given plant can ship to more than one warehouse.

a. Determine the minimum-cost method for meeting customer demands.

b. Use SolverTable to see how a change in the capacity of plant 1 affects the total cost.

c. Use SolverTable to see how a change in the customer 2 demand affects the total cost.

93. You are given the following means, standard deviations, and correlations for the annual return on three potential investments. The means are 0.12, 0.15, and 0.20. The standard deviations are 0.20, 0.30, and 0.40. The correlation between stocks 1 and 2 is 0.65, between stocks 1 and 3 is 0.75, and between stocks 2 and 3 is 0.41. You have $100,000 to invest and can invest no more than half of your money in any single investment. Determine the minimum-variance

1363025 - Cengage Learning ©

portfolio that yields an expected annual return of at least 0.14.

94. You have $50,000 to invest in three stocks. Let Ri be the random variable representing the annual return on $1 invested in stock i. For example, if Ri = 0.12, then $1 invested in stock i at the beginning of a year is worth $1.12 at the end of the year. The means are E(R1) = 0.14, E(R2) = 0.11, and E(R3) = 0.10. The variances are Var R1 = 0.20, VarR2 = 0.08, and VarR3 = 0.18. The correlations are r12 = 0.8, r13 = 0.7, and r23 = 0.9. Determine the minimum-variance portfolio that attains an expected annual return of at least 0.12.

LEVEL B

95. The risk index of an investment can be obtained by taking the absolute values of percentage changes in the value of the investment for each year and averaging them. Suppose you are trying to determine the percentages of your money to invest in stocks, 3-month Treasury bills, and 10-year Treasury bonds. The file P14_95.xlsx lists the annual returns (percentage changes in value) for these investments since 1970. Let the risk index of a portfolio be the weighted average of the risk indices of these investments, where the weights are the f ractions of the portfolio assigned to the investments. Suppose the amount of each investment must be between 20% and 50% of the total inve