Problem 3. [20'] There is a simplified road map between Seattle (Node 1) and New York (Node 11). If two nodes are connected by an edge, there exists a road between these two nodes. The numbers on the edges represents the scaled length of the corresponding roads. 1 5 2 3 2 3 13 8 5 12 5 7 8 Figure 3: Road map between cities 3 5 10 11 (1) [12] A student wants to take a road trip from Seattle to New York. Give an LP formulation to minimize the total distance traveled. Clearly define the decision variables, the objective function, and the constraints. (2) [8] The government needs to construct good quality telephone lines to connect all cities in Figure 3 for emergency use. Specifically, all cities in the map should be connected with at least one other city, so that all cities can contact each other. Provide a construction plan to minimize the total distances.

Problem 3. [20'] There is a simplified road map between Seattle (Node 1) and New York (Node 11). If two nodes are connected by an edge, there exists a road between these two nodes. The numbers on the edges represents the scaled length of the corresponding roads. Figure 3: Road map between cities (1) [12] A student wants to take a road trip from Seattle to New York. Give an LP formulation to minimize the total distance traveled. Clearly define the decision variables, the objective function, and the constraints. (2) [8] The government needs to construct good quality telephone lines to connect all cities in Figure 3 for emergency use. Specifically, all cities in the map should be connected with at least one other city, so that all cities can contact each other. Provide a construction plan to minimize the total distances