运筹学论文

《运筹学论文》由会员分享，可在线阅读，更多相关《运筹学论文（10页珍藏版）》请在金锄头文库上搜索。

1、1. 线性规划1.1 图解法1.1.1 解题步骤1. 图解法步骤 2.建立坐标系3.找出可行域 4.绘出目标函数图形5.求出最优解1.2 单纯形法1.2.1 解题思想：保持最优性不断改善解的可行性1.2.2 解题步骤1找到初始可行解确定基变量，没有合适的基变量时，引入人工变量。2列出单纯型表，通过检验系数。二Cj-C B-Pj确定进基变量，通过e二B-b-B-a 确定出基变量，不断迭代达到最优解。B3判断标准：在Max的条件下，。全部小于0时，停止迭代，达到最优解。12.3解的几种情况在终表上的体现1. 唯一最优解：终表上所有非基检验数均小于 0。2. 多重最优解（无穷）：终表上存在非基检验数

2、等于 0，通过终表可以写出一 个最优解 X* Max Z。3. 无界解：终表上，存在正检验数相应的系数列中的所有系数均为非正（两 出基e均小于0）。4. 无解（只出现在使用人工变量的情况下）I 大M法：最优解有X （X 不等于0）.人工人工II两阶段法：Min不等于0,无解。1.3 对偶单纯形法1.3.1 解题思想：保证最优性，改善可行性1.3.2 解题步骤1. 前提：保障最优性:o=c-z二c-CB-1 W0。B2检查可行性：检查B-ib （常数项），若非负，则得到最优解，若还有负数, 则开始下一步。3判断出基变量：找出B-ib中负数最小值，min（B-ib I B-ib0）,这个数所 在对

3、应变量Xi就是出基变量。4. 判断进基变量：看出基变量Xi所在行的每一个系数aij,若aijO,则无可 行解，若存在 aij0,则计算 6=min （o/ai） I ai0）.5. 主元迭代（初等行变换），直到B-ib0时结束。2. 对偶问题2.1 对偶问题的一般性质1. 对偶性：对偶问题的对偶问题是原问题。2弱对偶性：若拔X是原问题的可行解，则拔Y是对偶问题的可行解，cXW Yb （出让价格大于盈利）。3. 无界性:若原问题（对偶）为无界解，则其对偶问题（原问题）无可行解。4. 可行解和最最优解性质：设XA是原问题可行解，Y人是对偶问题可行解， 当cXa =Y Ab时，XA， Y均为最优解。

4、a5. 对偶定理:若原问题有最优解，那么对偶问题也有最优解，目标函数值相同6. 互补松性：期9, ；!最视胡丄刼役右条s似9 倒：艇词塑：X X卷教：张张日嚙： 1八兹:弘h Ja血产夕 A.=oLE d L 池r3灵敏度分析（关键因素B-）1将参数的改变通过计算反映到最终单纯形表上2检验是能否继续迭代是 否是最优解。3继续迭代改善。4运输问题4.1特征1决策变量数m*n个。2约束方程数m+n个。3独立约束（产销平衡）最多 有m+n-1个，基变量m+n-14.2表上作业法4.2.1基本思想1. 寻找初始基可行解：最小兀素法，西北角法，沃格尔法。2求出非基变量检验数，判断是否为最优解：闭回路法（

5、经济含义：由Ai 往Bi增运一个单位的货物时所引起的总运输成本的变化），位势法。3换基改进，直到o0.5. 目标规划5.1目标函数目标函数由优先级p和可调整的偏差变量d+, d-组成。目标函数中的偏差 变量之间都是加+号，但是偏差变量有所取舍。其优先级的重要性决定优先级 p 的系数。5.2 约束条件方程绝对约束不可以修改;目标约束可以通过调整偏差变量的方式进行调整， (约 束条件中填写的所有偏差变量都是(d+,d-)的形式，所有的di+,di-都列出。目标 规划模型的约束方程都是等号。6. 整数规划6.1 含义：一部分或者全部决策变量取整6.2 相关结论(1) 最优解不一定在顶点上达到；(2)

6、 最优解不一定是松弛问题:最优解的邻近整数解(3) 整数可行解远多余于顶点，枚举法不可取。6.3割平面法6.3.1 解题思想 先不考虑整数性约束，求解相应的线性规划问题。若线性规划问题的最优解 恰好是整数解，则此解即为整数规划问题的最优解。否则，就增加一个新的约束条件。6.3.2 解题步骤从线性规划问题的可行域中至少割掉的非整数最优解；不割掉任何整数可行 域，然后在缩小的可行域上。继续解线性规划问题。重复以上做法，经有限次切 割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。6.4 分支界定法6.4.1 解题思想首先不考虑变量的整数约束，求解相应的线性规划问题，得到线性规划问题

7、 的最优解。6.4.2 解题步骤1.先不考虑整数约束，求解整数规划的松弛问题。I若松弛问题没有可行解，则整数规划也没有可行解，停止计算；II若松弛问题有最优解，并符合整数规划的整数条件，则线性规划的 最优解即为整数规划的最优解，停止计算；III若松弛问题有最优解，但不符合整数规划的整数条件，转入下一步。2. 分支：从不满足整数条件的基变量中任选一个 xi 进行分支，它必须满足 xiWxi或xiMxi+1中的一个,把这两个约束条件加进原问题中，形成两个互不相 容的子问题。3. 定界:把满足整数条件各分支的最优目标函数值作为上（下）界，用它来判断 分支是保留还是剪支。4. 剪支:把那些子问题的最优

8、值与界值比较，凡不优或不能更优的分支全剪 掉，直到每个分支都查清为止。6.5 【0-1】型整数规划变量仅可取0/1,此时的变量xi称为0-1变量或二进制变量，其中0-1变量作为逻辑变量，常用来表示系统是否处于某一特定状态或决策时取某个方案。7. 动态规划7.1 所用概念1.阶段：将整个问题过程按照时间或者空间特征划分为有联系的部分2. 状态：过去历史的完整总结3. 决策与策略：确定下一阶段状态的选择。4. 指标函数：衡量所选策略优劣的各项指标7.2 解题思想1.分阶段，确定变量，逐个求解。2. 从边界开始，每次求解都用之前的最优解。3. 对于先前的决策形成的现在的状态，之后的所有决策都应当最优

9、7.3 模型的建立7.3.1 要素1阶段数k2.状态变量Sk。决策变量Uk。.状态转移方程Sk+1二T(Sk*Uk)。 5指标函数Vk, n。6最优值函数fk (sk)7.3.2 基本要求1. 所研究的问题必须能够分成几个相互联系的阶段,而且在每一个阶段都具 有需要决策的问题。2. 在每一个阶段都必须有与该阶段相关的状态。3. 具有明确的指标函数,且阶段指标值可以计算。4. 能正确列出最优质函数的递推公式和边界条件。三 运筹学在电子商务中的应用当用户从电子商务平台购物之后，订单生成，随后进入物流阶段。电子商务 物流涉及存储中心、配送中心，以及最后的送货问题。存储中心会收到捡货单， 经过捡货、包

10、装之后，货物从存储中心运输到配送中心，经过转运，最后送到用 户端。在这个过程 中，物流企业有这样几个关键的核心问题：在哪里建 立存储 中心和配送中心？解决这些问题需要用到运 筹学中的选址问题（。存储中 心的 存储量是多少？何时达到库存的预警？解决这些问题需要用到运筹学中的库存 管理问题（Inventory Management Problem ）。配送中心需要建成多大规模，需 要多少配送员，配送路径如何规划，解决这些问题需要用到运筹学。案例：YZ物流公司的选址问题。YZ 化工物流公司是经中国商务部和上海工商管理局批准的、从事陆河运国 际货运代理业务的综合性物流企业。公司下设一般化工品部、危险品

11、空运部、普 通箱危险品进出口部、罐式集装箱（Tank Container）国际物流部、罐式集装箱 国内物流部、危险品运输部、危险品仓储部、市场部、客户服务部、单证部、财 务部、风险管理部、海外部、报关部、事务部等。其主营业务为化工品物流运输， 同时也包括危险化学品的物流运输。所谓危险化学品，是指具有易燃、易爆、有毒、有腐蚀等特性，会对人（包 括生物）、设备、环境造成伤害和侵害的化学品。根据危险化学品管理条例，可 将其分为九大类，它们分别是：第1 类，爆炸品。爆炸品是指在外界作用下（如受热、摩擦、撞击等）能发 生剧烈的化学反应，瞬间产生大量气体和热量，使周围压力急剧上升，发生爆炸， 对周围环境、

12、设备、人员造成破坏和伤害的物品。爆炸品在国家标准中分 5 项， 其中有3 项包含危险化学品，另外 2 项专指弹药等；第2 类，压缩气体和液化气体。指压缩的、液化的或加压溶解的气体。这类 物品当受热、撞击或强烈震动时，容器内压力急剧增大，可能导致容器破裂，物 质泄漏、爆炸等，造成危害；第3 类，易燃液体。本类物质在常温下易挥发，其蒸气与空气混合能形成爆 炸性混合物；第4 类，易燃固体、自燃物品和遇湿易燃物品。这类物品易于引起火灾；第5 类，氧化剂和有机过氧化剂。这类物品具有强氧化性，易引起燃烧、爆 炸；第6 类，有毒品。指进入人（动物）肌体后，累积达到一定量能与体液和组 织发生生物化学作用或生物

13、物理作用，扰乱或破坏肌体的正常生理功能，引起暂 时或持久性的病理改变，甚至危及生命的物品，如各种氰化物、砷化物、化学农 药等等；第7 类，放射性物品。放射性物品的危险性在于辐射污染，最终使人员受到 辐射伤害；第8类，腐蚀品。指能灼伤人体组织并对金属等物品造成损伤的固体或液体；第9 类，杂类。指除以上类别之外的危险化学品，例如磁性材料等。YZ 公司目前可以承接的危险化学品类别有第2、3、4、5、6、8、9 类。危 险化学品一般都是工业原料或产品，因其特殊的物理、化学性能，在接触和处理 过程中必须遵守相应的规则，以免发生事故，造成灾害。其运输环节是一项技术 性和专业性很强的工作，主要特点为：品类繁

14、多，性质各异；危险性大； 专业性强。其专业性主要表现为：业务专营；车辆（运输工具）专用；人 员专业。因此，对于危险化学品的物流运输必须严格控制。而在危险化学品的仓 储方面，由于某些化学品之间的特性，不可兼容，使得化学品的存放更加严格。 因此，企业在选择仓库或配送中心的时候，不仅要考虑成本和规模，还要充分考 虑危险化学品的安全性问题。YZ 公司的选址决策问题YZ 公司目前代理甲、乙、丙、丁 4 家化学品生产企业的运输和配送服务。 各供应商所经营的危险化学品种类、产能及销售价格如表1所示。表 1. 各供应商经营的化学品类型、产能及销售价格经营化学品类型年生产能力（千吨）销售价格（万元/千吨）甲2、

15、5、8802 类：785 类：12008 类：80乙3、4703 类：5004 类：1300丙2、6602 类：806 类：1200丁8、9708 类：769 类：600YZ公司已有A、B两个危险化学品配送中心，可供危险化学品出口装箱使用， A 存货量为 30 千吨， B 存货量为 20 千吨。每个配送中心带有一个可同时停靠 3 辆集卡车并带雨棚的装卸平台。出于安全性考虑，某些化学品不能够混放，例如， A只能存放2、5、8、9类危险化学品，而B则存放3、4、6类危险化学品。为 减少B配送中心的危险性，同时扩大业务缓解存货压力，公司拟再建一个配送中 心，专门用来存放4类和6类化学品。经过初步筛选，有C、D、E、F四个备择 方案，各备选地点的运营成本和存储能力如表2所示，供应商到备选地点的运输 成本如表 3 所示。表 2. 各配送中心运营成本及存货能力配送中心运营成本（万元/年）存货能力（千 吨）A一60B一50备C260560选D216565