Lesson 9: Transportation Optimality: The MODI Method¶
9.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Compute the multipliers \(u_i\) and \(v_j\) from the basic cells.
- Compute opportunity costs \(d_{ij} = c_{ij} - u_i - v_j\) and apply the optimality test.
- Trace a closed loop and perform the stepping-stone reallocation.
- Resolve degeneracy by inserting an \(\epsilon\) allocation.
- Detect alternate optima and interpret the multipliers economically.
9.2 The MODI Method¶
MODI = MOdified DIstribution, also called the u–v method. It is the transportation problem's version of the simplex optimality test, exploiting the special structure to avoid a full tableau.
The multipliers¶
For each basic cell \((i,j)\) define multipliers satisfying
There are \(m+n\) unknowns but only \(m+n-1\) basic cells, so one multiplier is free. Set \(u_1 = 0\) by convention, then solve the rest by substitution.
Why this works. \(u_i\) and \(v_j\) are the dual variables of the transportation LP (L07): \(u_i\) is the shadow price of supply at source \(i\), and \(v_j\) the shadow price of demand at destination \(j\). The redundant constraint (L08 §1.1) is exactly why one dual variable is free.
The optimality test¶
For each non-basic cell compute the opportunity cost (reduced cost)
Interpretation. \(d_{ij}\) is the net change in total cost per unit shipped through the currently unused route \((i,j)\). If \(d_{ij} < 0\), using that route reduces cost.
Entering cell. Choose the most negative \(d_{ij}\).
The stepping-stone loop¶
Once an entering cell is chosen, we must adjust the allocations to keep every supply and demand satisfied. This is done along a closed loop.
Definition (closed loop). A cycle starting and ending at the entering cell, turning only at basic cells, moving alternately horizontally and vertically, with exactly one turn per cell visited.
Theorem. For any non-basic cell there exists exactly one such loop. (This is the graph-theory fact that adding one edge to a spanning tree creates exactly one cycle — the basic cells form a spanning tree of the bipartite supply–demand graph.)
The reallocation.
1. Label the entering cell '+', then alternate '-', '+', '-', ... around the loop
2. theta = the SMALLEST allocation among the '-' cells
3. Add theta to every '+' cell; subtract theta from every '-' cell
4. The '-' cell that reaches zero LEAVES the basis
Cost change. \(\Delta Z = \theta \times d_{ij}\), which is negative — an improvement.
The complete algorithm¶
1. Obtain an initial BFS (VAM recommended -- L08)
2. Check: exactly m+n-1 basic cells? If fewer, insert epsilon (Section 3)
3. Compute u_i, v_j from u_i + v_j = c_ij over basic cells, with u_1 = 0
4. Compute d_ij = c_ij - u_i - v_j for all non-basic cells
5. If all d_ij >= 0 -> STOP, OPTIMAL
6. Choose the most negative d_ij as the entering cell
7. Trace its closed loop; determine theta; reallocate
8. Go to 3
9.3 Worked Example — Complete MODI Solution¶
The problem (continued from L08 §4).
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | Supply | |
|---|---|---|---|---|---|
| \(S_1\) | 19 | 30 | 50 | 10 | 7 |
| \(S_2\) | 70 | 30 | 40 | 60 | 9 |
| \(S_3\) | 40 | 8 | 70 | 20 | 18 |
| Demand | 5 | 8 | 7 | 14 | 34 |
VAM starting solution (L08, cost 779):
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | |
|---|---|---|---|---|
| \(S_1\) | 5 | – | – | 2 |
| \(S_2\) | – | – | 7 | 2 |
| \(S_3\) | – | 8 | – | 10 |
Basic cells: \((1,1), (1,4), (2,3), (2,4), (3,2), (3,4)\) — 6 = \(m+n-1\) ✓.
Iteration 1¶
Step 1 — compute the multipliers. Set \(u_1 = 0\) and use \(u_i + v_j = c_{ij}\) on basic cells.
| Basic cell | Equation | Deduce |
|---|---|---|
| \((1,1)\) | \(u_1 + v_1 = 19\) | \(v_1 = 19\) |
| \((1,4)\) | \(u_1 + v_4 = 10\) | \(v_4 = 10\) |
| \((2,4)\) | \(u_2 + v_4 = 60\) | \(u_2 = 50\) |
| \((2,3)\) | \(u_2 + v_3 = 40\) | \(v_3 = -10\) |
| \((3,4)\) | \(u_3 + v_4 = 20\) | \(u_3 = 10\) |
| \((3,2)\) | \(u_3 + v_2 = 8\) | \(v_2 = -2\) |
(Negative multipliers are perfectly normal — they are dual variables of equality constraints, hence unrestricted in sign.)
Step 2 — opportunity costs for the six non-basic cells.
| Cell | \(c_{ij}\) | \(u_i\) | \(v_j\) | \(d_{ij} = c_{ij}-u_i-v_j\) |
|---|---|---|---|---|
| \((1,2)\) | 30 | 0 | \(-2\) | \(30 - 0 + 2 = 32\) |
| \((1,3)\) | 50 | 0 | \(-10\) | \(50 - 0 + 10 = 60\) |
| \((2,1)\) | 70 | 50 | 19 | \(70 - 50 - 19 = 1\) |
| \((2,2)\) | 30 | 50 | \(-2\) | \(30 - 50 + 2 = \mathbf{-18}\) ← |
| \((3,1)\) | 40 | 10 | 19 | \(40 - 10 - 19 = 11\) |
| \((3,3)\) | 70 | 10 | \(-10\) | \(70 - 10 + 10 = 70\) |
\(d_{22} = -18 < 0\) ⟹ NOT OPTIMAL. Entering cell: \((2,2)\).
Step 3 — trace the closed loop from \((2,2)\).
Starting at \((2,2)\), move along row 2 to a basic cell, then along that column, and so on:
Verify the loop. \((2,2)\to(2,4)\) is horizontal (same row 2); \((2,4)\to(3,4)\) is vertical (same column 4); \((3,4)\to(3,2)\) is horizontal (same row 3); \((3,2)\to(2,2)\) is vertical (same column 2) ✓. All turning cells \((2,4), (3,4), (3,2)\) are basic ✓.
Step 4 — determine \(\theta\).
Step 5 — reallocate.
New allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | |
|---|---|---|---|---|
| \(S_1\) | 5 | – | – | 2 |
| \(S_2\) | – | 2 | 7 | – |
| \(S_3\) | – | 6 | – | 12 |
Cost change. \(\Delta Z = \theta\,d_{22} = 2\times(-18) = -36\).
Direct verification.
Iteration 2¶
New basic cells: \((1,1), (1,4), (2,2), (2,3), (3,2), (3,4)\) — 6 ✓.
Multipliers (\(u_1 = 0\)):
| Basic cell | Equation | Deduce |
|---|---|---|
| \((1,1)\) | \(u_1+v_1 = 19\) | \(v_1 = 19\) |
| \((1,4)\) | \(u_1+v_4 = 10\) | \(v_4 = 10\) |
| \((3,4)\) | \(u_3+v_4 = 20\) | \(u_3 = 10\) |
| \((3,2)\) | \(u_3+v_2 = 8\) | \(v_2 = -2\) |
| \((2,2)\) | \(u_2+v_2 = 30\) | \(u_2 = 32\) |
| \((2,3)\) | \(u_2+v_3 = 40\) | \(v_3 = 8\) |
Opportunity costs.
| Cell | \(d_{ij}\) |
|---|---|
| \((1,2)\) | \(30 - 0 + 2 = 32\) |
| \((1,3)\) | \(50 - 0 - 8 = 42\) |
| \((2,1)\) | \(70 - 32 - 19 = 19\) |
| \((2,4)\) | \(60 - 32 - 10 = 18\) |
| \((3,1)\) | \(40 - 10 - 19 = 11\) |
| \((3,3)\) | \(70 - 10 - 8 = 52\) |
All \(d_{ij} > 0\) ⟹ OPTIMAL.
The optimal shipping plan.
| Route | Units | Cost/unit | Total |
|---|---|---|---|
| \(S_1 \to D_1\) | 5 | 19 | 95 |
| \(S_1 \to D_4\) | 2 | 10 | 20 |
| \(S_2 \to D_2\) | 2 | 30 | 60 |
| \(S_2 \to D_3\) | 7 | 40 | 280 |
| \(S_3 \to D_2\) | 6 | 8 | 48 |
| \(S_3 \to D_4\) | 12 | 20 | 240 |
| Total | ₹743 |
Summary of the solution path. VAM gave 779; one MODI iteration reached the optimum 743 — a 4.8 % improvement. NWCM's 1015 would have needed many more iterations.
Economic reading of the multipliers¶
Since \(u_1 = 0\) is an arbitrary normalisation, only differences are meaningful.
- \(u_2 - u_1 = 32\): an extra unit of capacity at \(S_2\) is worth ₹32 more than at \(S_1\) — i.e. \(S_2\) is the most expensive source to ship from, so relieving it saves the most.
- \(v_2 = -2\): reducing demand at \(D_2\) by one unit increases cost by 2? No — read it correctly: \(v_j\) is the marginal cost of supplying one more unit to \(D_j\). A negative \(v_2\) relative to \(u_1=0\) simply reflects the normalisation; the meaningful statement is \(u_3 + v_2 = 8\) — supplying \(D_2\) from \(S_3\) costs 8, the cheapest route in the table.
- Total check: \(\sum_i a_iu_i + \sum_j b_jv_j = 7(0)+9(32)+18(10) + 5(19)+8(-2)+7(8)+14(10)\) \(= 288+180 + 95-16+56+140 = 468 + 275 = 743 = Z^{*}\) ✓ — strong duality (L07), confirmed.
9.4 Handling Degeneracy¶
When it occurs. A BFS has fewer than \(m+n-1\) basic cells. This happens when a row and a column are exhausted simultaneously during the initial allocation, or when two "−" cells tie for \(\theta\) during a MODI iteration.
Why it is a problem. With fewer than \(m+n-1\) basic cells, the equations \(u_i+v_j = c_{ij}\) are underdetermined — some multipliers cannot be found, and the optimality test cannot be applied.
The fix.
1. Choose an EMPTY cell that does NOT form a closed loop with the existing basic cells
2. Allocate an infinitesimal amount, epsilon (treat it as 0 for cost, as basic for the algorithm)
3. Proceed normally
4. At the end, discard epsilon
Choosing wisely. Prefer a low-cost empty cell — it is more likely to remain basic and it keeps the arithmetic simple. Never choose a cell that closes a loop, because then the \(u,v\) system becomes inconsistent rather than merely underdetermined.
9.5 Solved Problems¶
Problem 1 — MODI verification of a VAM solution¶
Verify by MODI that the VAM solution to the L08 Problem 3 data is optimal.
Costs, supplies \((20,30,25)\), demands \((15,25,35)\):
| \(D_1\) | \(D_2\) | \(D_3\) | |
|---|---|---|---|
| \(S_1\) | 8 | 6 | 10 |
| \(S_2\) | 9 | 12 | 13 |
| \(S_3\) | 14 | 9 | 16 |
VAM gave: \((1,3)=20\), \((2,1)=15\), \((2,3)=15\), \((3,2)=25\), with \(Z = 755\).
Solution.
Basic cells: 4, but \(m+n-1 = 5\) ⟹ DEGENERATE.
Insert \(\epsilon\). Choose a low-cost empty cell forming no loop — take \((1,1)\) with cost 8.
Basic cells: \((1,1)_\epsilon, (1,3), (2,1), (2,3), (3,2)\) — 5 ✓.
Multipliers (\(u_1 = 0\)):
| Cell | Equation | Deduce |
|---|---|---|
| \((1,1)\) | \(u_1+v_1 = 8\) | \(v_1 = 8\) |
| \((1,3)\) | \(u_1+v_3 = 10\) | \(v_3 = 10\) |
| \((2,1)\) | \(u_2+v_1 = 9\) | \(u_2 = 1\) |
| \((2,3)\) | \(u_2+v_3 = 13\) | check: \(1+10 = 11 \ne 13\) ✗ |
Inconsistency! The choice of \((1,1)\) closed a loop: \((1,1)\to(1,3)\to(2,3)\to(2,1)\to(1,1)\) is a valid cycle among basic cells, which is not allowed.
Retry with \((3,3)\), cost 16. Basic cells \((1,3), (2,1), (2,3), (3,2), (3,3)_\epsilon\).
| Cell | Equation | Deduce |
|---|---|---|
| \((1,3)\) | \(u_1+v_3 = 10\) | \(v_3 = 10\) |
| \((2,3)\) | \(u_2+v_3 = 13\) | \(u_2 = 3\) |
| \((2,1)\) | \(u_2+v_1 = 9\) | \(v_1 = 6\) |
| \((3,3)\) | \(u_3+v_3 = 16\) | \(u_3 = 6\) |
| \((3,2)\) | \(u_3+v_2 = 9\) | \(v_2 = 3\) |
Opportunity costs.
| Cell | \(d_{ij} = c_{ij}-u_i-v_j\) |
|---|---|
| \((1,1)\) | \(8 - 0 - 6 = 2\) |
| \((1,2)\) | \(6 - 0 - 3 = 3\) |
| \((2,2)\) | \(12 - 3 - 3 = 6\) |
| \((3,1)\) | \(14 - 6 - 6 = 2\) |
All \(d_{ij} > 0\) ⟹ OPTIMAL ✓
Duality check.
The lesson about \(\epsilon\) placement. The first attempt failed because \((1,1)\) formed a loop with existing basic cells. Always check for a loop before placing \(\epsilon\). A quick test: if you can trace an alternating horizontal/vertical cycle through the candidate and the existing basic cells, choose a different cell.
Problem 2 — A full MODI iteration on an NWCM start¶
Improve the NWCM solution to the §2 example (cost 1015) by one MODI iteration.
Solution.
NWCM solution (L08 §4.1): \((1,1)=5\), \((1,2)=2\), \((2,2)=6\), \((2,3)=3\), \((3,3)=4\), \((3,4)=14\).
Multipliers (\(u_1 = 0\)):
| Cell | Equation | Deduce |
|---|---|---|
| \((1,1)\) | \(u_1+v_1 = 19\) | \(v_1 = 19\) |
| \((1,2)\) | \(u_1+v_2 = 30\) | \(v_2 = 30\) |
| \((2,2)\) | \(u_2+v_2 = 30\) | \(u_2 = 0\) |
| \((2,3)\) | \(u_2+v_3 = 40\) | \(v_3 = 40\) |
| \((3,3)\) | \(u_3+v_3 = 70\) | \(u_3 = 30\) |
| \((3,4)\) | \(u_3+v_4 = 20\) | \(v_4 = -10\) |
Opportunity costs.
| Cell | \(d_{ij}\) |
|---|---|
| \((1,3)\) | \(50 - 0 - 40 = 10\) |
| \((1,4)\) | \(10 - 0 + 10 = \mathbf{20}\) |
| \((2,1)\) | \(70 - 0 - 19 = 51\) |
| \((2,4)\) | \(60 - 0 + 10 = 70\) |
| \((3,1)\) | \(40 - 30 - 19 = -9\) |
| \((3,2)\) | \(8 - 30 - 30 = \mathbf{-52}\) ← |
Most negative is \(d_{32} = -52\). Entering cell \((3,2)\).
Loop from \((3,2)\).
Check: \((3,2)\to(2,2)\) vertical (column 2); \((2,2)\to(2,3)\) horizontal (row 2); \((2,3)\to(3,3)\) vertical (column 3); \((3,3)\to(3,2)\) horizontal (row 3) ✓.
\(\theta\). Minus cells are \((2,2) = 6\) and \((3,3) = 4\). So \(\theta = \mathbf{4}\).
Reallocate.
New allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | |
|---|---|---|---|---|
| \(S_1\) | 5 | 2 | – | – |
| \(S_2\) | – | 2 | 7 | – |
| \(S_3\) | – | 4 | – | 14 |
New cost.
Verification.
Progress so far. \(1015 \to 807\) in one iteration. Still above the optimum of 743, so more iterations are needed — illustrating exactly why VAM (which started at 779 and needed only one iteration) is worth the extra setup effort.
Problem 3 — Detecting alternate optima¶
A final MODI tableau has \(d_{ij} \ge 0\) for all non-basic cells, with \(d_{23} = 0\) exactly. Interpret and find the second optimum.
Solution.
Diagnosis.
Why. Shipping through route \((2,3)\) changes the cost by \(\theta\times d_{23} = \theta\times 0 = 0\) — a different plan at exactly the same cost.
Finding the second optimum.
- Trace the closed loop from \((2,3)\).
- Determine \(\theta\) from the "−" cells.
- Reallocate.
- The new allocation has the same total cost.
Describing all optima. With optimal plans \(X^{(1)}\) and \(X^{(2)}\), every convex combination
is also optimal — and every one satisfies all supply and demand constraints, since those are linear.
A practical caution. For \(\lambda\) strictly between 0 and 1, \(X(\lambda)\) may have fractional allocations even though \(X^{(1)}\) and \(X^{(2)}\) are integral. If shipments must be whole units, use one of the extreme plans, which total unimodularity (L08) guarantees are integral.
Why this matters commercially. Two shipping plans at identical cost let the manager choose on grounds the model never captured: carrier reliability, existing relationships, route congestion, or simply keeping a warehouse's staff employed. Always search for and report \(d_{ij} = 0\) cells — free flexibility is valuable.
Problem 4 — Resolving degeneracy during an iteration¶
During a MODI iteration, the "−" cells have allocations 6, 6 and 9. Explain what happens and how to proceed.
Solution.
But TWO cells reach zero simultaneously.
The problem. If both leave the basis, the number of basic cells drops from \(m+n-1\) to \(m+n-2\) — degenerate, and the multipliers become undetermined at the next iteration.
The fix.
1. Remove only ONE of the tied cells from the basis (choose either -- convention: the higher cost)
2. Keep the OTHER in the basis with allocation epsilon (i.e. 0, but flagged as basic)
3. Continue normally
Worked illustration. Suppose the tied cells are \((1,3)\) with \(c = 25\) and \((2,4)\) with \(c = 18\).
- Remove \((1,3)\) (the higher cost — it is less likely to be wanted later).
- Keep \((2,4)\) basic with allocation \(\epsilon = 0\).
The basis now has \(m+n-1\) cells again ✓, the multipliers are computable, and the algorithm proceeds.
Does \(\epsilon\) affect the cost? No — \(\epsilon\times c_{24} = 0\). It is purely a bookkeeping device to keep the basis a spanning tree.
When does \(\epsilon\) disappear? Either it stays basic at 0 until the end (then discard it), or a later iteration gives it a genuine positive value.
Why this is not a numerical fudge. In the underlying simplex method this is exactly a degenerate basic variable (L05, Problem 4) — a basic variable at value zero. The transportation tableau simply makes it visible. Degeneracy is a property of the problem, not an error.
Frequency note. Degeneracy is very common in transportation problems, because any coincidence of partial sums of supplies and demands triggers it. Expect it, handle it routinely.
Problem 5 — A complete real-world transportation study¶
A cement company has plants at Chennai (500 t), Kolkata (700 t) and Mumbai (600 t), supplying Bengaluru (400), Delhi (450), Hyderabad (350) and Pune (600 t). Freight costs (₹/tonne):
| Bengaluru | Delhi | Hyderabad | Pune | |
|---|---|---|---|---|
| Chennai | 300 | 800 | 250 | 600 |
| Kolkata | 900 | 500 | 700 | 850 |
| Mumbai | 750 | 600 | 550 | 200 |
Solve and advise management.
Solution.
Step 1 — balance.
Balanced ✓. Basic cells needed: \(3+4-1 = 5\).
Step 2 — VAM.
Round 1 penalties:
| Line | Two smallest | Penalty |
|---|---|---|
| Chennai | 250, 300 | 50 |
| Kolkata | 500, 700 | 200 |
| Mumbai | 200, 550 | 350 |
| Bengaluru | 300, 750 | 450 |
| Delhi | 500, 600 | 100 |
| Hyderabad | 250, 550 | 300 |
| Pune | 200, 600 | 400 |
Bengaluru wins (450). Cheapest is Chennai at 300. Allocate \(\min(500,400) = 400\). Bengaluru done; Chennai has 100 left.
Round 2: Mumbai's penalty is \(550-200 = 350\); Pune's is \(600-200 = 400\); Hyderabad's is \(550-250 = 300\); Delhi's is \(600-500 = 100\).
Pune wins (400). Cheapest is Mumbai at 200. Allocate \(\min(600,600) = 600\). Pune done; Mumbai has 0 left — Mumbai is exhausted too.
Round 3: Remaining rows Chennai(100), Kolkata(700); columns Delhi(450), Hyderabad(350).
| Line | Penalty |
|---|---|
| Chennai | \(800-250 = 550\) ← |
| Kolkata | \(700-500 = 200\) |
| Delhi | \(800-500 = 300\) |
| Hyderabad | \(700-250 = 450\) |
Chennai wins. Cheapest is Hyderabad at 250. Allocate \(\min(100,350) = 100\). Chennai done; Hyderabad needs 250 more.
Round 4: Only Kolkata (700) remains, for Delhi (450) and Hyderabad (250). Allocate Kolkata→Delhi 450 and Kolkata→Hyderabad 250.
The plan.
| Bengaluru | Delhi | Hyderabad | Pune | |
|---|---|---|---|---|
| Chennai | 400 | – | 100 | – |
| Kolkata | – | 450 | 250 | – |
| Mumbai | – | – | – | 600 |
Cost.
Step 3 — MODI check. Basic cells: 5 ✓. With \(u_{\text{Ch}} = 0\):
Mumbai connects only through Pune, whose column has no other basic cell — so \(u_{\text{Mum}}\) and \(v_{\text{Pune}}\) are linked but not pinned to the rest. This signals that the basis graph is disconnected, i.e. the solution is degenerate in structure. Insert \(\epsilon\) at a low-cost empty cell joining Mumbai to the rest — say \((\text{Mumbai}, \text{Hyderabad})\), cost 550:
Opportunity costs.
| Cell | \(d_{ij}\) |
|---|---|
| (Ch, Del) | \(800 - 0 - 50 = 750\) |
| (Ch, Pune) | \(600 - 0 + 100 = 700\) |
| (Kol, Ben) | \(900 - 450 - 300 = 150\) |
| (Kol, Pune) | \(850 - 450 + 100 = 500\) |
| (Mum, Ben) | \(750 - 300 - 300 = 150\) |
| (Mum, Del) | \(600 - 300 - 50 = 250\) |
All positive ⟹ OPTIMAL.
Advice to management.
-
The plan is optimal at ₹665 000, versus, say, a naive "nearest plant" heuristic that would ship Kolkata→Bengaluru (₹900/t) and cost substantially more.
-
Kolkata is the expensive plant (\(u_{\text{Kol}} = 450\), the highest multiplier). If capacity could be shifted, moving it away from Kolkata saves the most. This is the single most actionable insight in the analysis.
-
Mumbai→Pune (₹200/t) is the cheapest lane in the network and is used to its full 600 t. If Pune demand grew, Mumbai should expand.
-
Chennai splits between Bengaluru and Hyderabad — its two cheapest destinations, as expected.
-
Sensitivity. The smallest opportunity cost is 150 (two cells tied). So a ₹150/t change in either of those lanes' freight rates would change the optimal plan. Rates are volatile; re-run the model whenever a rate moves by more than ₹150/t on the Kolkata–Bengaluru or Mumbai–Bengaluru lanes.
This last point — translating opportunity costs into a monitoring rule — is what turns a solved model into an operating decision-support tool.
9.6 Practice Problems¶
- Given basic cells \((1,1),(1,2),(2,2),(2,3)\) with costs \(4, 6, 8, 5\), find \(u,v\) with \(u_1=0\). [Ans: \(u=(0,2)\), \(v=(4,6,3)\)]
- Compute \(d_{13}\) if \(c_{13}=9\), \(u_1=0\), \(v_3=3\). [Ans: 6 — not entering]
- Trace the loop from \((1,3)\) given basic cells \((1,1),(1,2),(2,2),(2,3)\). [Ans: \((1,3)^+,(2,3)^-,(2,2)^+,(1,2)^-\)]
- Minus cells have 7, 4, 4. Find \(\theta\) and describe the degeneracy. [Ans: \(\theta=4\); keep one at \(\epsilon\)]
- All \(d_{ij} > 0\) except \(d_{31} = 0\). Is the solution optimal? [Ans: yes, but alternate optima exist]
- Verify strong duality for the §2 optimum.
- Why must the \(\epsilon\) cell not close a loop?
9.7 Summary¶
- MODI computes multipliers from \(u_i + v_j = c_{ij}\) over the basic cells, with \(u_1 = 0\) (one multiplier is free because one constraint is redundant).
- Opportunity cost \(d_{ij} = c_{ij}-u_i-v_j\) for non-basic cells; optimal iff all \(d_{ij}\ge0\). The most negative \(d_{ij}\) enters.
- The closed loop through the entering cell is unique; label \(+,-,+,-\), take \(\theta\) = smallest "−" allocation, reallocate. Cost falls by \(\theta\,|d_{ij}|\).
- \(u_i\) and \(v_j\) are the LP dual variables; \(\sum a_iu_i + \sum b_jv_j = Z^{*}\) (strong duality).
- Degeneracy (fewer than \(m+n-1\) basic cells, or a tie in \(\theta\)) is resolved by an \(\epsilon\) allocation in a cell that forms no loop — check this before placing it.
- \(d_{ij}=0\) on a non-basic cell ⟹ alternate optima — report them, since they give free operational flexibility.
- On the worked example: VAM 779 → one iteration → optimum 743; NWCM 1015 → one iteration → 807, still far away. Good starting solutions pay for themselves.
Next lesson: L10 — The assignment problem and the travelling salesman problem.
Practise now: unit1-lp-lab.html → Transportation Lab: run MODI step by step with multipliers,
opportunity costs and the closed loop drawn on the tableau.