GATE Mathematics Linear Programming Syllabus

In the MODI method, how are the dual variables $u_i$ and $v_j$ determined?

For every basic (occupied) cell, set $u_i + v_j = c_{ij}$. Assign one variable (usually $u_1 = 0$) and solve the system for the rest.

In the MODI method, what is the optimality criterion for empty (non-basic) cells?

Compute $d_{ij} = c_{ij} - (u_i + v_j)$ for each empty cell. The current solution is optimal if all $d_{ij} \geq 0$. A negative value indicates improvement is possible by bringing that cell into the basis.

What is the assignment problem?

A special transportation problem in which $n$ jobs (tasks) must be assigned to $n$ agents (machines/persons) on a one-to-one basis so as to minimize total cost (or time), with each agent doing exactly one job and each job done by exactly one agent.

Why is the assignment problem considered a special case of the transportation problem?

Because it is a balanced transportation problem where the cost matrix is square ($n \times n$) and every supply and demand equals 1, so each $x_{ij}$ is either 0 or 1.

What is the Hungarian method used for?

The Hungarian method is an efficient combinatorial algorithm for solving the assignment problem to find the optimal one-to-one assignment that minimizes total cost (or maximizes profit after conversion).

Who developed the Hungarian method and on whose work is it based?

It was developed by Harold W. Kuhn (1955), who named it the 'Hungarian method' because it was based on the earlier work of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry.

State the four main steps of the Hungarian method for a minimization assignment problem.

1) Row reduction: subtract each row's minimum from that row. 2) Column reduction: subtract each column's minimum from that column. 3) Cover all zeros with the minimum number of horizontal/vertical lines. 4) If lines = $n$, optimal assignment exists; otherwise adjust the matrix and repeat.

In the Hungarian method, what is the optimality test based on covering zeros?

An optimal assignment is possible when the minimum number of lines needed to cover all zeros equals the order $n$ of the matrix. If the number of lines is less than $n$, the matrix must be further reduced.

In the Hungarian method, how is the cost matrix adjusted when the number of covering lines is less than $n$?

Find the smallest uncovered element $k$. Subtract $k$ from every uncovered element, add $k$ to every element at the intersection of two lines, and leave singly-covered elements unchanged. Then re-test optimality.

How do you make the final optimal assignment from a reduced Hungarian matrix?

Examine rows/columns having a single zero, assign that zero (mark it) and cross out the other zeros in its row and column. Continue until each row and each column has exactly one assigned zero.

What is the prerequisite balance condition for applying the Hungarian method?

The cost matrix must be square ($n \times n$); the number of jobs must equal the number of agents. If unbalanced, add a dummy row or column with zero costs to make it square.

How is a maximization assignment problem (e.g., maximizing profit) solved with the Hungarian method?

Convert it to a minimization problem first—either by subtracting every element from the largest element of the matrix (creating an opportunity-loss/regret matrix) or by negating all entries—then apply the standard Hungarian minimization steps.

How is a prohibited (infeasible) assignment handled in the Hungarian method?

Assign a very large cost $M$ (Big-M) to the prohibited cell so that the algorithm naturally avoids selecting it in the optimal assignment.

For an $n \times n$ assignment problem, how many feasible assignments are theoretically possible, and how many basic variables does the equivalent transportation problem have?

There are $n!$ possible complete assignments. As a transportation problem it has $m + n - 1 = n + n - 1 = 2n - 1$ basic cells, of which only $n$ carry a value of 1; the rest are degenerate (zero).

What is the computational time complexity of the Hungarian method?

The Hungarian algorithm runs in polynomial time, $O(n^{3})$, for an $n \times n$ assignment problem.

Why is the Hungarian method preferred over solving the assignment problem with the general simplex/transportation method?

Because the assignment problem is highly degenerate (many zero allocations), the simplex/transportation approach is inefficient; the Hungarian method exploits the special 0–1 structure to solve it directly and far more efficiently in $O(n^{3})$.

In a transportation tableau, what defines an 'occupied' (basic) cell versus an 'empty' (non-basic) cell?

An occupied cell has a positive allocation $x_{ij} > 0$ and is part of the basic feasible solution; an empty (non-basic) cell has $x_{ij} = 0$ and is not in the basis.

What is a 'loop' (closed path) in the Stepping Stone / MODI method?

A closed circuit of horizontal and vertical moves connecting an empty cell back to itself through occupied cells, turning only at occupied cells (and the starting empty cell), used to evaluate the cost change of reallocating units.

How is the net cost change of an empty cell evaluated in the Stepping Stone method?

Trace the closed loop from the empty cell, alternately adding ($+$) and subtracting ($-$) the unit costs at the corner cells starting with $+$ at the empty cell. The algebraic sum gives the cell's net change; a negative sum means reallocation reduces total cost.

Compare the Least Cost Method and Vogel's Approximation Method in terms of allocation criterion.

The Least Cost Method allocates to the single cheapest cell currently available, considering only the absolute lowest cost. VAM allocates based on penalty (opportunity cost of not using the cheapest cell), giving it a more forward-looking, near-optimal result.

Compare the North-West Corner Rule and the Least Cost Method in terms of cost awareness.

The North-West Corner Rule ignores costs entirely and allocates by position, while the Least Cost Method explicitly uses unit costs by always filling the lowest-cost available cell first, generally producing a cheaper initial solution.

What is the row penalty for the row with costs $\{8, 3, 11, 5\}$ in Vogel's Approximation Method?

The two smallest costs are $3$ and $5$, so the penalty is $5 - 3 = 2$.

In the Hungarian method, after row and column reduction, what does a zero entry $c'_{ij} = 0$ signify?

A zero indicates a potentially optimal (zero opportunity-cost) assignment of agent $i$ to job $j$; the algorithm seeks an independent set of $n$ such zeros, one in each row and column.

If total supply $= 200$ and total demand $= 170$ in a transportation problem, what balancing step is required?

Add a dummy destination (column) with demand $200 - 170 = 30$ and zero unit costs, so that total supply equals total demand and the problem becomes balanced.

What is meant by 'opportunity cost' in the context of Vogel's penalties and the Hungarian method?

Opportunity cost is the penalty (extra cost) incurred by not choosing the cheapest available option. VAM uses the row/column penalty as opportunity cost; the Hungarian method's row/column reductions create an opportunity-cost (regret) matrix whose zeros mark cost-free choices.

Does the choice of IBFS method (NWCR, Least Cost, or VAM) affect the final optimal transportation cost?

No. All valid IBFS methods lead to the same optimal solution after MODI/Stepping Stone optimization; they only differ in how close the starting solution is to the optimum and hence in the number of iterations needed.

What characterizes the allocations produced by the North-West Corner Rule structurally?

They form a staircase pattern from the top-left to the bottom-right of the tableau, since allocation always proceeds rightward and downward.

In an assignment problem, why is each $x_{ij}$ restricted to the values 0 or 1?

Because each agent is assigned to exactly one job and each job to exactly one agent; $x_{ij} = 1$ means agent $i$ is assigned to job $j$, and $x_{ij} = 0$ means it is not. The constraints $\sum_j x_{ij} = 1$ and $\sum_i x_{ij} = 1$ enforce this.

State the objective function and constraints of the assignment problem.

Minimize $Z = \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}\,x_{ij}$ subject to $\sum_{j=1}^{n} x_{ij} = 1$ for all $i$, $\sum_{i=1}^{n} x_{ij} = 1$ for all $j$, and $x_{ij} \in \{0,1\}$.

Why does row and column reduction in the Hungarian method not change the optimal assignment?

Subtracting a constant from an entire row or column reduces every complete assignment's total cost by the same constant, so the assignment that was optimal remains optimal; only the absolute cost shifts, not the relative ranking.

Summarize the key contrast between the transportation problem and the assignment problem.

The transportation problem distributes divisible quantities from $m$ sources to $n$ destinations (any $x_{ij} \geq 0$, generally $m \neq n$), solved via NWCR/Least Cost/VAM then MODI. The assignment problem is a special $n \times n$ case with $x_{ij} \in \{0,1\}$ and unit supplies/demands, solved efficiently by the Hungarian method.