第４１卷第４期数学的头践与认识Ｖｂｌ．４１．Ｎｏ．４２０１１年２月ＭＡＴＨＥＭＡＴＩＣＳＩＮＰＲＡＣＴＩＣＥＡＮＤＴＨＥＯＲＹＦｅｂ．．２０１１
基于航段需求计算网络竞价的近似动态规划方法
刘风，，一，吴祈宗・，王亚楠３，崔春生４
（１．北京理工大学管理与经济学院，北京１０００８１）
（２．中央司法警官学院信息管理系，河北保定０７１０００）
（３．河北科技大学经济管理学院，河北石家庄０５００１８）
（４．中国电子信息产业发展研究院中国软件评测中心，北京１０００６６）
摘要：竞价控制是收益管理中广泛应用的一种存量控制方法．将网络存量控制问
题描述为一个动态规划模型，通过状态向量的一个仿射函数近似动态规划的最优值
函数，并且在航段水平上考虑随机需求，最终得到一个计算网络竞价所需的确定性
线性规划（ＤＬＰ），相对于标准的ＤＬＰ，这个ＤＬＰ得到了更接近于动态规划最优值
的上界．给出了一个列生成算法用于求解这个ＤＬＰ，并提供了模拟算例，计算结果
表明可获得比标准的ＤＬＰ方法更好的收益．
关键词：网络收益管理；动态规划；竞价控制
１引言
．收益管理中的网络存量控制问题可描述为一个动态规划模型，但由于状态空间的维度过于巨大，要得到这个模型的精确解基本上是不可能的，唯一实用的方法是尽量对决策问题近似化【１１．在各种近似方法中，Ｄ’Ｓｙｌｖａｉ２】和Ｇｌｏｖｅｒ等【３】提出的确定性线性规划（ＤＬＰ）方法可能是最广为人知，也是最简单的一个例子．这种方法的主要不足在于它只考虑需求的期望值而忽略了需求预测中的所有不确定性．
由近似方法所得到的最有用的结果是对竞价的估计．Ｓｉｍｐｓｏｎ［４】和Ｗｉｌｌｉａｍｓｏｎ［５】介绍了竞价控制的思想并提出把决策问题构建为各种数学规划，将其对偶价格作为竞价的近似值．以航空客运业为例，航空公司的资源是客运网络中各航节的存量，产品则是网络中各航线上特定价格等级的座位，同一航线，不同价格等级的座位属于不同的产品．竞价是每个航节（资源）的阈值．在资源允许的前提下，对于一个产品（某一航线上特定价格等级的座位）的预订请求，竞价控制意味着只有当产品的价格超过了它所使用的全部资源（航节）的竞价总和时，产品才会被出售，即接受预订．
网络收益管理中的大多数存量控制模型针对产品（特定航线与价格等级的组合）考虑不确定性需求．Ｈｉｇｌｅ［６】和ＢｕｒａｋＢｉｉｋｅ等［７】研究了基于航段需求的随机规划（ｓＰ）模型．随着消费者选择购买不同航线或不同价格等级的机票可到达同一目的地的机会的增加，探索基于航段考虑随机需求的模型将会变得日益重要．出于此种考虑，这篇文章主要集中于建立一个基于航段需求计算网络竞价的易处理模型及求解算法，并通过模拟算例与标准的ＤＬＰ方法收稿日期：２０１０－１０—１４资助项目：国家自然科学基金（６０９７９７０１０）
５０数学的实践与认识４１卷进行对比．
２问题描述
在这一节中将给出对决策问题的基本描述以及贯穿全文所使用的符号．
２．１马尔科夫决策过程描述
模型是一个时间离散且有界的马尔科夫决策过程．目标是使总的期望收益最大化．
首先，假设一个包含ｍ个航节（资源）的航空客运网络，航节ｉ∈Ｉ＝｛１，２，…，ｍ）．整个网络有ｉ个航段，航段ｎ∈Ｎ＝｛１，２，…，ｚ｝．航节的不同组合构成了网络中各航段上的航线，对于一个给定的航段礼可能有多条航线，ｒ∈风＝｛１，２，…，ｆ心Ｉ）表示属于航段礼的航线，ｌ凰ｆ是集合Ｒ。的势．航空公司销售ｋ种产品，铲品Ｊ∈Ｊ＝｛１，２，…，忌）．设山∈Ｊ是属于航线ｒ的产品集合．・
定义关联矩阵Ａ＝【ｏ‘，，】，其中，如果航线ｒ使用航节ｉ，ａｉ，，＝１，否则，８小＝０．矩阵Ａ的第ｒ列，记为∥，表示航线ｒ所使用航节的集合．
时间是离散的，ｔ表示任意的＿个时段，总共有Ｔ个时段．
需求定义在航段的水平上．每个时段ｔ内，至多有一名顾客到达，顾客到达的概率为阮。，没有顾客到达的概率为１一∑Ｐ协．．
ｎＥＮ
网络的状态由剩余航节存量向量ｚ＝０１，…，茁。）描述，初始状态由初始存量向量ｃ＝（ｃ１，…，ｃ。）表示．向量ｚ满足
ｚ∈托三∽，【｛ｚ∈．ｍ：鼢∈｛ｏ，１，…，Ｑ）Ｖｉ｝，当ｔ＝２，…，Ｔ
如果出售了航线ｒ的一个座位，网络的状态变为ｚ—Ａ’，忽略顾客不到和退订的情况．给定当前的时段ｔ和当前剩余航节存量向量ｚ（ｔ），当接到一个预订请求时，预订系统必卦“，须决定是否接受这个预订．
虽然需求是基于航段的，但必须针对产品（特定航线与价格等级）制定决策．设忌维向量．札表示这个决策，如果接受一个对航线ｔ和价格等级Ｊ的座位．（产品）预订，Ｕｒｊ＝１，否则，Ｕｒｊ＝ｏ．一般地，决策ｕｒＪ是剩余存量向量ｚ和机票价格，ｒＪ的函数，即ｕ，Ｊ＝Ｕｒｊ（ｚ，南），其中，Ｊ∈五Ⅶ，ｒ∈％，ｎ∈Ｎ．由于在任一时段内至多只有一个预订请求，并且不考虑不到和退订，因此决策向量ｕ属于集合
．ｕ（ｚ）＝｛ｕ∈｛０】１）七：∑∑肌，ｊ≤ｚ｝‘ｈＥＮｒＥＲ。，ｊ∈凡
如果系统接受了一个对航线ｒ和价格等级Ｊ的座位预订，即ｕｒＪ＝ｌ，将获得收益南＞０，并且资源将按照矩阵Ａ的第ｒ列，∥，消耗．如果没有足够的资源可以满足预订，请求将被拒绝，当然也没有收益．即使有足够的资源，但如果将这些资源提供给潜在的未来顾客能够获得更多收益，当前的预订请求也可能被拒绝．
设Ｖ。（ｚ）是在时段￡的期初，状态为ｚ，经过时期ｔ，…，Ｔ所获得的最大的总期望收益，那么Ｖ。（ｚ）必须满足贝尔曼方程．
嘶）：１１１ｕＥａＸＵ｛三Ｐｔ，ｎ［，∈纛ＪｒｆｒｊＵｒｊ－＿Ｉ－Ｖｔ－ｋｌ（一，∈磊＾∥ｕ巧）］＋
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５１
（・一∑ｐｔ＇。）阱・（ｚ）ＭｎＥＮ
边界条件为卯＋ｌ（ｚ）＝０Ｖｘ．
当初始状态为ｃ时，（１）式的值函数可通过下面的线性规划计算，
（ＤＯ）ｍ，ｉｎ、
”Ｌ。ＪＶｌ（ｃ），、
ｓ．ｔ．仇ｉｚ）≥∑Ｐ狮［∑加让，ｊ＋饥＋，（ｚ一∑∥ｕ巧）］＋ｈＥＮｒ∈Ｒｎ，Ｊ∈山ｒＥＲ竹，ｊ∈Ｊ，
（１一∑Ｐｔ，ｎ）阱１（。）ｖｔ，ｚ∈托，ｕ∈ｕ（ｚ）
ｈＥＮ
决策变量为饥（ｚ）Ⅵ，。∈Ｘｔ．通过归纳法容易证明，（Ｄｏ）的任意可行解砚（・）是方程（１）的最优值仇（・）的一个上界，相关证明参见文献［８】．
２．２（ＤＬＰ）描述
由于状态空间的维度过大，一般情况下，（１）式和（ＤＯ）都很难精确求解．因此，在收益管理中，标准的方法是忽略时间的动态性，转而求解一个更简单的ＤＬＰ．标准的ＤＬＰ根据需求的期望值分配存量，这种方法假设每名顾客申请预订某一产品（特定航线和价格等级的座位），如果这个产品已经售完，顾客将离开系统．与之不同的是，这篇文章假设每名顾客申请预订某一特定航段（而不是特定航线和价格等级）的座位，当这个航段拥有多条航线时，即使某条航线的机票已经售完，顾客仍可能选择预订这个航段中其他航线的座位．设％表示在最后一个时段结束Ｈ寸＇分配给航线ｒ上价格等级为Ｊ的期望座位数，则（ＤＬＰ）模型如下：
（ＤＬＰ）ＺＤＬＰ＝ｍ。ａｘ∑∑如％
ｎＥⅣｒＥＲ。，Ｊ∈Ｊｒ（２）
（３）
（４）ｓ，ｔ．∑∑ａｉ，，％≤ｃｉ，ＶｉｈＥＮｒＥ如，ｊ∈Ｊｒ０≤∑‰≤∑Ｐ抽，Ｖｎ一ＺＪ。Ｊ—Ｚ√。＇…
ｒ∈Ｒ。，Ｊ∈Ｊｒｔ、７
蚱ｊ≥０，Ｖｎ，７．∈Ｒ。，Ｊ∈矗、
其中，需求是在航段的水平上加以考虑的．实际上，（ＤＬＰ）是标准的ＤＬＰ在航段需求下的一种扩展．（ＤＬＰ）的对偶形式如下：
骝∑ｃｉＴｒｉ＋∑（∑ｐｔ＇ｎ）ｐｎ
吼加
。＋ｐｎ＞一抽Ｖｎｒ∈昆ｎ∈‘∑州＂＞一其中，７ｒｉ是约束（３）的对偶价格（即航节ｉ的竞价），ｐ。是约束（４）中右端不等式的对偶价格．设丌；和麻表示最优的对偶价格．在资源允许的前提下，假设有一个对航线ｒ和价格等级Ｊ的座位预订请求，按照竞价控制的思想，如果
，ｒＪ≥∑ａｉ，，砖ｖｎ，ｒ∈％，Ｊ∈Ｊｒ
ｉＥＪ
就接受预订，否则将拒绝此预订．
５２数学的实践与认识４１卷３函数近似
如前所述，（ＤＯ）含有大量的决策变量和约束条件，很难精确求解．使之得以简化的一种方式是通过一系列基本函数来近似仇（・）．本节首先用一系列仿射函数来近似饥（・），并给出由此而得到的原规划和对偶规划．其次，建立对偶规划和（ＤＬＰ）的联系．
３．１描述
考虑下面的仿射函数近似：
饥（。）≈仇＋∑巩，‘甄
ｔ
其中巩是常量补偿，丌ｔ，‘是在时段ｔ航节ｉ的竞价，０Ｔ＋１＝０，７ｒＴ＋ｌ，ｔ＝ｏ，Ｖｔ．
将（６）式代入（Ｄｏ）得到
（Ｄ１）ｍ日ｉ。ｎ６１＋∑７ｒｌ，｛ｑ
ｓ．ｔ．巩一‰・＋∑ｈ溉一，Ｔｔ＋ｌ，ｉ（戤一∑Ｐｔ，ｎ∑％ｒ牡巧）］
≥∑仇，。
（Ｄ１）的对偶模型如下：∑局乱啊Ⅵ，ｚ∈五，ｕ∈Ｕ（ｚ）
（Ｐ１）钠＝峄∑（∑巩。∑＾牡，ｊ）孙，。
ｆ龟，当江１
ｓ．ｔ’础‰蛳忍俨｛纛＿擘ｎＥＮ≯ｒＥＲ∑，。，ｊＥ凡％胁¨州６）
∑，‰胪｛蚝ｘｔｍ∈Ｕ婶）
７≥０ｆ１，ｉｆ扛１ＬｚＥＸｔ乩ｕｅＵ（ｚ）‘∑¨＾。，Ⅵ－２＇…，Ｔ（７）
约束（７）意味着
≥：ｍ，掣＝１，Ⅵ（８）
因此决策变量ｍ忍。可解释为状态．行动概率，即＂／ｔ尚。表示在时段ｔ，状态为ｚ，做出决策Ｕ的概率．（６）式为流量平衡约束．
３．２与（ＤＬＰ）的联系
为了由（Ｐ１）得到（ＤＬＰ），定义
％＝∑（ｐｔ’。ｕｒＪ）Ｔｔ而。，ＶＶ∈取，Ｊ∈Ｊｒ（９）
由于９＇ｔ。啪可解释为在时段ｔ，状态为ｚ，做出决策ｕ的概率，（９）式右端的含义就是当最后一个时段结束时，提供给航线ｒ上价格等级为Ｊ的期望座位数，这也正是（ＤＬＰ）中决策变量％的含义．这样，（Ｐ１）的目标函数可写作：
∑（∑Ｐｔ，。∑九“，ｊ）‰一＝∑∑加‰
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５３
现在，固定ｉ，将（６）式对ｔ加总得到
∑ｘｉ＂／ｔ而ｕ
￡，ｚ∈ｘｔ，ｕ∈ｃ，（ｚ）
＝ｃｉ＋。∑（戤一∑仇－１＇。‘ｈＥＮ∑ｒ∈Ｒｎ，Ｊ∈Ｊ－口印％）ｍ－１＇舭
（１０）ｔ＝２，…，Ｔ，ｚＥＸｔ—ｌ，ｔ‘∈￡，（。）上式化简后得到ｑ＝∑∑ｐ抽∑
∑
＂ｈｅＮｒＥＲｎ，Ｊ∈Ｊｒｔ＝ｌ，…，Ｔ一１，ｘＥＸｔ，ｕ∈ｕ（￡）ｈＥＮｒＥＲｎ，ｊＥＪｒ‘∑Ｘｉ＇ＩＴ忍。（。妒札巧）弧州＋ｚＥＸｔ，ｕｅＵ（ｘ）ＥｒＥＲｎ，Ｊ∈ＪｒｎＥＮ由集合ｕ的定义知瓢≥∑
此，（１０）式意味着
Ｑ≥ａｉ，，乱，ｊ忱，故ｘｉ≥∑Ｐｔ，ｎａｉ，，让，ｊＶｉ．因∑
ｔ，ＺＥＸｔ，“∈【，（ｚ）
ｎＥＰ咖∑（。时Ｕｒｊ）“／ｔ而。ｔｌｒ∈ｔｋ，Ｊ∈Ｊｒ＝∑∑ａｉ，ｒｒＥＲｎ，ｊ∈凡∑ｔ，ｚＥＸｔ，ｔ‘∈ｕ（。）（ｐｔ，。扎ｒｊ）‰，。＝∑∑ａｉ，ｒ％，Ｖｉｎｒ∈Ｒｎ，ｊ∈Ｊｒ
从而得到了（３）式．另由（９）式可得
∑％＝∑
ｒ∈Ｒｎ，Ｊ∈Ｊｒ∑（ｐｔ，。ｕｒＪ）‰，。
∑ｕ，ｊＴｔ，刚ｒＥＲｎ，ｊｅＪｒｔ，ｚＥＸｔ，ｔ‘∈ｕ（ｚ）＝∑仇，。∑
ｔｒＥＲｎ，ｊ∈．７●ｘＥＸｔ，ｔ‘∈￡，（ｏ）
ｓ∑Ｐ帅
ｔ∑ｚＥＸｔ，ｕ∈ｃ，（￥）‰，。＝∑Ｐ加，Ｖｎ‘
即产生了（４）式中右端的不等式．
上述讨论表明ＺＤＬＰ≥Ｚｐｌ．如前所述，（ＤＯ）的任意可行解瓴（・）是方程（１）的最优值仇（・）的一个上界，由于（Ｐ１）一（Ｄ１）给出Ｙ（Ｄ０）的一个可行解，因此，Ｚｐｌ≥Ｖｌ（Ｃ）．下面的命题总结了这些结论．
命题１（Ｐ１）的任意可行解均是（ＤＬＰ）的可行解，且有相同的目标函数值．因此，ＺＤＬＰ≥ＺｐＩ≥Ｖｌ（ｃ）．
文献【９】证明了上界ＺＤＬＰ是渐进最优的，即随着时间的流逝，需求不断实现，各航节的存量不断消耗，ＺＤＬＰ逐渐收敛于ｕ１（ｃ），由命题１知Ｚｐｌ也是渐进最优的．
４列生成算法
（Ｐ１）中虽然含有大量的变量，但约束条件相对较少，因此可以考虑用列生成算法对其求解．变量ｍ＾。使名Ｐ・减少的收益ｈ，。，。的检验数）可表示为：
咄刚＝∑ｐ抽
ｎ∑ｒ∈Ｒ竹，ｊ∈Ｊｒ（岛一∑口ｔＩｒ丌ｔ＋１’ｔ）ｕ订一∑（７ｒｔｒ７ｒｔ＋ｌ，ｉ）翰一巩＋‰・ｔ‘
命题２吼禹。＝｛：：翼暑，ｚ
２ｃＩ钆＝０’Ⅵ，。，ｕ是（Ｐ１）的一个可行解．证明对于所有的ｔ和ｉ，（６）式左端有∑ｚｔ‰。＝ｑ‰ｏ＝Ｑｚ∈ｘｔ，ｕ∈Ｕ（￥）．
数学的实践与认识４１卷
并且对于所有的ｔ＞１，（６）式石端有
∑
ｘＥＸｔ一１，ｕ∈ｕ（茁）∑口｛’，％）讯－ｌ＇叫＝ｃｔ讯＿１１ｃ，ｏ＝ｑ（翰一∑ｐ¨，。ｔＥＲｎ，ｊ∈山ｎ
由命题２给定的（Ｐ１）的一个初始可行解可得（Ｄ１）的解为目，丌，下面解
船吼ｍ胀ａｘ帅，Ｗｔ，ｘｕ＝们眠ｍ艇ａｘ吣，Ｅ。Ｐｔ，ｎ懈Ｅ棚∈＾（护≯ｍ扎ｔ）盱
∑（％一巩＋１’ｉ）觑也＋０ｔ＋１
如果上式的最优函数值非正，那么（Ｐ１）就已经达到了最优，否则，将得到的列（上式的解）增加到（Ｐ１）中已经存在的列（解）中．对固定的ｔ＞１，这相当于求解下面的整数规划．
鼍警∑ｐ伽
ｎ∈Ｎ∑（如一∑。妒７ｒｔ＋ｌ’ｔ）ｕｒｊ—Ｅ（％一叭埘）％一巩＋吼＋１（１１）（１２）
（１３）ｓ．ｔ．∑Ｅ。寸ｕ，ｊ≤％ＶｉｒＥＲ。，Ｊ∈Ｊ，ｕ，ｊ∈｛ｏ，１），Ｖｎ，ｒ∈Ｒ。，Ｊ∈Ｊｒ
Ｘｉ∈｛ｏ，…，Ｑ），Ⅵ
定义ｕ；＝’（１４）’。ｚ∈．Ｘｔ，ｔ‘∈Ｕ（ｚ）ｍａｘ．，眦而。Ⅵ是在ｔ时段口，７ｒ情况下印】减少的最大收益．‘‘
命题３设善是决策变量ｍｍ。的所有可能下标的一个子集，称仅含有下标属于集合∈的决策变量的（Ｐ１）为受限制的（Ｐ１），记为（Ｐ１（∈））．若（彳，（百，亓））分别为（Ｐ１（毒））及其对偶问题的解，耐是根据舀和亓计算ｕ；得到的值，翟为（Ｐ１（专））的最优目标函数值，则有
Ｔ
Ｚｐｌ≤翟＋Ｅ
ｔ＝ｌ０～９ｔ．
证明考虑（Ｐ１）的任意可行解７，和任意数量的０ｔ和？ｒｔ，ｉＶｔ，ｉ．对每一个ｔ，ｉ，（６）式两边乘以丌ｔ，ｉ并加上巩，然后把所得方程与
ｚ（，ｙ）＝∑（∑Ｐ枷∑加札巧）‰，。
ｔ，茁，ｔＩｈＥＮｒＥＲｎ，Ｊ∈Ｊｒ
合并可得
ｚ（，ｙ）一∑丌１，ｉＣｘ一日，＝∑ｗｔ，ｘ，ｕＴｔ，叩≤∑ｕ；‰，。＝∑ｕ；（∑‰，。）＝∑ｕ；
ｔｔ，￥，ｕ．ｔ，Ｘ，ｔ‘ｔｚ，ｕｔ
其中，最后的等式是根据（８）式所得．对（Ｐ１）所有的可行解７，上式均成立，特别地，对于（Ｐ１）的一个最优解７木，其目标函数值为Ｚｎ木）＝Ｚｐｌ．进而，由受限问题（Ｐ１＠＂的强对偶性可得
∑亓¨ｑ一百１＝ｚ（彳）＝旅
ｉＧｌ
Ｔ
因此，有ＺＰｌ≤誓＋∑硪．
对于（ＰＩ），命题３给出了最优值Ｚｐ・与一个给定下标属于集合毒的可行解的目标函数值翟之间差的一个上界．若使翟比Ｚｐｌ不超过Ｑ，即，Ｚｐｌ／Ｚｅ≤１＋Ｑ，须满足七－≤Ｑ．此式可作为列生成算法的停机标准，完整的算法见图１．
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５５
列生成算法
令∈＝｛（ｔ，ｃ，０）ｖｔ｝，解受限问题（Ｐ１（∈）），并对所有的ｔ，令ｕ；＝ｏｏ
ｗｈｉｌｅＥ沈＞磁Ｑｄｏ
ｔ
对所有的ｔ∈｛１，…，Ｔ）
计算ｕ；＝ｍａｘｗｔ禹ｕ
正・Ｕ
选择一个（ｚｔ，ｕｔ）∈ａｒｇＩＴｌａｘｔｏｔ＾ｕ
Ｚ・Ｕ
更新∈一毒Ｕ｛（ｔ，耽，ｕｔ））．
解（Ｐ１（∈））
图ｌ求解（Ｐ１）的列生成算法
５模拟算例
图２是一个假设的航空客运网络，这个网络包含５个航节，６个航段和１０条航线．而且，每条航线有３个价格等级（商务，休闲一１和休闲一２）．商务票价服从均值为２００的泊松分布，休闲一１的票价服从均值为１００的泊松分布，休闲一２的票价服从均值为５０的泊松分布．需求是平稳的，简单起见，设每个时段没有顾客到达的概率为ｏ．２．模拟Ｔ∈｛２０，５０，１００，２００，４００｝５种情况．对每种情况，每个航节的初始存量均为ｃ．算例尝试比较求解（Ｐ１）与（ＤＬＰ）产生的上界以及各自执行竞价控制策略所得到的总期望收益．借助ＭＡＴＬＡＢ，设Ｑ＝５％，求解（Ｐ１）一（Ｄ１）和（ＤＬＰ），每个算例对（Ｐ１）一（Ｄ１）与（ＤＬＰ）用相同的顾客需求序列分别执行竞价控制藻略，模拟１００次，计算结果见表１．
图２—个具有５个航节、６个航段和１０条航线的假设航空客运网络表１上界和总期望收益
５６数学的实践与认识４１卷６结束语
需求主要是根据以往的销售数据进行预测，而这些数据是基于产品（特定航线和价格等级）的．对于给定的一个航段，可能包含多条航线，在这种情况下，要分辨出顾客属于哪条航线或哪个价格等级并不是一件容易的事，这就增加了需求预测的难度．在这篇文章中，需求是基于网络中的航段而非产品．对此，可利用当前基于产品的需求预测技术，即对每个航段中相关航线和价格等级的需求进行加总以提高预测的准确性．
文章首先由动态规划入手，对动态规划的最优值函数做仿射函数近似，得到一个基于航段需求，用于计算网络竞价的ＤＬＰ模型．相对于标准的ＤＬＰ，这个ＤＬＰ模型得到了更接近于动态规划最优值的上界．然后提供了一个列生成算法用于求解这个ＤＬＰ，计算结果验证了上述结论并表明可获得比标准的ＤＬＰ方法更好的收益．
参考文献
【１】ＴａｌｌｕｒｉＫＴ，ｖａｎＲｙｚｉｎＧＪ．ＴｈｅＴｈｅｏｒｙａｎｄＰｒａｃｔｉｃｅｏｆＲｅｖｅｎｕｅＭａｎａｇｅｍｅｎｔ［Ｍ］．Ｂｏｓｔｏｎ：Ｋｌｕｗｅｒ
ＡｃａｄｅｍｉｃＰｕｂｌｉｓｈｅｒｓ，２００４：８８－９２．
［２】Ｄ’ＳｙｌｖａＥ．ＯＤｓｅａｔａｓｓｉｇｎｍｅｎｔｔｏｍａｘｉｍｉｚｅｅｘｐｅｃｔｅｄｒｅｖｅｎｕｅ［Ｒ］．Ｓｅａｔｔｌｅ：ＢｏｅｉｎｇＣｏｍｍｅｒｃｉａｌ
ＡｉｒｐｌａｎｅＣｏｍｐａｎｙ，１９８２．
【３】ＧｌｏｖｅｒＦＲ，ＧｌｏｖｅｒＪ，ＬｏｒｅｎｚｏＣ．Ｍｃｍｉｌｌａｎ．Ｔｈｅｐａｓｓｅｎｇｅｒ－ｍｉｘｐｒｏｂｌｅｍｉｎｔｈｅｓｃｈｅｄｕｌｅｄａｉｒｌｉｎｅｓ［Ｊ］．
Ｉｎｔｅｒｆａｃｅｓ．１９８２，１２：７孓７９．
［４】ＳＩＭＰＳＯＮＲＷ．ＵｓｉｎｇＮｅｔｗｏｒｋＦｌｏｗＴｅｃｈｎｉｑｕｅｓｔｏＦｉｎｄＳｈａｄｏｗＰｒｉｃｅｓｆｏｒＭａｒｋｅｔａｎｄＳｅａｔ
ＩｎｖｅｎｔｏｒｙＣｏｎｔｒｏｌ［Ｍ］．Ｍａｓｓａｃｈｕｓｅｔｔｓ：ＭＩＴＦｌｉｇｈｔＴｒａｎｓｐｏｒｔａｔｉｏｎＬａｂｏｒａｔｏｒｙＭｅｍｏｒａｎｄｕｍ，Ｍ８９－１，Ｃａｍｂｒｉｄｇｅ，１９８９．
［５】ＷｉｌｌｉａｍｓｏｎＥＬ．Ａｉｒｌｉｎｅｎｅｔｗｏｒｋｓｅａｔｃｏｎｔｒｏｌ：ｍｅｔｈｏｄｏｌｏｇｉｅｓａｎｄｒｅｖｅｎｕｅｉｍｐａｃｔｓ［Ｄ］．ＰｈＤｔｈｅｓｉｓ，
Ｍａｓｓａｃｈｕｓｅｔｔｓ：ＭＩＴＦｌｉｇｈｔＴｒａｎｓｐｏｒｔａｔｉｏｎＬａｂｏｒａｔｏｒｙ，Ｃａｍｂｒｉｄｇｅ，１９９２．
【６】ＨｉｇｌｅＪＬ．Ｂｉｄ－ｐｒｉｃｅｃｏｎｔｒｏｌｗｉｔｈｏｒｉｇｉｎ－ｄｅｓｔｉｎａｔｉｏｎｄｅｍａｎｄ：ａｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇａｐｐｒｏａｃｈ［Ｊ］．
ＪｏｕｒｎａｌｏｆＲｅｖｅｎｕｅａｎｄＰｒｉｃｉｎｇＭａｎａｇｅｍｅｎｔ，２００７，５（４）：２９１－３０４．
【７】ＢｕｒａｋＢｉｉｋｅ，ＵｔｋｕＹｉｌｄｉｒｉｍａｎｄＨａｒｕｎＡｈｍｅｔＫｕｙｕｍｃｕ．Ｎｅｗｓｔｏｃｈａｓｔｉｃｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ
ａｐｐｒｏｘｉｍａｔｉｏｎｓｆｏｒｎｅｔｗｏｒｋｃａｐａｃｉｔｙｃｏｎｔｒｏｌｐｒｏｂｌｅｍｗｉｔｈｂｕｙ－ｕｐｓ［Ｊ］．ＪｏｕｒｎａｌｏｆＲｅｖｅｎｕｅａｎｄＰｒｉｃｉｎｇＭａｎａｇｅｍｅｎｔ，２００８，７（１）：６１—８４．
【剐ＡｄｅｌｍａｎＤ．Ｄｙｎａｍｉｃｂｉｄ—ｐｒｉｃｅｓｉｎｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ［Ｊ］．ＯｐｅｒＲｅｓ，２００７，５５（４）：６４７・６６１．
【９】ＣｏｏｐｅｒＷＬ．Ａｓｙｍｐｔｏｔｉｃｂｅｈａｖｉｏｒｏｆａｎａｌｌｏｃａｔｉｏｎｐｏｌｉｃｙｆｏｒｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ
Ｒｅｓｅａｒｃｈ，２００２，５０：７２０－７２７．
【１０】ＴａｌｌｕｒｉＫＴ，ｖａｌｌＲｙｚｉｎＧＪ．Ａｎａｎａｌｙｓｉｓｏｆｂｉｄ—ｐｒｉｃｅｃｏｎｔｒｏｌｓｆｏｒｎｅｔｗｏｒｋｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ［Ｊ］．
ＭａｎａｇｅｍｅｎｔＳｃｉ，１９９８，４４（４）：１５７７－１５９３．
【１１】ＴａｌｌｕｒｉＫＴ，ｖａｎＲｙｚｉｎＧＪ．Ａｒａｎｄｏｍｉｚｅｄｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄｆｏｒｃｏｍｐｕｔｉｎｇｂｉｄｐｒｉｃｅｓ［Ｊ］．
ＴｒａｎｓｐｏｒｔａｔｉｏｎＳｃｉ，１９９９，３３（２）：２０７—２１６．
【１２】ＷｏｌｌｍｅｒＲＤ．Ａｎａｉｒｌｉｎｅｓｅａｔｍａｎａｇｅｍｅｎｔｍｏｄｅｌｆｏｒａｓｉｎｇｌｅｌｅｇｒｏｕｔｅｗｈｅｎｌｏｗｅｒｆａｒｅｃｌａｓｓｅｓｂｏｏｋ
ｆｉｒｓｔ［Ｊ】．Ｏｐｅｒ．Ｒｅｓ，１９９２，４０：２６－３７．
【１３］ＺｈａｎｇＤ，ＡｄｅｌｍａｎＤ．Ａｎａｐｐｒｏｘｉｍａｔｅｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇａｐｐｒｏａｃｈｔｏｎｅｔｗｏｒｋｒｅｖｅｎｕｅｍａｎ—
ａｇｅｍｅｎｔｗｉｔｈｃｕｓｔｏｍｅｒｃｈｏｉｃｅ［Ｊ］．ＴｒａｎｓｐｏｒｔａｔｉｏｎＳｃｉ，２００９，４３（３）：３８１—３９４．
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５７ＡｎＡｐｐｒｏｘｉｍａｔｅＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇＡｐｐｒｏａｃｈｆｏｒＣｏｍｐｕｔｉｎｇＮｅｔｗｏｒｋＢｉｄＰｒｉｃｅｓｗｉｔｈＦｌｉｇｈｔＳｅｇｍｅｎｔ
Ｄｅｍａｎｄｓ
ＬＩＵＦｅｎ９１，一，ＷＵＱｉ—ｚｏｎ９１，ＷＡＮＧＹａ－ｎａｎ３，ＣＵＩＣｈｕｎ－ｓｈｅｎ９４
（１．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔａｎｄＥｃｏｎｏｍｉｃｓ，ＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１０００８１，Ｃｈｉｎａ）
（２．ＤｅｐａｒｔｍｅｎｔｏｆＩｎｆｏｒｍａｔｉｏｎＭａｎａｇｅｍｅｎｔ，ｔｈｅＣｅｎｔｒａｌＩｎｓｔｉｔｕｔｅｆｏｒＣｏｒｒｅｃｔｉｏｎａｌＰｏｌｉｃｅ，Ｂａｏｄｉｎｇ０７１０００，
Ｃｈｉｎａ）‘’
（３．ＣｏｌｌｅｇｅｏｆＥｃｏｎｏｍｉｃａｎｄＭａｎａｇｅｍｅｎｔ，ＨｅｂｅｉＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｓｈｉｊｉａｚｈｕａｎｇ０５００１８，
Ｃｈｉｎａ）
（４．ＣｈｉｎａＣｅｎｔｅｒｆｏｒＩｎｆｏｒｍａｔｉｏｎＩｎｄｕｓｔｒｙＤｅｖｅｌｏｐｍｅｎｔ，ＣｈｉｎａＳｏｆｔｗａｒｅＴｅｓｔｉｎｇＣｅｎｔｅｒ，Ｂｅｉｊｉｎｇ１０００６６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｂｉｄ．ｐｒｉｃｅｃｏｎｔｒｏｌｉｓａｐｏｐｕｌａｒｍｅｔｈｏｄｆｏｒｃｏｎｔｒｏｌｌｉｎｇｔｈｅｓａｌｅｏｆｉｎｖｅｎｔｏｒｙｉｎｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ．Ｉｔｉｓｗｅｌｌｋｎｏｗｎｔｈａｔｔｈｅｎｅｔｗｏｒｋｃａｐａｃｉｔｙｃｏｎｔｒｏｌｐｒｏｂｌｅｍｃａ４－１ｂｅｆｏｒｍｕｌａｔｅｄａｓａｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅａｐｐｒｏｘｉｍａｔｅｔｈｅｏｐｔｉｍａｌｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｖａｌｕｅｆｕｎｃｔｉｏｎｗｉｔｈａｎａｆｆｉｎｅｆｕｎｃｔｉｏｎｏｆｔｈｅｓｔａｔｅｖｅｃｔｏｒａｎｄｄｅｖｅｌｏｐｏｕｒｍｏｄｅｌｂａｓｅｄｏｎｔｈｅｆｌｉｇｈｔｓｅｇｍｅｎｔｄｅｍａｎｄｓ．Ｗｅｓｈｏｗｔｈａｔｔｈｅｒｅｓｕｌｔｉｎｇｐｒｏｂｌｅｍｉｓｔｈｅｄｅｔｅｒｍｉｎｉｓｔｉｃｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＤＬＰ）ｆｏｒｃｏｍｐｕｔｉｎｇｎｅｔｗｏｒｋｂｉｄ－ｐｒｉｃｅｓ．ＴｈｅＤＬＰ卵ｅｌｄｓｔｉｇｈｔｅｒｂｏｕｎｄｓｔｈａｎｔｈｅｃｌａｓｓｉｃａｌＤＬＰ．、＾，ｅｇｉｖｅａｃｏｌｕｍｎｇｅｎｅｒａｔｉｏｎｐｒｏｃｅｄｕｒｅｆｏｒｓｏｌｖｉｎｇｔｈｅＤＬＰｗｉｔｈｉｎａｄｅｓｉｒｅｄｏｐｔｉｍａｌｉｔｙｔｏｌｅｒａｎｃｅ，ａｎｄｐｒｏｖｉｄｅｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓ．ＴｈｅｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈｅｐｏｌｉｃｙｐｅｒｆｏｒｍｆｒｏｍｏｕｒｓｏｌｕｔｉｏｎａｐｐｒｏａｃｈｃａＪｌｏｕｔｐｅｒｆｏｒｍｔｈａｔｆｒｏｍｔｈｅｃｌａｓｓｉｃａｌＤＬＰ．
Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ；ｂｉｄ－ｐｒｉｃｅｃｏｎｔｒｏｌｓ
基于航段需求计算网络竞价的近似动态规划方法
作者：
作者单位：刘风， 吴祈宗， 王亚楠， 崔春生， LIU Feng， WU Qi-zong， WANG Ya-nan， CUIChun-sheng刘风,LIU Feng(北京理工大学,管理与经济学院,北京,100081;中央司法警官学院信息管理系
,河北,保定,071000)， 吴祈宗,WU Qi-zong(北京理工大学,管理与经济学院,北京,100081)
， 王亚楠,WANG Ya-nan(河北科技大学,经济管理学院,河北,石家庄,050018)， 崔春生,CUI
Chun-sheng(中国电子信息产业发展研究院,中国软件评测中心,北京,100066)
数学的实践与认识
MATHEMATICS IN PRACTICE AND THEORY
2011,41(4)刊名：英文刊名：年，卷(期)：
本文链接：http://d.g.wanfangdata.com.cn/Periodical_sxdsjyrs201104008.aspx
第４１卷第４期数学的头践与认识Ｖｂｌ．４１．Ｎｏ．４２０１１年２月ＭＡＴＨＥＭＡＴＩＣＳＩＮＰＲＡＣＴＩＣＥＡＮＤＴＨＥＯＲＹＦｅｂ．．２０１１
基于航段需求计算网络竞价的近似动态规划方法
刘风，，一，吴祈宗・，王亚楠３，崔春生４
（１．北京理工大学管理与经济学院，北京１０００８１）
（２．中央司法警官学院信息管理系，河北保定０７１０００）
（３．河北科技大学经济管理学院，河北石家庄０５００１８）
（４．中国电子信息产业发展研究院中国软件评测中心，北京１０００６６）
摘要：竞价控制是收益管理中广泛应用的一种存量控制方法．将网络存量控制问
题描述为一个动态规划模型，通过状态向量的一个仿射函数近似动态规划的最优值
函数，并且在航段水平上考虑随机需求，最终得到一个计算网络竞价所需的确定性
线性规划（ＤＬＰ），相对于标准的ＤＬＰ，这个ＤＬＰ得到了更接近于动态规划最优值
的上界．给出了一个列生成算法用于求解这个ＤＬＰ，并提供了模拟算例，计算结果
表明可获得比标准的ＤＬＰ方法更好的收益．
关键词：网络收益管理；动态规划；竞价控制
１引言
．收益管理中的网络存量控制问题可描述为一个动态规划模型，但由于状态空间的维度过于巨大，要得到这个模型的精确解基本上是不可能的，唯一实用的方法是尽量对决策问题近似化【１１．在各种近似方法中，Ｄ’Ｓｙｌｖａｉ２】和Ｇｌｏｖｅｒ等【３】提出的确定性线性规划（ＤＬＰ）方法可能是最广为人知，也是最简单的一个例子．这种方法的主要不足在于它只考虑需求的期望值而忽略了需求预测中的所有不确定性．
由近似方法所得到的最有用的结果是对竞价的估计．Ｓｉｍｐｓｏｎ［４】和Ｗｉｌｌｉａｍｓｏｎ［５】介绍了竞价控制的思想并提出把决策问题构建为各种数学规划，将其对偶价格作为竞价的近似值．以航空客运业为例，航空公司的资源是客运网络中各航节的存量，产品则是网络中各航线上特定价格等级的座位，同一航线，不同价格等级的座位属于不同的产品．竞价是每个航节（资源）的阈值．在资源允许的前提下，对于一个产品（某一航线上特定价格等级的座位）的预订请求，竞价控制意味着只有当产品的价格超过了它所使用的全部资源（航节）的竞价总和时，产品才会被出售，即接受预订．
网络收益管理中的大多数存量控制模型针对产品（特定航线与价格等级的组合）考虑不确定性需求．Ｈｉｇｌｅ［６】和ＢｕｒａｋＢｉｉｋｅ等［７】研究了基于航段需求的随机规划（ｓＰ）模型．随着消费者选择购买不同航线或不同价格等级的机票可到达同一目的地的机会的增加，探索基于航段考虑随机需求的模型将会变得日益重要．出于此种考虑，这篇文章主要集中于建立一个基于航段需求计算网络竞价的易处理模型及求解算法，并通过模拟算例与标准的ＤＬＰ方法收稿日期：２０１０－１０—１４资助项目：国家自然科学基金（６０９７９７０１０）
５０数学的实践与认识４１卷进行对比．
２问题描述
在这一节中将给出对决策问题的基本描述以及贯穿全文所使用的符号．
２．１马尔科夫决策过程描述
模型是一个时间离散且有界的马尔科夫决策过程．目标是使总的期望收益最大化．
首先，假设一个包含ｍ个航节（资源）的航空客运网络，航节ｉ∈Ｉ＝｛１，２，…，ｍ）．整个网络有ｉ个航段，航段ｎ∈Ｎ＝｛１，２，…，ｚ｝．航节的不同组合构成了网络中各航段上的航线，对于一个给定的航段礼可能有多条航线，ｒ∈风＝｛１，２，…，ｆ心Ｉ）表示属于航段礼的航线，ｌ凰ｆ是集合Ｒ。的势．航空公司销售ｋ种产品，铲品Ｊ∈Ｊ＝｛１，２，…，忌）．设山∈Ｊ是属于航线ｒ的产品集合．・
定义关联矩阵Ａ＝【ｏ‘，，】，其中，如果航线ｒ使用航节ｉ，ａｉ，，＝１，否则，８小＝０．矩阵Ａ的第ｒ列，记为∥，表示航线ｒ所使用航节的集合．
时间是离散的，ｔ表示任意的＿个时段，总共有Ｔ个时段．
需求定义在航段的水平上．每个时段ｔ内，至多有一名顾客到达，顾客到达的概率为阮。，没有顾客到达的概率为１一∑Ｐ协．．
ｎＥＮ
网络的状态由剩余航节存量向量ｚ＝０１，…，茁。）描述，初始状态由初始存量向量ｃ＝（ｃ１，…，ｃ。）表示．向量ｚ满足
ｚ∈托三∽，【｛ｚ∈．ｍ：鼢∈｛ｏ，１，…，Ｑ）Ｖｉ｝，当ｔ＝２，…，Ｔ
如果出售了航线ｒ的一个座位，网络的状态变为ｚ—Ａ’，忽略顾客不到和退订的情况．给定当前的时段ｔ和当前剩余航节存量向量ｚ（ｔ），当接到一个预订请求时，预订系统必卦“，须决定是否接受这个预订．
虽然需求是基于航段的，但必须针对产品（特定航线与价格等级）制定决策．设忌维向量．札表示这个决策，如果接受一个对航线ｔ和价格等级Ｊ的座位．（产品）预订，Ｕｒｊ＝１，否则，Ｕｒｊ＝ｏ．一般地，决策ｕｒＪ是剩余存量向量ｚ和机票价格，ｒＪ的函数，即ｕ，Ｊ＝Ｕｒｊ（ｚ，南），其中，Ｊ∈五Ⅶ，ｒ∈％，ｎ∈Ｎ．由于在任一时段内至多只有一个预订请求，并且不考虑不到和退订，因此决策向量ｕ属于集合
．ｕ（ｚ）＝｛ｕ∈｛０】１）七：∑∑肌，ｊ≤ｚ｝‘ｈＥＮｒＥＲ。，ｊ∈凡
如果系统接受了一个对航线ｒ和价格等级Ｊ的座位预订，即ｕｒＪ＝ｌ，将获得收益南＞０，并且资源将按照矩阵Ａ的第ｒ列，∥，消耗．如果没有足够的资源可以满足预订，请求将被拒绝，当然也没有收益．即使有足够的资源，但如果将这些资源提供给潜在的未来顾客能够获得更多收益，当前的预订请求也可能被拒绝．
设Ｖ。（ｚ）是在时段￡的期初，状态为ｚ，经过时期ｔ，…，Ｔ所获得的最大的总期望收益，那么Ｖ。（ｚ）必须满足贝尔曼方程．
嘶）：１１１ｕＥａＸＵ｛三Ｐｔ，ｎ［，∈纛ＪｒｆｒｊＵｒｊ－＿Ｉ－Ｖｔ－ｋｌ（一，∈磊＾∥ｕ巧）］＋
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５１
（・一∑ｐｔ＇。）阱・（ｚ）ＭｎＥＮ
边界条件为卯＋ｌ（ｚ）＝０Ｖｘ．
当初始状态为ｃ时，（１）式的值函数可通过下面的线性规划计算，
（ＤＯ）ｍ，ｉｎ、
”Ｌ。ＪＶｌ（ｃ），、
ｓ．ｔ．仇ｉｚ）≥∑Ｐ狮［∑加让，ｊ＋饥＋，（ｚ一∑∥ｕ巧）］＋ｈＥＮｒ∈Ｒｎ，Ｊ∈山ｒＥＲ竹，ｊ∈Ｊ，
（１一∑Ｐｔ，ｎ）阱１（。）ｖｔ，ｚ∈托，ｕ∈ｕ（ｚ）
ｈＥＮ
决策变量为饥（ｚ）Ⅵ，。∈Ｘｔ．通过归纳法容易证明，（Ｄｏ）的任意可行解砚（・）是方程（１）的最优值仇（・）的一个上界，相关证明参见文献［８】．
２．２（ＤＬＰ）描述
由于状态空间的维度过大，一般情况下，（１）式和（ＤＯ）都很难精确求解．因此，在收益管理中，标准的方法是忽略时间的动态性，转而求解一个更简单的ＤＬＰ．标准的ＤＬＰ根据需求的期望值分配存量，这种方法假设每名顾客申请预订某一产品（特定航线和价格等级的座位），如果这个产品已经售完，顾客将离开系统．与之不同的是，这篇文章假设每名顾客申请预订某一特定航段（而不是特定航线和价格等级）的座位，当这个航段拥有多条航线时，即使某条航线的机票已经售完，顾客仍可能选择预订这个航段中其他航线的座位．设％表示在最后一个时段结束Ｈ寸＇分配给航线ｒ上价格等级为Ｊ的期望座位数，则（ＤＬＰ）模型如下：
（ＤＬＰ）ＺＤＬＰ＝ｍ。ａｘ∑∑如％
ｎＥⅣｒＥＲ。，Ｊ∈Ｊｒ（２）
（３）
（４）ｓ，ｔ．∑∑ａｉ，，％≤ｃｉ，ＶｉｈＥＮｒＥ如，ｊ∈Ｊｒ０≤∑‰≤∑Ｐ抽，Ｖｎ一ＺＪ。Ｊ—Ｚ√。＇…
ｒ∈Ｒ。，Ｊ∈Ｊｒｔ、７
蚱ｊ≥０，Ｖｎ，７．∈Ｒ。，Ｊ∈矗、
其中，需求是在航段的水平上加以考虑的．实际上，（ＤＬＰ）是标准的ＤＬＰ在航段需求下的一种扩展．（ＤＬＰ）的对偶形式如下：
骝∑ｃｉＴｒｉ＋∑（∑ｐｔ＇ｎ）ｐｎ
吼加
。＋ｐｎ＞一抽Ｖｎｒ∈昆ｎ∈‘∑州＂＞一其中，７ｒｉ是约束（３）的对偶价格（即航节ｉ的竞价），ｐ。是约束（４）中右端不等式的对偶价格．设丌；和麻表示最优的对偶价格．在资源允许的前提下，假设有一个对航线ｒ和价格等级Ｊ的座位预订请求，按照竞价控制的思想，如果
，ｒＪ≥∑ａｉ，，砖ｖｎ，ｒ∈％，Ｊ∈Ｊｒ
ｉＥＪ
就接受预订，否则将拒绝此预订．
５２数学的实践与认识４１卷３函数近似
如前所述，（ＤＯ）含有大量的决策变量和约束条件，很难精确求解．使之得以简化的一种方式是通过一系列基本函数来近似仇（・）．本节首先用一系列仿射函数来近似饥（・），并给出由此而得到的原规划和对偶规划．其次，建立对偶规划和（ＤＬＰ）的联系．
３．１描述
考虑下面的仿射函数近似：
饥（。）≈仇＋∑巩，‘甄
ｔ
其中巩是常量补偿，丌ｔ，‘是在时段ｔ航节ｉ的竞价，０Ｔ＋１＝０，７ｒＴ＋ｌ，ｔ＝ｏ，Ｖｔ．
将（６）式代入（Ｄｏ）得到
（Ｄ１）ｍ日ｉ。ｎ６１＋∑７ｒｌ，｛ｑ
ｓ．ｔ．巩一‰・＋∑ｈ溉一，Ｔｔ＋ｌ，ｉ（戤一∑Ｐｔ，ｎ∑％ｒ牡巧）］
≥∑仇，。
（Ｄ１）的对偶模型如下：∑局乱啊Ⅵ，ｚ∈五，ｕ∈Ｕ（ｚ）
（Ｐ１）钠＝峄∑（∑巩。∑＾牡，ｊ）孙，。
ｆ龟，当江１
ｓ．ｔ’础‰蛳忍俨｛纛＿擘ｎＥＮ≯ｒＥＲ∑，。，ｊＥ凡％胁¨州６）
∑，‰胪｛蚝ｘｔｍ∈Ｕ婶）
７≥０ｆ１，ｉｆ扛１ＬｚＥＸｔ乩ｕｅＵ（ｚ）‘∑¨＾。，Ⅵ－２＇…，Ｔ（７）
约束（７）意味着
≥：ｍ，掣＝１，Ⅵ（８）
因此决策变量ｍ忍。可解释为状态．行动概率，即＂／ｔ尚。表示在时段ｔ，状态为ｚ，做出决策Ｕ的概率．（６）式为流量平衡约束．
３．２与（ＤＬＰ）的联系
为了由（Ｐ１）得到（ＤＬＰ），定义
％＝∑（ｐｔ’。ｕｒＪ）Ｔｔ而。，ＶＶ∈取，Ｊ∈Ｊｒ（９）
由于９＇ｔ。啪可解释为在时段ｔ，状态为ｚ，做出决策ｕ的概率，（９）式右端的含义就是当最后一个时段结束时，提供给航线ｒ上价格等级为Ｊ的期望座位数，这也正是（ＤＬＰ）中决策变量％的含义．这样，（Ｐ１）的目标函数可写作：
∑（∑Ｐｔ，。∑九“，ｊ）‰一＝∑∑加‰
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５３
现在，固定ｉ，将（６）式对ｔ加总得到
∑ｘｉ＂／ｔ而ｕ
￡，ｚ∈ｘｔ，ｕ∈ｃ，（ｚ）
＝ｃｉ＋。∑（戤一∑仇－１＇。‘ｈＥＮ∑ｒ∈Ｒｎ，Ｊ∈Ｊ－口印％）ｍ－１＇舭
（１０）ｔ＝２，…，Ｔ，ｚＥＸｔ—ｌ，ｔ‘∈￡，（。）上式化简后得到ｑ＝∑∑ｐ抽∑
∑
＂ｈｅＮｒＥＲｎ，Ｊ∈Ｊｒｔ＝ｌ，…，Ｔ一１，ｘＥＸｔ，ｕ∈ｕ（￡）ｈＥＮｒＥＲｎ，ｊＥＪｒ‘∑Ｘｉ＇ＩＴ忍。（。妒札巧）弧州＋ｚＥＸｔ，ｕｅＵ（ｘ）ＥｒＥＲｎ，Ｊ∈ＪｒｎＥＮ由集合ｕ的定义知瓢≥∑
此，（１０）式意味着
Ｑ≥ａｉ，，乱，ｊ忱，故ｘｉ≥∑Ｐｔ，ｎａｉ，，让，ｊＶｉ．因∑
ｔ，ＺＥＸｔ，“∈【，（ｚ）
ｎＥＰ咖∑（。时Ｕｒｊ）“／ｔ而。ｔｌｒ∈ｔｋ，Ｊ∈Ｊｒ＝∑∑ａｉ，ｒｒＥＲｎ，ｊ∈凡∑ｔ，ｚＥＸｔ，ｔ‘∈ｕ（。）（ｐｔ，。扎ｒｊ）‰，。＝∑∑ａｉ，ｒ％，Ｖｉｎｒ∈Ｒｎ，ｊ∈Ｊｒ
从而得到了（３）式．另由（９）式可得
∑％＝∑
ｒ∈Ｒｎ，Ｊ∈Ｊｒ∑（ｐｔ，。ｕｒＪ）‰，。
∑ｕ，ｊＴｔ，刚ｒＥＲｎ，ｊｅＪｒｔ，ｚＥＸｔ，ｔ‘∈ｕ（ｚ）＝∑仇，。∑
ｔｒＥＲｎ，ｊ∈．７●ｘＥＸｔ，ｔ‘∈￡，（ｏ）
ｓ∑Ｐ帅
ｔ∑ｚＥＸｔ，ｕ∈ｃ，（￥）‰，。＝∑Ｐ加，Ｖｎ‘
即产生了（４）式中右端的不等式．
上述讨论表明ＺＤＬＰ≥Ｚｐｌ．如前所述，（ＤＯ）的任意可行解瓴（・）是方程（１）的最优值仇（・）的一个上界，由于（Ｐ１）一（Ｄ１）给出Ｙ（Ｄ０）的一个可行解，因此，Ｚｐｌ≥Ｖｌ（Ｃ）．下面的命题总结了这些结论．
命题１（Ｐ１）的任意可行解均是（ＤＬＰ）的可行解，且有相同的目标函数值．因此，ＺＤＬＰ≥ＺｐＩ≥Ｖｌ（ｃ）．
文献【９】证明了上界ＺＤＬＰ是渐进最优的，即随着时间的流逝，需求不断实现，各航节的存量不断消耗，ＺＤＬＰ逐渐收敛于ｕ１（ｃ），由命题１知Ｚｐｌ也是渐进最优的．
４列生成算法
（Ｐ１）中虽然含有大量的变量，但约束条件相对较少，因此可以考虑用列生成算法对其求解．变量ｍ＾。使名Ｐ・减少的收益ｈ，。，。的检验数）可表示为：
咄刚＝∑ｐ抽
ｎ∑ｒ∈Ｒ竹，ｊ∈Ｊｒ（岛一∑口ｔＩｒ丌ｔ＋１’ｔ）ｕ订一∑（７ｒｔｒ７ｒｔ＋ｌ，ｉ）翰一巩＋‰・ｔ‘
命题２吼禹。＝｛：：翼暑，ｚ
２ｃＩ钆＝０’Ⅵ，。，ｕ是（Ｐ１）的一个可行解．证明对于所有的ｔ和ｉ，（６）式左端有∑ｚｔ‰。＝ｑ‰ｏ＝Ｑｚ∈ｘｔ，ｕ∈Ｕ（￥）．
数学的实践与认识４１卷
并且对于所有的ｔ＞１，（６）式石端有
∑
ｘＥＸｔ一１，ｕ∈ｕ（茁）∑口｛’，％）讯－ｌ＇叫＝ｃｔ讯＿１１ｃ，ｏ＝ｑ（翰一∑ｐ¨，。ｔＥＲｎ，ｊ∈山ｎ
由命题２给定的（Ｐ１）的一个初始可行解可得（Ｄ１）的解为目，丌，下面解
船吼ｍ胀ａｘ帅，Ｗｔ，ｘｕ＝们眠ｍ艇ａｘ吣，Ｅ。Ｐｔ，ｎ懈Ｅ棚∈＾（护≯ｍ扎ｔ）盱
∑（％一巩＋１’ｉ）觑也＋０ｔ＋１
如果上式的最优函数值非正，那么（Ｐ１）就已经达到了最优，否则，将得到的列（上式的解）增加到（Ｐ１）中已经存在的列（解）中．对固定的ｔ＞１，这相当于求解下面的整数规划．
鼍警∑ｐ伽
ｎ∈Ｎ∑（如一∑。妒７ｒｔ＋ｌ’ｔ）ｕｒｊ—Ｅ（％一叭埘）％一巩＋吼＋１（１１）（１２）
（１３）ｓ．ｔ．∑Ｅ。寸ｕ，ｊ≤％ＶｉｒＥＲ。，Ｊ∈Ｊ，ｕ，ｊ∈｛ｏ，１），Ｖｎ，ｒ∈Ｒ。，Ｊ∈Ｊｒ
Ｘｉ∈｛ｏ，…，Ｑ），Ⅵ
定义ｕ；＝’（１４）’。ｚ∈．Ｘｔ，ｔ‘∈Ｕ（ｚ）ｍａｘ．，眦而。Ⅵ是在ｔ时段口，７ｒ情况下印】减少的最大收益．‘‘
命题３设善是决策变量ｍｍ。的所有可能下标的一个子集，称仅含有下标属于集合∈的决策变量的（Ｐ１）为受限制的（Ｐ１），记为（Ｐ１（∈））．若（彳，（百，亓））分别为（Ｐ１（毒））及其对偶问题的解，耐是根据舀和亓计算ｕ；得到的值，翟为（Ｐ１（专））的最优目标函数值，则有
Ｔ
Ｚｐｌ≤翟＋Ｅ
ｔ＝ｌ０～９ｔ．
证明考虑（Ｐ１）的任意可行解７，和任意数量的０ｔ和？ｒｔ，ｉＶｔ，ｉ．对每一个ｔ，ｉ，（６）式两边乘以丌ｔ，ｉ并加上巩，然后把所得方程与
ｚ（，ｙ）＝∑（∑Ｐ枷∑加札巧）‰，。
ｔ，茁，ｔＩｈＥＮｒＥＲｎ，Ｊ∈Ｊｒ
合并可得
ｚ（，ｙ）一∑丌１，ｉＣｘ一日，＝∑ｗｔ，ｘ，ｕＴｔ，叩≤∑ｕ；‰，。＝∑ｕ；（∑‰，。）＝∑ｕ；
ｔｔ，￥，ｕ．ｔ，Ｘ，ｔ‘ｔｚ，ｕｔ
其中，最后的等式是根据（８）式所得．对（Ｐ１）所有的可行解７，上式均成立，特别地，对于（Ｐ１）的一个最优解７木，其目标函数值为Ｚｎ木）＝Ｚｐｌ．进而，由受限问题（Ｐ１＠＂的强对偶性可得
∑亓¨ｑ一百１＝ｚ（彳）＝旅
ｉＧｌ
Ｔ
因此，有ＺＰｌ≤誓＋∑硪．
对于（ＰＩ），命题３给出了最优值Ｚｐ・与一个给定下标属于集合毒的可行解的目标函数值翟之间差的一个上界．若使翟比Ｚｐｌ不超过Ｑ，即，Ｚｐｌ／Ｚｅ≤１＋Ｑ，须满足七－≤Ｑ．此式可作为列生成算法的停机标准，完整的算法见图１．
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５５
列生成算法
令∈＝｛（ｔ，ｃ，０）ｖｔ｝，解受限问题（Ｐ１（∈）），并对所有的ｔ，令ｕ；＝ｏｏ
ｗｈｉｌｅＥ沈＞磁Ｑｄｏ
ｔ
对所有的ｔ∈｛１，…，Ｔ）
计算ｕ；＝ｍａｘｗｔ禹ｕ
正・Ｕ
选择一个（ｚｔ，ｕｔ）∈ａｒｇＩＴｌａｘｔｏｔ＾ｕ
Ｚ・Ｕ
更新∈一毒Ｕ｛（ｔ，耽，ｕｔ））．
解（Ｐ１（∈））
图ｌ求解（Ｐ１）的列生成算法
５模拟算例
图２是一个假设的航空客运网络，这个网络包含５个航节，６个航段和１０条航线．而且，每条航线有３个价格等级（商务，休闲一１和休闲一２）．商务票价服从均值为２００的泊松分布，休闲一１的票价服从均值为１００的泊松分布，休闲一２的票价服从均值为５０的泊松分布．需求是平稳的，简单起见，设每个时段没有顾客到达的概率为ｏ．２．模拟Ｔ∈｛２０，５０，１００，２００，４００｝５种情况．对每种情况，每个航节的初始存量均为ｃ．算例尝试比较求解（Ｐ１）与（ＤＬＰ）产生的上界以及各自执行竞价控制策略所得到的总期望收益．借助ＭＡＴＬＡＢ，设Ｑ＝５％，求解（Ｐ１）一（Ｄ１）和（ＤＬＰ），每个算例对（Ｐ１）一（Ｄ１）与（ＤＬＰ）用相同的顾客需求序列分别执行竞价控制藻略，模拟１００次，计算结果见表１．
图２—个具有５个航节、６个航段和１０条航线的假设航空客运网络表１上界和总期望收益
５６数学的实践与认识４１卷６结束语
需求主要是根据以往的销售数据进行预测，而这些数据是基于产品（特定航线和价格等级）的．对于给定的一个航段，可能包含多条航线，在这种情况下，要分辨出顾客属于哪条航线或哪个价格等级并不是一件容易的事，这就增加了需求预测的难度．在这篇文章中，需求是基于网络中的航段而非产品．对此，可利用当前基于产品的需求预测技术，即对每个航段中相关航线和价格等级的需求进行加总以提高预测的准确性．
文章首先由动态规划入手，对动态规划的最优值函数做仿射函数近似，得到一个基于航段需求，用于计算网络竞价的ＤＬＰ模型．相对于标准的ＤＬＰ，这个ＤＬＰ模型得到了更接近于动态规划最优值的上界．然后提供了一个列生成算法用于求解这个ＤＬＰ，计算结果验证了上述结论并表明可获得比标准的ＤＬＰ方法更好的收益．
参考文献
【１】ＴａｌｌｕｒｉＫＴ，ｖａｎＲｙｚｉｎＧＪ．ＴｈｅＴｈｅｏｒｙａｎｄＰｒａｃｔｉｃｅｏｆＲｅｖｅｎｕｅＭａｎａｇｅｍｅｎｔ［Ｍ］．Ｂｏｓｔｏｎ：Ｋｌｕｗｅｒ
ＡｃａｄｅｍｉｃＰｕｂｌｉｓｈｅｒｓ，２００４：８８－９２．
［２】Ｄ’ＳｙｌｖａＥ．ＯＤｓｅａｔａｓｓｉｇｎｍｅｎｔｔｏｍａｘｉｍｉｚｅｅｘｐｅｃｔｅｄｒｅｖｅｎｕｅ［Ｒ］．Ｓｅａｔｔｌｅ：ＢｏｅｉｎｇＣｏｍｍｅｒｃｉａｌ
ＡｉｒｐｌａｎｅＣｏｍｐａｎｙ，１９８２．
【３】ＧｌｏｖｅｒＦＲ，ＧｌｏｖｅｒＪ，ＬｏｒｅｎｚｏＣ．Ｍｃｍｉｌｌａｎ．Ｔｈｅｐａｓｓｅｎｇｅｒ－ｍｉｘｐｒｏｂｌｅｍｉｎｔｈｅｓｃｈｅｄｕｌｅｄａｉｒｌｉｎｅｓ［Ｊ］．
Ｉｎｔｅｒｆａｃｅｓ．１９８２，１２：７孓７９．
［４】ＳＩＭＰＳＯＮＲＷ．ＵｓｉｎｇＮｅｔｗｏｒｋＦｌｏｗＴｅｃｈｎｉｑｕｅｓｔｏＦｉｎｄＳｈａｄｏｗＰｒｉｃｅｓｆｏｒＭａｒｋｅｔａｎｄＳｅａｔ
ＩｎｖｅｎｔｏｒｙＣｏｎｔｒｏｌ［Ｍ］．Ｍａｓｓａｃｈｕｓｅｔｔｓ：ＭＩＴＦｌｉｇｈｔＴｒａｎｓｐｏｒｔａｔｉｏｎＬａｂｏｒａｔｏｒｙＭｅｍｏｒａｎｄｕｍ，Ｍ８９－１，Ｃａｍｂｒｉｄｇｅ，１９８９．
［５】ＷｉｌｌｉａｍｓｏｎＥＬ．Ａｉｒｌｉｎｅｎｅｔｗｏｒｋｓｅａｔｃｏｎｔｒｏｌ：ｍｅｔｈｏｄｏｌｏｇｉｅｓａｎｄｒｅｖｅｎｕｅｉｍｐａｃｔｓ［Ｄ］．ＰｈＤｔｈｅｓｉｓ，
Ｍａｓｓａｃｈｕｓｅｔｔｓ：ＭＩＴＦｌｉｇｈｔＴｒａｎｓｐｏｒｔａｔｉｏｎＬａｂｏｒａｔｏｒｙ，Ｃａｍｂｒｉｄｇｅ，１９９２．
【６】ＨｉｇｌｅＪＬ．Ｂｉｄ－ｐｒｉｃｅｃｏｎｔｒｏｌｗｉｔｈｏｒｉｇｉｎ－ｄｅｓｔｉｎａｔｉｏｎｄｅｍａｎｄ：ａｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇａｐｐｒｏａｃｈ［Ｊ］．
ＪｏｕｒｎａｌｏｆＲｅｖｅｎｕｅａｎｄＰｒｉｃｉｎｇＭａｎａｇｅｍｅｎｔ，２００７，５（４）：２９１－３０４．
【７】ＢｕｒａｋＢｉｉｋｅ，ＵｔｋｕＹｉｌｄｉｒｉｍａｎｄＨａｒｕｎＡｈｍｅｔＫｕｙｕｍｃｕ．Ｎｅｗｓｔｏｃｈａｓｔｉｃｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ
ａｐｐｒｏｘｉｍａｔｉｏｎｓｆｏｒｎｅｔｗｏｒｋｃａｐａｃｉｔｙｃｏｎｔｒｏｌｐｒｏｂｌｅｍｗｉｔｈｂｕｙ－ｕｐｓ［Ｊ］．ＪｏｕｒｎａｌｏｆＲｅｖｅｎｕｅａｎｄＰｒｉｃｉｎｇＭａｎａｇｅｍｅｎｔ，２００８，７（１）：６１—８４．
【剐ＡｄｅｌｍａｎＤ．Ｄｙｎａｍｉｃｂｉｄ—ｐｒｉｃｅｓｉｎｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ［Ｊ］．ＯｐｅｒＲｅｓ，２００７，５５（４）：６４７・６６１．
【９】ＣｏｏｐｅｒＷＬ．Ａｓｙｍｐｔｏｔｉｃｂｅｈａｖｉｏｒｏｆａｎａｌｌｏｃａｔｉｏｎｐｏｌｉｃｙｆｏｒｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ
Ｒｅｓｅａｒｃｈ，２００２，５０：７２０－７２７．
【１０】ＴａｌｌｕｒｉＫＴ，ｖａｌｌＲｙｚｉｎＧＪ．Ａｎａｎａｌｙｓｉｓｏｆｂｉｄ—ｐｒｉｃｅｃｏｎｔｒｏｌｓｆｏｒｎｅｔｗｏｒｋｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ［Ｊ］．
ＭａｎａｇｅｍｅｎｔＳｃｉ，１９９８，４４（４）：１５７７－１５９３．
【１１】ＴａｌｌｕｒｉＫＴ，ｖａｎＲｙｚｉｎＧＪ．Ａｒａｎｄｏｍｉｚｅｄｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄｆｏｒｃｏｍｐｕｔｉｎｇｂｉｄｐｒｉｃｅｓ［Ｊ］．
ＴｒａｎｓｐｏｒｔａｔｉｏｎＳｃｉ，１９９９，３３（２）：２０７—２１６．
【１２】ＷｏｌｌｍｅｒＲＤ．Ａｎａｉｒｌｉｎｅｓｅａｔｍａｎａｇｅｍｅｎｔｍｏｄｅｌｆｏｒａｓｉｎｇｌｅｌｅｇｒｏｕｔｅｗｈｅｎｌｏｗｅｒｆａｒｅｃｌａｓｓｅｓｂｏｏｋ
ｆｉｒｓｔ［Ｊ】．Ｏｐｅｒ．Ｒｅｓ，１９９２，４０：２６－３７．
【１３］ＺｈａｎｇＤ，ＡｄｅｌｍａｎＤ．Ａｎａｐｐｒｏｘｉｍａｔｅｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇａｐｐｒｏａｃｈｔｏｎｅｔｗｏｒｋｒｅｖｅｎｕｅｍａｎ—
ａｇｅｍｅｎｔｗｉｔｈｃｕｓｔｏｍｅｒｃｈｏｉｃｅ［Ｊ］．ＴｒａｎｓｐｏｒｔａｔｉｏｎＳｃｉ，２００９，４３（３）：３８１—３９４．
４期刘风，等：基于航段需求计算网络竞价的近似动态规划方法５７ＡｎＡｐｐｒｏｘｉｍａｔｅＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇＡｐｐｒｏａｃｈｆｏｒＣｏｍｐｕｔｉｎｇＮｅｔｗｏｒｋＢｉｄＰｒｉｃｅｓｗｉｔｈＦｌｉｇｈｔＳｅｇｍｅｎｔ
Ｄｅｍａｎｄｓ
ＬＩＵＦｅｎ９１，一，ＷＵＱｉ—ｚｏｎ９１，ＷＡＮＧＹａ－ｎａｎ３，ＣＵＩＣｈｕｎ－ｓｈｅｎ９４
（１．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔａｎｄＥｃｏｎｏｍｉｃｓ，ＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１０００８１，Ｃｈｉｎａ）
（２．ＤｅｐａｒｔｍｅｎｔｏｆＩｎｆｏｒｍａｔｉｏｎＭａｎａｇｅｍｅｎｔ，ｔｈｅＣｅｎｔｒａｌＩｎｓｔｉｔｕｔｅｆｏｒＣｏｒｒｅｃｔｉｏｎａｌＰｏｌｉｃｅ，Ｂａｏｄｉｎｇ０７１０００，
Ｃｈｉｎａ）‘’
（３．ＣｏｌｌｅｇｅｏｆＥｃｏｎｏｍｉｃａｎｄＭａｎａｇｅｍｅｎｔ，ＨｅｂｅｉＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｓｈｉｊｉａｚｈｕａｎｇ０５００１８，
Ｃｈｉｎａ）
（４．ＣｈｉｎａＣｅｎｔｅｒｆｏｒＩｎｆｏｒｍａｔｉｏｎＩｎｄｕｓｔｒｙＤｅｖｅｌｏｐｍｅｎｔ，ＣｈｉｎａＳｏｆｔｗａｒｅＴｅｓｔｉｎｇＣｅｎｔｅｒ，Ｂｅｉｊｉｎｇ１０００６６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｂｉｄ．ｐｒｉｃｅｃｏｎｔｒｏｌｉｓａｐｏｐｕｌａｒｍｅｔｈｏｄｆｏｒｃｏｎｔｒｏｌｌｉｎｇｔｈｅｓａｌｅｏｆｉｎｖｅｎｔｏｒｙｉｎｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ．Ｉｔｉｓｗｅｌｌｋｎｏｗｎｔｈａｔｔｈｅｎｅｔｗｏｒｋｃａｐａｃｉｔｙｃｏｎｔｒｏｌｐｒｏｂｌｅｍｃａ４－１ｂｅｆｏｒｍｕｌａｔｅｄａｓａｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅａｐｐｒｏｘｉｍａｔｅｔｈｅｏｐｔｉｍａｌｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｖａｌｕｅｆｕｎｃｔｉｏｎｗｉｔｈａｎａｆｆｉｎｅｆｕｎｃｔｉｏｎｏｆｔｈｅｓｔａｔｅｖｅｃｔｏｒａｎｄｄｅｖｅｌｏｐｏｕｒｍｏｄｅｌｂａｓｅｄｏｎｔｈｅｆｌｉｇｈｔｓｅｇｍｅｎｔｄｅｍａｎｄｓ．Ｗｅｓｈｏｗｔｈａｔｔｈｅｒｅｓｕｌｔｉｎｇｐｒｏｂｌｅｍｉｓｔｈｅｄｅｔｅｒｍｉｎｉｓｔｉｃｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＤＬＰ）ｆｏｒｃｏｍｐｕｔｉｎｇｎｅｔｗｏｒｋｂｉｄ－ｐｒｉｃｅｓ．ＴｈｅＤＬＰ卵ｅｌｄｓｔｉｇｈｔｅｒｂｏｕｎｄｓｔｈａｎｔｈｅｃｌａｓｓｉｃａｌＤＬＰ．、＾，ｅｇｉｖｅａｃｏｌｕｍｎｇｅｎｅｒａｔｉｏｎｐｒｏｃｅｄｕｒｅｆｏｒｓｏｌｖｉｎｇｔｈｅＤＬＰｗｉｔｈｉｎａｄｅｓｉｒｅｄｏｐｔｉｍａｌｉｔｙｔｏｌｅｒａｎｃｅ，ａｎｄｐｒｏｖｉｄｅｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓ．ＴｈｅｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈｅｐｏｌｉｃｙｐｅｒｆｏｒｍｆｒｏｍｏｕｒｓｏｌｕｔｉｏｎａｐｐｒｏａｃｈｃａＪｌｏｕｔｐｅｒｆｏｒｍｔｈａｔｆｒｏｍｔｈｅｃｌａｓｓｉｃａｌＤＬＰ．
Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｒｅｖｅｎｕｅｍａｎａｇｅｍｅｎｔ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ；ｂｉｄ－ｐｒｉｃｅｃｏｎｔｒｏｌｓ
基于航段需求计算网络竞价的近似动态规划方法
作者：
作者单位：刘风， 吴祈宗， 王亚楠， 崔春生， LIU Feng， WU Qi-zong， WANG Ya-nan， CUIChun-sheng刘风,LIU Feng(北京理工大学,管理与经济学院,北京,100081;中央司法警官学院信息管理系
,河北,保定,071000)， 吴祈宗,WU Qi-zong(北京理工大学,管理与经济学院,北京,100081)
， 王亚楠,WANG Ya-nan(河北科技大学,经济管理学院,河北,石家庄,050018)， 崔春生,CUI
Chun-sheng(中国电子信息产业发展研究院,中国软件评测中心,北京,100066)
数学的实践与认识
MATHEMATICS IN PRACTICE AND THEORY
2011,41(4)刊名：英文刊名：年，卷(期)：
本文链接：http://d.g.wanfangdata.com.cn/Periodical_sxdsjyrs201104008.aspx