EM 505 – Decision Models, Fall 2012 Homework 3 – December 10-11, 2012 1. The diagram below depicts a system of aqueducts that originate at three rivers (nodes R1, R2 and R3) and terminate at a major city (node T) where the other nodes are junction points in the system. Using units of thousands of acre feet, the tables below show the maximum amount of water that can be pumped through each aqueduct per day and the following diagram shows the network of the system.

The city water manager wants to determine a flow plan that will maximize the flow of water of the city. Formulate this problem as a max flow problem by identifying a source, a sink and transshipment nodes, and then drawing the complete network that shows the capacity of each arc. 2. The Quick Chip gravel company has received a contract to supply two new construction projects in the towns of Brock and Wurst. A total of 60 truckloads are needed at Brock in the next month and 90 at Wurst. Quick Chip has idle gravel pits in the towns of Nova, Scova, and Tova, each with a monthly production capacity of 50 truckloads.

The truck company wants to fulfill its contract at least total truck travel distance. Formulate an LP to choose an optimal shipping plan. 3. The Makonsel Company is a fully integrated company that both produces goods and sells them at its retail outlets. After production, the goods are stored in the company’s two warehouses until needed by the retail outlets. Trucks are used to transport the goods from two plants to the warehouses, and then from the warehouses to the three retail outlets. Using the units of full truckloads, the following table shows each plant’s monthly output, its shipping cost per truckload sent to each warehouses, and the maximum amount that it can ship per month to each warehouse.

For each retail outlet (RO), the next table shows its monthly demand, its shipping cost per truckload from each warehouse, and the maximum amount that can be shipped per month from each warehouse. unit shipping cost.

Management now wants to determine a distribution plan (# of truckloads shipped per month from each plant to each warehouse and from each warehouse to each retail outlet) that will minimize the total shipping cost. (a) Draw a network that depicts the company’s distribution network. (b) Formulate this problem as a minimum cost flow problem. 4. RentCar is developing a replacement plan for its car fleet for a 5-year (2008 to 2012) planning horizon. At the start of each year, a decision is made as to whether a car should be kept in operation or replaced. A car must be in service at least 1 year but must be replaced after 3 years. The following table provides the replacement cost as a function of the year a car is acquired and the number of years in operations. year acquired.

Formulate the problem that will minimize the total cost. 5. The Chicago Board of Education is taking bids on the city’s four school bus routes. Four companies have made the bids in table below.

(a) Suppose each bidder can be assigned only one route. How can Chicago minimize its cost of running the four bus routes? (b) Suppose that each company can be assigned two routes. How can Chicago minimize its cost of running the four bus routes?

6. The R&D department of the Good Products Company has developed three possible new products. However, to avoid undue diversification of the company’s product line, management has decided that from the three possible new products, at most two should be chosen to produce. Each of these products can be produced in either of two plants. For administrative reasons, management has imposed a second restriction in this regard. Just one of the two plants should be chosen to be sole producer of the new products.

The production cost per unit of each product would be essentially the same in the two plants. However, because of differences in their production facilities, the number of the hours of production time needed per unit of each product might differ between the two plants. These data are given in the table below, including marketing estimate of the number of units of each product that could be sold per week. The objective is to choose the products, the plant and the production rates so as to maximize the profit.

Plant 1 Plant 2 Unit Profit Sales Potential

7. The Fly-Right Airplane Company builds small jet airplanes to sell to corporations for the use of their executives, for the custom designed airplanes a substantial start-up cost is incurred to initiate the production. They have recently received purchase requests from 3 customers with short deadlines. However, because the company’s production facility has been tied up filling previous orders, it will not be able to accept all 3 orders. Therefore, a decision now has to be made on the number of airplanes to produce (if any) for each of the 3 customers. The relevant data are given in the table below. Once the production is under way, the marginal net revenue (purchase price minus the marginal production cost) from each airplane produced is shown. Maximize the company’s total profit. Formulate a model with both integer and binary variables for this problem. Customer 1 $3 million $2 million 20% 3 planes 2 $2 million $3 million 40% 2 planes 3 0 $0.8 million 20% 5 planes

Start-up cost Marginal net revenue Capacity used per plane Maximum order

8. Consider the situation in which orders from m different destinations are delivered from a central warehouse. Each destination receives its order in one delivery. Feasible routes are assigned to different carriers, and each carrier may combine at most r orders. Suppose that there are n feasible routes with each route specifying the destinations to which orders are delivered. Assume further that the cost of the jth route is Cj. Overlapping is expected so that the same destination can be reached by more than one carrier. Formulate this problem as an integer model. 9. Consider the job-shop scheduling problem involving eight operations on a single machine with a total of two end products.

The sequencing of operations is shown in Figure 1. Let bj be the processing time for the jth operation (j=1,2,..,8). Delivery dates for products 1 and 2 are restricted by d1 and d2 time units measured from the zero datum. Since each operation requires a special machine setup, it is assumed that any operation once started must be completed before a new operation can be undertaken. Formulate the problem as a mixed integer programming model to minimize the total processing time on the machine while satisfying all the pertinent constraints.

10. The board of directors of the General Wheels Co. is considering seven large capital investments. These investments differ in the estimated long-run profit (net present value) they will generate, as well as in the amount of capital required, as shown by the following table (in units of millions of dollars).

The total amount of capital available for these investments is $100.000.000. Investment opportunities 1 and 2 are mutually exclusive, and so are 3 and 4. Furthermore, neither 3 nor 4 can be undertaken unless either 1 or 2 is undertaken. There are no such restrictions on investment opportunities 5, 6 and 7. The objective is to select the combination of capital investments that will maximize the total estimated long-run profit (net present value). Formulate the BIP model for this problem. 11. A company sells seven types of boxes, ranging in volume from 17 to 33 cubic feet.

The variable cost (in dollars) of producing each box type is equal to the volume of the box. A fixed cost of $1000 is incurred to produce any of a particular box type. If the company desires, demand for a box type can be satisfied by a box type of a larger size. Determine how to minimize the cost of meeting the demand for boxes. 12. An American professor will be spending a short sabbatical leave at the University of Iceland. She wishes bring all needed items with her on the airplane.

After collecting together the professional items that she must have, she finds that airline regulations on space and weight for checked luggage will severely limit the clothes she can take. She plans to carry on a warm coat, and then purchase a warm Icelandic sweater upon arriving in Iceland. Clothes under consideration for checked luggage include 3 skirts, 3 slacks, 4 tops, and 3 dresses. The professor wants to maximize the number of outfits she will have in Iceland (including the special dress she will wear on the airplane). Each dress constitutes an outfit. Other outfits consist of a combination of a top and either a skirt or slacks. However, certain combinations are not fashionable and so will not qualify as an outfit.

Slacks

Formulate a BIP model to choose which items of clothing to take. (Hint: After using binary decision variables to represent the individual items, introduce auxiliary binary variables to represent outfits involving combinations of items. Then use constraints and the objective function to ensure that these auxiliary variables have the correct values given the values of the decision variables.)