江西财经大学 0405学年第二学期期末考试试卷(参考答案 试卷代码:03883B卷 课时:64 课程名称:运筹学I(英) 适用对象:03管理科学专业 1. Label each of the following statements about linear programming problems as true or false (10 (a)When the simplex method solves for the next BF solution, elementary algebraic operations are used to eliminate each nonbasic variable from all but one equation (its equation) and to give it a coefficient of +l in that one equation( True (b)If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. True (c) The simplex methods rule for choosing the entering basic variable is used because it always leads to the best adjacent BF solution (largest Z).( False ( d) The simplex methods minimum ratio rule fro choosing the leaving basic variable used because making another choice with a large ratio would yield a basic solution that is not feasible. True (e)If at least one of the basic variables has a coefficient of zero in row o of the final tableau, then the problem has multiple optimal solutions.( False 2. A company needs to lease warehouse storage space over the next 5 months. Just how much space will be required in each of these months is known. However, since these space requirements are quite different, it may be most economical to lease only the amount needed each month on a month-by-month basis. On the other hand, the additional cost for leasing space for additional months is much less than for the first month, so it may be less expensive to lease the maximum amount needed for the entire 5 months. Another option is the intermediate approach of changing the total amount of space leased(by adding a new lease and /or having an old lease expire)at least once but not every month The space requirement (in thousands of square feet) and the leasing costs(in hundreds of dollars) for the various leasing periods are as follows month Required space (000Leasing eriod Cost per 1,000 square Square feet) (Months) feet leased ($00 650 12345 20 1.000 350 600 The objective is to minimize the total leasing cost for meeting the space requirements. Please formulate a linear programming model for this problem. (10 Solution: we denote xi as the ith month lease months period warehouse. The linear
1 江西财经大学 04-05 学年第二学期期末考试试卷（参考答案） 试卷代码：03883B 卷 课时：64 课程名称：运筹学 I（英） 适用对象：03 管理科学专业 1. Label each of the following statements about linear programming problems as true or false. (10 points) (a) When the simplex method solves for the next BF solution, elementary algebraic operations are used to eliminate each nonbasic variable from all but one equation (its equation) and to give it a coefficient of +1 in that one equation. ( True ) (b) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. ( True ) (c) The simplex method’s rule for choosing the entering basic variable is used because it always leads to the best adjacent BF solution (largest Z).( False ) (d) The simplex method’s minimum ratio rule fro choosing the leaving basic variable is used because making another choice with a large ratio would yield a basic solution that is not feasible.( True ) (e) If at least one of the basic variables has a coefficient of zero in row 0 of the final tableau, then the problem has multiple optimal solutions. ( False ). 2. A company needs to lease warehouse storage space over the next 5 months. Just how much space will be required in each of these months is known. However, since these space requirements are quite different, it may be most economical to lease only the amount needed each month on a month-by-month basis. On the other hand, the additional cost for leasing space for additional months is much less than for the first month, so it may be less expensive to lease the maximum amount needed for the entire 5 months. Another option is the intermediate approach of changing the total amount of space leased (by adding a new lease and /or having an old lease expire) at least once but not every month. The space requirement (in thousands of square feet) and the leasing costs (in hundreds of dollars) for the various leasing periods are as follows: Month Required space (000 Square feet) Leasing period (Months) Cost per 1,000 square feet leased ($00) 1 30 1 650 2 20 2 1,000 3 40 3 1,350 4 10 4 1,600 5 50 5 1,900 The objective is to minimize the total leasing cost for meeting the space requirements. Please formulate a linear programming model for this problem. (10 points) Solution: we denote xij as the ith month lease j months period warehouse. The linear
model minz=650(x1+x21+x3+x41+x31)+1000x12+x2+x32+x42)+ 1350(x13+x23+x3)+1600x14+x24)+1900x51 x1+x2+x13+x14+x15≥30 +x4+x1+xy1+x2,+x23+xy4≥20 x13+x14+x5+x2+x23+x24+x31+x2+x32 +x1+x23+x24+x32+x232+x14+x24≥10 x15+x24+x3+x24≥50 ≥0 3. A corporation has decided to produce three new products. Five branch plants now have excess product capacity. The unit manufacturing cost of the first product would be $31, $29, $32, $28, and $29, in plants 1, 2, 3, 4, and 5, respectively. The unit manufacturing cost of the second product would be $45, $41, $46, $42, and $43 in Plants 1, 2, 3, 4, and 5, respectively. The unit manufacturing cost of the third product would be $38, $35, and $40 in Plants 1, 2, and 3, respectively, and Plants 4 and 5 do not have the capability for producing this product. Sales forecasts indicate that 600 1000, and 800 units of products 1, 2, and 3, respectively, should be produced per day Plants 1, 2, 3, 4, and 5 have the capacity to produce 400,600, 400, 600, and 1000 units daily, respectively, regardless of the product or combinations of products involved Assume that any plant having the capability and capacity to produce them can produce any combination of the products in any quantity Management wishes to know how to allocate the new products to the plants to minimize the total manufacturing cost Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) Solution: the transportation tableau is Nant Plant1 Plant 2 Plant 3 Plant 4 Plant 5Demand production Production 245 41 46 42 43 1000 Production 3 38 800 400 600 400 600 1000 4. Use the simplex method to solve the following problem(15 points Maximize Z=5x,+3x+4 2 subject to 3x, +x,+2x, <30 ≥0,x2≥0,x2≥0
2 programming model is ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ + + + ≥ + + + + + + + ≥ + + + + + + + + ≥ + + + + + + + ≥ + + + + ≥ + + + + + = + + + + + + + + + 0 50 10 40 20 30 . . 1350( ) 1600( ) 1900 min 650( ) 1000( ) 15 24 33 24 14 15 23 24 32 33 14 24 13 14 15 22 23 24 31 32 33 12 13 14 15 21 22 23 24 11 12 13 14 15 13 23 33 14 24 51 11 21 31 41 51 12 22 32 42 ij x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x st x x x x x x Z x x x x x x x x x 3. A corporation has decided to produce three new products. Five branch plants now have excess product capacity. The unit manufacturing cost of the first product would be $31, $29,$32,$28, and $29, in plants 1,2,3,4, and 5, respectively. The unit manufacturing cost of the second product would be $45, $41,$46,$42, and $43 in Plants 1,2,3,4, and 5, respectively. The unit manufacturing cost of the third product would be $38, $35, and $40 in Plants 1,2, and 3, respectively, and Plants 4 and 5 do not have the capability for producing this product. Sales forecasts indicate that 600, 1000, and 800 units of products 1,2,and 3, respectively, should be produced per day. Plants 1,2,3,4, and 5 have the capacity to produce 400,600,400,600, and 1000 units daily, respectively, regardless of the product or combinations of products involved. Assume that any plant having the capability and capacity to produce them can produce any combination of the products in any quantity. Management wishes to know how to allocate the new products to the plants to minimize the total manufacturing cost. Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) Solution: the transportation tableau is plant unit cost production Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Demand Production 1 31 29 32 28 29 600 Production 2 45 41 46 42 43 1000 Production 3 38 35 40 — — 800 Supply 400 600 400 600 1000 4. Use the simplex method to solve the following problem (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = + + 0, 0, 0 3 2 30 2 20 5 3 4 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x subject to Maximize Z x x x
Solution: Solution: the process of simplex method iteration described as follows Basic variable Co X3 X4 X5 Right side (0) 0 (1)0 2 (0 010010 0 0 236 0 X3 0 -1 OZ 0000 X2 2 0 So, the optimal solution is x1=0, x2=10, x3=10, the optimal value is maxZ=70 5 Consider the following problem(15 points) Maxz= 2x,+7x2+4x x1+2x2+x3≤10 s3x+3x2+2x3≤10 ≥0,x2≥0,x3≥0 (a)Construct the dual problem for this primal problem (b) Use the dual problem to demonstrate that the optimal value of Z for the primal problem cannot exceed 25 (c)It has conjectured that x2 and x4 should be the basic variables for the optimal solution of the primal problem. Directly derive this basic solution(and z) by using Gaussian elimination. Simultaneously derive and identify the complementary basic solution for the dual problem by using Eq (0) for the primal problem Solution:(a) the dual problem W=10y,+10 3y,≥2 3y2≥7 y1+2y2≥4 y1,y2 ≥0 (b)y1=0, y2=5/2, is a feasible solution of the dual problem, and the objective value is W=25. According to dual theorem, Z=CX <Yb=W, so the optimal value of Z for the primal problem cannot exceed 25 (c)By using Gaussian elimination, let x2 and x4 be the basic variables, the simplex tableau Basic variable Coefficient of X3 X4 X5Right side (0) 2/3 70/3 -1/3 The optimal solution is x1=0, x2=10/3, x3=0, maxz=70/3 The complementary basic solution for the dual problem is y1=0, y2=7/3
3 Solution: Solution: the process of simplex method iteration described as follows: Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 -5 -3 -4 0 0 0 X4 (1) 0 2 1 1 1 0 20 X5 (2) 0 3 1 2 0 1 30 Z (0) 1 1 0 -1 3 0 60 X3 (1) 0 2 1 1 1 0 20 X5 (2) 0 1 0 1 -1 1 10 0Z (0) 1 2 0 0 2 1 70 X3 (1) 0 1 1 0 2 -1 10 X2 (2) 0 1 0 1 -1 1 10 So, the optimal solution is x1=0,x2=10,x3=10, the optimal value is maxZ=70 .5 Consider the following problem (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = + + 0, 0, 0 3 3 2 10 2 10 . . 2 7 4 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x st MaxZ x x x (a) Construct the dual problem for this primal problem. (b) Use the dual problem to demonstrate that the optimal value of Z for the primal problem cannot exceed 25. (c) It has conjectured that x2 and x4 should be the basic variables for the optimal solution of the primal problem. Directly derive this basic solution (and Z) by using Gaussian elimination. Simultaneously derive and identify the complementary basic solution for the dual problem by using Eq.(0) for the primal problem. Solution: (a) the dual problem is ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + ≥ + ≥ + ≥ = + , 0 2 4 2 3 7 3 2 . . min 10 10 1 2 1 2 1 2 1 2 1 2 y y y y y y y y st W y y (b) y1=0, y2=5/2, is a feasible solution of the dual problem, and the objective value is W=25. According to dual theorem, Z = CX ≤ Yb = W , so the optimal value of Z for the primal problem cannot exceed 25. (c) By using Gaussian elimination, let x2 and x4 be the basic variables, the simplex tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 5 0 2/3 0 7/3 70/3 X4 (1) 0 -1 0 -1/3 1 -2/3 10/3 X2 (2) 0 1 1 2/3 0 1/3 10/3 The optimal solution is x1=0,x2=10/3,x3=0,maxZ=70/3 The complementary basic solution for the dual problem is y1=0,y2=7/3
6. Consider the following parametric linear programming problem: (20 points) MaxZ= 2x,+4x2+5x3 x1+3x2+2x3≤5+0 s{x1+2x2+3x3≤6+20 0,x2≥0,x3≥0 where 0 can be assigned any positive or negative values. Let x4 and xs be the slack variables for the respective functional constraints. After we apply the simplex method with 0=0, the final simplex tableau is Basic variable Coefficient of Z XI X2 x4 X5 Right side (0) 11 a. Express the BF solution(and Z) given in this tableau as a function of o 2 0 Determine the lower and upper bounds on e before this optimal solution would become infeasible Then determine the best choice of o between these bound b. Given that e is between the bounds found in part(a), determine the allowable range to stay optimal for cl(the coefficient of xl in the objective function) Solution:(a)the BF solution is 86b=/3-2T 5+01[3-01 l116+20|1+0 When ≥0, that is-1≤θ≤3, this optimal is still feasible. The best choice of 1+b (b)if the coefficient of xl in the objective function is cl Basic variable E Coefficient of Right side XI X3 (2)0 1+6 (0)105c1-903c1-55-2c1 3-0 X3 The allowable range for cl is≤C1≤ 7. Consider the following project network. By using the PERT three-estimate approach, suppose that the usual three estimates for the time required(in weeks) for each of these activities are as follows (20 points) ty Optimistic estimate Most likely estimate Pessimistic estimate 28 36
4 6. Consider the following parametric linear programming problem: (20 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + + ≤ + = + + 0, 0, 0 2 3 6 2 3 2 5 . . 2 4 5 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x st MaxZ x x x θ θ where θcan be assigned any positive or negative values. Let x4 and x5 be the slack variables for the respective functional constraints. After we apply the simplex method with θ=0, the final simplex tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 1 0 1 1 11 X1 (1) 0 1 5 0 3 -2 3 X3 (2) 0 0 -1 1 -1 1 1 a. Express the BF solution (and Z) given in this tableau as a function ofθ. Determine the lower and upper bounds onθ before this optimal solution would become infeasible. Then determine the best choice of θ between these bounds. b. Given thatθ is between the bounds found in part(a), determine the allowable range to stay optimal for c1(the coefficient of x1 in the objective function). Solution: (a) the BF solution is ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ + − =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ + + ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − − = − θ θ θ θ 1 3 6 2 5 1 1 3 2 1 B b When 0 1 3 ≥⎥ ⎦ ⎤ ⎢ ⎣ ⎡ + − θ θ , that is −1 ≤ θ ≤ 3 , this optimal is still feasible. The best choice of θ isθ=3. (b) if the coefficient of x1 in the objective function is c1 Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 2-c1 1 0 1 1 11+3θ X1 (1) 0 1 5 0 3 -2 3-θ X3 (2) 0 0 -1 1 -1 1 1+θ Z (0) 1 0 5c1-9 0 3c1-5 5-2c1 X1 (1) 0 1 5 0 3 -2 3-θ X3 (2) 0 0 -1 1 -1 1 1+θ The allowable range for c1 is 2 5 5 9 ≤ C1 ≤ . 7. Consider the following project network. By using the PERT three-estimate approach, suppose that the usual three estimates for the time required (in weeks) for each of these activities are as follows:(20 points) Activity Optimistic estimate Most likely estimate Pessimistic estimate 1→2 1→3 2→6 28 22 26 32 28 36 36 32 46
3→4 14 16 18 32 32 74 5→6 12 (a)On the basis of the estimates just listed, calculate the expected value and standard deviation of the time required for each activity (b) Using expected times, determine the critical path for the project Solution:(a) the expected value and standard deviation are listed in the following table Activit OptimisticMost Pessimisti Expected Variance Standard y estimate likely c estimate value deviation estimate 36 3.33 0.444 0.67 32 32 3→6 74 53.67 32.11 5.67 4→5 24 1667 5→6 6 20.33 7.11 2.67 17.67 (b) 8 1000 The critical path for the project is 1-3-6-7, the expected finish time for the whole project is 100 weeks
5 3→4 3→5 3→6 4→5 5→6 5→7 6→7 14 32 40 12 16 26 12 16 32 52 16 20 34 16 18 32 74 24 26 42 30 (a) On the basis of the estimates just listed, calculate the expected value and standard deviation of the time required for each activity. (b) Using expected times, determine the critical path for the project. Solution: (a) the expected value and standard deviation are listed in the following table Activit y Optimistic estimate Most likely estimate Pessimisti c estimate Expected value Variance Standard deviation 1→2 1→3 2→6 3→4 3→5 3→6 4→5 5→6 5→7 6→7 28 22 26 14 32 40 12 16 26 12 32 28 36 16 32 52 16 20 34 16 36 32 46 18 32 74 24 26 42 30 32 27.67 36 16 32 53.67 16.67 20.33 34 17.67 1.77 2.77 11.11 0.444 0 32.11 4 2.77 7.11 9 1.33 1.67 3.33 0.67 0 5.67 2 1.67 2.67 3 (b) The critical path for the project is 1→3→6→7, the expected finish time for the whole project is 100 weeks. 1 2 3 4 5 6 7 32 28 36 16 32 54 17 20 34 18 32 46 14 82 82 0 100 100 0 61 62 1 44 45 28 1 28 0 0 0 0