What does Optimal Transport for Luxury Stock Transfers conclude, in numbers, about “The Potential Method: Northwest-Corner Starts, Closed Loops and an Exact MODI Solution”?

Answer: Chapter 2 walks from a northwest-corner start of 2564 yuan to the optimum of 1281 yuan in six exchanges, and shows that Vogel's start is already optimal in 0.777 of snapshots.

Scope of the numbers: Chapter 5 applies optimal transport to client migration: in an illustrative matrix, gross movement is 13.43 times what the net change requires, so goods follow net flows and people follow gross flows. Chapter 7 examines equitable transport in the Treatise on the Balanced Standard of the Shiji (lateral transfers save 0.721 of freight in an illustrative model) and Monge's cuttings and fillings.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.777, 1281, 2564

network Astartpivotsfinal
northwest256461281
least-cost130811281
vogel128101281
1500 snapshotsstart gapexact sharemean pivots
northwest0.23220.0393.15
least-cost0.02060.3751.23
vogel0.00400.7770.36
Show the full program
# Chapter 2. p22: does the starting plan matter? Northwest corner,
# least-cost cell and Vogel's approximation as MODI starting bases.
# Each start crosses out exactly one row or column per allocation, so it
# yields m + n - 1 basic cells (a spanning tree), as MODI requires.
# Network A from p21, then 1,500 random snapshots as in p12 (fixed seed).
import math
import random

# 十一城经纬度(取整到 0.1 度);单位搬运费 = 30 + 0.1 * 公里,取整(示意:
# 含保价快递与门店交接,非任何承运商报价)
CITY = {"BJ": (116.4, 39.9), "TJ": (117.2, 39.1), "SH": (121.5, 31.2),
        "HZ": (120.2, 30.3), "NJ": (118.8, 32.1), "GZ": (113.3, 23.1),
        "SZ": (114.1, 22.5), "CD": (104.1, 30.7), "CQ": (106.5, 29.6),
        "WH": (114.3, 30.6), "XA": (108.9, 34.3)}


def km(a, b):
    (x1, y1), (x2, y2) = CITY[a], CITY[b]
    dx = (x1 - x2) * 111.0 * math.cos(math.radians((y1 + y2) / 2.0))
    return math.hypot(dx, (y1 - y2) * 111.0)


def unit_cost(a, b):
    return 30 + round(0.1 * km(a, b))
def northwest(s, d):
    # 西北角初解:阶梯形走 m + n - 1 步,保证基是一棵生成树
    s, d = list(s), list(d)
    m, n = len(s), len(d)
    x = [[0] * n for _ in range(m)]
    basis = []
    i = j = 0
    while True:
        q = min(s[i], d[j])
        x[i][j] = q
        basis.append((i, j))
        s[i] -= q
        d[j] -= q
        if i == m - 1 and j == n - 1:
            break
        if s[i] == 0 and i < m - 1:
            i += 1
        else:
            j += 1
    return x, basis


def potentials(c, basis, m, n):
    # 位势:基格上 u_i + v_j = c_ij,取 u_0 = 0
    u = [None] * m
    v = [None] * n
    u[0] = 0
    while None in u or None in v:
        for i, j in basis:
            if u[i] is not None and v[j] is None:
                v[j] = c[i][j] - u[i]
            elif v[j] is not None and u[i] is None:
                u[i] = c[i][j] - v[j]
    return u, v


def tree_path(basis, i, j):
    # 基树中从列 j 走回行 i 的格子序列(闭回路去掉入基格)
    adj = {}
    for a, b in basis:
        adj.setdefault(("r", a), []).append(("c", b))
        adj.setdefault(("c", b), []).append(("r", a))
    prev = {("r", i): None}
    todo = [("r", i)]
    while todo:
        node = todo.pop()
        for nb in adj.get(node, []):
            if nb not in prev:
                prev[nb] = node
                todo.append(nb)
    path, node = [], ("c", j)
    while prev[node] is not None:
        p = prev[node]
        cell = (p[1], node[1]) if p[0] == "r" else (node[1], p[1])
        path.append(cell)
        node = p
    return path


def modi(c, s, d, x=None, basis=None, trace=None):
    # 位势法(MODI):检验数 r_ij = c_ij - u_i - v_j 全部非负即最优
    m, n = len(s), len(d)
    if x is None:
        x, basis = northwest(s, d)
    x = [row[:] for row in x]
    basis = list(basis)
    steps = 0
    while True:
        u, v = potentials(c, basis, m, n)
        best, cell = 0, None
        for i in range(m):
            for j in range(n):
                r = c[i][j] - u[i] - v[j]
                if r < best:
                    best, cell = r, (i, j)
        if cell is None:
            return x, basis, u, v, steps
        i, j = cell
        path = tree_path(basis, i, j)
        minus, plus = path[0::2], path[1::2]
        theta = min(x[a][b] for a, b in minus)
        out = [e for e in minus if x[e[0]][e[1]] == theta][0]
        x[i][j] += theta
        for a, b in minus:
            x[a][b] -= theta
        for a, b in plus:
            x[a][b] += theta
        basis.remove(out)
        basis.append(cell)
        steps += 1
        if trace is not None:
            trace.append((cell, best, theta, out))


def total(c, x):
    return math.fsum(c[i][j] * x[i][j]
                     for i in range(len(x)) for j in range(len(x[0])))

def crossing(c, s, d, pick):
    # 通用初解:每次按 pick 规则选格,装满后划去一行或一列(只划一条)
    m, n = len(s), len(d)
    s, d = list(s), list(d)
    rows, cols = set(range(m)), set(range(n))
    x = [[0] * n for _ in range(m)]
    basis = []
    while rows and cols:
        i, j = pick(c, s, d, sorted(rows), sorted(cols))
        q = min(s[i], d[j])
        x[i][j] = q
        basis.append((i, j))
        s[i] -= q
        d[j] -= q
        if len(rows) == 1 and len(cols) == 1:
            break
        if s[i] == 0 and len(rows) > 1:
            rows.discard(i)
        else:
            cols.discard(j)
    return x, basis


def pick_least(c, s, d, rows, cols):
    return min(((c[i][j], i, j) for i in rows for j in cols))[1:]


def penalty(vals):
    vals = sorted(vals)
    return vals[1] - vals[0] if len(vals) > 1 else vals[0]


def pick_vogel(c, s, d, rows, cols):
    # 伏格尔法:罚数 = 该行(列)最小与次小运价之差,罚数最大的线上取最便宜格
    cand = []
    for i in rows:
        cand.append((penalty([c[i][j] for j in cols]), 0, i))
    for j in cols:
        cand.append((penalty([c[i][j] for i in rows]), 1, j))
    _, kind, k = max(cand, key=lambda t: (t[0], -t[1], -t[2]))
    if kind == 0:
        return k, min(cols, key=lambda j: (c[k][j], j))
    return min(rows, key=lambda i: (c[i][k], i)), k


def starts(c, s, d):
    out = {"northwest": northwest(s, d),
           "least-cost": crossing(c, s, d, pick_least),
           "vogel": crossing(c, s, d, pick_vogel)}
    res = {}
    for key, (x0, b0) in out.items():
        x, _, _, _, steps = modi(c, s, d, x0, b0)
        res[key] = (total(c, x0), steps, total(c, x))
    return res


SUP, S = ["SH", "SZ", "TJ", "CD"], [6, 5, 5, 2]
DEM, D = ["BJ", "CQ", "HZ", "WH", "GZ"], [3, 3, 5, 5, 2]
C = [[unit_cost(a, b) for b in DEM] for a in SUP]
print("network A          start  pivots  final")
for key, (c0, st, cf) in starts(C, S, D).items():
    print("%-15s %8d %7d %6d" % (key, int(c0), st, int(cf)))

rng = random.Random(20261114)
names = sorted(CITY)
N = 1500
acc = {k: ([], []) for k in ("northwest", "least-cost", "vogel")}
for _ in range(N):
    sup = rng.sample(names, rng.randint(3, 4))
    dem = rng.sample([k for k in names if k not in sup], rng.randint(3, 5))
    s = [rng.randint(1, 6) for _ in sup]
    tot = int(math.fsum(s))
    while tot < len(dem):
        s[0] += 1
        tot += 1
    cuts = sorted(rng.sample(range(1, tot), len(dem) - 1))
    d = [b - a for a, b in zip([0] + cuts, cuts + [tot])]
    c = [[unit_cost(a, b) for b in dem] for a in sup]
    for key, (c0, st, cf) in starts(c, s, d).items():
        acc[key][0].append(c0 / cf - 1.0)
        acc[key][1].append(st)
print("%d snapshots    start gap  exact share  mean pivots" % N)
for key, (g, st) in acc.items():
    print("%-15s %10.4f %12.3f %12.2f"
          % (key, math.fsum(g) / N, len([v for v in g if v < 1e-12]) / N,
             math.fsum(st) / N))

Single source and citation

Fan, Y. (2026). Optimal Transport and Kantorovich Duality: Minimum-Cost Rebalancing of Luxury Stock across Regions and Client-Migration Matrices (Version 1.0.0), Chapter 2: The Potential Method: Northwest-Corner Starts, Closed Loops and an Exact MODI Solution. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-233 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026233,
  author    = {Fan, Yafu},
  title     = {Optimal Transport and Kantorovich Duality: Minimum-Cost Rebalancing of Luxury Stock across Regions and Client-Migration Matrices},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book