江西财经大学 05-06学年第二学期期末考试试卷(参考答案 试卷代码:03883A卷 课时 课程名称:运筹学I(英) 适用对象:04管理科学专业 1. Fill in the blanks (10 points) (a)the four assumptions of linear programming are O Proportionality assumption: ② Addit ③ Divisible ④ Certainty assumption (b)the difference between simplex method and dual simplex method are the simplex method first to determine the entering basic variable, but dual simplex method first to determine leaving basic variable 2the criterion of the simplex method determine optimal is CrB-A-c20,but the criterion of the simplex method determine optimal is B-b>0 3 In simplex method minimum ratio test is to pick out each coefficient in the pivot column that is strictly positive divide each of these coefficients into the right side entry for the same row; but in dual simplex method minimum ratio test is to pick out each coefficient in the pivot row that is strictly negative divide each of these coefficients into row(0) entry for the same row. (c) the duality theorem stated that the only possible relationship between the primal and the dual problems are Oif one problem has feasible solution and a bounded obiective function, then so do the other problem, so both the weak and strong duality properties are applicable. 2 if one problem has feasible solutions and an unbounded obiective function,then the other problem has no feasible solutions. 3 if one problem has no feasible solutions, then the other problem has either no feasible solutions or an unbounded obiective function. 2. We want to select an advertising strategy to reach two types of customers homemakers in families with over $25000 annual income and homemakers in families with under $25,000 income. We feel that people in the first group will purchase twice as much of our product as people in the second, and our goal is to maximize purchases. We may advertise either on TV or in a magazine; one unit of TV advertising costs $40,000 and reaches approximately 20,000 people in the first group and 80,000 in the second. One unit of advertising in the magazine costs $24,000 and
1 江西财经大学 05-06 学年第二学期期末考试试卷（参考答案） 试卷代码：03883A 卷 课时：64 课程名称：运筹学 I（英） 适用对象：04 管理科学专业 1.Fill in the blanks. (10 points) (a) the four assumptions of linear programming are: ① Proportionality assumption; ②Additivity assumption; ③ Divisible assumption; ④ Certainty assumption。 (b) the difference between simplex method and dual simplex method are: ① the simplex method first to determine the entering basic variable, but dual simplex method first to determine leaving basic variable; ②the criterion of the simplex method determine optimal is CB B A − C ≥ o −1 ,but the criterion of the simplex method determine optimal is 0 1 ≥ − B b ③ In simplex method minimum ratio test is to pick out each coefficient in the pivot column that is strictly positive divide each of these coefficients into the right side entry for the same row; but in dual simplex method minimum ratio test is to pick out each coefficient in the pivot row that is strictly negative divide each of these coefficients into row (0) entry for the same row. (c) the duality theorem stated that the only possible relationship between the primal and the dual problems are: ①if one problem has feasible solution and a bounded objective function, then so does the other problem, so both the weak and strong duality properties are applicable. ② if one problem has feasible solutions and an unbounded objective function, then the other problem has no feasible solutions. ③ if one problem has no feasible solutions, then the other problem has either no feasible solutions or an unbounded objective function. 2.We want to select an advertising strategy to reach two types of customers: homemakers in families with over $25,000 annual income and homemakers in families with under $25,000 income. We feel that people in the first group will purchase twice as much of our product as people in the second, and our goal is to maximize purchases. We may advertise either on TV or in a magazine; one unit of TV advertising costs $40,000 and reaches approximately 20,000 people in the first group and 80,000 in the second. One unit of advertising in the magazine costs $24,000 and
reaches 60,000 people in the first group and 30,000 in the second. We require that at least 6 units of Tv advertising be used and that no more than 12 units of magazine advertising be used for policy reasons. The advertising budget is 360,000 Formulate this problem as a linear programming problem, defining all variables used.(10 points) Solution: we set advertise xI TV unit and x2 magazine unit, the linear programming mo maxZ=2(20000x1+60000x2)+(80000x+30000x2) 40000x1+24000x2≤360000 x1≥6 s t x,≤12 x1,x2≥0 3.A manufacturing firm has discontinued the production of a certain unprofitable product line. This act created considerable excess production capacity. Management is considering devoting this excess capacity to one or more of three products; call them products 1, 2, and 3. The available capacity on the machines that might limit output is summarized in the following table Machine Ty Available Time(in Machine Hours per W Milling machine 500 Lathe 350 The number of machine hours required for each unit of the respective products is as Machine type Product 1 Product 2 Product 3 Lathe 953 4 Grinde 2 The sales department indicates that the sales potential for products I and 2 exceeds the maximum production rate and that the sales potential for product 3 is 20 units per week. The unit profit would be $50, $20, and $25, respectively, on products 1, 2 and 3 the objective is to determine how much of each product the firm should produce to maximize profit Formulate a linear programming model for this problem. (10 points) Solution: we set the production of production 1, 2, 3 are x1, X2, X3. So the linear programming model is maxZ=50x1+20x,+25 9x1+3x2+5x3≤500 5x,+4x,+0x2≤350 s3x1+0x,+2x2≤150 x,x
2 reaches 60,000 people in the first group and 30,000 in the second. We require that at least 6 units of TV advertising be used and that no more than 12 units of magazine advertising be used for policy reasons. The advertising budget is 360,000. Formulate this problem as a linear programming problem, defining all variables used. (10 points) Solution: we set advertise x1 TV unit and x2 magazine unit, the linear programming model is ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≤ ≥ + ≤ = + + + , 0 12 6 40000 24000 360000 . . max 2(20000 60000 ) (80000 30000 ) 1 2 2 1 1 2 1 2 1 2 x x x x x x st Z x x x x 3.A manufacturing firm has discontinued the production of a certain unprofitable product line. This act created considerable excess production capacity. Management is considering devoting this excess capacity to one or more of three products; call them products 1,2, and 3. The available capacity on the machines that might limit output is summarized in the following table: Machine Type Available Time (in Machine Hours per Week) Milling machine Lathe Grinder 500 350 150 The number of machine hours required for each unit of the respective products is as follows: Machine Type Product 1 Product 2 Product 3 Milling machine Lathe Grinder 9 5 3 3 4 0 5 0 2 The sales department indicates that the sales potential for products 1 and 2 exceeds the maximum production rate and that the sales potential for product 3 is 20 units per week. The unit profit would be $50, $20, and $25, respectively, on products 1,2 and 3. the objective is to determine how much of each product the firm should produce to maximize profit. Formulate a linear programming model for this problem. (10 points) Solution: we set the production of production 1, 2, 3 are x1, x2, x3. So the linear programming model is ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≤ + + ≤ + + ≤ + + ≤ = + + , , 0 20 3 0 2 150 5 4 0 350 9 3 5 500 . . max 50 20 25 1 2 3 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 x st Z x x x
4. For a linear programming max:=5x,+2r+3 ≤b1 5x2-6x3≤b2 x1,x2,x3≥0 In this model, b1, b 2 are unknown parameters, and the final simplex table is Basic variable E Coefficient of: Right side (2)0 Please determine the parameters in b1, b2 LP model and a, b, c, d, e in final simplex table.(15 Solution: because B-b-1 ob 1110/sb=30,b2=4 105 e=0d=5,B-A2 sob=5,c=10,a=23 5. Consider the transportation problem having the following cost and requirements Destination supply 6 Source 2 2 4 Demand Determine the optimal solution (15 points) Solution: the optimal transportation plan is described in following table: the red words in square blanks are the optimal shipment. The minimum shipping cost is 32 Destination 6 Source 3(2) 3(3) 6. For a linear programming model (15 points)
3 4. For a linear programming In this model, b1,b2 are unknown parameters，and the final simplex table is： Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 a 7 d e 150 X1 (1) 0 1 b 2 1 0 30 X5 (2) 0 0 c -8 -1 1 10 Please determine the parameters in b1,b2 LP model and a, b, c, d, e in final simplex table。（15 points） Solution: because ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − = − 10 30 1 1 1 0 2 1 1 b b B b , so b1=30, b2=40 e=0,d=5, ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − = − c b B A 5 5 1 1 1 0 2 1 , so b=5,c=-10,a=23 5. Consider the transportation problem having the following cost and requirements table: Destination 1 2 3 4 Supply 1 3 7 6 4 5 Source 2 2 4 3 2 2 3 4 3 8 5 3 Demand 3 3 2 2 Determine the optimal solution. (15 points) Solution: the optimal transportation plan is described in following table: the red words in square blanks are the optimal shipment. The minimum shipping cost is 32. Destination 1 2 3 4 Supply 1 3(3) 7 6 4(2) 5 Source 2 2 4 3(2) 2 2 3 4 3(3) 8 5 3 Demand 3 3 2 2 6. For a linear programming model (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ − − ≤ + + ≤ = + + 0 5 6 5 2 5 2 3 1 2 3 1 2 3 2 1 2 3 1 1 2 3 x x x x x x b x x x b x x x , , s.t. max z
max:=3x+2x,+5 x2+x3≤430 °n+2 x1+4x2≤420 x1,x2,x3≥0 Let x4, Xs, and x6 denote the slack variables for the respective constraints. The final simplex tableau is as folle Basic variable Eq Coefficient of Right side X3 (2)03/20 0 1/2 0001 230 2 (a) Identify the optimal solution from this table (b)Identify the optimal solution for the dual problem (c) Introduce a new constraint x,+2x,+3x, 480, so the previous optimal solution is not till optimal (d)If we want the previous optimal solution to be al ways optimal, then 2-1/40Tb B-b=01/20460≥0,230≤b1≤440, bi can increase 10 units 21 420 (e) If a new variable Xnew has been introduced into the model =CB4+-C,=0202|-9=-2 <0, so the previous optimal solution is ot till optimal
4 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + ≤ + ≤ + + ≤ = + + 0 4 420 3 2 460 2 430 3 2 5 1 2 3 1 2 1 3 1 2 3 1 2 3 x x x x x x x x x x x x x , , s.t max z Let x4,x5, and x6 denote the slack variables for the respective constraints. The final simplex tableau is as follows: Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 X6 Right side Z (0) 1 4 0 0 1 2 0 X2 (1) 0 -1/4 1 0 1/2 -1/4 0 100 X3 (2) 0 3/2 0 1 0 1/2 0 230 X6 (3) 0 2 0 0 -2 1 1 20 (a) Identify the optimal solution from this table. (b) Identify the optimal solution for the dual problem. (c) Introduce a new constraint 480 x1 + 2x2 + 3x3 ≤ , Determine whether the previous optimal solution is till optimal. (d) If we want the previous optimal solution to be always optimal, how much does the right-side of constraint 1 b1 increase? . (e) If a new variable Xnew has been introduced into the model, Xnew coefficient is ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ 4 2 3 9 37 27 17 7 a a a c . Determine whether the previous optimal solution is till optimal. Solution: (a) The optimal solution is x1=0,x2=100,x3=230, maxZ=1350. (b) The optimal solution for the dual problem is y1=1,y2=2,y3=0,minW=1350 (c) Put the optimal solution x1=0,x2=100,x3=230 into the new constraint x1 + 2x2 + 3x3 ≤ 480 , 0+2×100+3×230=890>480, so the previous optimal solution is not till optimal. (d) If we want the previous optimal solution to be always optimal, then 0 420 460 2 1 1 0 1/ 2 0 1/ 2 1/ 4 0 1 1 ≥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − = − b B b , 230 440 ≤ b1 ≤ , b1 can increase 10 units. (e) If a new variable Xnew has been introduced into the model, ( ) 9 2 0 4 2 3 7 7 1 2 0 1 7 − = − < ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = − = − σ CB B A C , so the previous optimal solution is not till optimal
7. Solve the parameter programming as follow:(15 points) Maxz= 2x, +x 10+26 x1+x2≤25-6 x2≤10+26 x1≥0,x2≥0 Solution: when 0=0, the optimal tableau is Basic variable Eq Coe d2000 Right side 0 X4 (2) 0000 When the right-side is b= 25-0 the final tableau is 10+26 Coefficient of asic varia (3 X4X5Right side 000 0 30+60 (1) 000 0 0 10+20 (2) 5-50 10+26 So, when 25, the problem has no optimal solution 8. At a small but growing airport, the local airline company is purchasing a new tractor for a tractor-trailer train to bring luggage to and from the airplanes. A new mechanized luggage system will be installed in 3 years, so the tractor will not be
5 7.Solve the parameter programming as follow: (15 points) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≤ + + ≤ − ≤ + = + 0, 0 10 2 25 10 2 . . 2 1 2 2 1 2 1 1 2 x x x x x x st Maxz x x θ θ θ Solution: when θ=0, the optimal tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 0 2 0 1 30 X1 (1) 0 1 0 1 0 0 10 X4 (2) 0 0 0 -1 1 -1 5 X2 (3) 0 0 1 0 0 1 10 When the right-side is ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ + − + = θ θ θ 10 2 25 10 2 b ,the final tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 0 2 0 1 30+6θ X1 (1) 0 1 0 1 0 0 10+2θ X4 (2) 0 0 0 -1 1 -1 5-5θ X2 (3) 0 0 1 0 0 1 10+2θ So, when0<θ≤1,the optimal solution is x1=10+2θ,x2=10+2θ,maxZ=30+6θ When1 < θ ≤ 5 , the final tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 0 1 1 0 35+θ X1 (1) 0 1 0 1 0 0 10+2θ X5 (2) 0 0 0 1 -1 1 5θ-5 X2 (3) 0 0 1 -1 1 0 15-3θ When1 < θ ≤ 5 , the final tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 1 0 2 0 50-2θ X1 (1) 0 1 1 0 1 0 25-θ X5 (2) 0 0 1 0 0 1 2θ+10 X3 (3) 0 0 -1 1 -1 0 3θ-15 Whenθ ≥ 25 , the problem has no optimal solution. 8. At a small but growing airport, the local airline company is purchasing a new tractor for a tractor-trailer train to bring luggage to and from the airplanes. A new mechanized luggage system will be installed in 3 years, so the tractor will not be
needed after that. However, because it will receive heavy use, so that the running and maintenance costs will increase rapidly as the tractor ages, it may still be more economical to replace the tractor after 1 or 2 years. The following table gives the total net discounted cost associated with purchasing a tractor (pure trade-in allowance, plus running and maintenance costso at the trading it in at the end of year j(where year 0 is now) 0 10 21 The problem is to determine at what times(if any) the tractor should be replaced to minimize the total cost for the tractors over 3 years. (10 points) Solution: Applying the shortest algorithm, we get the following graph, and the shortest path 0-1-3, the total minimum cost is 29 8
6 needed after that. However, because it will receive heavy use, so that the running and maintenance costs will increase rapidly as the tractor ages, it may still be more economical to replace the tractor after 1 or 2 years. The following table gives the total net discounted cost associated with purchasing a tractor (purchase price minus trade-in allowance, plus running and maintenance costs0 at the end of year I and trading it in at the end of year j (where year 0 is now). j 1 2 3 0 8 18 31 i 1 10 21 2 12 The problem is to determine at what times (if any) the tractor should be replaced to minimize the total cost for the tractors over 3 years. (10 points) Solution: Applying the shortest algorithm, we get the following graph, and the shortest path 0→1→3, the total minimum cost is 29. 0 1 2 3 8 18 31 10 21 12 8 18 29
