OSCM 471/571 Optimization and Decision Support Modeling for Business

OSCM 471/571 Optimization and Decision Support Modeling for Business

Homework 4, Spring 2023

Notice for Homework 4

Instructor: Seokjun Youn ( [email protected] )

· Due date: Tuesday 4/4, 11:59 pm

· Please submit your files to D2L > Assignments > Homework 4

1. A Word file (or PDF) with your answers combined into a single document.

2. An Excel spreadsheet template with your answers (for some sub-questions).

· This homework is made up of 8 questions (20 + 3 pts):

· Lecture Note 5: Integer Programming Models

· Q1: 2 sub-questions (3.5 pts)

· Q2: 2 sub-questions (3.5 pts)

· Q3: Bonus question for 496A; Required for 596A (3 pts)

· Lecture Note 6: Non-linear Programming Models

· Q4: 4 sub-questions (2 pts)

· Q5: 3 sub-questions (3 pts)

· Q6: 5 sub-questions (3 pts)

· Q7: 2 sub-questions (2 pts)

· Q8: 3 sub-questions (3 pts)

· Students may choose either handwriting or word processing (or both).

· Handwriting: please properly scan or take photos and organize them into one file before uploading in D2L.

· Please write down your solutions step-by-step for partial credit.

· You may use:

· Your textbook and notes from the class.

· Notes or sources from a related class or internet source.

· Discussion with the instructor.

· Voluntary, mutual, and cooperative discussion with other students currently taking the class.

· You may not use:

· Solution manuals (printed or electronic).

· Copying from other students in this class, including expecting them to reveal their solutions in “discussion.”

· It is fine if your answer is not 100% correct. However, if you do not put enough effort to the assignment, your score for this homework will be lower than your expectation. So, please try to convince your logic to instructor.

Your Name:

Lecture Note 5: Integer Programming Models

1. Speedy Delivery provides two-day delivery service of large parcels across the United States. Each morning at each collection center, the parcels that have arrived overnight are loaded onto several trucks for delivery throughout the area. Since the competitive battlefield in this business is speed of delivery, the parcels are divided among the trucks according to their geographical destinations to minimize the average time needed to make the deliveries.

On this particular morning, the dispatcher for the Blue River Valley Collection Center, Sharon Lofton, is hard at work. Her three drivers will be arriving in less than an hour to make the day’s deliveries. There are nine parcels to be delivered, all at locations many miles apart. As usual, Sharon has loaded these locations into her computer. She is using her company’s special software package, a decision support system called Dispatcher. The first thing Dispatcher does is use these locations to generate a considerable number of attractive possible routes for the individual delivery trucks. These routes are shown in the table below (where the numbers in each column indicate the order of the deliveries), along with the estimated time required to traverse the route.

Dispatcher is an interactive system that shows these routes to Sharon for her approval or modification. (For example, the computer may not know that flooding has made a particular route infeasible.) After Sharon approves these routes as attractive possibilities with reasonable time estimates, Dispatcher next formulates and solves a BIP model for selecting three routes that minimize their total time while including each delivery location on exactly one route.

a. Using the data in the table, demonstrate how Dispatcher can formulate and solve this BIP model on a spreadsheet.

Answer:

b. Describe how the problem addressed in part a is analogous to the crew scheduling problem described in Section 7.4.

Answer:

2. The school board for the Bellevue School District has made the decision to purchase 1,350 additional Macintosh computers for computer laboratories in all its schools. Based on past experience, the school board also has directed that these computers should be purchased from some combination of three companies—Educomp, Macwin, and McElectronics. In all three cases, the companies charge a discounted variable cost per computer and a fixed delivery and installation cost for these large sales to school districts. The table below shows these charges as well as the capacity (the maximum number of computers that can be sold from the limited inventory) for each of the companies.

The school board wants to determine the minimum-cost plan for meeting its computer needs.

a. Formulate a BIP model in algebraic form for this problem.

Answer:

b. Formulate and solve this model on a spreadsheet.

Answer:

3. [Bonus question for 496A; Required for 596A] Read the referenced article that fully describes the management science study summarized in the application vignette below (from Section 7.1). Briefly describe how mixed BIP was applied in this study. Then list the various financial and nonfinancial benefits that resulted from this study (300-400 words).

An Application Vignette: With headquarters in Houston, Texas, Waste Management, Inc. (a Fortune 100 company), is the leading provider of comprehensive waste-management services in North America. Its network of operations includes 293 active landfill disposal sites, 16 waste-to-energy plants, 72 landfill gas-to-energy facilities, 146 recycling plants, 346 transfer stations, and 435 collection operations (depots) to provide services to nearly 20 million residential customers and 2 million commercial customers throughout the United States and Canada.

The company’s collection-and-transfer vehicles need to follow nearly 20,000 daily routes. With an annual operating cost of nearly $120,000 per vehicle, management wanted to have a comprehensive route-management system that would make every route as profitable and efficient as possible. Therefore, a management science team that included a number of consultants was formed to attack this problem.

The heart of the route-management system developed by this team is a huge mixed BIP model that optimizes the routes assigned to the respective collection-and-transfer vehicles. Although the objective function takes several factors into account, the primary goal is the minimization of total travel time. The main decision variables are binary variables that equal 1 if the route assigned to a particular vehicle includes a particular possible leg and that equal 0 otherwise. A geographical information system (GIS) provides the data about the distance and time required to go between any two points. All of this is imbedded within a Web-based Java application that is integrated with the company’s other systems.

It is estimated that the recent implementation of this comprehensive route-management system will increase the company’s cash flow by $648 million over a five-year period, largely because of savings of $498 million in operational expenses over this same period. It also is providing better customer service.

Source: S. Sahoo, S. Kim, B.-I. Kim, B. Krass, and A. Popov, Jr., “Routing Optimization for Waste Management,” Interfaces 35, no. 1 (January–February 2005), pp. 24–36.

Answer:

Lecture Note 6: Non-linear Programming Models

4. The Chiplet Corporation is about to launch the production and marketing of a new microchip that is more powerful than anything that is currently on the market. Not surprisingly, the profitability of this microchip will depend greatly on its reception in this highly competitive and fast-moving market. If the sales are fairly low, the company will still be able to make a respectable profit because it will have enough available production capacity to produce the microchip with its current facilities. However, if sales are somewhat higher, the company will need to expand its production facilities, which will have the effect of depressing the profit from the microchip if sales only reach a moderate level. (Fully meeting this demand would still be worthwhile because one of top management’s prime goals is to continue increasing the company’s market share as it points toward future generations of microchips already under development.) Fortunately, if sales reach a relatively high level, the profit from the microchip will become very substantial. The following table shows the estimated profit for various levels of sales over the short lifetime of this microchip.

a. Does the microchip have decreasing marginal returns, increasing marginal returns, or neither?

Answer:

b. Use Excel’s curve fitting method to (1) obtain a nonlinear formula with a quadratic form (a polynomial of order 2) for the profit graph and then (2) construct the graph.

Answer:

c. Repeat part c when using the Excel option of a polynomial of order 3 instead of order 2.

Answer:

d. Which of the Excel options used in parts c and d does a better job of fitting the profit graph to the data?

Answer:

5. A stockbroker, Richard Smith, has just received a call from his most important client, Ann Hardy. Ann has $50,000 to invest and wants to use it to purchase two stocks. Stock 1 is a solid blue-chip security with a respectable growth potential and little risk involved. Stock 2 is much more speculative. It is being touted in two investment newsletters as having outstanding growth potential, but also is considered very risky. Ann would like a large return on her investment, but also has considerable aversion to risk. Therefore, she has instructed Richard to analyze what mix of investments in the two stocks would be appropriate for her. She also informs him that her plan is to hold the stock being purchased now for three years before selling it.

After doing some research on the historical performances of the two stocks and on the current prospects for the companies involved, Richard is able to make the following estimates. If the entire $50,000 were to be invested in Stock 1 now, the profit when sold in three years would have an expected value of $12,500 and a standard deviation of $5,000. If the entire $50,000 were to be invested in Stock 2 now, the profit when sold in three years would have an expected value of $20,000 and a standard deviation of $30,000. The two stocks behave independently in different sectors of the market so Richard’s calculation from historical data is that the covariance of the profits from the two stocks is 0.

Richard now is ready to use a spreadsheet model to determine how to allocate the $50,000 to the two stocks so as to minimize Ann’s risk while providing an expected profit that is at least as large as her minimum acceptable value. He asks Ann to decide what her minimum acceptable value is.

a. Without yet assigning a specific numerical value to the minimum acceptable expected profit, formulate a quadratic programming model in algebraic form for this problem.

Answer:

b. Display this model on a spreadsheet. Solve this model for four cases: Minimum acceptable expected profit = $13,000, $15,000, $17,000, and $19,000.

Answer:

c. Ann was a statistics major in college and so understands well that the expected return and risk in this model represent estimates of the mean and standard deviation of the probability distribution of the profit from the corresponding portfolio. Ann uses the notation and for the mean and standard deviation. She recalls that, for typical probability distributions, the probability is fairly high (about 0.8 or 0.9) that the return will exceed , and the probability is extremely high (often close to 0.999) that the profit will exceed . Calculate and for the four portfolios obtained in part c. Which portfolio will give Ann the highest among those that also give ?

Answer:

6. The Dorwyn Company has two new products (special kinds of doors and windows) that will compete with the two new products for the Wyndor Glass Co. (described in Section 2.1). Using units of hundreds of dollars for the objective function, the linear programming model in algebraic form shown below has been formulated to determine the most profitable product mix.

Maximize

Subject to

and

However, because of the strong competition from Wyndor, Dorwyn management now realizes that the company will need to make a strong marketing effort to generate substantial sales of these products. In particular, it is estimated that achieving a production and sales rate of D doors per week will require weekly marketing costs of hundred dollars (so $100 for D = 1, $800 for D = 2, $2,700 for D = 3, etc.). The corresponding marketing costs for windows are estimated to be 2 W 2 hundred dollars. Thus, the objective function in the model should be

Dorwyn management now would like to use the revised model to determine the most profitable product mix.

a. Formulate and solve this nonlinear programming model on a spreadsheet.

Answer:

b. Construct tables to show the profit data for each product when the production rate is 0, 1, 2, 3.

Answer:

c. Draw a figure that plots the weekly profit points for each product when the production rate is 0, 1, 2, 3. Connect the pairs of consecutive points with (dashed) line segments.

Answer:

d. Use separable programming based on this figure to formulate an approximate linear programming model on a spreadsheet for this problem. Then solve the model. What does this say to Dorwyn management about which product mix to use?

Answer:

e. Compare the solution based on a separable programming approximation in part d with the solution obtained in part a for the exact nonlinear programming model.

Answer:

7. Consider the following nonlinear programming problem.

Maximize

Subject to

a. Formulate this problem in a spreadsheet and then use the Nonlinear Solver and the Multistart feature to solve this problem.

Answer:

b. Use Evolutionary Solver to solve this problem.

Answer:

8. Reconsider the portfolio optimization problem considered in Section 8.5, where the goal was to select the portfolio that beat the market for the largest number of quarters over the last six years.

a. Using the naive solution (20 percent in each stock) as a starting point, apply Evolutionary Solver to optimize the portfolio again when considering the data for the first three years only (Q1 2011 through Q4 2013).

Answer:

b. For how many quarters does this same portfolio beat the market for the next three years (Q1 2014 through Q4 2016)?

Answer:

c. (Open-Ended Question) Comment on the results from parts a and b.

Answer:

8/8

,

,