关于「贪心与线性规划对照:随机到达、样本定价与分布漂移」,《周期配额的路由与倒计时》给出的定量结论是什么?

结论:第六章对照随机到达下的规则,先到先用平均得到事后最优的 0.8427,按几何检查点动态重算得到 0.9875。

数据口径:示意参数下,线性规划相对先到先用多出 0.1668 到 0.2217,相对按复杂度分档的固定规则只多出 0.41 % 到 5.05 %,大头来自分档本身。 书中参数为示意,不含任何厂商的价格或配额;全部计算由书中程序生成。

English version

对照数据表

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

policy mean ratio 5th pct worst (200 cycles, eps 0.1)
greedy0.84270.81560.8026
one-shot0.96550.90000.8709
dynamic0.98750.96650.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}
}

本书其他章节结论