离线运筹求解流程

基于线上运筹优化公式推导，概述一下如何用二分搜索来运筹求解 $\lambda$ 。

原问题 $\sum_{i} max_{j} (p_{ij} - \lambda c_{ij})$ 是一个求解 $\lambda$ 最优值的线性规划问题，其目标是找到使得目标函数最大化的 $\lambda$。我们可以使用二分搜索来求解。

算法描述

输入参数

• $p_{ij}$：核销率
• $c_{ij}$：发券成本

输出

• 求解值 $\lambda$

算法步骤

1. 初始化搜索区间：由于 $\lambda \geq 0$，设置左右初始区间 $[L, R]$ ，其中 $L=0$，$R$ 可以是任意足够大的数
2. 二分循环（直到 $|R-L| \leq \epsilon$：
   1. $m = \frac{L+R}{2}$
   2. 遍历每个用户 $i$，找出券 $j$，使得 $max_{j} (p_{ij} - m c_{ij})$ 最大化
   3. 如果$\sum_{i} max_{j} (p_{ij} - \lambda c_{ij}) \gt C$，表明 $m$ 过小，则更新搜索区间$L = m$，否则 $R = m$
3. 返回结果：$\lambda = m$