《规划问题求解与EXCEL应用.doc》由会员分享，可在线阅读，更多相关《规划问题求解与EXCEL应用.doc（42页珍藏版）》请在金锄头文库上搜索。
1、培训与发展Training & Development2005年专刊2（总第34期）国家发展和改革委员会培训中心 2005年6月30日规划问题求解与EXCEL应用目录第一节 EXCEL中的规划求解工具(2)第二节 线性规划求解方法(7)第三节 对偶问题与影子价格(23)第四节 线性规划的敏感度分析 (28)第五节 整数规划求解(32)第六节 非线性规划求解(33)第七节 目标规划问题求解(37)规划问题求解与EXCEL应用国家发展改革委培训中心委机关培训部编写 1939年，前苏联科学家康托洛维奇总结了他对生产组织的研究，写出了生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著
2、作。1947年，丹齐格提出了单纯形方法后，线性规划便迅速形成了一个独立的理论分支。此后，整数规划、目标规划、非线性规划理论逐渐形成并成熟。 微软在EXCEL中开发的“规划求解”工具是以单纯形方法为基础的，使用起来比较方便。另外，芝加哥LINDO公司研制的Lindo软件在解决线性规划模型、整数规划模型、二次规划模型等方面功能比较强大。但目前尚无汉化版，需要学习者，可从LINDO公司的网址免费下载教学演示软件，如果要得到功能全面的软件，必须购买正版软件。 我们组织编写的经济计量分析与EXCEL应用一书，对“规划求解”略有介绍。由于规划理论是经济学中的一种重要方法，规划求解在实际经济管理和管理决策中
3、应用广泛，我们特编一个参阅材料，仅供参考。第一节 EXCEL中的规划求解工具EXCEL中的规划求解工具设置了4个对话框。有的选项已有默认值，只是需要改变才需要选择。为便于大家选择，我们特将选项作些说明。一、关于“规划求解参数”对话框 【设置目标单元格】在此指定要设置为特定数值或者最大值或最小值的目标单元格。该单元格必须包含公式。【等于】在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定数值，请在右侧编辑框中键入该值。【可变单元格】在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。可变单元格必须直接或间接地与目标单
4、元格相关联。在“设置目标单元格”框中，输入目标单元格的单元格引用或名称。目标单元格必须包含公式。在“可变单元格”框中，输入每个可变单元格的名称或引用，用逗号分隔不相邻的引用。可变单元格必须直接或间接与目标单元格相联系。最多可以指定 200 个可变单元格。 【推测】单击此按钮，自动推测“设置目标单元格”框中的公式所引用的所有非公式单元格，并在“可变单元格”框中定位这些单元格的引用。【约束】在此列出了规划求解的所有约束条件。【添加】显示“添加约束”对话框。【更改】显示“更改约束”对话框。【删除】删除选定的约束条件。【求解】对定义好的问题进行求解。【关闭】关闭对话框，不进行规划求解。但保留通过“选项
5、”、“添加”、“更改”或“删除”按钮所做的更改。【选项】显示“规划求解选项”对话框。在其中可加载或保存规划求解模型，并对求解过程的高级属性进行控制。【全部重设】清除规划求解中的当前设置，将所有的设置恢复为初始值。二、关于“规划求解选项”对话框在本对话框中，可以设定规划求解过程的一些高级功能、加载或保存规划求解定义，以及为线性和非线性规划求解定义参数。每一选项都有默认设置，可以满足大多数情况下的要求。【最长运算时间】在此设定求解过程的时间。可输入的最大值为 32767（秒），默认值 100（秒）可以满足大多数小型规划求解要求。【迭代次数】在此设定求解过程中迭代运算的次数，限制求解过程的时间。可输
6、入的最大值为 32767，默认值 100 次可满足大多数小型规划求解要求。【精度】在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。精度值必须表示为小数（0 到 1 之间），输入数字的小数位越多，精度越高。例如，0.0001 比 0.01 的精度高。【允许误差】在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只应用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。【收敛度】在此输入收敛度数值，当最近五次迭代后目标单元格中数值的变化小于“收敛度”框中设置的数值时，“规划求解”停止运行。收敛度只应用于非线性
7、规划求解问题，并且必须表示为小数（0 到 1 之间）。设置的数值越小，收敛度就越高。例如，0.0001 表示比 0.01 更小的相对差别。收敛度越小，“规划求解”得到结果所需的时间就越长。【采用线性模型】当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解进程。【显示迭代结果】如果选中此复选框，每进行一次迭代后都将中断“规划求解”，并显示当前的迭代结果。【自动按比例缩放】如果选中此复选框，当输入和输出值量级差别很大时，可自动按比例缩放数值。例如，基于百万美元的投资将利润百分比最大化。【假定非负】如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没有设置下限
8、的所有可变单元格，假定其下限为 0（零）。【估计】指定在每个一维搜索中用来得到基本变量初始估计值的逼近方案。【正切函数】使用正切向量线性外推。【二次方程】用二次方程外推法，提高非线性规划问题的计算精度。【导数】指定用于估计目标函数和约束函数偏导数的差分方案。【向前差分】 用于大多数约束条件数值变化相对缓慢的问题。【中心差分】 用于约束条件变化迅速，特别是接近限定值的问题。虽然此选项要求更多的计算，但在“规划求解”不能返回有效解时也许会有帮助。表1差分公式表阶数向前差分公式向后差分公式中心差分公式一阶二阶【搜索】指定每次的迭代算法，以确定搜索方向。【牛顿法】牛顿法的基本思想是利用目标函数f(x)
9、在第三代点xk处的二次Taylor展开作为模型函数，并用这个二次模型函数小点序列去逼近目标函数的极小点。用准牛顿法迭代需要的内存比共轭法多，但所需的迭代次数少。【共轭法】比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代运算。当问题较大和内存有限，或步进迭代进程缓慢时，可用此选项。【装入模型】显示“装入模型”对话框，输入对所要加载的模型的引用。【保存模型】显示“保存模型”对话框，在其中可指定保存模型的位置。只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自动保存。三、约束条件（一）添加约束条件 1.在“规划求解参数”对话框的“约束”下，单击“添加”。2.在“单元格引用位置”框中
10、，输入需要对其中数值进行约束的单元格引用或单元格区域的名称。3.单击希望在引用单元格和约束条件之间使用的关系（“=”、“Int”或“Bin”）。如果单击“Int”，则“约束值”框中会显示“整数”；如果单击“Bin”，则“约束值”框中会显示“二进制”。4.在“约束值”框中，键入数字、单元格引用或名称，或键入公式。5.执行下列操作之一：一是若要接受约束条件并要添加其他的约束条件，请单击“添加”；若要接受约束条件并返回“规划求解参数”对话框，请单击“确定”。 6.只能在对可变单元格的约束条件中应用“Int”和“Bin”关系。当“规划求解选项”对话框中的“采用线性模型”复选框被选中时，对约束条件的数量
11、没有限制。对于非线性问题，每个可变单元格除了变量的范围和整数限制外，还可以有多达 100 个约束。(二)更改或删除约束条件1.在“规划求解参数”对话框的“约束”下，单击要更改或删除的约束条件。2.单击“更改”，并进行所需的更改，或单击“删除”。3.单击“求解”，再执行下列操作之一：若要在工作表中保存求解后的数值，请在“规划求解结果”对话框中，单击“保存规划求解结果”。 4.若要恢复原始数据，请单击“恢复为原值”。四、关于“规划求解结果”对话框显示完成消息和最接近的目标求解结果。【保存规划求解结果】单击此选项，接受求解结果，并将其放置到可变单元格中。【恢复为原值】单击此选项可在可变单元格中恢复初
12、始值。【报告】创建指定类型的报告，并将每份报告放置于工作簿中单独的一张工作表上。【运算结果报告】列出目标单元格和可变单元格及其初始值和最终结果、约束条件以及有关约束条件的信息。【敏感性报告】提供有关求解结果对“规划求解参数”对话框的“目标单元格”框中所指定的公式的微小变化或约束条件的微小变化的敏感程度的信息。含有整数约束条件的模型不能生成该报告。对于非线性模型，该报告提供递减梯度和拉格朗日乘数；对于线性模型，该报告中将包含递减成本、阴影价格、目标式系数（允许的增量和允许的减量）以及约束右侧的区域。【极限值报告】列出目标单元格和可变单元格及其各自的数值、上下限和目标值。含有整数约束条件的模型不能
13、生成该报告。下限是在保持其他可变单元格数值不变并满足约束条件的情况下，某个可变单元格可以取到的最小值。上限是在这种情况下可以取到的最大值。【保存方案】打开“保存方案”对话框，在其中可保存用于 Microsoft Excel“方案管理器”的单元格数值。五、规划求解常用函数表2规划求解常用函数表名称功能语法MDETERM返回一个数组的矩阵行列式的值MDETERM(array)Array：行数和列数相等的数值数组MIN VERSE返回数组矩阵的逆距阵MINVERSE(array)Array：是具有相等行数和列数的数值数组。MMULT返回两数组的矩阵乘积。结果矩阵的行数与 array1 的行数相同，矩
14、阵的列数与 array2 的列数相同。MMULT(array1,array2)Array1, array2：是要进行矩阵乘法运算的两个数组。SUMPRODUCT在给定的几组数组中，将数组间对应的元素相乘，并返回乘积之和。SUMPRODUCT(array1,array2,array3, .)Array1, array2, array3, 为 2 到 30 个数组，其相应元素需要进行相乘并求和。第二节线性规划求解方法 线性规划是在一定的限制条件下，利用数学方法进行运算，使对前景的规划达到最优的方法。在经济管理中，线性规划研究的主要问题包括运输问题、生产的组织与计划问题、合理下料问题、配料问题、布局问题、分派问题等。有的著作把它分为资源分配问题、成本收益平衡问题、网络配送问题等。线性规划的组成： 目标函数：Max f（x）或Min f(x) 约束条件：s.t. (subject to)满足于 决策变量：用符号来表示可控制的因素线性规划问题的一般形式为：目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2+ a1n xn()b1 a21x1 + a22 x2 + a2n xn( )b2
