6运筹学建模.ppt

运筹学建模 1.线性规划 2.对偶规划和影子价格 3.运输问题 4.整数规划 5.动态规划 运筹学简介 1.引言： 运筹学（Operations Research）主要研究系统最优化。在我国公元前6世纪《孙子兵法》中处处体现了军事运筹的思想，贾思勰的《齐民要术》一书是一部体现运筹思想、合理规划农事的宝贵文献。 欧美，在20世纪前叶，1914年提出了军事运筹学中的兰彻斯特（Lanchester）战斗方程；1917年排队论的先驱者丹麦工程师爱尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式；20世纪20年代初提出了存贮论的最优批量公式；20世纪30年代，在商业方面列温逊已经运用运筹思想来分析商业广告和顾客心里等；20世纪30年代末，美英对付德国……，20世纪50年代中期，我国著名的科学家钱学森、许国志等将运筹学从西方引入中国……。 运筹学在管理方面的应用 生产运作，物资库存管理，物资运输，组织人事管理，市场营销，财务管理和会计，计算机应用和信息系统开发，城市管理等。 运筹学的来源和组成 运筹学的三个来源：军事、管理和经济。 运筹学的三个组成部分：运用分析理论、竞争理论和随机服务理论（排队论） 运筹学分支 线性规划是由美国运筹学工作者G.B.Dantzig在1947年发表的结果，提出单纯形法。列昂杰夫在1932年提出了投入产出模型；冯·诺伊曼（Von Neumman）和O.Moogenstern合著（1944年）的《对策论与经济行为》是对策论的奠基作，同时该书已隐约地提出了对策论与线性规划对偶理论地紧密联系。 运筹学分支 运筹学一般包含：线性规划，非线性规划，整数规划，目标规划，动态规划，随机规划，模糊规划； 图论与网络，排队论，存贮论，对策论，有哪些信誉好的足球投注网站论，维修更新理论，排序与运筹方法等。 运筹学定义 （1）为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法（P.M.Morse 和G.E.Kimball给出的）。 （2）运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。 （3）运筹学是给出问题坏的答案的艺术，否则的话问题的结果会更坏。 运筹学的原则 为了有效地应用运筹学，必须遵循下列六条原则： （1）合伙原则 （2）催化原则 （3）互相渗透原则 （4）独立原则 （5）宽容原则 （6）平衡原则 线性规划例 引例：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品，每种产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表 线性规划例 问：工厂应如何安排生产可获得最大的总利润？ 线性规划例 注：Max为Maximize求f的最大值，s.t.为Subject to约束，限制，满足于 线性规划例 求解方法一：图解法 线性规划例 求解方法二：单纯形法 线性规划例 第一次迭代： 线性规划例 （2）选择进基变量：目标函数中非基变量的系数全为负时，则刚才的基本可行解即为最优解。若有正的，选择系数大的非基变量为进基变量，本例为x2 （3）出基变量为当进基变量增大时，首先下降为零的基变量，本例为x5 线性规划例 第二次迭代 线性规划例 （2）选择进基变量：方法同第一次迭代，本例为x1 （3）出基变量：方法同第一次迭代，本例为x3 线性规划例 第三次迭代： 线性规划例 2）选择进基变量：已无 ，因此该可行解即为最优解，结束。 线性规划一般模型 目标函数： 约束条件： 线性规划一般模型 其它形式 线性规划中的一些名词和术语 线性规划模型三要素： 决策变量 约束条件 目标函数 线性规划中的一些名词和术语 可行解——满速线性规划全部约束条件的解 可行域——全体可行解的集合 最优解——使得目标函数实现最小值（或最大值）的可行解 最优值——最优解的目标函数值 线性规划模型标准型 LP 求线性规划方法－单纯形法 G.B.Danting在1947年提出了求解线性规划问题的方法——单纯形法(simplex method)，其原理是：如果（LP）的可行域K不是空集，我们从K的某一顶点X0出发，判别它是否为最优解？若不是，沿着边界找它邻近的另一个顶点，它应比原来的顶点优，看它是否为最优解？若不是，再沿着边界找它邻近的顶点。通过逐次迭代，直至找出最优解。 求线性规划方法－软件 LINDO软件包首先由Linus Schrage开发，现在，美国的LINDO系统公司（LINDO System Inc.）拥有版权，是一种专门求解数学规划（优化问题）的软件包。它能求解线性规划、（0，1）规划、整数规划、二次规划等优化问题，并能同时给出灵敏度分析、影子