6运筹学建模

null运筹学建模运筹学建模1.线性规划 2.对偶规划和影子价格 3.运输问题 4.整数规划 5.动态规划运筹学简介运筹学简介1.引言： 运筹学（Operations Research）主要研究系统最优化。在我国公元前6世纪《孙子兵法》中处处体现了军事运筹的思想，贾思勰的《齐民要术》一书是一部体现运筹思想、合理规划农事的宝贵文献。null 欧美，在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三种类型的设备，生产甲、乙两种产品，每种产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表 线性规划例线性规划例问：工厂应如何安排生产可获得最大的总利润？解：设xj为第j种（甲、乙）产品的生产件数 j＝1，2 则由题意知，问题可转化为 线性规划例线性规划例注：Max为Maximize求f的最大值，s.t.为Subject to约束，限制，满足于 线性规划例线性规划例求解方法一： 图解法 X1X2(20，0）（15，10）（5，25）（0，25）线性规划例线性规划例求解方法二：单纯形法 线性规划例线性规划例第一次迭代：（1）取x3，x4，x5为基变量，x1，x2为非基变量 ，基本可行解为（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线性规划例线性规划例第三次迭代：（1）取x1，x2，x4为基变量，x3，x5为非基变量 ，可行解为（5，25，0，5，0），f＝70000 线性规划例线性规划例2）选择进基变量：已无 ，因此该可行解即为最优解，结束。 线性规划一般模型线性规划一般模型目标函数： 约束条件： 称xj为决策变量，cj为价值系数和费用系数，aij为约束系数或技术系数，bi为资源系数。线性规划一般模型线性规划一般模型其它形式 线性规划中的一些名词和术语线性规划中的一些名词和术语线性规划模型三要素： 决策变量 约束条件 目标函数线性规划中的一些名词和术语线性规划中的一些名词和术语可行解——满速线性规划全部约束条件的解 可行域——全体可行解的集合 最优解——使得目标函数实现最小值（或最大值）的可行解 最优值——最优解的目标函数值线性规划模型标准型线性规划模型标准型LP求线性规划方法－单纯形法求线性规划方法－单纯形法 G.B.Danting在1947年提出了求解线性规划问题的方法——单纯形法(simplex method)，其原理是：如果（LP）的可行域K不是空集，我们从K的某一顶点X0出发，判别它是否为最优解？若不是，沿着边界找它邻近的另一个顶点，它应比原来的顶点优，看它是否为最优解？若不是，再沿着边界找它邻近的顶点。通过逐次迭代，直至找出最优解。求线性规划方法－软件求线性规划方法－软件 LINDO软件包首先由Linus Schrage开发，现在，美国的LINDO系统公司（LINDO System Inc.）拥有版权，是一种专门求解数学规划（优化问题）的软件包。它能求解线性规划、（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种设备上加工，根据设备性能和以往的生产情况知道单位产品的加工工时、各种设备的最大加工工时限制，以及每种产品的单位利润，如下表。问如何安排生产计划，才能使工厂得到最大利润？对偶问题对偶问题对偶问题对偶问题解：设xj为产品Aj的生产件数 j＝1,2,3，则由题意知，问题可转化为如下的线性规划问题对偶问题对偶问题现在从另一个角度来讨论问题：假设工厂考虑不安排生产，而准备将所有设备出租，收取租费。于是需要为每种设备的台时进行估价。设y1, y2, y3, y4分别表示甲、乙、丙、丁4种设备的台时估价，下面分析约束条件和目标函数对偶问题对偶问题由上面的表可知，生产一件产品A1需要各设备台时分别为2h，4h，3h，2h，如果将2h，4h，3h，2h不用于生产产品A1，而是用于出租，租费应满足（为了不蚀本，租费不能少于利润，否则还不如自己生产产品合算呢！） 2 y1+4y2+3 y3+2 y4≥8，依次可分析得线性规划模型如下 对偶问题对偶问题 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 ：企业为了能够得到租用设备的用户，使出租设备的计划成交，在价格满足约束条件下，应将设备价格定得尽可能低 。对偶规划对偶规划设 为对偶问题（D）的最优解，则称 为原有问题（P）第i个约束对应的影子价格（Shadow Price）对偶规划－影子价格对偶规划－影子价格影子价格的经济含义：（1）影子价格是对现有资源实现最大效益的一种估价。根据上例，企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租；第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。对偶规划－影子价格对偶规划－影子价格（2）影子价格表明资源增加对总效益产生的影响。易见有 从而，如果 增加一个单位，目标函数值的增量将是 ，据此，由影子价格的大小可以知道哪种资源的增加可以给企业带来较大的收益。对偶规划－影子价格应用例对偶规划－影子价格应用例某外贸公司准备购进两种产品A, B。购进产品A每件需要10元，占用5m3的空间，待每件A卖出后，可获纯利润3元；购进产品B每件需要15元，占用3m3的空间，待每件B卖出后，可获纯利润4元。公司现有资金1400元，有430 m3的仓库空间存放产品，如何安排可以获得最大利润？对偶规划－影子价格应用例对偶规划－影子价格应用例现在公司有另外一笔资金585元，准备用于投资，到底是购买产品呢？还是增加仓库容量？（假设增加1m3的仓库空间需要0.8元） 灵敏度分析灵敏度分析例如：有一个木匠作坊制作两种不同大小的黄杨木棋子。小棋子一套需要车床加工3小时，大棋子一套需要2小时。木匠作坊内有4个车床和4名熟练工人，每人每周工作40小时，因此每周车床总工时数为160小时。小棋子一套需要1kg的黄杨木，大棋子一套需要3kg的黄杨木。很不幸的是，黄杨木现在很稀缺，每周只能得到200kg. 如果售出，每套大棋子能够得到20元的利润，每套小棋子能够得到5元利润。问每周应分别加工每种棋子多少套，才能够得到最多的利润？灵敏度分析灵敏度分析解：假设生产小棋子数量为xs套，大棋子xl套，则问题的模型为 目标函数：maxf=5xs+20xl 约束条件：3xs+2xl≤160 xs+3xl≤200 xs≥0， xl≥0整数灵敏度分析灵敏度分析建模时显然的假定： （1）对于每种棋子，总生产时间与所需生产的棋子套数成正比； （2）在切换生产不同大小的棋子时不存在由于设备重新调整带来的额外时间支出； （3）生产出的所有棋子都能够售出。灵敏度分析灵敏度分析建模时隐含的假定： （1）车床不会损坏和卡死； （2）操作员每天都来上班； （3）黄杨木不存在任何可能导致原料不可用或生产出的棋子质量不满足要求； （4）我们不需要降低价格（从而使单位产品利润也降低）来得到订单； （5）棋子只加工了部分的情况不予考虑（其实对下周还是有用的）。灵敏度分析灵敏度分析最优解是在参数cj、bi、aij都固定不变的条件下取得的。但是，在实际问题中，对一个具体的企业来说，参数cj、bi、aij不是固定不变的，或者说得到的这些参数有一定的误差。 如产品的市场价格可能有所变动；国家分配的原材料可能有所增减；动力供应情况可能随季审而变化f添置新设备而使生产台时增加；由于产品设计结构有所改进，使单位产品的原材料消耗定额有所增减……，灵敏度分析灵敏度分析现实诸因素的种种变化都会引起已建立的数学模型的参数变化。或者，当运用线性规划编制完生产计划并即将付诸应用时，又发生了新的情况，某些原来未加限制的资源现在有了限制，从而出现一个新的追加约束条件。或者，企业准备增加新产品，使工厂的生产计划发生整个变化。 灵敏度分析灵敏度分析从而，我们面临这样的问题：上述种种情况的发生，将对已求得的最优解产生什么影响?或者说，我们如何在原有的最优单纯形表的基础上用最少的计算量，去获得修改后的线性规划问题的最优解?这就是我们要讨论的灵敏度分析（Sensitivity Analysis）问题。 灵敏度分析灵敏度分析一般分下面5个问题来进行灵敏度分析： 1．变量xj的目标函数系数cj在何范围内变动，问题(LP)的最优基(最优解)不变?如果超出这个范围，如何求最优解? 2．第s种资源bs在何范围内变动，最优基不变?如果bs超出这个范围，如何求最优解? 3．变量xj在矩阵A中的系数列向量发生变化，如何求新问题的最优解? 4．追加新的约束条件，如何求新的线性规划的最优解? 5．增加新的变量xj，如何求新问题的最优解?特殊规划－运输问题特殊规划－运输问题一般模型：m个物资产地（发点）A1, A2,…, Am，n个物资销地（收点）B1, B2, …, Bn，ai为发点Ai的物资供应量（发量），bj为收点Bj对物资的需求量（收量），cij表示把物资从Ai运到Bj的单位运价，xij表示把物资从Ai运到Bj的运输量，问应如何运输才能使运费最小？（假定收发平衡）特殊规划－运输问题特殊规划－运输问题Ai运输收发平衡单位运价表（简称运输表格）特殊规划－运输问题特殊规划－运输问题称之为运输问题的标准模型，此为产销平衡模型，产销不平衡时，增加虚拟的收点和发点（松弛变量）即可达到产销平衡。特殊规划－运输问题特殊规划－运输问题求解方法：线性规划的解法也适用运输问题，但是针对运输问题的特殊性有其特殊解法——表上作业法（详见有关书籍）。 一些名词：闭回路，孤立点，寻找初始基本可行解方法（西北角法，最小元素法），计算检验数方法（位势法）一般模型有：平衡运输问题，不平衡运输问题，有界发量运输问题，运量有界的运输问题，转运问题，多品种物资运输问题，空车调度问题特殊规划－整数规划特殊规划－整数规划决策变量为整数时的线性规划称为整数规划，如：去掉整数要求后的最优解为（1.5, 3.33）是否通过作舍入处理，就可得到最优解？特殊规划－整数规划特殊规划－整数规划我们发现（2, 3）,（1, 3）,（2, 4）,（1, 4）都不是，其实（2, 2）或（3, 1）才是。另一方面，这种舍入的计算量也是相当大的（多大？） 由此可见，整数规划有其自己独到的一些解法！割平面法，柯莫力割，柯莫力割平面法,分支定界法（隐式枚举法） 整数规划含纯整数规划（AIP）、混合整数规划（MIP）和0－1规划（BIP）