Introduction To Operations Research By Frederick Hillier – Test Bank

Problem 11-1:
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.

Advertising Expenditure Product
1 2 3
1 7 4 6
2 10 8 9
3 14 11 13
4 17 14 15

Use dynamic programming to solve this problem.

Solution for Problem 11-1:

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 xn be the advertising dollars (in millions) spent on product n.
Let sn be the amount of advertising budget remaining.
Let be the increase in sales of product n when xn 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,
s3

1 6 1
2 9 2
3 13 3
4 15 4

For n = 2,
x2 f2(s2, x2) = p2(s2)+

s2 1 2 3 4
2 10 10 1
3 13 14 14 2
4 17 17 17 17 1, 2, 3
5 19 21 20 20 21 2

For n = 1,
x1 f1(s1, x1) = p1(s1)+

s1 1 2 3 4
6 28 27 28 27 28 1, 3

Hence, since s2 = 6 – and s3 = s2 – , there are two optimal plans as given in the table below.

Optimal plan

1 1 2 3
2 3 2 1

Problem 11-2:
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.

Product
1 2 3
Start-up cost, cn 3 2 0
Marginal net revenue, rn 2 3 1
Capacity used per unit, % 20 40 20

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.

Solution For Problem 11-2:

Since the decisions to be made are xn = 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 sn be measured as the number of 20% blocks of production capacity still available for use on the remaining products, so the possible values of sn are 0, 1, 2, 3, 4, 5, where s1 = 5, s2 = 5 – x1, and s3 = s2 – 2×2.

Using the cn and rn values given in the above table, the profit from producing xn units of product n is easily calculated as

pn(xn) = rnxn – cn, 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,
s3

0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5

For n = 2,

x2 f2(s2, x2)

s2 0 1 2
0 0 – – 0 0
1 1 – – 1 0
2 2 1 – 2 0
3 3 2 – 3 0
4 4 3 4 4 0, 2
5 5 4 5 5 0, 2

For n = 1,

x1 f1(s1, x1)
f1*(s1)

s1 0 1 2 3
5 5 3 4 5 5 0, 3

Optimal solution x1* x2* x3*
1 0 0 5
2 0 2 1
3 3 0 2

(b) Now production quantities are treated as continuous variables. Let sn be the percentage of the capacity left for the remaining products. (Note that the units of sn now are different than in part (a), so the possible values of sn now are 0 ≤ sn ≤ 100 rather than 0, 1, 2, 3, 4, 5.) We now have s1 = 100, s2 = 100 -20×1, and s3 = s2 – 40×2.

For product 3: = s3 /20, with = s3 /20.

For product 2: ,

where .

This is linear in x2 except for the term. Therefore, we only need to examine the endpoints of the range for x2.
If x2 = 0, we get = s2 /20.
If x2 = s2 /40, we get .
Equating these two quantities, the breakpoint is s2 =80.
So,

and .

For product 1: ,
where .

Again, this is linear in x1 except for the term. Therefore, we only need to examine the endpoints of the range for x1.
If x1 = 0, we get = 5.5.
If x1 = 3, we get = 6 – 3 + (40) = 5.
So, = 0 and (100) = 5.5.

With = 0, the state at stage 2 becomes s2 = 100, which leads to = 2.5 and s3 = 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.