运筹学与效益管理课件.ppt

1、运筹学与效益管理绪论本章是绪论，介绍运筹学的释义，重点是运筹学的基本特征与方法，使学生了解运筹学主要分支，明确计算机专业学习运筹学的目的，掌握学习运筹学的方法。第一节运筹学释义与发展简史大英百科全书：运筹学是一门应用于管理有组织系统的科学，运筹学为掌管这类系统的人提供决策目标和数量分析的工具。英：Operational research美：Operations research发展简史朴素运筹学：齐王赛马、丁渭修皇宫。起源：1938年，英国研究雷达站的配置协调问题。发展：1.45-50，创建、线性规划2.50年代，使用计算机、快速成长发展3.60年代，应用普及、快速发展4.当代，广泛应用，尤其

2、在经济领域第二节基本特征与方法 系统的整体观念：协调部分、整体最优 多学科的综合：交叉学科，吸收多学科多领域的经验和技能 模型方法的应用：建立数学和模拟的模型，抽象研究。模型方法1.分析和表述问题：定性分析,决定决策目标，识别关键因素，列出控制变量。2.建立模型：抽象规范，找出本质规律，分析因果关系，研究算法。3.求解：求出可行解，满意解，最优解4.检验解5.建立对解的控制6.方案的实施第三节运筹学主要分支 线性规划 非线性规划 动态规划 图与网络分析 存贮论 排队论 对策论 决策论第四节运筹学与管理科学 马克思：一门科学只有成功地应用数学时，才算达到了完善的地步。运筹学实际上是数学应用于管理

3、计算机专业为什么学运筹学 效率与效益 复杂计算机算法需要运筹学 将来从事管理工作如何学好运筹学 多动脑筋 多做题 多理论联系实际本章介绍的线性规划及单纯形法是运筹学的基础和核心，重点是线性规划数学模型，从图解法开始，引入单纯形法的原理，使学生了解单纯形法计算步骤，通过对一些实例的分析，使学生掌握建立数学模型的方法。本章的难点是单纯形法计算步骤，必须通过大量的习题练习，本章共布置15道习题。第一章线性规划及单纯形法 第一节线性规划问题及数学模型 例 产量 I x1 II x2每天可用能力设备A(h)y1设备B(h)y2调试工序(h)y306152115245利润(元)21目标函数max z=2x

4、1+x2约束条件5x2156x1+2x2 24x1+x2 5x1,x20目标函数max(min)z=c1x1+c2x2+cnxn约束条件a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2am1x1+am2x2+amnxn(=,)bmx1,x2,xn 0标准化步骤1.当 bi0 时，等式两边同乘-1。2.约束条件为不等式，添加松弛变量。当“”，加+xk,使约束条件为等式。当“”，加-xk,使约束条件为等式。3.X取值无约束，令 x=x x,x 0,x 0。4.当 x0 时,令x=-x,x 0。5.min z=cx 改为 max(-z)=-cx。标准形式m

5、ax z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1,x2,xn 0b1,b2,bm 0 线性消元法(1)两边同乘非零。(2)交换两行。(3)将一行的倍数加到另一行。1 0 0 c1r+1 c1n d10 1 0 c2r+1 c2n d2 0 0 1 crr+1 crn dr0 0 0 0 0 dr+10 0 0 0 0 dm 若dr+1,dm不全为零，方程组无解。若r=n，方程组有唯一解。若r 0,又Pj 0,则当，z,即有无界解。无可行解：找不到初始基可行解。直接观察x1=b1-a

6、1m+1xm+1-a1jxj-a1nxn x2=b2 a2m+1xm+1-a1jxj a2nxnxm=bm-amm+1xm+1-amjxj amnxn当xj增加1，则目标函数增加cj，然而xi减少aij，目标函数减少ciaij，i=1,2,m.合计变动，miijijjacc1 当j 0，为了得到最大，xj越小越好，xj=0。当j 0，为了得到最大，xj越大越好，因此把xj 0，即取作基变量。但是xj增大，会使xj0(2）确定换出基变量：（3）初等行变换4.重复第2，3步，直至所有j 0lklikikiabaab0|mincj21000CB基Bx1x2x3x4x5000 x3x4x5152450

7、61521100010001j21000020 x3x1x5154101052/64/610001/6-1/6001j01/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2000-1/4-1/2第五节单纯形法的进一步讨论1.人工变量法：如果标准化后，系数矩阵中没有单位矩阵，则引进单位向量，形成单位矩阵。为了在最优解中人工变量取值为零，令人工变量的价值系数为任意大的负值，“-M”。在计算各列的检验数时，只要人工变量取值大于零，目标函数就不是最优。2.若最优解中，人工变量取值大于零，则原问题无可行解。cj-30100-M-MCB基B

8、x1x2x3x4x5x6x70-M-Mx4x6x74191-201131-111000-10010001j-2M-34M10-M0000-Mx4x2x73163-260102-141001-13-11-3001j6M-304M+103M-4M000-3x4x2x103100101001/32/3100-1/201/21/20-1/2-1/21/31/6j00303/2-M-3/2-M2 两阶段法:相当于ci=ci/M为了解决计算机求解时“M”的取值的麻烦（1）先求目标函数中只包含人工变量的线形规划，他们的价值系数为-1。当人工变量取值为零，目标函数值也为零。此时的最优解是原问题的基可行解。若最

9、优解的目标函数值不为零，则原问题无可行解。（2）若有可行解，则在原问题中除去人工变量，恢复原来的价值系数，继续寻找。cj00000-1-1CB基Bx1x2x3x4x5x6x70-1-1x4x6x74191-201131-111000-10010001j-2400-10000-1x4x2x73163-260102-141001-13-11-3001j60403-40000 x4x2x103100101001/32/3100-1/201/21/20-1/2-1/31/6j00000-1-1恢复原来的目标函数cj-30100CB基bx1x2x3x4x500-3x4x2x103100101001/32

10、/3100-1/201/2j00303/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/4j-9/2000-3/43。几个问题1.极小问题：最优标志是所有j 02.退化：在选择换出基，有时会出现多个最小比值，表示有多余的约束条件，存在线性相关。对策：始终选择下标值最小的变量作为换出变量和换入变量。3.无可行解：添加人工变量后。无论人工变量法还是两阶段法，当求解出现所有j 0，如基变量中仍然含有非零的人工变量，表明问题无可行解。第六节数据包络分析1。有关概念：数据包络分析(data envelopment analysis,DEA)是一种基于线性规划的用于

11、评价同类型组织工作绩效相对有效性的工具。各个部门有相同的投入产出项目，如果投入产出比可以折算成同一单位，就可以进行绩效排序。2维投入可化生产前沿面，形成一条数据包络线。线上的点，表示投入的最低极限。2.线性规划的数学模型设有n个决策单元，每个决策单元有相同的m项投入和相同的s项产出。决 策 单 元 d1 d2dn投 1 x11 x12 x1n 2 x21 x22 x2n入m xm1 xm2 xmn y11 y12 y1n 1 产 y21 y22 y2n 2 ys1 ys2 ysn s 出 构造由n个决策单元的线性组合1d1+2d2+ndn,1+2+n=1投入为：X 产出为：Y 现在要衡量某一个

12、决策单元j的DEA,Min EX ExjY yj1+2+n=1 例8 分理处1分理处2 分理处3 分理处4职员数 15 20 21 20营业面积 140 130 120 135储蓄存款 1800 1000 800 900 贷款 200 350 450 420中间业务 1600 1000 1300 1500 再用4个决策单元的线性组合对每个分理处计算 E，确定各分理处是否 DEA有效第七节应用举例 问题的目标能用某种指标度量大小，并能用线性函数表示。存在多种方案达到目标。受到一些条件的约束，可用线性等式或不等式表示。建立实际问题的线性规划模型，比解线性规划更有挑战性，创造性。本章介绍线形规划的对

13、偶性理论，重点是对偶性理论的意义，从对偶问题开始，引入对偶性理论，使学生从多方面了解线形规划，通过对灵敏度分析和参数线形规划的分析，使学生建立变化运动的观点，掌握辨证的思维方法。本章的难点是对偶性理论的经济意义，本章共布置12道习题。第二章线性规划对偶性理论与灵敏度分析第一节线性规划的对偶性理论1。问题的提出：每一个线性规划问题都有对偶问题，求出一个问题，同时也给出另一个问题的解。用yi表示第i种资源的估价。对称条件下对偶问题的一般形式max z=c1x1+c2x2+cnxna11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1,

14、x2,xn 0对偶问题min =b1y1+b2y2+bmyma11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcmy1,y2,ym 0Max z=CX min w=bYAX b AY CX 0 Y 0 max w=(-b)Y(-AY)-C Y 0 min w=(-C)Z(-A)Z (-b)Z 0 非对称条件下原-对偶问题关系原问题（对偶问题）对偶问题（原问题）AbC目标函数约束系数矩阵约束 条件右端向量价格系数向量转置矩阵价格系数向量约束 条件右端向量xj 0 xj 0 xj 无约束yj 0yj 0yj无约束njjjxczmaxmii

15、iybminmijiijcya1mijiijcya1mijiijcya1njijijbxa1njijijbxa1njijijbxa1第二节 对偶问题的基本性质 单纯形法的矩阵描述：A=(B,N),X=(XB,XN)T,C=(CB,CN).Max z=CX+0Xs=CBXB+CNXN+0XsAX+IXs=bBXB+NXN+IXs=b BXB=b-NXN-IXsXB=B-1b-B-1NXN-B-1Xs代入目标函数Max z=CBB-1b+(CN-CBB-1N)XN-CBB-1Xs CBCN0XBXNXs0XBbBNIjCBCN0CBXBB-1bIB-1NB-1j0CN-CBB-1N-CBB-1当

16、CN-CB B-1N 0,-CBB-1 0则 令XN=0，Xs=0，XB=B-1b,Max z=CB B-1b.(CB,CN)-CBB-1(B,N)0,C-CBB-1A 0-CBB-1 0令 Y=CBB-1,则AY CY 0Y就是松弛变量的检验数的相反数，恰好是对偶问题的可行解。w=Yb=CB B-1b=CBXB=z原问题max z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24x1+x2 +x5=5对偶问题min w=15y1+24y2+5y3+0y4+0y56y2+y3-y4 =25y1+2y2+y3 -y5=1xi,yi0cj21000CB

17、基bx1x2x3x4x5021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2j000-1/4-1/2cjy4y5y1y2y3b基CB1524500y1y2y3y4y5245y2y31/41/2-5/415/21001-1/41/21/4-3/2j15/2x30 x40 x57/2x13/2x2对偶问题的基本性质 1.弱对偶性：如果X是原问题的可行解，Y是对偶问题的可行解，AX b,YAX Yb,YA C,YAX CX,则 z=CX Yb=w 2.最优性：如果X是原问题的可行解，Y是对偶问题的可行解，且CX=Yb，则它们都是最优解。3.无界性：如果

18、原问题（对偶问题）具有无界解时，则其对偶问题（原问题）无可行解。注：逆命题不成立。如果原问题(对偶问题)有可行解,对偶问题(原问题)无可行解时，则其原问题(对偶问题)具有无界解。4.强对偶性：如果原问题和对偶问题都有可行解，则它们都有最优解，并且最优解的目标函数值相等。5.互补松弛性：最优解中，对偶变量 0 对应约束条件为等式。对应约束条件为不等式 对偶变量=0，CX YAX Yb,CX=Yb,Y(AX-b)=0,(YA-C)X=0 6.原问题和对偶问题之间存在一对互补的基解，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。(1)两者都有可行解,zw,从而有最优解z=w

19、。(2)两者都没有可行解。(3)一个有无界解 另一个无可行解。(4)一个有可行解,另一个无可行解可行解为无界解。四种情况恰出现一次。第三节影子价格 在最优解中，bi表示资源,对偶变量yi表示对资源的估价，称为影子价格，不是市场价格。Z=CX=bY=w1。影子价格取决于资源的利用率。2。影子价格是边际价格，表示在最优解中bi表示每增加一个单位时目标函数的增量。3。影子价格是机会成本，市场价格低于影子价格，可以买进，反之则卖出。4。yi 0 yi=0 5。j=cj-CBB-1Pj=cj YPj=cj-后者是生产第j种产品的隐含成本。6。线性规划的求解是资源的最优分配。对偶问题的求解是资源的恰当估价

20、。njjjijbxa1njjjijbxa1miiijya1第四节对偶单纯形法 对偶单纯形法的基本思想：单纯形法的迭代中，在保持常数项非负的条件下，逐步使得检验数非正。对偶的思想是，在保持检验数非正的条件下，逐步使得常数项非负。对偶单纯形法的计算步骤：1.列出初始单纯形表，使得检验数都非正。如果b列都非负，即为最优解。否则，计算br=minbi,xr为换出变量。2.确定换入变量：rssrjrjjaaa0|min3.以ars为主元素，xs为换入变量，消元。4.如果br1,x4的检验数0c2+1+2000CB基bx1x2x3x4x502+1+2x4x1x26230100014/5-1/51/5100

21、-610001/5-/50-2-当1,Z=7+8+当 -1/5,x5的检验数01/3+5/3 0,-1/3-/6 0 推出-2 -1/5,z=8+4 2+0,1+2 0推出 -2,z=0c2+1+2000CB基bx1x2x3x4x502+0 x3x1x5154101051/32/310001/6-1/600101/3+5/30-1/3-/60000 x3x4x5152450615211000100012+1+2000b=(15,24+,5)T,b=B-1bc21000CB基bx1x2x3x4x5021x3x1x215/2+5/47/2+/43/2-/40100011005/41/4-1/4-1

22、5/2-1/23/2000-1/4-1/2当当-6 6,6,继续Z=对17/2+偶单/4纯形法c21000CB基bx1x2x3x4x5020 x3x1x4155-6+01051-410000101-60-100-2021x5x1x2-1-/63+/63010001-2/15-1/151/5-1/61/601000-1-1/15-1/30001x5x3x2-7-/2-45-5/212+/2-2-153001010-1/2-5/21/2100-100-1/20讨论 当6，最优解不变，z=10-1-/6 0,3+/6 0推出-18 -6,z=9+/3-7-/2 0,-45-5/2 0推出-24 -1

23、8,z=12+/2 当200，z=9000-15c12300CB基bx1x2x3x4x521x2x12000100001107/3-4/31/10-1/10-104000-1/3-1/10-2021x2x12000-101000+4001107/3-4/31/10-1/10-10400 20000-1/3-1/10-2001x5x1-200900001-1/104-7/308-1/1003/10102000-2-5-3/100本章介绍运输问题，重点是运输问题的数学模型，从简单的事例开始，引入表上作业法，使学生掌握运输问题的解题方法。本章的难点是用运输问题的方法解决一些特殊线形规划问题，本章共布

24、置6道习题 第三章 运输问题 第一节 数学模型 0,.,2,1,.,2,1,min1111ijjmiijnjiijminjijijxnjbxmiaxxcz 产销地 B1B2 Bn 产量A1x11|c11x12|c12 x1n|c1na1A2x21|c21x22|c22 x2n|c2na2Amxm1|cm1xm2|cm2 xmn|cmnam销量b1b2 bnnjjmiibaQ1特点1.运输问题有有限最优解。xij=aibj/Q 是可行解,目标函数有下界0。2.运输问题约束条件的系数矩阵:秩=m+n-1。Aij=(0,1,0,0,1,0,0)3.运输问题的基可行解中非零变量的个数不能大于m+n-1

25、个，反映m+n-1个约束条件，对应的系数列向量线性独立。第二节表上作业法 先按某种规则找出一个初始解，然后作最优性判别。若不是最优，则在运输表上改进，迭代直至最优。一.初始基可行解：1.最小元素法：为了减少运费，优先考虑单位运价最小的供销业务，最大限度满足其供销量。然后再满足其次的供销业务。2.西北角法：优先满足运输表上西北角的供销业务。3.沃格尔法：对每一个供应地或销售地，计算它到各销售地或供应地的最小单位运价和次小单位运价的差，称之为该地的罚数，优先考虑罚数最大的供销业务，最大限度满足其供销量。然后再满足其次的罚数最大的供销业务。沃格尔法得出的初始解的质量最好，常作运输问题最优解的近似解。

26、二.解的最优性检验1.闭回路法：计算每一个空格的检验数，即给这个空格上增加一个单位运量，同时沿着一条包含它的闭回路调整相应格子的值，使其满足约束条件。闭回路经过的其余拐点都是填有数字的格子(基变量格)。闭回路上第奇数个格子的单位运价之和减去第偶数个格子的单位运价之和就是这个空格的检验数。在迭代中，不允许全部拐点都是填有数字的格子组成的闭回路，对应的列线性相关。2.对偶变量法运输问题的对偶规划：Max z=a1u1+amum+b1v1+bnvnui+vj cijui,vj 的符号不限。i=1,m,j=1,n由公式(2.24)知j=cj-CBB-1Pj=cj Ypj ij=cij (u1,um,v

27、1,vn)pij=cij (ui+vj)设xi1j1,xi2j2,xisjs,(s=m+n-1)是运输问题的一个基可行解，它们对应的检验数等于零，所以ui1+vj1=ci1j1uis+vjs=cisjs 这是关于一组(m+n)个对偶变量的(m+n-1)个方程，存在多个解。令ui=0，解出方程，不妨解就是u,v,如果它们满足约束方程ij=cij(ui+vj)0则它们就是对偶问题的可行解。对于X的基变量，j=cj Ypj=0，YA=C,YA-C=0对于X的非基变量,X=0。因此(YA-C)X=0,YAX=CX。另外原问题中 AX=b，于是Yb=CX，即X和Y分别为原问题和对偶问题的最优解。(Y不一

28、定是基可行解)如果求出的解不满足约束方程：ij=cij(ui+vj)0，则X不是原问题的最优解，还要继续迭代计算。3.解的改进(1)如果某一个格子代表的非基变量的检验数是负数，则把检验数最小的非基变量引入基变量。(2)沿着经过它的闭回路，寻找第偶数个格子的运输量的最小值min x ij作为调整量，(3)所有第偶数个格子的运输量都减去这个值，所有第奇数个格子的运输量都加上这个值，可使总运费减少ij min x ij。4。几个问题：1.在最优解中，如果有非基变量的检验数是零，则说明有无穷多个解。2.在求初始解和迭代过程中，可能出现在某格填上一个运量后需要在运输表上同时划去一行和一列，就出现退化。为

29、了不减少基变量，需要在同时划去一行或一列的某格填上零，表示它代表的变量是取值为零的基变量，从而使基变量恰好是m+n-1。3.在求初始解时，尽量减少退化。4.填零不可以形成闭回路。5.可能需要重新填零。第三节进一步讨论 1.产销不平衡：产量销量：加一个假想的销地。产量销量：加一个假想的产地。单位运价都是零。2.有转运的运输问题：实际中常常有转运的问题，即先把物品由产地运到某个中转站（可能是产地、销地或中转仓库），然后再运到最终销地。中转要花转运费，总运费可能降低。数学模型ai:第i个产地的产量。bj:第j个销地的销量。xij:由第i个发送地到第j个接收地的数量。cij:由第i个发送地到第j个接收

30、地的单位运价ti:第i个地点的转运量。ci:第i个地点的单位转运费。cii=-ci,xii=Q-tinjjmiibaQ1接收产地销地发送量发送1 mm+1 m+n产地1 mx11 x1m xm1 xmmx1m+1 x1m+n xmm+1 xmm+nQ+a1Q+an销地m+1m+nxm+11 xm+1m xm+n1 xm+nmxm+1m+1 xm+1m+n xm+n m+1 xm+n m+nQQ接收量 Q QQ+bm+1 Q+bm+n接收产地销地发送量发送1 mm+1 m+n产地1 m-c1 c1m cm1 -cmc1m+1 c1m+n cmm+1 cmm+nQ+a1Q+an销地m+1m+ncm+11 cm+1m cm+n1 xm+nm-cm+1 cm+1m+n cm+n m+1 -cm+n QQ接收量 Q QQ+bm+1 Q+bm+n第四节应用问题举例 如果为了使xij=0，可令cij=M。如果为了使xij充分满足，可令cij=0。如果产量在一个区间内，可分成两个产量，一个为必需满足的，另一个为可能满足的。然后增加虚销地，必需部分的cij=M，可能部分的cij=0。