关于「贪心与线性规划对照:随机到达、样本定价与分布漂移」,《周期配额的路由与倒计时》给出的定量结论是什么?
结论:第六章对照随机到达下的规则,先到先用平均得到事后最优的 0.8427,按几何检查点动态重算得到 0.9875。
数据口径:示意参数下,线性规划相对先到先用多出 0.1668 到 0.2217,相对按复杂度分档的固定规则只多出 0.41 % 到 5.05 %,大头来自分档本身。 书中参数为示意,不含任何厂商的价格或配额;全部计算由书中程序生成。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.8427, 0.9875
| policy mean ratio 5th pct worst (200 cycles, eps 0.1) | |||
| greedy | 0.8427 | 0.8156 | 0.8026 |
| one-shot | 0.9655 | 0.9000 | 0.8709 |
| dynamic | 0.9875 | 0.9665 | 0.9508 |
查看完整验算程序
# Chapter 6. p61: first-come greedy, a learned plan, and hindsight.
# Model: a cycle of N = 530 tasks drawn one by one from the class mix
# (300, 150, 60, 20)/530, in random order, quotas H 600 and F 900.
# greedy - every task tries H first, then F
# one-shot - the first 10 percent go by the fixed rule; then one LP
# on the observed counts, with the remaining quota scaled
# to the sample and shaved by the sample share, gives per
# class H shares used as routing probabilities
# dynamic - the same, re-solved at 10, 20, 40 and 80 percent of the
# cycle (the doubling schedule of Agrawal, Wang and Ye)
# offline - the LP on the realised counts, known only in hindsight
# 200 seeded cycles; ratios are to the offline optimum. Illustrative.
import math
import random
from fractions import Fraction as Fr
def simplex(c, A, b, rule="bland", cap=500):
m, n = len(A), len(c)
T = [[Fr(v) for v in A[i]] + [Fr(int(i == j)) for j in range(m)]
+ [Fr(b[i])] for i in range(m)]
z = [-Fr(v) for v in c] + [Fr(0)] * (m + 1)
basis = [n + i for i in range(m)]
steps = 0
while steps < cap:
cols = [j for j in range(n + m) if z[j] < 0]
if not cols:
break
if rule == "bland":
e = cols[0]
else:
e = min(cols, key=lambda j: (z[j], j))
rows = [i for i in range(m) if T[i][e] > 0]
if not rows:
return None
r = min(rows, key=lambda i: (T[i][-1] / T[i][e], basis[i]))
p = T[r][e]
T[r] = [v / p for v in T[r]]
for i in range(m):
if i != r and T[i][e] != 0:
f = T[i][e]
T[i] = [a - f * w for a, w in zip(T[i], T[r])]
f = z[e]
z = [a - f * w for a, w in zip(z, T[r])]
basis[r] = e
steps += 1
x = [Fr(0)] * (n + m)
for i, j in enumerate(basis):
x[j] = T[i][-1]
return x[:n], z[-1], z[n:n + m], steps
VALUE = (1, 2, 5, 10)
COST = {"H": (4, 6, 10, 16), "F": (1, 2, 3, 4)}
SUCC = {"H": ("0.97", "0.95", "0.90", "0.85"),
"F": ("0.95", "0.80", "0.45", "0.15")}
RW = {t: [VALUE[k] * Fr(SUCC[t][k]) for k in range(4)] for t in "HF"}
Q = {"H": 600, "F": 900}
N = 530
MIX = (300, 150, 60, 20)
def lp(counts, q):
c = [RW[t][k] for t in "HF" for k in range(4)]
A = [[COST["H"][k] if t == "H" else 0 for t in "HF" for k in range(4)],
[COST["F"][k] if t == "F" else 0 for t in "HF" for k in range(4)]]
b = [q["H"], q["F"]]
for k in range(4):
A.append([1 if j == k else 0 for t in "HF" for j in range(4)])
b.append(counts[k])
x, val, _, _ = simplex(c, A, b)
share = [x[k] / counts[k] if counts[k] else Fr(1, 2) for k in range(4)]
return val, share
def draw(rng, mix_a, mix_b):
out = []
for i in range(N):
mix = mix_a if i < N // 2 else mix_b
out.append(rng.choices(range(4), weights=mix)[0])
return out
def serve(k, first, left):
for t in first:
if left[t] >= COST[t][k]:
left[t] -= COST[t][k]
return RW[t][k]
return Fr(0)
def online(tasks, policy, eps, rng):
left = dict(Q)
got = Fr(0)
cut = max(1, int(eps * N))
share = None
nxt = cut
for i, k in enumerate(tasks):
if policy == "greedy":
got += serve(k, "HF", left)
continue
if i < cut:
got += serve(k, "HF" if k >= 2 else "FH", left)
continue
if share is None or (policy == "dynamic" and i == nxt):
seen = [tasks[:i].count(j) for j in range(4)]
scale = Fr(N - i, i)
room = (1 - Fr(cut, N)) if policy == "dynamic" else 1 - eps
q = {t: Fr(left[t]) * room / scale for t in "HF"}
share = lp(seen, q)[1]
nxt = 2 * i
first = "HF" if rng.random() < share[k] else "FH"
got += serve(k, first, left)
return got
rng = random.Random(20261113)
res = {p: [] for p in ("greedy", "one-shot", "dynamic")}
for trial in range(200):
tasks = draw(rng, MIX, MIX)
best = lp([tasks.count(j) for j in range(4)], Q)[0]
for p in res:
got = online(tasks, p, Fr(1, 10), rng)
res[p].append(float(got / best))
print("policy mean ratio 5th pct worst (200 cycles, eps 0.1)")
for p, v in res.items():
v = sorted(v)
print("%-9s %10.4f %7.4f %6.4f" % (p, math.fsum(v) / len(v),
v[9], v[0]))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《周期配额削峰填谷与跨模型路由、重置倒计时线性规划与重推理轻量模型算力分配母典》第 6 章「贪心与线性规划对照:随机到达、样本定价与分布漂移」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-270 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026270,
author = {Fan, Yafu},
title = {Peak-Shaving Periodic Quotas and Cross-Model Routing: Linear Programming against Reset Countdowns to Split Work between Heavy-Reasoning and Fast Models},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}