运筹学(重点).ppt

目 录 绪 论 第一章 线性规划 第二章 运输问题 第三章 整数规划 第四章 动态规划 第五章 目标规划 第六章 图与网络分析 运筹学的分支 数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划、多目标规划 图论与网络理论 随机服务理论：排队论 存储理论 决策理论 对策论 系统仿真：随机模拟技术、系统动力学 可靠性理论 三、运筹学解决问题的方法步骤 明确问题 建立模型 设计算法 整理数据 求解模型 评价结果 第一章 线性规划 §1.1 一般线性规划问题及数学模型 1.1.1 问题的提出 例： 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备时间和原料A、B的消耗量如下表。 该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划能使该厂获利最多？ 建立模型： 图解法举例 实施图解法，以求出最优生产计划（最优解）。 两个约束条件及非负条件x1,x2 ?0所代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。 第二个约束条件的边界－－ 直线CD: 1/3x1+4/3 x2 =3 沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E, E点就是要求的最优解，即x1=1,x2=2就是线性规划模型的最优解，Zmax=8就是相应的目标函数最优值。 一、初始方案(基本可行解)的确定 初始方案(基本可行解)的确定的方法 1.西北角法 2.最小元素法 3.Vogel法 3.伏格尔(Vogel)法 Vogel法步骤： 一、分别计算运价表的每行、每列最小元素与次小元素的差并填入该表的最右列和最下行 二、在行或列差额中选出最大者，选择这所在的行或列中单位运价最小格开始安排 三、划去对应的行或列的元素，再分别计算运价表的每行、每列两最小元素（最小、次小）差并填入该表的最右列和最下行，且不断重复上述步骤，直至给出调运方案。 Vogel法求出的初始解即为近似最优解 应用举例 某百货公司去外地采购A，B，C，D四种规格的服装，数量分别为A--1500套，B--2000套，C--3000套，D--3500套。有三个城市可以供应上述规格服装，供应数量分别为Ⅰ--2500套，Ⅱ--2500套，Ⅲ--5000套。由于这些城市的服装质量、运价的销售情况不同，预计售出后的利润也不同，见下表，请帮该百货公司确定一个预期赢利最大的采购方案。 第三章 整数规划 1.整数规划的数学模型及解的特点 2.分支定界法、割平面法 1.整数规划的数学模型及解的特点 整数规划数学模型的一般形式 一部分或全部决策变量取整数值的规划问题 ——整数规划 整数规划中不考虑整数条件所对应的规划问题 ——该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 ——整数线性规划 整数线性规划的几种类型 解的特点 整数线性规划与其松弛问题比较，前者的最优解的目标函数值不会优于后者的。 2. 整数规划的分枝定界法 建模： 分枝问题的松弛解 问题1的分支问题松弛解 分枝定界法: 第四章 0-1规划与指派问题 0-1规划问题及模型 二、0-1变量的应用 三、解法---隐枚举法 例： 求解图示： 课后练习： 习题求解 弹性约束的处理方法 思考题 第六章 图与网络分析 图是最直观的模型 图论 Graph Theory 哥尼斯堡七桥问题 (K?nigsberg Bridge Problem) 中 国 邮 递 员 问 题 Chinese Postman Problem CPP 最 短 路 问 题 交通图上的选址问题 选址问题 使所选地址到最远的服务对象距离尽可能小 ——中心点 使所选地址到各服务对象的总距离最小——中位点 网络最大流问题 奇偶点算法改进（二） ----（初始方案的改进） 在所给的图的奇点处做标记，如加“·” 求该图最小生成树（用避圈法或破圈法,破圈原则:1.从权数最长边的圈开始,2.尽可能多保留与奇点相连的边,3.已为偶点者的边尽可能不去掉） 在最小生成树上的奇点处添加重复边（原则是点从权