江西财经大学 0405学年第二学期期末考试试卷 试卷代码:03883B卷 课时:64 课程名称:运筹学I(英) 适用对象:03管理科学专业 1. Label each of the following statements about linear programming problems as true or false (10 (a)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. (b) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. ( (c) The simplex methods rule for choosing the entering basic variable is used because it always leads to the best adjacent BF solution(largest z).( ( d) The simplex methods minimum ratio rule fro choosing the leaving basic variable used because making another choice with a large ratio would yield a basic solution that is not feasible. (e)If at least one of the basic variables has a coefficient of zero in row o of the final tableau, then the problem has multiple optimal solutions. 2. A company needs to lease warehouse storage space over the next 5 months. Just how much space will be required in each of these months is known. However, since these space requirements are quite different, it may be most economical to lease only the amount needed each month on a month-by-month basis. On the other hand, the additional cost for leasing space for additional months is much less than for the first month, so it may be less expensive to lease the maximum amount needed for the entire 5 months. Another option is the intermediate approach of changing the total amount of space leased(by adding a new lease and /or having an old lease expire)at least once but not every month The space requirement (in thousands of square feet) and the leasing costs(in hundreds of dollars) for the various leasing periods are as follows month Required space (000Leasing eriod Cost per 1,000 square Square feet) (Months) feet leased ($00 650 12345 20 1.000 350 600 The objective is to minimize the total leasing cost for meeting the space requirements. Please formulate a linear programming model for this problem. (10 points)
1 江西财经大学 04-05 学年第二学期期末考试试卷 试卷代码：03883B 卷 课时：64 课程名称：运筹学 I（英） 适用对象：03 管理科学专业 1. Label each of the following statements about linear programming problems as true or false. (10 points) (a) 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. ( ) (b) If a feasible solution is optimal but not a CPF solution, then infinitely many optimal solutions exist. ( ) (c) The simplex method’s rule for choosing the entering basic variable is used because it always leads to the best adjacent BF solution (largest Z).( ) (d) The simplex method’s minimum ratio rule fro choosing the leaving basic variable is used because making another choice with a large ratio would yield a basic solution that is not feasible.( ) (e) If at least one of the basic variables has a coefficient of zero in row 0 of the final tableau, then the problem has multiple optimal solutions. ( ). 2. A company needs to lease warehouse storage space over the next 5 months. Just how much space will be required in each of these months is known. However, since these space requirements are quite different, it may be most economical to lease only the amount needed each month on a month-by-month basis. On the other hand, the additional cost for leasing space for additional months is much less than for the first month, so it may be less expensive to lease the maximum amount needed for the entire 5 months. Another option is the intermediate approach of changing the total amount of space leased (by adding a new lease and /or having an old lease expire) at least once but not every month. The space requirement (in thousands of square feet) and the leasing costs (in hundreds of dollars) for the various leasing periods are as follows: Month Required space (000 Square feet) Leasing period (Months) Cost per 1,000 square feet leased ($00) 1 30 1 650 2 20 2 1,000 3 40 3 1,350 4 10 4 1,600 5 50 5 1,900 The objective is to minimize the total leasing cost for meeting the space requirements. Please formulate a linear programming model for this problem. (10 points)
3. A corporation has decided to produce three new products. Five branch plants now have excess product capacity. The unit manufacturing cost of the first product would be $31, $29, $32, $28, and $29, in plants 1, 2,3, 4, and 5, respectively. The unit manufacturing cost of the second product would be $45, $41, $46, $42, and $43 in Plants 1, 2, 3, 4, and 5, respectively. The unit manufacturing cost of the third product would be $38, $35, and $40 in Plants 1, 2, and 3, respectively, and Plants 4 and 5 do not have the capability for producing this product. Sales forecasts indicate that 600 1000, and 800 units of products 1, 2, and 3, respectively, should be produced per da Plants 1, 2, 3, 4, and 5 have the capacity to produce 400, 600, 400, 600, and 1000 units daily, respectively, regardless of the product or combinations of products involved Assume that any plant having the capability and capacity to produce them can produce any combination of the products in any quantity Management wishes to know how to allocate the new products to the plants to minimize the total manufacturing cost Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) 4. Use the simplex method to solve the following problem(15 points) Maximize Z=5x,+3x+4 subject to3x+x,+2x3≤30 x1≥0,x2≥0,x3≥0 5 Consider the following problem(15 points) MaxZ= 2x,+7x.+4 x1+2x2+x3≤10 s【3x1+3x,+2x2≤10 ≥0,x2≥0,x3≥0 (a)Construct the dual problem for this primal problem (b)Use the dual problem to demonstrate that the optimal value of Z for the primal problem cannot exceed 25 (c) It has conjectured that x2 and x4 should be the basic variables for the optimal solution of the primal problem Directly derive this basic solution(and Z)by using Gaussian elimination. Simultaneously derive and identify the complementary basic solution for the dual problem by using Eq (0) for the primal problem 6. Consider the following parametric linear programming problem (20 points)
2 3. A corporation has decided to produce three new products. Five branch plants now have excess product capacity. The unit manufacturing cost of the first product would be $31, $29,$32,$28, and $29, in plants 1,2,3,4, and 5, respectively. The unit manufacturing cost of the second product would be $45, $41,$46,$42, and $43 in Plants 1,2,3,4, and 5, respectively. The unit manufacturing cost of the third product would be $38, $35, and $40 in Plants 1,2, and 3, respectively, and Plants 4 and 5 do not have the capability for producing this product. Sales forecasts indicate that 600, 1000, and 800 units of products 1,2,and 3, respectively, should be produced per day. Plants 1,2,3,4, and 5 have the capacity to produce 400,600,400,600, and 1000 units daily, respectively, regardless of the product or combinations of products involved. Assume that any plant having the capability and capacity to produce them can produce any combination of the products in any quantity. Management wishes to know how to allocate the new products to the plants to minimize the total manufacturing cost. Formulate this problem as a transportation problem by constructing the appropriate cost and requirements table. (10 points) 4. Use the simplex method to solve the following problem (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = + + 0, 0, 0 3 2 30 2 20 5 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 .5 Consider the following problem (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + ≤ = + + 0, 0, 0 3 3 2 10 2 10 . . 2 7 4 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x st MaxZ x x x (a) Construct the dual problem for this primal problem. (b) Use the dual problem to demonstrate that the optimal value of Z for the primal problem cannot exceed 25. (c) It has conjectured that x2 and x4 should be the basic variables for the optimal solution of the primal problem. Directly derive this basic solution (and Z) by using Gaussian elimination. Simultaneously derive and identify the complementary basic solution for the dual problem by using Eq.(0) for the primal problem. 6. Consider the following parametric linear programming problem: (20 points)
Maxz= 2x, +4x +5x x1+3x2+2x3≤5+b sn{x1+2x2+3x3≤6+20 0,x,≥0,x2≥0 where e can be assigned any positive or negative values. Let x4 and xs be the slack variables for the respective functional constraints. After we apply the simplex method with 0=0, the final simplex tableau is Basic variable Coefficient of E XI Right side 0 a. Express the BF solution (and Z) given in this tableau as a function of e Determine the lower and upper bounds on e before this optimal solution would become infeasible Then determine the best choice of 0 between these bound that 0 the bounds found in part(a), determine the allow range to stay optimal for cl(the coefficient of xl in the objective function) 7. Consider the following project network. By using the PErT three-estimate approach, suppose that the usual three estimates for the time required(in weeks) for each of these activities are as follows: (20 points) Activity Optimistic estimate Most likely estimate Pessimistic estimate 2364 14 18 3→6 20 26 26 34 42 6→7 12 (a)On the basis of the estimates just listed, calculate the expected value and standard deviation of the time required for each activity (b)Using expected times, determine the critical path for the project
3 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ ≥ + + ≤ + + + ≤ + = + + 0, 0, 0 2 3 6 2 3 2 5 . . 2 4 5 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x st MaxZ x x x θ θ where θcan be assigned any positive or negative values. Let x4 and x5 be the slack variables for the respective functional constraints. After we apply the simplex method with θ=0, the final simplex tableau is Coefficient of : Basic variable Eq. Z X1 X2 X3 X4 X5 Right side Z (0) 1 0 1 0 1 1 11 X1 (1) 0 1 5 0 3 -2 3 X3 (2) 0 0 -1 1 -1 1 1 a. Express the BF solution (and Z) given in this tableau as a function ofθ. Determine the lower and upper bounds onθ before this optimal solution would become infeasible. Then determine the best choice of θ between these bounds. b. Given thatθ is between the bounds found in part(a), determine the allowable range to stay optimal for c1(the coefficient of x1 in the objective function). 7. Consider the following project network. By using the PERT three-estimate approach, suppose that the usual three estimates for the time required (in weeks) for each of these activities are as follows:(20 points) Activity Optimistic estimate Most likely estimate Pessimistic estimate 1→2 1→3 2→6 3→4 3→5 3→6 4→5 5→6 5→7 6→7 28 22 26 14 32 40 12 16 26 12 32 28 36 16 32 52 16 20 34 16 36 32 46 18 32 74 24 26 42 30 (a) On the basis of the estimates just listed, calculate the expected value and standard deviation of the time required for each activity. (b) Using expected times, determine the critical path for the project
