第5章 高级线性规划应用

第五章高级线性规划应用,教师：朱玉春教授单位：经济管理学院2011年,西北农林科技大学,本章主要内容,5.1数据包络分析5.2收益管理5.3投资组合模型和资产分配5.4博弈论,5.1数据包络分析,DEA是线性规划用于测量有相同目标和目的的工作单位的相对效率的一种应用。5.1.1医院绩效评价总医院、大学医院、县医院和州医院的管理者聚在一起讨论能以自己的医院帮助彼此改进绩效的方法。一个顾问建议他们采用DEA来测量每所医院相对于所有4所医院的绩效。在讨论这种评价如何进行时，确定出下面三种输入测量和四种输出测量：,5.1数据包络分析,输入测量全日制非医生人员的数目物资花费总数可用床日的数目。输出测量具有医疗保险服务的病人日；无医疗保险服务的病人日；培训的护士数目；培训的实习医生数目。这4个医院输入和输出的年测量结果如下表所示。我们接下来说明DEA如何利用这些数据来找出相对低效的医院。,5.1数据包络分析,5.1数据包络分析,5.1数据包络分析,5.1.2DEA方法概述在DEA的应用中，为每个要评价其效率的医院都建立了一个线性规划模型。为说明该建模过程，我们构造了一个用来确定县医院相对效率的线性规划。首先，使用一个线性规划模型，基于有相同目标的所有运营单位的输入和输出，构建一个假定的合成单位，在这个例子中是一家合成的医院。对这四所医院的每个输出测量，合成的医院的输出由全部4家医院对应输出的加权平均计算而得。对每个输入测量，合成的医院的输入由采用相同权重的全部四家医院对应输入的加权平均计算得到。线性规划模型中的约束条件要求合成医院的所有输出大于等于要评价的县医院的输出。如果组合单位的输入能显示出少于县医院的输入，那么就说明合成医院能利用较少的输入产出一样或更多的输出。在这种情况下，模型就说明合成医院比县医院更有效率。,5.1数据包络分析,5.1.3DEA线性规划模型为了确定在计算合成医院的输出和输入时每家医院所占的权重，我们采用下面的决策变量：Wg=总医院输入和输出采用的权重Wu=大学医院Wc=县医院Ws=州医院DEA方法要求这些权重的总和等于1，因此第一个约束条件就是wg+wu+wc+ws=1一般来说，每个DEA线性规划模型都包含一个要求运营单位权重之和等于1的约束条件。,5.1数据包络分析,合成医院的医疗保险病人日数目=（总医院的医疗保险病人日数目）wg+（大学医院的医疗保险病人日数目）wu+（县医院的医疗保险病人日数目）wc+（州医院的医疗保险病人日数目）ws用数据代替每所医院医疗保险病人日的数目，得到下面的表达式：合成医院的医疗保险病人日数目=48.14wg+34.62wu+36.72wc+33.16ws用相同的方法可以计算合成医院的其他输出测量。计算结果如下：,wgwuwcws,5.1数据包络分析,医疗保险34.62非医疗保险27.11护士148实习医生27,医疗保险48.14非医疗保险43.10护士253实习医生41,医疗保险36.72非医疗保险45.98护士175实习医生23,总医院,大学医院,县医院,医疗保险33.16非医疗保险56.46护士160实习医生84,州医院,5.1数据包络分析,医疗保险48.14wg+34.62wu+36.72wc+33.16ws非医疗保险43.10wg+27.11wu+45.98wc+56.46ws护士253wg+148wu+175wc+160实习医生41wg+27wu+23wc+84ws,组合医院,5.1数据包络分析,对这四个输出测量中的每一个，我们需要一个限制合成医院的输出大于等于县医院的输出的约束条件。输出的约束条件的总形式为：合成医院的输出县医院的输出因为县医院的医疗保险病人日的数目是36.72，因此医疗保险病人日对应的输出约束为48.14wg+34.62wu+36.72wc+33.16ws36.72同理，其他三个为：43.10wg+27.11wu+45.98wc+56.46ws45.98253wg+148wu+175wc+160ws17541wg+27wu+23wc+84ws23,5.1数据包络分析,下一步，我们需要考虑能够构建出合成医院输入与合成医院可用资源之间关系的约束条件。3个输入测量都需要一个约束条件。输入的约束条件的总形式如下：合成医院的输入合成医院可用的资源对于每个输入测量，合成医院的输入是4家医院每个对应输入的加权平均。因此，对于输入测量1，全日制非医生人员的数目，合成医院的输入为合成医院FTE非医生人员数目=（总医院FTE非医生人员数目）wg+（大学医院FTE非医生人员数目）wu+（县医院FTE非医生人员数目）wc+（州医院FTE非医生人员数目）ws用上图的数据代替每个医院全日制非医生人员的数目，我们得到合成医院全日制非医生人员数目的表达式如下：285.20wg+162.30wu+275.70wc+210.40ws,5.1数据包络分析,我们可以写出其他两个输入测量的表达式，如下图所示。,162.30FTE非医生人员128.70物资花费64.21床日,285.20FTE非医生人员123.80物资花费106.72床日,275.70FTE非医生人员348.50物资花费104.10床日,总医院,大学医院,县医院,州医院,210.40FTE非医生人员154.10物资花费104.04床日,5.1数据包络分析,FTE非医生人员物资花费床日,组合医院,285.20wg+162.30wu+275.70wc+210.40ws123.80wg+128.70wu+348.50wc+154.10ws106.72wg+64.21wu+104.10wc+104.04ws,5.1数据包络分析,在DEA方法中，这些右侧值是县医院输入值的一个百分比，因此，我们必须引入下面的决策变量：E=县医院输入可用于合成医院的百分比如果E=1，合成医院可用的FTE非医生人员数目就为275.70，与县医院相同。E1，则合成医院就按比例拥有更多的非医生人数；E1，则更少。E被称为效率指标。我们现在可以写出与合成医院可用的FTE非医生人员数目相对应的输入约束条件：285.20wg+162.30wu+275.70wc+210.40ws275.70E同理，物资和床日的输入约束条件为：123.80wg+128.70wu+348.50wc+154.10ws348.50E106.72wg+64.21wu+104.10wc+104.04ws104.10E,5.1数据包络分析,DEA模型的目标函数就是最小化E的值，其等价于最小化合成医院可用的输入资源。目标函数可以写为：MinEDEA效率的结论是基于E的最佳目标函数值的。决策规则如下：E=1，合成医院需要与县医院一样多的输入。没有证据表明县医院是低效的。E1，合成医院需要较少的输入就能得到县医院达到的产出。合成医院更有效。县医院效率评价的DEA线性规划模型有5个决策变量和8个约束条件。,5.1数据包络分析,完整模型如下:MinES.t.wg+wu+wc+ws=148.14wg+34.62wu+36.72wc+33.16ws36.7243.10wg+27.11wu+45.98wc+56.46ws45.98253wg+148wu+175wc+16017541wg+27wu+23wc+84ws23285.20wg+162.30wu+275.70wc+210.40ws275.70E123.80wg+128.70wu+348.50wc+154.10ws348.50E106.72wg+64.21wu+104.10wcc+104.04ws104.10EE,wg,wu,wc,ws0,5.1数据包络分析,从解中可以看出合成医院是由总医院（wg=0.212）、大学医院（wu=0.260）和州医院（ws=0.527）加权平均形成的。合成医院的每一个输入和输出都是由这3家医院的输入和输出进行相同的加权平均得来的。,5.1数据包络分析,5.1.4DEA方法总结下面的步骤能帮你为其他类型的DEA应用构建线性规划模型。我们要测量其相对效率的运营单位被记作第j个运营单位。第一步定义决策变量或权重（每个运营单位都有一个），用于确定合成运营单位的输入和输出。第二步写出要求权重总和等于1的约束条件。第三步对每个输出测量，写出一个要求合成运营单位的输出大于或等于第j个运营单位对应输出的约束条件。第四步定义一个决策变量E，它用于确定第j个运营单位的输入可用于合成运营单位的比例。第五步，对于每个输入测量，写出一个要求合成运营单位的输入小于或等于合成运营单位可用资源的约束条件。第六步写出目标函数，为MinE,5.2收益管理,建立一个收益系统是昂贵费时的，但是其潜在收益相当大。例如，美国航空公司采用的收益管理系统使其年增加收益近1亿元。为了说明收益管理的基本原理，我们将用一个线性规划模型为休闲航空公司建立一个收益管理计划。这是一家为匹兹堡、纽瓦克、夏洛特、默特尔比奇和奥兰多提供航空服务的地区航空公司。休闲航空公司有两架波音737-400飞机，一架于匹兹堡出发，另一架于纽瓦克出发。两架飞机都有一个容量为132座位的经济舱。每天早上，由匹兹堡出发的飞机在夏洛特中途停留后飞往奥兰多，由纽瓦克出发的飞机也在夏洛特中途停留后飞往默特尔比奇。当天，两架飞机再回到其出发地。为了把问题的规模控制在一个合理范围内，我们只考虑早上匹兹堡到夏洛特、夏洛特到奥兰多、纽瓦克到夏洛特以及夏洛特到默特尔比奇的航程。,5.2收益管理,休闲航空公司的机票有两个价位等级：折扣票Q级和全票Y级。预定折扣票Q级必须提前14天并且要在目的地城市停留周六一晚。预定全价Y等级可以在任何时间进行，而且要在日后改变预订也没有任何损失。为了确定休闲航空能为其顾客提供航线和费用选择，我们不仅必须考虑每次航班的起飞地和目的地，而且还得考虑费用等级。例如，可能的客户选择有Q等级的匹兹堡到夏洛特、Q等级的纽瓦克到奥兰多、Y等级的夏洛特到默特尔比奇等。把每个客户选择记作起飞地-目的地-旅程费（ODIF）。在5月5日，休闲航空为其16个ODIF确定费用并预测顾客需求。这些数据如表所示。,5.2收益管理,5.2收益管理,假定在4月4日，一位顾客打电话到休闲航空公司的预定处，要求预订5月5日从匹兹堡到默特尔比奇的Q等级座位航班。休闲航空应该接受这个预定吗？制定这个决策的困难之处在于即使休闲航空可能有剩余的座位，但休闲航空可能不愿意接受只有268美元的Q等级费用的预定，尤其是了解到或有可能在之后能以456美元的Y等级费用销售此预定。为了运行其预定系统，确定有多少个Q等级座位和Y等级座位是休闲航空需要作出的重要决策。为了建立一个线性规划模型，来确定休闲航空应为每种费用等级分配多少个座位，我们需要定义16个决策变量，即为每个起飞地-目的地-旅程费选择定义一个变量。用P代表匹兹堡，N代表纽瓦克，C代表夏洛特，M代表默特尔比奇，O代表奥兰多，决策变量采用下面的形式：PCQ=分配给匹兹堡-夏洛特Q等级的座位数PMQ=分配给匹兹堡-默特尔比奇的Q等级座位数POQ=分配给匹兹堡-奥兰多Q等级座位数PCY=分配给匹兹堡-夏洛特Y等级座位数,5.2收益管理,.NCQ=分配给纽瓦克-夏洛特Q等级座位数.COY=分配给夏洛特-奥兰多Y等级的座位数目标是最大化总收益。使用上表数据，我们可以写出线性规划模型的目标函数，如下：Max178PCQ+268PMQ+228POQ+380PCY+456PMY+560POY+199NCQ+249NMQ+349NOQ+385NCY+444NMY+580NOY+179CMQ+380CMY+224COQ+582COY,5.2收益管理,接下来，我们需写出约束条件。容量约束条件为：PCQ+PMQ+POQ+PCY+PMY+POY132匹兹堡-夏洛特NCQ+NMQ+NOQ+NCY+NMY+NOY132纽瓦克-夏洛特PMQ+PMY+NMQ+NMY+CMQ+CMY132夏洛特-默特尔比奇POQ+POY+NOQ+NOY+COQ+COY132夏洛特-奥兰多需求约束条件基于预测需求量限制每个ODIF的座位数目。前四个需求约束条件如下：PCQ33匹兹堡-夏洛特Q等级PMQ44匹兹堡-默特尔比奇Q等级POQ45匹兹堡-奥兰多Q等级PCY16匹兹堡-夏洛特Y等级,5.2收益管理,完整的线性规划模型有16个决策变量、4个容量约束条件和16个需求约束条件，Max178PCQ+268PMQ+228POQ+380PCY+456PMY+560POY+199NCQ+249NMQ+349NOQ+385NCY+444NMY+580NOY+179CMQ+380CMY+224COQ+582COYPCQ+PMQ+POQ+PCY+PMY+POY132匹兹堡-夏洛特NCQ+NMQ+NOQ+NCY+NMY+NOY132纽瓦克-夏洛特PMQ+PMY+NMQ+NMY+CMQ+CMY132夏洛特-默特尔比奇POQ+POY+NOQ+NOY+COQ+COY132夏洛特-奥兰多需求约束条件：PCQ33PMQ44POQ45PCY16.CMQ64CMY8COQ46COY10PCQ,PMY,POQ,PCY,.,COY0,5.2收益管理,最优解的值为103.103美元。PCQ=33，PMQ=44，POQ=22，PCY=16等。因此，为了最大化收益，应该分配33个Q等级座位给匹兹堡-夏洛特，44个Q等级座位给匹兹堡-默特尔比奇，22个Q等级座位给匹兹堡-奥兰多，16个Y等级座位给匹兹堡-夏洛特等。,5.3投资组合模型和资产分配,5.3.1共有基金的投资组合Hauck投资服务公司为风险偏好的投资者设计年金、IRA、401（K）计划，以及其他投资手段。Hauck愿意建立一个投资组合模型，能用于确定一个混合有6种共有基金的最佳投资组合。可以用多种方法代表风险，但是对金融资产的投资组合，所有的方法都与回报的变化性相关。下表显示了6种共有基金的5年一年期的年回报率。第一年表示所有共有基金的年回报都是好的，第二年内大部分共有基金的年回报也是好的，但是第三年小市值价值基金的年回报不好，第四年的中期债券基金的年回报不好，以及第五年6个共有基金中有四个的年回报都不好。,5.3投资组合模型和资产分配,5.3投资组合模型和资产分配,5.3.2保守的投资组合Hauck的一个投资组合管理者被要求为公司的保守客户建立一个投资组合。这类客户对风险有强烈的规避意识。经历的任务是决定投资在这六种共有基金上的各个比例，使投资组合能以最小的风险提供最大可能的回报。在投资组合模型中，风险通过多样化而达到最小。为了说明多样化的价值，首先假定把所有投资放在这六种共有基金中的一种上。现在让我们看一下如何构建这些共有基金的一个多样化投资组合，以最小化损失的风险。为了确定投资于每种共有基金的投资比例，我们使用下面的决策变量：,5.3投资组合模型和资产分配,FS=投资于外国股票共有基金的投资比例LB=投资于中期债券基金的投资比例LG=投资于大市值成长基金的投资比例LV=投资于大市值价值基金的投资比例SG=投资于小市值成长基金的投资比例SV=投资于小市值价值基金的投资比例这些比例总和=1，即FS+LB+LG+LV+SG+SV=1,5.3投资组合模型和资产分配,5个计划方案的投资组合回报如下所示：方案1的回报：R1=10.06FS+17.64LB+32.41LG+32.36LV+33.44SG+24.56SV其他的依次R2=13.12FS+3.25LB+18.71LG+20.61LV+19.40SG+25.32SVR3=13.47FS+7.51LB+33.28LG+12.93LV+3.85SG-6.70SVR4=45.42FS-1.33LB+41.46LG+7.06LV+58.68SG+5.43SVR5=-21.93FS+7.361LB-23.26LG-5.37LV-9.02SG+17.31SV,5.3投资组合模型和资产分配,我们引入变量M代表投资组合的最低回报。为了保证每种方案下的回报都至少与最低回报M一样大，我们添加下面的最低回报约束条件：R1M方案1最低回报R2M方案2最低回报R3M方案3最低回报R4M方案4最低回报R5M方案5最低回报带入前面的5个计划方案的投资组合回报，有：10.06FS+17.64LB+32.41LG+32.36LV+33.44SG+24.56SVM方案113.12FS+3.25LB+18.71LG+20.61LV+19.40SG+25.32SVM方案213.47FS+7.51LB+33.28LG+12.93LV+3.85SG-6.70SVM方案345.42FS-1.33LB+41.46LG+7.06LV+58.68SG+5.43SVM方案4-21.93FS+7.361LB-23.26LG-5.37LV-9.02SG+17.31SVM方案5,5.3投资组合模型和资产分配,完整的线性规划模型如下：目标函数MaxMS.t.10.06FS+17.64LB+32.41LG+32.36LV+33.44SG+24.56SVM13.12FS+3.25LB+18.71LG+20.61LV+19.40SG+25.32SVM13.47FS+7.51LB+33.28LG+12.93LV+3.85SG-6.70SVM45.42FS-1.33LB+41.46LG+7.06LV+58.68SG+5.43SVM-21.93FS+7.361LB-23.26LG-5.37LV-9.02SG+17.31SVMFS+LB+LG+LV+SG+SV=1M,FS,LB,LG,LV,SG,SV0,5.3投资组合模型和资产分配,解得，目标函数最优值6.445.因此最优投资组合在情形最差的方案下挣6.445%。最优解要求55.4%的资金投资于中期债券基金，13.2%的资金投资于大市值成长基金，31.4%的资金投资于小市值价值基金。,5.3投资组合模型和资产分配,5.3.3中等风险的投资组合Hauck的投资组合经理也愿意为这样一类客户建立一个投资组合，这类客户为了试图获得更好的回报而愿意接受中等程度的风险。假定这种风险分类的客户愿意接受一些风险，但是不愿意投资组合的年回报低于2%。通过设定最大最小模型中的最低回报约束条件M=2，我们能约束模型来提供一个年回报最少2%的解。提供年回报最少2%的最低回报约束条件，如下：R12方案1最低回报R22方案2最低回报R32方案3最低回报R42方案4最低回报R52方案5最低回报,5.3投资组合模型和资产分配,带入前面的R1，R2，有：10.06FS+17.64LB+32.41LG+32.36LV+33.44SG+24.56SV2方案113.12FS+3.25LB+18.71LG+20.61LV+19.40SG+25.32SV2方案213.47FS+7.51LB+33.28LG+12.93LV+3.85SG-6.70SV2方案345.42FS-1.33LB+41.46LG+7.06LV+58.68SG+5.43SV2方案4-21.93FS+7.361LB-23.26LG-5.37LV-9.02SG+17.31SV2方案5这个投资组合最优化问题需要一个不同的目标。一个普遍方法是最大化投资组合的回报预期值。例如，我们假定计划方案等可能性发生，我们为每个方案分配一个0.2的概率。此时目标函数是：回报的预期值=0.2R1+0.2R2+0.2R3+0.2R4+0.2R5,5.3投资组合模型和资产分配,目标函数是：12.03FS+6.89IB+20.52LG+13.52LV+21.27SG+13.18SV完整线性规划表达式为：Max12.03FS+6.89LB+20.52LG+13.52LV+21.27SG+13.18SVS.t.10.06FS+17.64LB+32.41LG+32.36LV+33.44SG+24.56SV2方案113.12FS+3.25LB+18.71LG+20.61LV+19.40SG+25.32SV2方案213.47FS+7.51LB+33.28LG+12.93LV+3.85SG-6.70SV2方案345.42FS-1.33LB+41.46LG+7.06LV+58.68SG+5.43SV2方案4-21.93FS+7.361LB-23.26LG-5.37LV-9.02SG+17.31SV2方案5FS+LB+LG+LV+SG+SV=1FS,LB,LG,LV,SG,SV0解得，最优分配是投资10.8%在大市值成长共有基金，41.5%在小市值成长共有基金，47.7%在小市值价值共有基金。,5.4博弈论,5.4.1市场份额的竞争假定两家公司是一种特殊产品仅有的制造商，他们互相竞争市场份额。在为来年计划营销策略时，每家公司将选择设计好的3个策略之一来从对方公司中争夺市场份额。这三个策略，假定对两家公司都是一样的，如下：策略1：增加广告。策略2：提供数量折扣策略3:延长保修期。下表是效益表，显示了在策略的每个组合下，公司A市场份额的百分率收益。因为这是一个零和博弈，公司A在市场份额的任意收益是公司B市场份额的损失。,5.4博弈论,5.4博弈论,这个市场份额博弈满足两人零和博弈的条件。两家公司的最佳策略分别是什么呢？假定公司A选择策略a1，依赖于B的策略，公司A的市场份额可能增加4%、3%或2%。这一点，公司A假定B会选择对其最好的策略。因此，A选择策略a1，A认为B将选择其最优策略b3，这将限制A市场份额增加2%。继续这样的逻辑，公司A通过应对B可能选择的策略来分析博弈。这样，A确定了每个策略的最低效益，也就是效益表每一行的最小值。,5.4博弈论,考虑行最小值的各项，我们知道通过选择策略a1，公司A可以保证增加最低2%。A2可能导致减少1%，a3导致减少2%。在比较行最小值后，A选择提供最大的行最小值的策略。这称为最大最小策略。考虑列最大值这一行的各项，公司B选择策略b3能保证市场份额的减少不超过2%。B1可能导致减少5%，b2可能导致减少4%。在比较列最大值后，B选择了能提供最小的列最大值的策略。称为最小最大策略。,5.4博弈论,5.4.2纯策略的确定如果选择一个策略对两个参与者都是最优的，并且无论对方做什么都会坚持这个策略，这种博弈就有纯策略解。这种博弈有一个均衡点。因此，纯策略是参与者的最优策略。拥有纯策略解的条件：行最小值=列最大值，则有纯策略解。确定每个参与者的最优纯策略的步骤：第一步，计算每行的最小收益（参与者A）第二步，对参与者A，选择提供最大的行最小值的策略。第三步，计算每列的最大收益（B）第五步，对B，选择提供最小的列最大值的策略。第六步，如果行最小值的最大值等于列最大值的最小值，这个值就是博弈的值，并且纯策略解存在。A的最优纯策略在第二步中确定，B的最优纯策略在第四步确定。,5.4博弈论,5.4.3混合策略解的确定修改后的收益表如右图。只有一收益改变了。,5.4博弈论,在分析博弈确定纯策略解是否存在时，我们发现列最大值的最小值为4%，行最小值的最大值为2%。因为这两个不等，所以纯策略解不存在。此时，每个公司可预见的并且无论另一个公司做什么都选择纯策略不是最优的。这两个参与者的最优解采用了一个混合策略。混合策略中，每个参与者根据概率分布来选择他的策略。博弈时，每家公司将使用其概率分布来随机选择策略中的一个。从A的立场来考虑。A将基于以下概率选择3个中的一个：PA1=A选择a1的概率PA2=A选择a2的概率PA3=A选择a3的概率,5.4博弈论,把每个收益用其概率加权并相加得出公司A市场份额增加的预期值。B选择策略b1，这个预期值称为选择b1的预期收益，写作：EG(b1)=4PA1-PA2+5PA3例如，公司A以相等的概率（1/3）采用混合策略，对B的每个策略，A的市场份额预期收益如下：EG(b1)=4PA1-1PA2+5PA3=2.67EG(b2)=3PA1+4PA2-2PA3=1.67EG(b3)=2PA1+PA2+5PA3=2.67博弈论的逻辑假定A采用一个混合策略，B将选择能最小化A预期收益的策略。根据这些结论，A认为B将选择策略b2来限制A市场份额预期收益为1.67%。因为A的纯策略a1提供2%的市场份额增加，所以等概率的混合策略不是A的最优策略。,5.4博弈论,给定概率PA1，PA2，PA3和预期收益表达式，博弈论假定B选择提供A最小预期收益的策略。因此，B基于下面的公式，来选择b1，b2或b3，为minEG(b1),EG(b2),EG(b3)当B选择它的策略时，博弈的值将是最小预期收益。这个策略将最小化A市场份额的预期收益。A将用最大最小策略来选择其最优混合策略，这就是最大化最小预期收益。目标写作：Max【minEG(b1),EG(b2),EG(b3)】定义GAINA为A市场份额的最优预期收益。B将选择最小化这个预期收益的策略，所以我们知道GAINA等于minEG(b1),EG(b2),EG(b3)。因此，单个预期收益为EG(b1),EG(b2),EG(b3)必须全部大于或等于GAINA。如果B选择策略b1，我们知道EG(b1)GAINA,5.4博弈论,使用概率PA1、PA2和PA3和预期收益表达式，这个条件写为：4PA1-1PA2+5PA