《运筹学建模》PPT课件

《《运筹学建模》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学建模1.线性规划2.对偶规划和影子价格3.运输问题4.整数规划5.动态规划运筹学简介1.引言：运筹学（OperationsResearch）主要研究系统最优化。在我国公元前6世纪《孙子兵法》中处处体现了军事运筹的思想，贾思勰的《齐民要术》一书是一部体现运筹思想、合理规划农事的宝贵文献。欧美，在20世纪前叶，1914年提出了军事运筹学中的兰彻斯特（Lanchester）战斗方程；1917年排队论的先驱者丹麦工程师爱尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式；20世纪2

2、0年代初提出了存贮论的最优批量公式；20世纪30年代，在商业方面列温逊已经运用运筹思想来分析商业广告和顾客心里等；20世纪30年代末，美英对付德国……，20世纪50年代中期，我国著名的科学家钱学森、许国志等将运筹学从西方引入中国……。运筹学在管理方面的应用生产运作，物资库存管理，物资运输，组织人事管理，市场营销，财务管理和会计，计算机应用和信息系统开发，城市管理等。运筹学的来源和组成运筹学的三个来源：军事、管理和经济。运筹学的三个组成部分：运用分析理论、竞争理论和随机服务理论（排队论）运筹学分支线性规划是由美国运

3、筹学工作者G.B.Dantzig在1947年发表的结果，提出单纯形法。列昂杰夫在1932年提出了投入产出模型；冯·诺伊曼（VonNeumman）和O.Moogenstern合著（1944年）的《对策论与经济行为》是对策论的奠基作，同时该书已隐约地提出了对策论与线性规划对偶理论地紧密联系。运筹学分支运筹学一般包含：线性规划，非线性规划，整数规划，目标规划，动态规划，随机规划，模糊规划；图论与网络，排队论，存贮论，对策论，搜索论，维修更新理论，排序与运筹方法等。运筹学定义（1）为决策机构在对其控制下的业务活动进行决策

4、时，提供以数量化为基础的科学方法（P.M.Morse和G.E.Kimball给出的）。（2）运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。（3）运筹学是给出问题坏的答案的艺术，否则的话问题的结果会更坏。运筹学的原则为了有效地应用运筹学，必须遵循下列六条原则：（1）合伙原则（2）催化原则（3）互相渗透原则（4）独立原则（5）宽容原则（6）平衡原则线性规划例引例：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品，每种产品在生产中需要占用

5、的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500线性规划例问：工厂应如何安排生产可获得最大的总利润？解：设xj为第j种（甲、乙）产品的生产件数j＝1，2，则由题意知，问题可转化为线性规划例注：Max为Maximize求f的最大值，s.t.为Subjectto约束，限制，满足于线性规划例求解方法一：图解法线性规划例求解方法二：单纯形法线性规划例第一次迭代：（1）取x3，x4，x5为基变量，x1，x2

6、为非基变量，基本可行解为（0，0，65，40，75），f＝0线性规划例（2）选择进基变量：目标函数中非基变量的系数全为负时，则刚才的基本可行解即为最优解。若有正的，选择系数大的非基变量为进基变量，本例为x2（3）出基变量为当进基变量增大时，首先下降为零的基变量，本例为x5线性规划例第二次迭代（1）取x2，x3，x4为基变量，x1，x5为非基变量，可行解为（0，25，15，15，0），f＝62500线性规划例（2）选择进基变量：方法同第一次迭代，本例为x1（3）出基变量：方法同第一次迭代，本例为x3线性规划例第三次

7、迭代：（1）取x1，x2，x4为基变量，x3，x5为非基变量，可行解为（5，25，0，5，0），f＝70000线性规划例2）选择进基变量：已无，因此该可行解即为最优解，结束。线性规划一般模型目标函数：约束条件：称xj为决策变量，cj为价值系数和费用系数，aij为约束系数或技术系数，bi为资源系数。线性规划一般模型其它形式线性规划中的一些名词和术语线性规划模型三要素：决策变量约束条件目标函数线性规划中的一些名词和术语可行解——满速线性规划全部约束条件的解可行域——全体可行解的集合最优解——使得目标函数实现最小值（或

8、最大值）的可行解最优值——最优解的目标函数值线性规划模型标准型LP求线性规划方法－单纯形法G.B.Danting在1947年提出了求解线性规划问题的方法——单纯形法(simplexmethod)，其原理是：如果（LP）的可行域K不是空集，我们从K的某一顶点X0出发，判别它是否为最优解？若不是，沿着边界找它邻近的另一个顶点，它应比原来的顶点优，看它是否为最优解？若不是，再沿