随机规划场景中的两类目标利润概率模型

文章目录 1 引言2 最大化达成目标利润的概率2.1 不考虑缺货损失2.2 考虑缺货损失 3 约束目标利润的达成概率3.1 一维变量3.2 多维变量 4 总结5 相关阅读

1 引言

上个月因回老家结婚和过春节，持续学习的计划暂时被搁置一旁。这个月开始，要重回正轨了。

去年，我总结了几篇关于随机规划的文章：①随机规划：求解报童问题期望值模型的算法方案；②一文了解经典报童模型的扩展问题；③经典报童问题的2类扩展实例：带广告的报童问题和多产品报童问题。在这些文章中，目标函数都是围绕最大化利润的期望值。

本文将不再关注利润的期望值，而是研究与目标利润达成概率相关的两类目标函数：①最大化达成目标利润的概率；②约束目标利润的达成概率。

为更好地说明期望值模型与这两类新模型之间的差异，以下是一个不太严谨的例子：在股票市场中，期望值模型回答的是，投资方案A的平均利润为100万，但对于此次具体投资，利润并不保证；“最大化达成目标利润的概率”模型则表明，要达到100万以上的目标利润，投资方案B的实现概率最高；“约束目标利润的达成概率”模型则告诉我们，要达到100万以上的目标利润，且实现概率不低于90%，可以选择投资方案C。

通常情况下，决策者对不利情况的发生越敏感，越会关注目标利润的达成概率。接下来的内容，将主要介绍如何求解这两类问题。

正文如下。

2 最大化达成目标利润的概率

本节将继续使用报童模型来阐述该类问题的求解方案。

在报童模型中，我们定义如下变量：$ D$ 表示需求量， g ( D ) g(D) g(D) 和 G ( D ) G(D) G(D) 是对应的概率分布函数和累积分布函数； Q Q Q 是订购量； R R R 是售卖价格； C C C 是成本； V V V是滞销损失； S S S 是缺货损失。假设变量满足如下条件： R > C > V R > C > V R>C>V。

实际销量可以表示为： A = min ⁡ ( Q , D ) A = \min(Q, D) A=min(Q,D)

接下来，我们将分别讨论不考虑缺货损失和考虑缺货损失这两种情况。

2.1 不考虑缺货损失

此时 S = 0 S=0 S=0，报童模型的利润表达式可以写为 Z = R A + V ⋅ max ⁡ ( 0 , Q − D ) − C Q Z=RA + V·\max(0,Q-D) - CQ Z=RA+V⋅max(0,Q−D)−CQ 由于 max ⁡ ( 0 , Q − D ) = Q − min ⁡ ( Q , D ) \max(0,Q-D) = Q - \min(Q,D) max(0,Q−D)=Q−min(Q,D)，所以上式等价于 Z = ( R − V ) A − ( C − V ) Q Z = (R-V)A - (C-V)Q Z=(R−V)A−(C−V)Q

假设目标利润为 B B B，则最大化达成目标利润的概率可以表达为 max ⁡ Pr ( Z ≥ B ) \max \text{Pr}(Z≥B) maxPr(Z≥B)

为了求解该问题，假设 Q Q Q为定值，此时 Z Z Z的最大值为 Z m = ( R − C ) Q Z_m=(R-C)Q Zm​=(R−C)Q。因此，如果 B > ( R − C ) Q B>(R-C)Q B>(R−C)Q 那么 Pr ( Z ≥ B ) = 0 \text{Pr}(Z≥B)=0 Pr(Z≥B)=0 反之，令 Z = B Z=B Z=B，可以得到对应的 D B D_B DB​为 D B = B + ( C − V ) Q R − V D_B=\frac{B+(C-V)Q}{R-V} DB​=R−VB+(C−V)Q​ 因此 Pr ( Z ≥ B ) = Pr ( D ≥ D B ) = 1 − G ( D B ) \text{Pr}(Z≥B)=\text{Pr}(D≥D_B)=1-G(D_B) Pr(Z≥B)=Pr(D≥DB​)=1−G(DB​) 从上面几个式子可以看出， Q Q Q越小， D B D_B DB​越小， G ( D B ) G(D_B) G(DB​)越小，而 Pr ( Z ≥ B ) \text{Pr}(Z≥B) Pr(Z≥B)越大。因此，要最大化 Pr ( Z ≥ B ) \text{Pr}(Z≥B) Pr(Z≥B)，应该取 Q Q Q的最小值。结合 B ≤ ( R − C ) Q B≤(R-C)Q B≤(R−C)Q的约束，可得 Q ∗ = B R − C Q^{\ast}=\frac{B}{R-C} Q∗=R−CB​ 这里有个有意思的现象： Q Q Q的最优解，和 D D D的分布没有任何关系。

2.2 考虑缺货损失

此时 S > 0 S>0 S>0，报童模型的利润表达式可以写为 Y = R A + V ⋅ max ⁡ ( 0 , Q − D ) − S max ⁡ ( 0 , D − Q ) − C Q Y=RA + V·\max(0,Q-D) - S\max(0,D-Q) - CQ Y=RA+V⋅max(0,Q−D)−Smax(0,D−Q)−CQ 由于 max ⁡ ( 0 , D − Q ) = S ( D − A ) \max(0,D-Q)=S(D-A) max(0,D−Q)=S(D−A)，所以上式等价于 Y = ( R − V + S ) A − S D − ( C − V ) Q Y=(R-V+S)A - SD - (C-V)Q Y=(R−V+S)A−SD−(C−V)Q

继续假设 Q Q Q为定值，相比不考虑缺货损失时的 Z Z Z， Y Y Y关于 D D D不再是单调函数：当 D < Q D < Q D<Q时，单调递增；当 D > Q D > Q D>Q时，单调递减。即，给定目标利润 B B B后，会同时存在两个恰好达成目标利润的 D D D（不考虑目标利润达不成的情况）。如下图所示。 当 D < Q D < Q D<Q时，令 Y = B Y = B Y=B，可以得到 D 1 = B + ( C − V ) Q R − V D_1=\frac{B+(C-V)Q}{R-V} D1​=R−VB+(C−V)Q​

当 D > Q D > Q D>Q时，仍令 Y = B Y = B Y=B，可以得到 D 2 = ( R − C + S ) Q − B S D_2=\frac{(R-C+S)Q-B}{S} D2​=S(R−C+S)Q−B​ 目标函数可以写为

P = Pr ( Y ≥ B ) = G ( D 2 ) − G ( D 1 ) P=\text{Pr}(Y≥B)=G(D_2)-G(D_1) P=Pr(Y≥B)=G(D2​)−G(D1​) 此时， Q Q Q同时影响 D 1 D_1 D1​和 D 2 D_2 D2​的值，其和 P P P的单调性关系不再容易判断。为了求得 P P P的极值，直接求导 d P d Q = g ( D 2 ) d D 2 d Q − g ( D 1 ) d D 1 d Q \frac{dP}{dQ}=g(D_2)\frac{dD_2}{dQ}-g(D_1)\frac{dD_1}{dQ} dQdP​=g(D2​)dQdD2​​−g(D1​)dQdD1​​ 将 D 1 D_1 D1​和 D 2 D_2 D2​的表达式带入上式，并令其值为0，得到 g ( ( R − C + S ) Q − B S ) R − C + S S − g ( B + ( C − V ) Q R − V ) C − V R − V = 0 g(\frac{(R-C+S)Q-B}{S})\frac{R-C+S}{S}-g(\frac{B+(C-V)Q}{R-V})\frac{C-V}{R-V}=0 g(S(R−C+S)Q−B​)SR−C+S​−g(R−VB+(C−V)Q​)R−VC−V​=0 该等式的根 Q ∗ Q^{\ast} Q∗即为最优解。

举个例子：假设 D ∼ N ( μ , σ 2 ) D \sim N(\mu,\sigma^2) D∼N(μ,σ2)，且 μ = 20 \mu=20 μ=20, σ = 4 \sigma=4 σ=4, R = 6 R=6 R=6, C = 4 C=4 C=4, S = 4 S=4 S=4, V = 1 V=1 V=1, B = 20 B=20 B=20。 运行以下代码，便可以得到，最优解 Q ∗ Q^{\ast} Q∗的值为 20.94 20.94 20.94，对应的最大概率为 0.7503 0.7503 0.7503。

import math from scipy.optimize import fsolve import numpy as np from scipy.stats import norm # 迭代计算模型 def f1(x, mu, sigma): return norm.pdf((6 * x - 20) / 4, mu, sigma) * 3 / 2 - norm.pdf((3 * x + 20) / 5, mu, sigma) * 3 / 5 if __name__ == '__main__': mu = 20 sigma = 4 sol = fsolve(f1, mu, args=(mu, sigma, )) # 使用mu值为初值 max_prob = norm.cdf((6 * sol - 20) / 4, mu, sigma) - norm.cdf((3 * sol + 20) / 5, mu, sigma) print('sol: {}, max_prob: {}'.format(sol, max_prob)) 3 约束目标利润的达成概率

为了求解该类问题，本节考虑如下的机会约束规划模型（CCP） max ⁡ f ‾ \max \quad \overline{f} maxf​ KaTeX parse error: No such environment: eqnarray at position 7: \begin{̲e̲q̲n̲a̲r̲r̲a̲y̲}̲\nonumber \text… 式中， α \alpha α和 β \beta β是约束条件和目标函数的达成概率，这意味着同时限制了目标利润的达成概率和约束条件的满足概率；如果不考虑约束条件，则退化为仅限制目标利润的达成概率。由于上述表达式可以统一为 Pr { g ( x , ξ ) ≤ 0 } ≥ α \text{Pr}\{g(\pmb x,\pmb \xi) ≤ 0 \} ≥ \alpha Pr{g(x,ξ)≤0}≥α 因此，在问题建模时，不必特别关注限制的是目标函数，还是约束条件的达成概率。

CCP的经典求解方法是将其转化为一个等价类，这可以理解为：将原包含随机变量的表达式转化为一个不含随机变量的新表达式，并保证新表达式的解与原公式的解保持一致。

接下来，我们将根据随机变量是一维还是多维分别进行分析。

3.1 一维变量

此时， ξ \xi ξ是一维变量，假设 g ( x , ξ ) = h ( x ) − ξ g(\pmb x,\xi)=h(\pmb x)-\xi g(x,ξ)=h(x)−ξ，则上式转化为 Pr { g ( x ) ≤ ξ } ≥ α \text{Pr}\{g(\pmb x) ≤ \xi \} ≥ \alpha Pr{g(x)≤ξ}≥α 其中， h ( x ) h(\pmb x) h(x)可以为 x \pmb x x的线性或非线性函数， ξ \xi ξ是一维随机变量，累积分布函数为 G ( ⋅ ) G(·) G(⋅)。

由于 Pr { g ( x ) ≤ ξ } = 1 − G ( g ( x ) ) \text{Pr}\{g(\pmb x) ≤ \xi \}=1-G(g(\pmb x)) Pr{g(x)≤ξ}=1−G(g(x))，带入上式，可以得到 g ( x ) ≤ 1 − α g(\pmb x) ≤ 1- \alpha g(x)≤1−α

举个实例： Pr { x 1 2 − x 2 3 ≤ ξ } ≥ 0.90 \text{Pr}\{x_1^2 - x_2^3 ≤ \xi \} ≥ 0.90 Pr{x12​−x23​≤ξ}≥0.90 该约束条件就等价于 x 1 2 − x 2 3 ≤ G − 1 ( 1 − 0.90 ) = 0.7184 x_1^2 - x_2^3 ≤ G^{-1}(1-0.90)=0.7184 x12​−x23​≤G−1(1−0.90)=0.7184

3.2 多维变量

此时， ξ = ( a 1 , a 2 , ⋅ ⋅ ⋅ , a n , b ) \xi=(a_1,a_2,···,a_n,b) ξ=(a1​,a2​,⋅⋅⋅,an​,b)，假设 g ( x , ξ ) g(\pmb x,\pmb \xi) g(x,ξ)的表达式为 g ( x , ξ ) = a 1 x 1 + a 2 x 2 + ⋅ ⋅ ⋅ + a n x n − b g(\pmb x,\pmb \xi) = a_1x_1+a_2x_2+···+a_nx_n - b g(x,ξ)=a1​x1​+a2​x2​+⋅⋅⋅+an​xn​−b 上式中， a i a_i ai​和 b b b相互独立，且均为正态随机变量。

机会约束可以写为 Pr { ∑ i = 1 n a i x i ≤ b } ≥ α \text{Pr}\{\sum_{i=1}^na_ix_i ≤ b\} ≥ \alpha Pr{i=1∑n​ai​xi​≤b}≥α

令函数 y ( x ) = ∑ i = 1 n a i x i − b y(x) = \sum_{i=1}^na_ix_i-b y(x)=i=1∑n​ai​xi​−b 根据正态分布的叠加性， y y y也服从正态分布，且 μ = ∑ i = 1 n E ( a i ) x i − E ( b ) \mu=\sum_{i=1}^nE(a_i)x_i - E(b) μ=i=1∑n​E(ai​)xi​−E(b) σ = ∑ i = 1 n V ( a i ) x i 2 + V ( b ) \sigma=\sum_{i=1}^nV(a_i)x_i^2 + V(b) σ=i=1∑n​V(ai​)xi2​+V(b) 式中， E ( ⋅ ) E(·) E(⋅)和 V ( ⋅ ) V(·) V(⋅)分别为期望值和方差。 再定义新的变量 X X X X = ∑ i = 1 n a i x i − b − ( ∑ i = 1 n E ( a i ) x i − E ( b ) ) ∑ i = 1 n V ( a i ) x i 2 + V ( b ) X = \frac{\sum_{i=1}^na_ix_i-b - (\sum_{i=1}^nE(a_i)x_i - E(b))}{\sqrt{\sum_{i=1}^nV(a_i)x_i^2 + V(b)}} X=∑i=1n​V(ai​)xi2​+V(b) ​∑i=1n​ai​xi​−b−(∑i=1n​E(ai​)xi​−E(b))​ 显然， X X X服从标准正态分布。

针对不等式 ∑ i = 1 n a i x i ≤ b \sum_{i=1}^na_ix_i≤b ∑i=1n​ai​xi​≤b，等价于 ∑ i = 1 n a i x i − b − ( ∑ i = 1 n E ( a i ) x i − E ( b ) ) ∑ i = 1 n V ( a i ) x i 2 + V ( b ) ≤ − ∑ i = 1 n E ( a i ) x i − E ( b ) ∑ i = 1 n V ( a i ) x i 2 + V ( b ) \frac{\sum_{i=1}^na_ix_i-b - (\sum_{i=1}^nE(a_i)x_i - E(b))}{\sqrt{\sum_{i=1}^nV(a_i)x_i^2 + V(b)}} ≤-\frac{\sum_{i=1}^nE(a_i)x_i - E(b)}{\sqrt{\sum_{i=1}^nV(a_i)x_i^2 + V(b)}} ∑i=1n​V(ai​)xi2​+V(b) ​∑i=1n​ai​xi​−b−(∑i=1n​E(ai​)xi​−E(b))​≤−∑i=1n​V(ai​)xi2​+V(b) ​∑i=1n​E(ai​)xi​−E(b)​

所以原约束条件等价于

Pr { X ≤ − ∑ i = 1 n E ( a i ) x i − E ( b ) ∑ i = 1 n V ( a i ) x i 2 + V ( b ) } ≥ α \text{Pr}\{X≤-\frac{\sum_{i=1}^nE(a_i)x_i - E(b)}{\sqrt{\sum_{i=1}^nV(a_i)x_i^2 + V(b)}}\} ≥ \alpha Pr{X≤−∑i=1n​V(ai​)xi2​+V(b) ​∑i=1n​E(ai​)xi​−E(b)​}≥α

到这里，就和一维变量的过程很相似了，此处直接给出上式的化简等价类如下 D − 1 ( α ) ≤ − ∑ i = 1 n E ( a i ) x i − E ( b ) ∑ i = 1 n V ( a i ) x i 2 + V ( b ) D^{-1}(\alpha)≤-\frac{\sum_{i=1}^nE(a_i)x_i - E(b)}{\sqrt{\sum_{i=1}^nV(a_i)x_i^2 + V(b)}} D−1(α)≤−∑i=1n​V(ai​)xi2​+V(b) ​∑i=1n​E(ai​)xi​−E(b)​ 即 ∑ i = 1 n E ( a i ) x i + D − 1 ( α ) ∑ i = 1 n V ( a i ) x i 2 + V ( b ) ≤ E ( b ) \sum_{i=1}^nE(a_i)x_i +D^{-1}(\alpha)\sqrt{\sum_{i=1}^nV(a_i)x_i^2 + V(b)}≤E(b) i=1∑n​E(ai​)xi​+D−1(α)i=1∑n​V(ai​)xi2​+V(b) ​≤E(b)

再举个实例： Pr { a 1 x 1 + a 2 x 2 + a 3 x 3 ≤ b } ≥ 95 % \text{Pr}\{a_1x_1+a_2x_2+a_3x_3≤b\}≥95\% Pr{a1​x1​+a2​x2​+a3​x3​≤b}≥95% 其中 a 1 , a 2 , a 3 a_1,a_2,a_3 a1​,a2​,a3​和 b b b分别服从正态分布 N ( 1 , 1 ) N(1,1) N(1,1), N ( 2 , 1 ) N(2,1) N(2,1), N ( 3 , 1 ) N(3,1) N(3,1)和 N ( 4 , 1 ) N(4,1) N(4,1)。则该式的等价类为 x 1 + 2 x 2 + 3 x 3 + 1.645 x 1 2 + x 2 2 + x 3 2 + 1 ≤ 4 x_1+2x_2+3x_3+1.645\sqrt{x_1^2+x_2^2+x_3^2+1}≤4 x1​+2x2​+3x3​+1.645x12​+x22​+x32​+1 ​≤4

4 总结

正文到此结束，以下是核心内容的总结：

(1) 最大化达成目标利润的概率：以报童问题为例，若不考虑缺货损失，最优解可以通过一个简单的公式得到； 而考虑缺货损失后，这个问题则可以转化为求解根的问题。

(2) 约束目标利润的达成概率：使用机会约束规划模型进行建模，根据随机变量是一维还是多维进行区分，当目标函数为特定类型时，可以将其转化为等价类进行求解。

5 相关阅读

The Newsboy Problem under Alternative Optimization Objectives： link.springer /article/10.1057/jors.1980.96

随机规划与模糊规划： book.douban /subject/1508496/