江西财经大学 2004~2005学年第一学期期末考试试卷 试卷代码:03275A卷 课时:80 课程名称:运筹学Ⅱ(英) 适用对象:管理科学专业 1. Fill in the blanks (10 points) (a)If the objective value is maximum sales revenue, then in dynamic programming, the basic f(Sk=max(v(Sk, xg)+R (Ski)) equation IS MM(Sn+))=0 (b) The dynamic programming is divided into two types, they are: deterministic dynamic programming and probabilistic dynamic programming. (c) The integer programming is divided into three types, they are pure integer programming. mixed integer programming and binary integer programming. ( d )For M/M/I model, the expected number of customers in queueing system isL=d The expected queue length is L (-2) The waiting time in system for each individual customer is w The waiting time in queue for each individual customer is w (-2) 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 Advertising expenditure Product 7 10 2481 36935 Use dynamic programming to solve this problem. (15 points)
1 江西财经大学 2004～2005 学年第一学期期末考试试卷 试卷代码：03275A 卷 课时：80 课程名称：运筹学Ⅱ（英） 适用对象：管理科学专业 1. Fill in the blanks. (10 points) (a) If the objective value is maximum sales revenue, then in dynamic programming, the basic equation is ⎪⎩ ⎪ ⎨ ⎧ = = + + + + + ∈ ( ) 0 ( ) { ( , ) ( )} 1 1 max 1 1 n n k k k k k x D k k f S f S v s x f S k k (b) The dynamic programming is divided into two types, they are: deterministic dynamic programming and probabilistic dynamic programming. (c) The integer programming is divided into three types, they are :pure integer programming, mixed integer programming and binary integer programming. (d) For M/M/1 model, the expected number of customers in queueing system is μ λ λ − L = The expected queue length is ( ) 2 μ μ λ λ − Lq = The waiting time in system for each individual customer is μ − λ = 1 W The waiting time in queue for each individual customer is μ(μ λ) λ − Wq = 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: Product Advertising expenditure 1 2 3 1 2 3 4 7 10 14 17 4 8 11 14 6 9 13 15 Use dynamic programming to solve this problem. (15 points)
Solution: Because the state variable and decision variable is discrete and integer, so we can use network to solving this programming 卖 So the optimal solution is advertise product 1, product 2 and product 3, xI=1, x2=2, X3=3, or xI=3. X2=2, X3=1, the maximum sales is 28 millions 3. Two manufacturers currently are competing for sales in two different but equally profitable product lines. In both cases the sales volume for manufacturer 2 is three times as large as that for manufacturer 1. Because of a recent technological breakthrough, both manufacturers will be making a major improvement in both products. However, they are uncertain as to what development and marketing strategy to follow If both product improvements are developed simultaneously, either manufacturer can have them ready for sale in 12 months. Another alternative as to have a" crash program "to develop only one product first to try to get it marketed ahead of the competition. By doing this manufacturer 2 could have one product ready for sale in 9 months, whereas manufacture 1 would require 10 months(because of previous commitments for its production facilities). For either manufacturer, the second product could then be ready for sale in an additional 9 mo For either product line, if both manufacturers market their improved models simultaneously, it is estimated that manufacturer 1 would increase its share of the total future sales of this product by 8 percent of the total(from 25 to 33 percent). Similarly, manufact I would increase its share by 20, 30, and 40 percent of the total if it marketed the pro than manufacturer 2 by 2, 6, and 8 months, respectively. On the other hand manufacturer I would lose 4, 10, 12, and 14 percent of the total if manufacturer 2 marketed it sooner by 1, 3, 7, and 10 months, respectively Formulate this problem as a two-person, zero-sum game, and then determine which strategy the respective manufacturers should use according to the minimax criterion. (10 points) Solution: two-person, zero-sum game model is
2 Solution: Because the state variable and decision variable is discrete and integer, so we can use network to solving this programming. So the optimal solution is advertise product 1, product 2 and product 3, x1=1,x2=2,x3=3, or x1=3,x2=2,x3=1, the maximum sales is 28 millions. 3. Two manufacturers currently are competing for sales in two different but equally profitable product lines. In both cases the sales volume for manufacturer 2 is three times as large as that for manufacturer 1. Because of a recent technological breakthrough, both manufacturers will be making a major improvement in both products. However, they are uncertain as to what development and marketing strategy to follow. If both product improvements are developed simultaneously, either manufacturer can have them ready for sale in 12 months. Another alternative as to have a “crash program” to develop only one product first to try to get it marketed ahead of the competition. By doing this, manufacturer 2 could have one product ready for sale in 9 months, whereas manufacture 1 would require 10 months (because of previous commitments for its production facilities). For either manufacturer, the second product could then be ready for sale in an additional 9 months. For either product line, if both manufacturers market their improved models simultaneously, it is estimated that manufacturer 1 would increase its share of the total future sales of this product by 8 percent of the total (from 25 to 33 percent). Similarly, manufacturer 1 would increase its share by 20,30,and 40 percent of the total if it marketed the product sooner than manufacturer 2 by 2, 6, and 8 months, respectively. On the other hand, manufacturer 1 would lose 4, 10,12, and 14 percent of the total if manufacturer 2 marketed it sooner by 1,3,7, and 10 months, respectively. Formulate this problem as a two-person, zero-sum game, and then determine which strategy the respective manufacturers should use according to the minimax criterion. (10 points) Solution: two-person, zero-sum game model is 6 2 3 4 5 0 1 2 3 4 0 17 14 10 7 8 4 11 8 4 14 11 8 4 4 8 14 11 6 9 13 15 0 0 6 9 13 15 10 14 17 21 28
Strategies of manufacture 1 Strategies of manufacture 2 Regular programming Crash programming Regular programming 20 Crash mmI According to the minimax criterion, the saddle point is 8. that is manufacture I and 2 both hoice Regular programming 4. The research and development division of a company has been developing four possible new product lines. Management must now make a decision as to which of these four products actually will be produced and at what levels. Therefore, they have asked the or department to formulate a mathematical programming model to find the most profitable product mix A substantial cost is associated with beginning the production of any product, as given in he first row of the following table. The marginal net revenue from each unit produced is given in the second row of the table Product Parallel Units 3 Start-up cost, S 50.000 40.000 70,000 60.000 Marginal revenue. S Let the continuous decision variables x1, x2, x3, and x4 be the production levels of products 1, 2,3 and 4, respectively. Management has imposed the following policy constraints on these (1) No more than two of the products can be produced (2) Either product 3 or 4 can be produced only if either product 1 or 2 is produced (3) Either5x1+3x2+6x3+4x4≤6000 4x1+6x,+3x3+5x4≤6000 Introduce auxiliary binary variables to formulate an MIP model for this problem. (10 points) Solution: the MiP model maxz=70x1+60x2+90x3+80x4-50000y1-40000y2-70000y3-60000y4 y1+y2+y3+y4≤2 y3≤y+y2 ≤1,+ s15x+3x2+6x3+4x≤6000+M 4x1+6x2+3x3+5x4≤6000+M(1-y) My x2≥0,y,y2=0Or 5. Use the BIP branch-and-bound algorithm to solve the following problem interactively(15
3 Strategies of manufacture 1 Strategies of manufacture 2 Regular programming Crash programming Regular programming 8 20 Crash programming 6 -8 According to the minimax criterion, the saddle point is 8. that is manufacture 1 and 2 both choice Regular programming. 4. The research and development division of a company has been developing four possible new product lines. Management must now make a decision as to which of these four products actually will be produced and at what levels. Therefore, they have asked the OR department to formulate a mathematical programming model to find the most profitable product mix. A substantial cost is associated with beginning the production of any product, as given in the first row of the following table. The marginal net revenue from each unit produced is given in the second row of the table. Product Parallel Units 1 2 3 4 Start-up cost,$ Marginal revenue,$ 50,000 70 40,000 60 70,000 90 60,000 80 Let the continuous decision variables x1,x2,x3, and x4 be the production levels of products 1,2,3 and 4, respectively. Management has imposed the following policy constraints on these variables: (1) No more than two of the products can be produced. (2) Either product 3 or 4 can be produced only if either product 1 or 2 is produced (3) Either 6000 5 3 6 4 x1 + x2 + x3 + x4 ≤ Or 6000 4x1 + 6x2 + 3x3 + 5x4 ≤ Introduce auxiliary binary variables to formulate an MIP model for this problem. (10 points) Solution: the MIP model is ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = ≤ + + + ≤ + − + + + ≤ + ≤ + ≤ + + + + ≤ = + + + − − − − 0, , 0 1 4 6 3 5 6000 (1 ) 5 3 6 4 6000 2 . . max 70 60 90 80 50000 40000 70000 60000 1 2 3 4 1 2 3 4 4 1 2 3 1 2 1 2 3 4 1 2 3 4 1 2 3 4 x y y or x My x x x x M y x x x x My y y y y y y y y y y st Z x x x x y y y y i i i i 5. Use the BIP branch-and-bound algorithm to solve the following problem interactively (15 points)
Max z= 2 5x2-3x4+4 3x1-2x2+7x3-5x4+4x5≤6 s{x1-x2+2x3-4x4+2x5≤0 x, is binary x1=1-y1,x2=y2,x3 odel is changed Maxz=11-2y1-y2-5y3-3y4-4y y1-2y2-1y3-5y4-4y s-y-y2-2y3-4y4-2y is bir No feasible solution No feasible solution =0 No feasible solution So, the optimal solution is y1=1,y2=0,y3=0,y4=1, y5=0, that is x1=0, x2=0, X3=1, x4=1, x5=1 the optimal value is z=6 6. Consider the following linearly constrained optimization problem f(x)=ln(x1+1)+x 2x,+x,≤3 x,≥0 x2 ≥0 Use the KKt conditions to derive an optimal solution (15 points) Solution: Using the KKT conditions, we derive the following equations
4 ⎪ ⎩ ⎪ ⎨ ⎧ − + − + ≤ − + − + ≤ = − + − + x is binary x x x x x x x x x x st Max Z x x x x x j 2 4 2 0 3 2 7 5 4 6 . . 2 5 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 Solution: we set 1 1 2 2 3 3 4 4 5 1 5 x = 1− y , x = y , x = 1− y , x = y , x = − y , the model is changed into ⎪ ⎩ ⎪ ⎨ ⎧ − − − − − ≤ − − − − − − ≤ − = − − − − − y is binary y y y y y y y y y y st Max Z y y y y y j 2 4 2 5 3 2 7 5 4 8 . . 11 2 5 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 So, the optimal solution is y1=1,y2=0,y3=0,y4=1,y5=0, that is x1=0,x2=0,x3=1,x4=1,x5=1, the optimal value is z=6 6. Consider the following linearly constrained optimization problem: ⎩ ⎨ ⎧ ≥ ≥ + ≤ = + + 0, 0 2 3 . . ( ) ln( 1) 1 2 1 2 1 2 x x x x st Max f x x x Use the KKT conditions to derive an optimal solution. (15 points) Solution: Using the KKT conditions, we derive the following equations: 1 2 7 4 3 y3=1 y3=0 y4=1 y4=0 z=3 5 6 y5=0 y5=1 No feasible solution z=2 y4=0 y4=1 No feasible solution 8 9 10 11 y5=1 y5=0 z=4 y1=1 y1=0 z=6 No feasible solution
2l1≤0 +1 2u1|=0 1-l1≤0 x2(1-1)=0 u1(2x1+x2-3)=0 x120,x20,120 Solving this equations system, we get the optimal solution x=0, X2=3, un=1 7. You are given a two-server queueing system in a steady-state condition where the number of customers in the system varies between 0 and 4. For n=0, 1, .., 4, the probability Pn that exactly n customers are in the system is Po=12,P1-1,P2=1,p3=,P416 a)Determine L, the expected number of customers in the system (c) Determine the expected number of customers being served (b)Determine Lg, the expected number of customers in the que (d)Given that the mean arrival rate is 2 customers per hour, determine the expected waiting time in the system, W, and the expected waiting time in the queue, Wa (e) Given that both serves have the same expected service time, use the results from part(d) to determine this expected service time. (15 points) Solution:(a)the expected number of customers in the system L=>np.=2 (b) The expected number of customers in the queue L, =2(n-2)P,=3/8 (c) The expected number of customers being served is E=L-L=2-3/8=13/8 (d)The expected waiting time in the system W=-=-=l, the expected waiting time in the 2 quee, W9=2-16 (e) This expected service time 8. A bank employs 4 tellers to serve its customers. Customers arrive according to a Poisson
5 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ + − = + − ≤ − = − ≤ =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − + − ≤ + 0, 0, 0 (2 3) 0 2 3 0 (1 ) 0 1 0 2 0 1 1 2 0 1 1 1 2 1 1 1 2 1 2 2 1 1 1 1 1 1 1 x x u u x x x x x u u u x x u x Solving this equations system, we get the optimal solution x1=0,x2=3,u1=1. 7. You are given a two-server queueing system in a steady-state condition where the number of customers in the system varies between 0 and 4. For n=0,1,….,4, the probability Pn that exactly n customers are in the system is 16 1 , 16 4 , 16 6 , 16 4 , 16 1 p0 = p1 = p2 = p3 = p4 = . (a) Determine L, the expected number of customers in the system. (b) Determine Lq, the expected number of customers in the queue. (c) Determine the expected number of customers being served. (d) Given that the mean arrival rate is 2 customers per hour, determine the expected waiting time in the system, W, and the expected waiting time in the queue, Wq. (e) Given that both serves have the same expected service time, use the results from part (d) to determine this expected service time. (15 points) Solution: (a) the expected number of customers in the system 2 4 0 = ∑ = n= L npn (b) The expected number of customers in the queue 8 ( 2) 3/ 4 2 = ∑ − = n= Lq n pn (c) The expected number of customers being served is E = L − Lq = 2 − 3/ 8 = 13/ 8 (d) The expected waiting time in the system 1 2 2 = = = q L W , the expected waiting time in the queue, 16 3 = = λ q q L W (e) This expected service time is 16 1 13 = W −Wq = μ 8. A bank employs 4 tellers to serve its customers. Customers arrive according to a Poisson
process at a mean rate of 3 per minute. If a customer finds all tellers busy, he joins a queue that is serviced by all tellers; 1. e. there are no lines in front of each teller but rather one line waiting for the first available teller. The transaction time between the teller and customer has an exponential distribution with a mean of l minute Find the steady-state probability distribution of the number of customers in the bank (10 points) Solution: The probability of non customer in the system is a/su The probability of n customer in the system (1/)2 P.0<n<4 0<n<4 n n! 53 P 3 P,n≥4 44-,n24
6 process at a mean rate of 3 per minute. If a customer finds all tellers busy, he joins a queue that is serviced by all tellers; i.e., there are no lines in front of each teller, but rather one line waiting for the first available teller. The transaction time between the teller and customer has an exponential distribution with a mean of 1 minute. Find the steady-state probability distribution of the number of customers in the bank. (10 points). Solution: The probability of non customer in the system is ( ) ( ) 53 2 1 / 1 ! / ! / 1 1 0 0 = − + ⋅ = ∑ − = λ μ λ μ λ μ n s s P s s n n The probability of n customer in the system is ( ) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ⋅ ⋅ ≤ ≤ = ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ⋅ ≤ ≤ = − − , 4 4!4 3 , 0 4 53 2 ! 3 , 4 4!4 / , 0 4 ! / 0 4 0 4 0 P n n n P n P n n P n n n n n n n λ μ λ μ