第一章用Excel求解规划问题ppt课件.ppt

主讲人: 雒兴刚东北大学系统工程研究所Email： Tel: 83682292,优化软件与应用,第一章 用Excel求解规划问题,Excel具有内置的规划求解功能。Microsoft Excel 的“规划求解”工具取自德克萨斯大学奥斯汀分校的 Leon Lasdon 和克里夫兰州立大学的 Allan Waren 共同开发的Generalized Reduced Gradient (广义既约梯度法) 非线性最优化代码。线性和整数规划问题取自 Frontline Systems 公司的 John Watson 和 DanFylstra 提供的有界变量单纯形法和分支边界法。,简 介,第一章 用Excel求解规划问题,1、启动Excel；2、ToolsAddIns3、选中Solver Addin,开启 “Solver”,Office07在excel选项-加载项，点选“转到”，选中“规划求解”，然后在“数据”=分析,第一章 用Excel求解规划问题,4、重新打开Tools菜单；5、选中Solver即可。,开启 “Solver”,第一章 用Excel求解规划问题,例：某工厂要生产两种产品：门和窗；每扇门需要在车间1加工1小时，车间3加工3小时；每扇窗需要在车间2加工2小时，车间3加工2小时；车间用于生产这两种产品的时间：车间1为4小时，车间2为12小时，车间3为18小时；每扇门的利润300元，窗的利润500元；如何确定产品周生产计划，使总利润最大？,入门：一个简单的例子,第一章 用Excel求解规划问题,规划模型： x1门生产量；x2=窗生产量,入门：一个简单的例子,Max z=300*x1+500*x2s.t.X1=0;,第一章 用Excel求解规划问题,打开Excel，输入模型参数的常量部分：上面是目标系数，下面是约束（黄色的是常量）；,入门：一个简单的例子,Examp01-01.xls,第一章 用Excel求解规划问题,然后输入模型参数的变量相关部分：即决策变量、与决策变量相关的量，如总利润和实际使用工时（蓝色是变量部分）；,入门：一个简单的例子,第一章 用Excel求解规划问题,选“Solver”，输入如下参数：,入门：一个简单的例子,第一章 用Excel求解规划问题,点击Options，选择“Assume linear model”和“Assume nonlinear”。点击【OK】，【solve】：,入门：一个简单的例子,第一章 用Excel求解规划问题,在弹出的“Solver Results”中，选择“Reports”中的“ Answer”, 选择【OK】。,入门：一个简单的例子,第一章 用Excel求解规划问题,结果如下：,入门：一个简单的例子,第一章 用Excel求解规划问题,同时，决策变量的最优值以及和决策变量相关变量的值也自动被填充。,入门：一个简单的例子,第一章 用Excel求解规划问题,灵敏度分析能够为决策提供有用的信息，能够帮助管理者进行正确的决策。例如，模型中的有些系数（例如上例中的可用工时）被认为是确定的，优化也在此基础上进行。但是，实际情况中，环境变化可能使系数发生变化，而这些变化可能又影响当前的最优解。因此，需要研究最优解对系数变化的反应程度，以适应各种偶然变化。,用Excel进行灵敏度分析,第一章 用Excel求解规划问题,回顾上节的例子：,用Excel进行灵敏度分析,某工厂要生产两种产品：门和窗；每扇门需要在车间1加工1小时，车间3加工3小时；每扇窗需要在车间2加工2小时，车间3加工2小时；车间用于生产这两种产品的时间：车间1为4小时，车间2为12小时，车间3为18小时；每扇门的利润300元，窗的利润500元；如何确定产品周生产计划，使总利润最大？,最优解：x1=2; x2=6, 最大利润3600。,第一章 用Excel求解规划问题,那么，考虑以下的问题：,用Excel进行灵敏度分析,如果门的利润由300提高到400，最优解是否改变？对总利润有怎样的影响？如果车间1的可用工时增加2个小时，总利润是否变化？如何变化，最优解是否发生变化？如果车间2更新工艺，生产一扇窗由以前的2小时下降到1小时，最优解如何变化？如果工厂新增加用电限制，是否会改变原来的最优方案？。,第一章 用Excel求解规划问题,用Excel进行灵敏度分析,用Excel进行灵敏度分析最简单的方法，就是修改参数并重新进行求解，但逐个尝试工作量很大；Excel提供了敏感性报告的功能，可以利用其结果方便的进行灵敏度分析。,第一章 用Excel求解规划问题,用Excel进行灵敏度分析,上例的灵敏度分析结果：,第一章 用Excel求解规划问题,用Excel进行灵敏度分析,上例的可变单元格的灵敏度分析结果：,最优解,当该非基变量增加一个单位时目标函数减少的量(对max型问题),目标系数（已知）,目标函数在允许的增量范围内变化时，最优解不变,目标函数在允许的递减范围内变化时，最优解不变,故c1的范围（300300，300450）；,c2的范围（500300，500无穷）；,第一章 用Excel求解规划问题,用Excel进行灵敏度分析,上例的灵敏度分析结果：,如果保证最优解不变，那么故车间1工时的范围（42，4无穷）；故车间1工时的范围（12-6, 12+6）;故车间3工时的范围(18-6, 18+6);,终值工时实际使用量,约束限制值不等式右边的常量,允许的增量(或渐量)：右端值在允许的增量和渐量范围内变化时，影子价格不变(但最优解可能变化)。,影子价格，表示约束右端值每增加和减少1时，目标函数值的相应增量或渐量,第一章 用Excel求解规划问题,用Excel进行灵敏度分析,影子价格第一个约束：增加车间1一个单位的可用工时，总利润并不变（因为时间使用工时2小时小于可用工时4小时）；第二个约束：在允许的范围内(12-6,12+6)，增加车间2一个单位的可用工时，将增加利润150（因为车间2的可用工时都用来生产了产品），这对管理者很有决策的意义。第三个约束：。,第一章 用Excel求解规划问题,用Excel进行灵敏度分析,影子价格的经济意义：影子价格实际上是一种机会成本。当资源的价格低于影子价格时，可买进该资源，反之可卖出。随着资源变化，影子价格也随之变化。当影子价格与市场价格相同时，才处于平衡状态；当影子价格0，表示该资源未得到充分利用；否则表示资源在生产中已全部利用；在公司内部，可借助资源的影子价格确定内部结算价格，以控制有限资源的使用，使有限资源得到更大的经济效益。,第一章 用Excel求解规划问题,练习：文具生产方案和临时工估计,某厂利用原材料白坯纸生产稿纸、日记簿和练习本三种产品；现有工人100人，白坯纸的日供应量30000公斤；若单独生产产品，工人每日可生产稿纸30捆、日记簿30打、练习本30箱；资源消耗情况：每捆稿纸用白坯纸10/3公斤,每打日记簿用白坯纸40/3公斤,每箱练习本用白坯纸80/3公斤；产品盈利情况：每捆稿纸1元，每打日记簿2元，每箱练习本3元,问题1：每天生产稿纸、日记簿和练习本各多少（可取小数），利润才最好？问题2：如果工人数量不足，可招临时工，其费用每天每人15元，问在目前的条件下，该厂是否需要招临时工？ 如果招临时工，那么招多少才好？,第一章 用Excel求解规划问题,规划求解中的参数和设置,Set Target Cell(设置目标单元格)：一些单元格、具体数值、运算符号的组合。注意：目标单元格一定要是公式，即一定是以“=”开始。类似于线性规划中的目标函数。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Max, Min, Value of (最大值、最小值、给定值)：在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定数值，请在右侧编辑框中键入该值;By Changing cells(可变单元格)：在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。可变单元格必须直接或间接地与目标单元格相关联。类似于线性规划中的变量。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Guess (推测)：单击此按钮，自动推测“设置目标单元格”框中的公式所引用的所有非公式单元格，并在“可变单元格”框中定位这些单元格的引用。Subject to the Constraints(约束)：列出了规划求解的所有约束条件。Add (添加)：显示“添加约束”对话框。Change (更改)：显示“更改约束”对话框。注意：单击此按钮的时候，要先选择需要更改的约束。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Delete (删除)：删除选定的约束条件。同样单击此按钮前，要先选择需要删除的约束。Solve(求解)：对定义好的问题进行求解。Close (关闭)：关闭对话框，不进行规划求解。但保留通过“选项”、“添加”、“更改”或“删除”按钮所做的更改。也就是说，当你下次再次单击“规划求解”按钮后，对话框显示上回所设置的参数。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Options(选项）：显示“规划求解选项”对话框。在其中可加载或保存规划求解模型，并对求解过程的高级属性进行控制。下面详细介绍选项中的各项设置的具体含义。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Max Time (最长运算时间)：在此设定求解过程的时间。可输入的最大值为32767（秒），默认值 100（秒）可以满足大多数小型规划求解要求。Durations (迭代次数)：在此设定求解过程中迭代运算的次数，限制求解过程的时间。可输入的最大值为 32767，默认值 100 次可满足大多数小型规划求解要求。Precision (精度)：在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。精度值必须表示为小数（0 到 1 之间），输入数字的小数位越多，精度越高。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Tolerance (允许误差)：在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只应用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。Convergence (收敛度)：在此输入收敛度数值，当最近五次迭代后目标单元格中数值的变化小于“收敛度”框中设置的数值时，“规划求解”停止运行。收敛度只应用于非线性规划求解问题，并且必须表示为小数（0 到 1 之间）。设置的数值越小，收敛度就越高。例如，0.0001 表示比 0.01 更小的相对差别。收敛度越小，“规划求解”得到结果所需的时间就越长。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Assume Linear Model (采用线性模型)：当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解进程。Assume Non-Negative (假定非负)：如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没有设置下限的所有可变单元格，假定其下限为 0（零）。Use Automatic Scaling (自动按比例缩放)：如果选中此复选框，当输入和输出值量级差别很大时，可自动按比例缩放数值。例如，基于百万美元的投资将利润百分比最大化。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Show Duration Results (显示迭代结果)：如果选中此复选框，每进行一次迭代后都将中断“规划求解”，并显示当前的迭代结果。Estimates (估计)：指定在每个一维搜索中用来得到基本变量初始估计值的逼近方案。正切函数 ：使用正切向量线性外推二次方程：用二次方程外推法，提高非线性规划问题的计算精度。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Derivatives (导数)：指定用于估计目标函数和约束函数偏导数的差分方案。Forward (向前差分)：用于大多数约束条件数值变化相对缓慢的问题。Center (中心差分)：用于约束条件变化迅速，特别是接近限定值的问题。虽然此选项要求更多计算，但在“规划求解”不能返回有效解时也许有帮助。Search (搜索)：指定每次的迭代算法，以确定搜索方向。牛顿法：用准牛顿法迭代需要的内存比共轭法多，但所需的迭代次数少。共轭法：比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代运算。当问题较大和内存有限，或步进迭代进程缓慢时，可用此选项。,第一章 用Excel求解规划问题,规划求解中的参数和设置,Load Model (装入模型)：显示“装入模型”对话框，输入对所要加载的模型的引用。Save Model (保存模型)：显示“保存模型”对话框，在其中可指定保存模型的位置。只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自动保存。,第一章 用Excel求解规划问题,用Excel求解整数规划,用Excel求解整数规划的步骤与一般线性规划问题相同，只是在约束条件中添加一个“整数”约束。在Excel的“添加约束”对话框中，用int表示整数，因此，只要在该参数对话框中添加一个约束条件，在左面输入要求取整的决策变量的单元格地址，然后选择“int”即可。,第一章 用Excel求解规划问题,用Excel求解整数规划,例：某公司的新产品选择问题。某公司开发了三种新产品，相关数据如表。管理层决定，选择其中两种产品进行生产，且两个工厂中必须选出一个专门生产新产品，那么如何选择产品、工厂并确定各种产品的周产量，使得总利润最大。,第一章 用Excel求解规划问题,用Excel求解整数规划,决策变量：x1, x2, x3 : 产品1，2，3的每周产量；y1, y2 , y3（0-1量） : y1=1表示生产产品1，=0表示不生产； y2=1表示生产产品2，=0表示不生产； y3=1表示生产产品3，=0表示不生产；y（0-1量）: y=0表示选择工厂1，=1表示选择工厂2；,约束1:选择其中两种产品进行生产y1+y2+y3=2;x1=M*y1; x2=M*y2; x3=M*y3; (M 为大数)（x1如果非零，那么y1必须为1）,第一章 用Excel求解规划问题,用Excel求解整数规划,约束2: 两个工厂中必须选出一个专门生产新产品3*x1+4*x2+2*x3=0, y1, y2, y3 =1 or 0, y=1 or 0;,第一章 用Excel求解规划问题,用Excel求解整数规划,综上，该问题的整数规划模型如下：Max z=5*x1+7*x2+3*x3s.t.y1+y2+y3=0;y1, y2, y3 =1 or 0;y=1 or 0;,第一章 用Excel求解规划问题,用Excel求解整数规划,建立Excel规划模型：常量(黄色); 决策变量(绿色); 中间变量(蓝色),Examp01-02.xls,第一章 用Excel求解规划问题,用Excel求解整数规划,建立Excel规划模型：常量(黄色); 决策变量(绿色); 中间变量(蓝色),注意：SUMPRODUCT的用法即两个矩阵各个相对应元素乘积的和。,第一章 用Excel求解规划问题,用Excel求解整数规划,建立Excel规划模型：常量(黄色); 决策变量(绿色); 中间变量(蓝色),第一章 用Excel求解规划问题,用Excel求解整数规划,Options： Assume linear model; Assume non-negative,第一章 用Excel求解规划问题,用Excel求解整数规划,最优解：,第一章 用Excel求解规划问题,用Excel求解整数规划,最优解：,第一章 用Excel求解规划问题,练习：指派问题,Exerc01-03.xls,第一章 用Excel求解规划问题,练习：指派问题,Exerc01-03.xls,第一章 用Excel求解规划问题,练习：飞机采购问题,某航空公司准备采购一批飞机，共有大型和小型飞机两种，购买飞机的数据如表。问如何采购，才能获得最高收益？,Exerc01-02.xls,第一章 用Excel求解规划问题,用Excel求解非线性规划,Excel可以求解非线性问题，但不保证全局最优解（可能是局部最优），也不保证能求解。例：已知5个二维点，其坐标分别是（3，1）（5，2）（4，3）（2，4）、（1，5），予每个点不同的权重1，7，3，3，6，求这些点的精确重心。这个问题在设备选址、新产品定位等问题都有应用；精确重心的优化模型如下：,第一章 用Excel求解规划问题,用Excel求解非线性规划,建立Excel模型如下：,Examp01-03.xls,第一章 用Excel求解规划问题,用Excel求解非线性规划,注意：1、模型目标选min；2、Options里去掉“线性”、“非负”的复选；,Examp01-03.xls,第一章 用Excel求解规划问题,用Excel求解非线性规划,结果：,Examp01-03.xls,第一章 用Excel求解规划问题,练习：面积最大问题,给定400米长的绳子，用来围成一个矩形菜地，问长和宽各为多少时面积最大。*可以试试用小于约束和不同的初始解。,Exerc01-04.xls,