江西财经大学 2005~2006学年第一学期期末考试试卷 试卷代码:03275A卷 课时:80 课程名称:运筹学Ⅱ(英) 适用对象:管理科学专业 1. Fill in the blanks(10 points) (a)In dynamic programming problem, when stage evaluation index is probability, then the recursive relationship Is (b) The key point of probabilistic dynamic programming differs from deterministic dynamic programming (c)For non-linear programming, the local optimal solution is not generally a global optimal solution, but it (d) The model M/M/I means that in a queueing system, all interarrival times are distributed according and all service times are distributed according and the number of servers is e) The birth-and-death equation for the following graph is λn-2 un-1 2. Three Or teams adopt different methods to study a scientific research project. The probability of failure is 0.40, 0.60, 0.80 respectively. To decrease the probability of all three probability of each teams is listed in following tabe research teams, and after that, the failure teams defeated two scientists are allocated to these Allocated scientists OR Team Team 3 0 0.40 0.15 Using dynamic programming to solving this problem, the objective is to minimize the total failure probability of three teams.(15 points 3. A toy manufacturer has developed two new toys for possible inclusion in its product line for the upcoming Christmas season. Setting up the production facilities to begin production would cost $50,000 for toy 1 and $80,000 for toy 2. Once these costs are covered, the toys would generate a unit profit of $10 for toy l and $15 for toy 2 The company has two factories that are capable of producing these toys. However, to avoid doubling the start-up costs, just one factory would be used and the choice would be
1 江西财经大学 2005～2006 学年第一学期期末考试试卷 试卷代码：03275A 卷 课时：80 课程名称：运筹学Ⅱ（英） 适用对象：管理科学专业 1. Fill in the blanks (10 points) (a) In dynamic programming problem, when stage evaluation index is probability, then the recursive relationship is (b) The key point of probabilistic dynamic programming differs from deterministic dynamic programming is . (c) For non-linear programming, the local optimal solution is not generally a global optimal solution, but it is true for . (d) The model M/M/1 means that in a queueing system, all interarrival times are distributed according to , and all service times are distributed according to , and the number of servers is . (e) The birth-and-death equation for the following graph is 2. Three OR teams adopt different methods to study a scientific research project. The probability of failure is 0.40，0.60，0.80 respectively. To decrease the probability of all three teams defeated, two scientists are allocated to these research teams, and after that, the failure probability of each teams is listed in following table Allocated scientists OR Team Team 1 Team 2 Team 3 0 0．40 0．60 0．80 1 0．20 0．40 0．50 2 0．15 0．20 0．30 Using dynamic programming to solving this problem, the objective is to minimize the total failure probability of three teams。（15 points）。 3. A toy manufacturer has developed two new toys for possible inclusion in its product line for the upcoming Christmas season. Setting up the production facilities to begin production would cost $50,000 for toy 1 and $80,000 for toy 2. Once these costs are covered, the toys would generate a unit profit of $10 for toy 1 and $15 for toy 2. The company has two factories that are capable of producing these toys. However, to avoid doubling the start-up costs, just one factory would be used and the choice would be n-2 n-1 n n+1 λn-2 μn-1 λn-1 λn μn μn+1
based on maximizing profit. For administrative reasons, the same factory would be used for both new toys if both are produced Toy 1 can be produced at the rate of 50 per hour in factory 1 and 40 per y 2 can be produced at the rate of 40 per hour in factory 1 and 25 per hour in factory 2 factories 1 and 2, respectively, have 500 and 700 hours of production time available before Christmas that could be used to produce these toys It is not known whether these two toys would be continued after Christmas. Therefore, the problem is to determine how many units (if any)of each new toy should be produced before Christmas in order to maximize the total profit Formulate an IP model for this problem. (10 points) 4. Use the BlP branch-and-bound algorithm to solve the following problem interactively.(15 points Maxz=8x1+2x2-4x3-7x4-5x5 3x1+3x2+x3+2x4+3x5≤4 s15x+3x2-2x3-x4+x≤4 5. Solving the following game model. (10 points) A 2042 6. Consider the following linearly constrained optimization problem: (15 points) Maxf(x)=15x+30x2+4x2-2x2-4x2 +2x2≤30 x1≥0,x2≥0 Use the Kkt conditions to derive an optimal solution 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=16 P!16 P2=16.Ps-16, P416 (a) Determine L, the expected number of customers in the system (b) Determine Lg, 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, Wa
2 based on maximizing profit. For administrative reasons, the same factory would be used for both new toys if both are produced. Toy 1 can be produced at the rate of 50 per hour in factory 1 and 40 per hour in factory 2. toy 2 can be produced at the rate of 40 per hour in factory 1 and 25 per hour in factory 2. factories 1 and 2, respectively, have 500 and 700 hours of production time available before Christmas that could be used to produce these toys. It is not known whether these two toys would be continued after Christmas. Therefore, the problem is to determine how many units (if any) of each new toy should be produced before Christmas in order to maximize the total profit. Formulate an IP model for this problem. (10 points) 4. Use the BIP branch-and-bound algorithm to solve the following problem interactively. (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ + − − + ≤ + + + + ≤ = + − − − x is binary x x x x x x x x x x st Max Z x x x x x j 5 3 2 4 3 3 2 3 4 . . 8 2 4 7 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 5. Solving the following game model. (10 points) ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − − = 4 2 2 0 2 0 4 2 4 8 2 6 2 4 0 2 A 6. Consider the following linearly constrained optimization problem: (15 points) ⎩ ⎨ ⎧ ≥ ≥ + ≤ = + + − − 0, 0 2 30 . . ( ) 15 30 4 2 4 1 2 1 2 2 2 2 1 2 1 2 1 x x x x st Max f x x x x x x x Use the KKT conditions to derive an optimal solution. 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) 8. You are given an M/M/I queueing system with mean arrival rate a and mean service rate u. An arriving customer receives n dollars if customers are already in the system Determine the expected cost in dollars per customer. (10 points)
3 (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) 8. You are given an M/M/1 queueing system with mean arrival rate λ and mean service rate μ. An arriving customer receives n dollars if customers are already in the system. Determine the expected cost in dollars per customer. (10 points)
