江西财经大学 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, 0, the simplex table is Basic variable Coefficient of XI X3 X5 Right side Z 03-202-202+0 (1)0 1 1 When O1, the simplex tableau is Basic variable Eq Coefficient of ght side -40 2)0 3 When 15/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 01, 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 15/4, the simplex tableau is
Basic variable Coefficient of XI Right side Z 0)1 (4 16/3-5)/3 /3 11/3 2)02/31/3 0 5/3 5/4, the optimal solution is xI=0, X2=0. X3=5/3 7. The BETTER PRODUCTS COMPANY has decided to initiate the production of four new products, using three plants that currently have excess production capacity The products require a comparable production effort per unit, so the available production capacity of the plants is measured by the number of units of any product that can be produced per day, as given in the following table. The bottom row gives the required production rate per day to meet projected sales. Each plant can produce any of these products, except that plant 2 cannot produce product 3. However, the variable costs per unit of each product differ from plant to plant Management now needs to make a decision on how to split up the production of the products among plants(1 Unit cost for product ty available Plant1 Plant 2 nt 3 Production rate20 Solution: First construct the supply-demand equilibrium table Unit cost for product apacity available 45(D) 75 Plant 2 40 75 Plant 3 37 27 2 000 45 Production rate 20 40 75 Second, solving this problem and get the optimal solution Unit cost for product Capacity available 2 4 5(D) PlantI 4127(3028(30240(15) 75 Plant 2 3(15)0 Plant 3 37(20)302721(25)0 45 Production rate2030 40 The red word in blanks are the optimal shipment, the minimum cost is Z=3260 8. Consider a project whose activities and required times are as given: (10 points Activity Required Time minutes) ,2) (2,3) 5555
6 Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 (14θ -16)/3 (4θ -5)/3 0 0 (7+ θ)/3 X4 (1) 0 5/3 1/3 0 1 -2/3 11/3 X3 (2) 0 2/3 1/3 1 0 1/3 5/3 Whenθ>5/4, the optimal solution is x1=0,x2=0,x3=5/3 7. The BETTER PRODUCTS COMPANY has decided to initiate the production of four new products, using three plants that currently have excess production capacity. The products require a comparable production effort per unit, so the available production capacity of the plants is measured by the number of units of any product that can be produced per day, as given in the following table. The bottom row gives the required production rate per day to meet projected sales. Each plant can produce any of these products, except that plant 2 cannot produce product 3. However, the variable costs per unit of each product differ from plant to plant. Management now needs to make a decision on how to split up the production of the products among plants. (15 points) Unit cost for product 1 2 3 4 Capacity available Plant 1 41 27 28 24 75 Plant 2 40 29 — 23 75 Plant 3 37 30 27 21 45 Production rate 20 30 30 40 Solution: First construct the supply-demand equilibrium table Unit cost for product 1 2 3 4 5(D) Capacity available Plant 1 41 27 28 24 0 75 Plant 2 40 29 — 23 0 75 Plant 3 37 30 27 21 0 45 Production rate 20 30 30 40 75 Second, solving this problem and get the optimal solution Unit cost for product 1 2 3 4 5(D) Capacity available Plant 1 41 27(30) 28(30) 24 0(15) 75 Plant 2 40 29 — 23(15) 0(60) 75 Plant 3 37(20) 30 27 21(25) 0 45 Production rate 20 30 30 40 75 The red word in blanks are the optimal shipment, the minimum cost is Z=3260. 8.Consider a project whose activities and required times are as given: (10 points) Activity Required Time (Minutes) (1,2) (2,3) (3,4) (4,5) 5 5 5 5
(5,9) 5 (26) 6 (78) (8,9) 6 (4,7) a. Construct the project network for this project b. Find the earliest time. latest time and slack for each event as well as the slack for each activity. Also identify the critical path c. If the precedence relationship implied by dummy activity(4, 7)could be removed by how much would the project completion time be reduced? Solution:(a) The project network is 0|0 50 150 201 15 21 )i+5-G 6 (b) The earliest time, latest time, and slack for each event is described in the above graph, the critical path is 1→2→3→4→7→8→9 (c)If the precedence relationship implied by dummy activity (4, 7) could be removed the earliest time, latest time, and slack for each event is changed, they are described in the following graph. We can see, one minutes can be reduced 150 100 15 6 2 13|1
7 (5,9) (2,6) (6,7) (7,8) (8,9) (4,7) 5 6 2 5 6 0 a. Construct the project network for this project. b. Find the earliest time, latest time , and slack for each event as well as the slack for each activity. Also identify the critical path. c. If the precedence relationship implied by dummy activity (4,7) could be removed, by how much would the project completion time be reduced? Solution: (a) The project network is (b) The earliest time, latest time , and slack for each event is described in the above graph, the critical path is 1→2→3→4→7→8→9. (c) If the precedence relationship implied by dummy activity (4,7) could be removed, the earliest time, latest time , and slack for each event is changed, they are described in the following graph. We can see, one minutes can be reduced. 1 2 3 4 5 9 6 7 8 5 5 5 5 5 6 2 0 5 6 0 0 0 5 5 0 10 10 0 15 15 0 20 21 1 26 26 0 20 20 15 0 15 11 0 13 14 1 2 3 4 5 9 6 7 8 5 5 5 5 5 6 2 5 6 0 0 0 5 5 0 10 10 0 15 15 0 20 20 0 25 25 0 18 19 13 1 14 11 1 12 1