CH 17 - Linear Programming: Simplex Method. Questions and Answers

Document Content and Description Below

True / False 1. When a system of simultaneous equations has more variables than equations, there is a unique solution. a. True b. False 2. In order to determine a basic solution, set... n − m of the variables equal to zero, and solve the m linear constraint equations for the remaining m variables. a. True b. False 3. A basic feasible solution also satisfies the nonnegativity restriction. a. True b. False 4. The simplex method is an iterative procedure for moving from one basic feasible solution (an extreme point) to another until the optimal solution is reached. a. True b. False 5. In a simplex tableau, a variable is associated with each column and both a constraint and a basic variable are associated with each row. a. True b. False 6. At each iteration of the simplex procedure, a new variable becomes basic and a currently basic variable becomes nonbasic, preserving the same number of basic variables and improving the value of the objective function. a. True b. False 7. Coefficients in a nonbasic column in a simplex tableau indicate the amount of decrease in the current basic variables when the value of the nonbasic variable is increased from 0 to 1. a. True b. False 8. If a variable is not in the basis, its value is 0. a. True b. False 9. The purpose of row operations is to create a unit column for the entering variable while maintaining unit columns for the remaining basic variables. a. True b. False 10. Infeasibility can be recognized when the optimality criterion indicates that an optimal solution has been obtained, and one or more of the artificial variables remain in the solution at a positive value. a. True b. False 11. Artificial variables are added for the purpose of obtaining an initial basic feasible solution. a. True b. False 12. A solution is optimal when all values in the cj − zj row of the simplex tableau are either zero or positive. a. True b. False 13. The variable to enter into the basis is the variable with the largest positive cj − zj value. a. True b. False 14. The variable to remove from the current basis is the variable with the smallest positive cj − zj value. a. True b. False 15. The coefficient of an artificial variable in the objective function is zero. a. True b. False Multiple Choice 16. Algebraic methods such as the simplex method are used to solve a. nonlinear programming problems. b. any size linear programming problem. c. programming problems under uncertainty. d. graphical models. 17. A basic feasible solution is a basic solution that a. also satisfies the nonnegativity conditions. b. contains 0 variables. c. corresponds to no extreme points. d. None of these are correct. 18. A basic solution and a basic feasible solution a. are the same thing. b. differ in the number of variables allowed to be zero. c. describe interior points and exterior points, respectively. d. differ in their inclusion of nonnegativity restrictions. 19. Whenever a system of simultaneous linear equations has more variables than equations, a. it is a basic set. b. it is a feasible set. c. there is a unique solution. d. we can expect an infinite number of solutions. 20. Unit columns are used to identify the a. tableau. b. c row. c. b column. d. basic variables. 21. The values in the cj − zj , or net evaluation, row indicate the a. value of the objective function. b. decrease in value of the objective function that will result if one unit of the variable corresponding to the jth column of the A matrix is brought into the basis. c. net change in the value of the objective function that will result if one unit of the variable corresponding to the jth column of the A matrix is brought into the basis. d. values of the decision variables. 22. The purpose of the tableau form is to provide a(n) a. infeasible solution. b. optimal infeasible solution. c. initial basic feasible solution. d. degenerate solution. 23. Which of the following is NOT a step that is necessary to prepare a linear programming problem for solution using the simplex method? a. Formulate the problem. b. Set up the standard form by adding slack and/or subtracting surplus variables. c. Perform elementary row and column operations. d. Set up the tableau form. 24. In the simplex method, a tableau is optimal only if all the cj − zj values are a. zero or negative. b. zero. c. negative and nonzero. d. positive and nonzero. 25. The way we guarantee that artificial variables will be eliminated before the optimal solution is reached is to assign each artificial variable the coefficient value of a. 0. b. 1. c. a very large negative number. d. a very large positive number. 26. If one or more of the basic variables in a linear program have a value of zero, a. post-optimality analysis is required. b. their dual prices will be equal. c. converting the pivot element will break the tie. d. a condition of degeneracy is present. 27. An alternative optimal solution is indicated when, in the simplex tableau, a a. nonbasic variable has a value of zero in the cj − zj row. b. basic variable has a positive value in the cj − zj row. c. basic variable has a value of zero in the cj − zj row. d. nonbasic variable has a positive value in the cj − zj row. 28. Infeasibility exists when one or more of the artificial variables a. remain in the final solution as a negative value. b. remain in the final solution as a positive value. c. have been removed from the basis. d. remain in the basis. 29. Which of the following steps is included in the preparation of a linear programming problem for a solution using the simplex method? a. Formulate the problem. b. Set up the standard form by adding slack and/or subtracting surplus variables. c. Set up the tableau form. d. All of these are correct. Subjective Short Answer 30. Write the following problem in tableau form. Which variables would be in the initial basic solution? Min Z = 3x1 + 8x2 s.t. x1 + x2 ≤ 200 x1 ≤ 80 x2 ≤ 60 31. An initial simplex tableau is shown below. x1 x2 x3 s1 s2 s3 Basis cB 5 8 12 0 0 0 s1 0 3 4 5 1 0 0 80 s2 0 9 15 20 0 1 0 250 s3 0 1 −1 2 0 0 0 20 zj 0 0 0 0 0 0 0 cj − zj 5 8 12 0 0 0 a. What variables form the basis? b. What are the current values of the decision variables? c. What is the current value of the objective function? d. Which variable will be made positive next, and what will its value be? e. Which variable that is currently positive will become 0? f. What value will the objective function have next? 32. A simplex tableau is shown below. x1 x2 x3 s1 s2 Basis cB 3 4 5 0 0 1/2 1 0 1/2 −1/2 6 0 0 1 −1/4 1 3 cj cj − zj a. What variables form the basis? b. What are the current values of the decision variables? c. What is the current value of the objective function? d. Which variable will be made positive next, and what will its value be? e. Which variable that is currently positive will become 0? f. What value will the objective function have next? 33. A simplex tableau is shown below. x1 x2 x3 s1 s2 s3 Basis cB 3 5 8 0 0 0 s1 0 3 6 0 1 0 −9 126 s2 0 −5/2 −1/2 0 0 1 −9/2 45 x3 8 1/2 1/2 1 0 0 1/2 18 zj 4 4 8 0 0 4 144 cj − zj −1 1 0 0 0 −4 a. Perform one more iteration of the simplex procedure. b. What is the current complete solution? c. Is this solution optimal? Why or why not? 34. A simplex tableau is shown below. x1 x2 x3 s1 s2 s3 Basis cB 5 4 8 0 0 0 s1 0 2/5 −3/5 0 1 −2/5 0 4 x3 8 4/5 4/5 1 0 1/5 0 8 s3 0 4/5 9/5 0 0 1/5 1 10 zj 32/5 32/5 8 0 8/5 0 64 cj − zj −7/5 −12/5 0 0 −8/5 0 a. What is the current complete solution? b. The 32/5 for z1 is composed of 0 + 8(4/5) + 0. Explain the meaning of this number. c. Explain the meaning of the −12/5 value for c 2 − z2. 35. Solve the following problem by the simplex method. Max 14x1 + 14.5x2 + 18x3 s.t. x1 + 2x2 + 2.5x3 ≤ 50 x1 + x2 + 1.5x3 ≤ 30 x1 , x2 , x3 ≥ 0 36. Solve the following problem by the simplex method. Max 100x1 + 120x2 + 85x3 s.t. 3x1 + 1x2 + 6x3 ≤ 120 5x1 + 8x2 + 2x3 ≤ 160 x1 , x2 , x3 ≥ 0 37. Determine from a review of the following tableau whether the linear programming problem has multiple optimal solutions. Basis cB x1 x2 s1 s2 s3 s3 0 0 0 1 −1/5 8/6 6 x2 2 0 1 0 1/5 −3/5 1 x1 3 1 0 0 1/5 2/5 4 zj 3 2 0 0 0 14 cj −zj 0 0 0 −1 0 38. Write the following problem in tableau form. Which variables would be in the initial basis? Max x1 + 2x2 s.t. 3x1 + 4x2 ≤ 100 2x1 + 3.5x2 ≥ 60 2x1 − 1x2 = 4 x1 , x2 ≥ 0 39. Write the following problem in tableau form. Which variables would be in the initial basic solution? Min Z = −3x1 + x2 + x3 s.t. x1 − 2x2 + x3 ≤ 11 −4 x1 + x2 + 2x3 ≥ 3 2x1 − x3 ≥ −1 40. Identify the type of solution shown in this simplex tableau. x1 x2 x3 s1 s2 a1 Basis cB 1 2 5 0 0 −M a1 −M −3 −1 0 −1 −2 1 4 x3 5 1 1/2 1 0 1/2 0 4 zj 5 + 3M 2.5 + M 5 M 2.5 + 2M −M −4M + 20 cj − zj −4 − 3M −0.5 − M 0 −M −2.5 − 2M 0 41. What type of solution is shown in this simplex tableau? x1 x2 x3 s1 s2 Basis cB 4 6 5 0 0 s1 0 3 0 −1 1 −1 26 x2 6 1 1 1 0 −1 10 zj 6 6 6 0 −6 60 cj − zj −2 0 −1 0 6 42. Joe Forrester, an operations analyst for a manufacturing company, developed the following LP formulation. From it, create an initial simplex tableau. Max 40xl + 30x2 + 50x3 s.t. 2xl + 3x2 + 4x3 < 200 x1 + 2x2 + 2x3 < 300 3xl + x2 + 5x3 < 500 43. Jackie Quinn developed the following LP formulation for a problem she is working on and now needs to create an initial simplex tableau. Create the initial simplex tableau. Min 75xl + 45x2 s.t. 3xl + 2x2 > 10 xl + 6x2 > 15 44. A student in a Management Science class developed this initial tableau for a maximization problem and now wants to perform row operations to create the next tableau and check for an optimal solution. Create the next tableau. Is there an optimal solution? x1 x2 s1 s2 s3 Basis cB 550 350 0 0 0 s1 0 2 2 1 0 0 2000 s2 0 2 1 0 1 0 1500 s3 0 1 2 0 0 1 3000 zj 0 0 0 0 0 0 cj – zj 550 350 0 0 0 45. A student in a Management Science class wants to perform row operations on this second tableau and complete the third tableau to see if it is optimal. If it is optimal, what is the optimal answer? x1 x2 s1 s2 s3 Basis cB 550 350 0 0 0 s1 0 0 1 1 –1 0 500 x1 550 1 1/2 0 1/2 0 750 s3 0 0 3/2 0 –1/2 1 2250 zj 550 275 0 275 0 412,500 cj – zj 0 75 0 –275 0 46. An operations research analyst for a communications company has the following LP problem and wants to solve it using the simplex method. Max 50x1 + 20x2 s.t. 2x1 + x2 < 200 x1 + x2 < 350 xl + 2x2 < 275 47. The operations research analyst for a big manufacturing firm in Oregon developed the following variable definitions for an LP maximization problem she was working on. The company was trying to determine how many consoles of each model to produce next week given each console had to go through three production departments. She obtained the following optimal simplex tableau for the problem and wanted to interpret its meaning. Variable definitions: xl = number of model 1 consoles produced x2 = number of model 2 consoles produced s1 = unused personnel hours in department 1 s2 = unused personnel hours in department 2 s3 = unused personnel hours in department 3 objective function = total profit on model 1 and model 2 consoles produced in the coming week Optimal tableau x1 x2 s1 s2 s3 Basis cB 180 350 0 0 0 x1 180 1 0 1 0 –1 15 s2 0 0 0 –1 1 1 10 x2 350 0 1 0 0 1 20 zj 180 350 180 0 170 9700 cj – zj 0 0 –180 0 –170 48. A manager for a food company is putting together a buffet, and she is trying to determine the best mix of crab and steak to be served. Below are variable definitions she developed including vitamin, mineral, and protein requirements and an optimal simplex tableau she obtained from her computations. She is interested in interpreting what it means. Variable definitions: xl = amount of crab (oz.) to be served per buffet batch x2 = amount of steak (oz.) to be served per buffet batch s1 = vitamin A units provided in excess of requirements s2 = mineral units provided in excess of requirements s3 = protein units provided in excess of requirements Optimal tableau x1 x2 a1 a2 a3 s1 s2 s3 Basis cB –7 –4 –M –M –M 0 0 0 s2 0 0 0 4 –2 –1 –4 1 2 2500 x2 –4 0 1 1/50 0 –1/100 –1/50 0 1/100 20 x1 –7 1 0 –1/100 0 1/100 1/100 0 –1/100 15 zj –7 –4 1/100 0 –3/100 1/100 0 170 –185 cj – zj 0 0 –M –M –M –1/100 0 –3/100 [Show More]

Last updated: 2 years ago

Preview 1 out of 21 pages