关于「整件、单票费与运价波动:从线性最优到可执行调货单」,《最优传输与奢品调货》给出的定量结论是什么?

结论:第六章处理整件、单票固定费与运价波动:单票费 200 元时线性最优比精确最优高 0.2117,此时「缺货店优先补」反而打平最优,剪枝法找回最优。

数据口径:书中的门店、城市坐标、运价、库存、毛利与概率均为示意;全部计算由书中程序生成;本书是非个人化经营建议,书中小工具给出的每一条调拨都须由经营者人工放行。 第三章把位势读成地点价格:计入缺货毛利损失后,示意网络的最优总成本是 7322 元,「缺货店优先补」是 11003 元;每家店多一件货的影子价格都挤在边际缺货店的 1320 元附近,缺一件损失最大的店只值 1253 元,而影子价格是局部斜率,同一家店多 8 件只值 5709 元。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.2117, 200

integer plans enumerated3874
fee best routes LP+fee routes greedy+fee routes prune LP excess
01015 6 1015 6 1028 4 1015 0.0000
501228 4 1315 6 1228 4 1228 0.0708
1001428 4 1615 6 1428 4 1428 0.1310
2001828 4 2215 6 1828 4 1828 0.2117
4002628 4 3415 6 2628 4 2628 0.2995
fee 200 plan: SH>BJ 2, HZ>CD 2, NJ>WH 4, GZ>SZ 2
LP plan: SH>BJ 1, HZ>WH 3, NJ>WH 1, NJ>BJ 1, NJ>CD 2, GZ>SZ 2
查看完整验算程序
# Chapter 6. p62: a fixed fee per shipment (pickup, sealing, two-person
# handover) on top of the per-unit cost. Four stores hold 12 spare units
# against 10 units of shortage, so 2 units may stay where they are.
# Every integer plan is enumerated column by column, so the fixed-charge
# optimum is exact. Compared: the linear optimum (MODI with a KEEP
# column at cost 0), shortage-first greedy, and "prune": forbid one used
# route at a time, re-solve by MODI, keep the best saving, repeat.
import math
import itertools

# 十一城经纬度(取整到 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", "HZ", "NJ", "GZ"], [3, 3, 4, 2]
DEM, D = ["WH", "BJ", "SZ", "CD"], [4, 2, 2, 2]
C = [[unit_cost(a, b) for b in DEM] for a in SUP]


def splits(q, k):
    for xs in itertools.product(range(q + 1), repeat=k):
        if int(math.fsum(xs)) == q:
            yield xs


plans = []
for cols in itertools.product(*[list(splits(q, 4)) for q in D]):
    x = [[cols[j][i] for j in range(4)] for i in range(4)]
    if all(int(math.fsum(x[i])) <= S[i] for i in range(4)):
        plans.append(x)
ck = [row + [0] for row in C]
xk = modi(ck, S, D + [int(math.fsum(S) - math.fsum(D))])[0]
lp = [row[:4] for row in xk]


def shortage_first():
    s, d = list(S), list(D)
    x = [[0] * 4 for _ in range(4)]
    for j in sorted(range(4), key=lambda k: (-d[k], k)):
        while d[j] > 0:
            i = min((k for k in range(4) if s[k] > 0),
                    key=lambda k: (C[k][j], k))
            q = min(s[i], d[j])
            x[i][j] += q
            s[i] -= q
            d[j] -= q
    return x


def with_fee(x, fee):
    n = len([w for row in x for w in row if w > 0])
    return total(C, x) + fee * n, n


def solve_lp(forbid):
    ck = [[C[i][j] if (i, j) not in forbid else 10 ** 6
           for j in range(4)] + [0] for i in range(4)]
    xk = modi(ck, S, D + [int(math.fsum(S) - math.fsum(D))])[0]
    return [row[:4] for row in xk]


def prune(fee):
    # 剪枝:逐条禁用在用路线并重解,取节省最多的一步,直到不再节省
    forbid = set()
    x = solve_lp(forbid)
    while True:
        best = (with_fee(x, fee)[0], None, x)
        for i in range(4):
            for j in range(4):
                if x[i][j] > 0:
                    y = solve_lp(forbid | {(i, j)})
                    if with_fee(y, fee)[0] < best[0] - 1e-9:
                        best = (with_fee(y, fee)[0], (i, j), y)
        if best[1] is None:
            return x
        forbid.add(best[1])
        x = best[2]


gr = shortage_first()
print("integer plans enumerated: %d" % len(plans))
print("fee  best routes  LP+fee routes  greedy+fee routes  prune  LP excess")
for fee in (0, 50, 100, 200, 400):
    best = min(plans, key=lambda x: (with_fee(x, fee)[0], str(x)))
    b, nb = with_fee(best, fee)
    l, nl = with_fee(lp, fee)
    g, ng = with_fee(gr, fee)
    pr = with_fee(prune(fee), fee)[0]
    print("%3d %5d %6d %6d %6d %11d %6d %6d %10.4f"
          % (fee, int(b), nb, int(l), nl, int(g), ng, int(pr), l / b - 1.0))
    if fee == 200:
        keep = best
print("fee 200 plan: " + ", ".join(
    "%s>%s %d" % (SUP[i], DEM[j], keep[i][j])
    for i in range(4) for j in range(4) if keep[i][j]))
print("LP plan:      " + ", ".join(
    "%s>%s %d" % (SUP[i], DEM[j], lp[i][j])
    for i in range(4) for j in range(4) if lp[i][j]))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《最优传输康托罗维奇对偶、跨区域奢品调货最小搬运代价与客群迁移矩阵母典》第 6 章「整件、单票费与运价波动:从线性最优到可执行调货单」(版本 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}
}

本书其他章节结论