数据模型与决策-71(线性与非线性规划)

数据、模型与决策丁邦俊[e-mail]线性规划与非线性规划线性规划问题线性规划模型线性规划的求解非线性规划例某家电公司准备将一种新型电视机在三家商场进行销售，每一个商场的批发价和推销费及产品的利润如表所示。由于该电视机的性能良好，各商场都纷纷争购，但公司每月的生产能力有限，只能生产1000台，故公司规定:甲商场至少经销100台，至多200台；乙至少经销300台，丙商场至少经销200台。公司计划在一个月内的广告预算费为8000元，推销人员最高可用工时数为1500，同时，公司只根据经销数进行生产，试问：公司下个月采取的市场对策？一个例子经销商场销售利润(元/台)广告费(元/台)推销工时(小时/台)甲商场50122乙商场8073丙商场7084甲乙丙三家市场销售电视机情况S.t.建立线性模型S.t.线性规划模型线性规划求解方法图解法√计算机解法—Excel,Lindo√单纯形方法（需要矩阵知识）×线性规划求解—图解法例3生产A、B两种产品，需要某种原料的数量和使用某种设备的时间如下：单位产品的消耗资源总量AB原料6432设备10230单位利润(万元/吨)52S.t.线性规划求解—图解法线性规划求解—图解法24681012141624681012141610x+2y=306x+4y=32xyP(2,5)0Q(5,2)5x+2y=0线性规划求解—Excel工具规划求解课堂演示：线性规划的对偶问题S.t.关于影子价格的讨论。非线性规划—举例*优利投资公司的投资组合仅包含三支股票STOCK1、STOCK2STOCK3，他们的预期回报率和风险参数见下表。问在预期回报率一定的情况下，三支股票在投资组合中各占多大的比例才能使投资组合的风险最小？回报率平均数0.140.110.05回报率标准差0.20.150.08相关系数表stock1stock2stock3stock11stock20.61stock3-0.4-0.71协方差表stock1stock2stock3stock10.04stock20.0180.0225stock30.0064-0.70.0064三支股票的数据规划建模设三支股票的投资比例分别为a、b、c，那么得到下面关系:0,0,01.)3,2(2)3,1(2)2,1(2)3()2()1()321(:222cbacbastabVarabVarabVarstockVarcstockVarbstockVarastockcstockbstockaVarMinExcel求解投资比例分别为0.3390、0.3249、0.3361，此时风险达到最小值0.0084三支股票的数据答案：优利公司按照33.90%、32.49%、33.61%的比例投资三支股票STOCK1、STOCK2、STOCK3他们的预期回报率在达到10%的情况下，投资组合的风险将达到最小。高级线性规划1.数据包络分析（DEA）2.收益管理3.投资组合模型和资产分配4.博弈论数据包络分析（DEA）DEA是线性规划用于测量有相同目标和目的的工作单位的相对效率的一种应用。例如，DEA被用于一个连锁销售店中单个的快餐店。在这种情况下，DEA的目标是找出应该进行进一步研究以及如果必要则进行纠正的低效率店面。DEA还用于测量医院、银行、法院、学校等相对效率。在这些应用中，每个机构或组织的绩效是相对于系统中所有运行单位的绩效来测量的。《银行分行的效率》描述了一个大型的知名银行如何运用DEA来发现哪个分行的运营是低效率的。银行分行的效率评估一个大型的知名银行管理层想要在分行水平上改善运营。本研究选取了位于4个主要城市的182家分支银行。DEA用于确定哪个银行分行的运营是低效率的。DEA模型比较了每个分行与所有其他分行的实际运营结果，相对于绩效最佳的分行，一个低生产力的分行生产相同的产出需要更多的资源。效率最佳的分行用１００％的DEA效率等级来标出（Ｅ＝１００），低效或低生产力分行用少于１００％的DEA效率等级来标出（Ｅ＜１００）分行的输入与输出每个分行的输入是：全日制出纳人员的数目全日制非出纳人员的数目停车位的数目ATM机的数目每位客户的广告花费每个分行的输出是：1.贷款的总量（直接贷款、间接贷款、商业贷款和股本贷款）2.存款的总量（支票存款、储蓄存款和CD存款）3.每位客户账户的平均数目4.基于季度的客户调查的客户满意度打分DEA结论最终收集了连续六个季度的数据以确定分行在这段时间内是如何运营的。结论：DEA线性规划模型的解显示，182个分行中92个是完全高效的；只有5个分行低于70%的效率水平，并且大约25%的分行的效率等级处于80%-89%之间。DEA找出了相对低效的那些分行，并对这些分行如何提高生产率效率提供了建议。关注低生产力的分行，银行能够在不显著减少规模和服务质量的前提下，找到减少需要输入的资源的方法。另外，DEA分析能使管理层更好地理解对分支银行效率贡献最大的因素。四个医院的绩效比较下面，我们通过一组4个医院的绩效来说明DEA的应用。总医院、大学医院、县医院和州医院的管理者聚在一起讨论能以自己的医院帮助彼此改进绩效的方法。一个顾问建议他们考虑采用DEA来测量每所医院相对于所有4所医院的绩效。在讨论这种评价如何进行时，确定出下面三种输入测量和四种输出测量：医院的输入与输出输入测量：全日制非医生人员的数目物资花费总数可用床日的数目输出测量：具有医疗保险服务的病人日无医疗保险服务的病人日培训的护士数目培训的实习医生数目上述的数据分别如下表一4所医院年消耗的资源（输入）输入总量总医院大学医院县医院州医院全日制非医生人员285.2162.3275.7210.4物资花费（$1000s）123.8128.7348.5154.1可用床日（1000s）106.7264.21104.1104.04表二4所医院提供的年服务（输出）输出总量总医院大学医院县医院州医院医疗保险病人数（1000s）48.1434.6236.7233.16无医疗保险病人数（1000s）43.127.1145.9856.46培训的护士253148175160培训的实习医生41272384DEA方法概述在DEA的这个应用中，为每个要评价其效率的医院都建立了一个线性规划模型。为了说明该建模过程，我们构造了一个用来确定县医院相对效率的线性规划。首先，使用一个线性规划模型，基于有相同目标的所有运营单位的输入和输出，构建一个假定的合成单位，在这个例子中是一家合成的医院。对这4所医院的每个输出测量，合成医院的输出由全部4家医院对应输出的加权平均计算而得。DEA方法概述对每个输入测量，合成医院的输入由采用相同的权重的全部4家医院对应输入的加权平均计算得到。线性规划模型中的约束条件要求合成医院的所有输出大于等于要评价的县医院的输出。如果组合单位的输入能显示出少于县医院的输入，那么就说明合成医院能利用较少的输入产出一样或更多的输出。在这种情况下，模型就说明合成医院比县医院更有效率。或者可以说，被评价的医院比合成医院的效率低。因为合成医院是基于全部4家医院的，所以当与同组内其它医院相比时，被评价医院被判定为是相对低效的。DEA方法概述其次，为了确定在计算合成医院的输出和输入时每家医院所占的权重，我们假设如下决策变量：wg=总医院输入和输出采用的权重wu=大学医院输入和输出采用的权重wc=县医院输入和输出采用的权重ws=州医院输入和输出采用的权重显然，这些权重的总和等于1，因此，第一个约束条件是wg+wu+wc+ws=1DEA方法概述一般来说，每个DEA线性规划模型都包含类似这样一个要求运营单位权重之和等于1的约束条件。正如前面所说，对每个输出测量，合成医院的输出由全部4家医院对应输出的加权平均计算而得。例如，对输出测量1，医疗保险服务的病人日数目（YLFW），合成医院的输出则为：合成医院YLFW=wg*总医院YLFW+wu*大学医院YLFW+wc*县医院YLFW+ws*州医院YLFWDEA方法概述具体数据带入，得到：（1）合成医院医疗保险=wg*48.14+wu*34.62+wc*36.72+ws*33.16类似地，我们得到其它三个输出（2）合成医院非医疗保险=wg*43.10+wu*27.11+wc*45.98+ws*56.46（3）合成医院护士=wg*253+wu*148+wc*175+ws*160（4）合成医院实习医生=wg*41+wu*27+wc*23+ws*84DEA方法概述对这4个输出中的每一个，我们需要一个限制合成医院的输出大于等于县医院输出的约束条件。因此，输出的约束条件的总形式为合成医院的输出=县医院的输出，或者（1’）wg*48.14+wu*34.62+wc*36.72+ws*33.16=36.72以相同的形式，得到其它三个约束条件如下：（2’）wg*43.10+wu*27.11+wc*45.98+ws*56.46=45.98（3’）wg*253+wu*148+wc*175+ws*160=175（4’）wg*41+wu*27+wc*23+ws*84=23DEA方法概述这4个输出的约束条件要求线性规划的解能够得到一组权重，使得合成医院的每个输出测量都大于等于县医院对应的输出测量。因此，如果能找到一个满足输出约束条件的解，合成医院每个输出将生产与县医院至少一样多的产出。DEA方法概述对于输入而言，我们需要考虑构建出合成医院输入与合成医院可用资源之间关系的约束条件。三个输入测量都需要一个约束条件，输入的约束条件的总形式为合成医院的输入=合成医院可用的资源（注意该约束与输出不同）对于每个输入测量，合成医院的输入是4家医院每个对应输入的加权平均，对于输入测量1，合成医院三种资源对应的输入为（1）合成医院非医生人员=285.2wg+162.3wu+275.7wc+210.4ws（2）合成医院物资花费=123.8wg+128.7wu+348.5wc+154.1ws（3）合成医院床日=106.72wg+64.21wu+104.1wc+104.04wsDEA方法概述为了完成输入的约束条件，我们必须写出每个约束条件右侧值得表达式。首先，要注意到右侧值是合成医院的可用资源。在DEA方法中，这些右侧值是县医院输入值得一个百分比。因此，我们必须引入下面的决策变量：E=县医院输入可用于合成医院的百分比DEA方法概述为了说明E在DEA方法中所起的重要作用，我们将出示如何写出合成医院的非医生人员数目的表达式。首先县医院的非医院人员数目为275.7，因此，275.7E是合成医院可用的非医院人员数目。若E=1，即100%，那么，合成医院的非医院人员数目就是275.7，与县医院非医院人员数目相同。然而，若E1，则合成医院就按比例拥有更多的非医生人员；而当E1时，合成医院就按比例拥有更少的非医生人员。由于E在决定合成医院可用资源时所起的作用，E被称为效率指标DEA方法概述根据关于输入的这种分析，可得如下的约束条件：（1’）合成医院非医生人员285.2wg+162.3wu+275.7wc+210.4ws=275.7E（2’）合成医院物资花费=123.8wg+128.7wu+348.5wc+154.1ws=348.5E（3’）合成医院床日=106.72wg+64.21wu+104.1wc+104.04ws=104.1E如果在E1能找到一个解，合成医院要生产相同水平的输出就不需要与县医院一样多的资源。DEA方法概述DEA模型的目标函数是最小化E的值，其等价于最小化合成医院可用的输入资源。因此，目标函数为：MinE县医院效率评价的DEA线性规划模型有5个决策变量和8个约束条件，完整的模型是：DEA方法概述MinEs.t.wg+wu+wc+ws=1wg*48.14+wu*34.62+wc*36.72+ws*33.16=36.72wg