第一章 线性规划及单纯形法（1-4）

管理运筹学 牧云志 WELCOME TO Management Operations Research 1第一章 线性规划及单纯形法 管理运筹学 绪论“ 夫运筹帷幄之中，决胜千里之外 ” 史记 .高祖本纪 2第一章 线性规划及单纯形法运筹学起源之一 军事 古代军事运筹学思想 “ 孙子兵法 ” （ 1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家）；中国古代运筹学思想的例子还有：田忌赛马、围魏救赵等等。 国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特 （ Lanchester） 提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。3第一章 线性规划及单纯形法 鲍德西（ Bawdsey） 雷达站的研究1939年， 以 Blackett为首的一个研究小组（代号 “Blackett 马戏团 ”），研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。 “Blackett马戏团 ”在秘密报告中使用了 “Operational Research”，即 “运筹学 ”。 (OR) 大西洋反潜战研究如何打破德国对英吉利海峡的海上封锁运筹学的正式产生：第二次世界大战4第一章 线性规划及单纯形法运筹学起源之二 管理 泰勒 的时间动作研究、甘特的用于生产计划与控制的 “甘特图 ”、 吉尔布雷思夫妇的动作研究等 爱尔朗 （ Erlong） 的排队论公式1909 1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是 1909年的论文 “概率与电话通话理论 ”，开创了运筹学的重要分支排队论。5第一章 线性规划及单纯形法运筹学起源之三 经济（数理经济学）Von Neumann （冯 诺依曼 ）与对策论 1932年， Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型； 1944年，与 Morgenstern（摩根斯顿 ）共著的 对策论与经济行为 开创了对策论分支。康托洛维奇与 “生产组织与计划中的数学方法 ” 30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作 生产组织与计划中的数学方法 ，其思想和模型被归入线性规划范畴。6第一章 线性规划及单纯形法诺贝尔经济学奖从 1969年首发至今的获奖者中就有多位是运筹学家。 1975年诺贝尔经济学奖授给了 库普曼 和 康脱罗维奇 ，以表彰首先将线性规划与经济问题相联系而做出的贡献； 1994年诺贝尔经济学奖授给了三位博弈论专家： 纳什 、泽尔腾 、 海萨尼 。博弈论已经成为当代经济学的基石。 2005年以色列经济学家 罗伯特 -奥曼 和美国经济学家 托马斯 -斯切林 ，因 “通过博弈论分析加强了我们对冲突和合作的理解 ”所作出的贡献而获奖。7第一章 线性规划及单纯形法我国运筹学的发展50年代中期由 钱学森 等由西方引入， 1957年正式定名为运筹学。 1970年后，在 华罗庚 教授的直接指导下，在全国范围内推广统筹法和优选法，并取得了卓著成效，同时也使运筹学的研究队伍迅速壮大。随后， 中国运筹学会 于 1980年成立， 1982年作为正式成员加入了国际运筹学联合会（ IFORS）。8第一章 线性规划及单纯形法运筹学在科学技术体系中的地位9第一章 线性规划及单纯形法运筹学的主要分支排队论 （ Queuing Theory）决策论 （ Decision Theory）对策论 （ Game Theory）存贮论 （ Inventory Theory）线性规划 （ Linear Programming）非线性规划 （ Nonlinear Programming）动态规划 （ Dynamic Programming）图论与网络分析 （ Graph Theory and Network Analysis）生产结构优化投资组合优化资源分配优化工程计划优化服务系统优化军事活动机会选择订货库存管理10第一章 线性规划及单纯形法运筹学研究的基本步骤分析和表述问题建立模型求解模型优化方案解的检验模型修正 解的实施解的控制11第一章 线性规划及单纯形法引例：12第一章 线性规划及单纯形法在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益 。13第一章 线性规划及单纯形法第一章 线性规划及单纯形法14第一章 线性规划及单纯形法线性规划 （ Linear Programming， LP）解决有限资源的最佳分配问题求解方法： 图解法 单纯形法 15第一章 线性规划及单纯形法第一章 线性规划及单纯形法 1 线性规划问题及其数学模型 2 线性规划问题的图解法 3 线性规划问题解的基本性质 4 单纯形法的基本原理 5 单纯形法的计算步骤 6 单纯形法的进一步讨论 7 线性规划应用举例 第一章 习题16第一章 线性规划及单纯形法本章学习要求 1了解一般线性规划问题的数学模型。 2掌握线性规划问题的图解法。 3理解单纯形法基本原理。 4掌握单纯形法的计算步骤。 5能够将实际问题抽象为数学模型。 重点和难点 ：图解法、单纯形法、单纯形法的原理及计算步骤17第一章 线性规划及单纯形法1 线性规划问题及其数学模型一、线性规划问题的提出例 1.1 资源合理利用问题某厂生产甲、乙两种产品，要消耗 A、 B、 C三种资源，已知每件产品对三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润见下表：如何安排生产计划，使总利润最大（列出数学模型）产 品资 源甲 乙 资 源限制A 3 2 65B 2 1 40C 0 3 75单 件利润1500 250018第一章 线性规划及单纯形法线性规划模型的三要素1.决策变量： 需决策的量，即待求的未知数；决策变量的取值要求非负。2.约束条件： 为实现优化目标需受到的限制，用决策变量的等式或不等式表示。LP的约束条件，都是决策变量的线性函数。 3.目标函数： 需优化的量，即欲达的目标，用决策变量的线性表达式表示；有的目标要实现极大，有的则要求极小。19第一章 线性规划及单纯形法(1)决策变量要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设 x1为甲产品产量， x2为乙产品产量。 (2)约束条件生产这两种产品受到现有资源的制约。 例 1.1 解：资源 A的限制：资源 B的限制：资源 C的限制：非负约束：(3)目标函数目标是利润最大化，用 z表示利润，即求 的最大值。综上所述，该问题的数学模型可表示为：20第一章 线性规划及单纯形法 模仿例 1.1的解题步骤： 引例 （列出数学模型）21第一章 线性规划及单纯形法引例的数学模型：22第一章 线性规划及单纯形法1 线性规划问题及其数学模型一、线性规划问题的提出原料化学成分 甲 乙产 品成分最低含量A 12 3 4B 2 3 2C 3 15 5单 位成本 3 2例 1.2 配料问题（ P.2）23第一章 线性规划及单纯形法1 线性规划问题及其数学模型一、线性规划问题的提出例 1.3 运输问题 (P.2)销 地产 地 B1 B2 B3 B4 产 量（ t）A1 21 25 7 15 2000A2 51 51 37 15 1100需求量（ t） 1700 1100 200 100总产量 =总需求量（产销平衡）24第一章 线性规划及单纯形法25第一章 线性规划及单纯形法练习26第一章 线性规划及单纯形法27第一章 线性规划及单纯形法1 线性规划问题及其数学模型二、线