1绪论2图解法3计算机法4应用.ppt

1 管理 运筹学 主讲人 张强博士教授博导北京理工大学管理与经济学院管理科学与工程系系主任E mail qiangzhang Tel 68912844 O 2 教材与参考书 1 韩伯棠 管理运筹学 高等教育出版社 2000 第一版 2005 第二版 2 吴祈宗 运筹学 机械工业出版社 2002 第一版 2006 第二版 3 吴祈宗 运筹学与最优化方法 机械工业出版社 2002 3 3 钱颂迪等 运筹学 第三版 清华大学出版社 2005 4 胡运全等 运筹学教程 第二版 清华大学出版社 2003 5 胡运全 运筹学习题集 第三版 清华大学出版社 2002 6 刁在筠等 运筹学 第三版 高等教育出版社 2002 4 线性规划 运输问题 整数规划目标规划动态规划图与网络规划排序与统筹方法存贮论排队论对策论决策分析预测 5 第一章绪论 运筹学是一门应用科学 至今没有统一的定义 据 大英百科全书 释义 运筹学是一门应用于管理有组织系统的科学 运筹学为掌管这类系统的人提供决策目标和数量分析的工具 6 中国大百科全书的释义为 运筹学 用数学方法研究经济 民政和国防等部门在内外环境的约束条件下合理分配人力 物力 财力等资源 使实际系统有效运行的技术科学 它可以用来预测发展趋势 制定行动规划或优选可行方案 7 中国管理百科全书的释义为 运筹学是应用分析 试验 量化的方法 对经济管理系统中的人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 运筹学有广泛的应用 它的产生和发展历史悠久 8 运筹学的思想方法在我国古代有过不少的记载 例如齐王赛马 丁渭修皇宫和沈括运军粮的故事就充分说明了我国不仅很早就有过朴素的运筹思想 而且在生产实践中实际运用了运筹方法 但是 运筹学作为一门新兴的学科是在第二 9 次世界大战期间出现的 当时英美成立了 运作研究 小组 通过科学方法的运用成功地解决了许多非常复杂的战略和战术问题 例如 如何合理运用雷达有效地对付德军的空袭 对商船队如何进行编队护航 在船队遭受德国潜艇攻击时使船队损失最少 在各种情况下如何调整反潜深水炸弹的爆炸深度 才能增如对德国潜艇的杀伤力等 10 运筹学一词起源于20世纪30年代 在英国称为OperationalResearch 在美国称为OperationsResearch 可直译为 运用研究 作业研究 运作研究 1957年 我国科技工作者从 夫运筹帷幄之中 决胜千里之外 见 史记 高祖本记 这句古语中摘取 运筹 二字 将OR正式译作运筹学 11 目前国际国内的运筹学组织有美国 英国 法国 印度 日本 荷兰 比利时等10国的运筹学会InternationalFederationofOperationsResearchSocieties IFORS 国际运筹学联合会 1959 国际运筹与管理科学协会 INFORMS 中国运筹学会 1980北京运筹学会 1986 1994 在北京工业学院 12 目前国际国内著名的运筹学刊物有ManagementScienceOperationsResearchInterfacesJournalofOperationalResearchSocietyEuropeanJournalofOperationsResearch运筹学学报运筹与管理 13 1决策 定量分析与管理运筹学 决策过程 问题解决的过程 1 提出问题 认清问题2 寻求可行方案 建模 求解3 确定评估目标及方案的标准或方法 途径4 评估各个方案 解的检验 灵敏性分析等5 选择最优方案 决策6 方案实施 回到实践中7 后评估 考察问题是否得到完满解决1 2 3 形成问题 4 5 分析问题 定性分析与定量分析 构成决策 14 2运筹学的分支 线性规划非线性规划整数规划动态规划多目标规划图与网络分析排队论 对策论决策分析存储论排序与统筹方法可靠性理论模型论投入产出分析 随机规划 模糊规划等 15 3运筹学在工商管理中的应用 生产计划 生产作业的计划 日程表的编排 合理下料 配料问题 物料管理等库存管理 多种物资库存量的管理 库存方式 库存量等运输问题 确定最小成本的运输线路 物资的调拨 运输工具的调度以及建厂地址的选择等人事管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等市场营销 广告预算 媒介选择 定价 产品开发与销售计划制定等财务和会计 预测 贷款 成本分析 定价 证券管理 现金管理等 设备维修 更新 项目选择 评价 工程优化设计与管理等 16 运筹学方法使用情况 美1983 17 运筹学方法在中国使用情况 随机抽样 18 运筹学的推广应用前景 据美劳工局1992年统计预测 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73 增长速度排到各项职业的前三位 结论 运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企业推广运筹学方面有大量的工作要做 19 4如何学习运筹学 MBA学员学习运筹学要把重点放在结合实际的应用上 不要被一些概念 理论的困难吓倒 要用好计算机这个强有力的工具 MBA学员学习运筹学要充分发挥自己实践经验丰富和理论联系实际能力强的优势 MBA学员学习运筹学要把注意力放在 入口 和 出口 两头 中间过程尽可能让计算机软件去完成 入口 即结合实际问题建立运筹学模型 出口 即解决问题的方案或模型的解 本书附有运筹学教学软件 使用方法很简单 MBA学员必须尽快学会使用这个运筹学教学软件 并借助它来学好本课程 20 第二章线性规划的图解法 在管理中一些典型的线性规划应用合理利用线材问题 如何下料使用材最少配料问题 在原料供应量的限制下如何获取最大利润投资问题 从投资项目中选取方案 使投资回报最大产品生产计划 合理利用人力 物力 财力等 使获利最大劳动力安排 用最少的劳动力来满足工作的需要运输问题 如何制定调运方案 使总运费最小 21 1问题的提出 例1 某工厂在计划期内要安排甲 乙两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗以及资源的限制 如下表 问题 工厂应分别生产多少单位甲 乙产品才能使工厂获利最多 线性规划模型 设生产甲产品x1个单位 生产乙产品x2个单位 目标函数 maxz 50 x1 100 x2约束条件 s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 22 线性规划问题是在一组线性等式或不等式的约束之下 求一个线性函数的最大值或最小值的问题 它由以下部分组成 目标函数maxz或minf约束条件s t subjectto 满足于决策变量用符号xj等来表示可控制的因素 23 线性规划模型 一般形式目标函数 max min z c1x1 c2x2 cnxn 2 1 约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 2 2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2 3 24 这是线性规划数学模型的一般形式 其中 式 2 1 称为目标函数 它只有两种形式 Max或Min 式 2 2 称为约束条件 它们表示问题所受到的各种条件 一般有三种形式 大于等于 小于等于 这两种情况又称不等式约束 或 等于 又称等式约束 式 2 3 称为非负约束条件 很多情况下决策变量都蕴含了这个假设 它们在表述问题时常常不一定明确指出 建模时应该注意这个情况 在实际当中 有些决策变量允许取任何实数 如温度变量 资金变量等 这时不能人为地强行限制其非负 25 在线性规划模型中 也直接称z为目标函数 称xj j 1 2 n为决策变量 称cj j 1 2 n为目标函数系数或价值系数或费用系数 称bi i 1 2 m为约束右端常数或简称右端项 也称资源常数 称aij i 1 2 m j 1 2 n为约束系数或技术系数 这里 cj bi aij均为常数 26 可以看出 线性规划模型有如下特点 1 决策变量x1 x2 xn表示要寻求的方案 每一组值就是一个方案 2 约束条件是用等式或不等式表述的限制条件 3 一定有一个追求目标 或希望最大或希望最小 4 所有函数都是线性的 27 2线性规划的图解法 例1 目标函数 maxz 50 x1 100 x2约束条件 s t x1 x2 300 E 2x1 x2 400 G x2 250 F x1 0 x2 0 28 一个线性不等式确定一个半平面 如不等式 E x1 x2 300确定的半平面为 29 30 31 5个半平面的交得到可行域 32 考查目标函数等值线图2 2 33 解联立方程组x1 x2 300 E x2 250 F 得最优解为 x1 50 x2 250 最优目标值为 z 27500 34 线性规划图解法的步骤 对于只有两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 其步骤如下 1 分别取决策变量x1 x2为坐标向量建立直角坐标系 35 2 对每个不等式 约束条件 先取其等式在坐标系中作直线 然后确定不等式所决定的半平面 若各半平面交出来的公共区域存在 显然 其中的点满足所有的约束条件 我们称这样的点为此线性规划的可行解 全体可行解的集合称为可行集或可行域 若这样的公共区域不存在 则该线性规划问题无可行解 36 3 任意给定目标函数一个确定的值 作出对应的目标函数等值线 并确定该族等值线平行移动时目标函数值增加 减少 的方向 然后平移目标函数的等值线 使其达到既与可行域有交点又不可能使值再增加 减少 的位置 有时交于无穷远处 此时称无有限最优解 此时 目标函数等值线与可行域的交点即此线性规划的最优解 一个或多个 此目标函数的值即最优值 37 线性规划解的性质 1 线性规划的最优解如果存在 则必定有一个顶点 极点 是最优解 2 有的线性规划问题存在无穷多个最优解的情况 如将例1中的目标函数变为求maxz 50 x1 50 x2 3 有的线性规划问题存在无有限最优解的情况 也称无解 见P16 15 3 和P17 16 图2 3 4 有的线性规划问题存在无可行解的情况 见P16 15 4 38 例1解的进一步讨论 把最优解x1 50 x2 250代入约束条件可知 设备台时数及原料B都恰好消耗完 而原料A则还剩余50千克 为此我们引入松驰变量 含义是资源的剩余量 s1 s2 s3 则例1的模型可写成目标函数 maxz 50 x1 100 x2 0s1 0s2 0s3约束条件 s t x1 x2 s1 3002x1 x2 s2 400 x2 s3 250 x1 x2 s1 s2 s3 0 求得最优解为 x1 50 x2 250 s1 0s2 50s3 0 39 线性规划的标准形式目标函数 maxz c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 40 线性规划的标准形式有如下四个要求 目标最大化 目标最小化 约束方程为等式决策变量为非负右端项为非负对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 41 1 极小化目标函数的问题 设目标函数为minf c1x1 c2x2 cnxn 可以 令z f 则该极小化问题与下面的极大化问题有相同的最优解 即maxz c1x1 c2x2 cnxn 但必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 即minf maxz 42 2 约束条件不是等式的问题 设约束条件为ai1x1 ai2x2 ainxn bi可以引进一个新的变量s 使它等于约束右边与左边之差s bi ai1x1 ai2x2 ainxn 显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 43 当约束条件为ai1x1 ai2x2 ainxn bi时 类似地令s ai1x1 ai2x2 ainxn bi 显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 44 为了使约束由不等式成为等式而引进的变量s 当不等式为 小于等于 时称为 松弛变量 当不等式为 大于等于 时称为 剩余变量 如果原问题中有若干个非等式约束 则将其转化为标准形式时 必须对各个约束引进不同的变量 有时也将它们统称为松弛变量 45 例 将以下线性规划问题转化为标准形式minf 3 6x1 5 2x2 1 8x3s t 2 3x1 5 2x2 6 1x3 15 74 1x1 3 3x3 8 9x1 x2 x3 38x1 x2 x3 0解 首先 将目标函数转换成极大化 令z f 3 6x1 5 2x2 1 8x3 46 其次考虑约束 有2个不等式约束 引进松弛变量x4 x5 0 于是 我们可以得到以下标准形式的线性规划问题 maxz 3 6x1 5 2x2 1 8x3s t 2 3x1 5 2x2 6 1x3 x4 15 74 1x1 3 3x3 x5 8 9x1 x2 x3 38x1 x2 x3 x4 x5 0 47 3 变量无符号限制的问题 在标准形式中 必须每一个变量均有非负约束 当某一个变量xj没有非负约束时 可以令xj xj xj 其中xj 0 xj 0即用两个非负变量之差来表示一个无符号限制的变量 当然xj的符号取决于xj 和xj 的大小 48 4 右端项有负值的问题 在标准形式中 要求右端项必须每一个分量非负 当某一个右端项系数为负时 如bi 0 则把该等式约束两端同时乘以 1 得到 ai1x1 ai2x2 ainxn bi 49 例将以下线性规划问题转化为标准形式minf 3x1 5x2 8x3 7x4s t 2x1 3x2 5x3 6x4 284x1 2x2 3x3 9x4 396x2 2x3 3x4 58x1 x3 x4 0 50 解 首先 将目标函数转换成极大化 令z f 3x1 5x2 8x3 7x4 其次考虑约束 有3个不等式约束 引进2个松弛变量和1个剩余变量x5 x6 x7 0 由于x2无非负限制 引入两个非负变量 可令x2 x2 x2 其中x2 0 x2 0 由于第3个约束右端项系数为 58 于是把该式两端乘以 1 于是 我们可以得到以下标准形式的线性规划问题 51 maxz 3x1 5x2 5x2 8x3 7x4s t 2x1 3x2 3x2 5x3 6x4 x5 284x1 2x2 2x2 3x3 9x4 x6 39 6x2 6x2 2x3 3x4 x7 58x1 x2 x2 x3 x4 x5 x6 x7 0 作业 P24 22 1 2 3 4 5 52 例2 某公司由于生产需要 共需要A B两种原料至少350吨 A B两种材料有一定替代性 其中A原料至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨A原料需要2个小时 加工每吨B原料需要1小时 而公司总共有600个加工小时 又知道每吨A原料的价格为2万元 每吨B原料的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 53 求使购进成本最低的x1和x2 解 问题的线性规划模型为目标函数 minf 2x1 3x2约束条件 x1 x2 350 x1 1252x1 x2 600 x1 0 x2 0 54 用图解法解此题 图2 4 2x1 3x2 600 55 例2的线性规划标准型为目标函数 maxz 2x1 3x2 0s1 0s2 0s3约束条件 x1 x2 s1 350 x1 s2 1252x1 x2 s3 600 x1 x2 s1 s2 s3 0 56 3图解法的灵敏度分析 灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析 在建立数学模型和求得最优解后 当线性规划的一个或多个参数 系数 cj aij bi变化时 问题的最优解会有什么变化 或者这些参数在一个多大范围内变化时 问题的最优解不变 这就是灵敏度分析所要研究解决的问题 57 当然 当线性规划问题中的一个或几个参数 系数 变化时 我们可以重新计算新问题的最优解 看最优解有无变化 但是 这样做有时既麻烦又没有必要 以下只介绍图解法的灵敏度分析法 1 对目标函数中的系数cj进行灵敏度分析 2 对约束条件中的右端常数项bi进行灵敏度分析 58 3 1目标函数中的系数cj的灵敏度分析 由图解法可知 在可行域 即约束条件 不变的情况下 线性规划问题的最优解一般随目标函数等值线z c1x1 c2x2的斜率变化而变化 上式的斜截式为x2 c1 c2 x1 z c2 或直接考虑 目标函数等值线的 斜率 c1 c2 59 在例1中图2 5 60 以下研究对最优解不变的参数 系数 范围 考虑例1的情况 目标函数等值线为z 50 x1 100 x2 从图2 5可以看出 当目标函数的斜率在直线 F z x2 x2 z斜率为0 到直线 E z x1 x2 x2 x1 z斜率为 1 的斜率之间变化时 原最优解x1 50 x2 250仍是其最优解 即当c1 c2满足 1 c1 c2 0 时 原最优解仍是其最优解 61 为了求c1和c2的范围 我们分别考虑 1 若产品乙的利润100元不变 即c2 100 代入式 并整理得0 c1 100 2 若产品甲的利润50元不变 即c1 50 代入式 并整理得50 c2 在上述c1 或c2 的范围内 最优解x1 50 x2 250仍是其对应的目标函数系数线性规划的最优解 62 此外 如果产品甲 乙的利润同时改变 则也可以用式 来判断B点是否仍为最优解 例如产品甲 乙的利润分别为c1 60元 c2 55元 因为 c1 c2 60 55 1 不满足式 可知B点已不再是其最优解 但有 2 直线G的斜率 60 55 1 直线E的斜率 所以 此时最优解为C点 即直线x1 x2 300和2x1 x2 400的交点x1 100 x2 200 63 3 2约束条件中右边系数bi的灵敏度分析 当约束条件中右边系数bi变化时 线性规划的可行域发生变化 可能引起最优解的变化 考虑例1的情况 假设设备台时增加10个台时 即b1变化为310 则约束条件E变为x1 x2 310 这时可行域扩大了 见p22 21 图2 6 由图解法知 最优解为x2 250和x1 x2 310的交点x1 60 x2 250 64 变化后的总利润 变化前的总利润 增加的利润 50 60 100 250 50 50 100 250 500 平均每台时增加500 10 50元利润 这说明在一定范围内每增加 减少 1个台时的设备能力就可增加 减少 50元利润 像这样在约束条件右边常数项增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格 从上面的讨论可知 设备对偶价格为50元 1台时 即在一定范围内增加或减少X个台时 则总利 65 润将增加或减少X个50元 又假设原料A增加10千克时 即b2变化为410 这时可行域扩大 见p23 22 图2 7 最优解仍为x2 250和x1 x2 300的交点x1 50 x2 250 此变化对总利润无影响 该约束条件的对偶价格为0 解释 原最优解并没有把原料A用尽 还有50千克的剩余 因此 如果再增加10千克原料 也只不过增加了库存而已 而不会增加利润 66 总结 在一定范围内 当约束条件右边常数增加1个单位时1 若约束条件的对偶价格大于0 则其最优目标函数值变好 即 求最大值时变得更大 求最小值时变得更小 2 若约束条件的对偶价格小于0 则其最优目标函数值变坏 即 求最大值时变得更小 求最小值时变得更大 3 若约束条件的对偶价格等于0 则其最优目标函数值不变 作业 P24 25 6 7 8 67 第三章线性规划问题的计算机求解 管理运筹学软件1 0版使用说明一 系统的进入与退出1 在WINDOWS环境下直接运行main exe文件 或者在DOS下UCDOS中文平台环境下运行 也可直接运行各可执行程序 2 退出系统的方法可以在主菜单中选退出项 也可按Ctrl Break键直接退出 68 3 在WINDOWS环境下直接运行软件 如果出现乱码 那是因为启用了全屏幕方式 解决办法是按Alt Enter键 即可转换成非全屏的界面 一般就会消除乱码 如果还是乱码 可以点击菜单的 汉 选项 若要每次启动程序都没有乱码 则需要修改屏幕设置的相应属性 具体方法是 在非全屏界面下点击菜单的 属性 选项 再选择 窗口 选项 然后选中其中的 窗口 项 并取消 启动时恢复设置 项 这样就可保证每次运行软件时以非全屏方式显示 69 二 输入注意事项1 英文字母输入要大写 如x1的输入为X1 2 用 号代替 号 用 2 而不是X1 2 3 输入的数据只能是整数或小数 不能是分数 4 输入前要先合并同类项 如2x2 3x2 要一次性输入5X2 不能输入2X2 3X2 70 5 线性规划 整数规划的目标函数和约束条件的输入必须严格按由小到大的序号顺序输入 同时约束变量必须放在运算符的左侧 如x1 x2 x3 0 的输入为X1 X2 X3 0 不能输为X2 X3 X1 0 或X1 X2 X3 6 当约束条件都输入完之后 在下一个约束条件后输入 END 71 例1数学模型maxz 50 x1 100 x2s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 输入形式目标函数 MAX50X1 100X2变量个数 2输入第一个约束 X1 X2 300输入第二个约束 2X1 X2 400输入第三个约束 X2 250输入第四个约束 END 演示例1 72 三 计算结果 输出 解释 分析 1 目标函数最优值为 275002 变量最优解相差值x1500 x22500相差值 在最优解中 如果某一决策变量xj 0 则目标函数系数cj需要改进相差值的数量 才有可能使新的最优解中的xj 0 当最优解中的决策变量已 73 取正值时 则相差值为0 如 在最优解中 决策变量x1 0 x1对应的相差值为20 目标系数的当前值为c1 50 则在求解最大 小 目标值时 c1调整为50 20 50 20 新的线性规划中的最优解x1才有可能大于0 74 3 约束松弛 剩余变量对偶价格105025003050对偶价格 bi的灵敏度分析 即bi增加一个单位 目标函数值增加 改进 对偶价格数量个单位 75 4 目标函数系数范围 变量下限当前值上限x1050100 x250100无上限目标函数系数cj的灵敏度分析 当目标函数系数cj单一的在上下限范围内变化 取值 时 其对应的 目标函数系数 线性规划的最优解不变 76 5 常数项范围 约束下限当前值上限12503003252350400无上限3200250300约束条件右边常数项bi的灵敏度分析 当约束条件中右边系数bi在上下限范围内变化 取值 时 其对应的线性规划的对偶价格不变 77 四 百分之一百法则以上计算机输出的关于目标函数系数和约束条件右边值的灵敏度分析都是基于这样一个重要假设 只有一个系数在变化 而其他的系数值保持不变 所有以上的目标函数系数及约束条件右边值的变化范围只适合于单个系数变化的情况 那么当两个或更多的系数都发生变化时 我们怎么来进行灵敏度分析呢 下面介绍解决这一问题的一个方法 百分之一百法则 78 定义目标函数系数cj和约束条件右边常数项bi的允许增加量 上限 当前值 允许减少量 当前值 下限 允许增加百分比 增加量 允许增加量 允许减少百分比 减少量 允许减少量 仍以例1c1的允许增加量为100 50 50 为例p30c2的允许减少量为100 50 50 如果c1由50变为74 c2由100变为78 则c1的允许增加百分比 74 50 50 48 c2的允许减少百分比 100 78 50 44 79 百分之一百法则 目标函数决策变量系数的百分之一百法则 对于所有变化的目标函数决策变量系数 当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时 最优解不变 约束条件右边常数项的百分之一百法则 对于所有变化的约束条件右边常数值 当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时 则其对偶价格不变 80 例 c1由50变为74 c2由100变为78 则c1的允许增加百分比 74 50 50 48 c2的允许减少百分比 100 78 50 44 c1的允许增加百分比 c2的允许减少百分比 48 44 92 故最优解不变 但此时的最大利润为23200 元 81 又 b1由300变为315 b2由400变为390 b3由250变为240 则 315 300 25 400 390 50 250 240 50 100 故对偶价格不变 但最大利润增加了50 15 0 10 50 10 250元 为27750元 82 解系数改变的线性规划maxz 50 x1 100 x2s t x1 x2 3152x1 x2 390 x2 240 x1 x2 0 输入形式目标函数 MAX50X1 100X2变量个数 2输入第一个约束 X1 X2 315输入第二个约束 2X1 X2 390输入第三个约束 X2 240输入第四个约束 END 计算机输入演示 83 计算结果 输出 解释 分析 1 目标函数最优值为 277502 变量最优解相差值x1750 x224003 约束松弛 剩余变量对偶价格105025003050 84 4 目标函数系数范围 变量下限当前值上限x1050100 x250100无上限5 常数项范围 约束下限当前值上限12403153152390390无上限3240240315 85 在使用百分之一百法则进行灵敏度分析时 要注意以下三点 1 当允许增加量 减少量 为无穷大时 则对于任一个增加量 减少量 其允许增加 减少 百分比都看成零 2 百分之一百法则是判断最优解或对偶价格变不变的充分条件 但不是必要条件 也就是说当其允许增加和减少百分比之和不超过100 时 其最 86 优解或对偶价格不变 但是当其允许增加和减少百分比之和超过100 时 我们并不知道其最优解或对偶价格变还是不变 3 百分之一百法则不能应用于目标函数决策变量系数和约束条件右边常数值同时变化的情况 在这种情况下 只能重新求解 87 例2用计算机求解前面例2中的线性规划问题 已知其线性规划数学模型为目标函数 minf 2x1 3x2约束条件 x1 x2 350 x1 1252x1 x2 600 x1 0 x2 0 用管理运筹学软件我们得到了计算机的输出如下 p33 32 图3 5 所示 88 1 目标函数最优值为 800 万元 2 变量最优解相差值x12500 x210003 约束松弛 剩余变量对偶价格10 421250301 89 4 目标函数系数范围 变量下限当前值上限x1无下限23x223无上限5 常数项范围 约束下限当前值上下限1252503475600700 90 五 两点注意A 有些书上常常使用影子价格这个术语 1 当约束条件右边值增加一个单位时最优目标函数值增加的数量称为影子价格 2 当约束条件右边值增加一个单位时最优函数目标值改进的数量称为对偶价格 由此可知当求目标函数的最大值时 影子价格 对偶价格 当求目标函数的最小值时 影子价格 为负的对偶价格 91 B 管理运筹学 微机软件可以解决有100个决策变量50个约束方程的线性规划问题 它可以解决工商管理中大量的问题 如果想要解决更大的线性规划问题 你可以使用由芝加哥大学LinusE Schrage开发的LINDO计算机软件包的微机版本LINDO PC 作业 p34 33 1 5 92 一 人力资源分配的问题例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 第四章线性规划在工商管理中的应用 93 解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们可以建立如下的线性规划模型目标函数 minx1 x2 x3 x4 x5 x6约束条件 s t 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 最优值 150最优解 x1 50 x2 20 x3 50 x4 0 x5 20 x6 10 94 例2福安商场是个中型的百货商场 它对售货员的需求经过统计分析如右表 为了保证售货人员充分休息 售货人员每周工作五天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 95 解 设xi i 1 7 表示星期i开始休息的人数 于是我们可以建立如下的线性规划模型目标函数 minx1 x2 x3 x4 x5 x6 x7约束条件 s t x1 x2 x3 x4 x5 28x2 x3 x4 x5 x6 15x3 x4 x5 x6 x7 24x4 x5 x6 x7 x1 25x5 x6 x7 x1 x2 19x6 x7 x1 x2 x3 31x7 x1 x2 x3 x4 28x1 x2 x3 x4 x5 x6 x7 0 最优值 36最优解 x1 12x2 0 x3 11x4 5 x5 0 x6 8 x7 0 96 例3 明兴公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如下表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 二 生产计划的问题 97 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司机加工和装配的甲 乙两种产品的件数 求一件xi的利润 利润 售价 各成本之和由上式可得到xi i 1 2 3 4 5 的利润分别为15 10 7 13 9元 这样我们可以建立如下的线性规划模型目标函数 max15x1 10 x2 7x3 13x4 9x5约束条件 s t 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 98 用管理运筹学软件我们得到计算机的输出结果如下 1 目标函数最优值为 294002 变量最优解相差值x116000 x202x3013 1x400 5x56000 99 3 约束松弛 剩余变量对偶价格100 3202 25340000从对偶价格栏可知铸造每工时的对偶价格为0 3元 机加工每工时的对偶价格为2 25元 装配每工时的对偶价格为0元 这样如果有人以低于铸造和机加工的对偶价格来提供铸造及机加工的工时 则可以购入来获取差价 同样如果有人要购买该公司的铸造与机加工的工时 则出价必须扣除成本外 还必须高于其对偶价格 否则就不宜出售 P46 43 100 例4 永久机械厂生产 三种产品 均要经过A B两道工序加工 设有两种规格的设备A1 A2能完成A工序 有三种规格的设备B1 B2 B3能完成B工序 可在A B的任何规格的设备上加工 可在任意规格的A设备上加工 但对B工序 只能在B1设备上加工 只能在A2与B2设备上加工 其有关数据如下表 问 为使该厂获得最大利润 应如何制定产品加工方案 101 解 设xijk表示第i种产品 在第j种工序上的第k种设备上加工的数量 如x123表示第 种产品在第B道工序上用B3设备加工的数量 总利润 销售单价 原料单价 产品件数 每台时的设备费用 设备实际使用的总台时数 这样可以我们建立如下的数学模型 maxz 0 75x111 0 7753x112 1 15x211 1 3611x212 1 9148x312 0 375x121 0 5x221 0 4475x122 1 2304x322 0 35x123 102 s t 5x111 10 x211 6000 设备A1 7x112 9x212 12x312 10000 设备A2 6x121 8x221 4000 设备B1 4x122 11x322 7000 设备B2 7x123 4000 设备B3 x111 x112 x121 x122 x123 0 产品在A B工序加工的数量相等 x211 x212 x221 0 产品在A B工序加工的数量相等 x312 x322 0 产品在A B工序加工的数量相等 xijk 0 i 1 2 3 j 1 2 k 1 2 3 103 x111的系数0 75的由来1 25 0 25 300 6000 5 1 0 05 5 0 75 x112的系数0 7753的由来1 25 0 25 321 10000 7 0 7753 x121的系数 0 375的由来 250 4000 6 0 375 x211的系数1 15的由来2 00 0 35 300 6000 10 1 65 0 05 10 1 15 x221的系数 0 5的由来 250 4000 8 0 5 104 最优值 1146 6005 最优解 x111 1200 x112 230 0492 x211 0 x212 500 x312 324 138 x121 0 x221 500 x122 858 6206 x322 324 138 x123 571 4286 105 例5 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 解 我们可以设计下列8种下料方案 但只需考虑前5种 三 套裁下料问题 106 设x1 x2 x3 x4 x5分别为上面前5种方案下料的原材料根数 于是我们可以建立如下的数学模型 目标函数 minx1 x2 x3 x4 x5约束条件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 用管理运筹学软件解得 目标函数最小值为90 x1 30 x2 10 x3 0 x4 50 x5 0 107 例6 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 已知产品的规格要求 产品的单价 每天能供应的原料数量及原料单价 分别见下表 问 该厂应如何安排生产 使利润收入为最大 四 配料问题 108 解 设xij表示第i i 1 2 3 1 甲 2 乙 3 丙 种产品中原料j j 1 2 3 的含量 如x23就表示乙产品中第3种原材料的含量 利润 总收入 总原料支出目标函数为 50 x11 x12 x13 35 x21 x22 x23 25 x31 x32 x33 65 x11 x21 x31 25 x12 x22 x32 35 x13 x23 x33 109 从第一个表得约束条件 x11 0 5 x11 x12 x13 x12 0 25 x11 x12 x13 x21 0 25 x21 x22 x23 x22 0 5 x21 x22 x23 从第二个表得约束条件 x11 x21 x31 100 x12 x22 x32 100 x13 x23 x33 60 110 整理后得此问题的数学模型 目标函数maxz 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33约束条件s t 0 5x11 0 5x12 0 5x13 0 0 25x11 0 75x12 0 25x13 00 75x21 0 25x22 0 25x23 0 0 5x21 0 5x22 0 5x23 0 x21 x31 100 x12 x22 x32 100 x13 x23 x33 60 xij 0 i 1 2 3 j 1 2 3 111 用管理运筹学软件解得 目标函数最大值为500 x11 100 x12 50 x13 50 其余的xij 0 P51 49 例7自学 112 例8 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目