第1章 线性规划y(2011,10).ppt

1 1 线性规划问题及模型2 线性规划的解3 线性规划的单纯形法4 单纯形表5 单纯形法的进一步讨论6 线性规划建模举例 第1章线性规划 2 线性规划经典应用回顾 为潘德罗索工业公司选择产品组合联合航空公司工作人员排程Citgo石油集团供应 配送与营销的规划 3 潘德罗索工业公司 潘德罗索工业公司 PonderosaIndustrial 是一家墨西哥公司 截止到1998年的销售 公司生产了全国胶合板产量的1 4 与其他胶合板生产厂商一样 潘得罗索工业公司的许多产品根据厚度和所用木材的质量而有所不同 因为产品在一个竞争的环境中进行销售 产品的价格由市场决定 所以产品的价格每月都有很大的变化 结果导致每项产品对公司整体利润的贡献也有很大的变动 这样 在某个月中一个产品比另一个产品能赚取更多的利润 而在下个月的情况可能正好相反 所以每个月管理层面临的一个关键问题是选择产品组合 ProductMIX 每项产品各生产多少 以获取尽可能多的利润 4 这一选择是很复杂的 因为它需要考虑当前生产产品必须的各种资源的可得数量 六项最重要的资源为1 四种类型的原木 根据原木的质量区分 和2 生产胶合板的两项关键作业的生产能力 模压作业和刨光作业 从1980年开始 潘得罗索工业公司管理部门每个月使用线性规划指导下个月的产品组合决策 线性规划的数学模型考虑了这一决策的所有相关限制条件 包括生产产品所需的有限的资源可得数量 然后对模型求解 找出可行并且最大可能利润 possibleprofit 的产品组合 一旦数据输人模型 包括下个月产品的估计价格 可能获得的最大利润会被准确地计算出来 5 但是 管理层知道哪怕仅仅只提前一个月的产品价格预测也是危险的 所以检验在其他似乎可信的价格预测下产品组合决策是如何发生改变就很重要 幸运的是 线性规划计算机系统是交互式的 管理者能够对市场决定的不同情景很快地再对模型进行求解 这种对感兴趣的各种情景进行考察的能力证明 在准确做出产品组合的决策上是无可限价的 在潘得罗索工业公司 线性规划的影响被报道是 惊人的 它导致公司强调生产的原木产品类型有巨大的转换 改进的产品组合决策使公司的总利润增加了20 线性规划的其他一些贡献包括更好的原材料利用 更好的资本投资和更好的人员使用 6 潘德罗索应用成功的因素 以自然语言为用户界面的财务计划系统 使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果 使得做决策的管理者能够很容易看懂整个过程 最优化系统是互动的 interactive 管理者在从一个版本的模型中获得一组最优解之后 可以提出一系列的what if问题 并能立即得到回应 7 联合航空公司人员排程 尽管1983年和1984年经历了史无前例的行业竞争 联合航空公司 UnitedAirlines 还是开通了48个新机场的服务 取得了很大的增长 1984年 它是唯一的一家在美国全部50个州开通服务的公司 1984年的收人比1983年增加了6个百分点达到了62亿美元 而同时成本的增长少于2 因此营运利润提高达到了5 64亿美元 在航空行业生存 成本控制是关键 作为公司扩展的一部分 1982年联合航空公司的高层管理部门实施了一个成本控制项目 目标是通过更紧密地根据消费者的需求进行工作排程 以改进航班订票处和机场工作人员的利用率 8 那时 联航在其11个航班订票处有超过4000名的机票销售代表和支持人员 在10个最大的机场大约有1000名客户服务代表 有些是兼职的 每班2 8个小时不等 大部分是全职的 每班8小时或10小时 有许多个不同的上班时间 每个订票处都一天24小时营业 通过电话订票 各个重要的机场也如此 然而 每个地点提供所需水平服务的雇员数量在一天24小时中的变化很大 或许每过半个小时就会有很大的变化 9 为了更有效率地满足服务需求 在每个地点为所有雇员设计工作排程是一个组合的梦魇 一旦一名雇员上了班 他 或她 就会工作一个班次 根据雇员2 10个小时不等 只有就餐和每隔两小时的短暂的休息时间 给定24小时的一天中每半个小时间隔的服务所需的最小雇员数 每周七天里这个最小值天天有变化 在一周七天 一天24小时中每个班次需要多少雇员并且何时上班呢 幸运的是 线性规划能解决这些组合梦魇问题 预测和排队模型都可以用来确定每半小时间隔任务的最少雇员数 整数规划可确定班次何时开始 但是 规划系统的核心是线性规划 它能进行所有实际的排程以在最小的劳动力成本下提供所需的服务 每个月会产生一个新的工作排程以反映实际情况的变化 10 线性规划的这个应用据报道 不仅对联航的管理层和项目小组成员 而且对许多未曾听说过管理科学或数学模型的人有压倒一切的影响 它获得了高级管理层 运营经理 相关雇员等等人员的强烈好评 例如 一位经理描述排程系统为 魔术般的 就好像消费者的排队正要变长的时候 新的工作人员就进来提供服务 就好像你认为工作强度在增大时 消费者就开始回家了 据有形估计 建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上节省了600万美元 得到的其他好处包括改善客户服务以及降低雇员的工作负担 1990年代早期经过一些升级以后 系统今天还在提供与过去同样的好处 11 联合航空公司 利用线性规划 来为其在主要的机场和定票点的上万个工作人员安排每周的工作时间表 目标是为了能够在满足客户的服务需要的同时 将一周内每天每半个小时的人员成本最小化 联合航空公司一些地点的规划模型却包括20 000个决策变量 应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持 12 Citgo石油集团 Citgo石油公司专长于石油炼制和销售 1980年代中期 它每年的销售额有几十亿美元 是美国150大工业公司之一 经过几年的财务亏损后 1983年被Southland集团收购了 Southland集团是7 11便利连锁店的拥有者 7 11便利连锁店每年销售20亿加仑高质量的汽车燃油 为了扭转Citgo石油公司的亏损局面 Southland集团组建了一个由Southland集团人员 Citgo石油公司人员和外部咨询顾问组成的任务小组 一位管理科学咨询顾问被任命为小组的负责人并直接向Citgo石油公司总裁和Southland集团董事长汇报工作 1984 1985年间 任务小组应用各种管理科学技术对Citgo石油公司广泛的业务领域活动进行了分析 例如炼油 供应和配送 营销计划 应付和应收账款 库存控制和收购等领域 据报道这些管理科学应用 转变了Citgo石油公司的经营方式以及带来了每年约7000万美元的利润增加 13 大部分增加的利润是由于应用了由任务小组开发的两个线性规划系统 一个称为 炼油LP系统 它改善了炼油的产出率 劳动成本的本质性下降和其他一些成本节支 炼油LP系统使管理部门能更有效率地运作Citgo石油公司的炼油作业 这是赢利还是亏损的重要取决因素 以至于1985年7000万美元的利润增加中有5000万美元是由于应用这一系统所创造的 另一个线性规划系统是供应 配送和营销模型系统 或简称SDM系统 引人系统多年后直至今日 Citgo石油公司继续在使用该系统并且从系统中得到好处 它是以一类特殊的线性规划模型为基础 应用网络对所要研究的系统进行描述 这个模型是对Citgo石油公司全部营销和配送网络的一个表述 14 SDM系统用来协调全在美国每项产品的供应 配送和营销 利用它做许多决策 例如产品销往何处 以什么价格 在哪儿购买或贸易 购买或贸易数量的多少 库存保持多少 以及各种运输方式各运输多少 线性规划指导这些决策的做出并且什么时候实施这些决策使Citgo石油公司的总成本最低 SDM系统还用作 What if 分析 管理部门可以探究如果情况发生了不是模型假设的变化时结果会发生怎样的变化 SDM系统大大改善了Citgo石油公司供应 配送和营销运作的效率 在不降低服务水平的同时产品库存有了巨大的下降 引入系统不久 石油产品的库存价值下降了11 650万美元 与保管库存相关的资金的巨大下降导致每年这些借贷资金的利息花费大约节约了1 400万美元 因而为Citgo石油公司增加了1 400万美元的年利润 据估计 在协调 定价和采购决策上的改善又为公司至少增加了250万美元的年利润 15 Citgo石油集团 运用管理科学的技术 特别是线性规划 建立供应 配送与营销的建模系统将公司主要产品的供应 配送与营销通过公司庞大的销售与配送网络得到很好的协调 在90年代中期创造了大量的财富 公司每种主要产品的模型都含有大约1 500个决策量以及3 000个确定需求的约束 最重要的成功因素是高层管理者所给予的无限制的支持 并且设立运作协调副总裁 来负责评价与协调这一跨组织边界的模型所提供的建议 16 第一节线性规划问题及其数学模型 一 线性规划问题二 线性规划的数学模型三 线性规划的标准型 17 一 线性规划问题 案例研究 伟恩德公司产品组合问题线性规划的其它例子 18 案例研究 伟恩德公司产品组合问题 伟恩德玻璃制品公司生产高质量的玻璃门窗 拥有3个工厂 由于收入下降 高层管理者决定修整公司的生产线 不盈利的产品将停止生产 将生产能力转移到有较大销售潜力的两个新产品 产品1 8英尺的铝框玻璃门产品2 4X6英尺的双把木框窗公司有三个工厂 工厂1 生产铝框和五金件工厂2 生产木框工厂3 玻璃生产和组装窗与门 19 产品1 需要工厂1和3的生产能力产品2 需要工厂2和3的生产能力进行市场研究得到结论 公司能够销售掉工厂所能生产的全部产品 然而 由于两种产品都为使用工厂3的生产能力而竞争 不清楚如何确定两种产品的组合可以实现利润最大化 因此 组织了一个运筹小组来研究这个问题 20 运筹小组开始与高层管理者进行讨论 以明确管理目标 并定义出了下面的问题 决定两种产品生产率的目标是总利润最大化 限制条件是三个工厂有限的生产能力满足这些限定条件的任何生产组合都是可行的 21 运筹小组还确定出需要收集的下列数据 1 每周在每个工厂能为生产这些新产品所提供的生产时间 小时 数 2 生产每一个新产品需要每家工厂所消耗的时间 小时 数 3 每一产品的单位利润 22 表1伟恩德玻璃制品公司产品组合问题的数据 23 现在管理部门要考虑下列两个问题 1 公司是否应该生产这两个新产品 2 如果生产 两个新产品的产品生产组合如何 每周分别生产多少数量 24 代数模型 25 26 结论 运筹学小组使用这个方法找到了最优解 WyndorGlass公司每周生产产品1和产品2的数量分别是2批和6批 带来的总利润是36000元 根据这个模型两种产品生产的其它组合都没有这种组合的盈利多 27 生产决策问题某厂生产甲乙两种产品 巳知制成一吨产品甲需用资源A3吨 资源B4m2 制成一吨产品乙需用资源A2吨 资源B6m2 资源C7个单位 若一吨产品甲和乙的经济价值分别为7万元和5万元 三种资源的限制量分别为90吨 200rn2和210个单位 试决定应生产这两种产品各多少吨才能使创造的总经济价值最高 线性规划的其它例子 28 投资问题 某单位有一批资金用于四个工程项目的投资 用于各工程项目时所得之净收益 投入资金的百分比 如下表所示 由于某种原因 决定用于项目A的投资不大于其它各项投资之和 而用于项目B的和C的投资不小于项目D的投资 试确定使该单位收益最大的投资分配方案 29 营养问题某动物饲养场利用n种天然饲料来配制混合饲料使用 已知单位第j种天然饲料的价格为cj 它含有第i种营养成份的量为aij 根据动物生长的需要 要求具有rn种营养成份 且第i种营养成份的含量不得低于bi 试确定在保证动物营养需要的条件下费用最低的饲料配合法 30 32 上面例子从数学上具有以下几点共同特征 1 用未知自变量表示某种重要的可变因素 变量的一组数据代表一种解决方案 通常求这些变量取非负值 2 存在一定的限制条件 它们可以自变量的线性方程 等式 或线性不等式来表示 这些条件称为约束条件 3 都有一个要达到的目标 它也是自变量的线性函数 称为目标函数 根据需要 要目标函数极大化或极小化 33 二 线性规划的数学模型 线性规划数学模型的一般表示方式 34 1 和式 35 2 向量式 36 3 矩阵式 37 三 线性规划的标准型 38 变换的方法 1 第i个约束为 型 在不等式左边增加一个非负的变量xn i 称为松弛变量 第i个约束为 型 在不等式左边减去一个非负的变量xn i 称为剩余变量 2 目标函数为min型 可将该目标函数乘以 1 变为极大化问题求解 3 若xj 不限 令xj xj xj xj 0 xj 0 39 X X Z f X Z f X 极小化 极大化 O Z 40 变换举例 41 有关线性规划的假设 比例性可加性可分割性确定性 数学模型仅仅是实践问题的一个理想化表达 通常需要近似和假设简化 目的在于容易处理问题 42 管理视角的线性规划 管理者需要具有线性规划是什么的一个良好直觉 管理者需要对线性规划的适应性和作用有一个正确的评价以使得在合适的时候鼓励应用 管理者必须理解如何解释线性规划研究得出的结果 理解这类信息对管理决策制定的意义 43 第二节线性规划问题的解 一 图解法二 线性规划解的概念 44 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 4 3 14 3 6 4 8 6 0 x1 x2 例1 maxz 46 3 45 2用图解法求解线性规划问题 46 最优解 B 3 3 2 Z 15 47 3用图解法求解线性规划问题 48 1234 2 1 3 4 3x1 2x2 12 X2 2 X1 2x2 6 A B C D 0 最优解 C 2 2 B 3 3 2 Z 6 无穷多个 X1 X2 49 4用图解法求解线性规划问题 50 最优解 B 0 1 Z 1 X1 X2 51 5用图解法求解线性规划问题 52 无上界 X1 X2 53 6用图解法求解线性规划问题 54 55 线性规划问题解的几种情况 1 有唯一最优解 2 有多重最优解 3 目标函数无界 4 无解 56 二 线性规划解的概念 线性规划数学模型的标准型 57 58 1基 59 60 解 基矩阵只有9个 62 2基向量 基变量 非基变量 当确定某一子矩阵为基矩阵时 则基矩阵对应的列向量称为基向量 其余列向量称为非基向量 基向量对应的变量称为基变量 63 称Pj j 1 2 m 为基向量 与基向量Aj相应的变量Xj j 1 2 m 为基变量 其它变量称为非基变量 64 3可行解 最优解 例如 65 4 基解 基可行解 可行基 基解 对某一确定的基B 令非基变量等于0 利用式1 2解出基变量则这组解称为基B的基解 基可行解 满足非负要求的基解 可行基 对应于基可行解的基 如上例中B3 在上例中 对B1 基解为 67 可行解 基解和基可行解举例 68 可行解 基解和基可行解举例 69 解的集合 非可行解 可行解 70 解的集合 基解 71 解的集合 可行解 基解 基可行解 72 解的集合 可行解 基解 基最优解 基可行解 73 二凸集及其顶点 P20 74 凸集概念 如果集合C中任意两点x 1 x 2 其连线上的所有点x也都是C中的点 则称C为凸集 即 若C中的任意两点x 1 x 2 C 存在0 1使得x x 1 1 x 2 C 则称C为凸集 75 X1 X2 X 1 X 2 X X 1 X 2 y X 1 X 2 0 1 X X 2 y X 2 X 1 X 2 X 1 1 X 2 X1 X2 X 1 X 2 X X 2 X 1 X 2 X X 2 y X 2 X 1 X 2 X 1 1 X 2 y X 1 X 2 0 1 77 凸集 78 非凸集 79 凸集性质二个凸集的交还是凸集 二个凸集的并不一定是凸集 80 顶点 设C是凸集 若C中的点x不能成为C中任何线段上的内点 则称x为凸集C的顶点 即 若C中的任意两点x 1 x 2 不存在数 0 1 使得x x 1 1 x 2 成立 则称x为凸集C的一个顶点 81 例 多边形上的点是顶点 圆周上的点都是顶点 82 线性规划的基本定理 定理1 线性规划问题的可行解集是凸集 引理 线性规划问题的可行解为基可行解的充要条件是x的正分量所对应的系数列向量是线性独立的 83 定理2 线性规划问题的基可行解X对应线性规划问题可行域的顶点 定理3 若线性规划问题有最优解 一定存在一个基可行解是最优解 84 上述定理给了我们一个启示 求最优解不是在无限个可行解中去寻找 而是在有限个基本可行解中去求得 但用这种方法求最优解的前提是该线性规划存在最优解 85 86 87 第三节线性规划的单纯形法 单纯形法的基本思路是 根据问题的标准 从可行域中某个基可行解 一个顶点 开始 转换到另一个基可行解 一个顶点 并且使目标函数达到最大值时 问题就得到了最优解 88 一 分析一个例子 解该问题的线性规划模型为 其标准型为 90 线性规划问题的一个基 初始基 B 0 A3 A4 A5 100010001 X3 X4 X5为基变量 得 X3 90 3X1 2X2X4 200 4X1 6X2X5 210 0X1 7X2 1 13 将 1 13 代入目标函数得 Z 7X1 5X2 0令非基变量X1 X2 0 便得到Z 0 这时得到一个基可行解X 0 92 X 0 0 0 90 200 210 T从 1 15 中可以看出 只有选择 才能使 1 15 成立 用X1去替换X3 再将 1 17 代入目标函数得 94 目标函数还可以增大 继续迭代得 此时 目标函数取得最大利润 95 该例的图解 例用单纯形法求下列线性规划的最优解 97 初始基可行解 检验数 目标函数用非基变量表示 其变量的系数为检验数 最优解判断标准当所有检验数基可行解为最优解 通过观测得到一个基可行解并判断其是否为最优解 1 约束条件系数矩阵存在m个不相关的单位向量 2 目标函数中不含有基变量 单纯形法的开始和后面就是 寻找基可行解和求检验数 99 X2为引入变量 由约束条件 X2 x3基变量 解出 100 基可行解为 X 1 0 10 30 0 T 检验未达最优 继续迭代X1引入变量 X3为退出变量 通过初等变换得到 检验达最优 102 上述全过程计算方法就是单纯形法 实际将用列表的方法进行计算 103 104 1 形约束 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm 二 初始基可行解 105 a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bm 得一基可行解如下 已设bi 0 X x1 xn 1 xn m T 0 0 0 b1 bm T显然 基变量对应的系数列向量全为单位列向量 106 2 等式约束考虑等式约束线性规划 MaxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 1 24 am1x1 am2x2 amnxn bmxj 0j 1 2 n 107 a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 1 25 am1x1 am2x2 amnxn xn m bmxj 0j 1 2 n m MaxZ c1x1 c2x2 cnxn mxn 1 mxn 2 mxn m 108 3 型约束设有如下线性规划问题 MaxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 1 26 am1x1 am2x2 amnxn bmxj 0j 1 2 n 109 MaxZ c1x1 c2x2 cnxn mxn m 1 mxn m 2 mxn 2ma11x1 a12x2 a1nxn xn 1 xn m 1 b1a21x1 a22x2 a2nxn xn 2 xn m 2 b2 am1x1 am2x2 amnxn xn m xn 2m bmxj 0j 1 2 n m 令人工变量为基变量 立刻得一基可行解如下 X x1 x2 xn xn 1 xn m n m 1 xn 2m T 0 0 0 0 0 b1 bm T 110 例 用上述方法为下面的线性规划问题构成初始基可行解 111 例 写出下述线性规划问题的初始基可行解 112 例 写出下述线性规划问题的初始基可行解 113 三 最优性检验 设前m个系数列向量为单位列向量 它们构成基 对应的基可行解 将基变量由 1 4 的约束条件解出 得 115 将 1 5 代入 1 4 中的目标函数表达式 得 116 117 Z0是现行解XB x1 x2 xm T b1 b2 bm T的目标函数值 Ci i 1 2 m 为基变量的价值系数 有时为避免混淆 特以下标B标明 记为CBi xj为非基变量 Cj为非基变量的价值系数 j m 1 nZj的意义是 当引入非基变量xj时 单位xj使原来目标函数的减少值 118 119 1 若所有非基变量的 皆非正 则这个解为最优解 1 最优解唯一 2 有多重最优解 2若存在某个或某些的非基变量 且其系数列向量含有正分量 120 通常选最大的变量为引入变量 3若存在为正的某非基变量xj 其系数列向量的所有分量皆非正 即aij 0 i 1 2 3 m 则该线性规划目标函数值无界 121 四 基可行解的转换 1 根据检验数确定引入变量2 根据规则确定退出变量确定主元素alk 122 2 其余的利用下列公式计算 3 系数变换 1 将主元素所在的L行数字除以主元素alk得变换后的第L个约束方程系数 123 1建模2给出初始基可行解 引入松弛和人工变量 3计算非基变量的 若所有均非正 这个解就是最优解 否则 转下一步 4在检验数为正的那些非基变量中 选检验数最大的那个变量为引入变量 例如说这个变量是xk 它对应系数列向量为Pk 五用单纯形法求解线性规划问题的步骤 124 5查看Pk的各个分量aij i 1 2 m 若所有aik 0 则该线性规划问题无界 否则 转下一步 6按最小比值规则确定 即 min aik 0 i 1 2 m 1 40 125 7以相应于 的那个变量xBl 基变量中的第l个变量 为退出变量 以alk为主元素 对约束方程组按式 1 7 进行变换 从而得一新的基可行解 8转回第3步 继续进行检验和变换 直至得出最优解或查明目标函数无界 126 第四节单纯形表 单纯形表格式如下 127 cj cBi xBi c1c2 cm c1 cm x1 xm x1x2 xm 1 00 1 0 1 cm 1 cnxm 1 xn a1 m 1 a1na2 m 1 a2n am m 1 amn bi bi aik b1b2 bm b1 a1kb2 a2k bm amk 0 0 128 矩形交叉相乘示意图 aij aik i行 alj alk l行 退出 j列 k列 引入 主元素 欲计算之元素 130 132 133 例 用单纯形法求解线性规划 134 其标准型为 136 137 例 用单纯形法求解线性规划 解 cj yj cj zj yj cj zj yj cj zj yj cj zj 3 1 100 M M x1x2x3x4x5x6x7 1 211000 3 6M 1 M 1 3M0 M00 cBi xBi 0 x4 Mx6 0 x4 Mx6 1x3 bi 4M bi aik 113 21 4120 110 Mx7 200001 1 1131 3 20100 1000 11 2 2010001 1 1011 1 1 1 M00 M01 3M 0 x4 1x2 1x3 001 22 50100 11 2 2010001 3 1 M 1211 4 1000 11 M 1 M 2 3x1 1x2 1x3 1001 3 2 32 3 5 30100 11 20012 3 4 34 3 7 3 419 000 1 3 1 31 3 M2 3 M 2 139 140 141 142 143 第五节单纯形法的进一步讨论 144 目标函数类型 检验数和最优性判定准则之间的关系 145 二 退化 当解的非零分量的个数不足m个 或者説基变量有取值为零的变量时 这样的解就称为退化解 146 三 两阶段法 Two PhaseMethod 147 148 两阶段法将求解过程分为两个阶段 第一阶段求解辅助线性规划 1 44 149 解 现用两阶段法求解 152 第二阶段 153 154 四 单纯形法小结 155 计算 所有 基变量中含非零的人工变量 存在非基变量检验数为零 惟一最优解 迭代运算1 用xk替换xl2 列出新的单纯形表 求出初始基可行解列出初始单纯形表 是 否 否 无界解 无可行解 无穷多最优解 是 是 是 否 否 156 第六节数据包络分析 DEA 简介 157 数据包络分析 DEA 是一种基于线性规划的用于评价同类型组织工作绩效相对有效性的工具手段 所谓生产前沿面是生产可行集的一条数据包络线 称处于生产前沿面上的点为DEA有效 158 159 例8 振华银行的4个分理处的投入产出情况如表1 16所示 要求分别确定各分理处的运行是否DEA有效 表1 16产出单位 处理笔数 月 160 解 判断分理处1的运行是否DEA有效 线性规划模型如下 minE 161 同理 将以上列出的约束条件中右端数字分别更换为分理处2 3 4的产出和投入的数字 就可以分别计算出E的值 其中 分理处2的E 0 996 则其运行非DEA有效 分理处3 4的E 1 则其运行为DEA有效 162 第七节线性规划的应用 线性规划问题种类繁多 形式各异 但主要可以概括为下面四种类型 资源分配问题 resource allocation 成本收益平衡问题 cost benefit trade off 网络配送问题 distribution network 混合问题 mixedProblem 163 资源分配问题 资源分配 resource allocation 问题是将有限的资源分配到各种活动中去的线性规划问题 这一类问题的共性是在线性规划模型中每一个函数限制均为资源限制 resourceconstraint 并且每一种有限资源都可以表现为如下的形式 使用的资源数量 可用的资源数量 164 收集数据 问题所有活动可获得使用的每种资源的有限数量每一种活动所需要的各种资源的数量 每一种资源与活动的组合 单位活动消耗资源量必须首先估计每一种活动对总的绩效测度的单位贡献 165 上海电器厂生产优化 上海电器厂生产A B两种电器产品 原材料消耗等资料见下表 问 产品A和产品B各生产多少 可使总利润最大 166 EXCEL 167 案例 伟恩德公司产品组合问题 168 梦大发展公司 资金预算 梦大发展公司是商务房地产开发项目的主要投资商 目前该公司有机会在三个建设项目中投资 项目1 建造高层办公楼项目2 建造宾馆项目3 建造购物中心每一个项目都要求投资者在四个不同的时期投资 在当前预付定金 一 二 三年后分别追加投资 下表显示了四个时期每个项目所需要的总资金 因此按投资者投资项目的一定百分比 投资者必须支付表中所示资金的对应百分比的数目 169 表2财务数据 170 从长期来看 这个项目都是极为有利可图的 因此 公司的管理层希望能尽量多地几个或所有的项目中投资 公司希望能在目前阶段就明确公司未来的投资数量 以及未来三年预期实现的追加投资 关键是在预测的回报率的基础上确定最有利可图的投资组合 171 公司目前有2500万元资金可供投资 预计一年后 又可获得2000万 两年后获得另外的2000万 三年后1500万以供投资 那么 梦大公司要在每个项目中投资多少百分比 才能使其投资组合获得最大的总净现值呢 172 分析思路 明确问题数据收集建模决策决策1 OB 办公楼项目中的投资比例决策2 H 宾馆项目中的投资比例决策3 SC 购物中心项目中的投资比例再次评估 173 表2资源数据 174 这是一个资源分配问题 模型如下 EXCEL 175 求解模型 最优解为 不投资办公楼在宾馆项目中投资16 50 的份额在购物中心项目中投资13 11 的份额 176 从广义的资源角度来说 对决策的任何限制条件 如果是以下面的形式出现 使用的数量 可获得的数量都可以认为是资源约束问题 177 投资问题 例8 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可以投资 次年末回收本利125 但规定每年最大投资额不能超过30万元 项目C 第三年初需要投资 到第五年末能回收本利140 但规定最大投资额不能超过80万元 项目D 第二年初需要投资 到第五年末能回收本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如下所示 178 问 1 应如何确定这些项目的每年投资额 使得第五年末拥有资金的本利金额为最大 2 应如何确定这些项目的每年投资额 使得第五年末拥有资金的本利在330万的基础上使得其投资总的风险系数为最小 179 解 1 确定变量1 我们设xij 第i年初投资于j项目的金额 单位万元 根据给定条件 将变量列于下表 80 1 1 1 25 1 4 30 100 1 55 10 11 180 2 约束条件第一年 x1A x1B 200第二年 x2A x2B x2D 1 1x1A第三年 x3A x3B x3C 1 1x2A 1 25x1B第四年 x4A x4B 1 1x3A 1 25x2B第五年 x5A 1 1x4A 1 25x3B此外 对项目B C D的投资额的限制有 xiB 30 i 1 2 3 4 x3C 80 x2D 100 3 目标函数Maxz 1 1x5A 1 25x4B 1 40 x3C 1 55x2D 181 excel 182 成本收益平衡问题 成本收益平衡问题 Cost benefit trade offProblem 是一类线性规划问题 这类问题中 通过选择各种活动水平的组合 从而以最小的成本来实现最低可接受的各种收益的水平 这类问题的共性是 所有的函数约束均为收益约束 并具有如下的形式 完成的水平 最低可接受的水平 183 成本收益平衡问题举例 利博公司广告组合问题工作人员排程套材下料问题控制空气污染 184 利博公司广告组合问题 利博公司生产家用的清洁产品 这是一个高度竞争的市场 公司为了增加市场份额连续挣扎多年 管理层决定集中在下列三个主要产品上实行一个大规模的新的广告运动 一种喷雾去污剂 一种新的液体洗涤剂 一种成熟的洗衣粉 185 186 在这里 活动是指电视上做广告和印刷媒体上做广告 因此 要做的决策为 决策1 TV一电视广告的单位数量决策2 PM一印刷媒体广告的单位数量要达到广告效果要求而成本最低 187 工作人员排程 188 解 设xi表示第i班次时开始上班的司机和乘务人员数则有 189 工作人员排程问题 公交公司 xls 190 例2 福安商场是个中型的百货商场 它对售货人员的需求经过统计分析如下所示 191 为了保证售货人员充分休息 售货人员每周工作五天 休