江西财经大学 03-04学年第二学期期末考试试卷(参考答案) 试卷代码:03883B卷 课时:64 课程名称:运筹学Ⅰ(英) 适用对象:02管理科学专业 1. Label each of the following statements about linear programming problems as true or false (10 points) (a) The simplex method's minimum ratio rule for choosing the leaving basic variable is used because making another choice with a large ratio would yield a basic solution that is not feasible (b)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 (c) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist.( True (d) If the problem has n variables(before augmenting), then the simultaneous solution of any set of n constraint boundary equations is a CPF solution( Fal (e) If the primal problem has an unbounded objective function, then the optimal value of the objective function for the dual problem must be zero. False 2. A certain corporation has three branch plants with excess production capacity. Fortunately, the corporation has a new product ready to begin production, and all three plants have this capability, so some of the excess capacity can be used in this way. This product can be made in three size--large, medium, and small ---that yield a net unit profit of $420, $360, and $300, The amount of available -prc limitation on the production rates of the new product. Plants 1, 2 and 3 have 13,000, 12,000, and 5,000 square feet, respectively, of in-process storage space available for a day's production of this product Each unit of the large, medium, and small sizes produced per day requires 20, 15, and 12 square feet, respectively Sales forecasts indicate that if available, 900, 1, 200, and 750 units of the large, medium and small sizes, respectively, would be sold per day At each plant, some employees will need to be laid off unless most of the plant's excess production capacity can be used to produce the new product. To avoid layoffs if possible, management has decided that the plants should use the same percentage of their excess apacity to produce the new product Management wishes to know how much of each size should be produced by each plant to maximize profit. Formulate a linear programming model for this problem. (10 points) Solution: We set produced large, medium, and small size xli, Xzi, X3i in plant i respectively The linear programming model is
1 江西财经大学 03-04 学年第二学期期末考试试卷（参考答案） 试卷代码：03883B 卷 课时：64 课程名称：运筹学 I（英） 适用对象：02 管理科学专业 1.Label each of the following statements about linear programming problems as true or false. (10 points) (a) The simplex method’s minimum ratio rule for 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 ) (b) 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 ) (c) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. ( True ) (d) If the problem has n variables (before augmenting), then the simultaneous solution of any set of n constraint boundary equations is a CPF solution. ( False ) (e) If the primal problem has an unbounded objective function, then the optimal value of the objective function for the dual problem must be zero.( False ) 2. A certain corporation has three branch plants with excess production capacity. Fortunately, the corporation has a new product ready to begin production, and all three plants have this capability, so some of the excess capacity can be used in this way. This product can be made in three size—large, medium, and small ---that yield a net unit profit of $420, $360, and $300, respectively. Plants 1,2, and 3 have the excess capacity to produce 750,900, and 450 units per day of this product, respectively, regardless of the size or combination of sizes involved. The amount of available in-process storage space also imposes a limitation on the production rates of the new product. Plants 1, 2 and 3 have 13,000, 12,000, and 5,000 square feet, respectively, of in-process storage space available for a day’s production of this product. Each unit of the large, medium, and small sizes produced per day requires 20, 15, and 12 square feet, respectively. Sales forecasts indicate that if available, 900,1,200, and 750 units of the large, medium, and small sizes, respectively, would be sold per day. At each plant, some employees will need to be laid off unless most of the plant’s excess production capacity can be used to produce the new product. To avoid layoffs if possible, management has decided that the plants should use the same percentage of their excess capacity to produce the new product. Management wishes to know how much of each size should be produced by each plant to maximize profit. Formulate a linear programming model for this problem. (10 points) Solution: We set produced large, medium, and small size x1i, x2i, x3i in plant i respectively. The linear programming model is
maxz=420(x1+x12+x13)+360x21+x2+x23)+300x31+x2+x3) 20x1+15x1,+12x12≤1300 20x2+15x2+12x2≤1200 20x12+15x+12x2≤5000 x1+x21+x31≤750 x2+x2+x2≤900 st x1+x12+x13≤900 +x22+x23≤1200 x+x2+x3≤750 33 900 450 0 3. The research and development division of a certain company has developed three new products. The problem is to decide which mix of these products should be produced Management wants primary consideration given to three factors: long-run profit, stability in the workforce, and an increase in the company's earning next year. In particular, using the units given in the following table, they want to Maximize Z=2P-5C-3D Where P=total(discounted profit over life of new products C=change(in either direction) in current level of employment, ease(if any)in next year's earnings from current year's level The amount of any increase in earning does not enter into Z, because man concerned primarily with just achieving some increase to keep the stockholders happy. (It has mixed feelings about a large increase that then would be difficult to surpass in subsequent years.) The impact of each of the new products(per unit rate of production) on each of these factors is shown in the following table Product unit contribution Fact Goal Units Long-run profit 20 25 Maximize (millions of dollars Employment level 6 4 (hundreds of employees) Earning next year ≥75 Millions of dollars) Assuming that three are no additional constraints on the production rates not described here use the goal programming technique to formulate a linear programming model for this problem.(10 points) Solution: we set produce production 1, 2, 3 are x1, x2, X3, the goal programming model is
2 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ + + = + + = + + + + ≤ + + ≤ + + ≤ + + ≤ + + ≤ + + ≤ + + ≤ + + ≤ + + ≤ = + + + + + + + + 0 750 900 450 750 1200 900 450 900 750 20 15 12 5000 20 15 12 1200 20 15 12 1300 . . max 420( ) 360( ) 300( ) 11 21 31 12 22 32 13 23 33 31 32 33 21 22 23 11 12 13 13 23 33 12 22 32 11 21 31 13 23 33 12 22 32 11 12 13 11 12 13 21 22 23 31 32 33 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 x x st Z x x x x x x x x x 3. The research and development division of a certain company has developed three new products. The problem is to decide which mix of these products should be produced. Management wants primary consideration given to three factors: long-run profit, stability in the workforce, and an increase in the company’s earning next year. In particular, using the units given in the following table, they want to Maximize Z=2P-5C-3D Where P=total (discounted) profit over life of new products. C=change (in either direction) in current level of employment, D=decrease (if any) in next year’s earnings from current year’s level. The amount of any increase in earning does not enter into Z, because management is concerned primarily with just achieving some increase to keep the stockholders happy. (It has mixed feelings about a large increase that then would be difficult to surpass in subsequent years.) The impact of each of the new products (per unit rate of production) on each of these factors is shown in the following table: Product unit contribution Factor 1 2 3 Goal Units Long-run profit 20 15 25 Maximize （millions of dollars） Employment level 6 4 11 =50 (hundreds of employees) Earning next year 8 7 5 ≥75 (Millions of dollars) Assuming that three are no additional constraints on the production rates not described here, use the goal programming technique to formulate a linear programming model for this problem. (10 points) Solution: we set produce production 1, 2, 3 are x1, x2, x3, the goal programming model is
maxZ=2d1-5(d2+d2)-3d2 20x1+15x2+25x3+d1-d1+=0 s16x+4x2+11x3+d2-d2=5 8x1+7x2+5x3+d3-d3=7 4. Use the simplex method to solve the following problem (15 points) Maximize Z=5x+4x +3x≤90 subject to 2x1+x2≤80 x1+x2≤45 x1≥0,x2≥0 Solution: the process of simplex method iteration described as follows Basic variable E Coefficient of XI X2 X5 Right side 4 0 0 X3 (2) X3 (1) XI (3) Z100010001000 3 90 3/2 5/2 200 5/2 -1/2 1/2 0 40 1/2 0 1/2 5 (0) 0 215 X3 (2) 0 (3) 2 So, the optimal solution is x1=35, 2=10, x3=25, the optimal value is maxZ=215 5. Consider the following problem (10 points) Maximize z=6x,+x+2x x1+2x2+x3 subject to 4x-2x2-2x32≤3 x1≥0,x2≥0,x3≥0 Let x4, x5, and x6 denote the slack variables for the respective constraints. After you apply the
3 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + + + − = + + + − = + + + − = = − + − − + − + − + + + − − 8 7 5 75 6 4 11 50 20 15 25 0 . . max 2 5( ) 3 1 2 3 3 3 1 2 3 2 2 1 2 3 1 1 1 2 2 3 x x x d d x x x d d x x x d d st Z d d d d 4. Use the simplex method to solve the following problem. (15 points) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ + ≤ + ≤ + ≤ = + 0, 0 45 2 80 3 90 5 4 1 2 1 2 1 2 1 2 1 2 x x x x x x x x subject to Maximize Z x x 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 -4 0 0 0 0 X3 (1) 0 1 3 1 0 0 90 X4 (2) 0 2 1 0 1 0 80 X5 (3) 0 1 1 0 0 1 45 Z (0) 1 0 -3/2 0 5/2 0 200 X3 (1) 0 0 5/2 0 -1/2 0 50 X1 (2) 0 1 1/2 1 1/2 0 40 X5 (3) 0 0 1/2 0 -1/2 1 5 Z (0) 1 0 0 0 1 3 215 X3 (1) 0 0 0 1 2 -5 25 X1 (2) 0 1 0 0 1 -1 35 X2 (3) 0 0 1 0 -1 2 10 So, the optimal solution is x1=35,x2=10,x3=25, the optimal value is maxZ=215 5.Consider the following problem (10 points) ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ − − − ≤ + + ≤ = + + 0, 0, 0 1 2 1 2 3 2 3 4 2 2 2 1 2 2 6 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x subject to Maximize Z x x x Let x4,x5, and x6 denote the slack variables for the respective constraints. After you apply the
simplex method, a portion of the final simplex tableau is as follows Coefficient of Basic variable Eq z XI X2X3 rIght side (1) X3 (2) 000 Use the fundamental insight to identify the missing numbers in the final simplex tableau Solution the final table is Coefficient of Basic variable X2 X3 X4 X5 X6 Ight side 000 0 6 X5 0 X3 (2) XI 000 0 0 6. Consider the following problem(20 points) Maximize Z=2x,+7x2-3x3 +3X+4x,≤30 abject to x,+4 10 x1≥0,x2≥0,x3≥0 The corresponding final set of equations yielding the optimal solution is +x,+x +2x=20 20 x,+4x,-x Now you are to conduct sensitivity analysis by independently investigating each of the following changes in the original model. For each change, use the sensitivity analysis procedure to determine whether the previous optimal solution is till optimal b|「20 (a)Change the right-hand sides to b2 (b)Change the coefficients of x, to,=3 2 C6 (c)Introduce a new variable x with coefficients a, I (d) Introduce a new constraint 3x, +2x, +3x, <25
4 simplex method, a portion of the final simplex tableau is as follows: Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 X6 Right side Z (0) 1 2 0 2 X5 (1) 0 1 1 2 X3 (2) 0 -2 0 4 X1 (3) 0 1 0 -1 Use the fundamental insight to identify the missing numbers in the final simplex tableau. Solution: the final table is: Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 X6 Right side Z (0) 1 0 7 0 6 X5 (1) 0 0 4 0 7 X3 (2) 0 0 4 1 0 X1 (3) 0 1 0 0 1 6. Consider the following problem (20 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + − ≤ + + ≤ = + − 0, 0, 0 4 10 3 4 30 2 7 3 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 The corresponding final set of equations yielding the optimal solution is (2) 4 10 (1) 5 20 (0) 2 20 1 2 3 5 2 3 4 5 2 3 5 + − + = − + + − = + + + = x x x x x x x x Z x x x Now you are to conduct sensitivity analysis by independently investigating each of the following changes in the original model. For each change, use the sensitivity analysis procedure to determine whether the previous optimal solution is till optimal. (a) Change the right-hand sides to ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 30 20 2 1 b b (b) Change the coefficients of x3 to ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 3 2 23 13 3 a a c (c) Introduce a new variable x6 with coefficients ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡− = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 1 3 21 11 6 a a c (d) Introduce a new constraint 3x1 + 2x2 + 3x3 ≤ 25
(e)Change constraint 2 to x,+2x2+2x3 0, So the previous optimal solution is till 2 (d) Input the optimal solution xl =10, 2=0, x3=0 into the new constraint 3x1+2x,+3x3≤25,3×10+2×0+3×02 So the previous optimal solution is not till optimal (e) If change constraint 2 to x,+2x,+2x, <35, the final tableau is changed into Coefficient of Basic variable Ight s 0 2 X4 (1) -5 0 35 So the previous optimal solution is till optimal 7. A contractor has to haul gravel to three building sites. She can purchase as much as 18 tons at a gravel pit in the north of the city and 14 tons at one in the south. She needs 10, 5, and 10 tons at sites 1, 2, and 3, respectively. The purchase price per ton at each gravel pit and the hauling cost per ton are given in the table below Hauling cost per ton at site Price per ton North South 12 Now formulate this problem as a transportation problem by constructing the appropriate cost and requirements table and determine the optimal solution (15 points Solution: We construct the transportation table
5 (e) Change constraint 2 to x1 + 2x2 + 2x3 ≤ 35 Solution: the final simplex tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 1 1 0 2 20 X4 (1) 0 0 -1 5 1 -1 20 X1 (2) 0 1 4 -1 0 1 10 (a) 0 30 10 30 20 0 1 1 1 1 ≥⎥ ⎦ ⎤ ⎢ ⎣ ⎡− =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − = − B b , so the previous optimal solution is not till optimal. (b) The new coefficient of x3 in row 0 is ( ) ( 2) 2 0 2 3 3 3 0 2 1 3 − − = − ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = − = − σ CB B A C , So the previous optimal solution is till optimal. (d) Input the optimal solution x1=10,x2=0,x3=0 into the new constraint: 3x1 + 2x2 + 3x3 ≤ 25,3×10 + 2× 0 + 3× 0 ≤ 25 So the previous optimal solution is not till optimal. (e) If change constraint 2 to x1 + 2x2 + 2x3 ≤ 35 , the final tableau is changed into Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 1 5 0 2 20 X4 (1) 0 0 1 2 1 -1 -5 X1 (2) 0 1 2 2 0 1 35 So the previous optimal solution is till optimal. 7. A contractor has to haul gravel to three building sites. She can purchase as much as 18 tons at a gravel pit in the north of the city and 14 tons at one in the south. She needs 10, 5, and 10 tons at sites 1,2, and 3, respectively. The purchase price per ton at each gravel pit and the hauling cost per ton are given in the table below. Hauling cost per ton at site Pit 1 2 3 Price per ton North 3 6 5 10 South 6 3 4 12 Now formulate this problem as a transportation problem by constructing the appropriate cost and requirements table and determine the optimal solution. (15 points) Solution: We construct the transportation table
Hauling and producing cost per ton at site 2 Price per ton 13 16 18 The optimal solution is in the following table Hauling and producing cost per ton at site Pit Price per te North 16(0) 18 South 18(0) 15(5) 16(2) 10 10 The minimum total cost is 357 8. Use the augmenting path algorithm to find the flow pattern giving the maximum flow from the supply node to the demand node given that the arc capacity from node i to node is the number nearest node i along the arc between these nodes (10 points) Demand Solution: the optimal solution is described in the following graph 4) Supply 44) Demand 3) 3,1) The maximum flow is F=9
6 Hauling and producing cost per ton at site Pit 1 2 3 Price per ton North 13 16 15 18 South 18 15 16 14 10 5 10 The optimal solution is in the following table: Hauling and producing cost per ton at site Pit 1 2 3 Price per ton North 13(10) 16(0) 15(8) 18 South 18(0) 15(5) 16(2) 14 10 5 10 The minimum total cost is 357. 8. Use the augmenting path algorithm to find the flow pattern giving the maximum flow from the supply node to the demand node given that the arc capacity from node i to node j is the number nearest node i along the arc between these nodes. (10 points) Solution: the optimal solution is described in the following graph The maximum flow is F=9 4 4 1 1 3 3 4 9 4 6 1 2 3 4 5 6 7 Supply Demand (4,4) (4,4) (1,1) 1 (3,1) (3,3) (4,2) (9,5) (4,4) (6,4) 1 2 3 4 5 6 7 Supply Demand
