《excel求解---第一章 线性规划和灵敏度分析》由会员分享,可在线阅读,更多相关《excel求解---第一章 线性规划和灵敏度分析(51页珍藏版)》请在金锄头文库上搜索。
1、应用EXCEL求解运筹学问题,一、EXCEL求解线性规划问题,求解线性规划 影子价格和灵敏度分析,线性规划模型的描述,例1:某工厂生产两种新产品:门和窗。经测算,每生产一扇门需要在车间1加工1小时、在车间3加工3小时;每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。已知每扇门的利润为300元,每扇窗的利润为500元。根据市场调查得到的这两种新产品的市场需求状况可以确定,按当前的定价可确保所有的新产品均能销售出去。问:该工厂如何安排这两种新产品的生产计划,才能使总利润最大?,线性规划模型的描述,数据表格:,线性规
2、划模型的建立,假设:每周各生产门和窗x1、x2个。 建立线性规划模型如下: Max Z=300x1+500x2 x14 2x212 3x1+2x218 x1、x20,EXCEL求解线性规划模型,一、在EXCEL电子表格中建立线性规划模型 预处理:加载宏规划求解 1、把相关数据输入到EXCEL电子表格中,EXCEL求解线性规划模型,EXCEL表格模型有关的四类单元格: 数据单元格:单位利润(C4:D4)、 可用工时(G7:G9) 可变单元格:每周产量(C12:D12) 输出单元格:实际使用(E7:E9) 目标单元格:总利润 (G12),EXCEL求解线性规划模型,2、主要求解结果 两种新产品每周
3、的产量; 两种新产品每周各实际使用的工时(不能超过计划工时); 两种新产品的总利润,EXCEL求解线性规划模型,3、主要结果的计算方法 (1)两种新产品的每周产量:C12、D12,初始值为0。 (2)实际使用工时计算(三种方法) 1)分别在E7、E8、E9中输入相应的计算公式: E7:C7*C12+D7*D12 E8:C8*C12+D8*D12 E9:C9*C12+D9*D12,EXCEL求解线性规划模型,2)复制、粘贴方法: 在E7中输入:C7*$C$12+D7*$D$12 复制E7单元格到E8、E9 3)公式法: 在E7中输入: =SUMPRODUCT(C7:D7,$C$12:$D$12)
4、 复制E7单元格到E8、E9,EXCEL求解线性规划模型,(3)总利润计算: 在G12单元格输入公式: =C4*C12+D4*D12 或: =SUMPRODUCT(C4:D4,C12:D12),EXCEL求解线性规划模型,收集问题数据; 在电子表格中输入数据(数据单元格); 确定决策变量单元格(可变单元格); 输入约束条件左边的公式(输出单元格)使用SUMPRODUCT函数简化输入; 输入目标函数公式(目标单元格)。使用SUMPRODUCT函数简化输入。,在电子表格中建立线性规划模型步骤总结,EXCEL求解线性规划模型,二、在EXCEL电子表格中求解线性规划模型 1、求解参数设置: “工具”规
5、划求解“,弹出“规划求解参数”对话框,设置求解相关参数。,EXCEL求解线性规划模型,2、约束的设置: 单击 “添加”,弹出“添加约束”,添加约束条件。,EXCEL求解线性规划模型,3、求解选项设置: 单击“选项”,弹出“规划求解选项”对话框。选择“采用线性模型”和“假定非负”。,EXCEL求解线性规划模型,4、求解及结果 单击“求解”,开始规划求解。弹出“规划求解结果”对话框。选择“保存规划求解结果”。,EXCEL求解线性规划模型,5、电子表格显示结果: 单击“确定”,在电子表格的可变单元格、输出单元格及目标单元格出现求解结果。,练习,某家具厂生产5种不同规格的家具,每件家具要经过成型、打磨
6、、上漆等几个主要生产工序。每种家具的每道工序所需要的时间以及每道工序的可用时间、每种家具的利润如下表所示,问:工厂应该如何安排生产,才能使得总利润最大?,输入数据 标识数据 每个数据对应唯一单元格 在电子表格中显示完整模型 数据、公式分离 保持简单化 使用相对和绝对地址简化公式并复制 使用边框、底色区分单元格类型,建模求解要点回顾,线性规划问题解的讨论,1、线性规划问题解的种类? 2、唯一解的表现是? 3、无穷解的表现是? 4、无可行域无解的表现是? 5、可行域无界的表现是? 上述结果用EXCEL建模求解的最后对话框提示不同。,EXCEL求解线性规划模型,图解法解得分析:,解的结果,有可行域,
7、无可行域,可行域有界,可行域无界,唯一解,无穷解,唯一解,无穷解,无解,一定无解,练习1,练习2,练习3,综合练习1,某公司是商务房地产开发项目的主要投资商。目前,该公司有机会在三个建设项目中投资: 项目1:建造高层办公楼 项目2:建造宾馆 项目3:建造购物中心 每个项目都要求投资者在四个不同的时期投资:在当前预付定金,以及一年、两年、三年后追加投资。右面表中显示了四个不同时期每个项目所需的资金。投资者可以按照一定的比例进行投资和获得相应比例的收益。 目前公司有2500万资金可供投资,预计一年后,又可获得2000万元,两年后获得另外的2000万元,三年后还有1500万元可供投资。那么,该公司要
8、再每个项目上按照多大比例投资,才能使得投资组合获得最大的总净现值?,综合练习,某公司生产甲、乙、丙三种产品,都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作,亦可以自行生产,但产品丙必须本厂铸造才能保证质量。数据如下表。问:公司为了获得最大利润,甲、乙、丙三种产品各生产多少件?甲、乙两种产品的铸造中,由本公司铸造和由外包协作各应多少件?,数学模型,决策变量 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数, x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。 目标函数:Max 15x1 + 10x2 + 7x3 + 13x4
9、 + 9x5 约束条件:,5x1 + 10x2 + 7x3 8000,6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000,3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000,x1,x2,x3,x4,x5 0,灵敏度分析,线性规划问题的灵敏度分析是在求出最优解的基础上,进一步讨论当ai,bi和ci发生变化时,对最优解的影响。 判断某一参数发生变化时,原最优解是否发生变化? 怎样得出使原最优解不变的参数变化范围 当最优解发生变化时,怎样求出新的最优解。,单个cj变动,比如当门的单位利润由原来的300元提升到500元,最优解是否发生变化,对总利润产生什么影响? 方法1
10、:利用电子表格分析,改变参数重新计算,观察结果 方法2:灵敏度分析,方法1:电子表格分析,最优解不变,总利润上升,方法2:灵敏度分析,对原电子表格模型运行“规划求解”功能,得出“规划求解结果”对话框,选择“敏感性报告”选项,得出结果。,比较,2、多个cj变动,例如把门的利润由300提高到450,同时把窗的单位利润由500减少到400,原来的最优解和最优值是否会发生变化。 方法1:电子表格分析,改变参数 方法2:灵敏度分析,电子表格分析,最优解不变,总利润下降300,灵敏度分析,应用敏感性报告以及百分之一百法则进行分析。 百分之一百法则: 对于所有变化的目标函数决策变量系数(或约束条件右边常数)
11、,当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时,最优解不变。,EXCEL求解线性规划模型,允许增加量百分比= 实际增加量(上限-现在值)/允许增加量 允许减少量百分比= 实际减少量(现在值-下限)/允许减少量 例:门300450;窗500400 例:门300600;窗500300 如果超过100%,用电子表格模型重新求解 思考:当结果刚好为100%时,最优解变吗?,EXCEL求解线性规划模型,应用规则: 当允许增加量(减少量)为无穷大时,则对于任一个增加量(减少量),其允许增加(或减少)的百分比都看成零。 百分之一百法则是判断最优解变与不变的充分条件,但不是必要条件。 不能应用
12、于目标函数决策变量系数和约束条件右端常数同时变化的情况。,EXCEL求解线性规划模型,3、单个bi变动 例:如果车间2的可用工时由12小时增加到13小时,原来的最优解和最优值是否发生变化? 方法1:应用电子表格进行分析 改变电子表格模型中相应的参数,再运行EXCEL”规划求解”功能,得出结果,看其是否对原最优解、最优值有影响。 分析:2101820的不同结果?,EXCEL求解线性规划模型,方法2:应用敏感性报告寻找允许变化范围 对原电子表格模型运行EXCEL”规划求解”功能,得出“规划求解结果”对话框,选择右端“敏感性报告”选项,得出相应结果。,EXCEL求解线性规划模型,4、多个bi变动 例
13、:如果车间2的可用工时由12小时增加到13小时,车间3的可用工时由18小时减少到17小时,原来的最优解和最优值是否发生变化? 方法1:应用电子表格进行分析 改变电子表格模型中相应的参数,再运行EXCEL”规划求解”功能,得出结果,看其是否对原最优解、最优值有影响。,EXCEL求解线性规划模型,方法2:应用敏感性报告及百分之百法则进行分析 对原电子表格模型,运行EXCEL”规划求解”功能,得出“规划求解结果”对话框,选择右端“敏感性报告”选项,得出相应结果。运用百分之百法则进行判断。 例:车间2:1213,车间3:1817 例:车间2:1216,车间3:1815,EXCEL求解线性规划模型,5、
14、aij变化 例:由于车间2采用新的生产工艺,生产一扇窗由原来的2小时下降到1.5小时,原来的最优解和最优值是否发生变化? 解决方法:改变电子表格模型中相应的参数,再运行EXCEL”规划求解”功能,得出结果,看其是否对原最优解、最优值有影响。,EXCEL求解线性规划模型,6、增加一个新变量 例:由于市场变化,工厂考虑增加一种新产品防盗门的生产,假设每周产量为x3,单位利润为400元,生产一个防盗门占用车间1、2、3各2、1、1工时。其最优解和最优值是多少? 解决方法:在原电子表格模型中增加一列,输入防盗门的相关数据,修改相应的计算公式形成新的电子表格模型,再运行EXCEL”规划求解”功能,得出新
15、的最优解、最优值。,EXCEL求解线性规划模型,7、增加一个约束条件 例:由于电力紧张,在原来生产计划中增加一个约束条件,假设两种产品每件需要消耗电力为20kw、10kw,工厂总供电能力为90kw。其最优解和最优值是多少? 解决方法:在原电子表格模型中增加一行,输入电力消耗的相关数据,修改相应的计算公式形成新的电子表格模型,再运行EXCEL”规划求解”功能,得出新的最优解、最优值。,EXCEL求解线性规划模型,8、影子价格的应用 案例分析 例2.3,练习(模型求解),某工厂生产A、B两种产品,均需经过两道工序,每生产一吨A产品需要经过第一道工序2小时,第二道工序加工3小时,每生产一吨B产品需要
16、经过第一道工序加工3小时,第二道工序加工4小时。可利用的第一道工序工时为15小时,第二道工序为25小时。 生产产品B的同时可产出副产品C,每生产一吨产品B,可同时得到2吨产品C而不需要增加任何额外费用。副产品C一部分可以盈利,但剩下的只能报废,报废需要一定的费用。 各项费用的情况为:出售产品A每吨能够获利400元,出售产品B每吨能够获利800元,每销售一吨副产品C能够获利300元,当剩余的产品C报废时,每吨损失费为200元。 经市场预测,在计划期内产品C的最大销量为5吨 问:如何安排A和B的生产可使工厂总盈利最大?,模型,决策变量为生产A数量x1,生产B数量x2,C盈利部分数量为x3,报废部分数量为x4; 目标函数 约束条件 工序1 工序2 产品B和C的关系 产品C的销量 非负约束,练习(灵敏度),某工厂利用原材料甲、乙、丙生产产品A、B和C,有关资料如右上表所示:问 怎样安排生产,才能使得利润最大? 若增加一公斤原材料甲,利润能增加多少?