TRB PG Assistant - Linear programming - simplex computational procedure, geometric interpretation, revised simplex method, duality, degeneracy, perturbation techniques Question Bank with Options

1. If a linear programming problem has multiple optimal solutions, what is characteristic of its simplex tableau at optimality?

A) At least one non-basic variable has a zero coefficient in the objective row

B) All non-basic variables have negative coefficients in the objective row

C) The problem is unbounded

D) The problem is infeasible

2. The perturbation technique can be viewed as introducing a small positive quantity 'epsilon' to:

A) The objective function coefficients

B) The right-hand side values of the constraints

C) The coefficients of the constraint matrix

D) The slack variables

3. What is the primary difference in approach between the standard simplex method and the revised simplex method?

A) The standard method uses a tableau, while the revised method uses matrix inversions

B) The standard method only works for minimization, while the revised method works for both

C) The standard method requires an initial feasible solution, while the revised method does not

D) The standard method is iterative, while the revised method is direct

4. The 'fundamental theorem of duality' states that for any primal-dual pair of linear programming problems:

A) If the primal is unbounded, the dual is unbounded

B) If the primal is infeasible, the dual is infeasible

C) The optimal value of the primal is always greater than the optimal value of the dual

D) The optimal value of the primal is always less than the optimal value of the dual

5. In the geometric interpretation, the simplex method moves from one vertex of the feasible region to an adjacent vertex by:

A) Increasing all non-basic variables

B) Changing one non-basic variable to basic and one basic variable to non-basic

C) Decreasing the objective function value

D) Introducing an artificial variable

6. What does the 'shadow price' of a resource represent in linear programming?

A) The total cost of the resource

B) The optimal value of the dual variable associated with the resource constraint

C) The number of units of the resource available

D) The slack in the resource constraint

7. The perturbation technique ensures that in each iteration of the simplex method:

A) A new variable enters the basis

B) A unique variable leaves the basis

C) The objective function value increases

D) The problem becomes infeasible

8. If the primal problem is unbounded, what is the status of the dual problem?

A) Unbounded

B) Infeasible

C) Has an optimal solution

D) Degenerate

9. What is the primary advantage of the revised simplex method over the standard simplex method for large-scale problems?

A) Simpler tableau calculations

B) Reduced storage requirements by avoiding explicit tableau construction

C) Faster convergence to the optimal solution

D) Easier identification of degeneracy

10. In the context of duality, if a dual variable is zero, what does it imply about the corresponding primal constraint?

A) The primal constraint is binding

B) The primal constraint is non-binding (has slack)

C) The primal constraint is infeasible

D) The primal constraint is redundant

11. Which method is often used to find an initial basic feasible solution for problems with no obvious origin solution?

A) The Simplex Method

B) The Revised Simplex Method

C) The Two-Phase Method or Big M Method

D) The Dual Simplex Method

12. The 'pricing out' operation in the revised simplex method involves calculating:

A) The updated basis inverse

B) The values of the basic variables

C) The reduced costs for the non-basic variables

D) The optimal objective function value

13. What does the term 'degeneracy' imply about the basic feasible solution?

A) It is the only feasible solution

B) It is at the intersection of more than the usual number of constraint boundaries

C) It is an unbounded solution

D) It is an infeasible solution

14. If a primal linear programming problem has no feasible solution, what can be said about its dual problem?

A) It has no feasible solution

B) It has an unbounded solution

C) It has a unique optimal solution

D) It is infeasible

15. What is the 'optimality condition' for a minimization problem in the simplex method?

A) All coefficients in the objective row (Cj - Zj) must be non-negative

B) All coefficients in the objective row (Cj - Zj) must be non-positive

C) All coefficients in the objective row (Cj - Zj) must be zero

D) The objective function value must be zero

16. The revised simplex method is computationally more efficient for problems with:

A) Few variables and many constraints

B) Many variables and few constraints

C) A very large number of constraints

D) Non-linear objective functions

17. When using the perturbation technique, how is a variable with a zero value handled?

A) It is removed from the basis

B) It is treated as having a very small positive value (epsilon)

C) It is replaced by a large penalty

D) It is ignored

18. What is the geometric interpretation of duality?

A) The feasible region of the primal is the same as the dual

B) The optimal solution of the primal corresponds to the optimal solution of the dual

C) The dual problem provides lower bounds for the primal maximization problem

D) The dual problem provides upper bounds for the primal minimization problem

19. In the dual simplex method, which variable is selected to leave the basis?

A) The basic variable with the most negative value

B) The basic variable with the most positive value

C) The non-basic variable with the most negative coefficient in the objective row

D) The non-basic variable with the most positive coefficient in the objective row

20. The dual simplex method is particularly useful when:

A) The initial solution is feasible but not optimal

B) The initial solution is optimal but not feasible

C) The problem is unbounded

D) The problem is degenerate

21. If a primal problem has 'm' constraints and 'n' variables, its dual problem will have:

A) m variables and n constraints

B) n variables and m constraints

C) m variables and m constraints

D) n variables and n constraints

22. The 'ratio test' in the simplex method is used to determine:

A) Which variable enters the basis

B) Which variable leaves the basis (the outgoing variable)

C) The optimal value of the objective function

D) Whether the problem is unbounded

23. What is the 'simplex criterion' for selecting the entering variable in a maximization problem?

A) The variable with the most negative coefficient in the objective row

B) The variable with the most positive coefficient in the objective row

C) The variable with the smallest index

D) The variable that results in the largest increase in the objective function

24. In the revised simplex method, how are the reduced costs (or objective function coefficients in the non-basic variables) calculated?

A) Directly from the simplex tableau

B) Using the basis inverse and the original cost coefficients

C) By solving the dual problem separately

D) By adding slack variables

25. What does it mean for a constraint to be 'binding' at the optimal solution?

A) The slack or surplus variable for that constraint is non-zero

B) The constraint is satisfied as an equality

C) The constraint is not active

D) The shadow price is zero

26. The Big M method uses a large penalty (M) in the objective function to:

A) Encourage the optimal solution to use artificial variables

B) Discourage the use of artificial variables in the optimal solution

C) Simplify the simplex tableau

D) Ensure degeneracy

27. What is the purpose of 'artificial variables' in the simplex method?

A) To represent slack in inequality constraints

B) To initiate a basic feasible solution when the origin is not feasible

C) To convert 'greater than or equal to' constraints to equalities

D) Both (B) and (C)

28. If the primal problem is a minimization problem with 'greater than or equal to' constraints, its dual will be:

A) A minimization problem with 'less than or equal to' constraints

B) A maximization problem with 'less than or equal to' constraints

C) A minimization problem with 'greater than or equal to' constraints

D) A maximization problem with 'greater than or equal to' constraints

29. In the context of duality, what is the 'complementary slackness' condition?

A) If a primal variable is positive, its corresponding dual constraint must be binding

B) If a primal constraint is binding, its corresponding dual variable must be positive

C) Both (A) and (B)

D) Neither (A) nor (B)

30. The perturbation technique modifies the problem slightly to ensure that:

A) The objective function becomes non-linear

B) All basic variables are strictly positive

C) The feasible region shrinks

D) The problem becomes infeasible

31. Which technique is commonly used to resolve degeneracy and prevent cycling in the simplex method?

A) Adding artificial variables

B) Using the revised simplex method

C) The perturbation technique (e.g., lexicographical method)

D) Introducing surplus variables

32. What is a potential problem caused by degeneracy during the simplex computation?

A) The algorithm may terminate prematurely with a non-optimal solution

B) The algorithm may cycle, returning to a previous basic feasible solution indefinitely

C) The problem becomes unbounded

D) The dual problem becomes infeasible

33. Degeneracy in linear programming occurs when:

A) The objective function has multiple optimal solutions

B) At least one basic variable in a basic feasible solution is zero

C) The problem has no feasible solution

D) The problem has an unbounded solution

34. What do the values of the dual variables at the optimal solution represent?

A) The optimal values of the primal variables

B) The shadow prices or marginal values of the resources

C) The number of iterations required

D) The slack in the dual constraints

35. Which of the following is a characteristic of the dual of a maximization problem?

A) It is a maximization problem

B) It is a minimization problem

C) It has the same number of variables as the primal

D) It uses slack variables instead of surplus variables

36. What is the 'dual' of a linear programming problem?

A) A modified version of the original problem

B) A problem derived from the original problem that provides information about the primal solution

C) A problem with no feasible region

D) A problem that always has an unbounded solution

37. The duality theorem in linear programming states that:

A) An infeasible problem has a unique optimal solution

B) If a primal problem has an optimal solution, so does its dual, and their optimal values are equal

C) The dual problem always has a better solution than the primal problem

D) Duality is only relevant for unbounded problems

38. What is the 'basis inverse' in the revised simplex method?

A) The inverse of the objective function coefficients

B) The inverse of the submatrix formed by the basic variables

C) The inverse of the constraint matrix

D) The inverse of the slack variable coefficients

39. The revised simplex method is an efficient alternative to the standard simplex method primarily because it:

A) Requires fewer iterations

B) Avoids the use of artificial variables

C) Computes only the necessary elements of the tableau

D) Works only for unbounded problems

40. What is a 'basic variable' in the context of the simplex method?

A) A variable with a value of zero in a basic feasible solution

B) A variable that is part of the basis and has a non-zero value

C) A variable that is not in the basis

D) A variable that is always zero

41. In a maximization problem, if all coefficients in the objective function row (Cj - Zj) of the simplex tableau are non-negative, what can be concluded?

A) The current solution is infeasible

B) The current solution is optimal

C) The problem is unbounded

D) Degeneracy is present

42. What is the purpose of 'slack variables' in linear programming?

A) To convert inequality constraints into equality constraints

B) To represent artificial variables

C) To indicate infeasibility

D) To maximize the objective function

43. When does a linear programming problem have an unbounded solution according to the simplex method?

A) When all coefficients in the objective row are negative

B) When an entering variable can be increased indefinitely without violating constraints

C) When the problem has no feasible solution

D) When degeneracy occurs

44. What does the geometric interpretation of the simplex method illustrate?

A) The movement between vertices of the feasible region

B) The intersection of constraint lines

C) The rate of change of the objective function

D) The convergence of artificial variables

45. Which of the following is NOT a characteristic of the simplex method's tableau?

A) It represents a basic feasible solution

B) It contains coefficients of the objective function

C) It includes slack and artificial variables

D) It shows the current value of the objective function

46. What is the role of the 'pivot element' in the simplex computational procedure?

A) To determine the direction of movement to a new basic feasible solution

B) To identify the constraint that is violated

C) To calculate the objective function value

D) To check for degeneracy

47. In the context of the simplex method, what does a 'basic feasible solution' represent?

A) A point that violates at least one constraint

B) A vertex of the feasible region

C) A point outside the feasible region

D) The origin of the coordinate system

48. What is the primary goal of the simplex method in linear programming?

A) To find the nearest feasible solution

B) To find the optimal solution to a linear programming problem

C) To identify infeasible regions

D) To approximate non-linear functions

Linear programming - simplex computational procedure, geometric interpretation, revised simplex method, duality, degeneracy, perturbation techniques - Question Bank