EXCEL求解线性规划问题.ppt

第五章第五章 利用利用EXCEL求解线性规划问题求解线性规划问题 建立线性规划问题的模型建立线性规划问题的模型利用利用EXCEL求解线性规划问题求解线性规划问题分析运算结果（敏感性分析）分析运算结果（敏感性分析）目的目的：一、一、EXCEL 基本知识基本知识 1、命名工作表、命名工作表 功能：功能：存储信息、进行计算、排序数据、用图或表的形存储信息、进行计算、排序数据、用图或表的形式显示数据、规划求解、财会分析、概率与统计分析等式显示数据、规划求解、财会分析、概率与统计分析等等等（1）激活工作表）激活工作表1，单击，单击sheet 1 标签标签（2）命名工作表）命名工作表 或或 （3）Format/sheet Rename 显示显示Rename sheet 对话框对话框（4）键入工作表名）键入工作表名 2、工作表、工作表 4、进行计算、进行计算 Excel-2003 256列列 65535 行行Excel-2007 16384列列 1048576行行 3、向单元格中输入数据、向单元格中输入数据常数：不能改变的文字或其它数据常数：不能改变的文字或其它数据公式：输入到单元格中的数字值，或返回数字值的表达式。公式：输入到单元格中的数字值，或返回数字值的表达式。（1）输出数据时计算）输出数据时计算A1 =456+789（2）根据其它单元格的数据进行计算）根据其它单元格的数据进行计算A3456 B3-789 C3=A3+B3 5、在公式中引用其它单元格、在公式中引用其它单元格 在公式中可以引用本工作簿中任何单元格或单元格在公式中可以引用本工作簿中任何单元格或单元格组的数组的数 据，也可以引用其它工作簿中任何单元格或据，也可以引用其它工作簿中任何单元格或单元格组的数据。引用单元格数据后，公式的运算单元格组的数据。引用单元格数据后，公式的运算值将随着被引用的单元格数据变化而变化。值将随着被引用的单元格数据变化而变化。（1）引用的类型）引用的类型三种类型三种类型：相对引用、相对引用、绝对引用、混合引用绝对引用、混合引用格式：格式：A3、B6（2）相对引用相对引用 使用相对引用后，系统将会记住建立公式的单元格和被使用相对引用后，系统将会记住建立公式的单元格和被引用的单元格的相对位置，在复制这个公式时，新的公式单引用的单元格的相对位置，在复制这个公式时，新的公式单元和被引用的单元仍然保持这种相对位置。元和被引用的单元仍然保持这种相对位置。（3）绝对引用）绝对引用 绝对引用是指被引用的单元与引用的公式单元的位置绝对引用是指被引用的单元与引用的公式单元的位置关系是绝对的，无论将这个公式复制到任何单元，公式所关系是绝对的，无论将这个公式复制到任何单元，公式所引用的还是原来单元格的数据。引用的还是原来单元格的数据。（4）混合引用）混合引用 格式：格式：$a$3$d$5格式：格式：$A3 列是绝对的，行是相对的列是绝对的，行是相对的 B$3 列是相对的，行是绝对的列是相对的，行是绝对的使用使用Excel进行求解进行求解1.关于关于“规划求解规划求解”2.如何加载如何加载“规划求解规划求解”3.“规划求解规划求解”各参数设置各参数设置4.“规划求解规划求解”步骤步骤5.利用利用“规划求解规划求解”解线性规划问题解线性规划问题2.如何加载如何加载“规划求解规划求解”1)在“工具”菜单上,单击“加载宏”2)在弹出的对话框中的“可用加载宏”列表框中,选定待添加的加载宏“规划求解”选项旁的复选框,然后单击“确定”.单击“确定”后,“工具”菜单下就会出现一项“规划求解”3.“规划求解规划求解”各参数设置各参数设置单击“规划求解”按钮,将会出现以下规划求解参数设置对话框单击“添加”,显示添加约束对话框选项:显示”规划求解选项”对话框.在其中可以加载或保存规划求解模型,并对规划求解过程的高级属性进行控制线性规划求解步骤：线性规划求解步骤：1.确定目标函数系数存放单元格，并在这些单元格中输入目标确定目标函数系数存放单元格，并在这些单元格中输入目标函数系数。函数系数。2.确定决策变量存放单元格，并任意输入一组数据；确定决策变量存放单元格，并任意输入一组数据；3.确定约束条件中左端项系数存放单元格，并输入约束条件左确定约束条件中左端项系数存放单元格，并输入约束条件左端项系数；端项系数；4.在约束条件左端项系数存放单元格右边的单元格中输入约束在约束条件左端项系数存放单元格右边的单元格中输入约束条件左端项的计算公式，计算出约束条件左端项对应于目前决条件左端项的计算公式，计算出约束条件左端项对应于目前决策变量的函数值。策变量的函数值。5.在步骤在步骤4的的数据右边输入约束条件中右端项（即常数项）的的数据右边输入约束条件中右端项（即常数项）6.确定目标函数值存放单元格，并在该单元格中输入目标函数确定目标函数值存放单元格，并在该单元格中输入目标函数值电容计算公式。值电容计算公式。一个简单的例子一个简单的例子某工厂计划生产两种产品，利润分别为某工厂计划生产两种产品，利润分别为2和和3，已知生，已知生产单位产品所需的设备台时和产单位产品所需的设备台时和A、B两种原材料的消耗，两种原材料的消耗，如表如表产品产品1产品产品2设备设备128台时台时原材料原材料A4016KG原材料原材料B0412KG目标是不超过资源限制的情况下，确定两产品产量，目标是不超过资源限制的情况下，确定两产品产量，得到最大利润。得到最大利润。建立数学公式（步骤一）建立数学公式（步骤一）在工作表的在工作表的顶部部输入数据入数据确定每个决策确定每个决策变量所量所对应的的单元格位置元格位置选择单元格元格输入公式，找入公式，找到目到目标函数的函数的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件左束条件左边的的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件右束条件右边的的值可采用可采用 复制粘贴复制粘贴 或或 直直接输入接输入 的方式导入数据。的方式导入数据。建立数学公式（步骤二）建立数学公式（步骤二）在工作表的在工作表的顶部部输入数据入数据确定每个决策确定每个决策变量所量所对应的的单元格位置元格位置选择单元格元格输入公式，找入公式，找到目到目标函数的函数的值选择一个一个单元格元格输入公式，入公式，计算每个算每个约束条件左束条件左边的的值选择一个一个单元格元格输入公式，入公式，计算每个算每个约束条件右束条件右边的的值图中，规定图中，规定B12、C12为可变单元格为可变单元格可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数建立数学公式（步骤三）建立数学公式（步骤三）在工作表的在工作表的顶部部输入数据入数据确定每个决策确定每个决策变量所量所对应的的单元格位置元格位置选择单元格元格输入公式，找入公式，找到目到目标函数的函数的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件左束条件左边的的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件右束条件右边的的值在目标单元格中，需要填入计算目标函数值的公式。在目标单元格中，需要填入计算目标函数值的公式。建立数学公式（步骤四）建立数学公式（步骤四）在工作表的在工作表的顶部部输入数据入数据确定每个决策确定每个决策变量所量所对应的的单元格位置元格位置选择单元格元格输入公式，找入公式，找到目到目标函数的函数的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件左束条件左边的的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件右束条件右边的的值在约束单元格中，需要填入计算约束函数值的公式。在约束单元格中，需要填入计算约束函数值的公式。建立数学公式（步骤五）在工作表的在工作表的顶部部输入数据入数据确定每个决策确定每个决策变量所量所对应的的单元格位置元格位置选择单元格元格输入公式，找入公式，找到目到目标函数的函数的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件左束条件左边的的值确定确定约束束单元格元格输入公式，入公式，计算每个算每个约束条件右束条件右边的的值调用调用 规划求解规划求解 模块模块选择选择工具工具下拉菜单下拉菜单选择选择规划求解规划求解选项（事先选项（事先需用需用Office安装盘安装安装盘安装规划求解的功能）规划求解的功能）填写目标单元格和可变单元格填写目标单元格和可变单元格出现出现规划求解参数规划求解参数对话框对话框在在目标单元格目标单元格中输入中输入B14B14在在等于等于选择最大选择最大在在可变单元格可变单元格中输入中输入B12:C12B12:C12选择选择添加添加在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。添加约束添加约束在在添加约束添加约束对话框中，在对话框中，在单元格引用位置单元格引用位置中输入中输入B17，选择，选择=，在约束，在约束值中输入值中输入D17。选择。选择添加添加第三个条件添加完毕后，第三个条件添加完毕后，选择选择确定确定当当规划求解参数规划求解参数对话框重对话框重新出现时，选择新出现时，选择选项选项“选项选项”设置设置当选项对话框出现时，选当选项对话框出现时，选择择假设非负假设非负。选择。选择确定确定用Excel求解出现出现规划求解参数规划求解参数对话框，对话框，选择选择求解求解。保存求解结果保存求解结果当当求解结果求解结果对话框出现时，选对话框出现时，选择择保存规划求解结果保存规划求解结果。选择。选择确确定定。运算结果报告运算结果报告列出列出目标单元格目标单元格和和可变单可变单元格元格以及它们的初始值、以及它们的初始值、最终结果、约束条件和有最终结果、约束条件和有关约束条件的信息。关约束条件的信息。初值初值和和终值终值分别指单元格分别指单元格在在本次求解前的数值和求本次求解前的数值和求解后的数值解后的数值。敏感性分析报告（敏感性分析报告（1）可变单元格中可变单元格中“单元格单元格”指决策变量所在单元格的地址指决策变量所在单元格的地址“名字名字”是决策变量的名称是决策变量的名称“终值终值”是决策变量的终值是决策变量的终值,即最优值即最优值“递减成本递减成本”指指最优解中等于0的变量，对应的目标函数中的系数增加或减少多少，最优解不再为0“目标式系数目标式系数”目标函数中的系数，为已知条件目标函数中的系数，为已知条件“允许的增量允许的增量”与与“允许的减量允许的减量”表示目标函数中的系数在增量表示目标函数中的系数在增量与减量的变化范围内变化时，最优解保持不变（注：最优值发生与减量的变化范围内变化时，最优解保持不变（注：最优值发生变化）变化）敏感性分析报告（敏感性分析报告（2）约束单元格约束单元格“单元格单元格”指约束条件左边所在单元格的地址指约束条件左边所在单元格的地址“名字名字”是约束条件左边的名称是约束条件左边的名称“终值终值”是约束条件左边的值是约束条件左边的值“阴影价格阴影价格”指约束条件右边增加或减少一个单位，目标函指约束条件右边增加或减少一个单位，目标函数值增加或减少的数量数值增加或减少的数量“约束的限制值约束的限制值”指约束条件右边的值，为已知条件指约束条件右边的值，为已知条件“允许的增量允许的增量，减量减量”表示约束条件右边在允许的范围内变表示约束条件右边在允许的范围内变化时，影子价格不变，即约束条件右边的值每增加化时，影子价格不变，即约束条件右边的值每增加1个单位，个单位，目标函数值的增加仍然为影子价格的大小。目标函数值的增加仍然为影子价格的大小。因此，右端项在因此，右端项在一定范围内变化时，影子价格不变，目标函数值的变动等于一定范围内变化时，影子价格不变，目标函数值的变动等于右端项变动值乘以影子价格右端项变动值乘以影子价格极限值报告解释极限值报告解释列出列出目标单元格目标单元格和和可变单元格可变单元格以及它们的数值、上下限和目标以及它们的数值、上下限和目标值。含有整数约束条件的模型不能生成本报告。其中，下限是值。含有整数约束条件的模型不能生成本报告。其中，下限是在满足约束条件和保持其它可变单元格数值不变的情况下，某在满足约束条件和保持其它可变单元格数值不变的情况下，某个可变单元格可以取到的最小值。上限是在这种情况下可以取个可变单元格可以取到的最小值。上限是在这种情况下可以取到的最大值。到的最大值。延伸延伸下面对目标系数同时变动以及约束右端值同时变动的情况分别作延伸。下面对目标系数同时变动以及约束右端值同时变动的情况分别作延伸。（1）目标系数目标系数c同时变动的百分之百法则同时变动的百分之百法则：如如果果目目标标函函数数系系数数同同时时变变动动，计计算算出出每每一一系系数数变变动动量量占占该该系系数数同同方方向向可可容容许许变变动动范范围围的的百百分分比比，而而后后将将各各个个系系数数的的变变动动百百分分比比相相加加，如如果果所所得得的的和和不不超超过过百百分分之之一一百百，最最优优解解不不会会改改变变；如如果果超超过过百百分分之之一一百百，则不能确定最优解是否改变。则不能确定最优解是否改变。如果如果x1对应的目标系数对应的目标系数c1由由2变为变为1.8，x2对应的目标系数对应的目标系数c2由由3变为变为3.5，运用百分之百法则，根据敏感性分析报告运用百分之百法则，根据敏感性分析报告c1由由2变为变为1占允许减量的百分比为占允许减量的百分比为(2-1.8)/0.5=40%C2由由3变为变为3.5占允许增加量的百分比为占允许增加量的百分比为(3.5-3)/1=50%.改变的百分比和改变的百分比和为为90%，没有超过，没有超过100%，因此最优解不变。，因此最优解不变。（2）约束右端值）约束右端值b同时变动的百分之百法则：同时变动的百分之百法则：同同时时改改变变几几个个或或所所有有函函数数约约束束的的约约束束右右端端值值，如如果果这这些些变变动动的的幅幅度度不不大大，那那么么可可以以用用影影子子价价格格预预测测变变动动产产生生的的影影响响。为为了了判判别别这这些些变变动动的的幅幅度度是是否否允允许许，计计算算每每一一变变动动占占同同方方向向可可容容许许变变动动范范围围的的百百分分比比，如如果果所所有有的的百百分分比比之之和和不不超超过过百百分分之之一一百百，那那么么影影子子价价格格还还是是有有效效的的；如如果果所所有有的的百百分分比比之之和和超超过过百百分分之之一一百百，那那就就无无法法确确定定影影子价格是否有效。子价格是否有效。如果右端值如果右端值b分别由分别由8,16,12变为变为8.5,15，和，和11，运用百分之百法则，运用百分之百法则:b1由由8变为变为8.5占允许增量的百分比为占允许增量的百分比为(8.5-8)/2=25%b2由由16变为变为15占允许减量的百分比为占允许减量的百分比为(16-15)/8=12.5%b3由由12变为变为11占允许减量的百分比为占允许减量的百分比为(12-11)/4=25%.改变的百分比和为改变的百分比和为62.5%，没有超过，没有超过100%，因此影子价格仍然有效。，因此影子价格仍然有效。单元格变量名最终值减少成本目标系数允许增加值允许减少值$B$9x102.862.81E+30$C$9x212.4097.83.4$D$9x39.50122.61.5已知一个线性规划问题的灵敏度分析报告如下已知一个线性规划问题的灵敏度分析报告如下变动单元格变动单元格单元格名 称最终值影子价格右端值允许增加值允许减少值$E$4第一资源约束580701E+3012$E$5第二资源约束372.8371531$E$6第三资源约束601.2601250约束条件约束条件2012年年12月管理创新实验班期末考试题月管理创新实验班期末考试题（1）写出该问题的最优解）写出该问题的最优解（2）分析当）分析当x1的目标系数减少的目标系数减少5，同时，同时x2的目标系数增加的目标系数增加4时，最优解是否改变。时，最优解是否改变。（3）分析当第一资源约束右端值增加）分析当第一资源约束右端值增加30，同时第二资源约束右端值增加，同时第二资源约束右端值增加4和第三资源和第三资源约束右端值减少约束右端值减少15时，目标函数值的改变量。时，目标函数值的改变量。解解：（：（1）最优解为最优解为x1=0,x2=12.4,x3=9.5（2）x1的目标系数减少的目标系数减少5，占允许减少的百分比，占允许减少的百分比=5/=0%，x2的目标系数增加的目标系数增加4,占允许增加的百分比占允许增加的百分比=4/7.8=51.2%。改变的百分比和为改变的百分比和为51.2%，没有超过，没有超过100%，因此最优解不变。，因此最优解不变。（3）第一资源约束右端值增加第一资源约束右端值增加30，占允许增加的，占允许增加的30/=0%，第二资源约束右端值增加第二资源约束右端值增加4，占允许增加的，占允许增加的4/15=26.7%，第三资源约束右端值减少第三资源约束右端值减少15，占允许减少的，占允许减少的15/50=30%。改变的百分比和为改变的百分比和为56.7%，没有超过，没有超过100%，因此影子价格仍然，因此影子价格仍然有效。因此目标函数值改变量为有效。因此目标函数值改变量为 30 30 0+4 0+4 2.8 2.8 15 15 1.2=11.2 1.2=11.2 18=18=6.86.8练习：话务员排班问题练习：话务员排班问题某寻呼公司雇用了多名话务员工作，他们每天工某寻呼公司雇用了多名话务员工作，他们每天工作作3节，每节节，每节3小时，每节开始时间为午夜、凌晨小时，每节开始时间为午夜、凌晨3点钟、凌晨点钟、凌晨6点钟，上午点钟，上午9点、中午点、中午12点、下午点、下午3点、点、6点、点、9点，为方便话务员上下班，管理层点，为方便话务员上下班，管理层安排每位话务员每天连续工作安排每位话务员每天连续工作3节，根据调查，节，根据调查，对于不同的时间，由于业务量不同，需要的话务对于不同的时间，由于业务量不同，需要的话务员的人数也不相同，公司付的薪水也不相同，有员的人数也不相同，公司付的薪水也不相同，有关数据见表。关数据见表。问：如何安排话务员才能保证服务人数，又使总成本最低？解：这个问题实际上是一个成本效益平衡问题。解：这个问题实际上是一个成本效益平衡问题。管理层在向客户提供满意服务水平的同时要控制管理层在向客户提供满意服务水平的同时要控制成本，因此必须寻找成本与效益的平衡。由于每成本，因此必须寻找成本与效益的平衡。由于每节工作时间为节工作时间为3小时，一天被分为小时，一天被分为8班，每人连续班，每人连续工作工作3节，各班时间安排如下表：节，各班时间安排如下表：为了建立数学模型，对应于一般成本效益平衡问为了建立数学模型，对应于一般成本效益平衡问题，我们首先必须明确包含的活动数目，活动一题，我们首先必须明确包含的活动数目，活动一个单位是对应于分派一个话务员到该班次收，效个单位是对应于分派一个话务员到该班次收，效益的水平对应于时段。收益水平就是该时段里上益的水平对应于时段。收益水平就是该时段里上下班的话务员数目，各活动的单位效益贡献就是下班的话务员数目，各活动的单位效益贡献就是在该时间内增加的在岗位话务员数目。我们给出在该时间内增加的在岗位话务员数目。我们给出下列成本效益平衡问题参数表：下列成本效益平衡问题参数表：决策变量决策变量Xi表示分派到第班的话务员人数（表示分派到第班的话务员人数（i=1，2，3，4，5，6，7，8），约束条件为：），约束条件为：0-3时间段：时间段：3-6时间段：时间段：6-9时间段：时间段：9-12时间段：时间段：12-15时间段：时间段：15-18时间段：时间段：18-21时间段：时间段：21-0时间段：时间段：非负约束：非负约束：目标函数为最小化成本：目标函数为最小化成本：