《(本科）第5章 线性规划的应用教学ppt课件.ppt》由会员分享，可在线阅读，更多相关《(本科）第5章 线性规划的应用教学ppt课件.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、(本科）第5章 线性规划的应用教学ppt课件21世纪高等院校公共课精品教材管理运筹学管理运筹学董银红 付丽丽 编著东 北 财 经 大 学 出 版 社Dongbei University of Finance&Economics PressCONTENTS第5章 线性规划的应用线性规划被认为是在制定决策时最成功的定量化方法之一，它应用于许多行业，涉及的问题包括：生产计划，媒体选择，财务计划，资本预算，运输问题，配送系统设计，产品组合，人事管理以及混合问题等等。前三章已经介绍了线性规划的模型和理论，并且将其作为一种灵活的解决问题的工具展示给大家了。那么在本章将从应用的角度来学习和熟练掌握线性规划这
2、一定量工具。线性规划的这些应用包括理论上的如数据包络分析，实践上的如来自传统商业领域的营销，财务，市场以及运营管理等。对这些问题的解决还是集中与前面提及的建模，求解和结果解释上。所以如何建模，利用计算机求解以及输入和输出结果的解释是本章的重点。在依据所研究的问题来建立数学模型时，使用的工具仍然是LINDO/LINGO和Excel工具。CONTENTS5.1 运输规划5.1.1 运输问题的数学模型运输问题的数学模型运输问题经常出现在计划货物配送和从供给地到需求地的服务中，特别是针对每个供给地的货物总量是有限的，每个需求地的货物需求是已知的情形。运输问题中最常用的目标是使得货物从起点到目的地的运输
3、成本最低。首先看下下面的例子。CONTENTS5.1 运输规划【例例5-15-1】 有A1、A2、A3三个铁矿，每天要把生产的铁矿石运往B1、B2、B3、B4四个炼铁厂。各矿的产量、各厂的销量(百吨/天)以及各厂矿间的运价（百元/百吨）见表5-1。问：应如何组织调运可使总运输费用最小？CONTENTS5.1 运输规划一般的运输模型可以分成3种类型：当总产量等于总销量，也即 时，称为产销平衡的问题；当 时，称为产大于销的运输问题；当 时，称为产小于销的运输问题；后两者统称为产销不平衡问题。因此对应于这三种类型，一般的运输模型有相应的三种数学表达形式。目标函数：11mnijijab11mnijij
4、ab11mnijijab11minmnijijijzc x CONTENTS5.1 运输规划约束条件为：产销平衡模型： 产大于销模型：11,1,2,.,. .,1,2,.,0nijiimijjjijxa imstxbjnx11,1,2,.,. .,1,2,.,0nijiimijjjijxa imstxbjnxCONTENTS5.1 运输规划产小于销模型：11,1,2,.,. .,1,2,.,0nijiimijjjijxa imstxbjnxCONTENTS5.1 运输规划由以上的模型容易看出，运输问题有以下两个特点：（1）它有mn个变量；（2）它有m+n个约束方程。其系数具有特殊的结构，例如例
5、5-1的系数矩阵就有这样的特征。CONTENTS5.1 运输规划 5.1.2 表上作业法表上作业法表上作业法的基本步骤可参照单纯形法归纳如下：（1）找出初始基可行解：即要在 阶产销平衡表上给出“ ”个数字格（基变量）；（2）求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；（3）确定入基变量，若 ，那么选取 为入基变量；m n1mnmin0ijijlklkxCONTENTS5.1 运输规划（4）确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量；（5）在表上用闭
6、合回路法调整运输方案；（6）重复步骤（2）至（5），直到得到最优解。CONTENTS5.1 运输规划1. 确定初始基可行解确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解），这一点是显然的。确定初始基可行解的方法有很多，在此介绍比较简单但能给出较好初始方案的最小元素法（the least cost rule）和伏格尔法（Vogels approximation method）。CONTENTS5.1 运输规划【例例5-25-2】 某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售
7、点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表5-3所示。问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。CONTENTS5.1 运输规划CONTENTS5.1 运输规划【例例5-35-3】 仍以例5-2种相关数据来说明伏格尔法。 伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤是完全相同的。伏格尔法给出的初始解比最小元素法给出的初始解一般来讲会更接近于最优解。CONTENTS5.1 运输规划2. 2. 基可行解的最优性检验基可行解的最优性检验对初始基可行解的最优性检验
8、有闭合回路法和位势法两种基本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。CONTENTS5.1 运输规划从表5-8给定的初始方案的任一空格出发寻找闭合回路，如对于空格（A，甲）在初始方案的基础上将A生产的产品调运一个单位给甲，为了保持新的平衡，就要依次在（A，丙）处减少一个单位、（B，丙）处增加一个单位、（B，甲）处减少一个单位；即要寻找一条除空格（A，甲）之外其余顶点均为有数字格（基变量）组成的闭合回路。表5-26中用虚线画出了这条闭合回路。闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。CON
9、TENTS5.1 运输规划对应这样的方案调整，运费会有什么变化呢？可以看出（A，甲）处增加一个单位，运费增加3个单位；在（A，丙）处减少一个单位，运费减少3个单位；在（B，丙）处增加一个单位，运费增加2个单位；在（B，甲）处减少一个单位，运费减少1个单位。增减相抵后，总的运费增加了1个单位。由检验数的经济含义可以知道，（A，甲）处单位运量调整所引起的运费增量就是（A，甲）的检验数，即 。111CONTENTS5.1 运输规划仿照此步骤可以计算初始方案中所有空格的检验数，表5-27至表5-32展示了各检验数的计算过程，表5-32给出了最终结果。可以证明，对初始方案中的每一个空格来说“闭合回路存在
10、且唯一”。CONTENTS5.1 运输规划CONTENTS5.1 运输规划CONTENTS5.1 运输规划如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导致运费的增加，即给定的方案是最优方案。在表5-32中， ，说明方案需要进一步改进。241 CONTENTS5.1 运输规划如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导致运费的增加，即给定的方案是最优方案。在表5-32中， ，说明方案需要进一步改进。241 CONTENTS5.1 运输规划对于特定的调运方案的每一行 给出一个因子 （称为行位势），每一列给出一个因子 （称为列位势），使对于目前解的每
11、一个基变量 有 ，这里的 和 可正、可负也可以为零。那么任一非基变量 的检验数就是这一表达式完全可以通过先前所述的闭合回路法得到。在某一的闭合回路上（如下表所示），由于基变量的运价等于其所对应的行位势与列位势之和，即： ， ， iiujvijxijijcuviujvijx()ijijijcuvikikcuvlklkcuvljljcuvCONTENTS5.1 运输规划于是所以()()()ijijiklkljijiklkljcccccuvuvuv()ijijijcuvCONTENTS5.1 运输规划3. 3. 方案的优化方案的优化在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。在入
12、基变量所处的闭合回路上，赋予入基变量最大的增量，即可完成方案的优化。在入基变量有最大增量的同时，一定存在原来的某一基变量减少为“0”，该变量即为出基变量。切记出基变量的“0”运量要用“空格”来表示，而不能留有“0”。在表5-32中 ，故选择 为入基变量。在入基变量 所处的闭合回路上（如表5-34所示），赋予 最大的增量“1”，相应地有 出基、 、 。利用闭合回路法或位势法计算各空格（非基变量）的检验数，可得表5-35（同伏格尔法的初始解表5-25）。24min|01ijij 24x24x24x23x513x214xCONTENTS5.1 运输规划由于表5-35中的检验数均大于等于零，所以表5-
13、35（同伏格尔法所给出的初始解表5-25）给出的方案是最优方案，这个最优方案的运费是85个单位。CONTENTS5.1 运输规划5.1.3 运输问题的运输问题的LINGO求解方法求解方法上面的求解过程比较复杂，利用软件可以在不知道原理的情况下轻松求解运输规划问题。针对以上提及的的产销平衡的运输问题：1111min,1,2,.,. .,1,2,.,0mnijijijnijiimijjjijzc xxa imstxbjnx CONTENTS5.1 运输规划可以给出一般的LINGO模型如下：Model:Sets:Row/1.m/:a;Arrange/1.n/: b;Link(row, arrange
14、): c,x;EndsetsData:a=a(1),a(2),a(m);b=b(1),b(2),b(n);c=c(1,1),c(1,2),.c(1,n), CONTENTS5.1 运输规划c(m,1),c(m,2),.c(m,n);enddataOBJmin=sum(link(i,j):c(i,j)*x(i,j);for(row(i):sum(arrange(j):x(i,j)=a(i););for(arrange(j):sum(row(i):x(i,j)=b(j););for(link(i,j):x(i,j)=0;);End 针对产销不平衡的情况，也可以类似的给出LINGO 代码。另外，只要
15、在以上的程序中赋值，就可以简便的求解运输规划问题。读者可以自己寻找例子来演算和验证。CONTENTS5.2 数据包络分析 数据包络分析(data envelopment analysis,简称DEA)将数学，经济，管理的概念和方法相结合，构成了运筹学的一个新领域，是线性规划及其对偶理论的一个应用。它对于研究具有相同类型的部门的相对有效性问题，处理多目标决策问题，经济理论中的多输入多输出问题十分有效。DEA的本质就是利用统计数据确定相对有效的生产前沿面，利用有效前沿面的理论和方法研究部门和企业的技术进步状况，建立非参数的最优化模型。CONTENTS5.2 数据包络分析5.2.1 DEA线性规划模
16、型线性规划模型DEA是线性规划一个很突出的应用，经常被用来衡量拥有相同的运转目标单位的相对效率。大多数机构的运营单位都有多种投入要素，如员工规模，工资水平，运转时间和广告投入等，同时也有多种产出要素，如利润，市场份额和增长率等。在这些情况下，当投入转化为产出量时，管理者是很难知道哪个运营单位是效率低下的。DEA通过产出与投入的比值来表示运营效率，利用最好的要素组合来评价一个运营单位。CONTENTS5.2 数据包络分析下面就利用DEA来评估4家医院的效率。待评价四家医院分别是：大众医院，学校医院，乡镇医院和国家医院。首先通过一些调查和研究，确定对于一个医院刻画绩效的比较关键的几个输入和输出指标
17、。比如：可以提炼出3个输入量和4个输出量。输入量为:全职非主治医师的人数；物料消耗额；可用的病床数。输出量分别为：开诊日的药物治疗服务；开诊日的非药物治疗；接受培训的护士数目；接受过培训的实习医师数目。一年里这4家医院的输入量和输出量的统计结果如表5-36所示。CONTENTS5.2 数据包络分析CONTENTS5.2 数据包络分析通过以上的讨论，基本上可以将以上的DEA线性规划模型按照标准的线性规划模型的形式写出来：min1 48.1434.6236.7233.1636.7243.10 +27.11+45.9856.4645.98253148175160175. . 412723842328
18、5.20162.30275.70210.40275.70123.8012gucsgucsgucsgucsgucsgucsgEwwwwwwwwwwwwwwwwstwwwwwwwwEw8.70348.50154.10348.50106.7264.21104.10104.04104.10,0.ucsgucsgucswwwEwwwwEE ww w wCONTENTS5.2 数据包络分析针对以上的模型，可以利用前面讲到的计算机求解方法得到结果E=0.902（下面的小节将详细介绍）。这个目标值表明，只需要使用乡镇医院90.2的输入资源，就可以获得与乡镇医院相同的输出量。求解报表得到的松弛变量和剩余变量提供
19、了丰富的信息，在下面的小节中也会着重提到。CONTENTS5.2 数据包络分析5.2.2 DEA模型的计算机求解与分析模型的计算机求解与分析1.LINDO1.LINDO求解求解DEADEA问题问题LINDO的应用十分简便，只需要按照第二章介绍的一些简单语法准则输入就可以了。具体的命令可以如下：min es.t.wg+wu+wc+ws=148.14 wg+34.62 wu+36.72 wc+33.16ws36.4243.10 wg+27.11 wu+45.98 wc+56.46 ws45.98253 wg+148 wu+175 wc+160 ws17541 wg+27 wu+23 wc+84 w
20、s23285.20 wg+162.30 wu+275.70 wc+210.40 ws-275.70 e0123.8 wg+128.7 wu+348.5 wc+154.1 ws-348.5 e0106.72 wg+64.21 wu+104.1 wc+104.04 ws-104.1 e0CONTENTS5.2 数据包络分析点击结果就得到如下的报表：以上结果求出了效率指数，说明了乡镇医院可以提供给合成医院的输入量比例为90.2%.CONTENTS5.2 数据包络分析2.DEA-Solver2.DEA-Solver求解求解DEADEA问题问题可以看到，单是求解一个运营单位的相对效率就非常复杂。在实际应
21、用中，对于DEA的求解都是应用专门的求解软件来求解的。DEA-Solver求解软件就是很常用的一种，它通过内嵌于Excel中的宏命令，只需要输入和输出数据，就可以得到所有运营单位的相对效率和一些整改措施。DEA-Solver提供了七种比较常见的模型。这些模型包括输入导向的CCR模型（CCR-I），输出导向的CCR模型（CCR-O），输入导向的BCC模型（BCC-I），输出导向的BCC模型（BCC-O），输入导向的自信区间模型（AR-I-C）等。这些模型的划分实际上是根据生产可能性集合来进行的，在本节中，主要利用输入导向的CCR模型来求解以上医院的评价问题，详细的应用过程可以参考附录B,对理论有
22、兴趣的读者可以参照其他相关的DEA书籍。CONTENTS5.2 数据包络分析5.2.3 CCR与与BCC模型模型1. CCR模型：假设有n个决策单元，每个决策单元都有m种类型的“输入”以及s种类型的“输出”。以x表示输入指标，y表示输出指标，则第j个DMU的输入和输出指标向量可以记做：决策单元集合DMUs的统计数据表示为： ， 1(,)Tjjmjxxx1(,)Tjjmjyyy11121121222212,jnjnmmmjmnxxxxxxxxxxxxx11121121222212,jnjnsssjsnyyyyyyyyyyyyyCONTENTS5.2 数据包络分析通过Charnes-Cooper变
23、换，分式目标函数中的分子部分从形式上保留了下来，分母变成了1，成为约束条件的一部分，这样分数目标规划函数就变成了线性目标函数。由以上线性规划(P)来判断决策单元的弱DEA有效性和DEA有效性的依据如下：如果线性规划问题的最优解 满足 ,则称决策单元 是弱DEA有效的。如果线性规划问题的最优解 满足 ，则称决策单元 是DEA有效的。 ,w01TY0j0,0w01TY0jCONTENTS5.2 数据包络分析以上的模型一般也可以采用对偶形式来表示: 0101min. .( )0,1,2,0DnjjjnjjjjVstXsXDYsYjnssCONTENTS5.2 数据包络分析2. BCC2. BCC模型
24、模型考虑由m项输入，s项输出和n个决策单元组成的评价系统，其中生产可能集为:上述的生产可能集形式与CCR模型是相对应的。实际上，生产可能集的形式是根据不同的公理唯一确定的。随着公理体系的不同，生产可能集也不相同，因而生产前沿面也是不一样的，而DEA有效的决策单元的判定本质上就是判定是否落在生产可能集的生产前沿面上。如果在CCR模型中加上锥性约束，那么CCR模型就可以转化为BCC模型。具体来讲，BCC的生产可能集为： 11(, )|,0nnCCRjjjjjjjTX YXXYY111(, )|,1,0nnnBCCjjjjjjjjjTX YXXYYCONTENTS5.2 数据包络分析用对偶形式可以写成：同样的，可以得到：如果问题（D）的最优值为1，并且 ，则决策单元是BCC有效的。 01011min. .( )10,1,2,0DnjjjnjjjnjjjVstXXYYDjnss