在线分配与流量管理

📝 Before You Continue: 本章需先读 12.1（全景图）——合约广告在生态中的位置与「保量」交易的由来；以及 12.4（智能出价与预算控制）——pacing 乘子与本章的对偶变量是同一思想在两个市场的投影。12.3（竞价机制）帮你看清本章的对照组：竞价市场靠价格出清，合约市场靠算法分配。

12.4 里我们解决的是「钱」的约束：预算有限，怎么花得又慢又准。这一章处理它的孪生兄弟——「量」的约束：品牌广告主签下的是「未来两周、25–35 岁女性用户、100 万次展示」这样的合约，平台必须在流量到来时实时决定每一次展示给谁，最终既不超卖（供给有限）也不欠量（合约要保）。这就是 在线分配（Online Allocation） 问题。它诞生于担保式投送（Guaranteed Delivery, GD）这种看起来有些「古老」的合约广告系统，但它给出的框架——供给/需求二部图 + 带约束优化 + 对偶变量定价——至今仍支撑着品牌合约广告的投放引擎，而它训练出的思维方式（把约束写进优化目标、用对偶价格解释流量价值）正是 12.4 那套智能出价体系的理论源头。

本章沿「问题 → 模型 → 支撑技术 → 求解 → 执行」的路线展开：先把保量问题写成二部图上的带约束优化，再补上流量预测与频次控制两块地基，然后看工程上如何从不可解的直接线性规划走到紧凑的对偶方案（SHALE），最后落到实用启发性算法 HWM 与它的线上执行逻辑。

读完本章，你将能够：

• 把「保量 + 优化收益」表述为供给/需求二部图上的带约束优化问题，写出需求约束、供给约束与目标函数
• 描述流量预测的反向索引方案，解释它为什么是「广告检索的对偶问题」
• 解释频次控制如何打破展示可分解性假设，以及客户端/服务端两种实现方案的取舍
• 说明为什么直接线性规划在大规模合约系统里不可解，紧凑分配方案如何用 $|A|$ 级的对偶变量恢复 $|E|$ 级的分配率
• 实现 HWM 离线规划与在线 serving 的完整流程，完成 5 道分层练习题

12.7.0 保量广告：一个带约束的决策系统

先区分两种卖法。竞价广告 （12.3 整章）像证券市场：每一次展示当场拍卖，价高者得，流量用价格出清。合约广告 像提前包场：广告主与媒体约定定向人群、时间段与展示量，价格与量都写进合同。合约的最初形态是按广告位包时段售卖的 CPT 广告，这类 排期系统 并不个性化——素材按事先确定的排期直接插入媒体页面，通过 CDN 加速访问，服务器端几乎没有决策压力。工程上唯一值得留意的是混合投放的调度：排期广告走 CDN 前端直投，动态广告走服务端决策；若服务端超时或出错，页面要渲染 CDN 上的 防天窗广告 （兜底素材），保证广告位永远不空白。这套「前端兜底」的思路今天仍是广告位容错的标准答案。

真正的复杂性出现在 展示量合约 ：按 CPM 计费、按人群售卖。此时服务器必须实时决策每一次展示给哪份合约，且必须保证每份合约到期能凑够约定量——这样的系统叫 担保式投送（GD）系统。只要所有合约都被满足，收益就是一个常量（量与价都签死了），优化目标随之从「收益最大」变成「在满足所有合约量的前提下，把流量分配得尽量好」。这一转变把一个无约束的排序问题变成了一个 带约束的优化问题 ，而这正是本章全部技术的出发点。

🧠 Mental Model: 包桌的餐厅

把广告系统想成一家餐厅。竞价广告是散客：每晚开门，谁出价高谁坐最好的位子，收入随行就市。合约广告是包桌：客人提前一个月订下「周五晚 8 点、二楼包间、10 桌」。包桌有两条铁律——每桌的菜不能少（合约量要满足），一桌不能同时坐两拨客人（流量不能超卖）。包桌生意难做在哪？周五晚上到底来多少客人（流量），你只能根据过去几个月的客流（历史日志）去猜；猜完还要提前定好「来了 100 位散客时，先安排哪几桌给包桌客人」（分配方案）。在线分配就是把这套「提前订位 + 当晚调度」变成数学。

GD 系统的整体架构并不复杂：在线投放引擎接收用户触发的广告请求，用用户标签与上下文标签匹配可服务的合约，再由 在线分配模块 决定本次展示投给谁；展示与点击日志进入数据高速公路，一面离线整理出合约执行计划（分配算法的参数），一面流式计算反作弊与计费。接下来两节先讲两块支撑技术（流量预测、频次控制），再进入分配算法本体。

12.7.1 二部图：把保量写成带约束优化

在线分配有两个天然难点：一是要在量的约束下优化效果；二是必须对每一次展示实时决策。直接同时优化这两件事非常困难，因此工程上把问题简化为一个 二部图（bipartite graph） 匹配问题：一侧是 供给节点 $i\in I$，每个节点代表所有标签都相同的一块流量库存，其总量记为 $s_i$；另一侧是 需求节点 $a\in A$，每个节点代表一份广告合约，约定量记为 $d_a$。若供给节点的受众标签能满足某合约的定向要求，就在两点间连一条边，全体边的集合记为 $E$，合约 $a$ 相邻的供给节点集合记为 $\Gamma (a)$。

图中的每份合约带着自己的定向条件与约定量，供给节点则按标签组合聚合流量。要注意这个结构做了一个重要近似：同一供给节点与同一需求节点之间的所有展示，收益不再区分（收益 $r_{ia}$ 只依赖节点对，不依赖单次展示的 $a,u,c$ 组合）。这不完全准确，却是研究在线分配算法的合理简化；而且供给节点的数目会随定向条件组合呈几何级数上升，这个近似也让问题规模保持在可处理的范围。

在这个二部图上，分配方案就是一组 分配比例 ：$x_{ia}$ 表示把供给节点 $i$ 的多大比例流量分配合约 $a$。整体收益函数假设可加、可分：

$$F(s,x)=\sum _{i\in I}{s}_i\sum _{a\in \Gamma (i)}{x}_{ia}{r}_{ia}$$

约束有两组。第一组是 需求约束（demand constraint）——分配合约 $a$ 的收益（或量）至少要达到约定值 $d_a$：

$$\sum _{i\in \Gamma (a)}{s}_i{x}_{ia}{q}_{ia}\ge d_a$$

其中 $q_{ia}$ 是把供给节点 $i$ 连接到需求节点 $a$ 的单位流量惩罚（或收益系数）。实际产品中需求约束常见两类：一类是预算、服务成本等上限要求；另一类是合约量的下限要求——后者 $q_{ia}$ 取负值，约束描述的是收益项的下限。第二组是 供给约束（supply constraint）——每个供给节点分出去的量不能超过它的总流量：

$$\sum _{a\in \Gamma (i)}{x}_{ia}\le 1$$

再加上 $x_{ia}\ge 0$ 保证分配非负，就得到在线分配的一般优化框架。这个框架不止服务于 GD：后面 12.7.4 的理论分析与 12.4 的预算出价，用的都是它。

两个典型实例值得记住。GD 问题 ：按 CPM 售卖的合约市场，所有合约都满足时收益是常量，于是优化目标写成最大化整体分配收益、同时保证每份合约的分得量不低于约定值——本质是「更好地满足所有合约」。AdWords 问题 （也称带预算约束的出价问题）：CPC 竞价环境下，给定各广告主的预算 $B_a$，最大化整个市场的收入——此时需求约束变成「每个广告主的花费不超过预算」。AdWords 问题的对偶变量正是「流量对预算的边际价值」，这就是 12.4.2 预算 pacing 乘子的理论原型；在自助式投放中广告主常常先设较少预算、花完再追加，所以预算在实践中未必是强约束，但这套思考方式对各类量约束优化问题的框架意义是值得体会的。

12.7.2 两块地基：流量预测与频次控制

分配算法要「提前离线算好方案、在线照此执行」，前提是你对未来的流量心中有数。流量预测（traffic forecasting） 要回答的问题是：给定一组受众标签组合与一个 eCPM 阈值，估算将来某时段内满足这些标签、且市场价在该阈值以下的展示量。eCPM 阈值主要用于竞价场景（了解某出价水平下能拿到多少流量）；对展示量合约，这个阈值设为一个很大的常数即可。

工程上的主要挑战在于：标签组合的可能性是天文数字，不可能预先把每个组合的流量都统计好。可行思路是把流量预测变成一个 反向索引 问题——普通广告检索里，索引的「文档」是广告，查询是展示上的标签；流量预测恰好对偶：文档是每次展示上的 $(u,c)$ 标签组合，查询是广告设定的受众条件。具体四步：

1. 准备文档 ：把历史流量按 $(u,c)$ 上所有标签聚合为供给节点，统计总流量 $s_i$，以及这部分流量在 eCPM 上的直方图 ${\mathrm{hist}}_i$；
2. 建立索引 ：对每个供给节点建倒排索引，关键词就是它的全部标签，正排表记录 $s_i$ 与 ${\mathrm{hist}}_i$；
3. 查询 ：对输入的广告 $a$，用其定向条件作查询，取出所有满足条件的供给节点；
4. 估算流量 ：遍历每个供给节点，计算广告在该节点的 $\mathrm{eCPM}=\mu (a,u_i,c_i)\cdot {\mathrm{bid}}_a$，结合直方图折算广告在出价 ${\mathrm{bid}}_a$ 下能获得的近似流量。

日志规模太大时，在第 1、2 步之间加一层采样即可——流量预测允许误差，索引规模控制住比精确更重要。这套方案今天仍在合约售卖的流量预估、ADX 询价优化等场景中使用；其现代演进在于，深度模型与时间序列方法已用于精细化的流量曲线预估，但「按标签组合聚合 + 反向索引」仍是工程上撑住查询响应的骨架。

第二块地基是 频次控制（frequency capping） ：控制组合 $(a,u)$ 在一定时间周期内的展示次数。动机来自经验规律——随着同一用户看到同一创意的频次上升，点击率呈单调下降趋势（传统广告的「三打理论」认为三次曝光最有效，在线环境的效果曲线则随频次单调下降，并不在第三次达到峰值）。在按 CPM 采购时，广告主常要求限制某创意对单一用户的曝光次数，以提高性价比；视频等高曝光强度的产品里尤其显著。

从计算的角度看，频次是破坏「每次展示独立、收益可分」假设的最主要因素——而 12.7.1 的整个框架恰恰建立在可分性之上。把频次作为可控的定向条件引入系统后，问题虽不能被彻底解决，却可大大缓解；在 CPC 竞价广告中，则把频次作为 CTR 预估的特征之一，隐式地控制重复展示的损耗。

实现方案有客户端与服务端两条路。客户端方案 把用户对某创意的频次记录在浏览器 cookie（或移动端 SDK 的本地存储）里，投放决策时传给投放机：简单、服务成本低，在 SDK 控制投放的移动场景是很好的选择；缺点是跨广告追踪多频次时 cookie 会变得很重，影响响应时间。服务端方案 在后台设一个专用的频次缓存，请求到来时查候选广告的频次、实际投放后更新：这要求缓存同时扛住高并发读与高并发写。好在频次存储的规模有天然上限（一个时间周期内的频次变量总数不会超过该周期内的展示总数），且业务上对极小比例的冲突组合允许频控不准——用 MD5 之类的哈希方法生成键即可，还能顺带满足投放过程弱一致的设计原则。因此通用 NoSQL 反而不合适，业界普遍自研轻量级内存键值对缓存，规模大到可以直接放在广告投放机的本机内存里。跨媒体的频次控制（同一用户在不同媒体上合并计频）则依赖统一身份识别——这条线索在 12.6 的开环/闭环与身份基础设施里已经展开。

12.7.3 求解：从直接线性规划到紧凑分配方案

现在进入分配算法本体。假设未来一段时间的合约已知，且流量分布在各周期内近似平稳——那么可以先用历史数据拟合未来流量 $s_i$，把在线问题转化成离线问题，直接对 12.7.1 的优化框架求解。这是几乎所有实用工程方法的基本出发点。

第一条路：直接求解。 当目标函数是线性或二次函数时，这是一个标准的线性规划（LP）或二次规划（QP）问题，用优化工具直接求解即可。它适合定向标签少、合约数少的小规模场景。但大型合约广告系统里，供给节点数随定向条件呈几何级数上升，需求节点可达数千个，边数 $|E|$ 在百万级以上——变量个数正比于 $|E|$，经典算法（内点法为 $n$ 的多项式级别，单纯形法约 $O(n^{1.5}\sim n^2)$）在小时级更新的节奏下几乎不可能求解；而且解出来的参数本身就是 $|E|$ 级的，线上投放机要加载、查询这么庞大的方案表也非常笨重。

第二条路：对偶与紧凑分配方案。 转机来自对偶视角。LP 的每个约束对应一个对偶变量：需求约束的对偶变量记为 ${\alpha }_a$（合约级，量级是合同数，成百上千），供给约束的对偶变量记为 ${\beta }_i$（供给级，量级数十万到千万）。直觉上 ${\beta }_i$ 是「节点 $i$ 一块流量本身的价值」，${\alpha }_a$ 是「合约 $a$ 的稀缺程度」。既然 $|A|$ 远小于 $|E|$，能否只保留合约级的对偶变量，在线上再恢复出完整的分配率？答案是肯定的：对偶问题的 KKT 条件给出了一组由 $\alpha$ 恢复 $\beta$ 与 $x$ 的解析关系。定义每个需求节点的 需求-供给比 ：

$${\theta }_a=\frac{d_a}{{\sum }_{i\in \Gamma (a)}{s}_i}$$

它衡量合约 $a$ 能分到的合规流量相对自身需求有多紧张。给定 $\beta$，供给侧与分配率可按如下关系恢复（$\theta$、$\alpha$ 已知时一步算出）：

$$x_{ia}=\max (0,{\theta }_a(1+{\alpha }_a-{\beta }_i))$$

由于方案的存储量正比于合约数 $|A|$ 而非边数 $|E|$，这被称为 紧凑分配方案（compact allocation plan）。它还有第二个关键性质——无状态 ：分配策略只依赖预计算好的 $\{{\alpha }_a\}$（及由它导出的比例），与投放历史无关，多台广告投放机之间不需要为状态同步做任何通信，系统的稳健性和扩展性都因此受益。这与 12.4.2 里 pacing 乘子「一个标量控制全局」的品味一脉相承：约束优化的对偶变量，天然就是把复杂约束压缩成低维控制信号的工具。

SHALE：原始对偶迭代。 紧凑方案还剩一个开销：在大规模历史数据上解对偶问题本身仍然昂贵。SHALE 算法把这一步改成原始对偶方法迭代：交替执行「固定 $\alpha$ 解 $\beta$、固定 $\beta$ 解 $\alpha$」，每轮迭代都改善对偶解，直到收敛。迭代法不仅省下离线计算时间，还能更好地支持 增量求解——插入一份新合约时从当前解出发继续迭代即可，不必整个重解。

Analysis: 三条路线的取舍可以浓缩成一张表。直接 LP：解质量最优，但变量 $O(|E|)$、求解时间不可行、方案表庞大；紧凑方案：存储 $O(|A|)$、无状态、支持增量，代价是要离线解一次对偶问题；HWM（下一节）：连对偶问题都不解，纯启发式，工程最简、效果近似。共同点是——三者都把「在线决策」压缩成「离线算参数 + 在线查参数」，这是在「信息不全时做实时决策」这一根本困难下，唯一现实的系统形态。

12.7.4 极限性能：对偶更新与 $1-1/e$ 上限

如果不利用流量预测，在线分配的效率上限在哪里？这一极端情形对实用系统的直接帮助有限，但它揭示了「聪明的分配策略」长什么样，而且结论直接通向现代预算出价的理论。衡量指标是 竞争比（competitive ratio） ：若某在线策略在最坏情形下能达到离线全局最优目标函数的 $ϵ$ 倍（$ϵ\in [0,1]$），就称它是 $ϵ$-competitive 的。

把每次展示当作一个 $s_i=1$ 的供给节点，优化框架的拉格朗日对偶给出一个在线算法骨架：为每份合约维护一个对偶变量 ${\beta }_a$（近似「该合约当前还差多少量、差的是好流量还是差流量」）；展示到达时，分配给 $r_{ia}-{\beta }_a$ 最大的合约（收益超过机会成本才投，否则交还给其他变现渠道）；随后按某种规则更新 ${\beta }_a$。不同更新规则对应不同算法： 贪心 （${\beta }_a$ = 已分配的前 $d_a$ 个高权重展示中的最低权重）、平均加权 （前 $d_a$ 个的算术平均）、指数加权 （前 $d_a$ 个的指数加权，越接近当前权重越高）——极限性能依次变好，其中指数加权被证明达到 $(1-1/e)$-competitive，且这是所有在线分配算法理论上可达的最优上限。

这段理论在今天的价值不在「背结论」，而在两个思想。其一，${\beta }_a$ 的含义就是 流量的机会成本 ：展示投给某合约之前，先问「这块流量在别处值多少钱」——12.4.2 的 pacing 乘子、oCPC 预算约束下的出价缩放，本质都是对这个对偶价格的在线估计。其二，Free Disposal（超投无损失也无收益）的假设符合大多数广告合约的现实，它让「分配少了可以补、多了不用赔」成为算法可以依赖的宽容性。

12.7.5 HWM：工程上活下来的启发式算法

理论方案离线求解对偶仍然复杂。能不能不解优化问题，只靠「合约的紧缺程度 + 一个分配比例」就把方案定出来？ 高水位（High Water Mark, HWM）算法 就是这样一种启发式：数学上不完全严谨，但保留了紧凑、无状态的特性，实际效果相当不错，加上工程实现简单，成为合约广告系统里真实在用的方案。

HWM 离线规划分两步。第一步，对每份合约计算紧缺程度 ${\theta }_a=d_a/{\sum }_{i\in \Gamma (a)}{s}_i$（与紧凑方案里的需求-供给比同一个量），按 $\theta$ 降序确定分配优先级——越难满足的合约越先分。第二步，按优先级依次处理各合约：合约 $a$ 先看其全部候选供给节点的剩余总流量，若不足则全部分给它（${\mathrm{rate}}_a=1$），否则分给它所需的比例 ${\mathrm{rate}}_a=d_a/{\sum }_{i\in \Gamma (a)}{s}_i^{\text{remain}}$，并把每个候选节点的剩余流量按 $(1-{\mathrm{rate}}_a)$ 折减。

线上执行时，对每次展示：把满足定向条件的候选合约按优先级排序，累加它们的分配比例；若累积比例超过 1，用随机数落在哪个合约的累积区间来决定投给谁（概率与优先级相配合）；若所有候选的分配比例之和不足 1，则以 $1-\sum {\mathrm{rate}}_a$ 的概率把这次展示交还服务器，转给其他流量变现渠道（如竞价广告）。

下面的 Python 代码实现了 HWM 的离线规划与在线决策两个函数，可以直接运行验证：

import random

def hwm_plan(supplies: dict, demands: dict, links: dict) -> tuple[dict, dict]:
    """离线规划。supplies: {供给节点: 流量}; demands: {合约: 约定量};
    links: {合约: [候选供给节点]}。返回 (优先级, 分配比例)。"""
    theta = {a: d / sum(supplies[i] for i in links[a]) for a, d in demands.items()}
    orders = dict(sorted(theta.items(), key=lambda kv: -kv[1]))  # 越紧缺越先分
    remains = dict(supplies)
    rates = {}
    for a in orders:
        total = sum(remains[i] for i in links[a])
        rate = 1.0 if total < demands[a] else demands[a] / total   # ← KEY LINE: 需求/剩余供给
        rates[a] = rate
        for i in links[a]:
            remains[i] *= (1 - rate)                               # ← KEY LINE: 折减候选节点余量
    return orders, rates

def hwm_serve(candidates: list, orders: dict, rates: dict) -> str | None:
    """在线决策。返回选中的合约 id，或 None 表示交还其他渠道。"""
    cands = sorted(candidates, key=lambda a: -orders[a])           # 按优先级排序
    r, acc = random.random(), 0.0
    for a in cands:
        acc += rates[a]
        if r < acc:                                                # ← KEY LINE: 随机数落累积区间
            return a
    return None

supplies = {"s1": 300, "s2": 500, "s3": 200}
demands  = {"a_men": 250, "a_geo": 300, "a_all": 200}
links    = {"a_men": ["s1"], "a_geo": ["s2"], "a_all": ["s1", "s2", "s3"]}
orders, rates = hwm_plan(supplies, demands, links)
print(rates)   # {'a_men': 0.83, 'a_geo': 0.6, 'a_all': 0.3} 量级示意
print(hwm_serve(["a_all", "a_geo"], orders, rates))

下面的交互式模拟器把整条链路跑给你看：点击「生成流量预测」看供给节点的余量如何被各合约按优先级逐层折减，然后逐次「投放展示」，观察随机数落区间与合约完成度的变化；把任一合约的约定量调大，你会看到它的 $\theta$ 上升、优先级前移，整个分配比例表随之重排。

模拟器中每一次展示的决策只依赖预计算好的优先级与分配比例——没有跨请求的状态，这正是 12.7.3 说的「弱状态 + 多机低耦合」在工程上的模样。

Analysis: HWM 的时间复杂度：离线规划 $O(|A|\log |A|+|E|)$（排序 + 每条边折减一次），在线决策 $O(k\log k)$（$k$ 为候选数，主要开销在排序）。它放弃了对偶变量对流量价值的精细刻画，换来「一个 dict 就能部署」的工程简单性；在合约结构相对稳定、流量预测足够准的市场里，这个近似是划算的。反过来，当合约之间强耦合、定向标签高度重叠时，HWM 的贪心顺序会让先分配的合约挤占后分配合约的优质流量，此时 SHALE 类方案的对偶定价仍不可替代。

⚠️ Common Mistakes in 12.7

本章小结

📌 Key Takeaways

❓ FAQ

Q1: 合约广告看起来是「过时」的形态，这套技术今天还有多少在用？

比想象中多。中国品牌广告大盘里合约售卖仍占相当份额，头部媒体的 GD/排期引擎每天都在跑在线分配；程序化交易里的 PD（程序化直采）同样带着保量承诺。更重要的是，这套「约束优化 + 对偶定价」的框架是预算出价（12.4）、ADX 询价优化等实效广告技术的理论底座——学它不是复古，是打底。

Q2: 紧凑方案只保留 $\alpha$，供给约束会不会被违反？

不会——恢复关系 $x_{ia}=\max (0,{\theta }_a(1+{\alpha }_a-{\beta }_i))$ 是从 KKT 条件推导出来的，${\beta }_i$ 恰好取到让供给约束取等的值（当该供给节点的流量被用满时）。工程上若流量预测偏差导致实际超投，Free Disposal 的假设也保证了超投部分无额外损失。

Q3: HWM 与紧凑方案该选哪个？

看合约结构与求解成本预算。合约数多、相互耦合强、标签重叠严重时，HWM 的贪心顺序损耗明显，值得离线跑 SHALE；合约稀疏、流量平稳时，HWM 的效果与优化方案差距很小，部署成本却低一个量级。实践中常见混合形态：核心保量合约走优化方案，长尾合约走 HWM。

🔗 前后关联

• 12.1 （全景与生态）：合约广告与竞价广告的市场分界，是本章问题来源的业务背景
• 12.4 （智能出价与预算控制）：pacing 乘子与 AdWords 对偶变量是同一约束优化框架在竞价侧的投影，预算约束 = 需求约束的镜像
• 12.6 （开环与闭环广告）：跨媒体频次控制依赖的身份识别基础设施，与开放互联网身份退化互为因果
• 12.2 （计费模式与核心指标）：流量预测的 eCPM 阈值与直方图，口径完全建立在 12.2 的 eCPM 定义上

Practice Problems

Work through all problems in order — they get progressively harder. Each has a complete solution you can reveal after trying it yourself.

Problem 12.7.1 — 计算 HWM 的分配比例 🟢 Easy

供给节点：$s_A=400$（女性用户），$s_B=600$（地域 X 用户），$s_C=300$（同时满足女性与地域 X）。合约：$d_1=300$（女性），$d_2=450$（地域 X），$d_3=200$（女性 且 地域 X）。按 $\theta$ 降序确定优先级，并给出各合约的分配比例。

Sample Input: 供给 $\{A:400,B:600,C:300\}$；需求 $\{1:300,2:450,3:200\}$ Sample Output: 优先级 $3\to 2\to 1$；比例 $\{3:0.667,2:0.643,1:0.689\}$（数值容差内）

Problem 12.7.2 — 用对偶关系恢复分配率 🟡 Medium

已知某市场有两个供给节点（$s_1=100,s_2=100$）与两份合约（$d_1=60,d_2=80$），合约 1 只能用节点 1，合约 2 可用两个节点。流量预测无偏。若求解对偶得到 ${\alpha }_1=0.2,{\alpha }_2=0$，且解出的 ${\beta }_1=0.3,{\beta }_2=-0.1$，用紧凑方案的恢复公式计算分配率 $x_{ia}$，并验证供给约束与需求约束。

Sample Input: $\alpha =\{0.2,0\}$，$\beta =\{0.3,-0.1\}$ Sample Output: $x_{11}=0.54$，$x_{12}=0$，$x_{22}=0.44$

Problem 12.7.3 — 实现 SHALE 的一轮原始对偶迭代 🔴 Hard

写出 SHALE 的 toy 版本：给定供给、需求与连接关系，实现 get_beta_from_alpha(alpha) 与 get_alpha_from_beta(beta) 两个交替更新函数，迭代 $N=50$ 次，从 $\alpha =0$ 出发。用 Problem 12.7.2 的市场数据验证：迭代收敛后需求约束应当取等（分得量 ≈ 约定量）。

Sample Input: $s=\{100,100\}$，$d=\{60,80\}$，$\Gamma (1)=\{1\}$，$\Gamma (2)=\{1,2\}$ Sample Output: 收敛后 $x_{11}=0.6$，$x_{12}=0.4$，$x_{22}=0.4$；两份合约分别分得 60 与 80，恰好足量

def get_theta(s, d, links_a):
    # 需求-供给比: theta[a] = d_a / sum(候选供给流量)
    return [d[a] / sum(s[i] for i in links_a[a]) for a in range(len(d))]

def beta_from_alpha(alpha, s, d, links_i, theta):
    """固定 alpha 更新 beta_i（供给约束对偶变量）。"""
    beta = []
    for i in range(len(s)):
        t = sum(theta[a] for a in links_i[i])          # 该节点可服务合约的 theta 之和
        if abs(t) < 1e-20:
            beta.append(0.0); continue
        tmp1 = t + sum(theta[a] * alpha[a] for a in links_i[i]) - 1
        beta.append(max(0.0, tmp1 / t))                # ← KEY LINE: KKT 解析式
    return beta

def alpha_from_beta(beta, s, d, links_a, theta):
    """固定 beta 更新 alpha_a（需求约束对偶变量）。"""
    alpha = []
    for a in range(len(d)):
        t = theta[a] * sum(s[i] for i in links_a[a])
        if abs(t) < 1e-20:
            alpha.append(0.0); continue
        tmp1 = d[a] + theta[a] * sum(s[i] * beta[i] for i in links_a[a]) - t
        alpha.append(tmp1 / t)                         # ← KEY LINE: 令需求约束取等
    return alpha

def shale(s, d, links_a, links_i, N=50):
    theta = get_theta(s, d, links_a)
    alpha = [0.0] * len(d)
    for _ in range(N):                                 # ← KEY LINE: 交替迭代
        beta = beta_from_alpha(alpha, s, d, links_i, theta)
        alpha = alpha_from_beta(beta, s, d, links_a, theta)
    x = {(i, a): max(0.0, theta[a] * (1 + alpha[a] - beta[i]))
         for i in range(len(s)) for a in links_i[i]}
    return alpha, beta, x

s = [100.0, 100.0]; d = [60.0, 80.0]
links_a = [[0], [0, 1]]   # 每份合约的候选供给
links_i = [[0, 1], [1]]   # 每个供给节点可服务的合约
alpha, beta, x = shale(s, d, links_a, links_i)
# x = {(0,0): 0.6, (0,1): 0.4, (1,1): 0.4}，alpha = beta = [0, 0]

Problem 12.7.4 — 供给节点组合爆炸的量化估算 🔴 Hard

某媒体定向维度为：性别 3 档、年龄 7 档、地域 30 档、兴趣 20 类、平台 3 种。若完全按标签笛卡尔积切分供给节点，估算供给节点数；再假设每份合约平均覆盖 1% 的供给节点、合约数 5000，估算二部图边数与直接 LP 的变量规模，并说明这解释了 12.7.3 的哪个论断。

Sample Input: 维度档数 $\{3,7,30,20,3\}$；覆盖率 1%；合约 5000 Sample Output: 供给节点 $3.78\times 10^6$；边数 $\approx 1.89\times 10^8$；LP 变量同量级

Problem 12.7.5 — 设计一个分配方案的线上监控体系 🏆 Challenge

你是某媒体 GD 系统的负责人，上线 HWM 分配方案两周后，运营反馈「部分合约完成率掉到 85%」。请设计一套诊断流程：列出至少 4 个可能根因（分别来自流量预测、分配算法、频次控制、上游链路），说明每个根因对应的可观测指标与验证方法，并给出修复动作。

Sample Input: 合约完成率周报 + 展示/点击日志 + 合约定向配置 Sample Output: 根因 × 指标 × 验证方法 × 修复动作的对照表