Text Material Preview
MASSACHUSETTS INSTITUTE OF TECHNOLOGY 15.053 – Introduction to Optimization (Spring 2005) Problem Set 7, Due April 7th, 2005 You will need 97 points out of 115 to receive a grade of 2.5. Problem 1: Max Flows and Minimum Cuts (20 Points) a. Find the maximum flow from source to sink for the network in Figure 1. b. Find the maximum flow from source to sink for the network in Figure 2. c. Find a cut whose capacity equals the maximum flow for the network in Figure 1. d. Find a cut whose capacity equals the maximum flow for the network in Figure 2. s t 42 31 Figure 1 6 4 6 4 2 1 6 2 4 6 Figure 2 Problem 2: Network Conversions (16 Points) a. Suppose the total flow into a node of a network is restricted to be 10 or less. How b. e capacity of each arc is od will find the max flow in a finite (ii) max flow solution found by the Ford Fulkerson can we modify a network to incorporate this restriction? Suppose a network contains a finite number of arcs and th an integer. Answer the following questions: (i) Explain why the Ford Fulkerson meth number of steps. True or False: The algorithm will be integral (Explain your answer). s 1 3 6 4 2 t 9 9 7 8 6 6 6 7 Problem 3: Min Cost Flow Formulation (16 Points) Do either b or b’ A truck must travel from New York to Los Angeles. As shown in Figure 3, a variety of routes are available. The number associated with each arc is the number of gallons of fuel required by the truck to traverse the arc. a. Use Dijkstra’s algorithm to find the route from the New York to Los Angeles that uses the minimum amount of gas. b. Formulate a balanced transportation problem that could be used to find the route from New York to Los Angeles that uses the minimum amount of gas. b’ Formulate the shortest path problem as an LP and use excel to solve it. Turn in a copy of your excel model. c. Formulate the problem of finding the New York to Los Angeles route that uses the minimum amount of gas as a Minimum Cost Network Flow Problem. 1800 St. Louis New York Dallas Nashville Salt Lake City Los Angeles Phoenix Cleveland 400 600950 800 600 900 1000 600 1300 1200 900 400 1100 Figure 3 Problem 4: Min Cost Flow (12 Points) Cost Capacity The graph above represents a minimum cost flow problem with capacity constraints. a. Our objective is to minimize the cost of shipping from supply nodes to demand nodes given the capacity constraints. . Formulate the problem as an LP (you do not need to solve the problem). b. Will the decision variables ALL be integral in the optimal solution, assuming it is solved using the simplex algorithm? Please explain your answers (1-3 sentences). c. Is it possible their exists an optimal solution where all the decision variables are not integral? Problem 5: Min Cost Flow Formulation (12 Points) 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 computers. 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 2. a. Formulate a minimum cost network flow problem 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 part (a) in this network.] A B C 2 3 Supply 5 Demand 5 10 8 E FD Supply 10 Demand 10 1 1515 15 45 115 1 15 To ($) From Chicago Austin Los Angeles Boston 80 220 280 Raleigh 100 140 170 Chicago - 40 50 Problem 6: IP Formulation (15 Points) Coach Night is trying to choose the starting lineup for the 2nd round of the NCAA tournament. The team consists of seven players who have been rated (from 1:Poor to 3:NBA bound) according to their ball-handling, shooting, rebounding, and defensive abilities. The positions that each player is allowed to play and the player abilities are listed in the table below. The five player starting lineup must satisfy the following restrictions. 1. At least 4 members must be able to play guard, at least two members must be able to play forward, and at least one player must be able to play center. 2. The average ball-handling, shooting, and rebounding level of the starting lineup must be at least 2. 3. If player 3 starts then player 6 can not start. 4. If player 1 starts then players 4 and 5 must both start 5. Either player 2 or player 3 must start. Given these constraints, Coach Night wants to maximize the total defensive ability of the starting team. Formulate an IP that will help him choose his starting team. Player Position Ball- Handling Shooting Rebounding Defense 1 G 3 3 1 3 2 C 2 1 3 2 3 G-F 2 3 2 2 4 F-C 1 3 3 1 5 G-F 3 3 3 3 6 F-C 3 1 2 3 7 G-F 3 2 2 1 Problem 7: IP Constraints (12 Points) a. How can integer programming be used to ensure that the variable x can assume only the values 1, 2, 3, and 4? b. If x and y are integers, how could you ensure that x + y ≤ 3, 2x + 5y ≤ 12, or both are satisfied by x and y? You may assume that x and y are both bounded above by 10. c. If x and y are both integers, how would you ensure that if x ≤ 2, then y ≤ 3? You may assume that x and y are both bounded above by 10. Problem 8: IP Formulation (12 Points) A city is reviewing the location of its fire stations. The city is made up of a number of neighborhoods. A fire station can be placed in any neighborhood. It is able to handle the fires for both its neighborhood and any adjacent neighborhood (any neighborhood with a non-zero border with its home neighborhood). The objective is to minimize the number of fire stations used. a. Formulate an IP that minimizes the number of firestations needed to be built in order to ensure coverage of every neighborhood. b. The optimum number is 3. Find an optimal solution. c. Give a short proof that there is no solution with only two fire stations. (HINT: find three districts such that these three districts cannot be covered with only two fire stations.) Challenge Problem G: Lower Bound Constraints (6 Points) Consider a network flow problem in which we impose an additional constraint fij ≥ dij for every arc (i, j). Construct an equivalent network flow problem in which there are no nonzero lower bounds on the arc costs. [Hint: Let ijf = fij - dij and construct a new network for the arc flows ijf . How should bi be changed? Massachusetts Institute of Technology
