6运筹学建模

运筹学建模1.线性规划2.对偶规划和影子价格3.运输问题4.整数规划5.动态规划运筹学简介•1.引言：运筹学（OperationsResearch）主要研究系统最优化。在我国公元前6世纪《孙子兵法》中处处体现了军事运筹的思想，贾思勰的《齐民要术》一书是一部体现运筹思想、合理规划农事的宝贵文献。欧美，在20世纪前叶，1914年提出了军事运筹学中的兰彻斯特（Lanchester）战斗方程；1917年排队论的先驱者丹麦工程师爱尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式；20世纪20年代初提出了存贮论的最优批量公式；20世纪30年代，在商业方面列温逊已经运用运筹思想来分析商业广告和顾客心里等；20世纪30年代末，美英对付德国……，20世纪50年代中期，我国著名的科学家钱学森、许国志等将运筹学从西方引入中国……。运筹学在管理方面的应用•生产运作，物资库存管理，物资运输，组织人事管理，市场营销，财务管理和会计，计算机应用和信息系统开发，城市管理等。运筹学的来源和组成•运筹学的三个来源：军事、管理和经济。•运筹学的三个组成部分：运用分析理论、竞争理论和随机服务理论（排队论）运筹学分支线性规划是由美国运筹学工作者G.B.Dantzig在1947年发表的结果，提出单纯形法。列昂杰夫在1932年提出了投入产出模型；冯·诺伊曼（VonNeumman）和O.Moogenstern合著（1944年）的《对策论与经济行为》是对策论的奠基作，同时该书已隐约地提出了对策论与线性规划对偶理论地紧密联系。运筹学分支•运筹学一般包含：线性规划，非线性规划，整数规划，目标规划，动态规划，随机规划，模糊规划；•图论与网络，排队论，存贮论，对策论，搜索论，维修更新理论，排序与运筹方法等。运筹学定义•（1）为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法（P.M.Morse和G.E.Kimball给出的）。•（2）运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。•（3）运筹学是给出问题坏的答案的艺术，否则的话问题的结果会更坏。运筹学的原则为了有效地应用运筹学，必须遵循下列六条原则：（1）合伙原则（2）催化原则（3）互相渗透原则（4）独立原则（5）宽容原则（6）平衡原则线性规划例引例：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品，每种产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500线性规划例•问：工厂应如何安排生产可获得最大的总利润？•解：设xj为第j种（甲、乙）产品的生产件数j＝1，2，则由题意知，问题可转化为线性规划例•注：Max为Maximize求f的最大值，s.t.为Subjectto约束，限制，满足于121212212150025003265240..375,0Maxfxxxxxxstxxx线性规划例•求解方法一：图解法线性规划例•求解方法二：单纯形法1212312425150025003265240..3750,1,2,3,4,5jMaxfxxxxxxxxstxxxj线性规划例•第一次迭代：（1）取x3，x4，x5为基变量，x1，x2为非基变量，基本可行解为（0，0，65，40，75），f＝01231241252150025006532402753fxxxxxxxxxx线性规划例•（2）选择进基变量：目标函数中非基变量的系数全为负时，则刚才的基本可行解即为最优解。若有正的，选择系数大的非基变量为进基变量，本例为x2•（3）出基变量为当进基变量增大时，首先下降为零的基变量，本例为x5线性规划例•第二次迭代（1）取x2，x3，x4为基变量，x1，x5为非基变量，可行解为（0，25，15，15，0），f＝6250015253154156250015002500/325/31532/3152/3fxxxxxxxxxx线性规划例•（2）选择进基变量：方法同第一次迭代，本例为x1•（3）出基变量：方法同第一次迭代，本例为x3线性规划例•第三次迭代：（1）取x1，x2，x4为基变量，x3，x5为非基变量，可行解为（5，25，0，5，0），f＝700003513525415700005005005/32/925/352/3/9fxxxxxxxxxx线性规划例•2）选择进基变量：已无，因此该可行解即为最优解，结束。线性规划一般模型•目标函数：•约束条件：1122nnMaxfcxcxcx1111221121122222112212..,,,0nnnnmmmnnmnaxaxaxbaxaxaxbstaxaxaxbxxx称xj为决策变量，cj为价值系数和费用系数，aij为约束系数或技术系数，bi为资源系数。线性规划一般模型•其它形式111,,..01,,njjjnijjijjMaxfcxaxbimstxjn..0TMaxfCXAXbstX线性规划中的一些名词和术语•线性规划模型三要素：•决策变量•约束条件•目标函数线性规划中的一些名词和术语•可行解——满速线性规划全部约束条件的解•可行域——全体可行解的集合•最优解——使得目标函数实现最小值（或最大值）的可行解•最优值——最优解的目标函数值线性规划模型标准型•LP11min1,,..01,,njjjnijjijjfcxaxbimstxjnmin..0TfCXAXbstXmin{|,0}TCXAXbX求线性规划方法－单纯形法G.B.Danting在1947年提出了求解线性规划问题的方法——单纯形法(simplexmethod)，其原理是：如果（LP）的可行域K不是空集，我们从K的某一顶点X0出发，判别它是否为最优解？若不是，沿着边界找它邻近的另一个顶点，它应比原来的顶点优，看它是否为最优解？若不是，再沿着边界找它邻近的顶点。通过逐次迭代，直至找出最优解。求线性规划方法－软件LINDO软件包首先由LinusSchrage开发，现在，美国的LINDO系统公司（LINDOSystemInc.）拥有版权，是一种专门求解数学规划（优化问题）的软件包。它能求解线性规划、（0，1）规划、整数规划、二次规划等优化问题，并能同时给出灵敏度分析、影子价格以及最优解的松弛分析，非常方便实用。与线性规划有关的名字•改进单纯形法•人工变量法（大M法和两节段法）•对偶问题，对偶理论，对偶单纯形法•影子价格•灵敏度分析线性规划有关的问题•1.生产计划问题：m种资源B1,B2,…,Bm，生产n种产品A1,A2,…,An，单位产品所需资源数aij，所得利润cj，可供应的资源总量bi，问应如何组织生产才能使利润最大？•2.合理下料问题：一维下料，二维下料，三维下料线性规划有关的问题•3.合理配料问题：m种原料B1,B2,…,Bm混合调制n种产品A1,A2,…,An，产品的规格要求、单位价格，原料供应量，原料的价格要求如下，问应如何组织生产才能使利润最大？线性规划有关的问题•4.运输问题：m个物资产地B1,B2,…,Bm，n个物资销地A1,A2,…,An，si为产地Bi产量，dj为销地Aj的销量，cij表示把物资从产地Bi运到销地Aj的单位运价，xij表示把物资从产地Bi运到销地Aj的运输量，问应如何运输才能使运费最小？对偶问题•引例：某工厂计划在下一生产周期生产3种产品A1,A2,A3，这些产品都要在甲、乙、丙、丁4种设备上加工，根据设备性能和以往的生产情况知道单位产品的加工工时、各种设备的最大加工工时限制，以及每种产品的单位利润，如下表。问如何安排生产计划，才能使工厂得到最大利润？对偶问题产品设备A1A2A3总工时限制/h甲21370乙42280丙30115丁22050单位利润/千元8102对偶问题•解：设xj为产品Aj的生产件数j＝1,2,3，则由题意知，问题可转化为如下的线性规划问题12312312313121238102237042280315..2250,,0Maxfxxxxxxxxxxxstxxxxx对偶问题•现在从另一个角度来讨论问题：假设工厂考虑不安排生产，而准备将所有设备出租，收取租费。于是需要为每种设备的台时进行估价。设y1,y2,y3,y4分别表示甲、乙、丙、丁4种设备的台时估价，下面分析约束条件和目标函数对偶问题•由上面的表可知，生产一件产品A1需要各设备台时分别为2h，4h，3h，2h，如果将2h，4h，3h，2h不用于生产产品A1，而是用于出租，租费应满足（为了不蚀本，租费不能少于利润，否则还不如自己生产产品合算呢！）2y1+4y2+3y3+2y4≥8，依次可分析得线性规划模型如下对偶问题•说明：企业为了能够得到租用设备的用户，使出租设备的计划成交，在价格满足约束条件下，应将设备价格定得尽可能低。1234123412312312370801550243282210..322,,0Minfyyyyyyyyyyystyyyyyy对偶规划原有问题（P）对偶问题（D）11min1,,..01,,njjjnijjijjfcxaxbimstxjn11max1,,..01,,miiimijijiizbyaycjnstyim设为对偶问题（D）的最优解，则称为原有问题（P）第i个约束对应的影子价格（ShadowPrice）****12ˆ(,,,)Tmyyyy*iy对偶规划－影子价格•影子价格的经济含义：（1）影子价格是对现有资源实现最大效益的一种估价。根据上例，企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租；第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。对偶规划－影子价格•（2）影子价格表明资源增加对总效益产生的影响。易见有•从而，如果增加一个单位，目标函数值的增量将是，据此，由影子价格的大小可以知道哪种资源的增加可以给企业带来较大的收益。*****1122mmfzbybybyib*iy对偶规划－影子价格应用例•某外贸公司准备购进两种产品A1,A2。购进产品A1每件需要10元，占用5m3的空间，待每件A1卖出后，可获纯利润3元；购进产品A2每件需要15元，占用3m3的空间，待每件A2卖出后，可获纯利润4元。公司现有资金1400元，有430m3的仓库空间存放产品，如何安排可以获得最大利润？对偶规划－影子价格应用例•现在公司有另外一笔资金585元，准备用于投资，到底是购买产品呢？还是增加仓库容量？（假设增加1m3的仓库空间需要0.8元）灵敏度分析•最优解是在参数cj、bi、aij都固定不变的条件下取得的。但是，在实际问题中，对一个具体的企业来说，参数cj、bi、aij不是固定不变的，或者说得到的这些参数有一定的误差。•如产品的市场价格可能有所变动；国家分配的原材料可能有所增减；动力供应情况可能随季审而变化f添置新设备而使生产台时增加；由于产品设计结构有所改进，使单位产品的原材料消耗定额有所增减……，灵敏度分析•现实诸因素的种种变化都会引起已建立的数学模型的参数变化。或者，当运用线性规划编制完生产计划并即将付诸应用时，又发生了新的情况，某些原来未加限制的资源现在有了限制，从而出现一个新的追加约束条件。或者，企业准备增加新产品，使工厂的生产计划发生整个变化。灵敏度