数据、模型与决策（原书第16版）课件 第5章、线性规划高级应用

数据、模型与决策,第16版第5章、线性规划高级应用章节内容5-1 数据包络分析5-2 收益管理5-3 投资组合模型和资产分配5-4 博弈论

本章小结学习目标完成本章后，你将能够：LO5.1 运用数据包络分析，建立衡量效率的线性规划模型并求解。LO5.2 建立收益管理的线性规划模型并求解。LO5.3 建立投资组合的线性规划模型并求解。LO5.4 建立博弈论的线性规划模型并求解。LO5.5 能够从线性规划解决方案中识别两人零和博弈的纯策略。LO5.6 利用线性规划确定混合策略并计算混合策略博弈的最优概率。引言本章将继续线性规划的应用研究，并介绍四种线性规划的新应用。

5.1节介绍数据包络分析（DEA），它采用线性规划方法来衡量有相同目标的运营单元的相对效率，我们将以医院绩效测评来讲述该方法的应用。

5.2节将介绍收益管理，收益管理是对不能保存或者不易保存的一类产品，在已知固定库存容量条件下，管理短期需求，以最大化可能取得的收益。收益管理在航空行业尤其重要，我们将通过确定五个城市间航班的全价票与折扣票价的最优分配来阐明这个概念。5.3节将说明线性规划如何用于优化与客户的风险偏好相一致的投资组合。5.4节将介绍博弈论，这是对两个或更多的决策制定者（参与者）如何能以最优方式参与竞争的研究。这里，我们用两家公司互相竞争市场份额的一个线性规划模型来说明。5-1数据包络分析(DEA)DEA的应用数据包络分析（DEA）是用线性规划技术衡量具有相同目标和目的的运营单元的相对效率的方法。例如，用DEA衡量连锁快餐店中每个店面的效率，找出低效率店面，并为低效率店面的效率提升提供初步的对策建议。.DEA还用于衡量医院、银行、法院、学校等组织的相对效率。在这些应用中，每个机构或组织的绩效是相对于同系统中所有工作单元的绩效来衡量的。医院绩效衡量总医院、大学医院、县医院和州医院的管理者聚在一起讨论如何帮助彼此共同改进医院绩效。一个顾问建议他们考虑采用DEA衡量这四家医院中每所医院的相对绩效。在讨论如何完成这种衡量时，我们首先确定出下面三种输入指标和四种输出指标。输入指标全日制（FTE）非医务人员数目物资花费可使用病床总天数输出指标医疗保险患者服务天数无医疗保险患者服务天数培训过的护士人数培训过的实习医生人数5-1DEA方法概述下面我们将以县医院相对效率衡量为例来说明线性规划模型是怎样构建的。首先，基于有相同目标的所有运营单元的输入和输出，构建一个虚拟合成单元，在这个例子中是一家虚拟医院。

对这四家医院的每个输出指标，虚拟医院的输出由全部四家医院的相应输出加权平均计算而得。

对每个输入指标，虚拟医院的输入由全部四家医院的相应输入采用相同的权重加权平均计算而得。四家医院年消耗的资源四家医院提供的年服务5-1DEA:决策变量

5-1DEA:输出指标

5-1DEA:输出的约束条件

5-1DEA:输入指标

5-1DEA:输入的约束条件为了完成输入的约束条件方程，我们必须写出每个约束条件的右端值的表达式。首先，要注意到右端值是虚拟医院的可用资源。在DEA方法中，这些右端值是县医院输入值的一个百分比。因此，我们必须引入下面的决策变量：E:

县医院输入可用于虚拟医院的百分比如果E=1，虚拟医院可用的FTE非医务人员数目就为275.70，与县医院使用的FTE非医务人员数目相同。

5-1DEA:完整的线性规划（LP）模型完整的模型如下所示：MinE

s.t.wg+wu+wc+ws=1权重的总和48.14wg+34.62wu+36.72wc+33.16ws≥36.72医疗保险43.10wg+27.11wu+45.98wc+56.46ws≥45.98非医疗保险253wg+148wu+175wc+160ws≥175护士41wg+27wu+23wc+84ws≥23实习医生285.20wg+

162.30wu+275.70wc+210.40ws−275.70E≤0FTE非医务人员123.80wg+

128.70wu+348.50wc+154.10ws−348.50E≤0物资106.72wg+64.21wu+104.10wc+104.04ws−104.10E≤0可使用病床总天数E,wg,wu,wc,ws≥0非负5-1DEA:模型求解县医院效率评价的DEA线性规划模型有5个决策变量和8个约束条件，最优解如下：5-1DEA:结果解读我们首先注意到目标函数值显示县医院的效率得分为0.905。这个分数告诉我们虚拟医院通过使用不超过县医院需要输入资源的90.5%，可以达到至少县医院能达到的每个输出的水平。我们看出虚拟医院是由总医院（wg=0.212）、大学医院（wu=0.260）、和州医院（ws=0.527）加权平均形成的。剩余变量(约束2-5)虚拟医院的每个输出至少与县医院一样多，相比县医院，它多出1.6个培训过的护士和37个培训过的实习医生松弛变量(约束6-8)约束条件6和7的松弛值说明虚拟医院使用的FTE非医务人员和物资花费资源比县医院使用资源的90.5%还少。由此，我们得出结论，县医院与同组其他医院相比是相对低效率的。鉴于DEA分析的结果，医院管理者应该检查县医院的运营作业以确定应该如何更有效地利用相关资源。5-1DEA方法总结下面的分步步骤能帮助你为其他类型的DEA应用构建线性规划模型。注意，我们要衡量其相对效率的运营单元被记作第j个运营单元。步骤1. 定义决策变量，也就是权重（每个运营单元都有一个），用于确定虚拟运营单元的输入和输出。步骤2. 写出要求权重总和等于1的一个约束条件。步骤3. 对每个输出指标，写出一个要求虚拟运营单元的输出大于或等于第j个运营单元对应输出的约束条件。步骤4. 定义一个决策变量E，它用于确定第j个运营单元的输入可用于虚拟运营单元的比例。步骤5. 对每个输入指标，写出一个要求虚拟运营单元的输入小于或等于虚拟运营单元可用资源的约束条件。步骤6. 写出目标函数，即MinE。收益管理休闲航空公司收益管理是在库存水平一定的情况下，通过对不易保存产品的短期需求管理，以取得潜在收益的最大化。这个方法最早由美国航空公司提出，最初是用于确定航班中折扣价座位和全价座位的数量。现在的应用领域包括旅馆、公寓出租、汽车出租、邮轮以及高尔夫球场。为了说明收益管理的基本原理，我们将用一个线性规划模型为休闲航空公司（LeisureAir）建立一个收益管理计划，这是一家为匹兹堡、纽瓦克、夏洛特、默特尔比奇和奥兰多提供航空服务的地区航空公司。5-2休闲航空公司:问题描述休闲航空公司有两架波音737-400飞机，一架的驻场在匹兹堡出，另一架的驻场在纽瓦克。

两架飞机都有一个容量为132个座位的经济舱。每天早上驻场在匹兹堡的飞机在夏洛特中途停留后飞往奥兰多，驻场在纽瓦克的飞机在夏洛特中途停留后飞往默特尔比奇。每天结束前，两架飞机再回到其出发地。为了把问题的规模控制在一个合理的范围内，我们只考虑早上匹兹堡到夏洛特、夏洛特到奥兰多、纽瓦克到夏洛特，以及夏洛特到默特尔比奇的航程。休闲航空公司的机票有两个价位等级：折扣票Q等级以及全价票Y等级。预订折扣票Q等级必须提前14天并且要在目的地城市停留一晚（周六）。使用全价票Y等级可以在任何时间预订，而且日后改签也没有任何损失。

为了确定休闲航空能为其顾客提供航线和费用选择，我们不仅须考虑每个航班的起飞地和目的地，还得考虑费用等级。5-2休闲航空公司:模型建立休闲航空16个起飞地—目的地—旅程费5月5日，休闲航空为其16个ODIF确定费用并对顾客需求进行预测。决策变量为了建立一个线性规划模型来确定休闲航空应为每种费用等级分配多少个座位，我们需要定义16个决策变量，即为每个起飞地—目的地—旅程费定义一个变量。我们用P代表匹兹堡，N代表纽瓦克，C代表夏洛特，M代表默特尔比奇，O代表奥兰多，决策变量采用下面的形式：PCQ:

分配给匹兹堡—夏洛特Q等级的座位数PMQ:分配给匹兹堡—默特尔比奇Q等级的座位数POQ:分配给匹兹堡—奥兰多Q等级的座位数PCY:

分配给匹兹堡—夏洛特Y等级的座位数 ⋮NCQ:分配给纽瓦克—夏洛特Q等级的座位数 ⋮COY:分配给夏洛特—奥兰多Y等级的座位数5-2休闲航空公司:约束条件容量的约束条件

需求的约束条件5-2休闲航空公司:完整的线性规划（LP）模型

5-2休闲航空公司:模型求解休闲航空收益管理问题的最优解如图所示：5-2休闲航空公司:结果解读最优解的值是103103美元。最优解显示PCQ=33，PMQ=44，POQ=22，PCY=16，等等。我们看到约束条件6的对偶值为85美元。对偶值告诉我们如果再多增加一个Q等级座位给匹兹堡—默特尔比奇，收益将增加85美元。收益的这个增量被称作这个起飞地—目的地—旅程费的出价。一般来说，一个ODIF的出价会告诉休闲航空预订代理，当这个ODIF售空后再增加一个额外预订的价值。通过观察图中需求的约束条件的对偶值，我们看到最高的对偶值（出价）为约束条件8（PCY≤16）的376美元。给定这个收益贡献，预订代理将最可能接受此额外预订，尽管这样会导致航班的超量预订。然而，当前解中的出价信息和一些简单的决策规则也能使预订代理做出改进公司收益的决策。理论上，每次在一个起飞地—目的地—旅程费的容量内接受一个预订，线性规划模型就应该被更新，进行重新求解以得到新的座位分配和出价信息。在实践中，因为涉及大量航班，所以实时更新分配是不实际的。5-3投资组合模型和资产分配共同基金的投资组合资产分配是关于决定如何分配投资资金到多种资产种类的过程，如股票、债券、共同基金、房地产和现金等。

投资组合模型用于确定应该在每种资产种类上分配的投资资金的比例。它的目标是建立一个投资组合，使风险和回报达到最佳平衡。Hauck投资服务公司希望建立一个投资组合模型，用于确定一个由6种共同基金构成的最佳投资组合。共同基金的年回报率Hauck投资服务公司的投资组合管理者认为下表可以代表这6种共同基金下一年回报的所有可能性。第1年所有共同基金的年回报都是好的，第2年大部分共同基金的回报也是好的，但是第3年小市值价值基金的回报不好，第4年中期债券基金的回报不好，第5年6种共同基金中有4种的回报都不好。5-3保守的投资组合决策变量Hauck投资服务公司的一个投资组合管理者被要求为公司的保守客户建立一个投资组合，这类客户对风险有很强烈的规避倾向。.经理的任务是决定投资在这6种共同基金上的各个比例，以使投资组合能以最小的风险提供最大可能的回报。

为了确定每种共同基金的投资比例，我们使用下面的决策变量：FS=外国股票基金的投资比例IB=中期债券基金的投资比例LG=大市值成长基金的投资比例LV=大市值价值基金的投资比例SG=小市值成长基金的投资比例SV=小市值价值基金的投资比例约束条件和目标函数

5-3保守的投资组合：完整的线性规划（LP）模型完整的模型如下所示：MaxM

s.t.10.06FS+17.64IB+32.41LG+32.36LV+33.44SG+24.56SV≥M13.12FS+

3.25IB+18.71LG+20.61LV+19.40SG+25.32SV≥M13.47FS+7.51IB+33.28LG+12.93LV+3.85SG−

6.70SV≥M45.42FS+1.33IB+41.46LG+7.06LV+58.68SG+5.43SV≥M−21.93FS+7.36IB−23.26LG−5.37LV−9.02SG+17.31SV≥MFS+IB+LG+LV+SG+SV=1M,FS,IB,LG,LV,SG,SV≥05-3保守的投资组合:模型求解和结果解释Hauck投资服务公司最大最小模型的最优解如图所示：目标函数的最优值是6.445，因此，最优投资组合在情形最差的方案下能得到6.445%的回报率。最优解要求55.4%的资金投资于中期债券基金，13.2%的资金投资于大市值成长基金，以及31.4%的资金投资于小市值价值基金。约束条件3、4和5对应方案3、4和5（表5-4中的第3年、第4年和第5年）。这些约束条件的剩余变量为0表示：如果这3个方案中任意一个发生，投资组合的回报率将是M=6.445%。约束条件1的剩余变量为15.321，表示如果方案1发生，投资组合的回报率将比M=6.445%多15.321%。因此，如果方案1发生，投资组合回报率将是6.445%+15.321%=21.766%。至于约束条件2的剩余变量，我们看到如果方案2发生，投资组合回报率将是6.445%+5.785%=12.230%。5-3中等风险的投资组合决策变量投资服务公司的投资组合经理愿意为这样一类客户建立一个投资组合，这类客户为了获得更好的回报而愿意接受中等程度的风险。

假定这类客户愿意接受一些风险，但是不愿意投资组合的年回报率低于2%。通过设定最大最小模型中的最低回报约束条件M=2，我们能使模型提供一个年回报率至少为2%的解。约束条件和目标函数

5-3中等风险的投资组合：完整的线性规划（LP）模型完整的模型如下所示：Max0.2R1+0.2R2+0.2R3+0.2R4+0.2R5

s.t.10.06FS+17.64IB+32.41LG+32.36LV+33.44SG+24.56SV=R113.12FS+

3.25IB+18.71LG+20.61LV+19.40SG+25.32SV=R213.47FS+7.51IB+33.28LG+12.93LV+3.85SG−

6.70SV=R345.42FS+1.33IB+41.46LG+7.06LV+58.68SG+5.43SV=R4−21.93FS+7.36IB−23.26LG−5.37LV−9.02SG+17.31SV=R5R1≥2R2≥2R3≥2R4≥2R5≥2FS+IB+LG+LV+SG+SV=1M,FS,IB,LG,LV,SG,SV≥0这个包含11个变量和11个约束条件的投资组合最优化问题完整的线性规划结果如图所示：目标函数值表明这样分配提供了17.33%的最大预期回报率。最优解如图所示。最优分配是投资10.8%在大市值成长基金、41.5%在小市值成长基金、47.7%在小市值价值基金。从剩余变量中，我们看到如果方案3或5发生（约束条件8和10是有效的），投资组合的回报率将只是2%。如果方案1、2或4发生，回报率将非常好：如果方案1发生，投资组合回报率将是29.093%；如果方案2发生，则为22.149%；如果方案4发生，则为31.417%。5-3中等风险的投资组合:模型求解和结果解释5-4博弈论导入在博弈论中，互相竞争的两个或更多的决策制定者被称作参与者。

每个参与者在预先不知道其他参与者所选策略的情况下，选择多个策略中的一个。

竞争策略组合为参与者提供了博弈的价值。这一节描述两人零和博弈。“两人”意味着有两个参与者参与博弈“零和”意味着一个参与者的获益（损失）等于另一个参与者的损失（获益）。市场份额的竞争假定两家公司是一种特殊产品仅有的制造商，它们互相竞争市场份额。在设计来年营销策略时，每家公司将选择设计好的三个策略之一来从对方公司中争夺市场份额。假定这三个策略对两家公司都是一样的，如下所示：策略1: 增加广告策略2: 提供数量折扣策略3: 延长保修效益表显示了在每个策略组合下，公司A市场份额的百分比收益。因为这是一个零和博弈，所以公司A在市场份额的任意收益是公司B市场份额的损失。5-4零和博弈效益表例如，如果公司A增加广告（a1），公司B延长保修期（b3），公司A的市场份额将领先，增加2%，而公司B的市场份额将相应减少2%。公司A想要最大化其收益，即增加市场份额；公司B想要最小化收益，因为公司A市场份额的增加是公司B市场份额的减少。两家公司的最佳策略公司A的最大最小策略：公司A选择提供最大的行最小值的策略。公司B的最小最大策略:公司B选择能提供最小的列最大值的策略。5-4纯策略解的确定如果选择一个策略对两个参与者都是最优的，并且无论对方做什么都会坚持这个策略，这种博弈就有纯策略解。纯策略解的条件如下所示：如果行最小值=列最大值，则一个博弈有纯策略解这种博弈被称作有一个鞍点或一个均衡点。如果纯策略解存在，它就是博弈的最优解即使一家公司提前发现其对手的纯策略，公司也不能从改变它自身纯策略中获得任何优势因为在我们的例子中这个等式成立，所以博弈的解就是公司A增加广告（策略a1）和公司B延长保修（策略b3）。公司A的市场份额将增加2%，公司B的市场份额将减少2%。如果行最小值的最大值不等于列最大值的最小值，纯策略解不存在。

在这种情形下，混合策略解变成最优解。.在后面的讨论中，我们定义混合策略解，并说明如何用线性规划来确定每个参与者的最优混合策略。5-4混合策略解的确定修改后的的效益表让我们继续两家公司市场份额的博弈，并考虑稍微修改后的效益表。如果公司A和公司B都选择延长保修策略，公司A现在的收益是市场份额增加5%而不是之前的0。预期收益

5-4混合