01-第一章-用Excel求解规划问题-优化软件与应用-教学课件.ppt

《01-第一章-用Excel求解规划问题-优化软件与应用-教学课件.ppt》由会员分享，可在线阅读，更多相关《01-第一章-用Excel求解规划问题-优化软件与应用-教学课件.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主讲人:雒兴刚Email：Tel:83682292优化软件与应用优化软件与应用第一章 用Excel求解规划问题 Excel Excel具有内置的规划求解功能。具有内置的规划求解功能。Microsoft Excel Microsoft Excel 的的“规划求解规划求解”工具取自德克萨斯大学奥斯汀分校的工具取自德克萨斯大学奥斯汀分校的 Leon Lasdon Leon Lasdon 和克里夫兰州和克里夫兰州立大学的立大学的 Allan Waren Allan Waren 共同开发的共同开发的Generalized Reduced Generalized Reduced Gradient(Grad

2、ient(广义既约梯度法广义既约梯度法)非线性最优化代码。线性和整数规划问非线性最优化代码。线性和整数规划问题取自题取自 Frontline Systems Frontline Systems 公司的公司的 John Watson John Watson 和和 DanFylstra DanFylstra 提供提供的有界变量单纯形法和分支边界法。的有界变量单纯形法和分支边界法。简 介第一章 用Excel求解规划问题1 1、启动、启动ExcelExcel；2 2、ToolsToolsAddAddInsIns3 3、选中、选中Solver AddSolver Addinin开启“Solver”Off

3、ice07在excel选项-加载项，点选“转到”，选中“规划求解”，然后在“数据”=分析第一章 用Excel求解规划问题4 4、重新打开、重新打开ToolsTools菜单；菜单；5 5、选中、选中SolverSolver即可。即可。开启“Solver”第一章 用Excel求解规划问题规划模型：规划模型：x1x1门生产量；门生产量；x2=x2=窗生产量窗生产量入门：一个简单的例子Max z=300*x1+500*x2Max z=300*x1+500*x2s.t.s.t.X1=4;X1=4;2*X2=12;2*X2=12;3*x1+2*x2=18;3*x1+2*x2=0;x1,x2=0;第一章 用

4、Excel求解规划问题打开打开ExcelExcel，输入模型参数的常量部分：上面是目标系数，下面是约，输入模型参数的常量部分：上面是目标系数，下面是约束（黄色的是常量）；束（黄色的是常量）；入门：一个简单的例子Examp01-01.xls第一章 用Excel求解规划问题然后输入模型参数的变量相关部分：即决策变量、与决策变量相关然后输入模型参数的变量相关部分：即决策变量、与决策变量相关的量，如总利润和实际使用工时（蓝色是变量部分）；的量，如总利润和实际使用工时（蓝色是变量部分）；入门：一个简单的例子第一章 用Excel求解规划问题点击点击OptionsOptions，选择，选择“Assume l

5、inear model”Assume linear model”和和“Assume nonAssume nonlinear”linear”。点击。点击【OKOK】，【solvesolve】：入门：一个简单的例子第一章 用Excel求解规划问题在弹出的在弹出的“Solver Results”Solver Results”中，选择中，选择“Reports”Reports”中的中的“Answer”,Answer”,选择选择【OKOK】。入门：一个简单的例子第一章 用Excel求解规划问题同时，决策变量的最优值以及和决策变量相关变量的值也自动同时，决策变量的最优值以及和决策变量相关变量的值也自动被填充

6、。被填充。入门：一个简单的例子第一章 用Excel求解规划问题回顾上节的例子：回顾上节的例子：用Excel进行灵敏度分析某工厂要生产两种产品：门和窗；某工厂要生产两种产品：门和窗；每扇门需要在每扇门需要在车间车间1加工加工1小时，小时，车间车间3加工加工3小时；小时；每扇窗需要在每扇窗需要在车间车间2加工加工2小时，小时，车间车间3加工加工2小时；小时；车间用于生产这两种产品的时间：车间用于生产这两种产品的时间：车间车间1为为4小时，小时，车间车间2为为12小时，小时，车间车间3为为18小时；小时；每扇门的利润每扇门的利润300元，窗的利润元，窗的利润500元；元；如何确定产品周生产计划，使总

7、利润最大？如何确定产品周生产计划，使总利润最大？最优解：最优解：x1=2;x2=6,x1=2;x2=6,最大利润最大利润36003600。第一章 用Excel求解规划问题那么，考虑以下的问题：那么，考虑以下的问题：用Excel进行灵敏度分析如果门的利润由如果门的利润由300300提高到提高到400400，最优解是否改变？对总利润，最优解是否改变？对总利润有怎样的影响？有怎样的影响？如果车间如果车间1 1的可用工时增加的可用工时增加2 2个小时，总利润是否变化？如何变个小时，总利润是否变化？如何变化，最优解是否发生变化？化，最优解是否发生变化？如果车间如果车间2 2更新工艺，生产一扇窗由以前的更

8、新工艺，生产一扇窗由以前的2 2小时下降到小时下降到1 1小时，小时，最优解如何变化？最优解如何变化？如果工厂新增加用电限制，是否会改变原来的最优方案？如果工厂新增加用电限制，是否会改变原来的最优方案？。第一章 用Excel求解规划问题用Excel进行灵敏度分析上例的灵敏度分析结果：上例的灵敏度分析结果：第一章 用Excel求解规划问题用Excel进行灵敏度分析上例的可变单元格的灵敏度分析结果：上例的可变单元格的灵敏度分析结果：最优解当该非基变量增加一个单位时目标函数减少的量(对max型问题)目标系数（已知）目标函数在允许的增量范围内变化时，最优解不变目标函数在允许的递减范围内变化时，最优解不

9、变故故c1c1的范围（的范围（300300300300，300300450450）；）；c2c2的范围（的范围（500500300300，500500无穷）；无穷）；第一章 用Excel求解规划问题用Excel进行灵敏度分析上例的灵敏度分析结果：上例的灵敏度分析结果：如果保证最优解不变，那么如果保证最优解不变，那么故车间故车间1 1工时的范围（工时的范围（4 42 2，4 4无穷）；无穷）；故车间故车间1 1工时的范围（工时的范围（12-6,12+612-6,12+6）;故车间故车间3 3工时的范围工时的范围(18-6,18+6);(18-6,18+6);终值工时实际使用量约束限制值不等式右边

10、的常量允许的增量(或渐量)：右端值在允许的增量和渐量范围内变化时，影子价格不变(但最优解可能变化)。影子价格，表示约束右端值每增加和减少1时，目标函数值的相应增量或渐量第一章 用Excel求解规划问题用Excel进行灵敏度分析影子价格影子价格第一个约束：增加车间第一个约束：增加车间1 1一个单位的可用工时，总利润并不变（因为时间一个单位的可用工时，总利润并不变（因为时间使用工时使用工时2 2小时小于可用工时小时小于可用工时4 4小时）；小时）；第二个约束：在允许的范围内第二个约束：在允许的范围内(12-6,12+6)(12-6,12+6)，增加车间，增加车间2 2一个单位的可用工一个单位的可用

11、工时，将增加利润时，将增加利润150150（因为车间（因为车间2 2的可用工时都用来生产了产品），这对的可用工时都用来生产了产品），这对管理者很有决策的意义。管理者很有决策的意义。第三个约束：。第三个约束：。第一章 用Excel求解规划问题用Excel进行灵敏度分析影子价格的经济意义：影子价格的经济意义：影子价格实际上是一种机会成本。当资源的价格低于影子价格时，可买影子价格实际上是一种机会成本。当资源的价格低于影子价格时，可买进该资源，反之可卖出。随着资源变化，影子价格也随之变化。当影子价进该资源，反之可卖出。随着资源变化，影子价格也随之变化。当影子价格与市场价格相同时，才处于平衡状态；格与市

12、场价格相同时，才处于平衡状态；当影子价格当影子价格0 0，表示该资源未得到充分利用；否则表示资源在生产中，表示该资源未得到充分利用；否则表示资源在生产中已全部利用；已全部利用；在公司内部，可借助资源的影子价格确定内部结算价格，以控制有限资在公司内部，可借助资源的影子价格确定内部结算价格，以控制有限资源的使用，使有限资源得到更大的经济效益。源的使用，使有限资源得到更大的经济效益。第一章 用Excel求解规划问题规划求解中的参数和设置Set Target Cell(Set Target Cell(设置目标单元格设置目标单元格)：一些单元格、具体数值、运算符号的组：一些单元格、具体数值、运算符号的组

13、合。注意：目标单元格一定要是公式，即一定是以合。注意：目标单元格一定要是公式，即一定是以“=”=”开始。类似于线性规开始。类似于线性规划中的目标函数。划中的目标函数。第一章 用Excel求解规划问题规划求解中的参数和设置Max,Min,Value of(Max,Min,Value of(最大值、最小值、给定值最大值、最小值、给定值)：在此指定是否希望目标单：在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定数值，请在右侧编辑框元格为最大值、最小值或某一特定数值。如果需要指定数值，请在右侧编辑框中键入该值中键入该值;By Changing cells(By Changing

14、cells(可变单元格可变单元格)：在此指定可变单元格。求解时其中的数：在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且值不断调整，直到满足约束条件并且“设置目标单元格设置目标单元格”框中指定的单元格达框中指定的单元格达到目标值。可变单元格必须直接或间接地与目标单元格相关联。类似于线性规到目标值。可变单元格必须直接或间接地与目标单元格相关联。类似于线性规划中的变量。划中的变量。第一章 用Excel求解规划问题规划求解中的参数和设置Guess(Guess(推测推测)：单击此按钮，自动推测：单击此按钮，自动推测“设置目标单元格设置目标单元格”框中的公式所框中的公式所引用的所有非公

15、式单元格，并在引用的所有非公式单元格，并在“可变单元格可变单元格”框中定位这些单元格的引用。框中定位这些单元格的引用。Subject to the Constraints(Subject to the Constraints(约束约束)：列出了规划求解的所有约束条件。：列出了规划求解的所有约束条件。Add(Add(添加添加)：显示：显示“添加约束添加约束”对话框。对话框。Change(Change(更改更改)：显示：显示“更改约束更改约束”对话框。注意：单击此按钮的时候，要对话框。注意：单击此按钮的时候，要先选择需要更改的约束。先选择需要更改的约束。第一章 用Excel求解规划问题规划求解中的

16、参数和设置Options(Options(选项）：显示选项）：显示“规划规划求解选项求解选项”对话框。在其中可加对话框。在其中可加载或保存规划求解模型，并对求载或保存规划求解模型，并对求解过程的高级属性进行控制。解过程的高级属性进行控制。下面详细介绍选项中的各项设下面详细介绍选项中的各项设置的具体含义。置的具体含义。第一章 用Excel求解规划问题规划求解中的参数和设置Max Time(Max Time(最长运算时间最长运算时间)：在此设定求解过程的时间。可输入的最大值为：在此设定求解过程的时间。可输入的最大值为3276732767（秒），默认值（秒），默认值 100100（秒）可以满足大多数

17、小型规划求解要求。（秒）可以满足大多数小型规划求解要求。Durations(Durations(迭代次数迭代次数)：在此设定求解过程中迭代运算的次数，限制求解过程：在此设定求解过程中迭代运算的次数，限制求解过程的时间。可输入的最大值为的时间。可输入的最大值为 3276732767，默认值，默认值 100 100 次可满足大多数小型规划求解次可满足大多数小型规划求解要求。要求。Precision(Precision(精度精度)：在此输入用于控制求解精度的数字，以确定约束条件单：在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。精度值必须表示为小数（元格中的数值是

18、否满足目标值或上下限。精度值必须表示为小数（0 0 到到 1 1 之之间），输入数字的小数位越多，精度越高。间），输入数字的小数位越多，精度越高。第一章 用Excel求解规划问题规划求解中的参数和设置Assume Linear Model(Assume Linear Model(采用线性模型采用线性模型)：当模型中的所有关系都是线性的，：当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解进程。并且希望解决线性优化问题时，选中此复选框可加速求解进程。Assume Non-Negative(Assume Non-Negative(假定非负假定非负)：如果选中此复选框，

19、则对于在：如果选中此复选框，则对于在“添加添加约束约束”对话框的对话框的“约束值约束值”框中没有设置下限的所有可变单元格，假定其下限框中没有设置下限的所有可变单元格，假定其下限为为 0 0（零）。（零）。Use Automatic Scaling(Use Automatic Scaling(自动按比例缩放自动按比例缩放)：如果选中此复选框，当输入和：如果选中此复选框，当输入和输出值量级差别很大时，可自动按比例缩放数值。例如，基于百万美元的投输出值量级差别很大时，可自动按比例缩放数值。例如，基于百万美元的投资将利润百分比最大化。资将利润百分比最大化。第一章 用Excel求解规划问题规划求解中的参

20、数和设置Show Duration Results(Show Duration Results(显示迭代结果显示迭代结果)：如果选中此复选框，每进行一次迭：如果选中此复选框，每进行一次迭代后都将中断代后都将中断“规划求解规划求解”，并显示当前的迭代结果。，并显示当前的迭代结果。Estimates(Estimates(估计估计)：指定在每个一维搜索中用来得到基本变量初始估计值的逼：指定在每个一维搜索中用来得到基本变量初始估计值的逼近方案。近方案。正切函数正切函数 ：使用正切向量线性外推：使用正切向量线性外推二次方程：用二次方程外推法，提高非线性规划问题的计算精度。二次方程：用二次方程外推法，提高

21、非线性规划问题的计算精度。第一章 用Excel求解规划问题规划求解中的参数和设置Derivatives(Derivatives(导数导数)：指定用于估计目标函数和约束函数偏导数的差分方案。：指定用于估计目标函数和约束函数偏导数的差分方案。Forward(Forward(向前差分向前差分)：用于大多数约束条件数值变化相对缓慢的问题。：用于大多数约束条件数值变化相对缓慢的问题。Center(Center(中心差分中心差分)：用于约束条件变化迅速，特别是接近限定值的问题。：用于约束条件变化迅速，特别是接近限定值的问题。虽然此选项要求更多计算，但在虽然此选项要求更多计算，但在“规划求解规划求解”不能返

22、回有效解时也许有帮助。不能返回有效解时也许有帮助。Search(Search(搜索搜索)：指定每次的迭代算法，以确定搜索方向。：指定每次的迭代算法，以确定搜索方向。牛顿法：用准牛顿法迭代需要的内存比共轭法多，但所需的迭代次数少。牛顿法：用准牛顿法迭代需要的内存比共轭法多，但所需的迭代次数少。共轭法：比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代运共轭法：比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代运算。当问题较大和内存有限，或步进迭代进程缓慢时，可用此选项。算。当问题较大和内存有限，或步进迭代进程缓慢时，可用此选项。第一章 用Excel求解规划问题规划求解中的参数和设置Loa

23、d Model(Load Model(装入模型装入模型)：显示：显示“装入模型装入模型”对话框，输入对所要加载的模型对话框，输入对所要加载的模型的引用。的引用。Save Model(Save Model(保存模型保存模型)：显示：显示“保存模型保存模型”对话框，在其中可指定保存模型对话框，在其中可指定保存模型的位置。只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自的位置。只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自动保存。动保存。第一章 用Excel求解规划问题用Excel求解整数规划用用ExcelExcel求解整数规划的步骤与一般线性规划问题相同，只是在约束条

24、件中添加求解整数规划的步骤与一般线性规划问题相同，只是在约束条件中添加一个一个“整数整数”约束。约束。在在ExcelExcel的的“添加约束添加约束”对话框中，用对话框中，用intint表示整数，因此，只要在该参数对话表示整数，因此，只要在该参数对话框中添加一个约束条件，在左面输入要求取整的决策变量的单元格地址，然后选框中添加一个约束条件，在左面输入要求取整的决策变量的单元格地址，然后选择择“int”int”即可。即可。第一章 用Excel求解规划问题用Excel求解整数规划例：某公司的新产品选择问题。某公司开发了三种新产品，相关数据如表。例：某公司的新产品选择问题。某公司开发了三种新产品，相

25、关数据如表。管理层决定，选择其中两种产品进行生产，且两个工厂中必须选出一个专管理层决定，选择其中两种产品进行生产，且两个工厂中必须选出一个专门生产新产品，那么如何选择产品、工厂并确定各种产品的周产量，使得门生产新产品，那么如何选择产品、工厂并确定各种产品的周产量，使得总利润最大。总利润最大。工厂单位产品的生产时间（小时）每周的可用生产时间（小时）产品1产品2产品3工厂134230工厂246240单位利润(千)573每周可销售量759第一章 用Excel求解规划问题用Excel求解整数规划决策变量：决策变量：x1,x2,x3:x1,x2,x3:产品产品1 1，2 2，3 3的每周产量；的每周产量

26、；y1,y2,y3y1,y2,y3（0-10-1量）量）:y1=1:y1=1表示生产产品表示生产产品1 1，=0=0表示不生产；表示不生产；y2=1y2=1表示生产产品表示生产产品2 2，=0=0表示不生产；表示不生产；y3=1y3=1表示生产产品表示生产产品3 3，=0=0表示不生产；表示不生产；y y（0-10-1量）量）:y=0:y=0表示选择工厂表示选择工厂1 1，=1=1表示选择工厂表示选择工厂2 2；约束约束1:1:选择其中两种产品进行生产选择其中两种产品进行生产y1+y2+y3=2;y1+y2+y3=2;x1=M*y1;x2=M*y2;x3=M*y3;(M x1=M*y1;x2=

27、M*y2;x3=M*y3;(M 为大数为大数)（x1x1如果非零，那么如果非零，那么y1y1必须为必须为1 1）第一章 用Excel求解规划问题用Excel求解整数规划约束约束2:2:两个工厂中必须选出一个专门生产新产品两个工厂中必须选出一个专门生产新产品3*x1+4*x2+2*x3=30+M*y;3*x1+4*x2+2*x3=30+M*y;(y(y如果等于如果等于1 1，即选择工厂，即选择工厂2 2，则不等式无效，则不等式无效)4*x1+6*x2+2*x3=40+M*(1-y);4*x1+6*x2+2*x3=40+M*(1-y);约束约束3 3：周产量受到周可销售量的限制：周产量受到周可销售

28、量的限制x1=7;x2=5;x3=9;x1=7;x2=5;x3=9;考虑考虑 x1=M*y1;x2=M*y2;x3=M*y3;(M x1=M*y1;x2=M*y2;x3=M*y3;(M 为大数为大数)因为每种产品的周最大产量就是周可销售量，因此二者可合并为因为每种产品的周最大产量就是周可销售量，因此二者可合并为 x1=7*y1;x2=5*y2;x3=9*y3x1=7*y1;x2=5*y2;x3=0,y1,y2,y3=1 or 0,y=1 or 0;x1,x2,x3=0,y1,y2,y3=1 or 0,y=1 or 0;第一章 用Excel求解规划问题用Excel求解整数规划综上，该问题的整数规

29、划模型如下：综上，该问题的整数规划模型如下：Max z=5*x1+7*x2+3*x3Max z=5*x1+7*x2+3*x3s.t.s.t.y1+y2+y3=2;y1+y2+y3=2;x1=7*y1;x2=5*y2;x3=9*y3;x1=7*y1;x2=5*y2;x3=9*y3;3*x1+4*x2+2*x3=30+M*y;3*x1+4*x2+2*x3=30+M*y;4*x1+6*x2+2*x3=40+M*(1-y);4*x1+6*x2+2*x3=0;x1,x2,x3=0;y1,y2,y3=1 or 0;y1,y2,y3=1 or 0;y=1 or 0;y=1 or 0;第一章 用Excel求解

30、规划问题用Excel求解整数规划建立建立ExcelExcel规划模型：常量规划模型：常量(黄色黄色););决策变量决策变量(绿色绿色););中间变量中间变量(蓝色蓝色)Examp01-02.xls第一章 用Excel求解规划问题用Excel求解整数规划建立建立ExcelExcel规划模型：常量规划模型：常量(黄色黄色););决策变量决策变量(绿色绿色););中间变量中间变量(蓝色蓝色)注意：注意：SUMPRODUCTSUMPRODUCT的用法的用法即两个矩阵各个相对应元素乘积即两个矩阵各个相对应元素乘积的和。的和。第一章 用Excel求解规划问题用Excel求解整数规划建立建立ExcelExc

31、el规划模型：常量规划模型：常量(黄色黄色););决策变量决策变量(绿色绿色););中间变量中间变量(蓝色蓝色)第一章 用Excel求解规划问题用Excel求解整数规划OptionsOptions：Assume linear model;Assume non-negativeAssume linear model;Assume non-negative第一章 用Excel求解规划问题用Excel求解整数规划最优解：最优解：第一章 用Excel求解规划问题用Excel求解整数规划最优解：最优解：第一章 用Excel求解规划问题练习：指派问题Exerc01-03.xls第一章 用Excel求解规划

32、问题练习：指派问题Exerc01-03.xls第一章 用Excel求解规划问题练习：飞机采购问题某航空公司准备采购一批飞机，共有大型和小型飞机两种，购买飞机某航空公司准备采购一批飞机，共有大型和小型飞机两种，购买飞机的数据如表。问如何采购，才能获得最高收益？的数据如表。问如何采购，才能获得最高收益？小型飞机 大型飞机总预算（百万）每架飞机年利润(百万)15100每架飞机采购价格(百万)550最多购买的数量2无限制Exerc01-02.xls第一章 用Excel求解规划问题用Excel求解非线性规划ExcelExcel可以求解非线性问题，但不保证全局最优解（可能是局部最优），可以求解非线性问题，

33、但不保证全局最优解（可能是局部最优），也不保证能求解。也不保证能求解。例：已知例：已知5 5个二维点，其坐标分别是（个二维点，其坐标分别是（3 3，1 1）（）（5 5，2 2）（）（4 4，3 3）（）（2 2，4 4）、（）、（1 1，5 5），予每个点不同的权重），予每个点不同的权重1 1，7 7，3 3，3 3，6 6，求这些点的精确，求这些点的精确重心。重心。这个问题在设备选址、新产品定位等问题都有应用；这个问题在设备选址、新产品定位等问题都有应用；精确重心的优化模型如下：精确重心的优化模型如下：第一章 用Excel求解规划问题用Excel求解非线性规划建立建立ExcelExcel模

34、型如下：模型如下：Examp01-03.xls第一章 用Excel求解规划问题用Excel求解非线性规划注意：注意：1 1、模型目标选、模型目标选minmin；2 2、OptionsOptions里去掉里去掉“线性线性”、“非负非负”的复选；的复选；Examp01-03.xls第一章 用Excel求解规划问题用Excel求解非线性规划结果：结果：Examp01-03.xls第一章 用Excel求解规划问题练习：面积最大问题给定给定400400米长的绳子，用来围成一个矩形菜地，问长和宽各为多少时面米长的绳子，用来围成一个矩形菜地，问长和宽各为多少时面积最大。积最大。*可以试试用小于约束和不同的初始解。可以试试用小于约束和不同的初始解。Exerc01-04.xls