Problem 1: Ford-Fulkerson Algorithm Consider the following Maximum Flow network. 2 5 7 8 3 3 s t 4 2 3 1 6 4 And consider the following residual network resulting from two iterations of the FordFulkerson algorithm. 5 2 5 2 8 3 3 s t 4 2 1 1 4 2 Part A: 4 2 Perform the final two iterations of the Ford-Fulkerson algorithm to determine the maximum flow. Part B: Determine the corresponding minimum cut based on the final residual network. Problem 2: Minimum Cost Network Flow Formulation 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 the following table. From Boston Raleigh Chicago Chicago 80 100 - To ($) Austin 220 140 40 Los Angeles 280 170 50 Part 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. Part B: How would you modify the Part A formulation if at most 200 units could be shipped through Chicago? Part C: How would you modify the network if 500 computers were produced in Raleigh instead of 300? Problem 3: Network Simplex 1 A 0 1 0 D E 0 1 B C 0 1 You are given the above network please perform network simplex iterations given the initial feasible tree as the arcs that are highlighted. Problem 4: Network Simplex Short Answer Consider the uncapacitated network problem shown below. The label next to each arc is its cost. Consider the spanning tree indicated by the dashed lines – that’s the associated basic solution. 3 1 3 4 7 4 1 1 2 6 1 2 3 9 2 2 1 8 5 4 2 1 Part A: What are the values of the arc flows corresponding to this basic solution? Is this a feasible solution? Part B: For this basic solution, find the reduced cost of each arc in the network. Part C: Is this basic solution optimal? Part D: Are there multiple solutions? Part E: By how much can we increase the cost on the arc (5,6) and still have the same basic feasible solution? Part F: If we change the supply at node 1 and the demand at node 9 by a small positive amount δ, what will be the change in optimal cost? Problem 5: Short Answer Part A For a Minimum Cost Network Flow Problem, a supply of -1 for a node is equivalent to a demand of 1. Part B For a Minimum Cost Network Flow problem, if the specified supply is not equal to the demand (that is, the sum of the bi’s does not equal 0), the corresponding Linear Program with flow balance equality constraints must be infeasible. Part C If we add a directed arc from s to t of capacity three, it is possible the max flow will increase by less than three Part D It is possible for an undirected graph to have an Eulerian Path but not an Eulerian Cycle. Part E Suppose all arcs in a network have different lengths. Then the network has a unique shortest path. Part F If we delete all arcs on an s-t path from a graph, the min cut value must strictly decrease (assume all arcs have positive capacity). Problem 6: Multiple Answers Part A Suppose we delete an arc of length k from a graph. Which of the following possibilities can happen to the shortest path from s to t? i) ii) iii) iv) It could increase by any number between 0 and k. It could increase by a number greater than k. It could possibly become infinite. It could decrease. Part B Suppose we have a network where all arc capacities are integer valued. Now, let’s say we increase the capacity of a single arc by 10 units. Then the maximum flow for the network: can stay the same i can increase by 1 to 10 units ii can increase by more than 10 units ivcan decrease Part C Let G = (N, A) be a network with n nodes and m arcs. i) ii) iii) iv) The maximum number of distinct s-t paths can be greater then 2m. If m < n-1, then G is not connected. If m is odd, then the graph can not contain an Eulerian Cycle. If m is even, then every s-t cut has an even number of arcs.