Homework 5

Due in class, 8 March, 2012
  1. Set up the shortest-path problem as in (P) on page 110 for the graph in Figure 4-1 (p. 92) and show how simplex can find either shortest path from s to t. Show how simplex finds the correct path if one of the edges leaving s has weight 2.
  2. Find the vertex of the polytope defined by (8.2) on page 168 that has the highest cost, and show that there is an edge from this vertex to the optimal vertex.
  3. Given the following flow network with all edge capacities equal to 1:

    Show how to set up a program in the form of 5.21 on page 114. Which optimal solutions correspond to vertices of the polytope? Are there other optimal solutions?