Integer programming, transportation problem - Question Bank

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. 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
21. Which algorithm is commonly used to solve the Assignment Problem?
A) Simplex Method
B) Hungarian Method
C) Branch and Bound Method
D) MODI Method
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. 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
29. 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
30. 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
31. 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
32. 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
33. 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
34. 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
35. 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
36. 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
37. 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
38. 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
39. 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
40. 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
41. 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
42. 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
43. 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
44. 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
45. 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
46. 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
47. 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
48. 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
All Question Banks
E-Book Integer programming, transportation problem One Line Questions Integer programming, transportation problem Online Test Integer programming, transportation problem