下载掌阅APP，畅读海量书库
立即打开
电信运营商最优定价控制问题是一个离散时间、离散状态的动态规划问题。传统处理此类问题的方法是逆向归纳法。首先，计算最后一期在所有可能 X T 情况下的 V T （ X T ）。然后，根据模型（3-1），可以求解出所有 X T-1 对应的 V T-1 （ X T-1 ）。类似地，可以计算出 V T -2 （ X T -2 ）， V T -3 （ X T -3 ），… V 1 （ X 1 ）。
但这种传统的处理方法有个弊端，就是系统状态较大。它在总数N较小的时候是有效率的，但是，当N较大时，系统状态会随着N指数级增长，产生“维数灾难”。在本书中，N是指市场内用户的总人数，一般来讲，这个人数是巨大的，千万甚至上亿级别。而且，由于状态转移随机，本书考虑的动态规划还是一个随机动态规划。所以，通过计算所有 X t 下的 V t （ X t ）来求解变得不可行。基于此，我们提出了一种近似动态规划求解方法，将超大用户数N近似取为趋近于无穷大 N →∞。
在此，引入一个新的变量 π j，t ，用来表示在第t期期初使用套餐j的用户比例，具体定义如下：
对应地，引入一个新的价值函数
，表示当总用户数趋近于无穷大时的人均收益。对于最后一期
T
，我们定义为：
对于时期 t ，1≤ t < T ，我们定义为：
其中， A t 是一个 J × J 维的矩阵，它的第（ i，j ）个元素是：
而 B t 是一个 J 维的列向量，（ B t ） j = p j，t
在之前的讨论中，我们将离网率
θ
j，t
表示成网络容量
C
和网络总使用量
的函数。等价地，我们也可以将
θ
j，t
表示为
的函数，其中
表示套餐
j
对导致网络拥塞的影响权重。为方便讨论，我们假设当
时，
；当
时，
θ
j，t
（π）=0。这里的Ω是一个临界值，反映了系统状态是否处于拥塞中。
定理3-1：
（证明见附录 A ）
定理3-1证明了当
N
足够大时，我们可以等价地将随机动态规划问题转化为连续状态求解。在下一小节，将展示
比
V
t
（
X
t
）更容易求解。
本节提出了通过混合整数线性规划来等价求解该动态规划问题的方法。该动态规划问题中主要的非线性元素是系统的状态转移方程：
，因为
A
t
和
π
t
都涉及决策变量。为后文讨论简单，我们定义一个新的变量π
0，
t
，表示在第
t
期期初没有加入运营商网络的潜在用户数比例，
，从而产生一个新的系统状态向量
，容易发现
中所有元素的求和为1。因此，系统的状态转移方程
可以等价地表示成
，其中
的展开形式如下：
不难看出，
取决于
p
j，t
和
θ
j，t
，而
p
j，t
是
I
t
的函数，
θ
j，t
依赖于
，所以
相当于是
I
t
和
的函数。
由于网络拥塞与否影响离网率
θ
j，t
，所以当
满足
，即网络不拥塞时，定义
。当
满足
，即网络拥塞时，定义
。对于给定的
I
t
，
S
（
I
t
，0）和
S
（
I
t
，1）都可以看作是给定的参数。于是，系统状态转移方程有了新的表现形式：当套餐开关控制策略是
I
t
，且网络不拥塞时，
；当套餐开关控制策略是
I
t
，且网络拥塞时，
。由于
S
（
I
t
，0）和
S
（
I
t
，1）的引入，系统状态转移方程变成了线性函数。
然后，引入二元决策变量
。对于控制策略
I
t
，如果被使用则
，否则
。根据这一定义，可以得出：
即在每期中只有一个控制策略会被使用。为方便书写，再引入一个二元决策变量
L
t
∈｛0，1｝来表示网络是否拥塞，当网络拥塞即
时，
L
t
=1，否则
L
t
=0。也可以用一个非常大的正数
M
来表现这个逻辑：
此时，系统状态转移方程可以用以下线性方程组来表示：
另外，动态规划模型中还有另外一处非线性项是：
其中
是非线性的。所以，我们引入
，并令
，
。在收益最大化问题中，
会在最优解处得到满足。于是，可以得到：
基于以上准备工作，得到了等价的混合整数线性规划模型。当电信运营商的初始状态（第1期状态）为
时，令它的最优值为
。则混合整数线性规划模型如下：
定理3-2：
，即混合整数线性规划求解的最优值等于动态规划的最优值。
（证明见附录A）
所以，将之前的随机动态规划问题可以等价地转化为混合整数线性规划模型来求解。通过混合整数线性规划，可以帮助运营商最优地、高效地求解动态定价模型。
在将随机动态规划模型等价转化为混合整数线性规划模型后，模型的维度依然很高，由于可能的控制策略 I t 共有2 J 种，总变量个数的规模为O（2 J*T ），所以计算复杂、求解较慢。我们努力寻找使维度降低、规模减小的方法。由于模型的高维度主要是因为每个控制策略下每期新用户选择加入套餐 j 的概率 p j，t （ I t ）导致的，所以尝试不通过穷举而把受控制策略 I t 影响的 p j，t 表示出来。
根据电信行业的实际情况，我们做出如下假设。
假设3-1：对于套餐的a，b，c属性，存在以下关系：
1. a j +1 > a j +（ b j +1 - b j ）/ c j ，∀1≤ j < J ，
2. b 1 < b 2 <…< b J ，
3. c 1 ≥ c 2 ≥…≥ c J .
该假设符合目前电信行业的基本定价规则，即高价位套餐包含的免费流量数与低价位套餐包含的免费流量数的差额的单位流量费用要小于低价套餐的超额后单位流量费用；高价位套餐超出免费流量限额后的单位流量费用要不大于低价套餐超出免费流量限额后的单位流量费用。
图3.3 各套餐流量使用量与价格的关系
因此，如图3.3所示，对于任意套餐
j
，如果1≤
i
1
<
j
<i
2
≤
J
，我们令
表示套餐
i
1
与套餐
j
价格相等时的用户流量使用量，
表示套餐
i
2
与套餐
j
价格相等时的用户流量使用量。则当
时，用户购买套餐
i
1
的价格会低于套餐
j
；当
时，用户购买套餐
i
2
的价格会低于套餐
j
，这两种情况下用户都不会选择套餐
j
。只有当时
，用户购买套餐j的价格才会低于其他套餐的价格，在这种情况下用户才会选择购买套餐j。
基于图3.3，可以把 p j，t 用以下约束表示出来：
其中， F （ X ）表示用户流量使用量的累积分布函数。为形式统一，我们把用户的保留价格表示成套餐0的形式。
令 β j，t 表示在第 t 期加入套餐 j 的新用户的比例， γ j，t 表示在第t期离开套餐 j 的用户的比例。因此， β j，t 可以由以下约束决定：
由于 π 0， t · p j ， t 是个非线性的，所以引入一个新的变量 pp j ， t 来代替 π 0， t · p j，t ，我们定义pp j，t =π 0，t ·p j，t 。则pp j，t 可以由以下约束决定：
此时，约束（3-5）可以转化写成如下形式：
通过以上的分析和转化，得到以下的混合整数线性规划问题：
定理3-3：
（证明见附录A）
所以，我们成功地将之前维度为 O （2 J * T ）的混合整数线性规划模型显著地降低维度到 O （ J * T ），运算复杂度大大降低，运算时间大大加快。从而，该模型可以广泛应用在电信运营商实际的运营中，具有较强的可操作性。