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

数据、模型与决策

线性规划与非线性规划线性规划问题线性规划模型线性规划的求解非线性规划例

某家电公司准备将一种新型电视机在三家商场进行销售，每一个商场的批发价和推销费及产品的利润如表所示。由于该电视机的性能良好，各商场都纷纷争购，但公司每月的生产能力有限，只能生产1000台，故公司规定:甲商场至少经销100台，至多200台；乙至少经销300台，丙商场至少经销200台。公司计划在一个月内的广告预算费为8000元，推销人员最高可用工时数为1500，同时，公司只根据经销数进行生产，试问：公司下个月采取的市场对策？一个例子S.t.建立线性模型S.t.线性规划模型线性规划求解方法图解法√计算机解法—Excel,Lindo√单纯形方法（需要矩阵知识）×线性规划求解—图解法例3生产A、B两种产品，需要某种原料的数量和使用某种设备的时间如下：

单位产品的消耗资源总量

AB原料6432设备10230单位利润(万元/吨)5

2

线性规划求解—图解法24681012141624681012141610x+2y=306x+4y=32xyP(2,5)0Q(5,2)5x+2y=0线性规划的对偶问题S.t.关于影子价格的讨论。回报率平均数0.140.110.05回报率标准差0.20.150.08相关系数表

stock1stock2stock3stock11

stock20.61

stock3-0.4-0.71协方差表

stock1stock2stock3stock10.04

stock20.0180.0225

stock30.0064-0.70.0064三支股票的数据规划建模设三支股票的投资比例分别为a、b、c，那么得到下面关系:Excel求解投资比例分别为0.3390、0.3249、0.3361，此时风险达到最小值0.0084三支股票的数据答案：优利公司按照33.90%、32.49%、33.61%的比例投资三支股票STOCK1、STOCK2、STOCK3他们的预期回报率在达到10%的情况下，投资组合的风险将达到最小。高级线性规划数据包络分析（DEA）收益管理投资组合模型和资产分配博弈论数据包络分析（DEA）DEA是线性规划用于测量有相同目标和目的的工作单位的相对效率的一种应用。例如，DEA被用于一个连锁销售店中单个的快餐店。在这种情况下，DEA的目标是找出应该进行进一步研究以及如果必要则进行纠正的低效率店面。DEA还用于测量医院、银行、法院、学校等相对效率。在这些应用中，每个机构或组织的绩效是相对于系统中所有运行单位的绩效来测量的。《银行分行的效率》描述了一个大型的知名银行如何运用DEA来发现哪个分行的运营是低效率的。分行的输入与输出每个分行的输入是：全日制出纳人员的数目全日制非出纳人员的数目停车位的数目ATM机的数目每位客户的广告花费每个分行的输出是：1.贷款的总量（直接贷款、间接贷款、商业贷款和股本贷款）2.存款的总量（支票存款、储蓄存款和CD存款）3.每位客户账户的平均数目4.基于季度的客户调查的客户满意度打分DEA结论最终收集了连续六个季度的数据以确定分行在这段时间内是如何运营的。结论：DEA线性规划模型的解显示，182个分行中92个是完全高效的；只有5个分行低于70%的效率水平，并且大约25%的分行的效率等级处于80%-89%之间。DEA找出了相对低效的那些分行，并对这些分行如何提高生产率效率提供了建议。关注低生产力的分行，银行能够在不显著减少规模和服务质量的前提下，找到减少需要输入的资源的方法。另外，DEA分析能使管理层更好地理解对分支银行效率贡献最大的因素。医院的输入与输出输入测量：全日制非医生人员的数目物资花费总数可用床日的数目输出测量：具有医疗保险服务的病人日无医疗保险服务的病人日培训的护士数目培训的实习医生数目上述的数据分别如下表一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方法概述对每个输入测量，合成医院的输入由采用相同的权重的全部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方法概述对这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，与县医院非医院人员数目相同。然而，若E>1，则合成医院就按比例拥有更多的非医生人员；而当E<1时，合成医院就按比例拥有更少的非医生人员。由于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如果在E<1能找到一个解，合成医院要生产相同水平的输出就不需要与县医院一样多的资源。DEA方法概述DEA模型的目标函数是最小化E的值，其等价于最小化合成医院可用的输入资源。因此，目标函数为：MinE县医院效率评价的DEA线性规划模型有5个决策变量和8个约束条件，完整的模型是：DEA方法概述MinEs.t.wg+wu+wc+ws=1wg*48.14+wu*34.62+wc*36.72+ws*33.16>=36.72wg*43.10+wu*27.11+wc*45.98+ws*56.46>=45.98wg*253+wu*148+wc*175+ws*160>=175wg*41+wu*27+wc*23+ws*84>=23-275.7E+285.2wg+162.3wu+275.7wc+210.4ws<=0-348.5E+123.8wg+128.7wu+348.5wc+154.1ws<=0-104.1E+106.72wg+64.21wu+104.1wc+104.04ws<=0wg,wu,wc,ws,E>=0DEA方法概述应用Excel规划求解得到如下结果：E0.905238wg0.212266wu0.260447wc0ws0.527287

st11st236.72st345.98st4176.6154st560.02707st6-35.8241st7-174.422st8-6.20E-07DEA方法概述我们首先注意到目标函数值显示县医院的效率得分为0.905，这个分数告诉我们合成医院通过使用不超过县医院需要输入资源的90.5%，可以达到至少县医院能达到的每个输出的水平。因此，合成医院是更有效的，并且DEA分析指出县医院是相对低效的。DEA方法概述从上面的解中，我们还看出合成医院是由总医院（wg=0.212）、大学医院（wu=0.26）和州医院（ws=0.527）加权平均形成的。合成医院的每一个输入和输出都是由这3家医院的输入和输出进行相同加权平均得来的。DEA方法概述松弛/剩余列给出了县医院效率与合成医院相比的一些其他信息。具体来说，合成医院的每个输出至少与县医院一样多（约束条件2～5在最终解计算结果都大于0）。相比县医院，它多出1.6个培训护士（在约束条件4中，176.6-175=1.6）和37个培训的实习生（约束条件5），约束条件8的松弛为0，合成医院使用的床日数约为县医院使用的90.5%。约束条件6和7合成医院使用的非医生人员和物资花费资源少于县医院使用的90.5%。DEA方法概述很明显，合成医院比县医院更有效率，由此，我们得出结论，县医院与同组其它医院相比是相对低效率的。鉴于DEA分析的结果，医院管理者应该检查运营操作以确定应该如何更有效地利用县医院的资源。DEA方法总结为了使用数据包络分析方法来检测县医院的相对效率，我们基于问题中4家医院的输入和输出，利用一个线性规划模型构建了一所假定的合成医院。使用DEA求解其它类型问题的方法是相似的。对每个我们需要测量其效率的运营单位，我们都必须建立并求解一个与测量县医院相对效率时求解的线性问题相似的线性规划模型。怎样求其它三家医院的效率？DEA方法的灵敏度分析灵敏度分析（sensitivityanalysis）能够为管理层决策提供非常有用的信息，能够帮助决策者做出正确的决策。我们知道，周围环境的变化会使系数发生变化，系数的变化很可能会影响已求得的最优解。因此，开明的管理者为了让管理决策能够更好地适应现实环境，还要继续研究最优解对数据变化的反应程度，以适应各种偶然的变化，这是灵敏度分析所要研究的内容之一，灵敏度分析研究的另一类问题是探讨在原线性规划模型的基础上增加一个变量或者一个约束条件对最优解的影响。总之，灵敏度分析通常可以解决参数变化对模型的影响。DEA方法的灵敏度分析下面先讨论单个目标函数系数变化的灵敏度分析。在规划求解结果对话窗中，从右边的“报告”列表框中选择“敏感性报告”选项，单击“确定”，这时就生成新的工作表“敏感性报告”如下：（提示：含有整数约束条件的模型，不能生成敏感性报告）DEA方法的灵敏度分析MicrosoftExcel11.0敏感性报告工作表[4家医院求解.xls]Sheet1报告的建立:2016/10/922:59:52可变单元格

终递减单元格名字值梯度$C$2E0.9052378920$C$3wg0.21226620$C$4wu0.2604471380$C$5wc00.094762078$C$6ws0.5272866610DEA方法的灵敏度分析约束

终拉格朗日单元格名字值乘数$C$8st11-0.238885969$C$9st236.72000050.013964551$C$10st345.980000050.013730874$C$11st4176.6153910$C$12st560.02706650$C$13st6-35.824082280$C$14st7-174.42242840$C$15st8-6.18443E-07-0.009606148DEA方法的灵敏度分析

目标式

单元格名字值$C$2E0.905

变量

下限目标式上限目标式单元格名字值极限结果