《运筹学线性规划》PPT课件

运筹学 举例 例 线材合理下料问题 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 例 机器负荷分配问题 某种机器可以在高 低两种负荷下进行生产 高负荷年产量8 年完好率0 7 低负荷年产量5 年完好率0 9 现有完好机器1000台 需制定一个5年计划 以决定每年安排多少台机器投入高 低负荷生产 使5年的总产量最大 消防站选址问题 某城市的消防总部将全市划分为11个防火区 设有4个消防救火站 下图 表示消防站 1 11表示防火区域 图中连线表示各地区由哪个消防站负责 问题 可否减少消防站的数目 仍能同样负责各地区的防火任务 如果可以 应关闭哪个消防站 绪论 产生于二战时期 运筹学 OperationalResearch 直译为 运作研究 20世纪60年代 在工业 农业 社会等各领域得到广泛应用在我国 20世纪50年代中期由钱学森等引入 运用数学方法 为决策者进行最优决策提供科学依据的一门应用科学 运筹学的特点面向管理和工程实际问题应用数学方法建立数学模型一定意义下的优化 一 运筹学的产生与发展 二 学科性质 三 运筹学的分支 线性规划非线性规划图论与网络分析存储论决策论排队论对策论 博弈论 四 管理运筹学的工作程序 明确问题 问题分类 建立数学模型 求解数学模型 结果分析 实施 五运筹学与决策管理就是决策 从这个意义上说 运筹学是典型的辅助决策的学科 决策的基本问题是发现问题和解决问题发现问题需要决策者丰富的经验 广博的知识和敏锐的观察判断能力以及深入细致的调查研究 运筹学可提供某些辅助分析 但主要不针对此问题 解决问题首先要提出方案 方案的创造同样是决策者才干的体现 在解决问题中有两类问题是值得注意的 有些问题的解决方案在既定的准则下隐含在一系列限制条件中 需要一些方法 找出 这个方案 有些问题可能提出几个 有限个 方案 需要一些方法评价和优选这些方案 运筹学在以上两类问题中是很有用的 课程教材 吴育华 杜纲 管理科学基础 修订版 天津大学出版社 主要参考书 1 钱颂迪等 运筹学 北京 清华大学出版社 1990 2 胡运权 运筹学教程 北京 清华大学出版社 1998 3 加 PeterCBell 韩伯棠等译 管理科学 运筹学 战略角度的审视 机械工业出版社 2000 4 丁以中主编 管理科学 运用Spreadsheet建模和求解 北京 清华大学出版社 2003 5 美 弗雷德里克 S 希利尔 FrederickSHillier 任建标译 数据 模型与决策 原书名IntroductiontoManagementScience 北京 中国财政经济出版社 2004 主要授课内容 线性规划 线性目标规划图论与网络分析 网络计划 风险型决策 库存决策动态规划 矩阵对策排队论 课程基本要求 掌握好基本概念 主要模型形式及其特点 必要的算法原理及简单的计算 所需基础知识 微积分 矩阵 线性方程组 概率基础等 班级公共邮箱 guanliyunchou 密码 6个6 第一章线性规划 LinearProgramming 简称LP 1线性规划的模型与图解法 一 LP问题及其数学模型 例1某工厂可生产甲 乙两种产品 需消耗煤 电 油三种资源 有关单耗数据如表 试拟定使总收入最大的生产计划 结构约束条件 非负约束条件 目标函数 资源向量 右端项 LP模型的一般形式 课堂练习 某蓄场每日要为每头牲畜购买饲料 以使其获取所需的A B C D四种养分 有关数据如下表 现饲料可从市场上出售的M N两种饲料中选择 试决定总花费最小的购买方案 列出模型 养分 饲料 课堂练习 某蓄场每日要为每头牲畜购买饲料 以使其获取所需的A B C D四种养分 有关数据如下表 现饲料可从市场上出售的M N两种饲料中选择 试决定总花费最小的购买方案 列出模型 养分 饲料 答案 设购买M饲料x1 N饲料x2 0 5x1 0 1x2 100 2x1 0 3x2 50 3x1 0 4x2 80 2x2 7x1 x2 0 s t MinZ 300 x1 200 x2 二 线性规划的图解法 1 步骤 1 作约束的图形 可行域 可行解的集合 先作非负约束 再作资源约束 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 2 作目标函数的等值线 给z不同的值 作相应直线 判断出z增大时 直线的移动方向 将直线向增大方向移动 直至可行域边界 交点X 即为最优解 7x1 12x2 84 7x1 12x2 168 如 令7x1 12x2 847x1 12x2 168 X 20 24 Z 428 最优解 x1 0 x2 1最优目标值z 6 练习 自学 图解法求解线性规划 2 LP解的几种情况 注 出现 3 4 情况时 建模有问题 图解法的结论 线性规划的可行域是凸集 线性规划的最优解若存在 必在可行域的在极点获得若在两个极点同时获得 则有无穷多最优解 极点 三线性规划应用举例 例1 线材合理下料问题 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 2x1 x2 x3 x4 1002x2 x3 3x5 2x6 x7 100 x1 x3 3x4 2x6 3x7 4x8 100 x1 x2 x3 x4 x5 x6 x7 x8 0 设x1 x2 x3 x4 x5 x6 x7 x8分别为上述8种方案下料的原材料根数 建立如下的LP模型 最优解为 x1 10 x2 50 x3 0 x4 30 x5 0 x6 0 x7 0 x8 0 minZ x1 x2 x3 x4 x5 x6 x7 x8 s t 解 共有下列8种下料方案 一 线性规划的标准型 1 标准形式 注 标准型中要求bi 0 2单纯形法 1 MinZ CX MaxZ CX 2 约束条件 例如 9x1 4x2 360 9x1 4x2 x3 360 松弛变量 型约束 加松弛变量 型约束 减松弛变量 3 自由变量xj 进行变量替换 xj xj xj 其中xj xj 0 例 将如下问题化为标准型 得标准型 二 单纯形法的基本方法 基本方法 确定初始基可行解 检验是否最优 转到另一更好的基可行解 停 Y N 方法前提 模型化为标准型 并保证其他的基变量非负 基变量和非基变量 三 单纯形法的步骤 1 初始可行基B0的确定 若A中含有I B0 I若A中不含I 人工变量法 2 最优性检验 1 计算每个xj的检验数 2 若所有 j 0 则当前解为最优 否则 至少有 k 0 转3 注 1 基变量的检验数必为0 2 非基变量 的经济含义 非基变量取值由0变正 每增加一个单位 使目标值的增加量 3 换基迭代 基变换 得新基 计算新的基可行解 转2 保证新解的可行性 的计算 四 单纯形法的实现 单纯形表 12 0 0 0 单纯形表 7 90 的计算 40 30 枢纽元素 x3 x4 x2 30 0 3 1 0 0 0 1 50 2 5 0 0 1 0 5 240 7 8 0 1 0 0 4 3 4 0 0 0 1 2 30 8 20 100 x3 x1 x2 24 0 1 0 0 12 0 16 20 1 0 0 0 4 0 2 84 0 0 1 3 12 1 16 0 0 0 1 36 0 52 X 20 24 84 0 0 TZ 428 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 0 0 40 0 36 5 10 8 20 24 0 30 课堂练习 用单纯形法求解 X 6 0 8 0 TZ 6 联系用矩阵表示的单纯形法原理 单纯形表各部分内容可如下表示 3线性规划的对偶问题 DualProgramming 一 对偶问题的提出和模型 1 问题的提出 煤电油例 今有另厂要购买三种资源 在原厂可接受的条件下 单价多少可使另厂付费最低 设煤电油 价格 分别为y1 y2 y3 DUAL 以后将特别讨论这一 价格 的含义 2 原问题与对偶问题的对应关系 原问题 P 对偶问题 D Y为行向量 对称的对偶问题原问题与对偶问题形式上的对应关系原问题 P 对偶问题 D 目标max型目标min型有n个变量 非负 有n个约束 大于等于 有m个约束 小于等于 有m个变量 非负 价格系数资源向量资源向量价格系数技术系数矩阵技术系数矩阵的转置 1 对称性 二 对偶性质与定理 2 弱对偶性 设X Y分别为 P D 的任一可行解 则 一个线性规划的对偶问题的对偶问题恰是原问题 即 P 与 D 互为对偶 3 无界性 若原问题 P 无上界 则对偶问题 D 无可行解 同样 若对偶问题 D 无下界 则原问题 P 无可行解 注意 该命题的逆命题不成立 4 解的最优性 5 对偶定理 强对偶性 若 P 有最优解 则 D 也有最优解 且二者最优值相等 由该性质的证明中可以得到一个有用的结论 若原问题 P 有最优解 设最优基为B 则CBB 1是对偶问题 D 的最优解 6 互补松弛定理 若是原问题 P 的可行解 是对偶问题 D 的可行解 那么和分别是原问题 P 和对偶问题 D 的最优解的充要条件是 对于性质5 进一步联系单纯型表的矩阵表示 三 对偶问题最优解的经济解释 影子价格 Y y1 y2 ym 为对偶问题的最优解 则yi 表示在原问题LP模型最有解基础上 资源 右端项 bi对目标函数的边际贡献 即bi变化1个单位对目标函数产生的影响 称yi 为bi的影子价格 shadowprice 例如 煤电油例的对偶问题的最优解为Y 01 360 52 即煤电油三种资源的影子价格分别为0 1 36 0 52 它表明 在所求出的最优生产方案 甲生产20 乙生产24 资源煤剩余84 资源电和油无剩余 总收入428 基础上 资源煤增加1单位 目标函数值不变 资源电增加1单位 目标函数值相应增加1 36 资源油增加1单位 目标函数值相应增加0 52 由原问题所做推导 注意 对偶解 影子价格 的所有应用都是基于这一基本概念 影子价格在管理决策中的作用 1 影子价格 市场价格在以本章引例为代表的目标函数最大化毛收入这类模型中 2 影子价格反映了当前优化模型中资源的稀缺性 影子价格越高 则越稀缺 例如 煤的影子价格为0 则表明有剩余 电的影子价格为1 36 是三种资源中最大的 则表明电是相对重要的 3 在资源不变条件下 增加新产品是否合算的评价 见灵敏性分析 4线性规划的灵敏性分析 sensitivityanalysis 1 右端项b变化的分析 先看后两页图示 对于线性规划在其最优解基础上 设B为最优基 则由单纯形法 b的变化直接影响右端项 可行性 而不直接影响检验数 最优性 右端项变化示意1 某个右端项在一定范围变化 可能不影响最优解 右端项变化示意2 某个右端项在一定范围变化 影响最优解 但可能不影响最优基 2 价格系数C变化的分析 5 线性 整数规划IntegerProgramming 简称IP 一 整数规划的一般模型 LP maxz CXAX bX 0 IP maxz CXAX bX 0X为整数 整数规划的解法 分枝定界法或割平面法 基本思想是把一个整数规划问题化为一系列的线性规划问题来求解 整数规划的分类 纯整数规划 所有变量都限制为整数混合整数规划 仅部分变量限制为整数0 1整数规划 变量的取值仅限于0或1 例 人力资源分配的问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 解 设xi表示第i班次时开始上班的司机和乘务人员数 于是LP模型为 x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0且为整数 minz x1 x2 x3 x4 x5 x6 最优解 X 60 10 50 0 30 0 T Z 150 二 0 1整数规划 选址问题指派问题固定费用问题背包问题 1 投资场所的选址问题某城市拟在东 西 南三区设立商业网点 备选位置有A1 A7共7个 如果选Ai 估计投资为bi元 利润为ci元 要求总投资不超过B元 规定东区 A A2 A3中至多选2个西区 A4 A5中至少选一个南区 A6 A7中至少选一个问如何设点使总利润最大 maxz xi 0或1 i 1 7 x1 x2 x3 2 x4 x5 1 x6 x7 1 s t 课堂练习1 某钻井队要从S1 S10共10个井位中确定五个钻井探油 如果选Si 估计钻探费用为ci元 并且井位选择上要满足下列条件 1 或选择S1和S7 或选择S8 2 选择了S3或S4就不能选择S5 反过来也一样 3 在S5 S6 S7 S8中最多只能选两个 问如何选择井位使总费用最小 课堂练习1 某钻井队要从S1 S10共10个井位中确定五个钻井探油 如果选Si 估计钻探费用为ci元 并且井位选择上要满足下列条件 1 或选择S1和S7 或选择S8 2 选择了S3或S4就不能选择S5 反过来也一样 3 在S5 S6 S7 S8中最多只能选两个问如何选择井位使总费用最小 minz s t 或1 i 1 10 某篮球队有8名队员 其身高和专长如下表 现要选拔5名球员上场参赛 要求 1 中锋只有1人上场 2 后卫至少有一人上场 3 只有2号上场 6号才上场要求平均身高最高 应如何选拔队员 课堂练习2 maxz 或1 i 1 8 s t 某篮球队有8名队员 其身高和专长如下表 现要选拔5名球员上场参赛 要求 1 中锋只有1人上场 2 后卫至少有一人上场 3 只有2号上场 6号才上场要求平均身高最高 应如何选拔队员 2 指派问题 例 有一份中文说明书 需译成英 日 德 俄四种文字 分别记作任务E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种说明书所需的时间如下表所示 问应指派何人去完成何项任务 使所需总时间最少 问题描述 n项任务可由n个人完成 由于专长不同 各人完成各任务的时间也不同 求最优安排 要求 每人只能完成一项任务 每项任务只能由一人完成 x11 x12 x13 x14 1 甲只能干一项工作 x21 x22 x23 x24 1 乙只能干一项工作 x31 x32 x33 x34 1 丙只能干一项工作 x41 x42 x43 x44 1 丁只能干一项工作 x11 x21 x31 x41 1 E任务只能一人干 x12 x22 x32 x42 1 J任务只能一人干 x13 x23 x33 x43 1 G任务只能一人干 x14 x24 x34 x44 1 R任务只能一人干 xij 0或1 i j 1 2 3 4 minz 2x11 15x12 13x13 4x14 10 x21 4x22 14x23 15x24 9x31 14x32 16x33 13x34 7x41 8x42 11x43 9x44 课堂练习 P57例2 23 指派问题可以一般化表述为有n个人n项工作 已知第i个人做第j项工作的费用为cij 现如何分派任务 使一个人只做一项工作 一项工作只由一个人完成 而且总费用最小 以4个人4项工作的指派问题为例 该问题需用4 4 16个0 1变量 即设 把这些变量和已知费用系数分别排成一4 4矩阵 分别称为解矩阵和费用矩阵 3 固定费用问题 最基本的带有固定费用的费用函数一般表示为 若引入0 1变量 则带有固定费用的费用函数可表示为 固体废物处理规划例 教材P52例2 20 示意图 固定费用问题另例 例 生产三种型号的防寒服 其消耗资源及单件成本如表 此外 每种防寒服不管生产多少 都要支付一定的固定费用 今要生产500件防寒服 确定总费用最低的生产方式 一般描述 已知 生产某产品有m种方式 设第j种生产方式的固定成本为kj 可变成本为cj 问题 应选择哪几种生产方式 分别生产多少产量可使总成本最低 分析 这是一个混合0 1规划问题 设第j种生产方式的产量为xj 于是该问题可表示为 xj Myj 例