第四章线性规划问题 在管理中的应用1线性规划 Linear Programming（LP ）数据包络分析DEA （date envelopment analysis）一种基于线性规划的用于评价同类型组织（或项目）工作绩效相 对有效性的特殊工具手段。这类组织例如学校、医院、银行的分支 机构、超市的各个营业部等，各自具有相同的投入相同的产出。衡 量这类组织之间的绩效高低，通常采用投入产出比这个指标，当各 自的投入产出均可折算成同一单位计量时，容易计算出各自的投入 产出比并按其大小进行绩效排序。但当被衡量的同类型组织有多项 投入和多项产出，且不能折算成统一单位时，就无法算出投入产出 比的数值，因而，需采用一种全新的方法进行绩效比较。这种方法 就是二十世纪七十年代末产生的数据包络分析DEA。2线性规划 Linear Programming（LP ）数据包络分析DEA （date envelopment analysis）引言1978年，著名运筹学家、美国德克萨斯大学教授 A.Charnes及W.W.Cooperh和E.Rhodes发表了一篇重要论 文：“Measuring the efficiency of decision making units” （决策单元的有效性度量），刊登在权威的“欧洲运筹学杂志”上。正式提出了运筹学的一个新领域：数据包络分析。其模型 简称 C2R 模型。3线性规划 Linear Programming（LP ）相对有效性评价问题例子例1：硕士点教育质量评价某系统工程研究所对我国金属热处理专业的26个硕士点的教育质量，进行了有效性评价。 评价采用的指标体系为： 输入：导师人数；实验设备；图书资料；学生入学情况。 输出：科研成果；论文篇数；学生毕业时的情况。 使用DEA进行评价，结果基本合理。4线性规划 Linear Programming（LP ）相对有效性评价问题例子例2：行风（行业作风）建设有效性评价本项目研究人员选定江苏省S市交通客运系统作为对象，包 括7家交通客运汽车公司。评价采用的指标基础依据为： 1、国际公交组织颁布的“十项基本考核指标” 2、国内颁布的公交运营服务的“八项考核指标”。在此基础上，根据该系统实际情况，最终选定了输入指标4 项，输出指标4项。分别是：5线性规划 Linear Programming（LP ）相对有效性评价问题例子 输入指标：1、年末职工总熟（单位：人）；2、单位成本（单位：元/千人公里）；3、燃料单位消耗（单位：升/千人公里）；4、行车责任事故率（单位：次/千人公里）。 输出指标：1、劳动生产率（单位：元/人）；2、行车准点率（%）；3、群众满意率（按问卷调查）（%）4、车辆服务合格率（包括：服务态度、服务措施 、 车辆设施等）（%）6线性规划 Linear Programming（LP ）相对有效性评价问题例子收集到所需数据后，使用DEA方法综合评价，结果为：3家公司为行风建设有效；4家公司在行风建设上存在不同程度（以量化形式给出）的缺点与不足。7线性规划 Linear Programming（LP ）相对有效性评价问题举例4所小学S1，S2，S3，S4，在校学生分别为1200，1000 ，1600，1400人，按800名标准学生的规模折算各个学校的教职工人数和建筑面积的投入，如下表：学 校 投 入S1S2S3S4教职职工人数 建筑面积积/m225 180040 150035 170020 2500请您评价：就培养800名学生而言，那些学校的投入产出效率较高，那些较低？8线性规划 Linear Programming（LP ）相对有效性评价问题举例一连锁餐饮企业拥有遍布全国的20家连锁餐厅，每家餐厅的每周运营时间、员工人数以及每周利润和所占市场份额如下表：餐厅厅 周运营时间营时间全职员职员 工每周利润润市场场份额额增长长率%餐厅厅 周运营时间营时间全职员职员 工每周利润润市场场份额额增长长率%A96.00 16.00 3800.00 25.00 K112.00 23.00 5900.00 22.00 B110.00 22.00 4600.00 32.00 L104.00 19.00 6300.00 20.00 C100.00 18.00 4400.00 35.00 M180.00 30.00 8000.00 18.00 D125.00 25.00 6500.00 30.00 N130.00 25.00 6800.00 16.00 E120.00 24.00 6000.00 28.00 O128.00 23.00 5800.00 21.00 F105.00 19.00 5800.00 33.00 P118.00 19.00 4600.00 30.00 G115.00 20.00 5000.00 27.00 Q107.00 25.00 5300.00 23.00 H109.00 18.00 5200.00 18.00 R116.00 24.00 6100.00 28.00 I98.00 17.00 4500.00 26.00 S127.00 19.00 5730.00 20.00 J130.00 28.00 6800.00 24.00 T108.00 16.00 4000.00 21.00 您对这20家餐厅的运营效率又作何判断？ 9线性规划 Linear Programming（LP ）相对有效性评价问题举例教职工人数建筑面积生产前沿线（面 ）S4S1S3S2M数据包络线10线性规划 Linear Programming（LP ）数据包络分析DEA问题线性规划数学模型在DEA中一般称被衡量绩效的组织为决策单元（decision making unitDMU）。 设：n 个决策单元（ j = 1，2，n ）每个决策单元有相同的 m 项投入（输入）（i = 1，2，m ）每个决策单元有相同的 s 项产出（输出）（r = 1，2，s ）aij 第 j 决策单元的第 i 项投入brj 第 j 决策单元的第 r 项产出评价（衡量）第 j0 决策单元是否DEA有效11线性规划 Linear Programming（LP ） 数据包络分析DEA问题线性规划数学模型决策单单元 1 2 n 投 入 项项 目1 2 ma11 a12 a1na21 a22 a2n am1 am2 amn1 2 n决策单单 元b11 b12 b1nb21 b22 b2n bs1 bs2 bsn1 2 s产产 出 项项 目 12线性规划 Linear Programming（LP ） 数据包络分析DEA问题线性规划数学模型构建模型的思路：衡量某一决策单元 j0 是否DEA有效是否处于由包络线 组成的生产前沿面上，先构造一个由 n 个决策单元组成（线性组合成）的假想决策单元。如果该假想单元的各项产出均不 低于 j0 决策单元的各项产出，它的各项投入均低于 j0 决策单元的各项的各项投入。 即有：13线性规划 Linear Programming（LP ） 数据包络分析DEA问题线性规划数学模型j brj brj0 （r = 1，2，s）j aij E aij0 （i = 1，2，m，E1）j = 1 ，j 0 （j = 1，2，n）j=1j=1j=1nnn这说明 j0 决策单元不处于生产前沿面上。14线性规划 Linear Programming（LP ） 数据包络分析DEA问题线性规划数学模型基于上述事实，可以写出如下线性规划的数学模型：min E S.t.j brj brj0 （r = 1，2，s）j aij E aij0 （i = 1，2，m）j = 1 ，j 0 （j = 1，2，n）j=1j=1j=1nnn我们称模型中的 j 为设计变量， E 为效率因子15线性规划 Linear Programming（LP ）数据包络分析DEA问题线性规划数学模型模型求解结果分析： 当求解结果有 E 1 时，则 j0 决策单元非DEA有效；否则，则 j0 决策单元DEA有效。16线性规划 Linear Programming（LP ）DEA分析应用举例例8（Page 39）振华银行的 4 个分理处的投入产出如下表。求各个分理处 的运行是否DEA有效。 产出单位：处理笔数/月分理处处投入产产出 职员职员 数营业营业 面积积（m2 ）储储蓄存取贷贷款中间业务间业务分理处处1 分理处处2 分理处处3 分理处处415 20 21 20140 130 120 1351800 1000 800 900200 350 450 4201600 1000 1300 150017线性规划 Linear Programming（LP ） DEA分析应用举例 解： 若先确定分理处1的运行是否DEA有效。建立线性规划模型min E18001 +10002 + 8003 + 9004 18002001 + 3502 + 4503 + 4204 20016001 +10002 +13003 +15004 1600 S.t. 151 + 202 + 213 + 204 15E1401 + 1302 + 1203 + 1354 140E1 + 2 + 3 + 4 = 1j 0 （ j = 1，2，3，4 ）18线性规划 Linear Programming（LP ） DEA分析应用举例 求解结果分析： 对分理处1，E =1，说明分理处1的运行DEA有效。 对分理处2，E =0.996，说明分理处2的运行非DEA 有效。 对分理处3，E =1，说明分理处3的运行DEA有效。 对分理处4，E =1，说明分理处4的运行DEA有效。19线性规划 Linear Programming（LP ）DEA分析应用举例 DEA应用中的“窗口”技术空军基地的效率评价（美国）美国空军军方曾对 7 个空军基地的效率进行了评价，使用 的方法为DEA。输入指标选定 3 项，输出指标选定 4 项（内容 未报道）。评价的时间范围为 1992 年 10 月 1 日至1993 年12 月 31 日。尽管具体内容及结果未予公布，但有一项技术“窗口 技术”却很有参考价值，介绍如下：20线性规划 Linear Programming（LP ）DEA分析应用举例 DEA应用中的“窗口”技术空军基地的效率评价（美国）一般来说，在对决策单元集进行DEA 评价时，对单元的个 数 n ，输入指标个数 m ，以及输出指标个数 s 应有一定的要求。经验表明它们大体上应满足或接近n 2ms在本例中，空军基地有 7 个，分别记为 A 、B 、C 、D 、E 、F 、G 。即 n = 7；而输入指标有 3 项，即 m = 3；输 出指标有 4 项，即 s = 4 。显然，决策单元数过少了。21线性规划