江西财经大学 0405学年第二学期期末考试试卷(参考答案 试卷代码:03883A卷 课时:64 课程名称:运筹学I(英) 适用对象:03管理科学专业 1. Label each of the following statements about linear programming problems as true or false(10 points) (a) The sum of the number of functional constraints and the number of variables (before augmenting) is the same for both the primal and the dual problems (b)At each iteration, the simplex method simultaneously identifies a CPF solution for the primal problem and a CPF solution for the dual problem such that their objective function values are the same( Tr (c)If the value of the objective functi qual at two different feasible points X and X*, then all points on the line segment connecting X and X** are feasible and z has the same value at all those points( True (d) Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of cPf solutions( False (e)The dual simplex method is al ways used to solve the dual programming. False 2. 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 500 Lathe 350 150 The number of machine hours required for each unit of the respective products is as follows Machine Ty Product 1 Product 2 Product Lathe Grindel 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 So the linear
1 江西财经大学 04-05 学年第二学期期末考试试卷（参考答案） 试卷代码：03883A 卷 课时：64 课程名称：运筹学 I（英） 适用对象：03 管理科学专业 1.Label each of the following statements about linear programming problems as true or false. (10 points) (a) The sum of the number of functional constraints and the number of variables (before augmenting) is the same for both the primal and the dual problems. ( False ). (b) At each iteration, the simplex method simultaneously identifies a CPF solution for the primal problem and a CPF solution for the dual problem such that their objective function values are the same. ( True ) (c) If the value of the objective function is equal at two different feasible points X* and X**, then all points on the line segment connecting X* and X** are feasible and Z has the same value at all those points. ( True ). (d) Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of CPF solutions. ( False ). (e) The dual simplex method is always used to solve the dual programming.( False ) 2. 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
mming model maxz=50x1+20x2+25x3 9x1+3x2+5x3≤50 5x1+4x2+0x3≤350 s3x1+0x,+2x2≤150 20 3.A manufacturer must produce two products in sufficient quantity to meet contracted sales in each of the next 3 months. The two products share the same production facilities, and each unit of both products requires the same amount of production capacity. The available production and storage facilities are changing month by month, so the production capacities, unit production costs, and unit storage costs vary by month. Therefore, it may be worthwhile to overproduce one or both products in some months and to store them until needed For each month, the second column of the following table gives the maximum number of units of the two products combined that can be produced on regular time (RT and on overtime (OT). For each product, the subsequent columns give(1) the number of units needed for the contracted sales, 2)the cost per unit produced on regular time, (3) the cost per unit produced on overtime, and(4)the cost of storing each extra unit that is held over into the next month In each case. the numbers for the two products are separated by a slash, with the number for Productl on the left and the number for product 2 on the right Maximum Combined production Product 1/ Product 2 Unit Cost of Production Unit cost Month RT OT Sales RT OT of Storage 10 5/315/16 18/20 1/2 2 3/5 17/15 20/18 2/1 19/1722/22 The production manager wants a schedule developed for the number of units of each product to be produced on regular time and (if regular time production capacity is used up)on overtime in each of the three months. The objective is to minimize the total of the production and storage costs while meeting the contracted sales for each month. There is no initial inventory, and no final inventory is desired after 3 months Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points Solution: the transportation tableau is Product l(unit cost) Product 2(unit cost) Supply IRT 16 18 6 I OT 19 2 RT 15 16
2 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 3.A manufacturer must produce two products in sufficient quantity to meet contracted sales in each of the next 3 months. The two products share the same production facilities, and each unit of both products requires the same amount of production capacity. The available production and storage facilities are changing month by month, so the production capacities, unit production costs, and unit storage costs vary by month. Therefore, it may be worthwhile to overproduce one or both products in some months and to store them until needed. For each month, the second column of the following table gives the maximum number of units of the two products combined that can be produced on regular time (RT) and on overtime (OT). For each product, the subsequent columns give (1) the number of units needed for the contracted sales, 2) the cost per unit produced on regular time, (3) the cost per unit produced on overtime, and (4) the cost of storing each extra unit that is held over into the next month. In each case, the numbers for the two products are separated by a slash, with the number for Product1 on the left and the number for Product 2 on the right. Maximum Combined Production Product 1/ Product 2 Unit Cost of Production Month RT OT Sales RT OT Unit cost of storage 1 2 3 10 8 10 3 2 3 5/3 3/5 4/4 15/16 17/15 19/17 18/20 20/18 22/22 1/2 2/1 The production manager wants a schedule developed for the number of units of each product to be produced on regular time and (if regular time production capacity is used up) on overtime in each of the three months. The objective is to minimize the total of the production and storage costs while meeting the contracted sales for each month. There is no initial inventory, and no final inventory is desired after 3 months. Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) Solution: the transportation tableau is Product 1(unit cost) Product 2 (unit cost) Supply 1 RT 15 16 18 16 18 19 10 1 OT 18 19 21 20 22 23 3 2 RT - 17 19 - 15 16 8
2 OT 18 3 RT 3 OT Demand 4. Consider the following problem MinZ=x,+-x +3x2≥3 S1.x,+x ≥0,x2≥0 Use the simplex method to demonstrate that this problem does not posses any feasible solutions. (15 points Solution: use the two-phase method Phase 1: To solve artificial-variable problem Mimy=y,+y2 x3+y1 1x1+x2-x4+y x1≥0,x2≥0 the final tableau is Basic variable E Coefficient of X4 Y1 Y2 Right side W 0) 0 0 X2 00 11/21/21/2-1/2 XI 0 3/2 l/23/2 Delete the artificial-variable column Y1, Y2, and change the objective row, go to Basic variable Coefficient of z XI X2 X3 X4 Y1 Y2Right side 0) 0 1/4-3/4 (2)0 01/2-3/2 3/2 This tableau is an optimal tableau. So, the optimal solution is x1=3/2, x2=1/2 minz=9 /4 onsager the following problem. (10 points) Maximize Z=x,-x2+2x3 x1+x2+3x3≤15 ibject to x2+x3 x1+x2+x3≤4 x1≥0,x2≥0,x3≥0 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
3 2 OT - 20 22 - 18 19 2 3 RT - - 19 - - 17 10 3 OT - - 22 - - 22 3 Demand 5 3 4 3 5 4 4. Consider the following problem ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ + ≥ + ≥ = + 0, 0 2 3 3 . . 2 3 1 2 1 2 1 2 1 2 x x x x x x st MinZ x x Use the simplex method to demonstrate that this problem does not posses any feasible solutions. (15 points) Solution: use the two-phase method Phase 1: To solve artificial-variable problem ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ + − + = + − + = = + 0, 0 2 3 3 . . 1 2 1 2 4 2 1 2 3 1 1 2 x x x x x y x x x y st Minw y y the final tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 Y1 Y2 Right side W (0) 1 0 0 0 0 -1 -1 0 X2 (1) 0 0 1 -1/2 1/2 1/2 -1/2 1/2 X1 (2) 0 1 0 1/2 -3/2 -1/2 3/2 3/2 Delete the artificial-variable column Y1,Y2, and change the objective row, go to phase 2: Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 Y1 Y2 Right side Z (0) 1 0 0 -1/4 -3/4 9/4 X2 (1) 0 0 1 -1/2 1/2 1/2 X1 (2) 0 1 0 1/2 -3/2 3/2 This tableau is an optimal tableau. So, the optimal solution is x1=3/2, x2=1/2, minZ=9/4. 5.Consider the following problem. (10 points) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ − + + ≤ − + ≤ + + ≤ = − + 0, 0, 0 4 2 2 3 15 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:
Basic variable Coefficient of X1 X2 X3 X4 X5 Right side 03/21/2 X3 0 01/21/2 0-1/21/2 Use the fundamental insight to identify the missing numbers in the final simplex table Solution the final tableau is Basic variable E nt of XI 2 X3 4 X5 X6Right side 3/2 1)0 6. Consider the following problem(20 points) Maximize z=3x, +x+4 6x,+3x+5X,≤25 subject to 33x, +4x, +5x,<20 x1≥0,x2≥0,x3≥0 The corresponding final set of equations yielding the optimal solution is +-x,+-X=17 x +-x 35 x2 (a)Identify the optimal solution from this set of equations (b) Construct the dual problem (c)Identify the optimal solution for the dual problem from the final set of equations (d)If coefficient of x2 is changed to a,2=2. Determine whether the previous optimal solution is till optimal (e) If a new variable Xnew has been introduced into the model, Xnew coefficient is C6 3. Determine whether the previous optimal solution is till optimal Solution the final tableau is
4 Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 X6 Right side Z (0) 1 0 3/2 1/2 X4 (1) 0 1 -1 -2 X3 (2) 0 0 1/2 1/2 X2 (3) 0 0 -1/2 1/2 Use the fundamental insight to identify the missing numbers in the final simplex tableau. Solution: the final tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 X6 Right side Z (0) 1 3/2 0 0 5 X2 (1) 0 1 0 0 5 X6 (2) 0 1/2 0 1 3 X3 (3) 0 -3/2 1 0 1 6. Consider the following problem (20 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = + + 0, 0, 0 3 4 5 20 6 3 5 25 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 The corresponding final set of equations yielding the optimal solution is 3 5 2 5 1 (2) 3 5 3 1 3 1 3 1 (1) 17 5 3 5 1 (0) 2 2 3 4 5 1 2 4 5 2 4 5 + − + = − + − = + + + = x x x x x x x x Z x x x (a) Identify the optimal solution from this set of equations. (b) Construct the dual problem (c) Identify the optimal solution for the dual problem from the final set of equations. (d) If coefficient of x2 is changed to ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 3 2 3 22 12 2 a a c . Determine whether the previous optimal solution is till optimal. (e) If a new variable Xnew has been introduced into the model, Xnew coefficient is ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 3 2 26 16 6 a a c . Determine whether the previous optimal solution is till optimal. Solution: the final tableau is
Basic variable Coefficient of Z XI X2 X3 X4 X5 Right side 1/5 -1/3 1/5 2/5 (a) The optimal solution is x1=5/3, x2=0, X3=3, maxZ=17 minS=25y,+ 20y2 y1+3y2 (b)The dual problem 13y1+4y2≥1 5y1+5y2≥4 0 (c)The optimal solution for the dual problem from the final set of equations is yl=1/5y2=3/5,minS=17 (d) The coefficient of x2 in row O is 0,=CBB-A,? 0 55人3 so the previous optimal solution is not till optimal (e) The coefficient of new variable Xnew is 06=CBBA6-C6=231-2=>0, so the previous optimal solution is till 552 7. Solve the parameter programming as follow:(15 points Maxz=2x,+x2 ≤10+26 x1+x2 x2≤10+26 x1≥0, Solution: when 0=0, the optimal tableau is Basic variable Coefficient of X4 X5 Right side 0) 0 0 30 )0 0 0 10 2 0 When the right-side is b= 25-0 the final tableau is 10+26
5 Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 2 0 1/5 3/5 17 X1 (1) 0 1 -1/3 0 1/3 -1/3 5/3 X3 (2) 0 0 1 1 -1/5 2/5 3 (a) The optimal solution is x1=5/3, x2=0, x3=3, maxZ=17 (b) The dual problem is ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + ≥ + ≥ + ≥ = + , 0 5 5 4 3 4 1 6 3 3 . . min 25 20 1 2 1 2 1 2 1 2 1 2 y y y y y y y y st S y y (c) The optimal solution for the dual problem from the final set of equations is y1=1/5,y2=3/5,minS=17 (d) The coefficient of x2 in row 0 is 0 5 4 3 3 2 5 3 5 1 2 2 1 2 − = − ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = − = − σ CB B A C , so the previous optimal solution is till optimal. 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
Basic variable Coefficient of X5 Right side 0 10+20 X4 1000 0 0010 5-50 0 10+20 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 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 et discounted cost associated with purchasing a tractor (purchase price minus trade-in allowance, plus running and maintenance costso at the end of year I and trading it in at the end of year j ( where year 0 is now) 0 31 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 path0→1→3, the total um cost is 29
6 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 (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
10
7 0 1 2 3 8 18 31 10 21 12 8 18 29