Skip to content

Lesson 9: Transportation Optimality: The MODI Method

9.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Compute the multipliers \(u_i\) and \(v_j\) from the basic cells.
  2. Compute opportunity costs \(d_{ij} = c_{ij} - u_i - v_j\) and apply the optimality test.
  3. Trace a closed loop and perform the stepping-stone reallocation.
  4. Resolve degeneracy by inserting an \(\epsilon\) allocation.
  5. 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

\[ \boxed{\ u_i + v_j = c_{ij} \qquad \text{for every BASIC cell } (i,j)\ } \]

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)

\[ \boxed{\ d_{ij} \ =\ c_{ij} - u_i - v_j\ } \]
\[ \boxed{\ \textbf{Optimal} \iff d_{ij} \ \ge\ 0 \ \text{ for every non-basic cell}\ } \]

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\)
\[ \vec u = (0,\ 50,\ 10), \qquad \vec v = (19,\ -2,\ -10,\ 10) \]

(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:

\[ (2,2)^{+} \ \to\ (2,4)^{-} \ \to\ (3,4)^{+} \ \to\ (3,2)^{-} \ \to\ \text{back to } (2,2) \]

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\).

\[ \text{minus cells: } (2,4) = 2, \quad (3,2) = 8 \]
\[ \theta = \min(2,\ 8) = \mathbf{2} \]

Step 5 — reallocate.

\[ (2,2): 0 + 2 = \mathbf{2}, \qquad (2,4): 2 - 2 = \mathbf{0} \ \text{(LEAVES)} \]
\[ (3,4): 10 + 2 = \mathbf{12}, \qquad (3,2): 8 - 2 = \mathbf{6} \]

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\).

\[ Z = 779 - 36 = \mathbf{743} \]

Direct verification.

\[ Z = 5(19) + 2(10) + 2(30) + 7(40) + 6(8) + 12(20) \]
\[ = 95 + 20 + 60 + 280 + 48 + 240 = \mathbf{743} \ \checkmark \]

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\)
\[ \vec u = (0,\ 32,\ 10), \qquad \vec v = (19,\ -2,\ 8,\ 10) \]

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.

\[ \boxed{\ Z^{*} = ₹743\ } \]

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

\[ \vec u = (0,\ 32,\ 10) \qquad \text{(shadow price of capacity at each source)} \]
\[ \vec v = (19,\ -2,\ 8,\ 10) \qquad \text{(shadow price of demand at each destination)} \]

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\)
\[ \vec u = (0,\ 3,\ 6), \qquad \vec v = (6,\ 3,\ 10) \]

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 ✓

\[ \boxed{\ Z^{*} = 755 \ \text{— VAM was exactly optimal here.}\ } \]

Duality check.

\[ \sum a_iu_i + \sum b_jv_j = 20(0)+30(3)+25(6) + 15(6)+25(3)+35(10) \]
\[ = 90+150 + 90+75+350 = 240 + 515 = \mathbf{755} \ \checkmark \]

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\)
\[ \vec u = (0,\ 0,\ 30), \qquad \vec v = (19,\ 30,\ 40,\ -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)\).

\[ (3,2)^{+} \to (2,2)^{-} \to (2,3)^{+} \to (3,3)^{-} \to \text{back to } (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.

\[ (3,2) = 0+4 = 4, \quad (2,2) = 6-4 = 2, \quad (2,3) = 3+4 = 7, \quad (3,3) = 4-4 = 0 \ \text{(leaves)} \]

New allocation.

\(D_1\) \(D_2\) \(D_3\) \(D_4\)
\(S_1\) 5 2 – –
\(S_2\) – 2 7 –
\(S_3\) – 4 – 14

New cost.

\[ \Delta Z = \theta\,d_{32} = 4\times(-52) = -208 \]
\[ Z = 1015 - 208 = \mathbf{807} \]

Verification.

\[ Z = 5(19)+2(30)+2(30)+7(40)+4(8)+14(20) = 95+60+60+280+32+280 = \mathbf{807} \ \checkmark \]

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.

\[ \boxed{\ d_{23} = 0 \ \text{ for a NON-BASIC cell } \Longrightarrow\ \textbf{ALTERNATE OPTIMA.}\ } \]

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.

  1. Trace the closed loop from \((2,3)\).
  2. Determine \(\theta\) from the "−" cells.
  3. Reallocate.
  4. The new allocation has the same total cost.

Describing all optima. With optimal plans \(X^{(1)}\) and \(X^{(2)}\), every convex combination

\[ X(\lambda) = \lambda X^{(1)} + (1-\lambda)X^{(2)}, \qquad \lambda\in[0,1] \]

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.

\[ \theta = \min(6, 6, 9) = \mathbf{6} \]

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.

\[ \sum a = 500+700+600 = \mathbf{1800}, \qquad \sum b = 400+450+350+600 = \mathbf{1800} \]

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.

\[ Z = 400(300) + 100(250) + 450(500) + 250(700) + 600(200) \]
\[ = 120{,}000 + 25{,}000 + 225{,}000 + 175{,}000 + 120{,}000 = \mathbf{₹665{,}000} \]

Step 3 — MODI check. Basic cells: 5 ✓. With \(u_{\text{Ch}} = 0\):

\[ v_{\text{Ben}} = 300, \quad v_{\text{Hyd}} = 250, \quad u_{\text{Kol}} = 700-250 = 450, \quad v_{\text{Del}} = 500-450 = 50 \]

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:

\[ u_{\text{Mum}} = 550 - 250 = 300, \qquad v_{\text{Pune}} = 200 - 300 = -100 \]

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.

\[ \boxed{\ Z^{*} = ₹665{,}000\ } \]

Advice to management.

  1. 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.

  2. 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.

  3. 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.

  4. Chennai splits between Bengaluru and Hyderabad — its two cheapest destinations, as expected.

  5. 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

  1. 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)\)]
  2. Compute \(d_{13}\) if \(c_{13}=9\), \(u_1=0\), \(v_3=3\). [Ans: 6 — not entering]
  3. 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)^-\)]
  4. Minus cells have 7, 4, 4. Find \(\theta\) and describe the degeneracy. [Ans: \(\theta=4\); keep one at \(\epsilon\)]
  5. All \(d_{ij} > 0\) except \(d_{31} = 0\). Is the solution optimal? [Ans: yes, but alternate optima exist]
  6. Verify strong duality for the §2 optimum.
  7. 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.