江西财经大学 03-04学年第二学期期末考试试卷 试卷代码:03883A卷 课时: 课程名称:运筹学Ⅰ(英) 适用对象: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 (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. (c) Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of CPF solutions. (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. (e) If there is no leaving basic variable at some iteration, then the problem has no feasible solution.( 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 0.02 0.03 0.05 0.02 0.04 Each machine is available 40 hours per month. Each part manufactured will yield a unit profit as follows: Profit B 40 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 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
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.. ( ). (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. ( ). (c) Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of CPF solutions. ( ). (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.( ) (e) If there is no leaving basic variable at some iteration, then the problem has no feasible solution. ( ). 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） 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:
Priority level Unit contribution activity 2 Goal First priority ≤20 Second priority Third priority Use the goal programming technique to formulate one complete linear programming model for this problem. (10 points) 4. Use the simplex method to solve the following problem (15 points) Maximize Z=4x, +3x +6x subject to 32x, +2x, +3x, <40 x1≥0,x,≥0,x2≥0 5. Consider the following problem. 8 points) Ma Z=xX, 2x1-2x2+3x3≤5 subje +x2-x3 x1-x2+x3≤2 x.≥0.x≥0.x≥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 Coefficient of Basic variable X3 x4 5 6 Right side 0 X2 (1)0 0 X6 (2)0 (3)0 Use the fundamental insight to identify the missing numbers in the final simplex tableau 6. Consider the following problem(20 points) Maximize Z=3x, +x+4x 6x1+3x2+5x3≤25 bject to 3x,+4x,+5x2 <20 ≥0,x,≥0,x3≥0 The corresponding final set of equations yielding the optimal solution is
2 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) 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 5.Consider the following problem. (8 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. 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. Determine whether the previous optimal a22 olution 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 7. Consider the transportation problem having the following cost and requirements table Destination Supply 2 2 2 4 3 5 Demand 2 Determine the optimal solution (13 points) 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.( 8 points) 7
3 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. 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. (13 points) 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. (8 points) 3 7 2 4 6 6 9 7 9 A B C D E F