Introduction to Optimization Problem 1: Max Flows and Minimum Cuts (20 Points) a. b. c. Find the maximum flow from source to sink for the network in Figure 1. Find the maximum flow from source to sink for the network in Figure 2. Find a cut whose capacity equals the maximum flow for the network in Figure 1. Find a cut whose capacity equals the maximum flow for the network in Figure 2. d. 6 Figure 1 1 4 s 4 6 3 2 6 t 1 2 4 4 2 6 Figure 2 6 1 9 3 9 7 s 2 8 t 6 6 6 4 7 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 can we modify a network to incorporate this restriction? b. Suppose a network contains a finite number of arcs and the capacity of each arc is an integer. Answer the following questions: (i) Explain why the Ford Fulkerson method will find the max flow in a finite number of steps. (ii) True or False: The max flow solution found by the Ford Fulkerson algorithm will be integral (Explain your answer). 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. Figure 3 1800 Cleveland Phoenix 900 400 400 1100 950 New York 900 600 St. Louis 600 1300 Dallas Los Angeles 1000 800 600 Nashville 1200 Salt Lake City Problem 4: Min Cost Flow (12 Points) Cost Capacity Supply 5 A 1 Supply 10 2 D B 10 15 1 5 15 3 8 15 E 1 4 15 Demand 5 C F 15 Demand 10 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.] From Boston Raleigh Chicago Chicago 80 100 - To ($) Austin 220 140 40 Los Angeles 280 170 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 1 2 3 4 5 6 7 G C G-F F-C G-F F-C G-F BallHandling 3 2 2 1 3 3 3 Shooting Rebounding Defense 3 1 3 3 3 1 2 1 3 2 3 3 2 2 3 2 2 1 3 3 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. c. 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. 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 f ij = fij - dij and construct a new network for the arc flows f ij . How should bi be changed?