江西财经大学 03-04学年第二学期期末考试试卷 试卷代码:03883B卷 课时:64 课程名称:运筹学Ⅰ(英) 适用对象:02管理科学专业 1. Label each of the following statements about linear programming problems as true or false (10 points) (a) The simplex method's minimum ratio rule for choosing the leaving basic variable is used because making another choice with a large ratio would yield a basic solution that is not feasible (b)When the simplex method solves for the next BF solution, elementary algebraic operations are used to eliminate each nonbasic variable from all but one equation(its equation ) and to give it a coefficient of +l in that one equation. (c) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. (d) If the problem has n variables(before augmenting), then the simultaneous solution of any set of n constraint boundary equations is a CPF solution O (e) If the primal problem has an unbounded objective function, then the optimal value of the objective function for the dual problem must be zero. 2. A certain corporation has three branch plants with excess production capacity. Fortunately, the corporation has a new product ready to begin production, and all three plants have this capability, so some of the excess capacity can be used in this way. This product can be made in three size--large, medium, and small ---that yield a net unit profit of $420, $360, and $300, The amount of available in-process sto limitation on the production rates of the new product. Plants 1, 2 and 3 have 13,000, 12,000, and 5,000 square feet, respectively, of in-process storage space available for a day's production of this product Each unit of the large, medium, and small sizes produced per day requires 20, 15, and 12 square feet, respectively Sales forecasts indicate that if available, 900, 1, 200, and 750 units of the large, medium and small sizes, respectively, would be sold per day At each plant, some employees will need to be laid off unless most of the plant's excess production capacity can be used to produce the new product. To avoid layoffs if possible management has decided that the plants should use the same percentage of their excess apacity to produce the new product Management wishes to know how much of each size should be produced by each plant to maximize profit. Formulate a linear programming model for this problem. (10 points) 3. The research and development division of a certain company has developed three new products. The problem is to decide which mix of these products should be produced
1 江西财经大学 03-04 学年第二学期期末考试试卷 试卷代码：03883B 卷 课时：64 课程名称：运筹学 I（英） 适用对象：02 管理科学专业 1.Label each of the following statements about linear programming problems as true or false. (10 points) (a) The simplex method’s minimum ratio rule for choosing the leaving basic variable is used because making another choice with a large ratio would yield a basic solution that is not feasible. ( ) (b) When the simplex method solves for the next BF solution, elementary algebraic operations are used to eliminate each nonbasic variable from all but one equation (its equation) and to give it a coefficient of +1 in that one equation. ( ) (c) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. ( ) (d) If the problem has n variables (before augmenting), then the simultaneous solution of any set of n constraint boundary equations is a CPF solution. ( ) (e) If the primal problem has an unbounded objective function, then the optimal value of the objective function for the dual problem must be zero.( ) 2. A certain corporation has three branch plants with excess production capacity. Fortunately, the corporation has a new product ready to begin production, and all three plants have this capability, so some of the excess capacity can be used in this way. This product can be made in three size—large, medium, and small ---that yield a net unit profit of $420, $360, and $300, respectively. Plants 1,2, and 3 have the excess capacity to produce 750,900, and 450 units per day of this product, respectively, regardless of the size or combination of sizes involved. The amount of available in-process storage space also imposes a limitation on the production rates of the new product. Plants 1, 2 and 3 have 13,000, 12,000, and 5,000 square feet, respectively, of in-process storage space available for a day’s production of this product. Each unit of the large, medium, and small sizes produced per day requires 20, 15, and 12 square feet, respectively. Sales forecasts indicate that if available, 900,1,200, and 750 units of the large, medium, and small sizes, respectively, would be sold per day. At each plant, some employees will need to be laid off unless most of the plant’s excess production capacity can be used to produce the new product. To avoid layoffs if possible, management has decided that the plants should use the same percentage of their excess capacity to produce the new product. Management wishes to know how much of each size should be produced by each plant to maximize profit. Formulate a linear programming model for this problem. (10 points) 3. The research and development division of a certain company has developed three new products. The problem is to decide which mix of these products should be produced
Management wants primary consideration given to three factors: long-run profit, stability in the workforce, and an increase in the companys earning next year. In particular, using the units given in the following table, they want to Maximize Z=2P-5C-3D Where P=total( discounted) profit over life of new products C=change(in either direction)in current level of employment, D=decrease(if any)in next years earnings from current year's leve The amount of any increase in earning does not enter into Z, because management is concerned primarily with just achieving some increase to keep the stockholders happy. (It has mixed feelings about a large increase that then would be difficult to surpass in subsequent The impact of each of the new products(per unit rate of production) on each of these factors is shown in the following table Product unit contribution Factor Units Long-run profit Maximize (millions of dollars Employment level (hundreds of employees) Earning next year ≥75 ( Millions of dollars) Assuming that three are no additional constraints on the production rates not described here, use the goal programming technique to formulate a linear programming model for this problem. (10 points) 4. Use the simplex method to solve the following problem (15 points Maximize Z=5x,+4x2 x1+3x2≤90 80 subject to x,+x≤45 x1≥0,x2≥0 5. Consider the following problem (10 points) Maximize Z=6x,+x2+2x3 x3 x3≤3 subject to 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 Basic variable E Coefficient of
2 Management wants primary consideration given to three factors: long-run profit, stability in the workforce, and an increase in the company’s earning next year. In particular, using the units given in the following table, they want to Maximize Z=2P-5C-3D Where P=total (discounted) profit over life of new products. C=change (in either direction) in current level of employment, D=decrease (if any) in next year’s earnings from current year’s level. The amount of any increase in earning does not enter into Z, because management is concerned primarily with just achieving some increase to keep the stockholders happy. (It has mixed feelings about a large increase that then would be difficult to surpass in subsequent years.) The impact of each of the new products (per unit rate of production) on each of these factors is shown in the following table: Product unit contribution Factor 1 2 3 Goal Units Long-run profit 20 15 25 Maximize （millions of dollars） Employment level 6 4 11 =50 (hundreds of employees) Earning next year 8 7 5 ≥75 (Millions of dollars) Assuming that three are no additional constraints on the production rates not described here, use the goal programming technique to formulate a linear programming model for this problem. (10 points) 4. Use the simplex method to solve the following problem. (15 points) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ + ≤ + ≤ + ≤ = + 0, 0 45 2 80 3 90 5 4 1 2 1 2 1 2 1 2 1 2 x x x x x x x x subject to Maximize Z x x 5.Consider the following problem (10 points) ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ − − − ≤ + + ≤ = + + 0, 0, 0 1 2 1 2 3 2 3 4 2 2 2 1 2 2 6 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 Eq. Coefficient of :
iz XI 2 3 x4 5 6 Right side 0 2 )|0 2 (2)0 20 Use the fundamental insight to identify the missing numbers in the final simplex tableau 6. Consider the following problem(20 points) Maximize Z=2x,+7x2-3x3 x1+3x2+4x3≤30 subject to{x1+4x2-x3≤10 x≥0,x2≥0,x3≥0 The corresponding final set of equations yielding the optimal solution is (0) x2+ +2x。=20 x2+5x3+x4-x6=20 (2) +4x2- Now you are to conduct sensitivity analysis by independently investigating each of the following changes in the original model. For each change, use the sensitivity analysis procedure to determine whether the previous optimal solution is till optimal (a)Change the right-hand sides to b2」[30 (b)Change the coefficients of x, to a,3= 3 2 (c)Introduce a new variable x6 with coefficients am=1 (d)Introduce a new constraint 3x,+2x,+3x2 <25 (e)Change constraint 2 to x,+2x2+2x, <35 7. A contractor has to haul gravel to three building sites. She can purchase as much as 18 tons at a gravel pit in the north of the city and 14 tons at one in the south. She needs 10, 5, and 10 tons at sites 1, 2, and 3, respectively. The purchase price per ton at each gravel pit and the hauling cost per ton are given in the table below Hauling cost per ton at site Price per ton
3 Z X1 X2 X3 X4 X5 X6 Right side Z (0) 1 2 0 2 X5 (1) 0 1 1 2 X3 (2) 0 -2 0 4 X1 (3) 0 1 0 -1 Use the fundamental insight to identify the missing numbers in the final simplex tableau. 6. Consider the following problem (20 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + − ≤ + + ≤ = + − 0, 0, 0 4 10 3 4 30 2 7 3 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 (2) 4 10 (1) 5 20 (0) 2 20 1 2 3 5 2 3 4 5 2 3 5 + − + = − + + − = + + + = x x x x x x x x Z x x x Now you are to conduct sensitivity analysis by independently investigating each of the following changes in the original model. For each change, use the sensitivity analysis procedure to determine whether the previous optimal solution is till optimal. (a) Change the right-hand sides to ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 30 20 2 1 b b (b) Change the coefficients of x3 to ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 3 2 23 13 3 a a c (c) Introduce a new variable x6 with coefficients ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡− = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 1 3 21 11 6 a a c (d) Introduce a new constraint 3x1 + 2x2 + 3x3 ≤ 25 (e) Change constraint 2 to x1 + 2x2 + 2x3 ≤ 35 7. A contractor has to haul gravel to three building sites. She can purchase as much as 18 tons at a gravel pit in the north of the city and 14 tons at one in the south. She needs 10, 5, and 10 tons at sites 1,2, and 3, respectively. The purchase price per ton at each gravel pit and the hauling cost per ton are given in the table below. Hauling cost per ton at site Pit 1 2 3 Price per ton
North 6 South Now formulate this problem as a transportation problem by constructing the appropriate cost and requirements table and determine the optimal solution (15 points 8. Use the augmenting path algorithm to find the flow pattern giving the maximum flow from the supply node to the demand node given that the arc capacity from node i to node is the number nearest node i along the arc between these nodes (10 points) upp Demand
4 North 3 6 5 10 South 6 3 4 12 Now formulate this problem as a transportation problem by constructing the appropriate cost and requirements table and determine the optimal solution. (15 points) 8. Use the augmenting path algorithm to find the flow pattern giving the maximum flow from the supply node to the demand node given that the arc capacity from node i to node j is the number nearest node i along the arc between these nodes. (10 points) 4 4 1 1 3 3 4 9 4 6 1 2 3 4 5 6 7 Supply Demand
