《运筹学建模》PPT课件.ppt

《《运筹学建模》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学建模》PPT课件.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学建模运筹学建模1.线性规划线性规划2.对偶规划和影子价格对偶规划和影子价格3.运输问题运输问题4.整数规划整数规划5.动态规划动态规划运筹学简介运筹学简介1.引言：引言：运运筹筹学学（OperationsResearch）主主要要研研究究系系统统最最优优化化。在在我我国国公公元元前前6世世纪纪孙孙子子兵兵法法中中处处处处体体现现了了军军事事运运筹筹的的思思想想，贾贾思思勰勰的的齐齐民民要要术术一一书书是是一一部部体体现现运运筹筹思思想想、合合理理规规划划农农事事的的宝宝贵贵文献。文献。欧美，在欧美，在20世纪前叶，世纪前叶，1914年提出了军年提出了军事运筹学中的兰彻斯特（事运筹学中的兰

2、彻斯特（Lanchester）战斗方程；战斗方程；1917年排队论的先驱者丹麦年排队论的先驱者丹麦工程师爱尔朗（工程师爱尔朗（Erlang）在哥本哈根电）在哥本哈根电话公司研究电话通信系统时，提出了排话公司研究电话通信系统时，提出了排队论的一些著名公式；队论的一些著名公式；20世纪世纪20年代初年代初提出了存贮论的最优批量公式；提出了存贮论的最优批量公式；20世纪世纪30年代，在商业方面列温逊已经运用运年代，在商业方面列温逊已经运用运筹思想来分析商业广告和顾客心里等；筹思想来分析商业广告和顾客心里等；20世纪世纪30年代末，美英对付德国年代末，美英对付德国，20世纪世纪50年代中期，我国著名的

3、科学家年代中期，我国著名的科学家钱学森、许国志等将运筹学从西方引入钱学森、许国志等将运筹学从西方引入中国中国。运筹学在管理方面的应用运筹学在管理方面的应用生产运作，物资库存管理，物资运输，生产运作，物资库存管理，物资运输，组织人事管理，市场营销，财务管理和组织人事管理，市场营销，财务管理和会计，计算机应用和信息系统开发，城会计，计算机应用和信息系统开发，城市管理等。市管理等。运筹学的来源和组成运筹学的来源和组成运筹学的三个来源：军事、管理和经济。运筹学的三个来源：军事、管理和经济。运筹学的三个组成部分：运用分析理论、运筹学的三个组成部分：运用分析理论、竞争理论和随机服务理论（排队论）竞争理论和

4、随机服务理论（排队论）运筹学分支运筹学分支线性规划是由美国运筹学工作者线性规划是由美国运筹学工作者G.B.Dantzig在在1947年发表的结果，提出年发表的结果，提出单纯形法。列昂杰夫在单纯形法。列昂杰夫在1932年提出了投年提出了投入产出模型；冯入产出模型；冯诺伊曼（诺伊曼（VonNeumman）和）和O.Moogenstern合著合著（1944年）的对策论与经济行为是年）的对策论与经济行为是对策论的奠基作，同时该书已隐约地提对策论的奠基作，同时该书已隐约地提出了对策论与线性规划对偶理论地紧密出了对策论与线性规划对偶理论地紧密联系。联系。运筹学分支运筹学分支运筹学一般包含：线性规划，非线性

5、规运筹学一般包含：线性规划，非线性规划，整数规划，目标规划，动态规划，划，整数规划，目标规划，动态规划，随机规划，模糊规划；随机规划，模糊规划；图论与网络，排队论，存贮论，对策论，图论与网络，排队论，存贮论，对策论，搜索论，维修更新理论，排序与运筹方搜索论，维修更新理论，排序与运筹方法等。法等。运筹学定义运筹学定义（1）为决策机构在对其控制下的业务活动进）为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法行决策时，提供以数量化为基础的科学方法（P.M.Morse和给出的）。和给出的）。（2）运筹学是一门应用科学，它广泛应用现）运筹学是一门应用科学，它广泛应用现有的科学技术

6、知识和数学方法，解决实际中有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提提出的专门问题，为决策者选择最优决策提供定量依据。供定量依据。（3）运筹学是给出问题坏的答案的艺术，否）运筹学是给出问题坏的答案的艺术，否则的话问题的结果会更坏。则的话问题的结果会更坏。运筹学的原则运筹学的原则为为了了有有效效地地应应用用运运筹筹学学，必必须须遵遵循循下下列列六六条原则：条原则：（1）合伙原则）合伙原则（2）催化原则）催化原则（3）互相渗透原则）互相渗透原则（4）独立原则）独立原则（5）宽容原则）宽容原则（6）平衡原则）平衡原则线性规划例线性规划例 引例：某工厂拥有引例：某工厂

7、拥有A、B、C三种类型的设备，三种类型的设备，生产甲、乙两种产品，每种产品在生产中需生产甲、乙两种产品，每种产品在生产中需要占用的设备机时数，每件产品可以获得的要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表利润以及三种设备可利用的机时数如下表产品甲产品甲产品乙产品乙设备能力设备能力（h）设备设备A3265设备设备B2140设备设备C0375利润（元利润（元/件）件）15002500线性规划例线性规划例问：工厂应如何安排生产可获得最大的问：工厂应如何安排生产可获得最大的总利润？总利润？解：设解：设xj为第为第j种（甲、乙）产品的生产种（甲、乙）产品的生产件数件数 j1

8、 1，2 2，则由题意知，问题可转则由题意知，问题可转化为化为线性规划例线性规划例注：注：MaxMax为为MaximizeMaximize求求f的最大值，的最大值，s.t.s.t.为为Subject to to约束，限制，满足于约束，限制，满足于线性规划例线性规划例求解方法一求解方法一：图解法 线性规划例线性规划例求解方法二：单纯形法求解方法二：单纯形法线性规划例线性规划例第一次迭代：第一次迭代：（1 1）取）取x3，x4，x5为基变量，为基变量，x1，x2为非为非基变量基变量，基本可行解为（基本可行解为（0 0，0 0，6565，4040，7575），），f0 0线性规划例线性规划例（2 2

9、）选选择择进进基基变变量量：目目标标函函数数中中非非基基变变量量的的系系数数全全为为负负时时，则则刚刚才才的的基基本本可可行行解解即即为为最最优优解解。若若有有正正的的，选选择择系系数数大的非基变量为进基变量，本例为大的非基变量为进基变量，本例为x2（3 3）出出基基变变量量为为当当进进基基变变量量增增大大时时，首先下降为零的基变量，本例为首先下降为零的基变量，本例为x5线性规划例线性规划例第二次迭代第二次迭代（1 1）取）取x2，x3，x4为基变量，为基变量，x1，x5为非为非基变量基变量，可行解为（可行解为（0 0，2525，1515，1515，0 0），），f6250062500线性规划

10、例线性规划例（2 2）选选择择进进基基变变量量：方方法法同同第第一一次次迭迭代，本例为代，本例为x1 （3 3）出出基基变变量量：方方法法同同第第一一次次迭迭代代，本例为本例为x3线性规划例线性规划例第三次迭代：第三次迭代：（1 1）取）取x1，x2，x4为基变量，为基变量，x3，x5为非为非基变量基变量，可行解为（可行解为（5 5，2525，0 0，5 5，0 0），），f7000070000线性规划例线性规划例2 2）选择进基变量：已无）选择进基变量：已无 ，因此该可行，因此该可行解即为最优解，结束。解即为最优解，结束。线性规划一般模型线性规划一般模型目标函数：目标函数：约束条件：约束条件

11、：称称xj为决策变量，为决策变量，cj为价值系数和费用系数，为价值系数和费用系数，aij为约束系数或技术系数，为约束系数或技术系数，bi为资源系数。为资源系数。线性规划一般模型线性规划一般模型其它形式其它形式线性规划中的一些名词和术语线性规划中的一些名词和术语线性规划模型三要素：线性规划模型三要素：决策变量约束条件目标函数线性规划中的一些名词和术语线性规划中的一些名词和术语可行解可行解满速线性规划全部约束条件满速线性规划全部约束条件的解的解可行域可行域全体可行解的集合全体可行解的集合最优解最优解使得目标函数实现最小值使得目标函数实现最小值（或最大值）的可行解（或最大值）的可行解最优值最优值最优

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

13、。通过逐次迭沿着边界找它邻近的顶点。通过逐次迭代，直至找出最优解。代，直至找出最优解。求线性规划方法软件求线性规划方法软件LINDO软件包首先由软件包首先由LinusSchrage开开发，现在，美国的发，现在，美国的LINDO系统公司系统公司（LINDOSystemInc.）拥有版权，是）拥有版权，是一种专门求解数学规划（优化问题）的一种专门求解数学规划（优化问题）的软件包。它能求解线性规划、（软件包。它能求解线性规划、（0，1）规划、整数规划、二次规划等优化问题，规划、整数规划、二次规划等优化问题，并能同时给出灵敏度分析、影子价格以并能同时给出灵敏度分析、影子价格以及最优解的松弛分析，非常方

14、便实用。及最优解的松弛分析，非常方便实用。与线性规划有关的名字与线性规划有关的名字改进单纯形法改进单纯形法人工变量法（大人工变量法（大M法和两节段法）法和两节段法）对偶问题，对偶理论，对偶单纯形法对偶问题，对偶理论，对偶单纯形法影子价格影子价格灵敏度分析灵敏度分析线性规划有关的问题线性规划有关的问题1.生产计划问题生产计划问题：m种种资资源源B1,B2,Bm，生生产产n种种产产品品A1,A2,An，单单位位产产品所需品所需资资源数源数aij，所得利，所得利润润cj，可，可供供应应的的资资源源总总量量bi，问应问应如何如何组织组织生生产产才能使利才能使利润润最大？最大？2.合理下料问题合理下料问

15、题：一维下料，二维下料，：一维下料，二维下料，三维下料三维下料 线性规划有关的问题线性规划有关的问题3.合理配料问题合理配料问题：m种原料种原料B1,B2,Bm混合混合调调制制n种种产产品品A1,A2,An，产产品的品的规规格要求、格要求、单单位价格，原料供位价格，原料供应应量，原料的价格要求如下，量，原料的价格要求如下，问应问应如何如何组组织织生生产产才能使利才能使利润润最大？最大？线性规划有关的问题线性规划有关的问题4.运输问题运输问题：m m个物资产地个物资产地B1,B2,Bm，n n个物资销地个物资销地A1,A2,An，si为为产地产地Bi产量，产量，d dj为销地为销地Aj的销量，的

16、销量，cij表示把物资从产地表示把物资从产地Bi运到销地运到销地Aj的的单位运价，单位运价，xij表示把物资从产地表示把物资从产地Bi运运到销地到销地Aj的运输量，问应如何运输才的运输量，问应如何运输才能使运费最小？能使运费最小？对偶问题对偶问题引例：引例：某工厂计划在下一生产周期生产某工厂计划在下一生产周期生产3种种产品产品A1,A2,A3，这些产品都要在甲、乙、，这些产品都要在甲、乙、丙、丁丙、丁4种设备上加工，根据设备性能和以种设备上加工，根据设备性能和以往的生产情况知道单位产品的加工工时、往的生产情况知道单位产品的加工工时、各种设备的最大加工工时限制，以及每种各种设备的最大加工工时限制

17、，以及每种产品的单位利润，如下表。问如何安排生产品的单位利润，如下表。问如何安排生产计划，才能使工厂得到最大利润？产计划，才能使工厂得到最大利润？对偶问题对偶问题产产品品设备设备A1A2A3总总工工时时限限制制/h甲甲21370乙乙42280丙丙30115丁丁22050单单位利位利润润/千元千元8102对偶问题对偶问题解：设解：设xj为产品为产品Aj的生产件数的生产件数j1,2,3，则由，则由题意知，问题可转化为如下的线性规划问题题意知，问题可转化为如下的线性规划问题对偶问题对偶问题现在从另一个角度来讨论问题：假设工厂考现在从另一个角度来讨论问题：假设工厂考虑不安排生产，而准备将所有设备出租，

18、收虑不安排生产，而准备将所有设备出租，收取租费。于是需要为每种设备的台时进行估取租费。于是需要为每种设备的台时进行估价。设价。设y1,y2,y3,y4分别表示甲、乙、丙、丁分别表示甲、乙、丙、丁4种设备的台时估价，下面分析约束条件和目种设备的台时估价，下面分析约束条件和目标函数标函数对偶问题对偶问题由上面的表可知，生产一件产品由上面的表可知，生产一件产品A1需要各设需要各设备台时分别为备台时分别为2h，4h，3h，2h，如果将，如果将2h，4h，3h，2h不用于生产产品不用于生产产品A1，而是用于出，而是用于出租，租费应满足（为了不蚀本，租费不能少租，租费应满足（为了不蚀本，租费不能少于利润，

19、否则还不如自己生产产品合算呢！）于利润，否则还不如自己生产产品合算呢！）2 y1+4y2+3 y3+2 y48，依次可分析得线性规划，依次可分析得线性规划模型如下模型如下 对偶问题对偶问题说明：企业为了能够得到租用设备的用户，说明：企业为了能够得到租用设备的用户，使出租设备的计划成交，在价格满足约束条使出租设备的计划成交，在价格满足约束条件下，应将设备价格定得尽可能低件下，应将设备价格定得尽可能低。对偶规划对偶规划原有问题（原有问题（P）对偶问题（对偶问题（D）设设为对偶问题（为对偶问题（D）的最优解，）的最优解，则称则称为原有问题（为原有问题（P）第）第i个约束对应的个约束对应的影子价格影子

20、价格（ShadowPrice）对偶规划影子价格对偶规划影子价格影子价格的经济含义影子价格的经济含义：（：（1）影子价格是对现）影子价格是对现有资源实现最大效益的一种估价。根据上例，有资源实现最大效益的一种估价。根据上例，企业可以根据现有资源的影子价格，对资源企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于的使用有两种考虑：第一，是否将设备用于出租，若租费高于某设备的影子价格，可考出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租；第二，是否虑出租该设备，否则不宜出租；第二，是否将投资用于购买设备，以扩大生产能力，若将投资用于购买设备，以扩大生产能力，若

21、市价低于某设备的影子价格，可考虑买进该市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。设备，否则不宜买进。对偶规划影子价格对偶规划影子价格（2）影子价格表明资源增加对总效益产生的）影子价格表明资源增加对总效益产生的影响。易见有影响。易见有从而，如果从而，如果增加一个单位，目标函数值的增增加一个单位，目标函数值的增量将是量将是，据此，由影子价格的大小可以知，据此，由影子价格的大小可以知道哪种资源的增加可以给企业带来较大的收道哪种资源的增加可以给企业带来较大的收益。益。对偶规划影子价格应用例对偶规划影子价格应用例某外某外贸贸公司准公司准备购进备购进两种两种产产品品A1,A2。购进购进产产

22、品品A1每件需要每件需要10元，占用元，占用5m3的空的空间间，待，待每件每件A1卖卖出后，可出后，可获纯获纯利利润润3元；元；购进产购进产品品A2每件需要每件需要15元，占用元，占用3m3的空的空间间，待每件，待每件A2卖卖出后，可出后，可获纯获纯利利润润4元。公司元。公司现现有有资资金金1400元，有元，有430m3的的仓库仓库空空间间存放存放产产品，如何品，如何安排可以安排可以获获得最大利得最大利润润？对偶规划影子价格应用例对偶规划影子价格应用例现在公司有另外一笔资金现在公司有另外一笔资金585元，准备用于投元，准备用于投资，到底是购买产品呢？还是增加仓库容量资，到底是购买产品呢？还是增

23、加仓库容量？（假设增加？（假设增加1m3的仓库空间需要的仓库空间需要0.8元）元）灵敏度分析灵敏度分析最优解是在参数最优解是在参数cj、bi、aij都固定不变的条件都固定不变的条件下取得的。但是，在实际问题中，对一个具下取得的。但是，在实际问题中，对一个具体的企业来说，参数体的企业来说，参数cj、bi、aij不是固定不变不是固定不变的，或者说得到的这些参数有一定的误差。的，或者说得到的这些参数有一定的误差。如产品的市场价格可能有所变动；国家分配如产品的市场价格可能有所变动；国家分配的原材料可能有所增减；动力供应情况可能的原材料可能有所增减；动力供应情况可能随季审而变化随季审而变化f添置新设备而

24、使生产台时增加；添置新设备而使生产台时增加；由于产品设计结构有所改进，使单位产品的由于产品设计结构有所改进，使单位产品的原材料消耗定额有所增减原材料消耗定额有所增减，灵敏度分析灵敏度分析现实诸因素的种种变化都会引起已建立的数现实诸因素的种种变化都会引起已建立的数学模型的参数变化。或者，当运用线性规划学模型的参数变化。或者，当运用线性规划编制完生产计划并即将付诸应用时，又发生编制完生产计划并即将付诸应用时，又发生了新的情况，某些原来未加限制的资源现在了新的情况，某些原来未加限制的资源现在有了限制，从而出现一个新的追加约束条件。有了限制，从而出现一个新的追加约束条件。或者，企业准备增加新产品，使工

25、厂的生产或者，企业准备增加新产品，使工厂的生产计划发生整个变化。计划发生整个变化。灵敏度分析灵敏度分析从而，我们面临这样的问题：上述种种情况从而，我们面临这样的问题：上述种种情况的发生，将对已求得的最优解产生什么影响的发生，将对已求得的最优解产生什么影响?或者说，我们如何在原有的最优单纯形表的或者说，我们如何在原有的最优单纯形表的基础上用最少的计算量，去获得修改后的线基础上用最少的计算量，去获得修改后的线性规划问题的最优解性规划问题的最优解?这就是我们要讨论的这就是我们要讨论的灵灵敏度分析（敏度分析（SensitivityAnalysis）问题。问题。灵敏度分析灵敏度分析一般分下面一般分下面5

26、个问题来进行灵敏度分析：个问题来进行灵敏度分析：1变量变量xj的目标函数系数的目标函数系数cj在何范围内变动，问题在何范围内变动，问题(LP)的最优基的最优基(最优解最优解)不变不变?如果超出这个范围，如如果超出这个范围，如何求最优解何求最优解?2第第s种资源种资源bs在何范围内变动，最优基不变在何范围内变动，最优基不变?如果如果bs超出这个范围，如何求最优解超出这个范围，如何求最优解?3变量变量xj在矩阵在矩阵A中的系数列向量发生变化，如何求中的系数列向量发生变化，如何求新问题的最优解新问题的最优解?4追加新的约束条件，如何求新的线性规划的最优追加新的约束条件，如何求新的线性规划的最优解解?

27、5增加新的变量增加新的变量xj，如何求新问题的最优解，如何求新问题的最优解?特殊规划运输问题特殊规划运输问题一一般般模模型型：m m个个物物资资产产地地（发发点点）A1,A2,Am，n n个个物物资资销销地地（收收点点）B1,B2,Bn，ai为为发发点点Ai的的物物资资供供应应量量（发发量量），b bj为为收收点点Bj对对物物资资的的需需求求量量（收收量量），cij表表示示把把物物资资从从Ai运运到到Bj的的单单位位运运价价，xij表表示示把把物物资资从从Ai运运到到Bj的的运运输输量量，问问应应如如何何运运输输才才能能使使运运费费最小？（假定收发平衡）最小？（假定收发平衡）特殊规划运输问题特

28、殊规划运输问题AiBjB1BjBnaiA1c11c1jc1na1Aici1cijcinaiAmcm1cmjcmnambjb1bjbn运输收发平衡单位运价表（简称运输表格）运输收发平衡单位运价表（简称运输表格）特殊规划运输问题特殊规划运输问题称称之之为为运运输输问问题题的的标标准准模模型型，此此为为产产销销平平衡衡模模型型，产产销销不不平平衡衡时时，增增加加虚虚拟拟的的收收点点和和发发点点（松松弛弛变变量量）即即可达到产销平衡。可达到产销平衡。特殊规划运输问题特殊规划运输问题求解方法：线性规划的解法也适用运输问题，求解方法：线性规划的解法也适用运输问题，但是针对运输问题的特殊性有其特殊解法但是针

29、对运输问题的特殊性有其特殊解法表上作业法（详见有关书籍）。表上作业法（详见有关书籍）。一些名词：闭回路，孤立点，寻找初始基本一些名词：闭回路，孤立点，寻找初始基本可行解方法（西北角法，最小元素法），计可行解方法（西北角法，最小元素法），计算检验数方法（位势法）算检验数方法（位势法）一般模型有：平衡运输问题，不平衡运输问题，有界一般模型有：平衡运输问题，不平衡运输问题，有界发量运输问题，运量有界的运输问题，转运问题，多发量运输问题，运量有界的运输问题，转运问题，多品种物资运输问题，空车调度问题品种物资运输问题，空车调度问题特殊规划整数规划特殊规划整数规划决决策策变变量量为为整整数数时时的的线线性

30、性规规划划称称为为整整数数规规划划，如：如：去掉整数要求后的最优解为（去掉整数要求后的最优解为（1.5,3.33）是否）是否通过作舍入处理，就可得到最优解？通过作舍入处理，就可得到最优解？特殊规划整数规划特殊规划整数规划我们发现（我们发现（2,3）,（1,3）,（2,4）,（1,4）都不是，其实（都不是，其实（2,2）或（）或（3,1）才是。另一）才是。另一方面，这种舍入的计算量也是相当大的（多方面，这种舍入的计算量也是相当大的（多大？）大？）由此可见，整数规划有其自己独到的一些解由此可见，整数规划有其自己独到的一些解法！割平面法，柯莫力割，柯莫力割平面法法！割平面法，柯莫力割，柯莫力割平面法,分支定界法（隐式枚举法）分支定界法（隐式枚举法）整数规划含纯整数规划（整数规划含纯整数规划（AIP）、混合整数规）、混合整数规划（划（MIP）和）和01规划（规划（BIP）