关于「熵正则与 Sinkhorn:更快,但是模糊」,《最优传输与奢品调货》给出的定量结论是什么?
结论:第四章说明熵正则与 Sinkhorn 迭代在温度 10 元时成本只高出 0.0033,但模糊的单子不能直接发货。
数据口径:书中的门店、城市坐标、运价、库存、毛利与概率均为示意;全部计算由书中程序生成;本书是非个人化经营建议,书中小工具给出的每一条调拨都须由经营者人工放行。 第三章把位势读成地点价格:计入缺货毛利损失后,示意网络的最优总成本是 7322 元,「缺货店优先补」是 11003 元;每家店多一件货的影子价格都挤在边际缺货店的 1320 元附近,缺一件损失最大的店只值 1253 元,而影子价格是局部斜率,同一家店多 8 件只值 5709 元。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.0033, 10
| exact MODI cost 1281; 20 possible routes, optimum uses 8 | |||||
| eps | iters | <C,P> | excess | routes>0.05 | routes>0.5 |
| 100.0 | 11 | 1877.28 | 0.4655 | 20 | 14 |
| 50.0 | 19 | 1561.22 | 0.2187 | 20 | 10 |
| 20.0 | 59 | 1323.32 | 0.0330 | 12 | 8 |
| 10.0 | 106 | 1285.29 | 0.0033 | 9 | 8 |
| 5.0 | 134 | 1281.13 | 0.0001 | 8 | 8 |
| 2.0 | 190 | 1281.00 | 0.0000 | 8 | 8 |
| 1.0 | 282 | 1281.00 | 0.0000 | 8 | 8 |
查看完整验算程序
# Chapter 4. p41: entropic regularisation and Sinkhorn on network A.
# Minimise <C, P> - eps * H(P) with the same margins as p21; the
# solution is P_ij = exp((f_i + g_j - c_ij) / eps), found by alternate
# scaling of rows and columns (Sinkhorn 1964; Cuturi 2013). Log-domain
# updates keep small eps stable. Stop when every row sum is within
# 1e-9 of its target. Compared with the exact MODI cost of network A.
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])))
def lse(vals):
top = max(vals)
return top + math.log(math.fsum(math.exp(w - top) for w in vals))
def sinkhorn(c, s, d, eps, tol=1e-9, cap=200000):
# 对数域 Sinkhorn:f_i = eps*log s_i - eps*LSE_j((g_j - c_ij)/eps)
m, n = len(s), len(d)
f, g = [0.0] * m, [0.0] * n
for it in range(1, cap + 1):
f = [eps * math.log(s[i]) - eps * lse(
[(g[j] - c[i][j]) / eps for j in range(n)]) for i in range(m)]
g = [eps * math.log(d[j]) - eps * lse(
[(f[i] - c[i][j]) / eps for i in range(m)]) for j in range(n)]
p = [[math.exp((f[i] + g[j] - c[i][j]) / eps) for j in range(n)]
for i in range(m)]
err = max(abs(math.fsum(p[i]) - s[i]) for i in range(m))
if err < tol:
break
return p, f, g, it
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]
exact = total(C, modi(C, S, D)[0])
print("exact MODI cost %d; 20 possible routes, optimum uses 8" % exact)
print(" eps iters <C,P> excess routes>0.05 routes>0.5")
for eps in (100.0, 50.0, 20.0, 10.0, 5.0, 2.0, 1.0):
p, f, g, it = sinkhorn(C, S, D, eps)
cost = math.fsum(C[i][j] * p[i][j] for i in range(4) for j in range(5))
r1 = len([1 for row in p for w in row if w > 0.05])
r2 = len([1 for row in p for w in row if w > 0.5])
ex = cost / exact - 1.0
ex = 0.0 if abs(ex) < 5e-5 else ex
print("%6.1f %7d %8.2f %8.4f %11d %11d" % (eps, it, cost, ex, r1, r2))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《最优传输康托罗维奇对偶、跨区域奢品调货最小搬运代价与客群迁移矩阵母典》第 4 章「熵正则与 Sinkhorn:更快,但是模糊」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}