Problem 1. Consider the optimization problem max 4z1 + 5z2 + 4z3 +824 +675 4z1 +672 + 5z3 +974 +7z5 0, j=1, ...,5. Assume that all z; may take only nonnegative integer values. (a) Formulate a dynamic programming problem for solving problem (1). Describe the state space, the action space, the feasible action mapping, and the dynamic programming equation. (b) Use the dynamic programming equations to obtain the optimal solution. Problem 2. Let A1,...,An be matrices with A; having ki-1 rows and k; columns for i=0,1,2,...,n. and some positive integers ko, k1, ... ,kn. The problem is to choose the order of multiplying the matrices that will minimize the number of multiplications needed to compute the product AjA2 -- An. (a) Formulate a dynamic programming problem to determine the optimal order in which to mul- tiply the matrices. Clearly formulate the dynamic programming equation. (b) Solve the problem numerically, when n = 4 and (ko, k1, ...,k4) = (10,30, 70, 2, 100). Problem 1. Consider the optimization problem max 4z1 + 5z2 + 4z3 +824 +675 4z1 +672 + 5z3 +974 +7z5 0, j=1, ...,5. Assume that all z; may take only nonnegative integer values. (a) Formulate a dynamic programming problem for solving problem (1). Describe the state space, the action space, the feasible action mapping, and the dynamic programming equation. (b) Use the dynamic programming equations to obtain the optimal solution. Problem 2. Let A1,...,An be matrices with A; having ki-1 rows and k; columns for i=0,1,2,...,n. and some positive integers ko, k1, ... ,kn. The problem is to choose the order of multiplying the matrices that will minimize the number of multiplications needed to compute the product AjA2 -- An. (a) Formulate a dynamic programming problem to determine the optimal order in which to mul- tiply the matrices. Clearly formulate the dynamic programming equation. (b) Solve the problem numerically, when n = 4 and (ko, k1, ...,k4) = (10,30, 70, 2, 100)