TRB PG Assistant - Integer programming, transportation problem Online Test (MCQ Quiz)

1. What is the primary objective of Integer Programming (IP) compared to Linear Programming (LP)?

A) To minimize the number of variables B) To ensure all decision variables take on integer values C) To maximize the sum of variables D) To allow continuous values for decision variables

2. Which type of integer programming problem requires all decision variables to be integers?

A) Mixed Integer Programming (MIP) B) Pure Integer Programming (PIP) C) Binary Integer Programming (BIP) D) Goal Programming

3. In Mixed Integer Programming (MIP), what types of variables are allowed?

A) Only integer variables B) Only continuous variables C) A mix of integer and continuous variables D) Only binary variables

4. What is a special case of Integer Programming where variables can only take values of 0 or 1?

A) Non-linear Integer Programming B) Pure Integer Programming C) Binary Integer Programming D) Goal Programming

5. Which of the following is a common method for solving Integer Programming problems?

A) Simplex Method B) Branch and Bound Method C) Hungarian Method D) Least Cost Method

6. The Branch and Bound method for IP typically involves:

A) Solving a sequence of LP relaxations B) Finding a feasible solution by inspection C) Graphing the feasible region D) Using only heuristic approaches

7. What is 'LP relaxation' in the context of Branch and Bound for IP?

A) Ignoring the integer constraints and solving as an LP B) Adding more constraints to the LP C) Using a simplified objective function D) Approximating the objective function

8. In the Branch and Bound method, when is a node considered 'fathomed'?

A) When it yields an integer solution B) When its LP relaxation is infeasible C) When its bound is worse than the current best integer solution D) All of the above

9. Which type of constraint is often introduced in IP to model 'either-or' situations?

A) Equality constraint B) Inequality constraint C) Big M constraint D) Surplus variable

10. The 'Big M' method in IP is used to handle:

A) Continuous variables B) Binary variables C) Disjunctive constraints (either-or) D) Non-linear objective functions

11. Which problem is a special case of the transportation problem where the objective is to minimize the total cost of shipping goods from a set of sources to a set of destinations?

A) Assignment Problem B) Transshipment Problem C) Network Flow Problem D) Standard Transportation Problem

12. In a transportation problem, what does a 'source' represent?

A) A destination for goods B) A point where goods are produced or available C) A shipping route D) The cost of transportation

13. In a transportation problem, what does a 'destination' represent?

A) A source of goods B) A point where goods are demanded or received C) A transportation link D) The quantity shipped

14. What condition must be met for a transportation problem to be 'balanced'?

A) Number of sources equals number of destinations B) Total supply equals total demand C) All transportation costs are positive D) All supplies and demands are integers

15. If total supply exceeds total demand in a transportation problem, how is it typically balanced?

A) By adding a dummy source with zero supply B) By adding a dummy destination with zero demand C) By increasing the demand at existing destinations D) By decreasing the supply at existing sources

16. If total demand exceeds total supply in a transportation problem, how is it typically balanced?

A) By adding a dummy source with zero supply B) By adding a dummy destination with zero demand C) By increasing the supply at existing sources D) By decreasing the demand at existing destinations

17. Which method is used to find an initial basic feasible solution for the transportation problem?

A) Simplex Method B) Hungarian Method C) North-West Corner Rule D) Branch and Bound Method

18. The North-West Corner Rule for finding an initial solution starts allocation from which cell?

A) The cell with the minimum transportation cost B) The top-left cell of the transportation tableau C) The bottom-right cell of the transportation tableau D) The cell with the highest supply

19. Which method is specifically designed for finding the optimal solution to the transportation problem?

A) Least Cost Method B) Vogel's Approximation Method (VAM) C) Stepping Stone Method D) North-West Corner Rule

20. The Stepping Stone Method improves an initial feasible solution by:

A) Making allocations to empty cells B) Identifying negative cost improvement cycles C) Reducing total supply D) Increasing total demand

21. What is the primary goal of Vogel's Approximation Method (VAM) for the transportation problem?

A) To minimize the number of allocations B) To obtain a better initial feasible solution with a lower cost C) To quickly find the optimal solution D) To balance supply and demand

22. In the context of the transportation problem, what does the MODI (Modified Distribution) method aim to achieve?

A) Find an initial feasible solution B) Check for optimality and find improvement paths C) Balance the supply and demand D) Reduce the number of sources

23. The MODI method is an alternative to which other method for checking optimality in transportation problems?

A) North-West Corner Rule B) Least Cost Method C) Stepping Stone Method D) Vogel's Approximation Method

24. What is the significance of the 'degeneracy' in a transportation problem?

A) It means the problem has no feasible solution B) It occurs when the number of independent basic variables is less than m + n - 1 C) It implies the optimal solution has been reached D) It indicates that all costs are zero

25. How is degeneracy typically handled in the transportation problem?

A) By adding a dummy source B) By adding a dummy destination C) By making a small allocation (epsilon) to an empty cell D) By ignoring it

26. What is a 'transshipment problem'?

A) A transportation problem with only one source B) A transportation problem where goods can be shipped through intermediate points C) A problem with only demand, no supply D) A problem where costs are non-linear

27. The Assignment Problem can be viewed as a special case of the transportation problem where:

A) Number of sources equals number of destinations B) Supply at each source is 1 and demand at each destination is 1 C) All transportation costs are zero D) The objective is to maximize profit

28. Which algorithm is commonly used to solve the Assignment Problem?

A) Simplex Method B) Hungarian Method C) Branch and Bound Method D) MODI Method

29. In integer programming, a feasible solution that satisfies the integer requirements is called:

A) An LP relaxation B) An optimal solution C) An integer feasible solution D) A bound

30. What is the 'gap' in the context of Branch and Bound for integer programming?

A) The difference between the objective function value of the LP relaxation and the best integer solution found so far B) The difference between two consecutive integer solutions C) The difference between the upper and lower bounds of a node D) The number of variables not yet branched on

31. Which of the following constraints is characteristic of integer programming and not standard linear programming?

A) x >= 0 B) Ax <= b C) xi is an integer D) x is a real number

32. Consider a fixed-charge problem in integer programming. What kind of variable is typically used to model the fixed cost?

A) Continuous variable B) Binary variable C) Integer variable greater than 1 D) Surplus variable

33. The cutting-plane method for solving integer programs aims to:

A) Generate additional constraints (cuts) to tighten the LP relaxation B) Branch the problem into smaller subproblems C) Find an initial feasible solution quickly D) Handle non-linearities

34. Gomory's cutting-plane algorithm generates cuts from:

A) The objective function coefficients B) The dual variables of the LP relaxation C) The tableau of the optimal LP relaxation solution D) The original constraints

35. What is the main challenge in solving large-scale integer programming problems?

A) The number of variables is too small B) The solution space grows exponentially, leading to long computation times C) The objective function is always linear D) The constraints are always equalities

36. In a transportation problem, if an optimal solution is not unique, it means:

A) There is an error in the calculations B) There are alternative optimal solutions C) The problem is infeasible D) The problem is unbounded

37. Which of the following is NOT a standard method for finding an initial feasible solution to the transportation problem?

A) North-West Corner Rule B) Least Cost Method C) Vogel's Approximation Method D) Stepping Stone Method

38. The Least Cost Method for initial solution allocation prioritizes:

A) The top-left cell B) The cell with the highest cost C) The cell with the minimum transportation cost among available routes D) The cell with the maximum supply

39. In the context of solving the transportation problem using MODI, what are u_i and v_j typically used for?

A) Representing supplies and demands B) Calculating opportunity costs or reduced costs C) Tracking the number of allocations D) Defining the objective function coefficients

40. Which of the following scenarios would most likely require Integer Programming?

A) Optimizing crop yields based on fertilizer amounts B) Scheduling flights where the number of flights must be a whole number C) Determining the optimal speed for a vehicle D) Allocating continuous budget across different marketing channels

41. If a transportation problem has m sources and n destinations, how many basic variables are required for a non-degenerate basic feasible solution?

A) m + n B) m * n C) m + n - 1 D) m - 1 + n - 1

42. What is the 'penalty cost' in Vogel's Approximation Method (VAM)?

A) The cost of the least expensive route B) The difference between the two lowest costs in a row or column C) The cost associated with not meeting demand D) The cost of the most expensive route

43. When is the Branch and Bound method guaranteed to find the optimal integer solution?

A) If the LP relaxation is always integer B) If all branches are explored or fathomed C) If the problem has only binary variables D) If the feasible region is convex

44. A 'knapsack problem' is a type of integer programming problem that involves:

A) Assigning tasks to workers B) Selecting items with different values and weights to fit into a limited capacity C) Minimizing shipping costs from factories to warehouses D) Maximizing production output with limited resources

45. The transportation problem assumes that:

A) Costs are non-linear B) Shipments can be made in fractions C) Each route has a fixed cost regardless of quantity D) There are intermediate transshipment points

46. Which of the following is a valid constraint for a binary integer programming problem?

A) 0 <= x <= 1 B) x is an integer C) x = 0 or x = 1 D) x >= 0

47. In integer programming, if the optimal solution to the LP relaxation is fractional, what action is typically taken in the Branch and Bound method?

A) The fractional solution is rounded up B) The fractional solution is rounded down C) A new branch is created based on the fractional variable D) The LP relaxation is discarded

48. The transportation problem formulation is a specific application of which broader class of optimization problems?

A) Non-linear Programming B) Integer Programming C) Network Flow Problems D) Dynamic Programming

Integer programming, transportation problem - Online Test

Test Results