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