第1章线性规划(1-2).ppt

第一章线性规划 线性规划广泛应用于经济领域 包括生产计划 广告媒体选择 投资决策 资本预算 人事安排 产品配比问题等等 线性规划是进行管理决策的最有效的方法之一 问题导入 生产优化 产品组合问题 问题背景和风家具有限公司生产高质量特色系列的茶几和餐桌 由于质量过硬 造型优美时尚 部分产品不仅畅销国内 还远销海外 为公司创造了不菲收益 最近 公司的制造总裁李文碰到了一件棘手的问题 总公司旗下有三个分厂 由于某些产品销售量的下降 高层管理部门决定调整公司的产品线 问题导入 生产优化 产品组合问题 如果征得管理部门的同意 不盈利的产品要停止生产并撤出生产能力来生产研发部刚开发的两个新产品 绿色时尚系列茶几A和餐桌B 现在管理部门要考虑下列两个问题 1 公司是否应该生产这两个新产品 2 如果生产 两个新产品的产品生产组合如何 每周分别生产多少数量 问题导入 生产优化 产品组合问题 为解决上述问题 我们首先要收集研究所需的信息 每家工厂的生产能力 生产每一产品各需要每家工厂多少生产能力 每一产品的单位利润 表1 1总结了收集到的数据 两种新产品的有关数据 问题导入 生产优化 产品组合问题 由上述分析可建立本问题的线性规划模型下 o b max300X 500Y 利润最大化 s t X 4 工厂1的工时约束 2Y 12 工厂2的工时约束 3X 2Y 18 工厂3的工时约束 X Y 0 非负约束 第一节线性规划问题及其数学模型 线性规划是运用数学模型 对人力 设备 材料 资金等进行系统和定量的分析 使生产力得到最为合理的组织 以获得最佳的经济效益 1 1线性规划的模型结构 规划问题的数学模型由三个要素组成 1 变量 或称决策变量 是问题中要确定的未知量 它用以表明规划中的用数量表示的方案 措施 可由决策者决定 2 目标函数 它是指对问题所追求的目标的数学描述 按优化目标分别在这个函数前加上max或min 3 约束条件 指决策变量取值时受到的各种资源条件的限制 通常表达为含决策变量的线性等式或不等式 1 1线性规划的模型结构 实际问题中线性的含义 一是严格的比例性 生产某产品对资源的消耗量和可获取的利润 同其生产数量严格成比例 二是可叠加性 如生产多种产品时 可获取的总利润是各项产品的利润之和 对某项资源的消耗量应等于各产品对该项资源的消耗量的和 在实际处理不符合条件的问题时 为方便可将其看作近似满足线性条件 线性规划的数学模型的一般形式为 目标函数max min z c1x1 c2x2 cnxn满足约束条件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 1 1线性规划的模型结构 线性规划模型的矩阵形式 目标函数max min Z CX约束条件AX b其中 C c1 c2 cn X x1 x2 xn Tb b1 b2 bm Ta11 a12 a1nA a21 a22 a2n am1 am2 amn 1 2线性规划问题求解的几种可能结局 线性规划模型解的概念1 解 给每个决策变量任意赋一个值就得到该模型的解 因此模型有无数个解 例如X 20 Y 40 是该模型的解 而X 30 Y 90也是该模型的解 等等还有很多 线性规划模型解的概念2 可行解 是指满足所有约束条件的解 也就是决策变量的值满足一组等式或不等式的值 需要求解 3 可行域 是指所有可行解的集合 4 最优解 可行域中使目标函数达到最优的解 最优解满足约束条件同时又使得目标函数值达到优 1 2线性规划问题求解的几种可能结局 线性规划问题的解可能出现下列情况 1 有惟一解这里 线性规划问题有惟一解是指该规划问题有且仅有一个既在可行域内 又使目标值达到最优的解 即只有一个最优解 1 2线性规划问题求解的几种可能结局 线性规划问题的解可能出现下列情况 2 有无穷多解这里 线性规划问题有无穷多解是指该规划问题无穷多个既在可行域内 又使目标值达到最优的解 即有无穷多个最优解 1 2线性规划问题求解的几种可能结局 线性规划问题的解可能出现下列情况 3 无解这里 线性规划问题无解是指该规划问题的约束条件不能同时满足 没有可行域 不存在可行解 也就不存在最优解 1 2线性规划问题求解的几种可能结局 线性规划问题的解可能出现下列情况 4 可行域无界这里 线性规划问题的可行域无界是指最大化问题的目标函数值可以无限增大 或最小化问题的目标函数值可以无限减小 1 2线性规划问题求解的几种可能结局 1 3应用Excel求解线性规划问题 图解法单纯形法Excel的 规划求解 1 3应用Excel求解线性规划问题 首先 根据问题建立电子表格模型具体步骤如下 1 收集问题的数据 2 在电子表格的数据单元格中输入数据 3 确定对活动水平需要作出的决策并且指定可变单元显示这些决策 4 确定对这些决策的约束条件并引入需具体化这些约束条件的输出单元格 5 选择要输入目标单元格的完全绩效测度 6 使用SUMPRODUCT函数为每个输出单元格 包括目标单元格 输入合适的值 1 3应用Excel求解线性规划问题 电子表格模型 1 3应用Excel求解线性规划问题 然后 建立了起电子表格模型 就可以利用Excel中的工具Solver 规划求解 求解 1 3应用Excel求解线性规划问题 规划求解的选项对话框 1 3应用Excel求解线性规划问题 最后 保存求解结果 第二节线性规划的灵敏度分析线性规划模型的一般形式为 目标函数max min z c1x1 c2x2 cnxn满足约束条件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 通常 假定系数aij bi cj都是常数 而实际上这些系数往往是估计值和预测值 如果市场条件一变 cj值就会变化 工艺条件发生变化会改变aij的值 同样 由于bi是根据资源投入后的经济效果决定的一种决策选择 灵敏度分析就是对系统或事物因周围条件变化显示出来的敏感性程度的分析 第二节线性规划的灵敏度分析 生产优化问题 它的线性规划模型为 o b max300X 500Y 利润最大化 s t X 4 工厂1的工时约束 2Y 12 工厂2的工时约束 3X 2Y 18 工厂3的工时约束 X Y 0 非负约束 提出这样两个问题 当这些系数有一个或几个发生变化时 已求得的线性规划问题的最优解 目标值会有什么变化 或者这些系数在什么范围内变化时 线性规划线性规划问题的最优解 目标值不变 2 1一个目标函数系数变动 本节讨论在假定只有一个系数cj改变 其他系数均保持不变的情况下 目标函数系数变动对最优解的影响 2 1一个目标函数系数变动 第一种方法可以借助电子表格互动地展开灵敏度分析 当模型参数发生改变时 只要改变电子表格模型中相应的参数 再重新运行Excel 规划求解 功能 就可以看出改变参数对最优解的影响 固然能达到灵敏度分析的目的 但需要一个一个地尝试 效率低下 2 1一个目标函数系数变动 第二种方法可以利用Excel中的 规划求解 功能可以直接到 敏感性分析 利用该报告可以很方便地进行灵敏度分析 在Excel中 敏感性分析 报告的获得敏感性报告的内容 由两部分组成 位于报告上部的 可变单元格 部分反映了目标函数中的系数变化对最优解产生的影响 位于报告下部的 约束 部分反映了约束条件右端值变化目标值产生的影响 敏感性报告 敏感性报告上部的表格反映目标函数中系数的变化对最优解的影响 表格中的前三列是该问题中决策变量的信息 单元格 是指决策变量所在单元格地址 名字 是这些决策变量的名称 终值 是决策变量的终值 即最优解 敏感性报告的第一部分内容 第四列是 递减成本 它的绝对值表示目标函数中决策变量的系数必须改进多少 才能得到该决策变量的正数解 改进 在最大化问题中是指增加 在最小化问题中是指减少 第五列 目标式系数 是指目标函数中的系数 第六列与第七列分别是 允许的增量 和 允许的减量 它们表示目标函数中的系数在允许的增量和减量范围内变化时 最优解不变 2 2目标函数系数同时变动的影响 在目标函数中只有一个系数变动的情况下 通过灵敏度分析报告中的数据找到该变动系数的允许变化范围 在分析多个系数同时变动的情况时 也使用同样的这些数据 即每个系数的允许增加值和减少值 目标函数系数同时变动的使用百分之百法则进行判断 2 2目标函数系数同时变动的影响 目标函数系数同时变动的百分之百法则的具体含义为 如果目标函数的系数同时变动 计算出每一系数变动量占该系数允许变化范围允许变动量 允许的增量或允许的减量 的百分比 而后 将各个系数的变动百分比相加 如果所得的和不超过100 最优解不会改变 如果超过100 则不能确定最优解是否改变 只能通过重新进行规划求解来判断了 2 2目标函数系数同时变动的影响 茶几的单位利润P1从原来的300美元增加到450美元 而餐桌的单位利润P2从原来的500美元下降到400美元 运用百分百法则 计算如下 P1 300美元 450美元占允许增加量的百分比 100 450 300 450 100 33 34 P2 500美元 400美元占允许增加量的百分比 100 500 400 300 100 33 34 总和 66 68 因为变动百分比之和不超过100 所以可以确定最初的 茶几 餐桌 2 6 的最优解没有改变 2 2目标函数系数同时变动的影响 P1 300美元 600美元占允许增加量的百分比 100 600 300 450 100 66 67 P2 500美元 400美元占允许增加量的百分比 100 500 400 300 100 66 67 总和 133 33 通过规划求解得到 最优解已经变成了 4 3 2 2目标函数系数同时变动的影响 P1 300美元 525美元占允许增加量的百分比 100 525 300 450 100 50 P2 500美元 350美元占允许增加量的百分比 100 500 350 300 100 50 总和 100 变动百分比之和刚好等于100 但因没有超过100 所以 茶几 餐桌 2 6 还是最优解 2 3单个约束条件变化的影响 在例1 1中 每个工厂的可用工时是约束条件的右端值 工厂1的可用工时是4 但在规划求解得出的最优方案中 1只用了2小时 因此如果小范围地改变车间1的工时 不会改变最优目标值和最优解 但对于工厂2和工厂3来说 情况有所不同了 需要通过灵敏度分析 来分析一下改变这两个工厂的可用工时对目标值及最优解的影响 2 3单个约束条件变化的影响 如果管理者让工厂2的可用工时从12小时增加到13小时 修改电子表格模型中相应的参数后 重新进行规划求解 此时总利润变为3750元 增加了150元 由于总利润增加了 而目标函数系数不变 所以最优解一定会发生改变 2 3单个约束条件变化的影响 在电子表格模型中把工厂2的可得时间继续上调 总利润会继续增长 直到工厂2可得时间增加到18小时 此时再增加时间不会带来利润的增长 这是因为工厂3的18小时可得时间只能每周生产9个餐桌 所以工厂2相应的最多只会使用18小时的工时 因此 当其他工厂的可得时间不发生改变时 18小时是工厂2可得时间的最大值 2 3单个约束条件变化的影响 约束右端值往往体现了管理层的决策 在建模决策后 管理者想要知道改变这些决策是否会提高最终受益 影子价格分析就可为管理者提供这方面的信息 在给定线性规划模型的最优解和相应的目标函数值的条件下 影子价格是指约束右端值增加 或减少 一个单位 目标值增加 或减少 的数量 敏感性报告提供了每个约束的影子价格 2 3单个约束条件变化的影响 敏感性报告下部的表格反映约束条件右边变化对目标值的影响 表格中的前三列是关于约束条件左边的信息 单元格 是指约束条件左边所在单元格地址 名字 是约束条件左边的名称 终值 是约束条件左边的终值 即最优解 第四列是 阴影价格 即影子价格 影子价格是指约束条件右边增加 或减少 一个单位 目标值增加 或减少 的数量 第五列为 约束限制值 是指约束条件右边的值 是已知条件 第六列与第七列分别是 允许的增量 和 允许的减量 它们表示约束条件右边在允许的增量和减量范围内变化时 影子价格不变 2 4约束右端值同时变动的情形 车间2 12 13总利润变化量 影子价格 150元车间3 18 17总利润变化量 影子价格 100元总利润是否增加150 100 50 元 不能确定两个约束右端值同时变动时 原先的影子价格是否依然有效 怎么处理呢 2 4约束右端值同时变动的情形 多个约束右端值同时变动的情形进行分析的方法 百分之百法则百分之百法则的具体含义为 如果约束右端值同时变动 计算每一变动占允许变动量 允许的增量或允许的减量 的百分比 如果所有的百分比之和不超过100 那么 影子价格依然有效 否则只能通过重新进行规划求解来判断了 2 4约束右端值同时变动的情形 利用该百分之百法则再分析上述问题 计算如下 工厂2 12 13 占允许增加量的百分比 13 12 6 100 16 67 工厂3 18 17 占允许减少量的百分比 18 17 6 100 16 67 总和 33 33 小于100 用影子价格来预测这些变动的影响是有效的 2 4约束右端值同时变动的情形 工厂2 12 15 占允许增加量的百分比 15 12 6 100 50 工厂3 18 15 占允许减少量的百分比 18 15 6 100 50 总和 100 所以影子价格仍然有效 但这一变动幅度是最大的 一旦大于这一幅