运筹学所有内容

单击此处编辑母版标题样式,单击此处编辑母版文本样式,Page,486,运 筹 学,( Operations Research ),运筹学简述,运筹学（,Operations Research,）,系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学,(Management Science),。运筹学所研究的问题，可简单地归结为一句话：,“依照给定条件和目标，从众多方案中选择最佳方案”,故有人称之为最优化技术。,运筹学简述,运筹学的历史,“,运作研究,(Operational Research),小组,”,:,解决复杂的战略和战术问题。例如：,如何合理运用雷达有效地对付德军德空袭,对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；,在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。,运筹学的主要内容,数学规划（,线性规划、整数规划、目标规划,、动态规划等）,图论,存储论,排队论,对策论,排序与统筹方法,决策分析,本课程的特点和要求,先修课：,高等数学，基础概率、线性代数,特点：,系统整体优化；多学科的配合；模型方法的应用,运筹学的研究的主要步骤：,真实系统,系统分析,问题描述,模型建立与修改,模型求解与检验,结果分析与实施,数据准备,运筹学在工商管理中的应用,运筹学在工商管理中的应用涉及几个方面：,生产计划,运输问题,人事管理,库存管理,市场营销,财务和会计,另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。,运筹学在工商管理中的应用,Interface,上发表的部分获奖项目,组织,应用,效果,联合航空公司,在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排,每年节约成本,600,万美元,Citgo,石油公司,优化炼油程序及产品供应、配送和营销,每年节约成本,7000,万,AT&T,优化商业用户的电话销售中心选址,每年节约成本,4.06,亿美元，销售额大幅增加,标准品牌公司,控制成本库存（制定最优再定购点和定购量确保安全库存）,每年节约成本,380,万美元,法国国家铁路公司,制定最优铁路时刻表并调整铁路日运营量,每年节约成本,1500,万美元，年收入大幅增加。,Taco Bell,优化员工安排，以最低成本服务客户,每年节约成本,1300,万美元,Delta,航空公司,优化配置上千个国内航线航班来实现利润最大化,每年节约成本,1,亿美元,“,管理运筹学,”,软件介绍,“,管理运筹学,”,2.0,版包括：线性规划、运输问题、整数规划（,0-1,整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共,15,个子模块。,Chapter1,线性规划,(Linear Programming),LP,的数学模型,图解法,单纯形法,单纯形法的进一步讨论人工变量法,LP,模型的应用,本章主要内容：,线性规划问题的数学模型,1.,规划问题,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（,1,）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（,2,）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大,.,）,线性规划问题的数学模型,例,1.1,如图所示，如何截取,x,使铁皮所围成的容积最大？,x,a,线性规划问题的数学模型,例,1.2,某企业计划生产甲、乙两种产品。这些产品分别要在,A,、,B,、,C,、,D,、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？,设 备,产 品,A,B,C,D,利润（元）,甲,2,1,4,0,2,乙,2,2,0,4,3,有 效 台 时,12,8,16,12,线性规划问题的数学模型,解：设,x,1,、,x,2,分别为甲、乙两种产品的产量，则数学模型为：,max Z = 2x,1,+ 3x,2,x,1, 0 , x,2, 0,s.t.,2x,1,+ 2x,2, 12,x,1,+ 2x,2, 8,4x,1, 16,4x,2, 12,线性规划问题的数学模型,2.,线性规划的数学模型由三个要素构成,决策变量,Decision variables,目标函数,Objective function,约束条件,Constraints,其特征是：,（,1,）问题的目标函数是多个决策变量的,线性,函数，通常是求最大值或最小值；,（,2,）问题的约束条件是一组多个决策变量的,线性,不等式或等式。,怎样辨别一个模型是线性规划模型？,线性规划问题的数学模型,目标函数：,约束条件：,3.,线性规划数学模型的一般形式,简写为：,线性规划问题的数学模型,向量形式：,其中：,线性规划问题的数学模型,矩阵形式：,其中：,线性规划问题的数学模型,3.,线性规划问题的标准形式,特点：,(1),目标函数求最大值（有时求最小值）,(2),约束条件都为等式方程，且右端常数项,b,i,都大于或等于零,(3),决策变量,x,j,为非负。,线性规划问题的数学模型,（,2,）如何化标准形式,目标函数的转换,如果是求极小值即 ，则可将目标函数乘以,(-1),，可化为求极大值问题。,也就是：令 ，可得到上式。,即,若存在取值无约束的变量 ，可令,其中：,变量的变换,线性规划问题的数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令 ，显然,线性规划问题的数学模型,例,1.3,将下列线性规划问题化为标准形式,用 替换 ，且,解,:,（）因为,x,3,无符号要求 ，即,x,3,取正值也可取负值，标准型中要求变量非负，所以,线性规划问题的数学模型,(2),第一个约束条件是“”号，在“”左端加入松驰变量,x,4,，,x,4,0,化为等式；,(3),第二个约束条件是“”号，在“”左端减去剩余变量,x,5,，,x,5,0,；,(4),第,3,个约束方程右端常数项为,-5,，方程两边同乘以,(-1),将右端常数项化为正数；,(5),目标函数是最小值，为了化为求最大值，令,z=-z,得到,max z=-z,，即当,z,达到最小值时,z,达到最大值，反之亦然,;,线性规划问题的数学模型,标准形式如下：,线性规划问题的数学模型,4.,线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件,(2),、,(3),的方程组中找出一个解，使目标函数,(1),达到最大值。,线性规划问题的数学模型,可行解,：满足约束条件、的解为可行解。所有可行解的集合为可行域。,最优解,：使目标函数达到最大值的可行解。,基：,设,A,为约束条件的,mn,阶系数矩阵,(m0,40,10,换出行,将,3,化为,1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以,1/3,后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,单纯形法的计算步骤,例,1.9,用单纯形法求解,解：将数学模型化为标准形式：,不难看出,x,4,、,x,5,可作为初始基变量，列单纯形表计算。,单纯形法的计算步骤,c,j,1,2,1,0,0,i,c,B,基变量,b,x,1,x,2,x,3,x,4,x,5,0,x,4,15,2,-3,2,1,0,0,x,5,20,1/3,1,5,0,1,1,2,1,0,0,0,x,4,2,x,2,20,x,2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x,1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,单纯形法的计算步骤,学习要点：,1.,线性规划解的概念以及,3,个基本定理,2.,熟练掌握单纯形法的解题思路及求解步骤,单纯形法的进一步讨论人工变量法,人工变量法：,前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大,M,法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,单纯形法的进一步讨论人工变量法,例,1.10,用大,M,法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量，得到人工变量单纯形法数学模型：,其中：,M,是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。,单纯形法的进一步讨论人工变量法,c,j,3,2,-1,0,0,-M,-M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,i,0,x,6,4,-4,3,1,-1,0,1,0,4,-M,x,5,10,1,-1,2,0,1,0,0,5,-M,x,7,1,2,-2,1,0,0,0,1,1,3-2M,2+M,-1+2M,-M,0,x,6,3,-6,5,0,-1,0,1,3/5,-M,x,5,8,-3,3,0,0,1,0,8/3,-1,x,3,1,2,-2,1,0,0,0,5-6M,5M,0,-M,0,0,2,x,2,3/5,6/5,1,0,1/5,0,-M,x,5,31/5,3/5,0,0,3/5,1,31/3,-1,x,3,11/5,2/5,0,1,2/5,0,5,0,0,0,0,2,x,2,13,0,1,0,1,2,3,x,1,31/3,1,0,0,1,5/3,-1,x,3,19/3,0,0,1,0,2/3,0,0,0,-5,-25/3,单纯形法的进一步讨论人工变量法,解的判别：,1,）唯一最优解判别：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解。,2,）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。,3,）无界解判别：某个,k,0,且,a,ik,（,i,=1,，,2,m,）则线性规划具有无界解。,4,）无可行解的判断：当用大,M,单纯形法计算得到最优解并且存在,Ri,0,时，则表明原线性规划无可行解。,5,）退化解的判别：存在某个基变量为零的基本可行解。,单纯形法的进一步讨论人工变量法,单纯性法小结,:,建,立,模,型,个 数,取 值,右 端 项,等式或,不等式,极大或极小,新加变量系数,两,个,三个,以上,x,j,0,x,j,无,约束,x,j,0,b,i,0,b,i, m,i,时，企业愿意购进这种资源，单位纯利为,y,i,*,m,i,，则有利可图；如果,y,i,*, m,i,则购进资源,i,，可获单位纯利,y,i,*,m,i,若,y,i,*, m,i,则转让资源,i,，可获单位纯利,m,i,y,i,对偶问题的经济解释影子价格,3,）影子价格在资源利用中的应用,根据对偶理论的互补松弛性定理,:,Y,*,X,s,=0 , Y,s,X,*,=0,表明生产过程中如果某种资源,bi,未得到充分利用时，该种资源的影子价格为,0,；若当资源资源的影子价格不为,0,时，表明该种资源在生产中已耗费完。,对偶问题的经济解释影子价格,4,）影子价格对单纯形表计算的解释,单纯形表中的检验数,其中,c,j,表示第,j,种产品的价格,;,表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。,当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。,对偶单纯形法,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,对偶单纯形法原理,对偶单纯形法基本思路：,找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断,X,B,是否可行（,X,B,为非负），若否，通过变换基解，直到找到原问题基可行解（即,X,B,为非负），这时原问题与对偶问题同时达到可行解，由定理,4,可得最优解。,对偶单纯形法,找出一个,DP,的可行基,LP,是否可行,（,X,B,0,）,保持,DP,为可行解情况下转移到,LP,的另一个基本解,最优解,是,否,循,环,结束,对偶单纯形法,例,2.9,用对偶单纯形法求解：,解,:,（,1,）,将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数,0,（求,max,问题）。,对偶单纯形法,c,j,-9,-12,-15,0,0,0,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,-2,-2,-1,1,0,0,-10,0,x,5,-2,-3,-1,0,1,0,-12,0,x,6,-1,-1,-5,0,0,1,-14,(-9/-1.-12/-1.,-15/-5,),j,-9,-12,-15,0,0,0,0,对偶单纯形法,c,j,-9,-12,-15,0,0,0,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,-9/5,-9/5,0,1,0,-1/5,-36/5,0,x,5,-9/5,-14/5,0,0,1,-1/5,-46/5,-15,x,3,1/5,1/5,1,0,0,-1/5,14/5,(-30/-9,-45/-14,-15/-1),-6,-9,0,0,0,-3,42,c,j,-9,-12,-15,0,0,0,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,-9/14,0,0,1,-9/14,-1/14,-9/7,-12,x,2,9/14,1,0,0,-5/14,1/14,23/7,(,-3/-9,-45/-9,-33/-1),-15,x,3,1/14,0,1,0,1/14,-3/14,15/7,-3/14,0,0,0,-45/14,-33/14,对偶单纯形法,c,j,-9,-12,-15,0,0,0,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,b,-9,x,1,1,0,0,-14/9,1,1/9,2,-12,x,2,0,1,0,1,-1,0,2,-15,x,3,0,0,1,1/9,0,-2/9,2,0,0,0,-1/3,-3,-7/3,原问题的最优解为：,X,*,=,（,2 , 2 , 2 , 0 , 0 , 0,），,Z,*,=72,其对偶问题的最优解为：,Y,*,=,（,1/3 , 3 , 7/3,），,W,*,= 72,对偶单纯形法,对偶单纯形法应注意的问题：,用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解,初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则,最小比值中 的绝对值是使得比值非负，在极小化问题,j,0,，分母,a,ij,0,这时必须取绝对值。在极大化问题中，,j,0,，分母,a,ij,0,， 总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成,这里,j,0,在求,k,时就可以不带绝对值符号。,对偶单纯形法,对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；,普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是,其目的是保证下一个对偶问题的基本解可行,对偶单纯形法在确定出基变量时，若不遵循,规则，任选一个小于零的,b,i,对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。,本章小结,学习要点：,1.,线性规划解的概念以及,3,个基本定理,2.,熟练掌握单纯形法的解题思路及求解步骤,Chapter3,运输规划,( Transportation Problem ),运输规划问题的数学模型,表上作业法,运输问题的应用,本章主要内容：,运输规划问题的数学模型,例,3.1,某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1, B,2, B,3,，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,B1,B2,B3,产量,A1,6,4,6,200,A2,6,5,5,300,销量,150,150,200,运输规划问题的数学模型,解：产销平衡问题：总产量,=,总销量,500,设,x,ij,为从产地,A,i,运往销地,B,j,的运输量，得到下列运输量表：,B1,B2,B3,产量,A1,x,11,x,12,x,13,200,A2,x,21,x,22,x,23,300,销量,150,150,200,Min C = 6,x,11,+ 4,x,12,+ 6,x,13,+ 6,x,21,+ 5,x,22,+ 5,x,23,s.t.,x,11,+,x,12,+,x,13,= 200,x,21,+,x,22,+,x,23,= 300,x,11,+,x,21,= 150,x,12,+,x,22,= 150,x,13,+,x,23,= 200,x,ij, 0 ( i = 1,、,2,；,j = 1,、,2,、,3,）,运输规划问题的数学模型,运输问题的一般形式：产销平衡,A,1,、,A,2,、,、,A,m,表示某物资的,m,个产地；,B,1,、,B,2,、,、,B,n,表示某物质的,n,个销地；,a,i,表示产地,A,i,的产量；,b,j,表示销地,B,j,的销量；,c,ij,表示把物资从产地,A,i,运往销地,B,j,的单位运价。设,x,ij,为从产地,A,i,运往销地,B,j,的运输量，得到下列一般运输量问题的模型：,运输规划问题的数学模型,变化：,1,）有时目标函数求最大。如求利润最大或营业额最大等；,2,）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束,),；,3,）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,定理,:,设有,m,个产地,n,个销地且产销平衡的运输问题，则基变量数为,m,+,n,-1,。,表上作业法,表上作业法是一种求解运输问题的特殊方法，其,实质是单纯形法。,步骤,描述,方法,第一步,求初始基行可行解（初始调运方案）,最小元素法、元素差额法、,第二步,求检验数并判断是否得到最优解当非基变量的检验数,ij,全都非负时得到最优解，若存在检验数,ij,0,，说明还没有达到最优，转第三步。,闭回路法和位势法,第三步,调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步,表上作业法,例,3.2,某运输资料如下表所示：,单位 销地,运价,产地,产量,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,问：应如何调运可使总运输费用最小？,表上作业法,解：第,1,步 求初始方案,方法,1,：最小元素法,基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,表上作业法,总的运输费,(31)+(64) +(43) +(12)+(310)+(35)=86,元,元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。,8,5,10,2,1,20,15,15,15,5,10,总运费是,z,=108+52+151=105,最小元素法：,表上作业法,8,5,10,2,1,20,15,15,5,15,10,总运费,z,=105+152+51=85,后一种方案考虑到,C,11,与,C,21,之间的差额是,8,2=6,，如果不先调运,x,21,，到后来就有可能,x,11,0,，这样会使总运费增加较大，从而先调运,x,21,，再是,x,22,，其次是,x,12,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,表上作业法,方法,2,：,Vogel,法,1,）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,B,1,B,2,B,3,B,4,产量,行差额,A,1,7,7,A,2,4,1,A,3,9,1,销量,3,6,5,6,列差额,2,5,1,3,3,11,3,10,1,9,2,7,4,10,5,8,表上作业法,2,）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。,重复,1),和,2),，直到找出初始解为至。,B,1,B,2,B,3,B,4,产量,行差额,A,1,7,7,A,2,4,1,A,3,9,1,销量,3,6,5,6,列差额,2,5,1,3,3,11,3,10,1,9,2,7,4,10,5,8,5,表上作业法,单位 销地,运价,产地,产量,行差额,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,列差额,7,1,1,3,5,2,1,5,表上作业法,单位 销地,运价,产地,产量,行差额,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,列差额,7,1,3,5,2,7,5,3,表上作业法,单位 销地,运价,产地,产量,行差额,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,列差额,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费,:,(13),(46),(35),(210),(18),(35),85,元,表上作业法,第,2,步 最优解的判别（检验数的求法）,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记,x,ij,的检验数为,ij,由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优,求检验数的方法有两种：,闭回路法,位势法（,）,表上作业法,闭回路的概念,为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表,表上作业法,例下表中闭回路的变量集合是,x,11,x,12,x,42,x,43,x,23,x,25,x,35,x,31,共有,8,个顶点，这,8,个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,B,1,B,2,B,3,B,4,B,5,A,1,X,11,X,12,A,2,X,23,X,25,A,3,X,31,X,35,A,4,X,42,X,43,一条回路中的顶点数一定是偶数，回路遇到顶点必须转,90,度与另一顶点连接，表,3,3,中的变量,x,32,及,x,33,不是闭回路的顶点，只是连线的交点。,表上作业法,闭回路,B,1,B,2,B,3,A,1,X,11,X,12,A,2,A,3,X,32,X,33,A,4,X,41,X,43,例如变量组 不能构成一条闭回路，但,A,中包含有闭回路,变量组 变量数是奇数，显然不是闭回路，也不含有闭回路；,表上作业法,用位势法对初始方案进行最优性检验：,1,）由,ij,=C,ij,-,（,U,i,+V,j,）计算位势,U,i,，,V,j,，因对基变量而言有,ij,=0,，,即,C,ij,-,（,U,i,+V,j,）,= 0,，令,U,1,=0,2,）再由,ij,=C,ij,-,（,U,i,+V