MBA学位课程-运筹学2(1)

1、2.6 2.6 运输问题及其解法运输问题及其解法 引例：某公司经销甲产品，它下设三个加工厂，每日的引例：某公司经销甲产品，它下设三个加工厂，每日的产量分别为：产量分别为：A1-40吨，吨，A2-40吨，吨，A3-90吨。该公司把这些吨。该公司把这些产品分别运往四个销售点，各销售点每日销量为：产品分别运往四个销售点，各销售点每日销量为：B1-30吨吨，B2-40吨，吨，B3-60吨，吨，B4-20吨吨, B5-20吨。已知从各工厂到各吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总

2、运费为最少产品，在满足各销售点需求量的前提下，使总运费为最少 销地 产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）30406020201解：这是一个产销平衡的运输问题，解：这是一个产销平衡的运输问题， 设设Xij表示从表示从Ai调运产调运产品到品到Bj的数量（吨），其数学模型是：的数量（吨），其数学模型是： 0X20XXX20XXX60XXX40XXX30XXX90XXXXX40XXXXX40XXXXX. t . sXCzminij352515342414332313322212222111353433323125242322211

3、51413121131i51jijij2一、产销平衡的运输问题及其解法一、产销平衡的运输问题及其解法1.产销平衡的运输问题的数学模型及其特点产销平衡的运输问题的数学模型及其特点 ：minjijijXCZ11min )n,.,1j,m,.,1i (0X)m,.,2, 1i (aX)n,.,2, 1j(bXijn1jiijm1ijij特点：（1）其系数矩阵的结构疏松，且每一列向量Pij=(0,1,1,0)T=ei+em+j 可以证明，r(A)=m+n1。即有m+n1个独立方程。于是，该LP问题有且仅有m+n1个基变量。 3（2） （产销平衡条件） minjjiba11（3）因为 , 故必有可行解和

4、最优解。 minjijijXCMinZ110 由于上述特点，若按单纯形法求解必须增加人工变量由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用特殊解法，致使计算量大大增加，故用特殊解法表上作业法。表上作业法。2.表上作业法表上作业法 表上作业法实质上还是单纯形法，但具体计算和术语上表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其计算步骤和方法，我们通过对引例的求解过有所不同。其计算步骤和方法，我们通过对引例的求解过程说明之。程说明之。（1）用最小元素法确定初始方案（即初始基可行解）用最小元素法确定初始方案（即初始基可行解） 切记在产销平衡表上必须且只能填写切记

5、在产销平衡表上必须且只能填写m+n1个数字格个数字格 4例18（P37）设某产品从产地A1，A2，A3运往销地B1，B2，B3，B4，B5，运量和单位运价如下表所示，问如何调运才能使总的运费最少？ 销地 运价产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020解：用最小元素法或伏格尔法求得其初始调运方案如下：解：用最小元素法或伏格尔法求得其初始调运方案如下：5 销地 运价产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）304060202030406020200

6、0接接下来我们就要判别这个调运方案是否是最优调运方案？下来我们就要判别这个调运方案是否是最优调运方案？ 判别的方法同线性规划一样，首先求出空格的检验数，判别的方法同线性规划一样，首先求出空格的检验数，由于是最小化问题，所以当所有空格的检验数均小于由于是最小化问题，所以当所有空格的检验数均小于0时得时得到的解为最优解。到的解为最优解。 求运输问题的空格的检验数的方法有闭回路法和位势求运输问题的空格的检验数的方法有闭回路法和位势法。法。6（2）用闭回路法或位势法求空格的检验数）用闭回路法或位势法求空格的检验数1) 用闭回路法求检验数：用闭回路法求检验数： 首先，每一个空格有且仅有一个闭回路，而圈格

7、无闭回首先，每一个空格有且仅有一个闭回路，而圈格无闭回路。路。 闭回路闭回路是以空格为起点，沿同一行或同一列前进，遇上是以空格为起点，沿同一行或同一列前进，遇上圈格可转圈格可转90度继续前进，按此方法进行下去，直到回到始度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。点的一个封闭折线。 以始点为第以始点为第0个点，依次给闭回路上的每一个顶点编号个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。 其次，其次，每一个空格的检验数每一个空格的检验数=奇顶点运费之和奇顶点运费之和 偶顶点偶顶点运费之和。运费之和。

8、7 2)用位势法求出空格的检验数并进行最优解的判别用位势法求出空格的检验数并进行最优解的判别设设u1,u2,um; v1,v2,vn是对应运输问题是对应运输问题m+n个约束条件的个约束条件的对偶变量，对偶变量，B为含有人工变量的初始可行基，由为含有人工变量的初始可行基，由LP问题的问题的对偶理论知：对偶理论知：CBB-1=(u1,u2,um; v1,v2,vn) 而每个决策变量而每个决策变量Xij相应的系数向量相应的系数向量Pij=ei+em+j，所以所以CBB-1Pij=ui+vj， 于是，检验数于是，检验数ij=CBB-1PijCij =(ui+vj)Cij又各基变量的检验数为又各基变量的

9、检验数为0，故对每个基变量所在的圈格的检，故对每个基变量所在的圈格的检验数有验数有 即有方程组：即有方程组：isjsjsisjijijijiCvuCvuCvu:22221111共m+n个未知数 s=m+n1个方程 Cvuijji)(08 显然上述方程有解，且由于含有一个自由变量，因此，令 任 一 未 知 数 为 0 ， 就 可 求 出 上 述 方 程 组 的 解(ui1,ui2,uim,vj1,vj2,vjn)称为位势解。如用位势法求引例初始基可行解的检验数： 销地 运价产地B1B2B3B4B5vjA17108646A259712612A336581110ui-7-3-50-2-8-7-704

10、12-33040602020009 第一步：将运价表中增加vj和ui列。 第二步：利用圈格分别算出ui和vj，即令u1=0，然后按ui+vj=Cij (i,jJB)，相继确定ui，vj的值。 第三步：按ij= (ui+vj)Cij (i,jJN)算出表中各空格（即非基变量）的检验数： 由于运输问题的目标函数是求最小化，故判别最优解故判别最优解的准则是所有的非基变量的检验数：的准则是所有的非基变量的检验数：ij=CBB-1PijCij0 因为25 =+4， 32 =+1， 34 =+2均为正数，所以目前尚未得到最优解（其实只要有一个正检验数，所对应的方案就不是最优方案），尚须改进。 方案的调整（

11、即换基迭代）是在闭回路上进行方案的调整（即换基迭代）是在闭回路上进行10 3）在调运平衡表上用闭回路法进行调整，得到新的基可）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案）行解（新的调运方案） i) 确定进基变量：自上而下，自左向右第一个正检验数相应的非基变量（空格）为进基变量。 ii) 作闭回路：以进基变量空格为出发点，用水平或垂直线向前划，当碰到某一恰当数格转90后，继续前进，直至回到起始空格止。 iii) 确定调整量=min奇顶点的调运量（即闭回路上奇顶点运量的最小值为调整量） iv) 在闭回路上进行调整：对闭回路上每个奇顶点的调运对闭回路上每个奇顶点的调运量量 ，对

12、闭回路上每个偶顶点（含起始格）的调运量对闭回路上每个偶顶点（含起始格）的调运量+ 。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解)11 销地 运价产地B1B2B3B4B5产量（万吨）A171086 +04 -040A259712-06 +040A336581190销量（万吨）304060202020 B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020200040306020306040020200124）表上作业法须注意的问题：）表上作业法须注意的问题

13、： i) 在最终调运表中，若有某个空格（非基变量）的检验数为0时，则表明该运输问题有多重调运方案； ii) 在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列（绝对不能同时把行、列划去，否则就不满足圈格=m+n1个的要求，即基变量的个数永远要保持为m+n1个）； iii) 在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n1个的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。13二、产销不平衡的运输问题及其求解方法1.数学模型：数学模型： minjjiijXCZ11min),.,2 ,

14、 1,.,2 , 1(0),.,2 , 1(),.,2 , 1(11njmiXnjbXmiaXijmijijnjiijminjjiijXC11min),.,2 , 1,.,2 , 1(0),.,2 , 1(),.,2 , 1(11njmiXnjbXmiaXijmijijnjiijnjjmiiba11产大于销njjmiiba11销大于产14然后再用产销平衡的运输问题的解法进行解之。 2.解法思路：解法思路： 将不平衡运输问题转化为平衡运输问题。即当 时，考虑在平衡表中增加一虚拟列，表示增加一个销货点(j=n+1)如仓库，其销货量为 ，且各运价Cin+1=0；当 时，考虑在平衡表中增加一虚拟行，表

15、示增加一个新产地，且各运价Cm+1j=0。 njjmiiba11njjmiiba11njjmiiba1115例题19（P45） 三个电视机厂供应四个地区某种型号的电视机，其运价表如下，试求总运费最少的调运方案？例18 下表是一个运输问题的单位运价表。 B1B2B3B4产量（万吨）A11035650A221131270A3781870销量（万吨）20304060 比较总产量和总销量可知，这是一个非平衡运输问题（属于产大于销的情况），为化为平衡运输问题，需虚设一个销点B5，其运价为0，其销量为40。B50004016 销地厂家B1B2B3B4产量（万台）A16312610A2439 12A3910

16、131010最低需求61405最高需求10146不不限限(12) 销地厂家B1B1B2B3B4B4产量（万台）A1663126610A24439 MM12A3991013101010A4M0M0M1010销量6414657化为产销平衡的运输问题有：17三、转运问题及其解法三、转运问题及其解法1.所谓转运问题是在以下背景产生的： (1)每个工厂生产的产品不直接运到销地，可以几个产地集中一起运。 (2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。 (3)除产、销地之外，还可以有几个中间转运站，在产地之间，销地之间或产销地之间转运。 凡类似上述情况下的调运物资并使总运费最小的问题统称为

17、转运问题。2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。183.求解“转运问题”的方法步骤： (1)建立扩大的产销平衡运输问题单位运价表。其中 1)对两地不能直接运输的单位运价定为M（很大的正数） 3)对产量列的各数据可按下式计算并填入： Ai的产量=ai+,Tj产量=，Bj的产量= 4)对销量行的各数据可按下式计算并填入： Aj的产量=,Tj销量=，Bj的销量=+bj (2)用表上作业法进行求解m1in1jji,maxba2)对所有中转站Tj的产量和销量定为相等，设定为19例26（P61）已知甲、乙两

18、处分别有100吨和85吨同种物质外运，A、B、C三处各需物质55，60，70（吨），物质可以直接运到目的地，也可以经某些中转点转运，已知各处之间的距离如下表所示，试确定一个最优的调运方案。 从 到甲乙甲乙010120从 到ABC甲乙101514121218从 到ABCABC0108140121140从 到甲乙ABC产量甲乙ABC010MMM120MMM1015010814121401212181140285270185185185销量185185240245255再用表上作业法进行求解。202.7 2.7 线性目标规划及其解法线性目标规划及其解法 前面的线性规划问题都是处理单个目标的情况，但是

19、在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。1、目标规划模型的建立 21引例： 对于生产计划问题： 甲 乙 资源限额 材料 2 3 24 工时 3 2 26 单位利润 4 3 现在工厂领导要考虑市场等一系列其他因素，提出如下目标：（1）根据市场信息，甲

20、产品的销量有下降的趋势，而乙产品的销量有上升的趋势，故考虑乙产品的产量应大于甲产品的产量。（2）尽可能充分利用工时，不希望加班。（3）应尽可能达到并超过计划利润30元。现在的问题是：在原材料不能超计划使用的前提下，如何安排生产才能使上述目标依次实现？22解：（1）决策变量：仍设每天生产甲、乙两种产品各为x1和x2 偏差变量：对于每一目标，我们引进正、负偏差变量。 如对于目标1，设d1-表示乙产品的产量低于甲产品产量的数，d1+表示乙产品的产量高于甲产品产量的数。称它们分别为产量比较的负偏差变量和正偏差变量。则对于目标1，可将它表示为等式约束的形式 -x1+x2+ d1- d1+ =0 (目标约

21、束) 同样设d2-和d2+分别表示安排生产时，低于可利用工时和高于可利用工时，即加班工时的偏差变量，则对目标2，有 -3x1+2x2+ d2-d2+ =26 对于目标3，设d3-和d3+分别表示安排生产时，低于计划利润30元和高于计划利润30元的偏差变量，有： 23 4x1+3x2+ d3-d3+ =30 （2）约束条件：有资源约束和目标约束 资源约束：2x1+3x224 目标约束：为上述各目标中得出的约束 （3）目标函数：三个目标依次为： minZ1=d1- ，minZ2=d2+d2- ，minZ3=d3- 因而该问题的数学模型可表述如下： minZ1=d1- ，minZ2=d2+d2-，m

22、inZ3=d3- 2x1+3x224 st -x1+x2+ d1- d1+ =0 -3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 24 例20（提级加新问题） 某公司的员工工资有四级，根据公司的业务发展情况，准备招收部分新员工，并将部分员工的工资提升一级。该公司的员工工资及提级前后的编制表如下，其中提级后编制是计划编制，允许有变化，其中1级员工中有8%要退休。公司领导的目标如下：（1）提级后在职员工的工资总额不超过550千元；（2）各级员工不要超过定编人数；（3）为调动积极性，各级员工的升级面不少于现有人数的18%；（4）总提级面不大于20%，但尽可能多提；（

23、5）4级不足编制人数可录用新工人。 25问：应如何拟定一具满意的方案，才能接近上述目标？ 级别1234工资（千元）8643现有员工数10204030编制员工数10225230解：（1）决策变量：设x1,x2,x3,x4分别表示提升到1，2，3级和新录用的员工数。 偏差变量：为各目标的正、负偏差变量。 （2）约束条件：1） 提级后在职员工的工资总额不超过550千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550 26 2）各级员工不要超过定编人数1级有： 10-10 8%+x1+d2-d2+=10 2级有： 20-x1+

24、x2+d3-d3+=22 3级有： 40-x2+ x3+d4-d4+=52 4级有： 30-x3+ x4+d5-d5+=303）各级员工的升级面不少于现有人数的18%对2级有： x1+d6-d6+=22 18%对3级有： x2+d7-d7+=40 18% 对4级有： x3+d8-d8+=30 18% 4）总提级面人数不大于20%，但尽可能多提 x1+ x2+ x3+d9-d9+=100 20% 27（3）目标函数： minZ1=d1+minZ2=d2+d3+ d4+ d5+minZ3=d6-+ d7-+ d8-minZ4=d9+ d9-目标规划的一般模型见书本P48 二、目标规划的解法二、目标

25、规划的解法 由于目标规划有多个目标，各个目标又有相对不同的重要性，求解时是首先满足重要性权数大的目标，再满足重要性权数次大的目标，所以并不能保证所有的目标都能达到，所求的解也不一定是最优解，而只能求出满意解。 28求解目标规划有图解法和单纯形法，在这里我们主要介绍单纯形法。 求解目标规划的单纯形法与线性规划的单纯形法原理基本一致，只是此时检验数行不再是一行，而是变化为一个检验数矩阵。 例1 例20 用单纯形法求解如下线性目标规划模型 minZ1=d1-，minZ2=d2+d2-，minZ3=d3- 2x1+3x224 加入松驰变量化为标准形 2x1+3x2+ x3=24 st -x1+x2+

26、d1- d1+ =0 -3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 解：取x3，d1-，d2-，d3-为基变量，建立初始单纯形表 29-1-2-1123-13402630Z1Z2Z3000-100-100-10000010010010010003 1 232-1342402630 x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步骤完全与线性规划的单纯形法一样。满意解的判定：检验数矩阵的每一列从上至下第一个非零元为负数，则解为满意解。迭代的最优表如下： 30-2-1-1-11-1020Z1Z2Z3100000-106/5-2

27、/5-13/5-10000010-6/52/51-3/57/51/5-11/50100000118/524/5224/5d3+x2d2-x1d3+d2+d1+d3-d2-d1-x3x2x1bXB因而满意解为：x1=24/5，x2=24/5，d2-=2，d3+=18/5 其中第一、三目标已达到最优，第二个目标未达最优。目标利润 Z=4x1+3x2=168/5312.8 2.8 评价相对有效性的评价相对有效性的DEA模型模型 DEA模型（也称数据包络分析）最早由美国运筹学家 A.Charnes等人于1978年提出，在中国最早由中国人民大学的魏权龄教授于1985向国内介绍。 DEA是对其决策单元（同

28、类型的企业或部门）的投入规模、技术有效性作出评价，即对各同类型的企业投入一定数量的资金、劳动力等资源后，其产出的效益（经济效益和社会效益）作一个相对有效性评价。 例如：区域可持续发展的DEA评价、企业营销效果的DEA评价、企业竞争能力的DEA评价等。为了说明DEA模型的建模思路，我们看下面的例子：32 例1： 某公司有甲、乙、丙三个企业，为评价这几个企业的生产效率，收集到反映其投入（固定资产年净值x1、流动资金x2、职工人数x3）和产出（总产值y1、利税总额y2）的有关数据如下表 企业指标甲乙丙x1（万元）41527x2 （万元）1545x3 （万元）825y1 （万元）602224y2 （万

29、元）1268 由于投入指标和产出指标都不止一个，故通常采用加权的办法来综合投入指标值和产出指标值。 33对于第一个企业，产出综合值为对于第一个企业，产出综合值为60u1+12u2,投入综合值投入综合值4v1+15v2+8v3，其中其中u1 u2 v1 v2 v3分别为产出与投入的权重系分别为产出与投入的权重系数。数。我们定义第一个企业的生产效率为：我们定义第一个企业的生产效率为：总产出与总投入的比总产出与总投入的比即即vvvuuh32121181541260类似，可知第二、第三个企业的生产效率分别为：类似，可知第二、第三个企业的生产效率分别为：vvvuuh3212122415622vvvuuh

30、452782432121334我们限定所有的我们限定所有的hj值不超过值不超过1，即，即 ，这意味着，这意味着，若第若第k个企业个企业hk=1，则该企业相对于其他企业来说生产率最则该企业相对于其他企业来说生产率最高，或者说这一生产系统是相对有效的，若高，或者说这一生产系统是相对有效的，若hk1，那么该那么该企业相对于其他企业来说，生产效率还有待于提高，或者企业相对于其他企业来说，生产效率还有待于提高，或者说这一生产系统还不是有效的。说这一生产系统还不是有效的。1maxhj即即vvvuuh32121181541260max12415622321212vvvuuh14527824321213vvv

31、uuh因此，建立第一个企业的生产效率最高的优化模型如下：因此，建立第一个企业的生产效率最高的优化模型如下：这是一个分式规划，需要这是一个分式规划，需要将它化为线性规划才能求将它化为线性规划才能求解。解。35设设vvvt3218154vtwutiiii,则此则此分式规划可化为如下的分式规划可化为如下的线性规划线性规划1w8w15w4w4w5w27824w2w4w15622w8w15w41260. t . s1260hmax321321213212132121211其其对偶对偶问题为问题为128612602422608428155415427154. t . sVmin32132132132132

32、1Dvvvuuh32121181541260max12415622321212vvvuuh14527824321213vvvuuh1v8v15v4u12u60h32121136 设vi为第i个指标xi的权重，ur为第r个产出yr指标的权重，则第j个企业投入的综合值为 ，产出的综合值为 其生产效率定义为: 于是问题实际上是确定一组最佳的权变量v1,v2,v3和u1,u2，使第j个企业的效率值hj最大。这个最大的效率评价值是该企业相对于其他企业来说不可能更高的相对效率评价值。 xvij31iiyurj21rr31iiji21rrjrjxvyuh 我们限定所有的hj值(j=1,2,3)不超过1，即m

33、axhj1。这意味着，若第k个企业hk=1，则该企业相对于其他企业来说生产率最高，或者说这一系统是相对而言有效的；若hk1，那么该企业相对于其他企业来说，生产率还有待于提高，或者说这一生产系统还不是有效的。 37 根据上述分析，可以建立确定任何一个企业（如第3 个企业即丙企业）的相对生产率最优化模型如下： 3 , 2 , 1i , 0, 2 , 1r , 03 , 2 , 1j , 1. t . sHmaxvuhhirj31、评价决策单元技术和规模综合效率的、评价决策单元技术和规模综合效率的C2R模型模型 设有n个同类型的企业（也称决策单元），对于每个企业都有m种类型的“输入”（表示该单元对“

34、资源”的消耗）以及p种类型的“输出”（表示该单元在消耗了“资源”之后的产出）。 这n个企业及其输入-输出关系如下： 38:y1ny2n:ypny1jy2j:ypj:y12y22:yp2y11y21:yp1u1u2:up12:p输出x1nx2n:xmnx1jx2j:xmj:x12x22:xm2x11x21:xm1v1v2:vm12:m输入nj21 部门指标 权数每个决策单元的效率评价指数为： m1iijip1rrjrjxvyuhj=1,2,n39而第j0个决策单元的相对效率优化评价模型为： 上述模型中xij,yrj为已知数（可由历史资料或预测数据得到），vi,ur为变量。模型的含义是以权系数vi

35、,ur为变量，以所有决策单元的效率指标hj为约束，以第j0个决策单元的效率指数为目标。即评价第j0个决策单元的生产效率是否有效，是相对于其他所有决策单元而言的。 m1i0ijip1r0rjr0jxvyuhmax s.t. vi,ur0, i=1,2,m; r=1,2,p n,.,2 , 1j , 1m1iijip1rrjrxvyu（1）40 这是一个分式规划模型，我们必须将它化为线性规划模型才能求解。为此，令 m1i0ijixv1tvwiiturrt则模型（1）转化为： p,.,2 , 1r;m,.2 , 1i, 0,1n,.,2 , 1j, 0. t . swxwxwyyhmaxir0ijm

36、1iip1rm1iijirjrp1r0rjr0 j（2）41其对偶问题为： 无约束,0p,.,2, 1r ,m,.,2, 1i ,. t . sminjn1j0rrjjn1j0iijjDyyxxv（3）写成向量形式有：, 0, 0, 0jn1j0jj0jn1jjssysyxsxs.t.无约束（4） min42设问题（4）的最优解为*，s*-,s*+,*，则有如下结论： （1）若*=1，则DMUj0为弱DEA有效（总体）。（2）若*=1，且s*-=0,s*+=0，则DMUj0为DEA有效（总体）（3）令 0=*x0- s*-, 0=y0- s*+,则为在有效前沿面上的投影，相对于原来的n个DMU

37、是有效（总体）的。 x y x y （4）若存在j*(j=1,2,m),使 =1成立，则DMUj0为规模效益不变；若不存在j*(j=1,2,m)，使 =1成立，则 1 DMUj0为规模效益递减。 n1j*jn1j*jn1j*jn1j*jn1j*j43评价第j0决策单元DMU纯技术效率C2GS2模型为： min 0, 0ssysyxsxn1j0jj0jn1jj1n1j*j0js.t.j=1,2,n无约束（5） 该模型计算出的DMU效率是纯技术效率，反映DMU的纯技术效率状况，称为纯技术效率。设问题（2）的最优解为*，s*-,s*+,*，则有如下对结论： 44（1）若*=1，则DMUj0为弱DEA

38、有效（纯技术）。（2）若*=1，且s*-=0,s*+=0，则DMUj0为DEA有效（纯技术）。评价第j0决策单元DMU纯规模效率模型为： *s（6） 根据DEA的理论，总体效率*、纯技术效率*、纯规模效率s*三个参数之间存在（6）式所述的关系，由（6）可直接计算DMU的纯规模效率。 45P63例例28 以以1997年全部独立核算企业为对象年全部独立核算企业为对象,对安徽、江西对安徽、江西、湖南和湖北四省进行生产水平的比较。投入要素取固定、湖南和湖北四省进行生产水平的比较。投入要素取固定资产净值年平均余额资产净值年平均余额(亿元亿元),流动资金年平均余额及从业人流动资金年平均余额及从业人员员(万

39、人万人),产出要素取总产值产出要素取总产值(亿元亿元)和利税总额和利税总额(亿元亿元).安徽安徽江西江西湖南湖南湖北湖北固定资产固定资产932.66583.08936.841306.56流动资金流动资金980.45581.64849.311444.30从业人员从业人员401.8294.2443.20461.00利税总额利税总额179.2949.76144.20181.41总产值总产值2196.09930.221659.042662.21全全要素相对生产率要素相对生产率(即即DEA评价值评价值)1.0000.71400.92851.000排序排序1321461. 建立评价湖南省的建立评价湖南省的

40、DEA模型如下模型如下 无约束无约束, 004.1659s21.266204.165922.93009.219620.144s410.18120.144760.4929.17920.443s000.46120.44320.24980.40131.849s40.144431.84964.58145.98084.936s56.130684.93608.58366.932. t . sVminj2432114321343212432114321D求解求解结果为结果为:24.107s, 0s,17.88s, 0s,71.119s, 0,8043. 0,9285. 0213214321 调整方案为调整方

41、案为:输入调整前输入调整前输入调整后输入调整后输出调整前输出调整前输出调整后输出调整后936.84936.84*0.9285-119.71=750.15144.20144.20849.31849.31*0.9285=788.581659.041659.04+107.24=1766.28443.20443.2*0.9285-88.17=323.3447第二章 整数线性规划问题及其解法 在上一章讨论的LP问题中,对决策变量只限于不能取负值的连续型数值,即可以是正分数或正小数。然而在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(Integer Pro

42、gramming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。根据变量取整数的情况根据变量取整数的情况,将整数规划分为将整数规划分为：（1）纯整数规划，所有变量都取整数）纯整数规划，所有变量都取整数.（2）混合整数规划，一部分变量取整数）混合整数规划，一部分变量取整数,一部分变量取实数一部分变量取实数（3）0-1整数规划整数规划 ,所有变量均取所有变量均取0或或1求解整数规划常用的算法有分枝定界法、割平面法求解整数规划常用的算法有分枝定界法、割平面法,求解求解0-1的还有隐枚举法、匈牙利法。的还有隐枚举

43、法、匈牙利法。48一、整数线性规划模型的建立一、整数线性规划模型的建立例题例题2 P72 某单位有某单位有5个拟选择的投资项目，其所需投资个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；之间必须选择一项且仅需选择一项；B和和D之间需选之间需选择也仅需选择一项；又由于择也仅需选择一项；又由于C和和D两项目密切相关，两项目密切相关，C的实的实施必须以施必须以D的实施为前提条件，该单位共筹集资金的实施为前提条件，该单位共筹集资金15万元万元，问应该选择哪些项目投资，使期望收益最大？，问

44、应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E5949解：决策变量：设)5 , 4 , 3 , 2 , 1j (j1j0 xj被选中表示项目不被选中表示项目目标函数：期望收益最大xxxxx54321967810zmax约束条件：投资额限制条件 6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件： x3 x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：10111554246967810zmaxxxxxxxxxxxxxxxxx

45、xxj43423215432154321或50由此，ILP问题数学模型的一般形式为：求一组变量X1,X2,Xn，使 n1jjjXCMaxZ数且皆为整数或部分为整, 0Xj)m, 2 , 1i (bXat . sn1jiijij此例还表明，利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源对可供选择的n个项目进行投资的数学模型为：求一组决策变量X1,X2,Xn，使 njjjXCZ1max), 2 , 1(10), 2 , 1(1njXmibXajnjijij或（3.1）（3.2）（3.3）511.对可供项目的选择 （1）如果在可供选

46、择的前k(kn)个项目中，必须且只能选择一项，则在(3.2)中加入新的约束条件：kjjX11（2）如果可供选择的k(kn)个项目是相互排斥的，则在(3.2)中加入新的约束条件：kjjX11同时它还表示在第k个项目中至多只能选择一项投资。 （3）如果在可供选择的k(kn)个项目中，至少应选择一项投资，则在(3.2)中加入新的约束条件：kjjX1152（4）如果项目j的投资必须以项目i的投资为前提，则可在(3.2)中加入新的约束条件： XjXi （5）如果项目i与项目j要么同时被选中，要么同时不被选中，则在(3.2)中加入新的约束条件：Xj=Xi (ij) 2.对可供资源的选择 （1）如果对第r种

47、资源br与第t种资源bt的投资是相互排斥的，即只允许对资源br与bt中的一种进行投资，则可将(3.2)的第r个和第t个约束条件改写为： 53 njrjrjyMbXa1njtjtjMybXa1)1 ( 其中y为新引进的0-1变量，M为充分大正数。易见，当y=0时，式就是原来的第r个约束条件，具有约束作用。此时对式而言，无论Xj为何值都成立，毫无约束作用，这就使问题仅允许第r种资源进行投资。当y=1时，式对Xj起了约束作用，而式成了多余的条件。到底是满足还是，则视问题在求出最优解后，y为0还是1而定。54（2）如果问题是要求在前m个约束条件中至少满足k(1k0，则令则令xj=1-yj3）如果约束条

48、件是如果约束条件是“ ”形，则可两边乘形，则可两边乘-1，改为，改为“ ”形形；4）若某个约束条件为）若某个约束条件为“=”形，则化为两个形，则化为两个“ ”的不等的不等式式,如如n1jijijn1jijijn1jijijbxabxabxa可化成63（3）隐枚举法的基本思想 见P83例1、用隐枚举法求解下列0-1规划)5.,2, 1j(100242645723. t . s4352zmaxxxxxxxxxxxxxxxxxj543215432154321或解：令x1=1-y1,x3=1-y3,x5=1-y5,x2=y2,x4=y4化为规范形得：64)5.,2, 1j(105242845723.

49、t . s435211zmaxyyyyyyyyyyyyyyyyj543215432154321或其求解过程如下图所示：y4=0y5=101234567810911121314Z=11y3=1y3=0y4=1y5=1y5=0y2=1y2=0y4=0y4=1y5=0y1=0y1=1可行解z=3可行解z=1可行解z=2不可行子域不可行子域可行解z=6可行解z=2不可行子域由此可知，最优解为x3=x4=x5=1,x1=x2=0,maxz=665三三. . 指派问题及其解法指派问题及其解法 任务 人员 E J G R 甲 3 14 10 5 乙 10 4 12 10 丙 9 14 15 13 丁 7 8

50、 11 9 解：设Xij表示第i人从事第j项工作，且 01jiX因此，该问题的数学模型为当指派第i人去完成第j项工作否则 引例：假设有4个人去完成4项任务，每个人由于技术、专长不同，完成任务的时间如下表，且规定每人只能做一项工作，每项工作只能由一人完成，问应如何分配任务使总费用最小？66MinZ=3X11+14X12+10X13+5X14+10X21+4X22+12X23+10X24 +9X31+14X32+15X33+13X34+7X41+8X42+11X43+9X44 111144342414433323134232221241312111XXXXXXXXXXXXXXXX表示第j项工作只指

51、派1人完成 111144434241343332312423222114131211XXXXXXXXXXXXXXXX表示第i人被指派完成一项工作 Xij=0或1(i,j=1,2,3,4) 67 诸如此类，有n项任务，恰好有n个人可承担这些任务，但由于每人的技术专长不同，完成任务的效率(所费时间不同，为使完成n项任务的总效率最高（即所需总时间最少），应如何指派（分派）人员的问题统称为指派（分派）问题。一、指派问题的数学模型及其特点一、指派问题的数学模型及其特点1.数学模型： ninjijijijCXCMinZ11)0(),.,2, 1(10),.,2, 1(1),.,2, 1(111nijXni

52、XnjXijnjijniij或682.特点 （1）给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(Cij)nxn,且Cij0，因此必有最优解( )。 ninjijijXCMinZ110（2）指派问题是一种特殊的平衡运输问题，由于模型结构的特殊性（看作每个产地的产量均为1，每个销地的销量均为1），故可用更为简便的匈牙利算法进行求解。二、指派问题的解法二、指派问题的解法匈牙利法匈牙利法 匈牙利法是求解指派问题的一种好算法，它只能求解目标函数为最小化的情况，它由匈牙利数学家柯尼格（D.Konig)提出，因此而得名。69 1.匈牙利法的基本思想是：对同一项工作（任务）j来说，同时提高或降低每人相

53、同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数di），也不影响其最优指派，因此可得到新的效率矩阵(bij)nxn，其中 bij=Cij+ti+dj （对所有的i,j）则新的目标函数为ninjijijXbZ11ninjijjiijXdtC11)( ninjninjniijjnjijiijijXdXtXC111111)()()(11ninjjidtZ其中ninjjidt11为常数70 这说明Z与Z同时达到最小值。因而最优解相同。故指派问题有以下性质： 若从效率矩阵(Cij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，得到的

54、新效率矩阵(bij)nxn不改变原指派问题的最优解。 2.匈牙利法的计算步骤见P88-89三、关于求最大化的指派问题71 对于求最大化的指派问题（即求 ）,可采用构造新的效率矩阵(MCij)nxn，其中M=maxCij，（显然MCij0），将其转化为 ninjijijXCMaxZ11ninjijijXCMZMin11)( 求所得到的最优解就是原问题的最优解。事实上 由于nM为常数，因此，使Z取得最小的最优解就是使Z取得最大的最优解。 ijninjijninjijninjijijXCXMXCMZ111111)(ZnMXCnMijninjij11724.以上讨论的指派问题是效率矩阵的行数等于列数，

55、即m+n的情况。当mn时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再用匈牙利法求解。 5.指派问题必有最优解，但可以不唯一。 n-m行000000,2111211mnmmnCCCCCC当mn时73第四章第四章 动态规划动态规划（Dynamic Programming) 动态规划是动态规划是1951年由美国数学家贝尔曼（年由美国数学家贝尔曼（Richard Bellman)提出，它是解决一类多阶段决策问题的优化方法，提出，它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径，而不是一种算法（如也是考察问题的一种途径，而不是一种算法（如LP单纯形法单纯形法）。因此它不象）。因此

56、它不象LP那样有一个标准的数学表达式和明确定义那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。的一组规则，而必须对具体问题进行具体分析处理。 动态规划方法是现代企业管理中的一种重要决策方法。如动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。方法进行求解。 根据多阶段决策过程的时序和决策过程的演变，动态规划根据多阶段决策过程的时序和决策过程的

57、演变，动态规划方法有以下四种类型：离散确定型、离散随机型、连续确定方法有以下四种类型：离散确定型、离散随机型、连续确定型和连续随机型型和连续随机型。返回741动态规划的基本概念和最优化原理一、引例（最短路问题）一、引例（最短路问题） 假如上图是一个线路网络，两点之间连线上的数字表示假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从两点间的距离（或费用），我们的问题是要将货物从A地运地运往往E地，中间通过地，中间通过B、C、D三个区域，在区域内有多条路径三个区域，在区域内有多条路径可走，现求一条由可走，现求一条由A到到E的线路，使总距离最短（或总费用的

58、线路，使总距离最短（或总费用最小）。最小）。AB1B2B3C1C2C3D1D2E2437463242653463333475 将该问题划分为将该问题划分为4个阶段的决策问题，即第一阶段为从个阶段的决策问题，即第一阶段为从A到到Bj（j=1，2，3），），有三种决策方案可供选择；第二阶段有三种决策方案可供选择；第二阶段为从为从Bj到到Cj（j=1,2,3），），也有三种方案可供选择；第三阶也有三种方案可供选择；第三阶段为从段为从Cj到到Dj(j=1,2)，有两种方案可供选择；第四阶段为有两种方案可供选择；第四阶段为从从Dj到到E，只有一种方案选择。如果用完全枚举法，则可只有一种方案选择。如果用完

59、全枚举法，则可供选择的路线有供选择的路线有3321=18（条），将其一一比较才（条），将其一一比较才可找出最短路线：可找出最短路线：AB1C2D3E 其长度为其长度为12。 显然，这种方法是不经济的，特别是当阶段数很多，各显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。也是不现实的。 由于我们考虑的是从全局上解决求由于我们考虑的是从全局上解决求A到到E的最短路问题的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始

60、计算，由后向前逐步推至阶段开始计算，由后向前逐步推至A点：点：76第四阶段，由第四阶段，由D1到到E只有一条路线，其长度只有一条路线，其长度f4（D1）=3，同理同理f4（D2）=4。 第三阶段，由第三阶段，由Cj到到Di分别均有两种选择，即分别均有两种选择，即64433minDfDCDfDCminCf2421141113，决策点为D1643*33minDfDCDfDCminCf2423141333,决策点为D17*4336minDfDCDfDCminCf2422141223，决策点为D277第二阶段，由Bj到Cj分别均有三种选择，即： 11667467minCfCBCfCBCfCBminBf