基于线上运筹优化公式推导概述一下如何用二分搜索来运筹求解λ \lambdaλ。原问题∑ i m a x j ( p i j − λ c i j ) \sum_{i} max_{j} (p_{ij} - \lambda c_{ij})∑imaxj(pij−λcij)是一个求解λ \lambdaλ最优值的线性规划问题其目标是找到使得目标函数最大化的λ \lambdaλ。我们可以使用二分搜索来求解。算法描述输入参数p i j p_{ij}pij核销率c i j c_{ij}cij发券成本输出求解值λ \lambdaλ算法步骤初始化搜索区间由于λ ≥ 0 \lambda \geq 0λ≥0设置左右初始区间[ L , R ] [L, R][L,R]其中L 0 L0L0R RR可以是任意足够大的数二分循环直到∣ R − L ∣ ≤ ϵ |R-L| \leq \epsilon∣R−L∣≤ϵm L R 2 m \frac{LR}{2}m2LR遍历每个用户i ii找出券j jj使得m a x j ( p i j − m c i j ) max_{j} (p_{ij} - m c_{ij})maxj(pij−mcij)最大化如果∑ i m a x j ( p i j − m c i j ) C \sum_{i} max_{j} (p_{ij} - m c_{ij}) \gt C∑imaxj(pij−mcij)C表明m mm过小则更新搜索区间L m L mLm否则R m R mRm返回结果λ m \lambda mλm 离线运筹求解流程
基于线上运筹优化公式推导概述一下如何用二分搜索来运筹求解λ \lambdaλ。原问题∑ i m a x j ( p i j − λ c i j ) \sum_{i} max_{j} (p_{ij} - \lambda c_{ij})∑imaxj(pij−λcij)是一个求解λ \lambdaλ最优值的线性规划问题其目标是找到使得目标函数最大化的λ \lambdaλ。我们可以使用二分搜索来求解。算法描述输入参数p i j p_{ij}pij核销率c i j c_{ij}cij发券成本输出求解值λ \lambdaλ算法步骤初始化搜索区间由于λ ≥ 0 \lambda \geq 0λ≥0设置左右初始区间[ L , R ] [L, R][L,R]其中L 0 L0L0R RR可以是任意足够大的数二分循环直到∣ R − L ∣ ≤ ϵ |R-L| \leq \epsilon∣R−L∣≤ϵm L R 2 m \frac{LR}{2}m2LR遍历每个用户i ii找出券j jj使得m a x j ( p i j − m c i j ) max_{j} (p_{ij} - m c_{ij})maxj(pij−mcij)最大化如果∑ i m a x j ( p i j − m c i j ) C \sum_{i} max_{j} (p_{ij} - m c_{ij}) \gt C∑imaxj(pij−mcij)C表明m mm过小则更新搜索区间L m L mLm否则R m R mRm返回结果λ m \lambda mλm