关于「标准库里的弗兰克与沃尔夫算法:均衡、最优与相对间隙」,《入口加法与协同层的均衡代价》给出的定量结论是什么?
结论:程序 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 段程序)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: -03, -04, 1.588, 16.000, 3.952
| iterations Frank-Wolfe gap successive-averages gap | |
| 1 | 7.466e-02 3.580e-01 |
| 3 | 3.032e-02 1.765e-01 |
| 10 | 1.588e-03 4.326e-03 |
| 30 | 8.352e-05 4.326e-03 |
| 100 | 7.260e-09 2.650e-03 |
| 300 | 0.000e+00 3.952e-04 |
| equilibrium at 300 iterations, average wait 16.000 minutes | |
| live Q&A load 2.739 wait | 8.000 |
| live->page load 0.314 wait | 7.000 |
| pay load 0.575 wait | 1.000 |
| order desk load 2.425 wait | 6.999 |
| search load 0.261 wait | 8.000 |
| search->page load 0.261 wait | 7.000 |
| NEW live->desk load 2.425 wait | 1.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}
}