关于「标准库里的弗兰克与沃尔夫算法:均衡、最优与相对间隙」,《入口加法与协同层的均衡代价》给出的定量结论是什么?

结论:程序 p31 在布雷斯网络上复现了 83.0000 与 92.0000,路段流量与分数解一致。程序 p32 显示,带一维搜索的弗兰克与沃尔夫的方法在第十步就把间隙降到 1.588e-03,逐次平均法第三百步还停在 3.952e-04。程序 p33 用同一套代码求出系统最优:新入口让最优平均从 12.030 降到 11.397,却让用户均衡从 12.200 升到 16.000,比值 1.4039。下一章把这套工具交给店主:从分钟推到订单,再逐个关闭入口,看看哪一个才是那条布雷斯链路。

数据口径:书中参数为示意;全部计算由书中程序生成;本书是非个人化经营建议,任何删入口、撤协同层的生产变更须由主事者人工复核放行。 书中以标注框区分已发表的证据、可运行的 Python 计算(21 段程序)、原典与作者的假说。

English version

对照数据表

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

iterations Frank-Wolfe gap successive-averages gap
17.466e-02 3.580e-01
33.032e-02 1.765e-01
101.588e-03 4.326e-03
308.352e-05 4.326e-03
1007.260e-09 2.650e-03
3000.000e+00 3.952e-04
equilibrium at 300 iterations, average wait 16.000 minutes
live Q&A load 2.739 wait8.000
live->page load 0.314 wait7.000
pay load 0.575 wait1.000
order desk load 2.425 wait6.999
search load 0.261 wait8.000
search->page load 0.261 wait7.000
NEW live->desk load 2.425 wait1.001
查看完整验算程序
# Chapter 3. p32: how fast does Frank-Wolfe close the gap, against the
# method of successive averages (step 1/k) that many spreadsheets use?
# Network: the purchase funnel of Chapter 4 with the new live-room ->
# order-desk entry open, 300 buyers an hour (illustrative). Waits follow
# the BPR form t0 (1 + 0.15 (x / c)^4) of the US Bureau of Public Roads.
# Relative gap = (total wait - demand * shortest route) / total wait.
import heapq
import math

# (from, to, free minutes, capacity in hundreds of buyers an hour)
FUNNEL = [("V", "L", 3.0, 1.5),    # live-room Q&A, host attention
          ("L", "C", 7.0, 9.0),    # live link to the product page
          ("C", "T", 1.0, 9.0),    # self-service payment
          ("V", "P", 9.0, 9.0),    # private-chat article
          ("P", "K", 1.0, 9.0),    # article to the order desk
          ("K", "T", 2.0, 1.2),    # human order desk queue
          ("V", "S", 8.0, 9.0),    # search and catalogue
          ("S", "C", 7.0, 9.0)]    # catalogue to the product page
NEW = ("L", "K", 1.0, 9.0)         # new entry: live room -> order desk
NAMES = ["live Q&A", "live->page", "pay", "chat page", "chat->desk",
         "order desk", "search", "search->page", "NEW live->desk"]


def cost(link, x):
    # BPR wait: free time * (1 + 0.15 (load / capacity)^4)
    return link[2] * (1.0 + 0.15 * (x / link[3]) ** 4)


def mcost(link, x):
    # marginal social cost: wait + load * d(wait)/d(load)
    return link[2] * (1.0 + 0.75 * (x / link[3]) ** 4)


def shortest(links, times, s, t):
    adj = {}
    for k, link in enumerate(links):
        adj.setdefault(link[0], []).append((link[1], k))
    dist, back, heap = {s: 0.0}, {}, [(0.0, s)]
    while heap:
        du, u = heapq.heappop(heap)
        if du > dist.get(u, math.inf):
            continue
        for v, k in adj.get(u, []):
            nd = du + times[k]
            if nd < dist.get(v, math.inf) - 1e-12:
                dist[v], back[v] = nd, k
                heapq.heappush(heap, (nd, v))
    path, node = [], t
    while node != s:
        k = back[node]
        path.append(k)
        node = links[k][0]
    return dist[t], path


def frank_wolfe(links, d, iters=300, f=cost, s="V", t="T"):
    def aon(x):
        times = [f(lk, xe) for lk, xe in zip(links, x)]
        c, path = shortest(links, times, s, t)
        y = [0.0] * len(links)
        for k in path:
            y[k] = d
        return y
    x = aon([0.0] * len(links))
    for _ in range(iters):
        y = aon(x)

        def slope(a):
            return math.fsum((ye - xe) * f(lk, xe + a * (ye - xe))
                             for lk, xe, ye in zip(links, x, y))
        if slope(1.0) <= 0:
            a = 1.0
        else:
            lo, hi = 0.0, 1.0
            for _ in range(60):
                mid = (lo + hi) / 2
                if slope(mid) > 0:
                    hi = mid
                else:
                    lo = mid
            a = (lo + hi) / 2
        x = [xe + a * (ye - xe) for xe, ye in zip(x, y)]
    return x


def average(links, x, d):
    return math.fsum(xe * cost(lk, xe) for lk, xe in zip(links, x)) / d


def gap(links, x, d):
    times = [cost(lk, xe) for lk, xe in zip(links, x)]
    c = shortest(links, times, "V", "T")[0]
    tot = math.fsum(xe * te for xe, te in zip(x, times))
    return max(0.0, (tot - d * c) / tot)


def msa(links, d, iters):
    x = None
    for k in range(1, iters + 1):
        base = x if x is not None else [0.0] * len(links)
        times = [cost(lk, xe) for lk, xe in zip(links, base)]
        path = shortest(links, times, "V", "T")[1]
        y = [d if j in path else 0.0 for j in range(len(links))]
        if x is None:
            x = y
        else:
            x = [xe + (ye - xe) / k for xe, ye in zip(x, y)]
    return x


NET = FUNNEL + [NEW]
D = 3.0
print("iterations   Frank-Wolfe gap   successive-averages gap")
for n in (1, 3, 10, 30, 100, 300):
    g1 = gap(NET, frank_wolfe(NET, D, iters=n), D)
    g2 = gap(NET, msa(NET, D, n), D)
    print("  %5d        %.3e          %.3e" % (n, g1, g2))
x = frank_wolfe(NET, D, iters=300)
print()
print("equilibrium at 300 iterations, average wait %.3f minutes"
      % average(NET, x, D))
for name, xe, lk in zip(NAMES, x, NET):
    if xe > 1e-6:
        print("  %-15s load %.3f  wait %6.3f"
              % (name, xe, cost(lk, xe)))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《布雷斯悖论瓦德罗普均衡、购买入口加法反效与协同层级的无秩序代价母典》第 3 章「标准库里的弗兰克与沃尔夫算法:均衡、最优与相对间隙」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-246 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026246,
  author    = {Fan, Yafu},
  title     = {Braess's Paradox and Wardrop Equilibrium: When One More Purchase Entry or One More Coordination Layer Slows Everyone Down},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论