运用EXCEL求解线性规划模型.ppt
运用EXCEL建模与求解,2011.05,学习背景知识介绍,学习运筹学不仅拥有深厚的数学功底，而且要应用计算机完成模型的建立，并求解最优化方案。使用电子表格软件已经成为管理优化和运筹学教学的一个新的潮流。近年来，美国高校“运筹学”（管理优化）教学思想、内容、方法和手段有了根本的转变，主要表现在美国各大学已普遍采用“电子表格”这一全新的教学方法。国外最新教材数据、模型与决策运用电子表格建模与案例研究（翻译版）详细介绍了各种运筹学模型及其在EXCEL软件中的实现方法。,应用EXCEL求解线性规划模型,线性规划模型的描述,例：某工厂生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。根据市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有的新产品均能销售出去。问：该工厂如何安排这两种新产品的生产计划，才能使总利润最大？,线性规划模型的描述,数据表格：,线性规划模型的建立,假设：每周各生产门和窗x1、x2个。建立线性规划模型如下：Max Z=300 x1+500 x2 x14 2x212 3x1+2x218 x1、x20,EXCEL求解线性规划模型,一、在EXCEL电子表格中建立线性规划模型1、把相关数据输入到EXCEL电子表格中,EXCEL求解线性规划模型,2、主要求解结果 两种新产品每周的产量；两种新产品每周各实际使用的工时（不能超过计划工时）；两种新产品的总利润,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）复制E7单元格到E8、E9,EXCEL求解线性规划模型,（3）总利润计算：在G12单元格输入公式：=C4*C12+D4*D12 或：=SUMPRODUCT（C4：D4，C12：D12）,EXCEL求解线性规划模型,收集问题数据；在电子表格中输入数据（数据单元格）；确定决策变量单元格（可变单元格）；输入约束条件左边的公式（输出单元格）使用SUMPRODUCT函数简化输入；输入目标函数公式（目标单元格）。使用SUMPRODUCT函数简化输入。,在电子表格中建立线性规划模型步骤总结,EXCEL求解线性规划模型,二、在EXCEL电子表格中求解线性规划模型1、求解参数设置：“工具”规划求解“，弹出“规划求解参数”对话框，设置求解相关参数。,EXCEL求解线性规划模型,2、约束的设置：单击“添加”，弹出“添加约束”，添加约束条件。,EXCEL求解线性规划模型,3、求解选项设置：单击“选项”，弹出“规划求解选项”对话框。选择“采用线性模型”和“假定非负”。,EXCEL求解线性规划模型,4、求解及结果 单击“求解”，开始规划求解。弹出“规划求解结果”对话框。选择“保存规划求解结果”。,EXCEL求解线性规划模型,5、电子表格显示结果：单击“确定”，在电子表格的可变单元格、输出单元格及目标单元格出现求解结果。,EXCEL求解线性规划模型,课堂练习1：P25 1利用SUMPRODUCT函数求解例。,EXCEL求解线性规划模型,某家具制造厂生产五种不同规格的家具.每件家具都要经过机械成型、打磨、上漆等几个主要生产工序.每件家具的每道工序所使用的时间及每道工序的可用时间、每种家具的利润等数据如下表。问工厂应如何安排生产，才能使总利润最大？,EXCEL求解线性规划模型,EXCEL求解线性规划模型,三、使用单元格命名方法求解线性规划模型 求解时首先给与公式和模型有关的四类单元格进行命名。数据单元格：单位利润（C4：D4）、可用工时（G7：G9）可变单元格：每周产量（C12：D12）输出单元格：实际使用（E7：E9）目标单元格：总利润（G12）,EXCEL求解线性规划模型,命名规则：（1）命名：选择命名区域（名称区域+数据区域）。例：把（C4：D4）区域命名为“单位利润”，则选择（B4：D4）。路径：“插入”“名称”“指定”，进入“指定名称”界面。选择名称所要放置的单元格。单击“确定”，完成一个名称设置。重复上述步骤，命名其它单元格。,EXCEL求解线性规划模型,（2）查看、更改、删除 路径：“插入”“名称”“定义”，进入“定义名称”界面。单击某个名称，可查看其引用位置。更改：先添加新名称，再删除原名称。也可修改原名称的引用位置。删除：选择欲删除单元格名称，单击“删除”。,EXCEL求解线性规划模型,查看、更改、删除操作界面,EXCEL求解线性规划模型,（3）将应用改为名称 路径：单击某一单元格，“插入”“名称”“应用”。在“应用名称”对话框中，选中准备使用的一个或多个名称。,EXCEL求解线性规划模型,（4）将单元格名称粘贴到电子表格中选择空白单元格，输入“区域名称”和“单元格”。单击“区域名称”下的单元格。路径：“插入”“名称”“粘贴”。出现“粘贴名称”对话框。单击“粘贴列表”，在电子表格中的相应位置得出结果。,EXCEL求解线性规划模型,EXCEL求解线性规划模型,（5）对结果进行修饰 利用“替换”功能中的“全部替换”去掉“=Sheet1!”和“$”，得出区域名称和引用结果。,EXCEL求解线性规划模型,规划求解过程,EXCEL求解线性规划模型,使用名称比使用字母更容易理解公式的含义在“规划求解参数”对话框中使用名称更容易理解线性规划模型的含义。增强了公式和模型的可读性,使用单元格命名法有何好处？,课堂练习3：P25 1,输入数据标识数据每个数据对应唯一单元格在电子表格中显示完整模型数据、公式分离保持简单化使用区域名称使用相对和绝对地址简化公式并复制使用边框、底色区分单元格类型,建模求解要点回顾,某公司有100万元的资金可供投资,该公司有六个可选的投资项目,其各种数据见下表.该公司的目标:投资风险最小,每年红利至少6.5万元,最低平均增长率为12%,最低平均信用度为7.,案例分析及求解：P3 例2,EXCEL求解线性规划模型,EXCEL求解线性规划模型,假设：xi为每种投资项目的投资额。建立线性规划模型如下：MinZ=0.18x1+0.06x2+0.10 x3+0.04x4+0.12x5+0.08x6 x1+x2+x3+x4+x5+x6=100 0.04x1+0.05x2+0.09x3+0.07x4+0.06x5+0.08x6 6.5 0.22x1+0.07x2+0.12x3+0.08x4+0.15x5+0.08x6 12 4x1+10 x2+2x3+10 x4+4x5+6x6 700 x1、x2、x3、x4、x5、x6 0,EXCEL求解线性规划模型,EXCEL求解线性规划模型,课堂练习:某公司受人委托,准备用120万元投资A和B两中基金,其中:A基金的单位投资额为50万元,年回报率为10%,B基金的单位投资额为100万元,年回报率为4%.委托人要求在每年的年回报金额至少达到6万元的基础上要求投资风险最小.据测定每单位A基金的投资风险指数为8,每单位B基金的投资风险指数为3,风险指数越大表明投资风险越大.委托人要求在基金B中的投资额不少于30万元.为了使总的投资风险指数最小,该公司应该在基金A和B中各投资多少单位?这时每年的回报金额是多少?,EXCEL求解线性规划模型,四、线性规划问题解的讨论 1、线性规划问题解的种类？2、唯一解的表现是？3、无穷解的表现是？4、无可行域无解的表现是？5、可行域无界的表现是？上述结果用EXCEL建模求解的最后对话框提示不同。,EXCEL求解线性规划模型,图解法解得分析：,解的结果,有可行域,无可行域,可行域有界,可行域无界,唯一解,无穷解,唯一解,无穷解,无解,一定无解,EXCEL求解线性规划模型,五、线性规划问题的灵敏度分析 线性规划问题的灵敏度分析是在求出最优解的基础上，进一步讨论当cj、bi、aij发生变化时，对最优解的影响。判断某一参数发生变化，原最优解是否发生变化？怎样得出使原最优解不变的参数变化范围 当最优解发生变化时，怎样求出新的最优解。,EXCEL求解线性规划模型,1、单个cj变动例：如果门的单位利润由原来的300元提升到500元，最优解是否会改变？对总利润会产生怎样的影响？方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解有影响。,EXCEL求解线性规划模型,求得结果如下。最优解不变，总利润上升400元。,EXCEL求解线性规划模型,方法2：应用敏感性报告寻找允许变化范围 对原电子表格模型运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。,EXCEL求解线性规划模型,比较两种方法的用途？,EXCEL求解线性规划模型,2、多个cj变动例：如果把门的单位利润由300元提高到450元，同时把窗的单位利润由500元减少到400元，原来的最优解和最优值是否会发生变化？方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。,EXCEL求解线性规划模型,求得结果如下。最优解不变，总利润下降300元。,EXCEL求解线性规划模型,方法2：应用敏感性报告及百分之百法则进行分析 对原电子表格模型，运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。运用百分之百法则进行判断。百分之一百法则：对于所有变化的目标函数决策变量系数（或约束条件右边常数），当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，最优解不变。,EXCEL求解线性规划模型,允许增加量百分比=实际增加量（上限-现在值）/允许增加量允许减少量百分比=实际减少量（现在值-下限）/允许减少量例：门300450；窗500400例：门300600；窗500300如果超过100%，用电子表格模型重新求解思考：当结果刚好为100%时，最优解变吗？,EXCEL求解线性规划模型,应用规则：当允许增加量（减少量）为无穷大时，则对于任一个增加量（减少量），其允许增加（或减少）的百分比都看成零。百分之一百法则是判断最优解变与不变的充分条件，但不是必要条件。不能应用于目标函数决策变量系数和约束条件右端常数同时变化的情况。,EXCEL求解线性规划模型,3、单个bi变动例：如果车间2的可用工时由12小时增加到13小时，原来的最优解和最优值是否发生变化？(最优解肯定变，范围就是可行性是否变)方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。分析：2101820的不同结果？,EXCEL求解线性规划模型,方法2：应用敏感性报告寻找允许变化范围 对原电子表格模型运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。,EXCEL求解线性规划模型,4、多个bi变动例：如果车间2的可用工时由12小时增加到13小时，车间3的可用工时由18小时减少到17小时，原来的最优解和最优值是否发生变化？方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。,EXCEL求解线性规划模型,方法2：应用敏感性报告及百分之百法则进行分析 对原电子表格模型，运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。运用百分之百法则进行判断。例：车间2：1213，车间3：1817例：车间2：1216，车间3：1815（4/6+3/6=7/6）,EXCEL求解线性规划模型,5、aij变化例：由于车间2采用新的生产工艺，生产一扇窗由原来的2小时下降到1.5小时，原来的最优解和最优值是否发生变化？解决方法：改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。,EXCEL求解线性规划模型,6、增加一个新变量例：由于市场变化，工厂考虑增加一种新产品防盗门的生产，假设每周产量为x3，单位利润为400元，生产一个防盗门占用车间1、2、3各2、1、1工时。其最优解和最优值是多少？解决方法：在原电子表格模型中增加一列，输入防盗门的相关数据，修改相应的计算公式形成新的电子表格模型，再运行EXCEL”规划求解”功能，得出新的最优解、最优值。,EXCEL求解线性规划模型,7、增加一个约束条件例：由于电力紧张，在原来生产计划中增加一个约束条件，假设两种产品每件需要消耗电力为20kw、10kw，工厂总供电能力为90kw。其最优解和最优值是多少？解决方法：在原电子表格模型中增加一行，输入电力消耗的相关数据，修改相应的计算公式形成新的电子表格模型，再运行EXCEL”规划求解”功能，得出新的最优解、最优值。,EXCEL求解线性规划模型,8、影子价格的应用 案例分析P48 例2.3,
