[管理学]第8章 网络管理ppt课件

1、第第8章章 网络管理网络管理旅游与酒店收益管理旅游与酒店收益管理8.1 背景引见背景引见 Network revenue management: 需求思索所销售的不同产品之间的相需求思索所销售的不同产品之间的相互作用，以及这对销售其他产品的才互作用，以及这对销售其他产品的才干的影响干的影响内容内容 网络管理何时适用？网络管理何时适用？ 线性规划方法线性规划方法 虚拟嵌套虚拟嵌套 网络竞标定价网络竞标定价 动态虚拟嵌套动态虚拟嵌套 网络管理的运用网络管理的运用8.2 网络管理何时适用？网络管理何时适用？ 全价全价Y Y、折扣价、折扣价M M、高折扣价、高折扣价B B 价钱等级并不能完全反映价钱价

2、钱等级并不能完全反映价钱 有的有的B B等级乘客支付超越等级乘客支付超越400400美圆美圆 有些有些Y Y等级乘客的支付却低于等级乘客的支付却低于250250美圆美圆 假设航空公司封锁了假设航空公司封锁了B B等级，它将依然接受等级，它将依然接受支付支付250250美圆的美圆的Y Y等级及等级及M M等级乘客，同等级乘客，同时却回绝情愿为一个座位付出超越时却回绝情愿为一个座位付出超越400400美圆美圆 的的B B等级乘客。等级乘客。 东京东京旧金山旧金山芝加哥芝加哥 基于航段的才干分配，不会允许航空公司基于航段的才干分配，不会允许航空公司回绝回绝Y Y等级的从旧金山到芝加哥的乘客，而等级的

3、从旧金山到芝加哥的乘客，而接受接受M M等级的东京到芝加哥的乘客等级的东京到芝加哥的乘客 网络管理的目的：经过同时管理产品的组网络管理的目的：经过同时管理产品的组合，以及每个产品所售价钱等级的组合，合，以及每个产品所售价钱等级的组合，来提高收益来提高收益8.2.1 网络的类型网络的类型 中心辐射型网络中心辐射型网络 线形网络线形网络AB节点节点A和和B是枢纽城市，其他节点是周边城市是枢纽城市，其他节点是周边城市酒店和汽车租赁公司典型的线形网络酒店和汽车租赁公司典型的线形网络资源：资源：周一周一周二周二周三周三周四周四周五周五产品：产品：周一开场入住三晚周一开场入住三晚周二开场入住两晚周二开场入

4、住两晚周三开场入住三晚周三开场入住三晚 网络中每个产品都有一个或多个价钱等级。网络中每个产品都有一个或多个价钱等级。 网络管理：网络管理： 针对任一时辰任何产品针对任一时辰任何产品/ /价钱等级能够组合价钱等级能够组合的预订恳求，决议接受哪一个的预订恳求，决议接受哪一个 ODFODForigin-destination fare classorigin-destination fare class 出发地出发地- -目的地价钱等级目的地价钱等级 网络管理的目的：网络管理的目的： 继续管理和更新一切继续管理和更新一切ODFODF的可获得性，以最的可获得性，以最大化期望利润大化期望利润酒店：酒店：

5、 不同的不同的ODFODF 6 6月月1313日的一个驻留四晚的挂牌价预订日的一个驻留四晚的挂牌价预订 6 6月月1414日的一个驻留三晚的折扣预订日的一个驻留三晚的折扣预订 在同一时间可提供的产品数量是非常大在同一时间可提供的产品数量是非常大远远大于酒店所拥有的房间数量远远大于酒店所拥有的房间数量 假设接受顾客在接下来的假设接受顾客在接下来的365365天里到达并驻天里到达并驻留留1 11515天的约定，产品数量：天的约定，产品数量：1515365=5475365=5475 4 4种房间类型，那么产品数量：种房间类型，那么产品数量：4 41515365=21900365=21900个个8.2

6、.2 网络管理的贪婪启发式算法网络管理的贪婪启发式算法 为什么失灵？为什么失灵？ 一家一家100100个房间的酒店个房间的酒店 无约束需求如图无约束需求如图8.58.5 酒店假设接受一切预订恳求那么将得到的酒店假设接受一切预订恳求那么将得到的房间入住总量房间入住总量 周三的无约束需求超越了酒店才干周三的无约束需求超越了酒店才干 酒店面临的网络管理问题：酒店面临的网络管理问题： 同时思索房间价钱和驻留天数，以决议接同时思索房间价钱和驻留天数，以决议接受或回绝哪些预订恳求，最大化期望利润受或回绝哪些预订恳求，最大化期望利润图图8.5 一家典型的市中心商务酒店的需求方式一家典型的市中心商务酒店的需求

7、方式才干才干无约束入住率无约束入住率周日周日周一周一周二周二周三周三周四周四周五周五周六周六 两种价钱：挂牌价两种价钱：挂牌价200200美圆一晚，折扣美圆一晚，折扣价价150150美圆一晚美圆一晚 经理如何思索？经理如何思索？ 根据需求方式，酒店的约束资源是周三晚根据需求方式，酒店的约束资源是周三晚的房间容量的房间容量 能够推理出：限制那些包括周三晚在内的能够推理出：限制那些包括周三晚在内的折扣预订数量，以维护挂牌价顾客的可获折扣预订数量，以维护挂牌价顾客的可获得性得性 严厉按价钱等级管理预订严厉按价钱等级管理预订 缺陷：缺陷： 周三到达并驻留一晚的挂牌价顾客支付周三到达并驻留一晚的挂牌价顾

8、客支付200200美圆，然而周二到达并驻留三晚的折扣顾美圆，然而周二到达并驻留三晚的折扣顾客会支付客会支付450450美圆美圆 假设酒店为了给全价预订留下房间而限制假设酒店为了给全价预订留下房间而限制折扣预订，那么就存在着为了折扣预订，那么就存在着为了200200美圆顾客美圆顾客而回绝而回绝450450美圆顾客的风险美圆顾客的风险 违背了收益管理的原那么违背了收益管理的原那么 有什么其他方法？有什么其他方法？贪婪启发式算法贪婪启发式算法greedy heuristic 当只存在单个约束资源时，可将一切运用当只存在单个约束资源时，可将一切运用约束资源的约束资源的ODFODF按照其所支付的总价钱排

9、序，按照其所支付的总价钱排序，然后，运用然后，运用EMSREMSR或类似的启发式算法求解或类似的启发式算法求解这个多等级问题这个多等级问题 这意味着什么？这意味着什么？ 周三的最低等级是周三到达驻留一晚并支周三的最低等级是周三到达驻留一晚并支付付150150美圆的折扣顾客，美圆的折扣顾客， 次低等级是驻留一晚并支付次低等级是驻留一晚并支付200200美圆的挂牌美圆的挂牌价顾客价顾客 然后是驻留两晚周二到周三，或周三到然后是驻留两晚周二到周三，或周三到周四并支付周四并支付300300美圆的折扣顾客美圆的折扣顾客 接下来是驻留两晚并支付接下来是驻留两晚并支付400400美圆的挂牌价美圆的挂牌价顾客

10、顾客 以此类推以此类推 只需无约束需求仅在周三晚超越酒店才干，只需无约束需求仅在周三晚超越酒店才干，经过这样建立等级并设置适当的预订限额，经过这样建立等级并设置适当的预订限额，就能最大化期望利润就能最大化期望利润贪婪启发式算法贪婪启发式算法将每航段上一切的将每航段上一切的ODFODF按价钱排序，并基于按价钱排序，并基于其总价钱来设置其可获得性其总价钱来设置其可获得性假设只需一个资源约束或瓶颈，该算法是假设只需一个资源约束或瓶颈，该算法是最优的最优的当存在一个以上资源约束时，该算法就立当存在一个以上资源约束时，该算法就立刻失效了刻失效了酒店的无约束需求在周三和周四晚都超越酒店的无约束需求在周三和

11、周四晚都超越100100个房间个房间 严厉按照总收益对价钱等级进展排序将不严厉按照总收益对价钱等级进展排序将不再是最优的再是最优的 假设酒店置信周四晚的房间不会住满，那假设酒店置信周四晚的房间不会住满，那么它该当接受一个驻留周三到周四两晚并么它该当接受一个驻留周三到周四两晚并支付支付300300美圆的折扣预订美圆的折扣预订 假设它置信周四房间会住满，那么它最好假设它置信周四房间会住满，那么它最好回绝那个回绝那个300300美圆驻留两晚的折扣预订，而美圆驻留两晚的折扣预订，而等待周三和周四晚等待周三和周四晚200200美圆的挂牌价预订美圆的挂牌价预订 当多个资源遭到约束时，每航段上当多个资源遭到

12、约束时，每航段上ODFODF的正的正确顺序依赖于其他一切确顺序依赖于其他一切ODFODF的价钱和需求，的价钱和需求，以及网络里其他一切资源的才干以及网络里其他一切资源的才干 举例：贪婪启发式算法如何失灵？举例：贪婪启发式算法如何失灵？图图8.6 一个简单的中心辐射型网络一个简单的中心辐射型网络旧金山旧金山 丹佛丹佛 圣路易斯圣路易斯 航班航班1 航班航班2曾经安排好时间表，曾经安排好时间表，使得乘客可在丹佛从航班使得乘客可在丹佛从航班1转机到航班转机到航班2 为每种产品只提供单一价钱，从旧金山到为每种产品只提供单一价钱，从旧金山到丹佛是丹佛是200200美圆，丹佛到圣路易斯是美圆，丹佛到圣路易

13、斯是160160美美圆，旧金山到圣路易斯是圆，旧金山到圣路易斯是300300美圆美圆 假设如今两个航班上恰好都只剩下一个座假设如今两个航班上恰好都只剩下一个座位。位。 一位顾客称想从旧金山飞到圣路易斯，并一位顾客称想从旧金山飞到圣路易斯，并情愿支付情愿支付300300美圆美圆 该当接受她的预订吗？或者回绝，以等待该当接受她的预订吗？或者回绝，以等待两个航段上部分乘客的预订？两个航段上部分乘客的预订？ 设设p1p1是航班是航班1 1将会收到至少一个未来预订的将会收到至少一个未来预订的概率，概率，p2p2是航班是航班2 2将会收到至少一个未来预将会收到至少一个未来预订的概率订的概率 那么回绝联程顾

14、客预订并只接受部分顾客那么回绝联程顾客预订并只接受部分顾客预订的期望价值是预订的期望价值是200p1+160p2200p1+160p2美圆美圆 假设这个数值大于假设这个数值大于300300美圆，那么航空公司美圆，那么航空公司最好回绝联程顾客，并依托部分顾客来坐最好回绝联程顾客，并依托部分顾客来坐满座位满座位 假设小于假设小于300300，那么应接受联程顾客的预订，那么应接受联程顾客的预订 概率概率p1p1和和p2p2是航空公司对未来这两个航班是航空公司对未来这两个航班部分需求的预测。部分需求的预测。 航空公司能否该当接受联程乘客，取决于航空公司能否该当接受联程乘客，取决于这些预测这些预测 整个

15、网络：对于任一特定航段，航空公司整个网络：对于任一特定航段，航空公司该当偏好联程航线还是部分航线？该当偏好联程航线还是部分航线？ 答案：依赖于对一切答案：依赖于对一切ODFODF未来需求的预测未来需求的预测 在整个网络上进展优化在整个网络上进展优化8.3 线性规划方法线性规划方法linear programming,LP 假设我们确切知道每个假设我们确切知道每个ODFODF的未来需求。的未来需求。 假设需求不受开放和封锁哪个假设需求不受开放和封锁哪个ODFODF的影响的影响 每个航班和每个航段的需求都是独立的每个航班和每个航段的需求都是独立的 有有m m种资源，且运用这些资源组合成种资源，且运

16、用这些资源组合成n n个个ODFODF。 假设每种资源都被用于至少一个假设每种资源都被用于至少一个ODFODF，所以，所以n mn m 用下标用下标i i对资源编号，用下标对资源编号，用下标j j对对ODFODF编号编号 每种资源每种资源i i都有一个有限才干都有一个有限才干ci 0ci 0。 每个每个ODFODF都有一个知的需求都有一个知的需求dj0dj0，以及净利，以及净利润润pj0pj0。 设设xj 0 xj 0是我们将售出的分配的是我们将售出的分配的ODFjODFj的数量的数量 确定性网络管理问题：确定性网络管理问题： 在资源才干约束条件下，找出可以最大化在资源才干约束条件下，找出可以

17、最大化总净利润的总净利润的xj xj 的值，其中的值，其中j=1,2, ,nj=1,2, ,n 需求表示出每个需求表示出每个ODFODF运用了哪些资源运用了哪些资源 定义关联变量定义关联变量aijaij如下：如下： 思索图思索图8.68.6中的简单航班网络中的简单航班网络图图8.6 一个简单的中心辐射型网络一个简单的中心辐射型网络旧金山旧金山 丹佛丹佛 圣路易斯圣路易斯 航班航班1 航班航班2曾经安排好时间表，曾经安排好时间表，使得乘客可在丹佛从航班使得乘客可在丹佛从航班1转机到航班转机到航班2 两种资源：两种资源： 从旧金山到丹佛的航班从旧金山到丹佛的航班1 1 从丹佛到圣路易斯的航班从丹佛

18、到圣路易斯的航班2 2 航空公司有航空公司有3 3种产品和种产品和2 2个价钱等级，共提个价钱等级，共提供供6 6个个ODFODF： 旧金山到丹佛全价票旧金山到丹佛全价票 旧金山到丹佛折扣票旧金山到丹佛折扣票 丹佛到圣路易斯全价票丹佛到圣路易斯全价票 丹佛到圣路易斯折扣票丹佛到圣路易斯折扣票 旧金山到圣路易斯全价票旧金山到圣路易斯全价票 旧金山到圣路易斯折扣票旧金山到圣路易斯折扣票表表8.2 两航班例子的关联变量两航班例子的关联变量aij的值的值资源资源（i）ODF(j)12345611100112001111关联变量关联变量-例例 思索一家酒店，它提供的产品只需驻留一思索一家酒店，它提供的产

19、品只需驻留一晚、两晚和三晚晚、两晚和三晚 实际上，酒店的网络管理问题无限地向未实际上，酒店的网络管理问题无限地向未来延伸来延伸 超越超越1414晚的驻留是很少见的，可当成个别晚的驻留是很少见的，可当成个别产品进展管理产品进展管理表表8.3 酒店例子里关联变量的酒店例子里关联变量的aij值值资资源源到达日期到达日期周日周日周一周一周二周二周三周三周四周四123123123123123周日周日111000000000000周一周一011111000000000周二周二001011111000000周三周三000001011111000周四周四000000001011111周五周五000000000

20、001011周六周六0000000000000018.3.1 确定性网络线性规划确定性网络线性规划 把确定性网络管理问题表示成一个线性规把确定性网络管理问题表示成一个线性规划：划： 约束条件：约束条件： 目的函数目的函数8.28.2表示：目的是接受能最大化总表示：目的是接受能最大化总净利润的需求净利润的需求 每种资源都有形如式每种资源都有形如式8.38.3的约束的约束 保证航空公司可满足接受的一切需求保证航空公司可满足接受的一切需求 式式8.48.4是需求约束：每个是需求约束：每个ODFODF的销量都遭到的销量都遭到该该ODFODF需求的限制需求的限制 式式8.58.5保证了一切的分配额都大于

21、等于零保证了一切的分配额都大于等于零例例8.1 某航空公司运营着如图某航空公司运营着如图8.68.6所示的两航班航所示的两航班航空网络，它为三条航线都提供折扣票和全空网络，它为三条航线都提供折扣票和全价票。价票。 两种资源组合成了两种资源组合成了6 6个个ODFODF，表，表8.28.2是是ODF-ODF-资资源对应表。航空公司分派了一架源对应表。航空公司分派了一架100100座的飞座的飞机给从旧金山到丹佛的航班机给从旧金山到丹佛的航班1 1，一架，一架120120座座的飞机给从丹佛到圣路易斯的航班的飞机给从丹佛到圣路易斯的航班2 2。相应。相应的需求和票价如表的需求和票价如表8.48.4。

22、留意：无约束需求在旧金山到丹佛的航班留意：无约束需求在旧金山到丹佛的航班上是上是160160，在丹佛到圣路易斯的航班上是，在丹佛到圣路易斯的航班上是170170 由于需求超越了两个航班的才干，因此需由于需求超越了两个航班的才干，因此需求回绝一些乘客求回绝一些乘客图图8.6 一个简单的中心辐射型网络一个简单的中心辐射型网络旧金山旧金山 丹佛丹佛 圣路易斯圣路易斯 航班航班1 航班航班2曾经安排好时间表，曾经安排好时间表，使得乘客可在丹佛从航班使得乘客可在丹佛从航班1转机到航班转机到航班2表表8.2 两航班例子的关联变量两航班例子的关联变量aij的值的值资源资源（i）ODF(j)123456111

23、00112001111表表8.4 两航班网络管理例子的票价和需求两航班网络管理例子的票价和需求编号编号ODF票价票价需求需求1旧金山到丹佛全价票旧金山到丹佛全价票150302旧金山到丹佛折扣票旧金山到丹佛折扣票100603丹佛到圣路易斯全价票丹佛到圣路易斯全价票120204丹佛到圣路易斯折扣票丹佛到圣路易斯折扣票80805旧金山到圣路易斯全价票旧金山到圣路易斯全价票250306旧金山到圣路易斯折扣票旧金山到圣路易斯折扣票17040这个例子的线性规划这个例子的线性规划 max(150 x1+100 x2+120 x3+80 x4+250 x5+170 x6) 约束条件：约束条件： x1 + x2

24、 + x5 + x6 100 x3 + x4 + x5 + x6 120 x1 30 x2 60 x3 20 x4 80 x5 30 x6 40 x1, x2, x3, x4, x5, x6 0MATLAB MATLAB的线性规划函数的线性规划函数linprog针对线性规划：针对线性规划：解释 输入部分：输入部分：f:f:目的函数，实为目的函数的系数，以列矩目的函数，实为目的函数的系数，以列矩阵表示阵表示a a：不等式约束矩阵，左边：不等式约束矩阵，左边b b：不等式约束矩阵，右边，以列矩阵表示：不等式约束矩阵，右边，以列矩阵表示aeqaeq：等式约束矩阵，左边：等式约束矩阵，左边beq:be

25、q:等式约束矩阵，右边，以列矩阵表示等式约束矩阵，右边，以列矩阵表示lb:lb:自变量自变量x x的下界，的下界，ubub：自变量：自变量x x的上界，均以列矩阵表示的上界，均以列矩阵表示解释-续 x:最优解，以列矩阵表示最优解，以列矩阵表示 fval或或fv：最优值：最优值 exitflag或或ex：输出标志：输出标志 1：有最优解：有最优解 0：迭代次数超越设定次数：迭代次数超越设定次数 -2：约束区域不可行：约束区域不可行 -3： 问题无解问题无解表表8.5 两航班网络管理例子的解两航班网络管理例子的解编号编号ODF票价票价分配额分配额收益收益1旧金山到丹佛全价票旧金山到丹佛全价票150

26、3045002旧金山到丹佛折扣票旧金山到丹佛折扣票1004040003丹佛到圣路易斯全价票丹佛到圣路易斯全价票1202024004丹佛到圣路易斯折扣票丹佛到圣路易斯折扣票807056005旧金山到圣路易斯全价票旧金山到圣路易斯全价票2503075006旧金山到圣路易斯折扣票旧金山到圣路易斯折扣票17000 总收益：总收益：24000美元美元表表8.4-8.5 两航班网络管理例子的解两航班网络管理例子的解编号编号ODF票价票价分配额分配额需求需求1旧金山到丹佛全价票旧金山到丹佛全价票15030302旧金山到丹佛折扣票旧金山到丹佛折扣票10040603丹佛到圣路易斯全价票丹佛到圣路易斯全价票120

27、12020204丹佛到圣路易斯折扣票丹佛到圣路易斯折扣票8070805旧金山到圣路易斯全价票旧金山到圣路易斯全价票25030306旧金山到圣路易斯折扣票旧金山到圣路易斯折扣票170040结果讨论结果讨论 接受了每个产品的一切全价票乘客接受了每个产品的一切全价票乘客 在两个市场都接受了一些部分折扣乘客，在两个市场都接受了一些部分折扣乘客，但没有接受任何一个旧金山到圣路易斯的但没有接受任何一个旧金山到圣路易斯的联程折扣乘客联程折扣乘客 为什么？为什么？ 部分乘客所支付的票价总和大于联程折扣部分乘客所支付的票价总和大于联程折扣票价票价 在给定需求预测的情况下，经过满足部分在给定需求预测的情况下，经过

28、满足部分需求而回绝联程折扣乘客，获得更多利润需求而回绝联程折扣乘客，获得更多利润8.3.2 最优解的构造最优解的构造 表表8.58.5所示的最优解中，所示的最优解中，ODFODF可分成三类：可分成三类： 不接受任何预订的不接受任何预订的ODFODF旧金山到圣路易斯旧金山到圣路易斯折扣票折扣票 只接受部分而不是全部需求的只接受部分而不是全部需求的ODFODF丹佛到丹佛到圣路易斯折扣票，旧金山到丹佛折扣票圣路易斯折扣票，旧金山到丹佛折扣票 接受了一切需求的接受了一切需求的ODFODF一切的全价票一切的全价票ODFODF表表8.4-8.5 两航班网络管理例子的解两航班网络管理例子的解编号编号ODF票

29、价票价分配额分配额需求需求1旧金山到丹佛全价票旧金山到丹佛全价票15030302旧金山到丹佛折扣票旧金山到丹佛折扣票10040603丹佛到圣路易斯全价票丹佛到圣路易斯全价票12020204丹佛到圣路易斯折扣票丹佛到圣路易斯折扣票8070805旧金山到圣路易斯全价票旧金山到圣路易斯全价票25030306旧金山到圣路易斯折扣票旧金山到圣路易斯折扣票170040最优解的构造续最优解的构造续 在确定性网络管理问题的最优解中，对于在确定性网络管理问题的最优解中，对于每种产品，我们最多在一个价钱等级里只每种产品，我们最多在一个价钱等级里只接受部分而不是全部需求接受部分而不是全部需求 在该产品的其他价钱等级

30、里，那么是在该产品的其他价钱等级里，那么是“全全部或都不要么接受一切的需求，要么就部或都不要么接受一切的需求，要么就完全不接受完全不接受 产品价钱等级的接受是按照价钱顺序进展产品价钱等级的接受是按照价钱顺序进展的的例例8.2 某航空公司运营着图某航空公司运营着图8.68.6所示的航班网络，所示的航班网络，各产品的总需求与例各产品的总需求与例8.18.1一样，但每种产品一样，但每种产品有有5 5个价钱等级。如表个价钱等级。如表8.68.6 该航空公司提供了该航空公司提供了1515个个ODFODF。最优分配额如。最优分配额如表表8.68.6。表表8.6 扩展的网络的解扩展的网络的解编号编号产品产品等级等级票价票价需求需求分配额分配额收益收益1旧金山到丹佛A