Deck 11: Dynamic Programming

Question 1

The management of a company is considering three possible new products for next year's product line.A decision now needs to be made regarding which products to market and at what production levels.Initiating the production of two of these products would require a substantial start-up cost,as shown in the first row of the table below.Once production is under way,the marginal net revenue from each unit produced is shown in the second row.The third row gives the percentage of the available production capacity that would be used for each unit produced. Only 3 units of product 1 could be sold,whereas all units that could be produced of the other two products could be sold.The objective is to determine the number of units of each product to produce in order to maximize the total profit (total net revenue minus start-up costs).(a)Assuming that production quantities must be integers,use dynamic programming to solve this problem.(b)Now consider the case where the divisibility assumption holds so that the variables representing production quantities are treated as continuous variables.Assuming that proportionality holds for both net revenues and capacities used,use dynamic programming to solve this problem.

Answer 1

Since the decisions to be made are x_n = production level of product n,for n = 1,2,3,the stages for a dynamic programming formulation of this problem correspond to the three products.When making the decision for a particular product,the essential information is the amount of production capacity still remaining,so this becomes the current state in this formulation.(a)At stage n,let the state s_n be measured as the number of 20% blocks of production capacity still available for use on the remaining products,so the possible values of s_n are 0,1,2,3,4,5,where s₁ = 5,s₂ = 5 - x₁,and s₃ = s₂ - 2x₂.Using the c_n and r_n values given in the above table,the profit from producing x_n units of product n is easily calculated as p_n(x_n)= r_nx_n - c_n,for n = 1,2,3.Therefore,using the usual dynamic programming notation presented in Sec.11.2 of the textbook,we have , , .Using these expressions for for n = 3,then n = 2,and then n = 1 in turn,the dynamic programming calculations are given below.For n = 3, For n = 2, For n = 1, (b)Now production quantities are treated as continuous variables.Let s_n be the percentage of the capacity left for the remaining products.(Note that the units of s_n now are different than in part (a),so the possible values of s_n now are 0 ≤ s_n ≤ 100 rather than 0,1,2,3,4,5.)We now have s₁ = 100,s₂ = 100 -20x₁,and s₃ = s₂ - 40x₂.For product 3: = s₃ /20,with = s₃ /20.For product 2: ,where .This is linear in x₂ except for the term.Therefore,we only need to examine the endpoints of the range for x_2. If x₂ = 0,we get = s₂ /20.If x₂ = s₂ /40,we get .Equating these two quantities,the breakpoint is s₂ =80.So, and .For product 1: ,where .Again,this is linear in x₁ except for the term.Therefore,we only need to examine the endpoints of the range for x_1. If x₁ = 0,we get = 5.5.If x₁ = 3,we get = 6 - 3 + (40)= 5.So, = 0 and (100)= 5.5.With = 0,the state at stage 2 becomes s₂ = 100,which leads to = 2.5 and s₃ = 0,so = 0.Therefore,the optimal solution is to produce 2.5 units of product 2,but none of products 1 and 3,with a profit of 5.5.This is better than with the integer restriction in part (a),as we would expect.

Question 2

A company is planning its advertising strategy for next year for its three major products.Since the three products are quite different,each advertising effort will focus on a single product.In units of millions of dollars,a total of 6 is available for advertising next year,where the advertising expenditure for each product must be an integer greater than or equal to 1.The vice-president for marketing has established the objective: Determine how much to spend on each product in order to maximize total sales.The following table gives the estimated increase in sales (in appropriate units)for the different advertising expenditures. Use dynamic programming to solve this problem.

Answer 2

Since the decisions to be made are the advertising expenditures on the three products,the stages for a dynamic programming formulation of this problem correspond to the three products.When making the decision for a particular product,the essential information is the amount of the advertising budget still remaining,so this becomes the current state in this formulation.Let x_n be the advertising dollars (in millions)spent on product n.Let s_n be the amount of advertising budget remaining.Let be the increase in sales of product n when x_n million dollars are spent on product n,as given by the above table.Then,using the usual dynamic programming notation presented in Sec.10.2 of the textbook,the recursive relationship for this problem is .The solution procedure now starts at the end (stage 3)and moves backward stage by stage.For n = 3, For n = 2, For n = 1, Hence,since s₂ = 6 - and s₃ = s₂ - ,there are two optimal plans as given in the table below.

Question 3

Consider the following integer nonlinear programming problem.Maximize Z = ,subject to ≥ 1, ≥ 1, ≥ 1,and , , are integers.Use dynamic programming to solve this problem.

Answer 3

The three stages involve making the decisions on the values of the three variables in order.At stage n,let the state s_n be the remaining slack in the constraint ,so s₁ = 10,s₂ = 10 - x₁,and s₃ = s₂ - 2x₂.Let .Then ,and for n = 1,2.For n = 3, For n = 2, For n = 1, Since = 2 leads to s₂ = 10 - = 8 and = 1,which then leads to s₃ = s₂ - 2 = 6 and = 2,it follows that (x₁,x₂,x₃)= (2,1,2)is optimal with Z = 16.

Question 4

Consider the following nonlinear programming problem.Maximize Z = ,subject to 2 + ≤ 13 + ≤ 9 and ≥ 0, ≥ 0.Use dynamic programming to solve this problem.

Question 5

Consider the following nonlinear programming problem.Maximize Z = ,subject to and ≥ 0, ≥ 0.Use dynamic programming to solve this problem.