《运筹学》全套课件（完整版）【PPT】

《《运筹学》全套课件（完整版）【PPT】》由会员分享，可在线阅读，更多相关《《运筹学》全套课件（完整版）【PPT】（365页珍藏版）》请在金锄头文库上搜索。

1、* 运 筹 学 ( Operations Research ) 经济学核心课程经济学核心课程 * 绪绪 论论 （1）运筹学简述 （2）运筹学的主要内容 （3）本课程的教材及参考书 （4）本课程的特点和要求 （5）本课程授课方式与考核 （6）运筹学在工商管理中的应用 本章主要内容： Page 3 * 运筹学简述运筹学简述 运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹 学称之为管理科学(Management Science)。运筹学所研究的 问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案” 故有人称之为最优化技术。

2、 Page 4 * 运筹学简述运筹学简述 运筹学的历史 “运作研究(Operational Research)小组”:解决复 杂的战略和战术问题。例如： 1. 如何合理运用雷达有效地对付德军德空袭 2. 对商船如何进行编队护航，使船队遭受德国潜 艇攻击时损失最少； 3. 在各种情况下如何调整反潜深水炸弹的爆炸深 度，才能增加对德国潜艇的杀伤力等。 Page 5 * 运筹学的主要内容运筹学的主要内容 数学规划（线性规划、整数规划、目标规划、动态 规划等） 图论 存储论 排队论 对策论 排序与统筹方法 决策分析 Page 6 * 本课程的教材及参考书本课程的教材及参考书 选用教材 运筹学基础及应用

3、胡运权主编 哈工大出版社 参考教材 运筹学教程胡运权主编 （第2版）清华出版社 管理运筹学韩伯棠主编 （第2版）高等教育出版社 运筹学(修订版) 钱颂迪主编 清华出版社 Page 7 * 本课程的特点和要求本课程的特点和要求 先修课：高等数学，基础概率、线性代数 特点：系统整体优化；多学科的配合；模型方法的应用 运筹学的研究的主要步骤： 真实系统 系统分析 问题描述 模型建立 与修改 模型求解 与检验 结果分析与 实施 数据准备 Page 8 * 本课程授课方式与考核本课程授课方式与考核 学科总成绩 平时成绩 （40） 课堂考勤 （50） 平时作业 （50） 期末成绩 （60） 讲授为主，结合

4、习题作业 Page 9 * 运筹学在工商管理中的应用运筹学在工商管理中的应用 运筹学在工商管理中的应用涉及几个方面： 1. 生产计划 2. 运输问题 3. 人事管理 4. 库存管理 5. 市场营销 6. 财务和会计 另外，还应用于设备维修、更新和可靠性分析，项目的选择 与评价，工程优化设计等。 Page 10 * 运筹学在工商管理中的应用运筹学在工商管理中的应用 Interface上发表的部分获奖项目 组织应用效果 联合航空公司在满足乘客需求的前提下，以最低成本进 行订票及机场工作班次安排 每年节约成本600万美元 Citgo石油公司优化炼油程序及产品供应、配送和营销每年节约成本7000万 A

5、T Page 26 * 线性规划问题的数学模型线性规划问题的数学模型 标准形式如下： Page 27 * 线性规划问题的数学模型线性规划问题的数学模型 4. 线性规划问题的解 线性规划问题 求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。 Page 28 * 线性规划问题的数学模型线性规划问题的数学模型 可行解：满足约束条件、的解为可行解。所有可行解 的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(m0 40 10 换 出 行 将3化为1 5/3 1 180 1/301/310 11/330 3

6、0 05/304/3 乘 以 1/3 后 得 到 103/5 1/5 18 011/52/54 00 11 Page 48 * 单纯形法的计算步骤单纯形法的计算步骤 例1.9 用单纯形法求解 解：将数学模型化为标准形式： 不难看出x4、x5可作为初始基变量，列单纯形表计算。 Page 49 * 单纯形法的计算步骤单纯形法的计算步骤 cj12100 i cB基变量bx1x2x3x4x5 0 x4152-3210 0 x5201/31501 12100 0 x4 2x2 20 x x2 2 2 2 1/3150120 75301713 1/30902 25 60 x x1 1 11017/31/3

7、125 0128/9-1/92/3 35/3 00-98/9 -1/9 -7/3 Page 50 * 单纯形法的计算步骤单纯形法的计算步骤 学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形法的解题思路及求解步骤 Page 51 * 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易 确定一组基可行解。在实际问题中有些模型并不含有单位 矩阵，为了得到一组基向量和初基可行解，在约束条件的 等式左端加一组虚拟变量，得到一组基变量。这种人为加 的变量称为人工变量，构成的可行基称为人工基，用大M 法或两阶段法

8、求解，这种用人工变量作桥梁的求解方法称 为人工变量法。 Page 52 * 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 例1.10 用大M法解下列线性规划 解：首先将数学模型化为标准形式 系数矩阵中不存在 单位矩阵，无法建 立初始单纯形表。 Page 53 * 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 故人为添加两个单位向量，得到人工变量单纯形法数学模型： 其中：M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；再用前面介 绍的单纯形法求解该模型，计算结果见下表。 Page 54 * 单纯形法的进一步讨论人工变量法单

9、纯形法的进一步讨论人工变量法 cj32-100-M-M CBXBbx1x2x3x4x5x6x7i -Mx64-431-10104 0 x5101-1201005 -Mx712-2100011 3-2M2+M-1+2M-M 0 x63-650-1013/5 -Mx58-3300108/3 -1x312-21000 5-6M5M0-M00 2x23/56/5101/50 -Mx531/53/5003/5131/3 -1x311/52/5012/50 5 0000 2x21301012 3x131/310015/3 -1x319/300102/3 000-5-25/3 Page 55 * 单纯形法的

10、进一步讨论人工变量法单纯形法的进一步讨论人工变量法 解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零, 则线 规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零, 则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个k0且aik（i=1，2,m）则线性 规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并 且存在Ri0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。 Page 56 * 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 单纯性法小结: 建 立 模 型 个 数取

11、 值右 端 项 等式或 不等式 极大或极小 新加变量 系数 两 个 三个 以上 xj0 xj无 约束 xj 0 bi 0bi mi 时，企业愿意 购进这种资源，单位纯利为yi*mi ，则有利可图；如果yi* mi 则购进资源i，可获单位纯利yi*mi 若yi* mi则转让资源i ，可获单位纯利miyi Page 99 * 对偶问题的经济解释影子价格对偶问题的经济解释影子价格 3）影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理: Y*Xs=0 , YsX*=0 表明生产过程中如果某种资源bi未得到充分利用时，该种资 源的影子价格为0；若当资源资源的影子价格不为0时，表明 该种资源在生产

12、中已耗费完。 Page 100 * 对偶问题的经济解释影子价格对偶问题的经济解释影子价格 4）影子价格对单纯形表计算的解释 单纯形表中的检验数 其中cj表示第j种产品的价格; 表示生产该种产品所 消耗的各项资源的影子价格的总和,即产品的隐含成本。 当产值大于隐含成本时，即 ，表明生产该项产品有 利，可在计划中安排；否则 ，用这些资源生产别的 产品更有利，不在生产中安排该产品。 Page 101 * 对偶单纯形法对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。它 是根据对偶原理和单纯形法原理而设计出来的，因此称为 对偶单纯形法。不要简单理解为是求解对偶问题的单纯形 法。 对偶单纯形法原

13、理对偶单纯形法原理 对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的 条件下，判断XB是否可行（XB为非负），若否，通过变换基 解，直到找到原问题基可行解（即XB为非负），这时原问题 与对偶问题同时达到可行解，由定理4可得最优解。 Page 102 * 对偶单纯形法对偶单纯形法 找出一个DP的可行基 LP是否可行 （XB 0） 保持DP为可行解情况下转移到LP 的另一个基本解 最优解 是 否 循 环结束 Page 103 * 对偶单纯形法对偶单纯形法 例2.9 用对偶单纯形法求解： 解:（1）将模型转化为求最大化问题，约束方程化为等式求 出一组基本

14、解，因为对偶问题可行，即全部检验数0（求 max问题）。 Page 104 * 对偶单纯形法对偶单纯形法 cj-9-12-15000b cBxBx1x2x3x4x5x6 0 x4-2-2-1100-10 0 x5-2-3-1010-12 0 x6-1-1-5001-14(-9/-1.-12/-1. -15/-5) j -9-12-150000 Page 105 * 对偶单纯形法对偶单纯形法 cj-9-12-15000b cBxBx1x2x3x4x5x6 0 x4-9/5-9/5010-1/5-36/5 0 x5-9/5-14/5001-1/5-46/5 -15x31/51/5100-1/514

15、/5(-30/-9,-45/-14, -15/-1) -6-9000-342 cj-9-12-15000b cBxBx1x2x3x4x5x6 0 x4-9/14001-9/14-1/14-9/7 -12x29/14100-5/141/1423/7 (-3/-9,-45/-9, -33/-1) -15x31/140101/14-3/1415/7 -3/14000-45/14-33/14 Page 106 * 对偶单纯形法对偶单纯形法 cj-9-12-15000 cBxBx1x2x3x4x5x6b -9x1100-14/911/92 -12x20101-102 -15x30011/90-2/92

16、000-1/3-3-7/3 原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72 Page 107 * 对偶单纯形法对偶单纯形法 对偶单纯形法应注意的问题： 用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶 问题的最优解 初始表中一定要满足对偶问题可行，也就是说检验数满足最优判 别准则 最小比值中 的绝对值是使得比值非负，在极小化问题j0 ，分母aij0 这时必须取绝对值。在极大化问题中， j0，分母 aij0， 总满足非负，这时绝对值符号不起作用，可以去掉。如 在本例中将目标函数写成 这里j 0在求k时就可以不带绝对值符号。 Page 108 * 对偶单纯形法对偶单纯形法 对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法 是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变 量后确定进基变量； 普通单纯形法的最小比值是 其目的是保证下一 个原问题的基本解可行，对偶单纯形法的最小比值是 其目的是保证下一个对偶问题的基本解可行 对偶单纯形法在确定出基变量时，若