Transportation and Assignment Problems - One Line Questions

1. What is the 'cost matrix' in the context of assignment problems? — A matrix where rows represent agents and columns represent tasks, with entries being the cost or profit of assigning an agent to a task.
2. When applying the Hungarian Method to a maximization problem, if the maximum profit is P, what is the resulting matrix for minimization? — A matrix where each element is P - original_profit.
3. In the context of the Stepping Stone Method, what is a 'closed loop'? — A path that starts and ends at the same allocated cell, using only allocated and unallocated cells.
4. What is an 'assignment problem'? — A special case of the transportation problem where supply and demand at each point are equal to 1.
5. What is a 'degenerate solution' in a transportation problem? — A solution where the number of allocated cells is less than (m + n - 1), where m is the number of sources and n is the number of destinations.
6. The assignment problem can be viewed as a special case of the transportation problem where: — Supply from each source is 1 and demand at each destination is 1.
7. For a maximization assignment problem, how is it typically converted to a minimization problem suitable for the Hungarian Method? — By subtracting each element from the maximum element in the entire matrix.
8. After obtaining an initial basic feasible solution, how is optimality checked in a transportation problem? — By using the Stepping Stone Method or MODI (Modified Distribution) Method.
9. How is degeneracy typically resolved in a transportation problem? — By making a small positive allocation (epsilon, ε) to an empty cell in a way that does not violate feasibility.
10. An unallocated cell (i, j) in a transportation problem is checked for optimality using the MODI method by calculating: — (u_i + v_j) - c_ij
11. Which of the following is a key assumption in the standard transportation and assignment problems? — All supplies and demands are non-negative.
12. What is the first step in the Hungarian Method for a minimization problem? — Subtracting the smallest element from each row and then from each column.
13. What is the relationship between the number of allocations in a basic feasible solution of a transportation problem and the number of sources (m) and destinations (n)? — Exactly m + n - 1
14. The Stepping Stone Method is used to: — Check for optimality and improve the current solution.
15. The Hungarian Method is an algorithm for: — Solving the assignment problem.
16. After performing row and column reductions in the Hungarian Method, the next step typically involves: — Making allocations to zero entries, aiming for one assignment per row and column.
17. The MODI method uses dual variables (u_i and v_j) to calculate: — Improvement indices (or opportunity costs) for unallocated cells.
18. If an optimal assignment cannot be made with the current zeros (i.e., fewer than n assignments are possible), what is the subsequent step in the Hungarian Method? — Draw the minimum number of lines to cover all zeros.
19. The MODI method is an alternative to the Stepping Stone Method because it: — Is conceptually simpler and computationally faster.
20. Vogel's Approximation Method (VAM) is generally preferred for finding an initial solution because it: — Often yields a solution closer to the optimal solution.
21. What is the main advantage of using the MODI method over the Stepping Stone method for transportation problems? — It requires fewer iterations and is computationally more efficient.
22. If all improvement indices are non-negative (for minimization problems), what can be concluded about the current solution? — It is optimal.
23. If a transportation problem has m sources and n destinations, and it is balanced, how many basic variables are there in any basic feasible solution? — m + n - 1
24. What is the minimum number of allocations required to represent a feasible solution in an assignment problem with n agents and n tasks? — n
25. Which method is specifically designed to solve the assignment problem? — Hungarian Method
26. Which of the following is NOT a method for finding an initial feasible solution for a transportation problem? — Hungarian Method
27. The concept of 'loops' is fundamental to which methods for solving transportation problems? — Stepping Stone Method and MODI Method
28. Which method is commonly used to find an initial basic feasible solution for a transportation problem? — North-West Corner Rule
29. The Least Cost Method (or Matrix Minimum Method) aims to find an initial solution by: — Prioritizing the cell with the lowest per-unit shipping cost.
30. What does 'demand' represent in the context of a transportation problem? — The quantity of goods required at a particular destination.
31. Which of the following describes the 'Rim' in a transportation tableau? — The cells representing supply and demand values.
32. In a transportation problem, what does 'supply' refer to? — The capacity of a particular source to ship goods.
33. The 'Stepping Stone' in the Stepping Stone Method refers to: — An unallocated cell that is part of a closed loop used to evaluate cost improvement.
34. In the Hungarian Method, if we have a 4x4 cost matrix and after line covering, we find 3 lines are needed, what is the implication? — The matrix needs further adjustment by modifying the uncovered elements to find more zeros.
35. If the total supply is greater than the total demand in a transportation problem, how is it typically handled? — A dummy destination with zero cost is introduced to absorb the excess supply.
36. If the total demand is greater than the total supply in a transportation problem, how is it typically handled? — A dummy source with zero cost is introduced to meet the excess demand.
37. In an assignment problem, if the number of agents is not equal to the number of tasks, what is the usual procedure? — Dummy agents or dummy tasks are added with zero cost/profit.
38. If the number of lines is less than n, what is done in the Hungarian Method? — The smallest uncovered element is subtracted from all uncovered elements, and added to elements at the intersection of two lines.
39. If, during the Hungarian Method, we find that the minimum number of lines required to cover all zeros is less than n, it implies: — The current zeros are insufficient for an optimal assignment, and the matrix needs adjustment.
40. When covering zeros with minimum lines in the Hungarian Method, if the number of lines equals the number of agents/tasks (n), what does this indicate? — An optimal assignment is possible with the current zeros.
41. What is the significance of 'improvement indices' or 'opportunity costs' in the Stepping Stone/MODI method? — They represent the change in total cost if one unit is shifted to an unallocated cell.
42. What is the core idea behind VAM for finding an initial solution? — To calculate penalties for not using a row or column and allocate to the lowest cost cell in the row/column with the highest penalty.
43. In the context of the Hungarian Algorithm, what does 'covering all zeros with minimum lines' attempt to achieve? — To determine if an optimal assignment can be made using the current zeros.
44. What is the primary objective of a transportation problem? — To minimize the total cost of shipping goods from various sources to different destinations.
45. What is the objective of the Northwest Corner Rule in finding an initial solution? — To allocate as much as possible to the cell in the top-left corner and proceed systematically.
46. What is the primary objective of an assignment problem? — To minimize the total cost or maximize the total profit of assigning tasks to agents.
47. What is the primary difference between a transportation problem and a general linear programming problem? — Transportation problems have a specific structure (e.g., constraints for supply and demand) which allows for specialized solution methods.
48. When using the MODI method, the values of u_i and v_j are determined such that: — u_i + v_j = c_ij for all allocated cells.
49. What is a 'balanced' transportation problem? — Where the total supply equals the total demand.
All One Line Questions
E-Book Transportation and Assignment Problems Online Test Transportation and Assignment Problems Question Bank Transportation and Assignment Problems