第一章 线性规划及单纯形法(1-4).ppt

第一章?线性规划及单纯形法 “夫运筹帷幄之中，决胜千里之外” 《史记.高祖本纪》 运筹学起源之一 ——军事 古代军事运筹学思想 “孙子兵法” （1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家）；中国古代运筹学思想的例子还有：田忌赛马、围魏救赵等等。 国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。 鲍德西（Bawdsey）雷达站的研究 　1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“Operational??Research”，即“运筹学”。 (OR) 大西洋反潜战 研究如何打破德国对英吉利海峡的海上封锁 运筹学起源之二 ——管理 泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等 爱尔朗（Erlong）的排队论公式 　1909－1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支－－排队论。 运筹学起源之三  ——经济（数理经济学） Von Neumann （冯·诺依曼 ）与对策论 1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern（摩根斯顿 ）共著的《对策论与经济行为》开创了对策论分支。 康托洛维奇与“生产组织与计划中的数学方法” 30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作－－《生产组织与计划中的数学方法》，其思想和模型被归入线性规划范畴。 诺贝尔经济学奖从1969年首发至今的获奖者中就有多位是运筹学家。 ??1975年诺贝尔经济学奖授给了库普曼和康脱罗维奇，以表彰首先将线性规划与经济问题相联系而做出的贡献； ??1994年诺贝尔经济学奖授给了三位博弈论专家：纳什、泽尔腾、海萨尼。博弈论已经成为当代经济学的基石。 ??2005年以色列经济学家罗伯特-奥曼和美国经济学家托马斯-斯切林，因“通过博弈论分析加强了我们对冲突和合作的理解”所作出的贡献而获奖。 我国运筹学的发展 50年代中期由钱学森等由西方引入，1957年正式定名为运筹学。1970年后，在华罗庚教授的直接指导下，在全国范围内推广统筹法和优选法，并取得了卓著成效，同时也使运筹学的研究队伍迅速壮大。随后，中国运筹学会于1980年成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）。 运筹学在科学技术体系中的地位 运筹学的主要分支 运筹学研究的基本步骤 引例： 在生产管理和经营活动中经常需要解决： 如何合理地利用有限的资源，以得到 最大的效益。 线性规划（Linear Programming，LP） 解决有限资源的最佳分配问题 求解方法： 图解法 单纯形法 第一章?线性规划及单纯形法 §1 线性规划问题及其数学模型 §2 线性规划问题的图解法 §3 线性规划问题解的基本性质 §4 单纯形法的基本原理 §5 单纯形法的计算步骤 §6 单纯形法的进一步讨论 §7 线性规划应用举例 第一章 习题 本章学习要求 1．了解一般线性规划问题的数学模型。 2．掌握线性规划问题的图解法。 3．理解单纯形法基本原理。 4．掌握单纯形法的计算步骤。 5．能够将实际问题抽象为数学模型。 重点和难点：图解法、单纯形法、 单纯形法的原理及计算步骤 §1 线性规划问题及其数学模型 一、线性规划问题的提出 线性规划模型的三要素 1.决策变量：需决策的量，即待求的未知数；决策变量的取值要求非负。 2.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。 LP的约束条件，都是决策变量的线性函数。 3.目标函数：需优化的量，即欲达的目标，用决策变量的线性表达式表示；