线上运筹优化公式推导

营销本质是个预算分配问题，即如何在有限资源约束下实现收益最大化。当用户进入营销场景时，我们需要确定是否给该用户发放红包以及发放红包面额。

选择发放用户和发放面额是一个典型的分组背包问题(MCKP, Multiple Choice Knapsack Problem)，在成本约束下的的券核销率最大化。

问题定义

$$min -\sum_{i,j} x_{ij}p_{ij} \\ \begin{aligned} \text { s.t. } x_{ij} & \in \{0, 1\} \\ \sum_{j} x_{ij} &= 1 \\ \sum_{i,j} x_{ij} c_{ij} &\leq C \\ \end{aligned}$$

• $x_{ij}$ 表示是否给用户$i$发放红包$j$
• $p_{ij}$ 表示用户$i$在红包$j$下的核销率，由量价模型预估产生
• $c_{ij}$ 表示给用户$i$发放红包$j$的成本，即红包$j$的面额
• $C$ 表示总成本

构造拉格朗日对偶函数

$$\begin{aligned} L(x, \lambda, u) & =-\sum_{i, j} x_{ij}p_{ij}+ \lambda\left(\sum_{i,j} x_{ij}c_{ij}-C\right) \\ & =\sum_{i,j} x_{ij}\left(-p_{ij}+ \lambda c_{ij}\right) - \lambda C \\ \text { s.t. } &\lambda \geq 0, \ u_i \geq 0, \ \sum_{j} x_{ij} = 1 \end{aligned}$$ $$\begin{aligned} D(\lambda, u) & =\max _{\lambda, u} \min _x L(x, \lambda, u) \\ & =\max _{\lambda, u} \min _x\left(\sum_{i,j} x_{ij}\left(-p_{ij}+ \lambda c_{ij}\right) - \lambda C \right) \\ \text { s.t. } &\lambda \geq 0, \ u_i \geq 0, \ \sum_{j} x_{ij} = 1 \end{aligned}$$

求解最优解

假设给定用户$i$，以及确定发放红包$j^{\prime}$，那么$\sum_{ij!=j^{\prime}} x_{ij}\left(-p_{ij}+ \lambda c_{ij}\right)=0$。为了使剩下的$x_{ij^{\prime}}\left(-p_{ij^{\prime}}+ \lambda c_{ij^{\prime}}\right)$最小，则有：

$$\begin{aligned} j^{\prime} &= argmin_{j} -p_{ij}+ \lambda c_{ij} \\ &= argmax_{j} p_{ij} - \lambda c_{ij} \\ \end{aligned}$$

线上运筹的时候，选择发放$j^{\prime}$红包。