MBA学位课程-运筹学1(1)

1运筹学(OperationResearch)MBA学位课程衷心希望本课程能让大家受益2教师介绍姓名：刘满凤职称：副教授博士单位：信息管理学院电话：3816922（O）3816926（H)E-mail:[e-mail]课程考核评分方法平时成绩分占40%其中课堂讨论5%平时作业5%大作业30%课程考试分占60%授课计划总时数：48课时授课时数：46课时其中课堂授课42课时，上机授课4课时案例讨论：2课时3课程内容简介与学习要求•课程内容简介运筹学是一门应用性学科，它主要是应用定性分析和定量分析相结合的方法，通过建立实际问题的数学模型，应用合适的优化算法对模型进行求解，从而解决实际问题。其主要内容有：线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队论、存贮论、对策论、决策论、多目标规划等。本课程选取了运筹学在经济管理领域中常用的五个部分作为教学内容，即：线性规划、整数规划、动态规划、图与网络分析、对策论。•学习要求本课程将通过重点讲授原理方法、上机解题、个人研究与小组讨论相结合的案例分析等环节，培养学员全局优化的思想，使学员掌握若干类常用的运筹学模型，并能用其解决经济管理中的复杂问题。因此要求学员：对布置的思考、案例讨论题进行认真准备，按进度完成平时作业和上机练习，按要求完成大作业书面报告。•参考资料（1）刘满凤、付波、聂高飞编著《运筹学模型与方法教程例题分析与题解》，清华大学出版社，2001年。（2）《运筹学》教材编写组编《运筹学》（修订版），清华大学出版社，1996年。（3）蓝伯雄、程佳惠、陈秉正编著《管理数学（下）——运筹学》，清华大学出版社，1998年。（4）中山、四川、西北、武汉、湘潭大学编《运筹学——经济管理决策方法》，四川大学出版社，1995年。（5）韩大卫编著《管理运筹学》，大连理工大学出版社，1998年。（6）胡运权主编《运筹学习题集》（修订版），清华大学出版社，1985年。4本课程内容安派：第一部分线性规划及其应用1、问题的数学模型与求解2、单纯形法与计算机求解3、对偶理论与灵敏度分析4、运输问题及其解法5、指派问题及其解法6、整数线性规划问题及其解法第二部分动态规划1、动态规划的基本概念和最优化原理2、动态规划模型的建立和求解方法3、建模训练与求解第三部分对策论模型第四部分图与网络分析1、两人有限零和对策模型及其解法2、两人有限非零和对策1、图与网络的基本概念2、树与最小树3、最短路问题4、最大流问题5、最小费用最大流问题5绪论一、运筹学的历史与发展国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。6二次世界大战时期，德国空军对英伦三岛狂轰滥炸，为对付敌人的空袭，英国人使用了雷达，但没有科学的布局，防空系统的效率并不很高，为解决这个问题，英国军方于1939年9月从全国各地调来一批科学家，共11人，他们中有将军1人、数学家2人、理论物理学家2人、应用物理学家1人、天体物理学家1人、测量学家1人、生物学家3人，来到英国皇家空军指挥部，组成了以著名的物理学家、诺贝尔奖金获得者P.M.S.Blacket为核心的世界上第一个运筹学小组，他们的任务就是应用系统论的观点，统筹规划的方法研究作战问题，这个运筹学小组在作战中发挥了卓越的作用，受到英国政府极大的重视。7于是，英国政府逐渐在它的海陆空三军中都成立了运筹学小组，美国参战以后，也仿效英国在军队中成立了运筹学小组。在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作《生产组织与计划中的数学方法》。但当时并没有引起重视，直到1960年康特洛为奇再次出版了《最佳资源利用的经济计算》，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。。线性规划提出后很快受到经济学家的重视，如二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。850年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。9二、运筹学的基本内容1、线性规划（LinearProgram）是一个成熟的分支，它有效的算法——单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。2、整数规划(IntegrateProgram)：在线性规划的基础上，变量加上整数约束3、非线性规划(NonlinearProgram)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。4、动态规划(DynamicProgram):多阶段决策问题。是美国贝尔曼于1951年提出的。5、图与网络(GraphTheoryandNetwork)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。106、存储模型（InventoryTheory)：主要解决生产中的库存问题，订货周期和订货量等问题。7、排队论(QueueTheory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。8、对策论(GameTheory)：主要研究具有斗争性质的优化问题。9、决策分析(DecisionAnalysis)：主要研究定量化决策三、运筹学的工作步骤1、明确目标、收集资料、提出问题2、建立模型3、模型求解与检验4、结果分析与实施11第一部分线性规划及其应用•线性规划研究的主要内容线性规划主要解决两个方面的问题：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？•线性规划内容框架12LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提出基本最优解基本方法图解法原始单纯形法单纯形法大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析──参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*13§1LP问题及其数学模型（一）引例1（生产计划问题）某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？ⅠⅡ资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23该问题可用一句话来描述，即在资源有限的条件下，求使利润最大的生产计划方案。第一章LP问题的数学模型与求解14解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：机器设备的限制条件:x1+2x2≤8原材料A的限制条件：4x1≤16（称为资源约束条件）原材料B的限制条件：4x2≤12同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有x1≥0，x2≥0（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数Z=2x1+3x2的值达到最大。15综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x1+3x20x,x12x416x48x2x.t.s212121例2.（营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能使在满足营养的前提下使购买食品的总费用最小？16序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10x1+6x2+3x3+2x4)4,3,2,1j(0x800x500x300x200x40055x10x20x60x503000x200x900x800x1000t.sj43214321432117例3运输问题（课本P6）某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？销地单位运价产地B1B2B3B4产量A15610360A2419740A3423860销量3050404018解:（1）确定决策变量：设xij(i=1,2,3;j=1,2,3,4)为从产地i运到销地j的运量xcij31i41jij（2）确定目标函数：总运费最小minz=（3）确定约束条件：x11+x12+x13+x14=60产量约束：x21+x22+x23+x24=40x31+x32+x33+x34=60x11+x21+x31=30销量约束：x12+x22+x32=50x13+x23+x33=40x14+x24+x34=4019非负约束xij≧0由此模型总结为：)4,3,2,1j;3,2,1i(040405030604060.t.sZminxxxxxxxxxxxxxxxxxxxxxxxxxXCij34241433231332221231211134333231242322211413121131i41jijij20（二）LP问题的模型上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。（1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。21满足以上三个条件的数学模型称为LP问题的数学模型，其一般形式为：max(或min)z=c1x1+c2x2+…+cnxn0,,,),(),(),(.2122212222222111212211nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats（1.1)（1.2)（1.3)或紧缩形式max(或min)z=njjjxc10),...,2,1(),(.1jnjijjxmibxats22或矩阵形式或向量形式：max(或min)z=cx),...,2,1(0),(.1njXbxptsjnjjj其中c=(c1,c2,…,cn)，称为价值系数向量；aaaaaaaaamn2m1mn22221