江西财经大学 05-06学年第二学期期末考试试卷(参考答案 试卷代码:03883B卷 课时:64 课程名称:运筹学I(英) 适用对象:04管理科学专业 1. Fill in the blanks (10 points) (a)In transportation problem, there are three methods to construct an initial BF solution, they are ① 2 Vogel's approximation method. 3 Russell's approximation method. (b) The four assumptions of linear programming are Proportionality assumption ② Additivity assumption ③ Divisible assumption ④ Certainty assumption (c)Write the following special linear programming model minZ=>C. (The general model of transportation problem is ≥0 minz= @The general model of assignee problem is x, is binary
1 江西财经大学 05-06 学年第二学期期末考试试卷（参考答案） 试卷代码：03883B 卷 课时：64 课程名称：运筹学 I（英） 适用对象：04 管理科学专业 1.Fill in the blanks. (10 points) (a) In transportation problem, there are three methods to construct an initial BF solution, they are ① Northwest corner rule ; ② Vogel’s approximation method. ③ Russell’s approximation method. (b) The four assumptions of linear programming are: ① Proportionality assumption; ②Additivity assumption; ③ Divisible assumption; ④ Certainty assumption。 (c)Write the following special linear programming model: ①The general model of transportation problem is ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = = = ∑ ∑ ∑ ∑ = = = = 0 . . min 1 1 1 1 ij i n j ij j m i ij m i n j ij ij x x a x b st Z C x ②The general model of assignee problem is ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ = = = ∑ ∑ ∑ ∑ = = = = x is binary x x st Z C x ij n j ij n i ij n i n j ij ij 1 1 . . min 1 1 1 1
minz= ∑∑ F aThe general model of min-cost flow problem is s1 2x -2x,=10, i*s, 2 -Fi=t 0≤x.≤W the start point, t is the end point, wii_is capacity, ci_is unit cost 2. An investor has money-making activities A and B available at the beginning of each of the next 5 years(call them years 1 to 5). Each dollar invested in a at the beginning of a year returns $1.40(a profit of $0. 40) two years later(in time for immediate reinvestment ). Each dollar invested in b at the beginning of a year returns $1.70 three years later In addition, money-making activities C and d will each be available at one time in the future. Each dollar invested in C at the beginning of year 2 returns $1.90 at the end of year 5. Each dollar invested in D at the beginning of year 5 returns 1.30 at the nd of year 5 The investor begins with $60000 and wishes to know which investment plan maximizes the amount of money that can be accumulated by the beginning of year 6 Formulate a linear programming model for this problem. (10 points) Solution: We set Ai, Bi, Ci, Di, Ri is the investor in ith year. The linear programming axZ=19C,+1.7B,+1.4A,+1.3D A1+B1+R=60000 A2+B2+C2+R2=R1 R3=14A1+R2 A2+R4=14A2+1.7B1+R3 D5=1.4A3+1.7B2+R4 B,C1,D,R1≥0 3. The BUILD-FAST COMPANY has agreed to supply is best customer with three widgets during each of the next 3 weeks, even though producing them will require some overtime work. The relevant production data are as follows week Maximum production, Maximum production, Production cost per Regular time it, Regular time(s) 400 The cost per unit produced with overtime for each week is $100 more than that for regular time. The cost of storage is $50 per unit for each week. There is already an nventory of two widgets on hand currently, but the company does not want to retain
2 ③The general model of min-cost flow problem is ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ≤ ⎪ ⎩ ⎪ ⎨ ⎧ − = ≠ = − = = ∑ ∑ ∑ ∑ = = ij ij ij ji m i n j ij ij x W F i t i s t F i s x x st Z C x 0 , 0, , , . . min 1 1 , s is the start point, t is the end point, wij is capacity, cij is unit cost. 2. An investor has money-making activities A and B available at the beginning of each of the next 5 years (call them years 1 to 5). Each dollar invested in A at the beginning of a year returns $1.40 (a profit of $0.40) two years later (in time for immediate reinvestment). Each dollar invested in B at the beginning of a year returns $1.70 three years later. In addition, money-making activities C and D will each be available at one time in the future. Each dollar invested in C at the beginning of year 2 returns $1.90 at the end of year 5. Each dollar invested in D at the beginning of year 5 returns 1.30 at the end of year 5. The investor begins with $60000 and wishes to know which investment plan maximizes the amount of money that can be accumulated by the beginning of year 6. Formulate a linear programming model for this problem. (10 points) Solution: We set Ai, Bi, Ci, Di, Ri is the investor in ith year. The linear programming model is ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = + + + = + + + + = + + + + = + + = = + + + , , , , 0 1.4 1.7 1.4 1.7 1.4 60000 . . max 1.9 1.7 1.4 1.3 5 3 2 4 2 4 2 1 3 2 3 3 1 2 2 2 2 2 1 1 1 1 2 3 4 3 Ai Bi Ci Di Ri D A B R A R A B R A B R A R A B C R R A B R st Z C B A D 3. The BUILD-FAST COMPANY has agreed to supply is best customer with three widgets during each of the next 3 weeks, even though producing them will require some overtime work. The relevant production data are as follows: week Maximum production, Regular time Maximum production, Overtime Production cost per unit, Regular time($) 1 2 3 2 2 1 2 1 2 300 500 400 The cost per unit produced with overtime for each week is $100 more than that for regular time. The cost of storage is $50 per unit for each week. There is already an inventory of two widgets on hand currently, but the company does not want to retain
any widgets in inventory after 3 weeks Management wants to know how many units should be produced in each week order to minimize costs Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) Solution: The transportation tableau is Unit cost Supply 1(RT) 400 I(OT 400 450 500 2(RT) 500 550 2(OT) 600 650 3(RT) 3(OT) 500 Demand 4. Consider the following problem (10 points) Maximize z=6 )x1+x2+2 2x,+2 2 4x,-2 3 subject to x,+2x,+-x,≤1 x1≥0,x2≥0,x3≥0 Let x4, 5, 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 Basic variable E z I X2 3 X4 X5 6 Right side 0 X5 100 Use the fundamental insight to identify the missing numbers in the final simplex tableau Solution the final table is Basic variable Coefficient of Right side 0 X3 (2) 000 4 0
3 any widgets in inventory after 3 weeks. Management wants to know how many units should be produced in each week in order to minimize costs. Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) Solution: The transportation tableau is Unit cost 1 2 3 Supply Storage 0 50 100 2 1(RT) 300 350 400 2 1(OT) 400 450 500 2 2(RT) — 500 550 2 2(OT) — 600 650 1 3(RT) — — 400 1 3(OT) — — 500 2 Demand 3 3 3 4.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 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
5. Consider the following problem(20 points) Maximize Z=2x,+7x2-3x3 3x,+4x3≤30 subject to x,+4x2-x3<10 x≥0,x2≥0,x3≥0 The corresponding final set of equations yielding the optimal solution is (0) +2x。=20 x2+5x3+x4-x5=20 x1+4x2-x3 10 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 b2」[30 b)Change the coefficients of x3 to a13 (c)Introduce a new variable x6 with coefficients a (d)Introduce a new constraint 3x,+2x,+3x3 <25 (e)Change constraint 2 to x,+2x2+2x3 $35 Solution the final simplex tableau is Basic variable E Coefficient of X3 X4 X5 Right side 0 2 XI 1-120 (a)b- b= 30/x0, so the previous optimal solution is not till optimal (b) The new 3 In row a3=CB-A4-C3=(02 So the previous optimal solution is not till optimal
4 5. 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 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 not till optimal
(c)The coefficient of new variable in row O is =C4-C=02(2-=70,50 previous optimal solution till optil (d) Input the optimal solution x1=10, x2=0, x3=0 into the new constraint 3x,+2x,+3x3≤25,3×10+2×0+3×02 the previous optimal solution is not till optimal (e) If change constraint 2 to x, +2x2+2x, <35, the final tableau is changed into Basic variable Coefficient of X2 5 Right side (0) 0 0 So the previous optimal solution is till optimal 6. Solve the following parametric linear programming problem (15 points) Maxz()=(10-46)x1+(4-6)x2+(7+6)x 3x,+x,+2x2≤7 s12x1+x2+3x3≤5 x120,x20,x320 when 0=0, the final simplex tableau is Basic variable E Coefficient of: X4 X5 Right side 0 0 24 (1 0 Solution: when 0 >0, the simplex table is Basic variable Coefficient of XI X3 X5 Right side Z 03-202-202+0 (1)0 1 1 When O<e<1, x1=2, X2=l is the optimal solution When 0>1, the simplex tableau is Basic variable Eq Coefficient of ght side -40 2)0 3 When 1<0<5/4, X4=2, x2=5 is the optimal solution When 0>5/4, the simplex tableau is
5 (c) The coefficient of new variable in row 0 is ( ) ( 3) 7 0 2 1 6 6 0 2 1 6 − − = > ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = − = − σ 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. 6. Solve the following parametric linear programming problem (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = − + − + + 0, 0, 0 2 3 5 3 2 7 . . ( ) (10 4 ) (4 ) (7 ) 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 when θ=0, the final simplex tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 0 3 2 2 24 X1 (1) 0 1 0 -1 1 -1 2 X2 (2) 0 0 1 5 -2 3 1 Solution: when θ>0, the simplex table is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 0 3-2θ 2-2θ 2+θ X1 (1) 0 1 0 -1 1 -1 2 X2 (2) 0 0 1 5 -2 3 1 When 0<θ≤1, x1=2,x2=1 is the optimal solution. Whenθ>1, the simplex tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 2θ-2 0 5-4θ 0 4-θ X4 (1) 0 1 0 -1 1 -1 2 X2 (2) 0 2 1 3 0 1 5 When 1<θ≤5/4, x4=2,x2=5 is the optimal solution. Whenθ>5/4, the simplex tableau is