《管理运筹学》PPT课件

管理运筹学 管理科学方法 2 教材与参考书籍 教材 谢家平编著 管理运筹学 管理科学方法 中国人民大学出版社 2010参考书 Davidetal 数据 模型与决策 机械工业出版社 2004费雷德里克 数据 模型与决策 中国财政经济出版社 2004Jamesetal 数据 模型与决策 中国人民大学出版社 2006 3 32课时讲授提纲 绪论第一章线性规划第二章线性规划讨论第三章对偶规划静态规划第四章整数规划第五章目标规划第六章动态规划动态优化第七章网络分析第八章网络计划第九章决策分析第十章方案排序第十一章库存控制第十二章排队理论 离散优化 随机优化 淡化数学算法LINDO求解 4 考核方式 结课考试 笔试 开卷or闭卷 每章一题80 案例研究 选择合适方法结合企业实际进行应用20 5 管理运筹学的称谓 管理运筹学是一门研究如何最优安排的学科 OperationsResearch日本译作 运用学 香港 台湾译为 作业研究 我国译作 运筹学 源于古语 运筹帷幄之中 决胜千里之外 取 运筹 二字 体现运心筹谋 策略取胜ManagementScience管理科学运用数学 统计学和运筹学中的量化分析原理和方法 建立数学模型 计算机仿真 给管理决策提供科学依据 6 绪论 一 发展历史二 学科作用三 学科性质四 工作程序五 学科体系六 学习要求 7 一 发展历史 1 早期的运筹思想齐王赛马 渭修皇宫沈括运军粮 科学管理2 军事运筹学阶段20世纪40年代诞生于英美1940年 英国为对付德国空军的空袭 使用了雷达 但没有科学布局 效果不好 为解决这个问题 成立运筹学小组 称OperationalResearch 意为作战研究 美国和加拿大也在军队设立运筹学小组 称OperationsResearch 协助指挥官研究战略及战术问题 3 管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究 使运筹学在企业管理方面的应用得到了长足进展 8 企业的成功要素中 观念意识更新47 人文文化35 技术优势18 决策意识的科学性成功决策正确决策 二 学科作用 理念的重要性 9 二 学科作用 1 量化管理的重要性管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科 目的 用科学方法分析管理问题 为管理者决策提供依据目标 在企业经营内外环境的限制下 实现资源效用最大 量化管理是第一步 它导致控制 并最终实现改进如果不能量化某些事情 那么就不能理解它如果不能理解它 那么就不能控制它如果不能控制它 那么就不能改进它 H JamesHarrington 定性到定量分析 数量界限的重要性 量变引起质变 10 听一场音乐会 网络订票的票价500元 不去可退票情况1 在你马上要出发的时候 发现你把最近的价值500元的电话卡弄丢了 你是否还会去听这场音乐会 情况2 假设昨天花500元钱买一张今晚的音乐会取票单 在你出发时 发现把票单丢了 如果去听音乐会 就必须再花500元钱买张票 去还会不去 二 学科作用 2 量化思考使人理性冰淇淋实验 一杯A有70克 装在50克的杯子里 看上去要溢出了一杯B是80克 装在100克的杯子里 看上去还没装满 单独凭经验判断时 在相同的价格上 人们普遍选择A 实验表明 大部分的回答者仍旧会去听 结果却是 大部分人回答说不去了 11 二 学科作用 3 量化分析辅助决策盈亏平衡分析 利润 I P Cm Ch Q F策略1 差异化 领先者战略策略2 规模化 大规模市场策略3 机械化 第一利润源策略4 技能化 第二利润源策略5 信息化 第三利润源 12 二 学科作用 量化辅助决策案例 盈亏平衡分析例 某企业总销售额1100万元物料成本700万元员工工资200万元管理费用100万元现在利润 100万元 目标利润150万元 利润实现的方法有 将销售收入增加100 将员工工资减少25 将管理费用减少50 将物料成本减少7 1 13 二 学科作用 4 决策意识的重要性生产计划决策 一星期工作5天 每天正常工作8小时一周作业费用 11000 直接人工成本与间接费用 直接人工成本 10 1h 一台机器需一位作业人员 间接费用 人工成本2 5倍 14 二 学科作用 甲产品产量40 乙产品80 丙产品40利润 40 66 80 89 40 70 12560人员有限如何实现 采取什么薪酬制度 计件工资制 让员工自愿加班 决策的科学性 方案一 15 二 学科作用 甲产品产量40 乙产品80 丙产品40总收入 40 173 80 233 40 170 32360原料成本 40 65 80 95 40 65 12800营运费用 11000总利润 32360 12800 11000 8560人员有限如何实现 采取什么薪酬制度 岗位工资制 定岗定员 让员工自觉加班 决策的科学性 方案二 16 二 学科作用 决策的科学性 产能符合计算 乙与丙哪一个产品比较赚钱 E是瓶颈 17 二 学科作用 方案三 计时工资 且以单位利润率高低为决策意识 乙比较赚钱 假如80个全部生产需用E产能2400分钟 但是E只有2400分钟可用因此只能生产80个乙 2400 30 而丙无法生产 方案 甲产品40个 乙产品80个 丙产品0个总收入 40 173 80 233 0 170 25560原料 40 65 80 95 0 65 10200 营运费用 11000利润 25560 10200 11000 4360 方案四 计时工资 但以占用瓶颈资源大小为决策意识 丙比较赚钱 优先生产40个需用E产能600 40 15 分钟剩下1800分钟 可生产60个乙 1800 30 方案 甲产品40个 乙产品60个 丙产品40个总收入 40 173 60 233 40 170 27700原材料 40 65 60 95 40 6540 10900 营运费用 11000利润 27700 10900 11000 5800 18 三 学科性质 1 研究对象经济和管理活动中能用 数量关系 描述的如运营 规划与组织管理问题解决的理论模型和优化方法实践2 学科特点强调科学性和定量分析强调应用性和实践性强调从整体上进行把握 19 四 工作程序 20 五 学科体系 1 管理问题 21 五 学科体系 2 学科内容 22 五 学科体系 3 学科应用管理既是科学又是艺术低层管理的科学成分较多 高层管理的艺术成分较多运营管理需较多管理科学 人力资源管理需较多管理艺术例行管理需要较多管理科学 例外管理需要较多管理艺术 M 管理决策问题 MC 定量解决方法 方案选择依据 问题导向 技术支持 战略决策营销决策生产安排财务分析人力资源方案优选 应用统计线性规划整数规划目标规划网络计划网络分析决策分析动态规划 管理科学 运用合理的分析来改善决策的制定 管理者 制定决策 23 六 学习要求 1 学科地位 24 六 学习要求 经济学 企业战略 公司治理 会计学财务管理 人力资源管理组织行为学 管理科学方法支持 25 六 学习要求 2 如何学习 重点在结合实际的应用发挥自己管理实践经验丰富和理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化解决问题的方案或模型的解的分析与应用能力充分借用管理运筹学教学软件 26 第1章线性规划 Subtitle 内容提要 第一节线性规划的一般模型一 线性规划的三个要素二 线性规划模型的特征三 线性规划的图解方法四 线性规划解的可能性第二节线性规划的单纯形法一 线性规划的标准型式二 线性规划之解的概念三 单纯形法的基本原理 27 一 线性规划的三个要素 第一节线性规划的一般模型 决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数衡量决策优劣的准则 如时间最省 利润最大 成本最低目标函数是决策变量的线性函数有的目标要实现极大 有的则要求极小 28 二 线性规划模型的举例 第一节线性规划的一般模型 1 生产计划问题 例 某厂生产甲乙两种产品 生产工艺路线为 各自的零部件分别在设备A B加工 最后都需在设备C上装配 经测算得到相关数据如表所示 应如何制定生产计划 使总利润为最大 据市场分析 单位甲乙产品的销售价格分别为73和75元 试确定获利最大的产品生产计划 29 第一节线性规划的一般模型 1 决策变量 设x1为甲产品的产量 x2为乙产品的产量 2 约束条件 生产受设备能力制约 能力需求不能突破有效供给量 设备A的约束条件表达为2x1 16同理 设备B的加工能力约束条件表达为2x2 10设备C的装配能力也有限 其约束条件为3x1 4x2 32 3 目标函数 目标是企业利润最大化maxZ 3x1 5x2 4 非负约束 甲乙产品的产量为非负x1 0 x2 0 综上的LP模型 30 二 线性规划模型的举例 第一节线性规划的一般模型 2 物资运输问题 例 某产品商有三个供货源A1 A2 A3 其经销商有4个 需求市场 B1 B2 B3 B4 已知各厂的产量 各经销商的销售量及从Ai到Bj的单位运费为Cij 为发挥集团优势 公司要统一筹划运销问题 求运费最小的调运方案 31 第一节线性规划的一般模型 1 决策变量 设从Ai到Bj的运输量为xij 2 目标函数 运费最小的目标函数为minZ 6x11 3x12 2x13 5x14 7x21 5x22 8x23 4x24 3x31 2x32 9x33 7x34 3 约束条件 产量之和等于销量之和 故要满足 供应平衡条件 x11 x12 x13 x14 50 x21 x22 x23 x24 20 x31 x32 x33 x34 30 销售平衡条件 x11 x21 x31 20 x12 x22 x32 30 x13 x23 x33 10 x14 x24 x34 40 非负性约束xij 0 i 1 2 3 j 1 2 3 4 32 二 线性规划模型的举例 第一节线性规划的一般模型 3 产品配比问题 例 用浓度45 和92 的硫酸配置100吨浓度80 的硫酸 决策变量 取45 和92 的硫酸分别为x1和x2吨约束条件 求解二元一次方程组得解 非负约束 x1 0 x2 0 33 第一节线性规划的一般模型 若有5种不同浓度的硫酸可选 30 45 73 85 92 会如何呢 取这5种硫酸分别为x1 x2 x3 x4 x5 有 有多少种配比方案 何为最好 若5种硫酸价格分别为400 700 1400 1900 2500元 t 则 34 三 线性规划模型的特征 第一节线性规划的一般模型 1 模型隐含假定 1 线性化假定函数关系式f x c1x1 c2x2 cnxn 称线性函数 建模技巧 将非线性的函数进行分段线性化 2 同比例假定决策变量变化引起目标函数和约束方程的改变量比例 3 可加性假定决策变量对目标函数和约束方程的影响是独立于其他变量的 目标函数值是决策变量对目标函数贡献的总和 4 连续性假定决策变量取值连续 5 确定性假定所有参数都是确定的 不包含随机因素 35 三 线性规划模型的特征 第一节线性规划的一般模型 2 一般数学模型 用一组非负决策变量表示的一个决策问题 存在一组等式或不等式的线性约束条件 有一个希望达到的目标 可表示成决策变量的极值线性函数 36 四 线性规划的图解方法 第一节线性规划的一般模型 1 线性规划的可行域 可行域 满足所有约束条件的解的集合 即所有约束条件共同围城的区域 maxZ 3x1 5x22x1 162x2 103x1 4x2 32x1 0 x2 0 S t 37 四 线性规划的图解方法 第一节线性规划的一般模型 2 线性规划的最优解 目标函数Z 3x1 5x2代表以Z为参数的一族平行线 38 四 线性规划的图解方法 第一节线性规划的一般模型 3 线性规划解的特性 由线性不等式组成的可行域是凸多边形 凸多边形是凸集 凸集定义 集合内部任意两点连线上的点都属于这个集合 可行域有有限个顶点 目标函数最优值一定在可行域的边界达到 而不可能在其区域的内部 39 五 线性规划解的可能性 第一节线性规划的一般模型 1 唯一最优解 只有一个最优点 2 多重最优解 无穷多个最优解 当市场价格下降到74元 其数学模型变为 40 五 线性规划解的可能性 第一节线性规划的一般模型 3 无界解 可行域无界 目标值无限增大 缺乏必要约束 41 五 线性规划解的可能性 第一节线性规划的一般模型 4 没有可行解 线性规划问题的可行域是空集 约束条件相互矛盾 42 一 线性规划的标准型式 第二节线性规划的一般模型 1 标准型表达方式 1 代数式 2 向量式 3 矩阵式 A 技术系数矩阵 简称系数矩阵 B 可用的资源量 称资源向量 C 决策变量对目标的贡献 称价值向量 X 决策向量 43 一 线性规划的标准型式 第二节线性规划的一般模型 2 标准型转换方法 1 如果极小化原问题minZ CX 则令Z Z 转为求maxZ CX 2 若某个bi 0 则以 1乘该约束两端 使之满足非负性的要求 3 对于 型约束 则在左端加上一个非负松弛变量 使其为等式 4 对于 型约束 则在左端减去一个非负剩余变量 使其为等式 5 若某决策变量xk无非负约束 令xk x k x k x k 0 x k 0 44 二 线性规划之解的概念 第二节线性规划的一般模型 基矩阵 一个非奇异的子矩阵 线性无关 矩阵A中任意m列的线性无关子矩阵B 称为一个基 组成基B的列为基向量 用Pj表示 j 1 2 n 基变量 与基向量Pj相对应的m个变量xj称为基变量其余的n m个变量为非基变量 1 线性规划解之关系 基解 令所有非基变量等于零 得出基变量的唯一解 基变量是x3 x4 x5非基变量是x1 x2令非基变量x1 x2 0 得到一个基解x3 16 x4 10 x5 32 45 二 线性规划之解的概念 第二节线性规划的一般模型 1 线性规划解之关系 可行解 满足约束条件AX b X 0的解 可行基 可行解对应的基矩阵 基可行解 满足非负性约束的基解称为基可行解 最优解 使目标函数最优的可行解 称为最优解 最优基 最优解对应的基矩阵 称为最优基 46 二 线性规划之解的概念 第二节线性规划的一般模型 2 线性规划基本原理 定理1 若线性规划问题存在可行域 则其可行域一定是凸集 定理2 线性规划问题的基可行解对应可行域的顶点 定理3 若可行域有界 线性规划的目标函数一定可以在可行域的顶点上达到最优 定理4 线性规划如果有可行解 则一定有基可行解 如果有最优解 则一定有基可行解是最优解 47 二 线性规划之解的概念 第二节线性规划的一般模型 3 线性规划解题思路 先找到一个初始基可行解 也就是找到一个初始可行基 想办法判断这个基可行解是不是最优解 如果是最优解 就得到这个线性规划问题的最优解 如果判断出不是最优解 就想法由这个可行基按一定规则变化到下一个可行基 然后再判断新得到的基可行解是不是最优解 如果还不是 再接着进行下一个可行基变化 直到得到最优解 48 三 单纯形法的基本原理 第二节线性规划的一般模型 maxZ 3x1 5x2 0 x3 0 x4 0 x5 02x1 x3 162x2 x4 103x1 4x2 x5 32 49 三 单纯形法的基本原理 第二节线性规划的一般模型 最优解 X 4 5 8 0 0 T Z 37 50 三 单纯形法的基本原理 第二节线性规划的一般模型 单纯形的管理启示 2x1 16 X0 0 0 10 10 32 T X1 0 5 10 0 12 T X1 4 5 8 0 0 T 企业管理过程也是如此 把现有方案作为初始方案 找到最急需要改进的某个问题和改进方向 一次做好某个主要问题的解决与改进 一次只解决和改进一个问题的难度最小 解决之后 再寻求可以改进的其它地方 再次改进 不断地追求完美 51 第2章线性规划讨论 Subtitle 内容提要 第一节目标函数的描述技巧计件工资岗位工资计时工资第二节线性规划的适用层次第三节线性规划的典型案例第四节线性规划灵敏度分析价值系数的变动分析资源数量的变动分析 52 计件工资体系 目标是企业利润最大化 第一节目标函数的描述技巧 一 计件工资 计件工资制薪酬体系下 工作时间不会完全受每天8小时工作时间约束 但有产品市场需求约束 如下 经Lindo软件求解 得到最优解为Z 12560 产品甲x1 40 产品乙x2 80 产品丙x3 40 53 第一节目标函数的描述技巧 二 岗位工资 岗位工资制薪酬体系 以计时工资制为基础 实行定岗定员 总收入 173x1 233x2 170 x3 原料成本 65x1 95x2 65x3 营运费用 11000 则目标函数为maxZ 108x1 138x2 105x3 11000岗位工资制薪酬体系下 工作时间也不会完全受每天8小时工作时间约束 但有产品市场需求约束 如下 经Lindo软件求解 得到最优解为Z 8560 x1 40 x2 80 x3 40 54 第一节目标函数的描述技巧 三 计时工资 目标函数为 经Lindo软件求解 得到最优解为Z 5800 x1 40 x2 60 x3 40 市场需求约束 设备能力约束 55 第二节线性规划的适用层次 计划链的层次 产值计划或利润计划绝对数量或增长幅度期限 年度单位 万元 大类产品销售收入或台套产品品种和数量如何确定期限 年度单位 万台 具体产品在具体时段的出产计划合同订单和预测转换为生产任务 将产品出产计划转换成物料需求表 大类产品年度生产计划确定产品的品种和数量期限 年度单位 万台 56 第三节线性规划的典型案例 配送中心选择 例 某企业存在两个供货源 产地 已知原有供货源每月的供货能力是5万台产品 新增供货源的生产能力可以满足产品的需求 且两个货源的价格相同 有三个区域目标市场 销地或销售商 各销地每月的市场需求量为5万台 10万台 5万台 在分销渠道中 拟定在2个地点中选址设立分销中心 执行产品的转运任务 各地之间的单位运输物流成本 由距离和运输方式决定 57 第三节线性规划的典型案例 决策变量 设从供货源到分销中心的运输量为 从分销中心到需求市场的运输量为 选址规划在于二者的实际取值 如果 则不设置分销中心 反之 则设置 其规模为如果 则不设置分销中心 反之 则设置 其规模为目标函数 各条路段上的实际运输量乘以物流运输的单位费用之总和最小 即存在供应能力约束 市场需求约束 配送中转约束 如下 58 第三节线性规划的典型案例 供应能力平衡约束 市场需求平衡约束配送中心不存留产品所有变量大于等于零 59 第四节线性规划灵敏度分析 一 灵敏度分析的必要性 线性规划研究的是一定条件下的最优化问题资源环境和技术条件是可变的基础数据往往是测算估计的数值灵敏度分析的概念灵敏度分析又称敏感性分析或优化后分析研究基础数据发生波动后对最优解的影响最优解对数据变化的敏感程度在多大的范围内波动才不影响最优基灵敏度分析解决的问题 参数在什么范围变化而最优基不变已知参数的变化范围 考察最优解 最优基 是否改变 60 第四节线性规划灵敏度分析 一 价值系数的变动分析 非基变量Cj的变化范围非基变量Cj变化 只影响它自己的检验数 参数Cj的变化范围 价值系数Cj变化影响检验数 61 第四节线性规划灵敏度分析 一 价值系数的变动分析 基变量CBl的变化范围 62 第四节线性规划灵敏度分析 二 右端常量的变动分析 参数bi的变化范围第r个约束的右端项为br 增量 br 其它数据不变 新的基解为 只要X B 0 则可保持最优基不变 63 第3章对偶规划 Subtitle 内容提要 第一节对偶规划的数学模型对偶问题的提出对偶规划的性质第二节对偶规划的经济解释影子价值的内涵影子价值的应用第三节资源定价的决策案例 64 第一节对偶规划的数学模型 一 对偶问题的提出 若例1中该厂的产品平销 现有另一企业想租赁其设备 厂方为了在谈判时心中有数 需掌握设备台时费用的最低价码 以便衡量对方出价 对出租与否做出抉择 在这个问题上厂长面临着两种选择 自行生产或出租设备 首先要弄清两个问题 合理安排生产能取得多大利润 为保持利润水平不降低 资源转让的最低价格是多少 问题 的最优解 x1 4 x2 5 Z 37 65 第一节对偶规划的数学模型 一 对偶问题的提出 出让定价 假设出让A B C设备所得利润分别为y1 y2 y3原本用于生产甲产品的设备台时 如若出让 不应低于自行生产带来的利润 否则宁愿自己生产 于是有2y1 0y2 3y3 3同理 对乙产品而言 则有0y1 2y2 4y3 5设备台时出让的收益 希望出让的收益最少值 min 16y1 10y2 32y3显然还有y1 y2 y3 0 66 第一节对偶规划的数学模型 一 对偶问题的提出 例1的对偶问题的数学模型 对偶问题的最优解 y1 0 y2 1 2 y3 1 W 37两个问题的目标函数值相等并非偶然前者称为线性规划原问题 则后者为对偶问题 反之亦然 对偶问题的最优解对应于原问题最优单纯型法表中 初始基变量的检验数的负值 67 第一节对偶规划的数学模型 二 对偶规划的性质 1 对称性定理对偶问题的对偶问题是原问题 根据对偶规划 很容易写出对偶问题的对偶问题模型 2 最优性定理设 分别为原问题和对偶问题的可行解 且则 分别为各自的最优解 3 对偶性定理若原问题有最优解 那么对偶问题也有最优解 而且两者的目标函数值相等 4 互补松弛性最优解的充分必要条件是 68 第二节对偶规划的经济解释 一 影子价值的内涵 左边是资源bi每增加一个单位对目标函数Z的贡献 对偶变量yi在经济上表示原问题第i种资源的边际价值 对偶变量的值yi 表示第i种资源的边际价值 称为影子价值 若原问题价值系数Cj表示单位产值 则yi称为影子价格 若原问题价值系数Cj表示单位利润 则yi称为影子利润 影子价格 资源成本 影子利润 69 第二节对偶规划的经济解释 一 影子价值的内涵 影子价格不是资源的实际价格 反映了资源配置结构 其它数据固定 某资源增加一单位导致目标函数的增量 对资源i总存量的评估 购进or出让对资源i当前分配量的评估 增加or减少第一 影子利润说明增加哪种资源对经济效益最有利第二 影子价格告知以怎样的代价去取得紧缺资源第三 影子价格是机会成本 提示资源出租 转让的基价第四 利用影子价格分析新品的资源效果 定价决策第五 利用影子价格分析现有产品价格变动的资源紧性第六 可以帮助分析工艺改变后对资源节约的收益第七 可以预知哪些资源是稀缺资源而哪些资源不稀缺 70 第三节资源定价的决策方案 例 某厂生产甲乙产品 1 如何安排每周的利润为最大 2 如果企业可以不生产 那资源出让如何定价 一 最优生产决策 71 第三节资源定价的决策方案 二 资源获利决策 如果决策者考虑自己不生产甲乙两种产品 而把原拟用于生产这两种产品的原材料 设备工时 电量资源全部出售给外单位 或者做代加工 则应如何确定这三种资源的价格 设原材料的单位出让获利为y1 设备工时的单位出让获利为y3 电量的单位出让获利为y2 出让决策的线性规划模型 72 第4章整数规划 Subtitle 内容提要 第一节整数规划问题纯整数规划0 1规划混合整数规划第二节整数规划求解分枝定界法第三节整数规划应用 73 第一节整数规划问题 线性规划的决策变量取值可以是任意非负实数 但许多实际问题中 只有当决策变量的取值为整数时才有意义例如 产品的件数 机器的台数 装货的车数 完成工作的人数等 分数或小数解显然是不合理的 要求全部或部分决策变量的取值为整数的线性规划问题 称为整数规划 IntegerProgramming 全部决策变量的取值都为整数 则称为全整数规划 AllIP 仅要求部分决策变量的取值为整数 则称为混合整数规划 MixedIP 要求决策变量只取0或1值 则称0 1规划 0 1Programming 74 第一节整数规划问题 一 纯整数规划 例 某企业利用材料和设备生产甲乙产品 其工艺消耗系数和单台产品的获利能力如下表所示 问如何安排甲 乙两产品的产量 使利润为最大 解 设x1为甲产品的台数 x2为乙产品的台数 maxZ 6x1 5x22x1 x2 95x1 7x2 35x1 x2 0 x1 x2取整数 75 第一节整数规划问题 二 0 1规划 登山队员可携带最大重量为25公斤 问都带哪些物品的重要性最大 解 对于每一种物品无非有两种状态 带或者不带 不妨设 0 1规划的模型 76 第一节整数规划问题 三 混合整数规划 例 某产品有n个区域市场 各区域市场的需求量为bj吨 月 现拟在m个地点中选址建生产厂 一个地方最多只能建一家工厂 若选i地建厂 生产能力为ai吨 月 其运营固定费用为F元 月 已知址i至j区域市场的运价为cij元 吨 如何选址和安排调运 可使总费用最小 解 选址建厂与否是个0 1型决策变量 假设yi 1 选择第i址建厂 yi 0 不选择第i址建厂 计划从i址至区域市场j的运输运量xij为实数型决策变量 77 第二节整数规划求解 一 舍入化整法 为了满足整数解的要求 自然想到 舍入 或 截尾 处理 以得到与最优解相近的整数解 这样做除少数情况外 一般不可行 因为化整后的解有可能超出了可行域 成为非可行解 或者虽是可行解 却不是最优解 不考虑整数约束则是一个LP问题 称为原整数规划的松弛问题对于例1的数学模型 不考虑整数约束的最优解 x1 28 9 x2 25 9 Z 293 9 舍入化整x1 3 x2 3 Z 33 不满足约束条件5x1 7x2 35 非可行解 x1 3 x2 2 Z 28 满足约束条件 是可行解 但不是最优解 x1 4 x2 1 Z 29 满足约束条件 才是最优解 78 第二节整数规划求解 二 穷举整数法 对于决策变量少 可行的整数解又较少时 这种穷举法有时是可行的 并且也是有效的 但对于大型的整数规划问题 可行的整数解数量很多 用穷举法求解是不可能的 例如 指派问题 3 3 79 第二节整数规划求解 三 分支定界法 不考虑整数限制 先求出相应线性规划的最优解 若求得的最优解符合整数要求 则是原IP的最优解 若不满足整数条件 则任选一个不满足整数条件的变量来构造新的约束 在原可行域中剔除部分非整数解 依次在缩小的可行域中求解新构造的线性规划的最优解 直到获得原整数规划的最优解 定界的含义 IP是在相应的LP基础上增加整数约束IP的最优解不会优于相应LP的最优解对MaxZ 相应LP的Z 是原IP的上界 80 第二节整数规划求解 三 分支定界法 x1 3 x1 4 x2 2 x2 3 x1 2 x1 3 x2 3 x2 4 81 第三节整数规划应用 一 生产基地规划 例 某公司拟建设A B两种类型的生产基地若干个 两种类型的生产基地每个占地面积 所需经费 建成后生产能力及现有资源情况如下表所示 问A B类型基地各建设多少个 可使总生产能力最大 解 设A B两类基地各建设x1 x2个 则其模型为 82 第三节整数规划应用 二 人员安排规划 某服务部门各时段 每2小时为一时段 需要的服务人数如表 解 设第j时段开始时上班的服务员人数为xj第j时段来上班的服务员将在第j 3时段结束时下班 故决策变量有x1 x2 x3 x4 x5 按规定 服务员连续工作8小时 4个时段 为一班 请安排服务员的工作时间 使服务员总数最少 83 第三节整数规划应用 三 项目投资选择 有600万元投资5个项目 收益如表 求利润最大的方案 84 第三节整数规划应用 四 互斥约束问题 例如关于煤资源的限制 其约束条件为 企业也可以考虑采用天然气进行加热处理 这两个条件是互相排斥的 引入0 1变量y 令互斥问题可由下述的条件来代替 其中M是充分大的数 85 第三节整数规划应用 五 租赁生产问题 服装公司租用生产线拟生产T恤 衬衫和裤子 每年可用劳动力8200h 布料8800m2 假设 yj 1 要租用生产线jyi 0 不租用生产线j第j种服装生产量xj 86 第三节整数规划应用 六 任务指派问题 甲乙丙丁四个人 ABCD四项任务 如何指派总时间最短 解 引入0 1变量xij xij 1 任务j指派人员i去完成xij 0 任务j不派人员i去完成 一项任务只由一个人完成一人只能完成一项任务 87 第三节整数规划应用 七 设施选址问题 拟定在2个地点中选址设立分销中心 执行产品的仓储和转运 一个分销中心拟定设立一个仓库W1 W2 若设立仓库W1 建设成本为10万元 最大库容为20万台 单位产品的月库存成本为2元 若设立仓库W2建造成本为20万元 最大库容为25万台 单位产品的月库存成本为3元 如何选址和安排调运 建造费用 运输费用 仓储费用为最小 解 设从供货源Si到分销中心Wj的运输量为xij 从分销中心到需求市场Rk的运输量为yjk 仓库选址决策引入0 1变量wj 88 第三节整数规划应用 七 设施选址问题 供应能力平衡约束 市场需求平衡约束 仓储能力限制约束 分销中心不存留产品 所有变量大于等于零 89 第5章目标规划 Subtitle 内容提要 第一节多目标规划问题第二节目标规划数学模型目标的期望值正负偏差变量目标达成函数目标优先级别第三节目标规划的图解法第四节目标规划单纯形法第五节目标规划应用案例 90 第一节多目标规划问题 一 线性规划的局限性 线性规划的局限性只能解决一组线性约束条件下 某一目标而且只能是一个目标的最大或最小值的问题实际决策中 衡量方案优劣考虑多个目标生产计划决策 通常考虑产值 利润 满足市场需求等生产布局决策 考虑运费 投资 供应 市场 污染等这些目标中 有主要的 也有次要的 有最大的 有最小的 有定量的 有定性的 有互相补充的 有互相对立的 LP则无能为力目标规划 GoalProgramming 多目标线性规划含有多个优化目标的线性规划 91 第一节多目标规划问题 二 多目标规划的提出 例 甲乙产品的最优生产计划 解 线规划模型 maxZ 3x1 5x22x1 162x2 103x1 4x2 32x1 x2 0 根据市场需求 合同规定 希望尽量扩大甲产品减少乙产品产量 又增加二个目标 maxZ1 3x1 5x2maxZ2 x1minZ3 x22x1 162x2 103x1 4x2 32x1 x2 0 这些目标之间相互矛盾 一般的线性规划方法不能求解 92 第一节多目标规划问题 三 多目标规划的解法 加权系数法 为每一目标赋一权数 把多目标转化成单目标 但权系数难以科学确定 优先等级法 各目标按重要性归不同优先级而化为单目标 有效解法 寻求能照顾到各目标而使决策者感到满意的解 但可行域大时难以列出所有有效解的组合 目标规划法 对每一个目标函数引入正的或负的偏差变量 引入目标的优先等级和加权系数 93 第二节目标规划的数学模型 一 目标期望值 每一个目标希望达到的期望值 或目标值 理想值 根据历史资料 市场需求或上级部门的布置等来确定 二 偏差变量 目标约束 目标的实际值和期望值之间可能存在正的或负的偏差 正偏差变量dk 表示第k个目标超过期望值的数值 负偏差变量dk 表示第k个目标未达到期望值的数值 同一目标的dk 和dk 中至少有一个必须为零 引入正负偏差变量 对各个目标建立目标约束 软约束 94 第二节目标规划的数学模型 上例中要求 目标一是利润最大 拟定利润目标是30 目标二是减少乙产品产量但希望不低于4件 目标三是甲产品产量希望不少于6件 对各目标引入正 负偏差变量 3x1 5x2 d1 d1 30 x2 d2 d2 4x1 d3 d3 6 95 第二节目标规划的数学模型 三 目标达成函数 目标达成函数 偏差变量之和为最小值 若要求尽可能达到规定的目标值正负偏差变量dk dk 都尽可能小 即minSk dk dk 若希望尽可能不低于期望值 允许超过 负偏差变量dk 尽可能小 不关心超出量dk minSk dk 若允许某个目标低于期望值 但希望不超过正偏差变量dk 尽可能小 不关心低于量dk minSk dk 四 优先等级权数 目标重要度不同 用优先等级因子Pk表示第k等级目标 优先等级因子Pk是正的常数 Pk Pk 1 同一优先等级下目标的相对重要性赋以不同权数w 96 第二节目标规划的数学模型 例如P1级目标实现利润至少30元 P2级目标是甲乙产品的产量假设 乙产品产量不少于4件比甲产品产量不少于6件更重要 取其权重为2minG P1d1 P2 2d2 d3 3x1 5x2 d1 d1 30 x2 d2 d2 4x1 d3 d3 6x1 x2 dk dk 0 k 1 2 3 97 第三节目标规划的图解法 目标规划的图解法首先 按照绝对约束画出可行域 其次 不考虑正负偏差变量 画出目标约束的边界线 最后 按优先级别和权重依次分析各级目标 F G H x1 5 x2 4 98 第四节目标规划的应用案例 一 无穷多满意解 解 设x1 x2表示A B产品的产量 两个等级的目标 P1 充分利用电量限额 正负偏差之和为最小目标达成函数目标约束条件P2 利润额希望不能低于100元 负偏差最小目标达成函数目标约束条件 计划生产两种产品 首先要充分利用设备工时而不加班 然后考虑利润不低于100元 问应如何制定产品A B的产量 99 第四节目标规划的应用案例 一 无穷多满意解 由于材料供应限量为8单位 所以有系统约束条件 如下 该问题的目标规划模型如下 图解法求解如图 C G 100 第四节目标规划的应用案例 二 加班时间问题 例 某音像店有5名全职售货员和4名兼职售货员 全职售货员每月工作160小时 兼职售货员每月工作80小时 根据记录 全职每小时销售CD25张 平均每小时工资15元 加班工资每小时22 5元 兼职售货员每小时销售CD10张 平均工资每小时10元 加班工资每小时10元 现在预测下月CD销售量为27500张 商店每周开门营业6天 所以可能要加班 每出售一张CD盈利1 5元 商店经理认为 保持稳定的就业水平加上必要的加班 比不加班就业水平要好 但全职销售员如果加班过多 就会因为疲劳过度而造成效率下降 因此不允许每月加班超过100小时 建立相应的目标规划模型 101 第四节目标规划的应用案例 二 加班时间问题 首先 确定目标约束的优先级 如下 P1 下月的CD销售量达到27500张 P2 全职售货员加班时间不超过100小时 P3 保持全体售货员充分就业 对全职的要比兼职的加倍优先考虑 P4 尽量减少加班时间 对两种售货员区别对待 权重由他们对利润的贡献而定 其次 建立目标约束函数 1 销售目标约束 设全体全职售货员下月的工作时间x1 全体兼职售货员下月的工作时间x2 达不到销售目标的偏差d1 超过销售目标的偏差d1 102 第四节目标规划的应用案例 二 加班时间问题 2 正常工作时间约束 设全体全职售货员下月的停工时间d2 加班时间d2 全体兼职售货员下月的停工时间d3 加班时间d3 3 加班时间的限制 设全体全职售货员下月的加班不足100小时的偏差d4 加班超过100小时的偏差d4 两类售货员区别对待 权重比d2 d3 1 3 另一加班目标约束为 103 第四节目标规划的应用案例 二 加班时间问题 第三 按目标的优先级 写出相应的目标规划模型 运用LINGO软件求解得x1 900 x2 500 下月共销售CD盘27500张 获利27500 1 5 800 15 100 22 5 500 10 22000 104 第四节目标规划的应用案例 三 目标管理方案 例 某公司准备生产甲 乙产品 据市场调查 甲产品的最大市场需求3台 乙产品的最大市场需求2台 在满足现有电力资源严格供给约束的前提下 该厂长考虑两个目标 一是总利润不低于3600元 二是充分利用设备台时 但尽量少加班 问应如何制定产品甲 乙的产量 试建立其目标规划的数学模型 105 第四节目标规划的应用案例 三 目标管理方案 1 利润期望优先目标规划数学模型 运用图解法进行求解 F E G x1 8 x2 3 106 第四节目标规划的应用案例 1 利润期望优先 满意解 x1 8 x2 3设备能力 需求 30 8 60 3 420 实际 360实现目标P1和P2 降低甲乙产品的设备消耗 降低率 420 360 360 17 甲产品的设备消耗降为30 1 17 25 乙产品的设备消耗降为60 1 17 50 107 第四节目标规划的应用案例 三 目标管理方案 2 设备工时优先目标规划数学模型 运用图解法进行求解 F E G x1 8 x2 2 108 第四节目标规划的应用案例 2 设备工时优先 满意解 x1 8 x2 2利润总额300 8 400 2 3200 目标 3600不能提价 就必须降低成本以增加利润 利润增长率为12 5 甲产品的成本需要降为1200 300 1 12 5 862 5元 台 降低幅度4 2 乙产品的成本需要降为1800 400 1 12 5 1350元 台 降低幅度3 6 109 第7章网络分析 Subtitle 内容提要 第一节图论的概念第二节最小树问题第三节最短路问题第四节网络最大流第五节最小费用流 110 18世纪 哥尼斯堡城中有一条普雷格尔河 河上有七座桥将河中的两个小岛与河岸连接起来 人们提出了这样的问题 一个散步者能否从某地出发 走遍七桥且每座桥恰好经过一次 最后回到原地 第7章网络分析 陆地A 陆地B 岛D 岛C A D B C 1736年瑞士数学家欧拉将两岸和小岛抽象为四个点 将桥抽象为七条边 此问题归结为一笔画问题 111 第一节图论的概念 一 图的内涵 1 图的定义 v1 v4 v2 v3 e1 e2 e3 e4 e5 e6 v1 v4 v2 v3 e1 e2 e3 e4 e5 e6 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 图论的图与一般几何图形或代数函数图形是完全不同的图论中的图 由一些点和连接点的线所组成的 图形 点和线的位置是任意的线的曲直 长短与实际无关 代表的只是点与点之间的相互关系例 表示苏州v1 杭州v2 上海v3 南京v4仓储网点之间的物流运输线路关系 112 第一节图论的概念 一 图的内涵 2 图的分类 不带箭头的连线称为 边 如公路运输线路 带箭头的连线称为 弧 如供排水的管道运输线路 1 无向图 由点和边的集合所构成 由点和弧的集合所构成 2 有向图 链 无向网络中 前后相继点和边的交替序列称为一条链 圈 闭合的链称为一个圈 路径 有向网络图中 前后相继并且方向一致的点弧序列称为一条路径 回路 闭合的路径称为一个回路 113 第二节最小树问题 例 一家企业分别要在6间办公室铺设网线接入口 网线的可行走线方式如下图所示 如何铺设网线才能使网线总长为最短 最短网线总长度为最小树权之和2 3 4 6 6 21 8 2 3 5 4 6 6 6 8 v1 v4 v2 v3 v5 v6 无圈的连通图就是一棵树 权数总和为最小的那棵支撑树 称为最小树 求解方法 破圈法避圈法 114 第三节最短路问题 一 双标号算法 狄克斯特拉 Dijkstra 算法路权 弧 vi vj 的权为wij 路权是路p中各条弧权之和最短路 在所有从vs到vt的路p中 求一条路权最短的路算法说明 1959年提出 目前公认的最短路算法适合于求解所有弧权wij 0的最短路问题算法假设 有向图D是完备图图D中任意两点vi vj之间 恰有两条弧 vi vj 和 vj vi 若vi vj不存在弧 可设想一条从vi vj的弧 权wij 若vi vj有重复的弧 则保留弧权最小的弧 115 第三节最短路问题 一 双标号算法 基本思路 从始点vs出发 逐步探寻 给每个点标号 标号分永久标号P vk 和临时标号T vk 两种 永久标号P vk 是从点vs vk的最短路权临时标号T vk 是从点vs vk最短路权的上界算法的每一步从临时标号集中选最小者变为永久标号 经过逐次改变 就可以得到从点vs到各点的最短路 标号形式 单标号法是对每一点赋予一个路权标号双标号法是对每一点赋予两个标号 路标 路权 116 第三节最短路问题 一 双标号算法 例 用双标号法求下图网络最短路 3 9 4 7 3 2 6 1 4 1 2 8 7 1 10 117 第三节最短路问题 一 双标号算法 第一步 3 9 4 7 3 2 6 1 4 1 2 8 7 1 10 118 第三节最短路问题 一 双标号算法 第二步 3 9 4 7 3 2 6 1 4 1 2 8 7 1 10 119 第三节最短路问题 一 双标号算法 第三步 3 9 4 7 3 2 6 1 4 1 2 8 7 1 10 120 第三节最短路问题 一 双标号算法 最终 依此类推 重复上述标号过程 得最短路 3 9 4 7 3 2 6 1 4 1 2 8 7 1 10 121 第三节最短路问题 二 最短路的应用 1 网络的中心 所谓网络的中心是指一个网络中 选择某一点 使之其余各点到该中心点的距离之和为最小 例 如果要在下表中6个销售点中选一个作为仓库所在地 应该建在哪个经销点 使其余各销售点都离它较近 122 第三节最短路问题 二 最短路的应用 2 网络的重心 引进点的权系数 将权系数与最短距离阵各列对应元素加权求和 再从中选择最小的即为网络重心 123 第四节网络最大流 一 相关概念与定理 1 弧容量与容量网络 对于有向图D V A 弧的容量表示弧的最大流通能力 在V中指定一点称为发点 记为vs 另一点称收点 记为vt 其余点叫中间点 这样的赋权有向图就称为一个容量网络 记N V A B 2 弧的流量与可行流 弧的实际通过量称为该弧的流量 弧集A上的流量集合称为网络上的流 满足下述条件的流称为可行流 容量限制 对每条弧 都有 平衡条件 中间点流出量 流入量 124 第四节网络最大流 一 相关概念与定理 3 前向弧与后向弧 4 饱和弧与非饱和弧 弧的流量与之容量比较 满足的弧称为饱和弧 弧的流量不能再扩充 满足的弧称为非饱和弧 弧的流量允许再被扩大 是从vs到vt的链 方向从vs vt 则链 上的弧分为两类前向弧 弧的方向与链 的方向相同 记 后向弧 弧的方向与链 的方向相反 记 5 零弧与非零弧 满足的弧称为零弧 由于 所以弧的流量不能减小 满足的弧称为非零弧 弧的流量可以被减小 但要满足0 125 第四节网络最大流 一 相关概念与定理 6 流量可以扩充的路 设是一可行流 是从vs到vt的链 若链 满足 上的所有前向弧为非饱和弧 即满足 可以扩充流量 上的所有后向弧为非零弧 即满足 可以减少流量 则称是一条关于可行流的可扩充流量的路 亦称增广链 7 流量可以扩充的路 可行流中 网络发点的流出量 或网络收点的流入量 就是网络的流量 一个容量网络的诸可行流中 网络流量最大的可行流 称为最大流 126 第四节网络最大流 二 求最大流标号法 1956年 福特和富尔克逊提出了寻求网络最大流的基本方法 称为福特 富尔克逊算法 Fold FulkersonAlgorithm 给定可行流X xij 标号判断有无增广链 先给vs标上 vs vs已标号尚未检查 其余未标号 取一个已标号但未检查的点vi进行检查 对未标号点vj 前向