江西财经大学 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. (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. (d)Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of cpf solutions (e) The dual simplex method is always used to solve the dual programming. 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 Machine Ty Product 1 Product 2 Product Lathe Grindel 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)
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. ( ). (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. ( ) (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. ( ). (d) Only CPF solutions can be optimal, so the number of optimal solutions cannot exceed the number of CPF solutions. ( ). (e) The dual simplex method is always used to solve the dual programming.( ) 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)
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 ProductI on the left and the number for product 2 on the right Maximum Combined Production Product 1/ Product 2 Production Unit cost Month RT OT esRT ot of storage 10 5/315/16 18/20 1/2 3/517/520/8 2/1 10 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 4. Consider the following problem Maxz=4x,+5x2+3x3 x,+2x,≥2( x3 0 2-5x3≤50 +3x2+5x3 x1≥0,x2≥0,x3≥0 Use the simplex method to demonstrate that this problem does not posses any feasible solutions(15 points) 5. Consider the following problem. (10 points)
2 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) 4. Consider the following problem ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + − ≤ + + ≥ = + + 0, 0, 0 3 5 30 15 6 5 50 2 20 . . 4 5 3 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 st MaxZ x x x Use the simplex method to demonstrate that this problem does not posses any feasible solutions. (15 points) 5.Consider the following problem. (10 points)
Maximize z=x-x+2 2x1-2x2+3x3≤5 ≤3 subject to +x,≤2 ≥0.x2≥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 Basic variable Z XI X2 X3 X4 X5 6 Right side (0) X6 (2)0 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 6x+3x,+5x2≤25 subject to 3x,+4x+5x.<20 ≥0,x2≥0,x3≥0 The corresponding final set of equations yielding the optimal solution is +-x,+-x。=17 (1) x5 x2+x35 x,+=X。=3 (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 a2=2 Determine whether the previous ptimal solution is till optimal (e)If a new variable Xnew has been introduced into the model, Xnew coefficient is
3 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ − + ≤ + − ≤ − + ≤ = − + 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 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
3. Determine whether the previous optimal solution is till optimal 7. Solve the parameter programming as follow: (15 points Maxz=2x, +x x1≤10+20 x1+x2≤25-6 x,≤10+26 x1≥0,x2≥0 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 costso at the end of year I and trading it in at the end of year j(where year 0 is now) 18 31 10 21 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)
4 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 3 2 26 16 6 a a c . Determine whether 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 θ θ θ 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)