Combinatorics and optimization

Question 1 (20 points) You want to decide the production of an item in the next n periods. For each period t = 1, ....n, there is a demand for d 2 0 units of the product which must be satisfied. Also, there is a cost associated to producing the product in that period, which is of dollars per unit produced. You are also allowed to stock the product from period { to period { + 1 for h, 2 0 dollars per unit of product stored (there is no maximum storage capacity and product can be stored for however long necessary). Any product that gets produced must be immediately used to satisfy the demand or stored for the next period. You wish to decide what is the minimum cost way to satisfy all the demand. You may assume that whatever gets produced in period t can be used to satisfy the demand of that same period. Denote by If the amount produced in period t and s, the amount stocked from period : to t + 1. You may assume that initial and final stock must be zero. (a) Show that there always exists an optimal solution (r*, s* ) to the problem that 1. s_10 = 0 for all t (that is, production only takes place when the stock is 0. 2. It >0 implies r = _ d; for some integer k 2 0. (b) Use this to derive a dynamic programming recursion for the