线性规划的EXCEL求解课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划问题的,EXCEL,求解,用,EXCEL,求解线性规划问题前，需要在工具菜单上选择加载宏,：,弹出对话框,勾选规划工具，点击“确定”即可,若已加载过则无需再次加载。若安装不完全，也是无法加载的，需要重新安装。,加载宏之后，工具菜单上即出现“规划求解”按钮，可以用来求解许多规划问题，当然包含线性规划问题,例：某工厂生产三种产品，各种产品所需的原材料和设备台时及能供给数量如下表所示，问如何安排生产利润最大？,甲,乙,丙,资源供给,原材料,120,工时,100,单位利润,4,5,3,事实上，本题的所有变量都应是整数,第一步：先将上述问题中的各个决策变量,（即未知数）,、目标函数、,约束条件表达式左边,在工作簿中中反映出来，如下,关于第一步的说明：,从理论上来讲，这些变量、目标函数、约束条件可以在任意单元格中出现，但是这样的结果解读不太方便；,这些表格中的底色部分只是为了讲课方便，并无实际意义，因此底色可以任意选择。,第二步，选择工具菜单中的“规划求解”，弹出对话框：,该处填写目标函数所在的单元格，本例中即为,4,要达到何种目标，本例取最大值,可变单元格，即表示决策变量的单元格，本例为,5,：,d5,选择适当的操作，完成约可条件，本处选择添加,（也可根据需要填更改或删除，左边是添加完成的效果）,填入或选择约束条件所在的单元格，,如本题的约束条件所在的单元格,E2:E3,选择一个要满足的条件，,int,表示只能取整数，,bin,表示只能取或,填入相应的约束值,当一个条件完成后，点击“添加”继续填写约束条件，直至完成，点击“确定”,由于本题的目标函数和约束条件全是一次式，是线性的，可以点击选项，勾选线性条件，使求解更快更精确，获得更多的信息,此处将会给出求解信息，是不是有最优解,可以选择是否生成报告以进一步分析，直接点击选择要生成的报告即可。,结果保存在,EXCEL,表中，如图中所示，求出了最优结果,先看一下运算结果报告,这里可以看到各个约束条件的满足情况，从而得知资源配置的初步情况。,从本例来看，可知原材料全部用完，工时没用完，因此要想得到更大利润应先考虑增加原材料。,再来看看敏感性报告,敏感性报告解读,本部分的术语请参阅任一本线性规划或运筹学教材，本处不做解释，只用红色字体标出,若可变单元格下的递减成本是,a,，即是指相应变量在目标函数中的系数减去,a,后，该变量将变为非负；,可变单元格下的允许的增量和允许的减量给出了不影响当前,最优基,的条件下各决策变量在目标函数中的系数的可变范围；,约束中的阴影价格则给出了各种资源的,影子价格,；,约束中的“允许的增量”和“允许的减量”则给出了在不影响当前,最优基,的条件下各有限资源的数量的变化范围。,再来看看极限值报告,这份报告的意义不如前两份大，在此不再赘述,灵敏度分析的,100%,原则（,1,）,1,、当多个目标函数的系数都在敏感性报告得出的范围之内变动时，计算出各个系数相对于允许范围的变化率，若其和不超过,100%,，则最优解不变。例如前面例子的敏感性报告如下：,若甲、乙、丙在目标函数中的系数分别从,4,、,5,、,3,变为：,7,、,4,、,0,，则总的变化率为：,这时最优解不变，仍为（,0,，,60,，,0,）,若甲、乙、丙在目标函数中的系数分别从,4,、,5,、,3,变为：,5,、,4,、,0,，则总的变化率为：,这时最优解有可能改变，也有可能不变,灵敏度分析的,100%,原则（,2,）,2,、前述的,100%,原则可以一样用来判断右端常量的变化对决策的影响：,当右端常量的总变化率不超过,100%,时，虽然问题的最优解会变化，但是基本变量的选择仍然不变，影子价格也不会变化；,当右端常量的总变化率超过,100%,时，情况不确定，需重新规化。,例如：,原题的解是（,0,，,60,，,0,）。,当原材料的约束限制值变为,80,，工时的约束限制值变为,90,时，由于变化率为,因此，解为（,0,x,0,）,代入得,x=40,新的敏感性表如下：,关于“规划求解选项”各可选项的说明,(1),最长运算时间：最长为,32767,秒，默认为,100,秒，可满足大多数小型求解问题需要；,迭代次数：最多为,32767,次，默认为,100,次，可满足大多数小型求解问题需要；,精度：默认为,0.000001,，以确定约束条件单元格中的数值是否满足要求。,允许误差：输入满足整数约束条件的目标单元格求解结果与最佳结果间的允许百分比误差，此选项只能用于有整数约束的问题。默认值为,5%;,收敛度：仅用于非线性规划问题。当最近五次迭代时，目标单元格中数值的变化都小于“收敛度”中设置的数值时，即停止运行。默认值为,0.001,关于“规划求解选项”各可选项的说明,(2),采用线性模型：仅当模型中的所有关系都是线性时，才会选择此选项，此时会加速求解。若需要对非线性问题进行线性逼近，也可选择该选项；,显示迭代结果：选中此选项，每次迭代后都会中断“规划求解”，并显示当前结果；,假定非负：若勾选此选项，则默认所有变量均为非负；,“正切函数”、“二次方程”、“向前差分”、“中心差分”、“牛顿法”、“共轭法”是求解非线性规划问题的各选项，在此不作介绍；,关于“规划求解选项”各可选项的说明,(,),装入模型：输入对所要调入模型的引用,保存模型：将打开“保存模型”对话框，输入模型的保存位置，只有当需要在工作表上保存多个模型时，单击此命令，第一个模型会自动保存。,一类特殊的线性规划问题：运输问题,例,1,某公司经销甲产品。它下设三个加工厂。每日的产量分别是：,A1,为,7,吨，,A2,为,4,吨，,A3,为,9,吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：,B1,为,3,吨，,B2,为,6,吨，,B3,为,5,吨，,B4,为,6,吨。已知从各工厂到各销售点的单位产品的运价如下表所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,解：先根据题目做出运价表和运量表,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,其中黄色部分为运价，墨绿色部分为相应产地的产量，红色部分为销量，上述表格称之为运价运量表。,则其总的运费为,至此，我们可以得到该问题的数学模型,这类问题，我们称之为,运输问题,。产量正好和销,量相等的运输问题称为,产销平衡问题,，产销平衡问题,有以下特征：,平衡运输问题必有可行解，也必有最优解,.,平衡运输问题的约束方程系数矩阵,A,的所有各阶子式只取,0,，,1,或,-1,三个值,.,如果平衡运输问题中的所有产量,ai,和销量,bj,都是整数，那么，它的任一基可行解都是整数解,.,产销平衡问题一般用表上作业法求解，此处从略。有兴趣的同学请参考任何一本线性规划或运筹学教材。,产销平衡的运输问题当然也是线性规划问题，可以用前面的方法求解，但是由于其特征性，我们建立,EXCEL,电子表时又有其特征,如图示，我们每隔一行作出运价与运量表，相应运价下面的格表示待定的运量，相应产（销）销量下面的格表示相应的约束条件。,各个约束条件比较容易写出，下面我们看一下目标函数怎样写比较简便,在本例中的运价我们用单元格表示就是,B2*B3+C2*C3+D2*D3+E2*E3+B4*B5+C4*C5+D4*D5+E4*E5+,B6*B7+C6*C7+D6*D7+E6*E7,我们将上述式子分成三部分,：,B2*B3+C2*C3+D2*D3+E2*E3,，,B4*B5+C4*C5+D4*D5+E4*E5,，,B6*B7+C6*C7+D6*D7+E6*E7,。,这三部分可以分别用函数,SUMPRODUCT(),来实现,SUMPRODUCT(B2:E2,B3:,3),SUMPRODUCT(B4:E4,B5:,5),SUMPRODUCT(B6:E6,B7:,7),因此，目标函数可以写为,在“工具”,“,规划求解”时，选项中选取非负假设和采用模型即可得最优解,