江西财经大学 03-04学年第二学期期末考试试卷(参考答案 试卷代码:03883A卷 课时:64 课程名称:运筹学Ⅰ(英) 适用对象:02管理科学专业 1. Label each of the following statements about linear programming problems as true or false (10 points) (a)For minimization problems, if the objective function evaluated at a CPF solution is no large than its value at every adjacent CPF solution, then that solution is optimal ( True (b)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 (c) Only CPf solutions can be optimal, so the number of optimal solutions cannot exceed the number of CPF solutions( False (d)In a particular iteration of the simplex method, if there is a tie for which variable should be the leaving basic variable then the next bf solution must have at least one basic variable T (e) If there is no leaving basic variable at some iteration, then the problem has no feasibl solution.( False 2. You are the production manager for a manufacturer of three types of spare parts for automobiles. The manufacture of each part requires processing on each of two machines, with the following processing time(in hours ): (table 1) Table 1 Machine B 0.02 0.04 Each machine is available 40 hours per month. Each part manufactured will yield a unit profit as follows Part B Profit You want to determine the mix of spare parts to produce in order to maximize total profit Formulate a linear programming model for this problem. (10 points Solution: we set the mix of spare parts is xA, xB,xc The linear programming model
1 江西财经大学 03-04 学年第二学期期末考试试卷（参考答案） 试卷代码：03883A 卷 课时：64 课程名称：运筹学 I（英） 适用对象：02 管理科学专业 1.Label each of the following statements about linear programming problems as true or false. (10 points) (a) For minimization problems, if the objective function evaluated at a CPF solution is no large than its value at every adjacent CPF solution, then that solution is optimal. ( True ). (b) 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 ). (c) Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of CPF solutions. ( False ). (d) In a particular iteration of the simplex method, if there is a tie for which variable should be the leaving basic variable, then the next BF solution must have at least one basic variable equal to zero.( True ) (e) If there is no leaving basic variable at some iteration, then the problem has no feasible solution. ( False ). 2.You are the production manager for a manufacturer of three types of spare parts for automobiles. The manufacture of each part requires processing on each of two machines, with the following processing time (in hours):(table 1) Table 1 Part Machine A B C 1 0.02 0.03 0.05 2 0.05 0.02 0.04 Each machine is available 40 hours per month. Each part manufactured will yield a unit profit as follows: Part A B C Profit 50 40 30 You want to determine the mix of spare parts to produce in order to maximize total profit. Formulate a linear programming model for this problem.（10 points） Solution: we set the mix of spare parts is xA,xB,xC The linear programming model is
maxZ=50x,+40x。+30x 0.02x+0.03xa+0.05x≤40 s0.05x,+0.02xn+0.04x≤40 0 3. Consider a preemptive goal programming problem with three priority levels, just one goal for each priority level, and just two activities to contribute toward these goals, as summarized in the following table Unit contribution activity Priority Level Goal First priority Second priority 2211 Third priority Use the goal programming technique to formulate one complete linear programming model for this problem. (10 points) Solution we set the activities level are xix min Z,=d min z=d.+d min z,=d The linear goal programming model is 2x,+d1-d1=20 d2-d2+=1 2x1+x2+d3-d3=4 4. Use the simplex method to solve the following problem (15 points Maximize Z=4x,+3x2+6x3 subject to 2x,+2x,+3x,<40 x1≥0,x2≥0,x3≥0 Solution: the process of simplex method iteration described as follows Coefficient of Basic variable (4 X5 Right side X4 (1)0 X5 (2) 0 2 2 Z 00100 60 l/3 (2) 36330100
2 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ + + ≤ + + ≤ = + + , , 0 0.05 0.02 0.04 40 0.02 0.03 0.05 40 . . max 50 40 30 A B C A B c A B c A B C x x x x x x x x x st Z x x x 3. Consider a preemptive goal programming problem with three priority levels, just one goal for each priority level, and just two activities to contribute toward these goals, as summarized in the following table: Unit contribution activity Priority Level 1 2 Goal First priority 1 2 ≤20 Second priority 1 1 =15 Third priority 2 1 ≥40 Use the goal programming technique to formulate one complete linear programming model for this problem. (10 points) Solution: we set the activities level are x1,x2 The linear goal programming model is ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + + − = + + − = + + − = = = + = − + − + − + − + − + 2 40 15 2 20 . . min min min 1 2 3 3 1 2 2 2 1 2 1 1 3 3 2 2 2 1 1 x x d d x x d d x x d d st Z d Z d d Z d 4. Use the simplex method to solve the following problem. (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = + + 0, 0, 0 2 2 3 40 3 3 30 4 3 6 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 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 -4 -3 -6 0 0 0 X4 (1) 0 3 1 3 1 0 30 X5 (2) 0 2 2 3 0 1 40 Z (0) 1 2 -1 0 2 0 60 X3 (1) 0 1 1/3 1 1/3 0 10 X5 (2) 0 -1 1 0 -1 1 10 Z (0) 1 1 0 0 1 1 70
(1)0 4/3 0 2/3 1/3 20/3 (2)0 So, the optimal solution is x1=0, x2=10, X3=20/3, the optimal value is maxZ=70 5. Consider the following problem. (10 points) Maximize Z=x-x+2x x3 ≤5 x2-x3≤3 subje x1-x2+x3≤2 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 Coefficient of Basic variable z XI x2 x3 x4 5 x6 Right side 0 X6 (2)0 X3 (3)0 Use the fundamental insight to identify the missing numbers in the final simplex tableau Solution the final table is Basic variable c30001 46 Right side 0 8 (1)0 X6 (2)020 X3 (3 0 0 0 6. Consider the following problem(20 points) Maximize z=3x, +x+4x 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
3 X3 (1) 0 4/3 0 1 2/3 -1/3 20/3 X2 (2) 0 -1 1 0 -1 1 10 So, the optimal solution is x1=0,x2=10,x3=20/3, the optimal value is maxZ=70 5.Consider the following problem. (10 points) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ − + ≤ + − ≤ − + ≤ = − + 0, 0, 0 2 3 2 2 3 5 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 1 1 0 X2 (1) 0 1 3 0 X6 (2) 0 0 1 1 X3 (3) 0 1 2 0 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 2 0 0 1 1 0 8 X2 (1) 0 5 1 0 1 3 0 14 X6 (2) 0 2 0 0 0 1 1 5 X3 (3) 0 4 0 1 1 2 0 11 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
+2x =17 (2) (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 a2」 solution is till optimal (e)If a new variable Xnew has been introduced into the model, Xnew coefficient is a6=3. Determine whether the previous optimal solution is till optimal 2 Solution: the final tableau Basic variable Eq 4 5 Right side 2 1/53/5 -1/3 1/3 5/3 (2) -1/5 /5 (a) The optimal solution is x1=5/3, x2=0, X3=3, maxz=17 min S=25y, + 20y2 6y1+3y2≥3 (b)The dual problem is 3y, +4y2 21 ≥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 0 is o,=CRB-A-C 3=--<0.so the 55八3 previous optimal solution is not till optimal (e) The coefficient of new variable Xnew iso=CRB-A6-C6(5 3
4 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 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. Consider the transportation problem having the following cost and requirements table Destinati 2 4 Source 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 Destinati Supply 3(3) 7 6 2 2 2 3 5 8. Consider the maximum flow problem shown below, where the supple node is node A, the demand node is node f, and the arc capacities are the numbers shown next to these directed arcs. Use the augmenting path algorithm to solve this problem. (10 points) 7 Solution: the solution is in the graph (7,7) 6,6) (76) So the maximum flow is F=15
5 the previous optimal solution is till optimal. 7. 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 8.Consider the maximum flow problem shown below, where the supple node is node A, the demand node is node F, and the arc capacities are the numbers shown next to these directed arcs. Use the augmenting path algorithm to solve this problem. (10 points) Solution: the solution is in the graph. So, the maximum flow is F=15 3 7 2 4 6 6 9 7 9 A B C D E F (3,1) (7,7) (2,2) 4 (6,6) (6,6) (9,9) (7,6) (9,9) A B C D E F
