Old MathJax webview

I want it with in two hours.

4. (25 points) A traveling salesperson plans to visit the 6 cities represented below, but would like to minimize their overall travel time. 2 i 3 3 6 0 6 The hours it takes to travel from city i to city j is given as the (1,3)-entry in the symmetric matrix so 2 7 10 13 14] 2 0 7 12 13 7 6 5 7 10 C = [cv] - 107 5 0 7 13 12 7 6 0 2 [14 13 10 7 2 0 Write out the linear programming problem on the previous page) and find the optimal solution without adding any constraints. There will be cycles. Add a constraint and find the optimal solution. Repeat until there is a tour. Clearly write out each iteration of the linear programming problem and each additional constraint. Explain your process as you go Note that you don't need to write out the coefficients, simply write the sums in condensed form using C, and define a set S.S., Sk as constraints are added. Do not use the simplex method or dual simplex method. Instead, use trial and error for every iteration to understand the graph. 3. (20 points) Consider the flow network where the capacities of the edges are given in the matrix TO 9 12 0 0 0 0 0 0 6 9 4 3 0 0 0 0 2 6 3 0 C = 0 0 0 0 2 0 7 0 0 0 0 0 28 0 0 0 0 0 0 5 0 0 0 0 0 0 0 In matrix C = [cu], the C entry represents the capacity of the edge from node i to node j. A quick drawing of the graph without capacities is given below. 7 (a) Draw a diagram of the flow network. (b) Find a maximal flow by drawing all iterations of the flow diagram and writing the path taken for each (c) Give the value of the maximal flow. (d) Find a minimal cut: draw the minimal cut and give the value