线性优化-1_线性规划.pdf

1 1 第七章 线性优化(1)清华大学清华大学MBA课程课程 Data,Models and Decisions 数据数据,模型与决策模型与决策 2 本章主要内容本章主要内容 1 约束理论的启示约束理论的启示 2 线性规划模型及图解法线性规划模型及图解法 3 求解线性规划的单纯形方法求解线性规划的单纯形方法 4 求解线性规划的软件工具求解线性规划的软件工具 5 线性规划的对偶理论线性规划的对偶理论 6 对偶解的经济解释对偶解的经济解释 7 敏感性分析敏感性分析 8 对偶问题的博弈内涵对偶问题的博弈内涵 9 线性规划中的价值计算线性规划中的价值计算 10 线性规划应用举例线性规划应用举例 1 约束理论的启示 3 Goldratt 和他的畅销小说和他的畅销小说 4 生产管理软件与畅销小说生产管理软件与畅销小说 Goldratt吸收吸收MRP和和JIT的长处开发的的长处开发的OPT（Optimized Production Technology）生产管理软件生产管理软件，以减少库存以减少库存，增加产销率增加产销率（利润利润）为目标；为目标；挑战传统管理思想挑战传统管理思想，在在APICS（American Production and Inventory Control Society）引起很大轰动；引起很大轰动；忽视了基本管理思想忽视了基本管理思想，项目失败案例多项目失败案例多，Goldratt将将OPT原理写成小说原理写成小说“The Goal”，被译成被译成20多种文字多种文字，在全世界销售在全世界销售400多万册多万册，被誉为最成功的企业管理小说被誉为最成功的企业管理小说。从从1984年至年至1998年先后写了年先后写了4本企业管理小说：本企业管理小说：目标（目标（The Goal:A Process of Ongoing Improvement）绝不靠运气（绝不靠运气（Its Not Luck）关键链（关键链（Critical Chain）仍然不足够（仍然不足够（Necessary But Not Sufficient）5 解决管理瓶颈的约束理论解决管理瓶颈的约束理论 OPT系统将重点放在控制整体产出的系统将重点放在控制整体产出的瓶颈瓶颈资源上，优先资源上，优先处理所有瓶颈作业，并以平衡物料流动为原则，使整个处理所有瓶颈作业，并以平衡物料流动为原则，使整个系统达到产出最大的目。系统达到产出最大的目。Goldratt 1990年发表的年发表的 “Theory of Constraints”代表代表着“约束理论”的正式诞生；着“约束理论”的正式诞生；传统的管理思想认为，只要不断地在各个环节、各个部传统的管理思想认为，只要不断地在各个环节、各个部门致力于改进，就可以带来整个系统的改进。门致力于改进，就可以带来整个系统的改进。TOC理论认为理论认为：一个系统的产出速度和产出量取决于系：一个系统的产出速度和产出量取决于系统各个环节中的瓶颈环节，管理的目标应该放在寻找并统各个环节中的瓶颈环节，管理的目标应该放在寻找并消除瓶颈环节上；消除瓶颈环节上；以简单常识处理复杂问题以简单常识处理复杂问题 6 TOC五步法五步法 1.约束识别与评价；约束识别与评价；2.根据某种准则确定最紧的根据某种准则确定最紧的瓶颈约束瓶颈约束；3.按瓶颈约束的按瓶颈约束的边际贡献边际贡献进行决策选择；进行决策选择；4.对选择结果进行评价；对选择结果进行评价；5.上面步骤中如果任何一个约束被打破，回到第上面步骤中如果任何一个约束被打破，回到第1步；步；TOC理论试图不停顿地对约束进行识别、评价与理论试图不停顿地对约束进行识别、评价与改进来改善系统效率。改进来改善系统效率。2 7 材料材料1 材料材料2 材料材料3 材料材料4 设备设备A 设备设备B 设备设备A$10$15 10分钟分钟 设备设备C$15 设备设备D 设备设备E 5分钟分钟 15分钟分钟 15分钟分钟 设备设备A 材料材料2$15 10分钟分钟 10分钟分钟 5分钟分钟 设备设备E 5分钟分钟 设备设备C 5分钟分钟 设备设备D 10分钟分钟 设备设备E 10分钟分钟$10 产品产品X 产品产品Y 产品产品Z$90$100$70 50/周周 75/周周 100/周周 TOC计算举例计算举例 需需求求端端 供供应应端端 生产过程生产过程 材料材料单位成本单位成本XYZ110121521315114101成本成本403025产品产品ABCDE合计合计单位加单位加工成本工成本加工加工成本成本X20015155550.422Y101052510600.424Z5105105350.4148 能力限制能力限制 满足全部市场需求需要以下加工能力：满足全部市场需求需要以下加工能力：D的需求大于实际能力，的需求大于实际能力，D为为瓶颈约束瓶颈约束；XYZ合计合计实际能力实际能力 负荷率负荷率A 1000750500225024000.94B 07501000175024000.73C 750375500162524000.68D 75018751000362524001.51E 250750500150024000.63瓶颈 9 产品盈利计算产品盈利计算*$4000固定成本按满足全部需求时，生产每种产品的固定成本按满足全部需求时，生产每种产品的加工时间占加工总时间的比例分摊到每种产品上。加工时间占加工总时间的比例分摊到每种产品上。1 3 2 1 2 3 直接成本直接成本*项目 产品项目 产品XYZ销售价格销售价格9010070材料成本材料成本403025加工成本加工成本222414毛利毛利284631分摊固定成本分摊固定成本20.522.313.0会计利润会计利润7.523.718.010 1.按毛利（利润）顺序排产按毛利（利润）顺序排产 产品产品X YZ 合计合计增减增减销售价格销售价格901007011175100%材料成本材料成本4030253562.5加工费加工费2224142535毛利润毛利润2846315077.5100%分摊固定成本分摊固定成本34.737.922.14000会计利润会计利润-6.78.18.91077.5100%占用占用D能力能力1525102400市场需求市场需求5075100产量决策产量决策07552.52 1 2 1 3 3 11 2.按约束理论排产按约束理论排产 产品产品X YZ 合计合计相对增减相对增减销售价格销售价格9010070141002617%材料成本材料成本4030255280加工费加工费2224143124毛利润毛利润284631569612.18%分摊固定成本分摊固定成本28.230.717.94000会计利润会计利润-0.215.313.1169657.40%占用占用D能力能力1525102400毛利毛利/D能力能力1.871.843.102.56市场需求市场需求5075100产量决策产量决策50261001 2 3 1 2 3 约束理论排产找到了最优产量决策，销售额上升约束理论排产找到了最优产量决策，销售额上升26.17%，毛利，毛利上升上升12.18%，净利润上升，净利润上升57.4%，12 约束理论存在的问题约束理论存在的问题 多瓶颈困难多瓶颈困难：每次只能考虑一个瓶颈约束，无法很：每次只能考虑一个瓶颈约束，无法很好解决存在多瓶颈的复杂问题；好解决存在多瓶颈的复杂问题；负荷率计算负荷率计算：负荷率的计算要求有标定的产量（如：负荷率的计算要求有标定的产量（如市场需求），对市场需求没有限制的问题，如何计市场需求），对市场需求没有限制的问题，如何计算负荷率；算负荷率；无有效算法无有效算法：计算方法类似于启发式方法，结果的：计算方法类似于启发式方法，结果的最优性无法从理论上证明；最优性无法从理论上证明；求解工具求解工具：没有好的求解软件；：没有好的求解软件；线性规划是解决多瓶颈下资源配置的最有效方法线性规划是解决多瓶颈下资源配置的最有效方法 3 13 基于边际分析的优化方法基于边际分析的优化方法 线性规划是研究资源优化配置的最常用方法；线性规划是研究资源优化配置的最常用方法；基于边际分析的决策方法；基于边际分析的决策方法；最优性（均衡）条件：资源利用的边际收益相等；最优性（均衡）条件：资源利用的边际收益相等；分配资源分配资源 A 单位单位 B 单位单位 C 单位单位 数量 边际收益 数量 边际收益 数量 边际收益 QB QA QC 边际收边际收益相等益相等 max:f(Q)s.t.QA+QB+QC Q 14 2 线性规划模型与图解法 管理中管理中应用最广泛的数量分析方法：应用最广泛的数量分析方法数学规划（线性规划，整数规划）、网络规划、数学规划（线性规划，整数规划）、网络规划、动态规划；模拟、决策分析、排队理论、动态规划；模拟、决策分析、排队理论、整数规划整数规划、网络规划网络规划、目标规划和多目标规划都目标规划和多目标规划都是以线性规划为基础是以线性规划为基础；15 例例1 产品组合问题产品组合问题 家具厂生产桌子、椅子两种产品，市场销售价格分别为家具厂生产桌子、椅子两种产品，市场销售价格分别为 100 元元/件和件和 65 元元/件。件。生产一个桌子需要用木工生产一个桌子需要用木工 4 小时，油漆工小时，油漆工 2 小时；小时；生产一个椅子需要用木工生产一个椅子需要用木工 3 小时，油漆工小时，油漆工 1 小时；小时；生产成本：木工、油漆工的小时成本分别为生产成本：木工、油漆工的小时成本分别为 10 和和 5 元元 桌子：桌子：410+25 =50元，利润元，利润=100 50=50元元 椅子：椅子：310+15 =35元，利润元，利润=65 35=30元元 该厂每周可使用的木工和油漆工工时分别为该厂每周可使用的木工和油漆工工时分别为 120 和和 50 小时；小时；问：如何生产才能使销售利润最大？问：如何生产才能使销售利润最大？典型典型的生产组合的生产组合问题（问题（Production Mix）16 生产利润高的产品生产利润高的产品：最多生产最多生产25个桌子，销售利润个桌子，销售利润1250元；元；油漆工工时用完，但木工资源剩余油漆工工时用完，但木工资源剩余20小时。小时。组合生产方案组合生产方案 1：调整生产桌、椅的数量调整生产桌、椅的数量 生产生产20个桌子，个桌子，10个椅子，销售利润个椅子，销售利润1300元；元；油漆工工时用完，木工资源仍剩余油漆工工时用完，木工资源仍剩余10小时。小时。组合生产方案组合生产方案 2：继续调整生产桌、椅的数量继续调整生产桌、椅的数量 生产生产15个桌子，个桌子，20个椅子，销售利润个椅子，销售利润1350元；元；全部工时用完全部工时用完 资源得到有效利用资源得到有效利用 最优解；最优解；优化：选择好的生产方案优化：选择好的生产方案 17 家具厂的数学家具厂的数学模型模型 决策变量决策变量：桌桌椅产量椅产量 x1=生产桌子的数量生产桌子的数量，x2=生产椅子的数量生产椅子的数量；目标函数目标函数：生产生产利润最大化利润最大化 max z=50 x1+30 x2 约束方程约束方程：条件条件限制限制 s.t.木工工时限制：木工工时限制：4x1+3x2 120 油漆工工时限制：油漆工工时限制：2x1+x2 50 非负约束非负约束：x1 0，x2 0 18 假定一个成年人每天需要从食物中获取假定一个成年人每天需要从食物中获取3000大卡热大卡热量量、55克蛋白质和克蛋白质和800毫克钙毫克钙，市场上有四种食品市场上有四种食品可供选择可供选择。每公斤所含热量和营养及价格见下表每公斤所含热量和营养及价格见下表，问问：如何选择才能在满足营养前提下使费用最小如何选择才能在满足营养前提下使费用最小。例例2 营养配餐问题营养配餐问题（Diet Problem）序号序号 食品食品 热量热量 蛋白质蛋白质 钙钙 价格价格 名称名称 (大卡大卡)(g)(mg)(元元)1 猪肉猪肉 1000 50 400 14 2 鸡蛋鸡蛋 800 60 200 6 3 大米大米 900 20 300 3 4 白菜白菜 200 10 500 2 4 19 营养配餐模型营养配餐模型 变量：变量：xj 购入购入 j 种食品种食品数数量。量。目标目标函数：采购成本最小函数：采购成本最小 min:z=14x1+6x2+3x3+2x4 约束方程：约束方程：s.t.满足热量满足热量:1000 x1+800 x2+900 x3+200 x4 3000 满足蛋白质：满足蛋白质：50 x1+60 x2+20 x3+10 x4 55 满足钙：满足钙：400 x1+200 x2+300 x3+500 x4 800 非负约束：非负约束：x1，x2，x3，x4 0 20 例例3 一般的资源优化模型一般的资源优化模型 某经济组织利用某经济组织利用 m 种资源从事种资源从事 n 种经营活动（如采种经营活动（如采购、制造、销售等）；购、制造、销售等从事第从事第 j（j=1,n）种经营活动需要使用数量为）种经营活动需要使用数量为 aij 的第的第 i（i=1,m）种资源，并可为组织带来）种资源，并可为组织带来 cj 的收益，组织可使用资源的限制为的收益，组织可使用资源的限制为bi，问：该组织如何经营，并使其收益最大化；问：该组织如何经营，并使其收益最大化；求解求解 n 种经营活动竞争使用种经营活动竞争使用m 种资源种资源 的的资源优化资源优化问题问题，设模型的变量设模型的变量 xj 为第为第 j 种经营活动的活动规模；种经营活动的活动规模；21 模型模型可以写为可以写为：max:z=c1x1+c2 x2+cnxn s.t.a11x1+a12x2+a1nxn b1 am1x1+am2x2+amnxn bm x1,x2,xn 0 表现为线性规划模型的一般形式；表现为线性规划模型的一般形式；线性规划的标准形式线性规划的标准形式:资源优化配置模型资源优化配置模型 矩阵表示矩阵表示:max cx s.t.Ax b x 0 max cx s.t.Ax=b x 0 22 决策变量决策变量：x1,.,xn 为决策变量为决策变量，表示表示第第 n 种种经济经济活活动动的活动的活动规模规模；目标函数目标函数：z=c1x1+cnxn反映反映经营经营活动目标活动目标。cj 为目标函数系数为目标函数系数（或或价值系数价值系数），表示表示与经营与经营活动活动相关相关的收益的收益（cj 0为费用为费用）；约束约束：ai1x1+ainxn bi 使用第使用第 i 种种资源的限制；资源的限制；约束约束系数：系数：aij也称也称技术系数或投入产出系数技术系数或投入产出系数，代表代表第第 j 种经营活动需要第种经营活动需要第 i 种资源的种资源的数数量量；右边项右边项：b=(b1,.,bm)代表代表 m 种资源的可用种资源的可用数数量量 非负约束非负约束：xj 0 决策变量的取值范围的决策变量的取值范围的限制限制。线性规划模型的一般形式线性规划模型的一般形式 23 线性规划的图解法线性规划的图解法 图解法图解法：直观了解线性规划基本原理和几何意义：直观了解线性规划基本原理和几何意义；GTC公司制造板手和钳子，制造过程包括成型和装公司制造板手和钳子，制造过程包括成型和装配两道工序。制定生产计划需考虑钢材数量、设备配两道工序。制定生产计划需考虑钢材数量、设备能力、市场需求和销售利润等限制条件，能力、市场需求和销售利润等限制条件，请构造一请构造一个生产利润最大的线性规划模型；个生产利润最大的线性规划模型；资源约束条件资源约束条件 扳手扳手 钳子钳子 可用数量可用数量 工具钢（磅）工具钢（磅）1.5 1.0 27,000 磅磅/天天 成型机（小时）成型机（小时）1.0 1.0 21,000 小时小时/天天 装配机（小时）装配机（小时）0.3 05 9,000 小时小时/天天 需求限制（件需求限制（件/天）天）15,000 16,000 销售利润（销售利润（1000件）件）$130$100 24 决策变量：决策变量：W :每天生产扳手的数量（以千件计）每天生产扳手的数量（以千件计）P :每天生产钳子的数量（以千件计）每天生产钳子的数量（以千件计）模型模型 Maximize:130 W +100 P Subject to:钢材钢材:1.5 W +P 27 成型成型:W +P 21 装配装配:0.3W +0.5P 9 扳手需求扳手需求:W 15 钳子需求钳子需求:P 16 非负约束非负约束:W,P 0 GTC公司生产计划模型公司生产计划模型 5 25 图解法求解图解法求解GTC模型模型 0 30 钳子需求钳子需求 扳手需求扳手需求 15 钳子钳子 扳手扳手 可行域可行域 装配能力约束装配能力约束 成型能力约束成型能力约束 钢材供应量约束钢材供应量约束 最优解最优解 1.5W+P 27 W P 0.3W+0.5P 9 W+P 21 30 5 10 15 20 25 26 存在多个最优解的图示存在多个最优解的图示 0 30 30 扳手需求扳手需求 钳子需求钳子需求 5 10 15 20 25 15 钳子钳子 扳手扳手 可行域可行域 装配装配 钢材供应钢材供应 多个最优解多个最优解 将成型约束改为：将成型约束改为：1 hrs1 hrs for W and for W and 1 hrs1 hrs for Pfor P 可用量改为可用量改为 21,000 hrs/day21,000 hrs/day 1.31.3 24,60024,600 成型成型 27 有无界解的线性规划问题有无界解的线性规划问题（Unbounded Solution）x 0 y 0 x+y 20 x 5-2 x+5 y 150 s.t Max x+1/3y 可行域可行域 x 30 10 20 y 0 10 20 40 0 30 40 28 3 线性规划求解方法 单纯形方法是求解线性规划的最有效的方法之一，单纯形方法是求解线性规划的最有效的方法之一，目前大部分商业软件都使用单纯形方法目前大部分商业软件都使用单纯形方法 单纯形方法的基本思想是从可行域的一个基本可行单纯形方法的基本思想是从可行域的一个基本可行解（极点）出发，判别它是否已是最优解，如果不解（极点）出发，判别它是否已是最优解，如果不是，寻找下一是，寻找下一 个基本可行解，并使目标函数得到改个基本可行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无进，如此迭代下去，直到找到最优解或判定问题无解或无界为止。解或无界为止。29 线性规划的基模型求解的基础线性规划的基模型求解的基础 基的基的定义定义：给定线性规划问题给定线性规划问题 P：max cx|Ax=b,x 0 A是是 m n 满秩矩阵满秩矩阵,nm,若若 B 是其中任一个是其中任一个 m m 满秩子矩阵满秩子矩阵，则称则称 B 是是 P 的一个的一个基基。基变量与非基变量基变量与非基变量 假定假定 B 由由 A 中前中前 m 个列向量个列向量构成，约束矩阵可划构成，约束矩阵可划分为分为 A=(B,N)，P 可表示为：可表示为：max z=cB xB+cN xN s.t.B xB+N xN=b xB,xN 0 xB 基变量基变量 xN 非基变量非基变量 30 基本解基本解 线性方程组线性方程组 BxB=b 的解的解 如果如果令令 xN=0，则则有：有：Ax=BxB+NxN=BxB=b B 满秩满秩有逆有逆线性方程组线性方程组 BxB=b 有唯一解有唯一解：xB=B-1b 则则 x=(xB,xN)T=(B-1b,0)T 是是 P 的的基本解基本解。基本可行解基本可行解 满足非负条件的基本解满足非负条件的基本解（即（即:xB=B-1b 0）为为基基本可行解本可行解。基本解与基本可行解基本解与基本可行解 6 31 可可 行行 解解 基基本本 可可行行解解 基基 本本 解解 基本解与基本可行解基本解与基本可行解 可行域可行域 可行解可行解 基本解基本解 基本可行解基本可行解 32 设设 B 是是 P 的一个基，的一个基，A=(B,N)，问题问题 P 可写为：可写为：max z=cB xB+cN xN s.t.B xB+N xN=b xB，xN 0 因因 B 有逆，有：有逆，有：xB=B-1(b NxN)=B-1b B-1NxN 将将 xB=B-1b B-1NxN 代入目标函数代入目标函数 z：z=cB xB+cN xN=cB(B-1b B-1NxN)+cN xN =cB B-1b+(cN cB B-1N)xN 单纯形方法的数学推导单纯形方法的数学推导 33 得到得到线性规划的新形式线性规划的新形式：max:z=cBB-1b+(cN cBB-1N)xN s.t.xB=B-1b B-1NxN xB,xN 0 检验向量：检验向量：=cN cBB-1N 检验分量：检验分量：j=cj cBB-1pj 通过分析检验向量通过分析检验向量 =cN cBB-1N 的正负，选择被的正负，选择被换入基的非基变量，并使目标函数改善；换入基的非基变量，并使目标函数改善；如果通过换基迭代后，检验向量如果通过换基迭代后，检验向量 0（对（对 max 问问题），题），P 得到最优解，求解结束；得到最优解，求解结束；j 被称为被称为检验数检验数或或递减成本递减成本(reduced cost)基本可行解基本可行解 x=(B-1b,0)T 单纯形方法的数学推导单纯形方法的数学推导 34 例：求解家具厂的线性规划模型：例：求解家具厂的线性规划模型：max z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0 加入松弛变量加入松弛变量 x3,x4 将问题转化为标准型：将问题转化为标准型：max z=50 x1+30 x2 s.t.4x1+3x2+x3 =120 2x1+x2 +x4=50 x1,x2,x3,x4 0 令令 x3,x4为基变量为基变量 单纯形方法计算举例单纯形方法计算举例 35 将非基变量将非基变量 x1,x2 移到等式右边移到等式右边 max z=50 x1+30 x2 s.t.x3=120-4x1-3x2 x4=50-2x1-x2 x1,x2,x3,x4 0 令令x1,x2等于零得到初始可行解等于零得到初始可行解 x1=(0,0,120,50)，z1=0 该解是最优解吗该解是最优解吗？如何判断如何判断？从经济意义判断：资源没有充分利用；从经济意义判断：资源没有充分利用；从数学意义判断：从数学意义判断：x1,x2 增加可以使目标增加；增加可以使目标增加；初始可行解初始可行解 40 30 20 10 10 20 30 初始可行解初始可行解 x1 x2 36 令令 x1入基入基,x4出基出基（基变量基变量:x1,x3,非基变量非基变量:x2,x4）约束方程整理为约束方程整理为:4x1+x3=120 3x2 2x1 =50 x2 x4 整理后的模型：整理后的模型：max:z =1250+5x2 25x4 s.t.x1=25 0.5x2 0.5x4 x3=20 x2+2x4 第二个可行解：第二个可行解：x2=(25,0,20,0)，z2=1250 该解是否为最优解该解是否为最优解？如何判断如何判断？第一次换基迭代第一次换基迭代 40 30 20 10 10 20 30 第二个可行解第二个可行解 x1 x2 7 37 令令x2入基入基,x3出基出基（基变量基变量:x1,x2,非基变量非基变量:x3,x4）约束方程整理为约束方程整理为:4x1+3x2=120 x3 2x1+x2=50 x4 换基后的模型为：换基后的模型为：z =1350 5x3 15 x4 x1=15+0.5x3 1.5x4 x2=20 x3+2x4 第三个可行解为第三个可行解为 x3=(15,20,0,0)，z3=1350 目标中非基变量的系数都为负目标中非基变量的系数都为负，无法继续改进无法继续改进。第二次换基迭代第二次换基迭代 40 30 20 10 10 20 30 最优解最优解 x1 x2 38 4 求解线性规划的软件工具 实用线性规划的求解必须要借助于计算机工具；实用线性规划的求解必须要借助于计算机工具；一般软件可以求解几百个变量的问题，商业软件一般软件可以求解几百个变量的问题，商业软件可求解有几万直至上百万变量的线性规划问题；可求解有几万直至上百万变量的线性规划问题；随着计算机和软件技术的进步，人们已经可以在随着计算机和软件技术的进步，人们已经可以在笔记本电脑上求解有十几万变量的复杂问题。笔记本电脑上求解有十几万变量的复杂问题。39 使用使用 EXCEL 求解线性规划求解线性规划 Excel 为大多数没有受过为大多数没有受过OR/MS专门专门训练的训练的使用者使用者提供了可以求解提供了可以求解线性规划线性规划，非线性规划非线性规划和和整数规划整数规划的“的“规划求解规划求解”软件；”软件；最初由最初由Frontline System(http:/)提供，后被提供，后被Solver收购收购(http:/)，Excel将将GUI，各种函数功能，模型各种函数功能，模型构造构造，优化，优化求解求解和编程功能和编程功能(VBA)结合在统一的环境下结合在统一的环境下，提供了强，提供了强大的数据组织、运算和呈现功能：大的数据组织、运算和呈现功能：可用更专业方式提供模型使用的数据；可用更专业方式提供模型使用的数据；可将输出结果用各种图表的方式表示出来；可将输出结果用各种图表的方式表示出来；40 进入进入EXCEL中的优化模块中的优化模块 选择选择“工具工具”“规划求解规划求解”进入规划求解进入规划求解对话对话窗窗口：口：2007版本：版本：通过“通过“数据数据”“规划求解规划求解”进入求解”进入求解对话框对话框；加载“规划求解”加载“规划求解”2003版本：版本：通过“工具”通过“工具”“加载宏”安装“加载宏”安装“规划规划求解求解”；2007版本：单击最左上角的“版本：单击最左上角的“Office 按钮”按钮”，然后，然后单击“单击“Excel 选项”。选项”。单击“加载项”，在最下面的“管理”框中，选择单击“加载项”，在最下面的“管理”框中，选择“Excel 加载项”，单击“转到”。加载项”，单击“转到”。在“可用加载宏”框中，选中“规划求解加载项”在“可用加载宏”框中，选中“规划求解加载项”复选框，然后单击“确定”。复选框，然后单击“确定”。如果如果 “规划求解加载项”未在“可用加载宏”中列“规划求解加载项”未在“可用加载宏”中列出，请单击“浏览”找到该加载宏。出，请单击“浏览”找到该加载宏。41 42 定义决策变量定义决策变量 决策变量可通过决策变量可通过表格表格（cell）定义；）定义；普通版本最多允许求解小于普通版本最多允许求解小于200个变量的问题；个变量的问题；可用“推测”按钮得到最初的变量组，该功能将所可用“推测”按钮得到最初的变量组，该功能将所有与目标函数相关的数据格（不含公式）假设为变有与目标函数相关的数据格（不含公式）假设为变量格；量格；8 43 定义约束方程定义约束方程 在参数定义窗口中可进行添加、修改、删除约束的在参数定义窗口中可进行添加、修改、删除约束的操作；操作；约束方程约束方程:由描述约束左、右边项格之间的关系定由描述约束左、右边项格之间的关系定义；义；定义约束左边项定义约束左边项一般为公式一般为公式 定义约束右边项定义约束右边项一般为数据一般为数据 44 为变量、约束、数据命名为变量、约束、数据命名 变量、约束和参数都可以定义名称（通过“插入”变量、约束和参数都可以定义名称（通过“插入”“名称”定义“名称”定义);在在Office2007中：通过“公式”中：通过“公式”“名称管理器”“名称管理器”“新建”，为单元格命名。“新建”，为单元格命名。45 定义名称使模型描述更为清晰定义名称使模型描述更为清晰 46 模型求解模型求解 Excel可以求解线性规划、非线性规划和整数规划可以求解线性规划、非线性规划和整数规划模型，模型，省缺设置是求解非线性规划省缺设置是求解非线性规划；可通过“选项”按钮修改省缺设置；可通过“选项”按钮修改省缺设置；采用线性模型采用线性模型：解线性规划；：解线性规划；假定非负：所有变量为非负变量；假定非负：所有变量为非负变量；自动按比例缩放：调整参数的大小差距；自动按比例缩放：调整参数的大小差距；47 例例5 NBS 原料供应问题原料供应问题 New Bedford Steel(NBS)是一家小型钢铁制造企业，是一家小型钢铁制造企业，焦炭是炼铁原材料，焦炭是炼铁原材料，NBS每年需要采购每年需要采购100到到150万万吨左右的炼焦煤，需要根据以下条件制订明年的炼吨左右的炼焦煤，需要根据以下条件制订明年的炼焦煤采购计划：焦煤采购计划：需求需求：预测明年需要：预测明年需要1225千吨炼焦煤；千吨炼焦煤；供应商供应商：8 家煤矿投标，产品的价格和质量不同；家煤矿投标，产品的价格和质量不同；质量约束质量约束：煤的平均挥发物含量不能小于：煤的平均挥发物含量不能小于19；工会关系工会关系：不少于：不少于50的炼焦煤需要从参加煤矿工会的炼焦煤需要从参加煤矿工会的供应商处采购；的供应商处采购；运输约束运输约束：铁路运量限制为：铁路运量限制为650千吨，公路运量限制千吨，公路运量限制为为720千吨；千吨；48 NBS 原材料供应表原材料供应表 问题：在满足各种约束条件下，问题：在满足各种约束条件下，NBS从每个煤矿采从每个煤矿采购多少煤能够使采购成本最低？购多少煤能够使采购成本最低？Bids from Potential Coking Coal Suppliers资源资源ABCDEFGH生产能力生产能力300600510655575680450490工会工会UUNUNUNN运输方式运输方式RTRTTTRR挥发度挥发度1516182021222325价格价格49.550.061.063.566.571.072.580.09 49 NBS 原材料采购模型原材料采购模型 变量：煤矿的采购数量为变量：煤矿的采购数量为 A,B,C,D,E,F,G,H 目标函数：总采购成本最小化目标函数：总采购成本最小化 Min:49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H 约束方程：约束方程：需要采购需要采购1225 千吨煤千吨煤 A+B+C+D+E+F+G+H=1225 不少于不少于50%的煤从参加煤矿工会的煤矿采购的煤从参加煤矿工会的煤矿采购 A+B+D+F C+E+G+H 等价于：等价于：A+B C+D E+F G H 0 50 NBS 原材料采购模型原材料采购模型 铁路和公路运输能力的约束：铁路和公路运输能力的约束：公路公路:B+D+E+F 720 铁路铁路:A+C+G+H 650 挥发物平均含量不小于挥发物平均含量不小于19%15A+16B+18C+20D+21E+22F+23G+25H 19(A+BC+D+E+F+G+H)整理整理:-4A-3B-C+D+2E+3F+4G+6H 0 各个煤矿生产能力限制各个煤矿生产能力限制:A 300 B 600 C 510 D 655 E 575 F 680 G 450 H 490 非负约束非负约束:A,B,C,D,E,F,G,H 0 51 整理后的模型整理后的模型 Min:49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80F s.t.需求需求:A+B+C+D+E+F+G+H 1225 工会工会:A+B C+D E+F G-H 0 挥发度挥发度:-4A-3B-C+D+2E+3F+4G+6H 0 公路公路:B+D+E+F 720 铁路铁路:A+C+G+H 650 生产能力生产能力:A 300，B 600，C 510，D 655 E 575，F 680，G 450，H 490 非负约束非负约束:A,B,C,D,E,F,G,H 0 52 NBS 的的 EXCEL 模型模型 NBS模型模型资源资源ABCDEFGH约束约束实际实际 限制限制生产能力生产能力 300600510655575680450490 总采购量总采购量 1225 1225工会工会UUNUNUNN工会数量工会数量 55%50%运输方式运输方式RTRTTTRR挥发度挥发度00挥发度挥发度1516182021222325铁路运量铁路运量505650价格价格49550.061.063.566.571.072.580.0 公路运量公路运量720720购买数量购买数量5560002010004500目标函数目标函数73267.553 NBS敏感性分析表敏感性分析表 可变单元格可变单元格终终递减递减目标式目标式允许的允许的允许的允许的单元格单元格名字名字值值成本成本系数系数增量增量减量减量$B$20 购买数量购买数量 A550.0049.50.51$C$20 购买数量购买数量 B600-1.50501.51E+30$D$20 购买数量购买数量 C02.50611E+302.5$E$20 购买数量购买数量 D200.0063.50.1250.05$F$20 购买数量购买数量 E1000.0066.50.050.125$G$20 购买数量购买数量 F01.50711E+301.5$H$20 购买数量购买数量 G450-1.0072.511E+30$I$20购买数量购买数量 H00.50801E+300.5约束约束终终阴影阴影约束约束允许的允许的允许的允许的单元格单元格名字名字值值价格价格限制值限制值增量增量减量减量$L$6工会数量工会数量 实际实际6750.0001251E+30$L$7平均挥发度平均挥发度 实际实际03.00020100$L$8铁路运量铁路运量 实际实际5050.006501E+30145$L$9公路运量公路运量 实际实际7201.00720203.333$L$5采购数量采购数量 实际实际1,22561.50122552554 材料材料1 材料材料2 材料材料3 材料材料4 设备设备A 设备设备B 设备设备A$10$15 10分钟分钟 设备设备C$15 设备设备D 设备设备E 5分钟分钟 15分钟分钟 15分钟分钟 设备设备A 材料材料2$15 10分钟分钟 10分钟分钟 15分钟分钟 设备设备E 5分钟分钟 设备设备C 5分钟分钟 设备设备D 10分钟分钟 设备设备E 10分钟分钟$10 产品产品X 产品产品Y 产品产品Z$90$100$70 50/周周 75/周周 100/周周 ABCDE材料成本材料成本X2001515540Y10105251030Z1510510525例例6.TOC问题的优化计算问题的优化计算 需需求求端端 供供应应端端 生产过程生产过程 修改修改参数参数 10 55 同时出现两个能力限制瓶颈同时出现两个能力限制瓶颈 如果满足全部需求，则需要以下加工能力如果满足全部需求，则需要以下加工能力 A和和D的需求都大于实际能力，的需求都大于实际能力，A和和D为瓶颈约束；为瓶颈约束；但但D的负荷率最大。的负荷率最大。XYZ合计合计实际能力实际能力 负荷率负荷率A 10007501500325024001.35B 07501000175024000.73C 750375500162524000.68D 75018751000362524001.51E 250750500150024000.6356 1.按毛利顺序排产结果按毛利顺序排产结果 产品产品XYZ合计合计增减增减销售价格销售价格901007010650100%材料成本材料成本4030253650加工费加工费2224182570毛利润毛利润2846274430100%分摊固定成本分摊固定成本34.237.428.04000会计利润会计利润-6.28.6-1.0430100%占用占用D能力能力1525102400占用占用A能力能力2010151450市场需求市场需求5075100产量决策产量决策357501 2 3 1 2 3