【培训课件】北京理工大学--运筹学

1运筹学21、绪论2、线性规划3、运输问题4、动态规划5、图与网络分析6、排队论7、教学日历运筹学——目录说明本教学课件是与教材紧密配合使用的，教材为：《运筹学》杨民助编著西安交通大学出版社，2000年6月参考书：《运筹学》清华大学出版社或其他的《运筹学》方面本科教材的相关内容下面所标注的页号，均为本课程教材的页号。例如：p123表示第123页p31-34表示从第31页到第34页3绪论运筹学（OperationalResearch)直译为“运作研究”运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。•运筹学有广泛应用（可以自己找一些参考书看）•运筹学的产生和发展（可以自己找一些参考书看）4运筹学解决问题的过程1）提出问题：认清问题2）寻求可行方案：建模、求解3）确定评估目标及方案的标准或方法、途径4）评估各个方案：解的检验、灵敏性分析等5）选择最优方案：决策6）方案实施：回到实践中7）后评估：考察问题是否得到完满解决1）2）3）：形成问题；4）5）分析问题：定性分析与定量分析。构成决策。5运筹学的分支•线性规划•非线性规划•整数规划•动态规划•多目标规划•随机规划•模糊规划等•图与网络理论•存储论•排队论•决策论•对策论•排序与统筹方法•可靠性理论等6运筹学在工商管理中的应用•生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等•库存管理：多种物资库存量的管理，库存方式、库存量等•运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等•人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等•市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等•财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等***设备维修、更新，项目选择、评价，工程优化设计与管理等7运筹学方法使用情况(美1983)（%）010203040506070统计计算机模拟网络计划线性规划排队论非线性规划动态规划对策论从不使用有时使用经常使用80102030405060708090统计计算机模拟网络计划线性规划排队论非线性规划动态规划对策论从不使用有时使用经常使用运筹学方法在中国使用情况(随机抽样)（%）9运筹学的推广应用前景•据美劳工局1992年统计预测:运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.结论:•运筹学在国内或国外的推广前景是非常广阔的•工商企业对运筹学应用和需求是很大的•在工商企业推广运筹学方面有大量的工作要做10•学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎么做等。•自学时要掌握三个重要环节：1、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好。2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会贯通起来，你做题的正确性自己就有判断。3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来该书所学内容。这样，你才能够从较高的角度来看问题，更深刻的理解有关知识和内容。这就称作“把书读薄”，若能够结合自己参考大量文献后的深入理解，把相关知识从更深入、广泛的角度进行论述，则称之为“把书读厚”•在建数学模型时要结合实际应用，要学会用计算机软件解决问题。如何学习运筹学课程返回目录11各章节的重点、难点及注意事项121、线性规划线性规划模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0**看p7--9例1-1，1-2例1.某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表：问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？甲乙资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元131、线性规划（续1.1）1.1线性规划的概念•线性规划的组成：目标函数Maxf或Minf约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素•一般形式(p10--p11)目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0•标准形式(p11--p15，例1-3)目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0**练习：p68--70习题11-1，1-2141、线性规划（续1.2）1.2线性规划问题解的概念及性质•熟悉下列一些解的概念（p15--16）可行解、可行解集（可行域），最优解、最优值，基、基变量、非基变量，基本解、基本可行解，可行基、最优基。•图解方法及各有关概念的意义（p16--20）看：图解法步骤，例1-4，1-5，1-6，1-7，1-8，1-9下一页是一个图解法解题的一个例子，右图中的阴影部分为可行域。•单纯形法的理论基础（p20--30）1.2.3段要求看懂，了解如何直接通过对约束矩阵的分析求出基本可行解1.2.4,1.2.5两段应注重结论的了解，如单纯形法思想和关于线性规划解的四个定理，而对证明过程则可根据自己的数学基础来掌握：基础很好，可要求掌握；否则，也可略去不看。**习题：p70习题11-3，1-4151、线性规划（续1.2）例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500161、线性规划（续1.3）1.3单纯形法利用单纯形表的方法求解线性规划——重点(p30--451.3.1,1.3.2,1.3.3)此项内容是本章的重点，学习中应注意掌握表格单纯形法求解线性规划问题的基本过程。要通过读懂教材内容以及大量练习来掌握。171、线性规划（续1.3）•表格单纯形法(p40--p45)•考虑：bi0i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0•加入松弛变量：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2…………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，xn，xn+1，…，xn+m≥018显然，xj=0j=1,…,n;xn+i=bii=1,…,m是基本可行解对应的基是单位矩阵。以下是初始单纯形表：mm其中：f=-∑cn+ibij=cj-∑cn+iaij为检验数cn+i=0i=1,…,mi=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,…,m1、线性规划（续1.3）c1…cncn+1…cn+mCBXBx1…xnxn+1…xn+mθicn+1xn+1b1a11…a1na1n+1…a1n+mθ1cn+2xn+2b2a21…a2na2n+1…a2n+mθ2┇┇┇┇┇┇┇┇┇┇cn+mxn+mbmam1…amnamn+1…amn+mθm-zfσ1…σn0…0191、线性规划（续1.3单纯形法解题例）50100000CBXBx1x2x3x4x5θi0x3300111003000x4400210104000x52500(1)001250-z050100*0000x350(1)010-1500x41502001-175100x225001001-z-2500050*000-10050x1501010-10x45000-211100x225001001-z-2750000-500-50例1。化标准形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最优解x1=50x2=250x4=50（松弛标量，表示原料A有50个单位的剩余）20•注意：单纯形法中，1、每一步运算只能用矩阵初等行变换；2、表中第3列的数总应保持非负（≥0）；3、当所有检验数均非正（≤0）时，得到最优单纯形表。1、线性规划（续1.3）211、线性规划（续1.3）•一般情况的处理及注意事项的强调（p45--55）1.3.4段主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例1-14~例1-17掌握这些方法，同时进一步熟悉用单纯形法解题。考虑一般问题：bi0i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0221、线性规划（续1.3）•大M法：引入人工变量xn+i≥0i=1,…,m;充分大正数M。得到，Maxz=c1x1+c2x2+…+cnxn+Mxn+1+…+Mxn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2…………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，xn，xn+1，…，xn+m≥0显然，xj=0j=1,…,n;xn+i=bii=1,…,m是基本可行解对应的基是单位矩阵。•结论：若得到的最优解满足xn+i=0i=1,…,m则是原问题的最优解；否则，原问题无可行解。231、线性规划（续1.3）•两阶段法：引入人工变量xn+i≥0，i=1,…,m；构造，Maxz=-xn+1-xn+2-…-xn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2…………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，xn，xn+1，…，xn+m≥0•第一阶段求解上述问题：显然，xj=0j=1,…,n;xn+i=bii=1,…,m是基本可行解对应的基是单位矩阵。•结论：若得到的最优解满足xn+i=0i=1,…,m则是原问题的基本可行解；否则，原问题无可行解。•得到原问题的基本可行解后，第二阶段求解原问题。241、线性规划（续1.3）例题例：（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0•大M法问题（LP-M）Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0•两阶段法：第一阶段问题（LP-1）Ma