Assignment - network models - formulate and solve a

Question

Assignment - Network Models

Part A - Shortest-Path Problems

Q1. Find the shortest path from node 1 to node 6 in Figure 3.

Q2. Find the shortest path from node 1 to node 5 in Figure 4.

Q3. Formulate Problem 2 as a transshipment problem.

Q4. Use Dijkstra's algorithm to find the shortest path from node 1 to node 4 in Figure 5. Why does Dijkstra's algorithm fail to obtain the correct answer?

Q5. Suppose it costs $10,000 to purchase a new car. The annual operating cost and resale value of a used car are shown in Table 4. Assuming that one now has a new car, determine a replacement policy that minimizes the net costs of owning and operating a car for the next six years.

Q6. It costs $40 to buy a telephone from the department store. Assume that I can keep a telephone for at most five years and that the estimated maintenance cost each year of operation is as follows: year 1, $20; year 2, $30; year 3, $40; year 4, $60; year 5, $70. I have just purchased a new telephone. Assuming that a telephone has no salvage value, determine how to minimize the total cost of purchasing and operating a telephone for the next six years.

Q7. At the beginning of year 1, a new machine must be purchased. The cost of maintaining a machine i years old is given in Table 5.

The cost of purchasing a machine at the beginning of each year is given in Table 6.

There is no trade-in value when a machine is replaced. Your goal is to minimize the total cost (purchase plus maintenance) of having a machine for five years. Determine the years in which a new machine should be purchased.

Q8. A library must build shelving to shelve 200 4-inch high books, 100 8-inch high books, and 80 12-inch high books.

Each book is 0.5 inch thick. The library has several ways to store the books. For example, an 8-inch high shelf may be built to store all books of height less than or equal to 8 inches, and a 12-inch high shelf may be built for the 12-inch books. Alternatively, a 12-inch high shelf might be built to store all books. The library believes it costs $2,300 to build a shelf and that a cost of $5 per square inch is incurred for book storage. (Assume that the area required to store a book is given by height of storage area times book's thickness.)

Formulate and solve a shortest-path problem that could be used to help the library determine how to shelve the books at minimum cost. (Hint: Have nodes 0, 4, 8, and 12, with c_ij being the total cost of shelving all books of height > i and ≤ j on a single shelf.)

Q9. A company sells seven types of boxes, ranging in volume from 17 to 33 cubic feet. The demand and size of each box is given in Table 7. The variable cost (in dollars) of producing each box is equal to the box's volume. A fixed cost of $1,000 is incurred to produce any of a particular box. If the company desires, demand for a box may be satisfied by a box of larger size. Formulate and solve a shortest-path problem whose solution will minimize the cost of meeting the demand for boxes.

Q10. Explain how by solving a single transshipment problem you can find the shortest path from node 1 in a network to each other node in the network.

Table 4
Age of Car (Years)	Resale Value ($)	Operating Cost ($)
1	7,000	300 (year 1)
2	6,000	500 (year 2)
3	4,000	800 (year 3)
4	3,000	1,200 (year 4)
5	2,000	1,600 (year 5)
6	1,000	2,200 (year 6)

 

Table 5
Age at Beginning of Year	Maintenance Cost for Nest Year ($)
0	38,000
1	50,000
2	97,000
3	182,000
4	304,000

 

Table 6
Year	Purchase Cost ($)
1	170,000
2	190,000
3	210,000
4	250,000
5	300,000

 

Table 7
	Box
	1	2	3	4	5	6	7
Size	33	30	26	24	19	18	17
Demand	400	300	500	700	200	400	200

Part B - Maximum-Flow Problems

Q1-3 Figures 18-20 show the networks for Problems 1-3. Find the maximum flow from source to sink in each network. Find a cut in the network whose capacity equals the maximum flow in the network. Also, set up an LP that could be used to determine the maximum flow in the network.

Q4-5. For the networks in Figures 21 and 22, find the maximum flow from source to sink. Also find a cut whose capacity equals the maximum flow in the network.

Q6. Seven types of packages are to be delivered by five trucks. There are three packages of each type, and the capacities of the five trucks are 6, 4, 5, 4, and 3 packages, respectively. Set up a maximum-flow problem that can be used to determine whether the packages can be loaded so that no truck carries two packages of the same type.

Q7. Four workers are available to perform jobs 1-4. Unfortunately, three workers can do only certain jobs: worker 1, only job 1; worker 2, only jobs 1 and 2; worker 3, only job 2; worker 4, any job. Draw the network for the maximum-flow problem that can be used to determine whether all jobs can be assigned to a suitable worker.

Q8. The Hatfields, Montagues, McCoys, and Capulets are going on their annual family picnic. Four cars are available to transport the families to the picnic. The cars can carry the following number of people: car 1, four; car 2, three; car 3, three; and car 4, four. There are four people in each family, and no car can carry more than two people from any one family. Formulate the problem of transporting the maximum possible number of people to the picnic as a maximum-flow problem.

Q9-10. For the networks in Figures 23 and 24, find the maximum flow from source to sink. Also find a cut whose capacity equals the maximum flow in the network.

Q11. Suppose a network contains a finite number of arcs and the capacity of each arc is an integer. Explain why the Ford-Fulkerson method will find the maximum flow in the finite number of steps. Also show that the maximum flow from source to sink will be an integer.

Q12. Consider a network flow problem with several sources and several sinks in which the goal is to maximize the total flow into the sinks. Show how such a problem can be converted into a maximum-flow problem having only a single source and a single sink.

Q13. Suppose the total flow into a node of a network is restricted to 10 units or less. How can we represent this restriction via an arc capacity constraint? (This still allows us to use the Ford-Fulkerson method to find the maximum flow.)

Q14. Suppose as many as 300 cars per hour can travel between any two of the cities 1, 2, 3, and 4. Set up a maximum-flow problem that can be used to determine how many cars can be sent in the next two hours from city 1 to city 4. (Hint: Have portions of the network represent t = 0, t = 1, and t = 2.)

Q15. Fly-by-Night Airlines is considering flying three flights. The revenue from each flight and the airports used by each flight are shown in Table 11. When Fly-by-Night uses an airport, the company must pay the following landing fees (independent of the number of flights using the airport): airport 1, $300; airport 2, $700; airport 3, $500. Thus, if flights 1 and 3 are flown, a profit of 900 + 800 - 300 - 700 = 500 = $200 will be earned. Show that for the network in Figure 25 (maximum profit) = (total revenue from all flights) - (capacity of minimal cut). Explain how this result can be used to help Fly-by-Night maximize profit (even if it has hundreds of possible flights). (Hint: Consider any set of flights F (say, flights 1 and 3). Consider the cut corresponding to the sink, the nodes associated with the flights not in F, and the nodes associated with the airports not used by F. Show that (capacity of this cut) = (revenue from flights not in F) + (costs associated with airports used by F).)

Q16. During the next four months, a construction firm must complete three projects. Project 1 must be completed within three months and requires 8 months of labor. Project 2 must be completed within four months and requires 10 months of labor. Project 3 must be completed at the end of two months and requires 12 months of labor. Each month, 8 workers are available. During a given month, no more than 6 workers can work on a single job. Formulate a maximum-flow problem that could be used to determine whether all three projects can be completed on time. (Hint: If the maximum flow in the network is 30, then all projects can be completed on time.)

Table 11
Flight	Revenue ($)	Airport Used
1	900	1 and 2
2	600	2
3	800	2 and 3

Part C - Minimum-Cost Network Flow Problems

Note: To formulate a problem as an MCNFP, you should draw the appropriate network and determine the c_ij's, the b_i's, and the arc capacities.

Q1. Formulate the problem of finding the shortest path from node 1 to node 6 in Figure 2 as an MCNFP. (Hint: Think of finding the shortest path as the problem of minimizing the total cost of sending 1 unit of flow from node 1 to node 6.)

Q2. A. Find the dual of the LP that was used to find the length of the critical path for Example 6 of Section 8.4.

b. Show that the answer in part (a) is an MCNFP.

c. Explain why the optimal objective function value for the LP found in part (a) is the longest path in the project network from node 1 to node 6. Why does this justify our earlier claim that the critical path in a project network is the longest path from the start node to the finish node?

Q3. Fordco produces cars in Detroit and Dallas. The Detroit plant can produce as many as 6,500 cars, and the Dallas plant can produce as many as 6,000 cars. Producing a car costs $2,000 in Detroit and $1,800 in Dallas. Cars must be shipped to three cities. City 1 must receive 5,000 cars, city 2 must receive 4,000 cars, and city 3 must receive 3,000 cars. The cost of shipping a car from each plant to each city is given in Table 33. At most, 2,200 cars may be sent from a given plant to a given city. Formulate an MCNFP that can be used to minimize the cost of meeting demand.

Q4. Each year, Data Corporal produces as many as 400 computers in Boston and 300 computers in Raleigh. Los Angeles customers must receive 400 computers, and 300 computers must be supplied to Austin customers. Producing a computer costs $800 in Boston and $900 in Raleigh.

Computers are transported by plane and may be sent through Chicago. The costs of sending a computer between pairs of cities are shown in Table 34.

a. Formulate an MCNFP that can be used to minimize the total (production + distribution) cost of meeting Data Corporal's annual demand.

b. How would you modify the part (a) formulation if at most 200 units could be shipped through Chicago? [Hint: Add an additional node and arc to this part (a) network.]

Q5. Oilco has oil fields in San Diego and Los Angeles. The San Diego field can produce 500,000 barrels per day, and the Los Angeles field can produce 400,000 barrels per day. Oil is sent from the fields to a refinery, in either Dallas or Houston (assume each refinery has unlimited capacity). To refine 100,000 barrels costs $700 at Dallas and $900 at Houston. Refined oil is shipped to customers in Chicago and New York. Chicago customers require 400,000 barrels per day, and New York customers require 300,000 barrels per day. The costs of shipping 100,000 barrels of oil (refined or unrefined) between cities are shown in Table 35.

a. Formulate an MCNFP that can be used to determine how to minimize the total cost of meeting all demands.

b. If each refinery had a capacity of 500,000 barrels per day, how would the part (a) answer be modified?

Q6. Workco must have the following number of workers available during the next three months: month 1, 20; month 2, 16; month 3, 25. At the beginning of month 1, Workco has no workers. It costs Workco $100 to hire a worker and $50 to fire a worker. Each worker is paid a salary of $140/month. We will show that the problem of determining a hiring and firing strategy that minimizes the total cost incurred during the next three (or in general, the next n) months can be formulated as an MCNFP.

a. Let

x_ij = number of workers hired at beginning of month I and fired after working till end of month j - 1 (if j = 4, the worker is never fired). Explain why the following LP will yield a minimum-cost hiring and firing strategy:

min z = 50(x₁₂ + x₁₃ + x₂₃)

+ 100(x₁₂ + x₁₃ + x₁₄ + x₂₃ + x₂₄ + x₃₄)

+ 140(x₁₂ + x₂₃ + x₃₄)

+ 280(x₁₃ + x₂₄) + 420x₁₄

s.t. (1) x₁₂ + x₁₃ + x₁₄ - e₁ = 20 (Month 1 constraint)

(2) x₁₃ + x₁₄ + x₂₃ + x₂₄ - e₂ = 16 (Month 2 constraint)

(3) x₁₄ + x₂₄ + x₃₄ - e₃ = 25 (Month 3 constraint)

x_ij  ≥  0

b. To obtain an MCNFP, replace the constraints in part (a) by

i. Constraint (1);

ii. Constraint (2) - Constraint (1);

iii. Constraint (3) - Constraint (2);

iv. - (Constraint (3)).

Explain why an LP with Constraints (i)-(iv) is an MCNFP.

c. Draw the network corresponding to the MCNFP obtained in answering part (b).

Q7. Braneast Airlines must determine how many airplanes should serve the Boston-New York-Washington air corridor and which flights to fly. Braneast may fly any of the daily flights shown in Table 36. The fixed cost of operating an airplane is $800/day. Formulate an MCNFP that can be used to maximize Braneast's daily profits. (Hint: Each node in the network represents a city and a time. In addition to arcs representing flights, we must allow for the possibility that an airplane will stay put for an hour or more. We must ensure that the model includes the fixed cost of operating a plane. To include this cost, the following three arcs might be included in the network: from Boston 7 P .M. to Boston 9 A.M.; from New York 7 P .M. to New York 9 A.M.; and from Washington 7 P .M. to Washington 9 A.M.)

Q8. Daisymay Van Line moves people between New York, Philadelphia, and Washington, D.C. It takes a van one day to travel between any two of these cities. The company incurs costs of $1,000 per day for a van that is fully loaded and traveling, $800 per day for an empty van that travels, $700 per day for a fully loaded van that stays in a city, and $400 per day for an empty van that remains in a city. Each day of the week, the loads described in Table 37 must be shipped. On Monday, for example, two trucks must be sent from Philadelphia to New York (arriving on Tuesday). Also, two trucks must be sent from Philadelphia to Washington on Friday (assume that Friday shipments must arrive on Monday). Formulate an MCNFP that can be used to minimize the cost of meeting weekly requirements. To simplify the formulation, assume that the requirements repeat each week. Then it seems plausible to assume that any of the company's trucks will begin each week in the same city in which it began the previous week.

Table 33
From	To ($)
	City 1	City 2	City 3
Detroit	800	600	300
Dallas	500	200	200

 

Table 34
From	To ($)
	Chicago	Austin	Los Angeles
Boston	80	220	280
Raleigh	100	140	170
Chicago	-	40	50

 

Table 35
From	To ($)
	Dallas	Houston	New York	Chicago
Los Angles	300	110	-	-
San Diego	420	100	-	-
Dallas	-	-	450	550
Houston	-	-	470	530

Part D - The Network Simplex Method

Q1. Consider the problem of finding the shortest path from node 1 to node 6 in Figure 2.

a. Formulate this problem as an MCNFP.

b. Find a bfs in which x₁₂, x₂₄, and x₄₆ are positive. (Hint: A degenerate bfs will be obtained.)

c. Use the network simplex to find the shortest path from node 1 to node 6.

Q2. For the MCNFP in Figure 62, find a bfs.

Q3. Find the optimal solution to the MCNFP in Figure 63 using the bfs in Figure 64 as a starting basis.

Q4. Find a bfs for the network in Figure 65.

Q5. Find the optimal solution to the MCNFP in Figure 66 using the bfs in Figure 67 as a starting basis.

Textbook - Operations Research APPLICATIONS AND ALGORITHMS, FOURTH EDITION by Wayne L. Winston WITH CASES BY Jeffrey B. Goldberg.

Chapter 8 - Network Models