What does Optimal Transport for Luxury Stock Transfers conclude, in numbers, about “Kantorovich Duality: Potentials Are the Shadow Prices of Stores”?

Answer: Chapter 3 reads potentials as location prices: with stock-out margins counted, the illustrative network's optimal total is 7322 yuan against 11003 for shortage-first; every store's shadow price of one more unit clusters around 1320 yuan, the loss at the marginal short store, the store with the largest loss per missing unit is worth only 1253, and since a shadow price is a local slope, 8 extra units at one store are worth only 5709.

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: 11003, 1253, 1320, 7322

lost margin per unmet unit: HZ 1800WH 1320SZ 2400CD 2100NJ 1080
optimum cost 7322shortage-first cost 11003excess 3681
unmet at optimum: HZ 0WH 3SZ 0CD 0NJ 2
storeroledual valuere-solve +1re-solve -1
SHsurplus122112211221
BJsurplus118511851236
GZsurplus121212121263
HZshort126712671267
WHshort132013201320
SZshort125312531304
CDshort136613661417
NJshort108010801080
Show the full program
# Chapter 3. p32: what one more unit is worth at each store.
# Network B (illustrative): three stores with surplus (13 units), five
# short stores (18 units), so 5 units of shortage must stay unmet. An
# unmet unit costs the store's expected lost margin: 6,000 yuan unit
# margin times the chance q that the unit would sell in the window.
# Balanced by two dummies: LOST (a supply row priced at the lost
# margin) and KEEP (a demand column for stock left where it is, cost 0).
# Shadow value of +1 unit: surplus store i -> -(u_i + v_KEEP); short
# store j -> v_j + u_LOST. Checked by re-solving with one more unit.
import math

# 十一城经纬度(取整到 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])))

SUP, S = ["SH", "BJ", "GZ"], [6, 3, 4]
DEM, D = ["HZ", "WH", "SZ", "CD", "NJ"], [4, 5, 3, 4, 2]
Q = [0.30, 0.22, 0.40, 0.35, 0.18]
MARGIN = [round(6000 * q) for q in Q]


def solve(s, d):
    c = [[unit_cost(a, b) for b in DEM] + [0] for a in SUP]
    c.append(MARGIN + [0])
    ss = list(s) + [int(math.fsum(d))]
    dd = list(d) + [int(math.fsum(s))]
    x, basis, u, v, _ = modi(c, ss, dd)
    k = v[-1]
    u = [a + k for a in u]
    v = [b - k for b in v]
    return total(c, x), x, u, v


def shortage_first(s, d):
    s, d = list(s), list(d)
    cost = 0
    for j in sorted(range(len(d)), key=lambda k: (-d[k], k)):
        while d[j] > 0 and max(s) > 0:
            i = min((k for k in range(len(s)) if s[k] > 0),
                    key=lambda k: (unit_cost(SUP[k], DEM[j]), k))
            q = min(s[i], d[j])
            cost += q * unit_cost(SUP[i], DEM[j])
            s[i] -= q
            d[j] -= q
        cost += d[j] * MARGIN[j]
    return cost


base, x, u, v = solve(S, D)
print("lost margin per unmet unit: " + "  ".join(
    "%s %d" % (b, m) for b, m in zip(DEM, MARGIN)))
print("optimum cost %d   shortage-first cost %d   excess %d"
      % (int(base), shortage_first(S, D), shortage_first(S, D) - int(base)))
print("unmet at optimum: " + "  ".join(
    "%s %d" % (b, x[3][j]) for j, b in enumerate(DEM)))
print("store  role     dual value  re-solve +1  re-solve -1")
for i, a in enumerate(SUP):
    s1 = list(S)
    s1[i] += 1
    s0 = list(S)
    s0[i] -= 1
    print("%-5s  surplus  %10d  %11d  %11d"
          % (a, -u[i], int(base - solve(s1, D)[0]),
             int(solve(s0, D)[0] - base)))
for j, b in enumerate(DEM):
    d1 = list(D)
    d1[j] -= 1
    d0 = list(D)
    d0[j] += 1
    print("%-5s  short    %10d  %11d  %11d"
          % (b, v[j] + u[3], int(base - solve(S, d1)[0]),
             int(solve(S, d0)[0] - base)))

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 3: Kantorovich Duality: Potentials Are the Shadow Prices of Stores. 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