江西财经大学 2005~2006学年第一学期期末考试试卷 试卷代码:03275A卷 课时:80 课程名称:运筹学Ⅱ(英 适用对象:管理科学专业 1. Fill in the blanks(10 points) (a)In dynamic programming problem, when stage evaluation index is probability, then the f(Sk)=opt Iv(Sk, xk) fk+(Sk+)) recursive relationship is xk∈D Un+ (Sn+1)=1 (b) The key point of probabilistic dynamic programming differs from deterministic dynamic programming is the state at the next stage is not completely determined by the state and policy decision at the current (c)For non-linear programming, the local optimal solution is not generally a global optimal solution, but it Is true for convex programming (d) The model M/M/I means that in a queueing system, all interarrival times are distributed according to an exponential distribution, and all service times are distributed according to another exponential distribution and the number of servers is 1 (e) The birth-and-death equation for the following graph is An-P-+umPm=(+u)P λn-2 2 1 n n+1 u n- 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 2 ean 0 0.40 0.60 0.80 0.20 0.40 2 0.15 dynamic programming to solving this problem, the objective is to minimize the total failure probability of three teams (15 points Solution: Using network method to solving this problem, the network graph is
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 ⎪⎩ ⎪ ⎨ ⎧ = = ⋅ + + + + ∈ ( ) 1 ( ) { ( , ) ( )} 1 1 1 1 n n k k k k k x D k k f S f S opt v s x f S k k (b) The key point of probabilistic dynamic programming differs from deterministic dynamic programming is the state at the next stage is not completely determined by the state and policy decision at the current stage. (c) For non-linear programming, the local optimal solution is not generally a global optimal solution, but it is true for convex programming. (d) The model M/M/1 means that in a queueing system, all interarrival times are distributed according to an exponential distribution, and all service times are distributed according to another exponential distribution, and the number of servers is 1. (e) The birth-and-death equation for the following graph is n Pn n Pn n n Pn ( ) λ −1 −1 + μ +1 +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 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）。 Solution: Using network method to solving this problem, the network graph is n-2 n-1 n n+1 λn-2 μn-1 λn-1 λn μn μn+1
0.80 0.30 0.40 50 0.50 0.16 0.30 0.60 The optimal solution is x1=1, x2=0, X3=1 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 9L The company has two factories that are capable of producing these toys. However, to oid doubling the start-up costs, just one factory would be used and the choice would be 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) Solution: we set produce the two toys x1, x2
2 The optimal solution is x1=1, x2=0, x3=1 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 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) Solution: we set produce the two toys x1,x2 2 0.15 0.20 0.40 0.06 0 1 2 0 1 2 0 0.48 0.30 0.16 0.80 0.50 0.30 0.60 0.40 0.60 0.20 0.60 0.40 0.30 0.50 0.80
maxz=10x1+15x2-50000y1-80000 ≤500+Mv +≤700+(1-M)y The lP model of this problem is . 40 25 x1≤M1 x,≤My y,y,y2 are binary 4. Use the BIP branch-and-bound algorithm to solve the following problem interactively(15 z=8x1+2x2-4x3-7x4-5 3x1+3x,+x2+2x1+3x。≤4 s15x1+3x2-2x3-x4+x5≤4 Solution: we set x, 1-y, x2=1-y2, x3=y3, x4= y4, xs =ys, the model is changed into Max z=10-8y1 3y1-3y2+y2+2y4+3 s1-5y1-3y2-2y3-4y4+y 2 No feasible soluti So, the optimal solution is y1=0, y2=1, y3=1,y4=0, y5=0, that is x1=1, x2=0, x3=1, X 4=0, x5=0, the optimal 5. Solving the following game model. (10 points)
3 The IP model of this problem is ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≤ ≤ + ≤ + − + ≤ + = + − − , 0 , , 700 (1 ) 40 25 500 50 40 . . max 10 15 50000 80000 1 2 1 2 2 2 1 1 1 2 1 2 1 2 1 2 x x y y y are binary x My x My M y x x My x x st Z x x y y 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 Solution: we set 1 1 2 2 3 3 4 4 5 5 x = 1− y , x = 1− y , x = 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 5 3 2 4 4 3 3 2 3 2 . . 10 8 2 4 7 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 So, the optimal solution is y1=0,y2=1,y3=1,y4=0,y5=0, that is x1=1,x2=0,x3=1,x4=0,x5=0, the optimal value is z=4 5. Solving the following game model. (10 points) 1 y1=1 y1=0 3 z=2 2 y2=1 y2=0 4 y3=1 y3=0 z=4 5 6 No feasible solution 7 No feasible solution
4826 A 4-2-20 Solution: Using dominate strategy method, we get the simpler 2X2matrix 2 4/,and we solved this matrix model, got the optimal solution: x,=0,x24'5NI 0 y=4. 22=0, y34y4=0, the value of this game is V=5/2 6. Consider the following linearly constrained optimization problem: (15 points) Mxf(x)=15x1+30x2+4x1x2-2x12-4x2 +2x,≤30 x1≥0.x1≥0 Use the KKT conditions to derive an optimal solution Solution: Using the KKt conditions, we derive the following equations u x(15+4x2-4x1-a1)=0 30+4x,-8x,-2l,≤0 x2(30+4x1-8x2-21)=0 2 30≤0 u1(x1+2x2-30)=0 x1≥0,x2≥0,120 Solving this equations system, we get the optimal solution x =12, X2=9 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 (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 (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)
4 ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − − = 4 2 2 0 2 0 4 2 4 8 2 6 2 4 0 2 A Solution: Using dominate strategy method, we get the simpler 2×2matrix： ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − 2 4 4 2 ，and we solved this matrix model, got the optimal solution ： , 0 4 1 , 4 3 0, x1 = x2 = x3 = x4 = ， , 0 4 3 , 0, 4 1 y1 = y2 = y3 = y4 = ，the value of this game is V=5/2。 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. Solution: Using the KKT conditions, we derive the following equations: ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ + − = + − ≤ + − − = + − − ≤ + − − = + − − ≤ 0, 0, 0 ( 2 30) 0 2 30 0 (30 4 8 2 ) 0 30 4 8 2 0 (15 4 4 ) 0 15 4 4 0 1 2 1 1 1 2 1 2 2 1 2 1 1 2 1 1 2 1 1 2 1 1 x x u u x x x x x x x u x x u x x x u x x u Solving this equations system, we get the optimal solution x1=12, x2=9. 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 L=2np.=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-378=13/8 (d) The expected waiting time in the system W L 2=1, the expected waiting time in the queue, Wa= 16 (e)This expected service time =W-_13 16 8. You are given an M/M/1 queueing system with mean arrival rate x 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) Solution: the expected cost in dollars per customer is E=n(l-Po)=n(
5 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. 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) Solution: the expected cost in dollars per customer is (1 ) (1 ) 0 μ λ E = n − p = n −