运筹学PPT完整版

运筹学(OperationsResearch)工商管理核心课程董君成塔里木大学经济与管理学院[e-mail]运筹帷幄之中决胜千里之外绪论Introduction第一章绪论（1）运筹学简述（2）运筹学的主要内容（3）本课程的教材及参考书（4）本课程的特点和要求（5）本课程授课方式与考核（6）运筹学在经济管理中的应用本章主要内容：绪论绪论运筹学简述运筹学（OperationsResearch,简写OR）系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。绪论运筹学的历史与发展“运筹学思想的出现可以追溯到很早—“田忌赛马”。齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王上中下田忌下上中绪论丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。绪论国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。运筹学简述“运作研究(OperationalResearch)小组”:解决复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。绪论在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作《生产组织与计划中的数学方法》。但当时并没有引起重视，直到1960年康特洛为奇再次出版了《最佳资源利用的经济计算》，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。线性规划提出后很快受到经济学家的重视，如：二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。绪论20世纪50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。绪论成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势运筹学的主要内容数学规划（线性规划、整数规划、目标规划、动态规划等）图论存储论排队论对策论排序与统筹方法决策分析运筹学的主要内容1.线性规划（LinearProgram）是一个成熟的分支，它有效的算法——单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。2.整数规划(IntegrateProgram)：在线性规划的基础上，变量加上整数约束。3.非线性规划(NonlinearProgram)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。4.动态规划(DynamicProgram)：多阶段决策问题。是美国贝尔曼于1951年提出的。运筹学的主要内容5、图与网络(GraphTheoryandNetwork)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。6、存储论（InventoryTheory)：主要解决生产中的库存问题，订货周期和订货量等问题。7、排队论(QueueTheory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。8、对策论(GameTheory)：主要研究具有斗争性质的优化问题。9、决策分析(DecisionAnalysis)：主要研究定量化决策。本课程的教材及参考书选用教材《运筹学教程》胡运权主编（第3版）清华出版社参考教材《运筹学基础及应用》胡运权主编哈工大出版社《管理运筹学》韩伯棠主编（第2版）高等教育出版社《运筹学》(修订版)钱颂迪主编清华出版社本课程的特点和要求先修课：高等数学，基础概率、线性代数特点：系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：真实系统系统分析问题描述模型建立与修改模型求解与检验结果分析与实施数据准备本课程授课方式与考核学科总成绩平时成绩（30％）课堂考勤（40％）平时作业（60％）期末成绩（70％）讲授为主，结合习题作业运筹学在经济管理中的应用运筹学在经济管理中的应用涉及的方面：1.生产计划2.运输问题3.人事管理4.库存管理5.市场营销6.财务和会计7.物流配送另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。“管理运筹学”软件介绍“管理运筹学”2.0版包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。运筹帷幄之中决胜千里之外线性规划及单纯形法LinearProgramming第一章Chapter1线性规划(LinearProgramming)LP的数学模型图解法单纯形法单纯形法的进一步讨论－人工变量法LP模型的应用本章主要内容：线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）线性规划问题的数学模型例1.1如图所示，如何截取x使铁皮所围成的容积最大？xaxxav220dxdv0)2()2()2(22xaxxa6ax线性规划问题的数学模型例1.2某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润项目ⅠⅡ每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21问：应如何安排生产计划，才能使总利润最大？解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总利润为z，则有：maxz=2x1+x23.约束条件：5x2≤156x1+2x2≤24x1+x2≤5x1，x2≥0线性规划问题的数学模型例1.3已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。设备产品ABCD利润（元）Ⅰ21402Ⅱ22043有效台时1281612解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总利润为z，则有：maxz=2x1+x23.约束条件：x1≥0,x2≥02x1+2x2≤12x1+2x2≤84x1≤164x2≤12线性规划问题的数学模型例1.4某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用量分别为：x1、x2、x3、x42.目标函数：设总成本为zminz=5x1+6x2+7x3+8x43.约束条件：x1+2x2+x3+x4≥1602x1+4x3+2x4＝2003x1＋x2+x3+2x4≤180x1、x2、x3、x4≥0例1.5某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：航线号船队类型编队形式货运成本（千元／队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型解：设：xj为第j号类型船队的队数（j=1，2，3，4），z为总货运成本则：minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2＝20040x3+20x4＝400xj≥0（j=1,2,3,4）线性规划问题的数学模型线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？线性规划问题的数学模型3.建模条件(1)优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；(2)限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；(3)选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。线性规划问题的数学模型4.建模步骤(1)确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量；(2)找出所有限定条件：即决策变量受到的所有的约束；(3)写出目标函数：即问题所要达到的目标，并明确是max还是min。线性规划问题的数学模型00)()((min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数：约束条件：5.线性规划数学模型的一般形式)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj简写为：线性规划问题的数学模型向量形式：)(21ncccCnxxX1mjjjaaP1mbbB10)((min)maxXBxpCXzjj其中：线性规划问题的数学模型矩阵形式：mnmnaaaaA11110)((min)maxXBAXCXZ其中：)(21ncccCnxxX1mbbB1线性规划问题的数学模型6.线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,,2,1,,2,1,0.max11特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。线性规划问题的数学模型（2）如何化标准形式目标函数的转换如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。jjx