线性规划的EXCEL求解课件.ppt

1、线性规划问题的EXCEL求解 用EXCEL求解线性规划问题前，需要在工具菜单上选择加载宏：弹出对话框勾选规划工具，点击“确定”即可 若已加载过则无需再次加载。若安装不完全，也是无法加载的，需要重新安装。加载宏之后，工具菜单上即出现“规划求解”按钮，可以用来求解许多规划问题，当然包含线性规划问题123123123123max453.32412023100,0Sxxxstxxxxxxx x x例：某工厂生产三种产品，各种产品所需的原材料和设备台时及能供给数量如下表所示，问如何安排生产利润最大？甲乙丙资源供给原材料120工时100单位利润453123,x x x解:设生产甲,乙,丙分别为件 则可得数

2、学模型为事实上，本题的所有变量都应是整数123,x x x 取整第一步：先将上述问题中的各个决策变量（即未知数）、目标函数、约束条件表达式左边在工作簿中中反映出来，如下 关于第一步的说明：从理论上来讲，这些变量、目标函数、约束条件可以在任意单元格中出现，但是这样的结果解读不太方便；这些表格中的底色部分只是为了讲课方便，并无实际意义，因此底色可以任意选择。第二步，选择工具菜单中的“规划求解”，弹出对话框：该处填写目标函数所在的单元格，本例中即为4要达到何种目标，本例取最大值可变单元格，即表示决策变量的单元格，本例为5：d5选择适当的操作，完成约可条件，本处选择添加（也可根据需要填更改或删除，左边

3、是添加完成的效果）填入或选择约束条件所在的单元格，如本题的约束条件所在的单元格E2:E3选择一个要满足的条件，int表示只能取整数，bin表示只能取或填入相应的约束值当一个条件完成后，点击“添加”继续填写约束条件，直至完成，点击“确定”由于本题的目标函数和约束条件全是一次式，是线性的，可以点击选项，勾选线性条件，使求解更快更精确，获得更多的信息此处将会给出求解信息，是不是有最优解可以选择是否生成报告以进一步分析，直接点击选择要生成的报告即可。结果保存在EXCEL表中，如图中所示，求出了最优结果先看一下运算结果报告这里可以看到各个约束条件的满足情况，从而得知资源配置的初步情况。从本例来看，可知原

4、材料全部用完，工时没用完，因此要想得到更大利润应先考虑增加原材料。再来看看敏感性报告敏感性报告解读 本部分的术语请参阅任一本线性规划或运筹学教材，本处不做解释，只用红色字体标出 若可变单元格下的递减成本是a，即是指相应变量在目标函数中的系数减去a后，该变量将变为非负；可变单元格下的允许的增量和允许的减量给出了不影响当前最优基的条件下各决策变量在目标函数中的系数的可变范围；约束中的阴影价格则给出了各种资源的影子价格；约束中的“允许的增量”和“允许的减量”则给出了在不影响当前最优基的条件下各有限资源的数量的变化范围。再来看看极限值报告这份报告的意义不如前两份大，在此不再赘述灵敏度分析的100%原则

5、（1）1、当多个目标函数的系数都在敏感性报告得出的范围之内变动时，计算出各个系数相对于允许范围的变化率，若其和不超过100%，则最优解不变。例如前面例子的敏感性报告如下：若甲、乙、丙在目标函数中的系数分别从4、5、3变为：7、4、0，则总的变化率为：3139100%3.52.3333331307e这时最优解不变，仍为（0，60，0）若甲、乙、丙在目标函数中的系数分别从4、5、3变为：5、4、0，则总的变化率为：113100%3.52.333333130e这时最优解有可能改变，也有可能不变灵敏度分析的100%原则（2）2、前述的100%原则可以一样用来判断右端常量的变化对决策的影响：当右端常量的

6、总变化率不超过100%时，虽然问题的最优解会变化，但是基本变量的选择仍然不变，影子价格也不会变化；当右端常量的总变化率超过100%时，情况不确定，需重新规化。例如：原题的解是（0，60，0）。当原材料的约束限制值变为80，工时的约束限制值变为90时，由于变化率为4030100%120130E因此，解为（0,x,0）,代入得x=40,新的敏感性表如下：关于“规划求解选项”各可选项的说明(1)最长运算时间：最长为32767秒，默认为100秒，可满足大多数小型求解问题需要；迭代次数：最多为32767次，默认为100次，可满足大多数小型求解问题需要；精度：默认为0.000001，以确定约束条件单元格中

7、的数值是否满足要求。允许误差：输入满足整数约束条件的目标单元格求解结果与最佳结果间的允许百分比误差，此选项只能用于有整数约束的问题。默认值为5%;收敛度：仅用于非线性规划问题。当最近五次迭代时，目标单元格中数值的变化都小于“收敛度”中设置的数值时，即停止运行。默认值为0.001关于“规划求解选项”各可选项的说明(2)采用线性模型：仅当模型中的所有关系都是线性时，才会选择此选项，此时会加速求解。若需要对非线性问题进行线性逼近，也可选择该选项；显示迭代结果：选中此选项，每次迭代后都会中断“规划求解”，并显示当前结果；假定非负：若勾选此选项，则默认所有变量均为非负；“正切函数”、“二次方程”、“向前

8、差分”、“中心差分”、“牛顿法”、“共轭法”是求解非线性规划问题的各选项，在此不作介绍；关于“规划求解选项”各可选项的说明()装入模型：输入对所要调入模型的引用 保存模型：将打开“保存模型”对话框，输入模型的保存位置，只有当需要在工作表上保存多个模型时，单击此命令，第一个模型会自动保存。一类特殊的线性规划问题：运输问题 例例1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。问该公司应如何调运产品，在

9、满足各销点的需要量的前提下，使总运费为最少。解：先根据题目做出运价表和运量表B1B2B3B4产量A13113107A219284A3741059销量3656其中黄色部分为运价，墨绿色部分为相应产地的产量，红色部分为销量，上述表格称之为运价运量表。ijijAB用c 表示从 到单位货物的运费ijjaAbB表示 地的产量,表示地的销量则其总的运费为3411ijijijCc xijijxAB设 表示从 到单位货物的运费jB因为每个销地的需求都要满足，因此对每个销地可得到一个方程123(1,2,3,4)jjjjxxxbjiA同理,因为每个产地的货物都要卖出，因此对每个产地 可得到一个方程123(1,2,

10、3)iiiixxxai至此，我们可以得到该问题的数学模型3411123123min,.(1,2,3,4)(1,2,3)ij ijijjjjjiiiiCc xs txxxbjxxxai这类问题，我们称之为运输问题。产量正好和销量相等的运输问题称为产销平衡问题，产销平衡问题有以下特征：1.平衡运输问题必有可行解，也必有最优解平衡运输问题必有可行解，也必有最优解.2.平衡运输问题的约束方程系数矩阵平衡运输问题的约束方程系数矩阵 A 的所有各阶子的所有各阶子式只取式只取 0，1 或或-1 三个值三个值.3.如果平衡运输问题中的所有产量如果平衡运输问题中的所有产量 ai 和销量和销量 bj4.都是整数，

11、那么，它的任一基可行解都是整数解都是整数，那么，它的任一基可行解都是整数解.产销平衡问题一般用表上作业法求解，此处从略。有兴趣的同学请参考任何一本线性规划或运筹学教材。产销平衡的运输问题当然也是线性规划问题，可以用前面的方法求解，但是由于其特征性，我们建立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)因此，目标函数可以写为在“工具”“规划求解”时，选项中选取非负假设和采用模型即可得最优解