# Question: Consider the following network where each number along a link

Consider the following network, where each number along a link represents the actual distance between the pair of nodes connected by that link. The objective is to find the shortest path from the origin to the destination.

(a) What are the stages and states for the dynamic programming formulation of this problem?

(b) Use dynamic programming to solve this problem. However, instead of using the usual tables show your work graphically (similar to Fig. 11.2). In particular, start with the given network, where the answers already are given for fn*(sn) for four of the nodes; then solve for and fill in f2*(B) and f1*(O). Draw an arrowhead that shows the optimal link to traverse out of each of the latter two nodes. Finally, identify the optimal path by following the arrows from node O onward to node T.

(c) Use dynamic programming to solve this problem by manually constructing the usual tables for n = 3, n = 2, and n = 1.

(d) Use the shortest-path algorithm presented in Sec. 9.3 to solve this problem. Compare and contrast this approach with the one in parts (b) and (c).

(a) What are the stages and states for the dynamic programming formulation of this problem?

(b) Use dynamic programming to solve this problem. However, instead of using the usual tables show your work graphically (similar to Fig. 11.2). In particular, start with the given network, where the answers already are given for fn*(sn) for four of the nodes; then solve for and fill in f2*(B) and f1*(O). Draw an arrowhead that shows the optimal link to traverse out of each of the latter two nodes. Finally, identify the optimal path by following the arrows from node O onward to node T.

(c) Use dynamic programming to solve this problem by manually constructing the usual tables for n = 3, n = 2, and n = 1.

(d) Use the shortest-path algorithm presented in Sec. 9.3 to solve this problem. Compare and contrast this approach with the one in parts (b) and (c).

## Answer to relevant Questions

Consider the following integer nonlinear programming problem. Maximize Z = 18x1 – x21 + 20x2 + 10x3, Subject to 2x1 + 4x2 + 3x3 ≤ 11 and x1, x2, x3 are nonnegative integers. Use dynamic programming to solve this problem. Consider the following nonlinear programming problem. Maximize Z = x31 + 4x22 + 16x3, Subject to x1 x2 x3 =4 and x1 ≥ 1, x2 ≥ 1, x3 ≥ 1. (a) Solve by dynamic programming when, in addition to the given constraints, all ...A backgammon player will be playing three consecutive matches with friends tonight. For each match, he will have the opportunity to place an even bet that he will win; the amount bet can be any quantity of his choice between ...Use dynamic programming to solve the Northern Airplane Co. production scheduling problem presented in Sec. 9.1 (see Table 9.7). Assume that production quantities must be integer multiples of 5. The Fly-Right Airplane Company builds small jet airplanes to sell to corporations for the use of their executives. To meet the needs of these executives, the company’s customers sometimes order a custom design of the ...Post your question