规划问题求解与EXCEL应用.doc

培训与发展Training & Development2005年专刊2（总第34期）国家发展和改革委员会培训中心 2005年6月30日规划问题求解与EXCEL应用目录第一节 EXCEL中的规划求解工具(2)第二节 线性规划求解方法(7)第三节 对偶问题与影子价格(23)第四节 线性规划的敏感度分析 (28)第五节 整数规划求解(32)第六节 非线性规划求解(33)第七节 目标规划问题求解(37)规划问题求解与EXCEL应用国家发展改革委培训中心委机关培训部编写 1939年，前苏联科学家康托洛维奇总结了他对生产组织的研究，写出了生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著作。1947年，丹齐格提出了单纯形方法后，线性规划便迅速形成了一个独立的理论分支。此后，整数规划、目标规划、非线性规划理论逐渐形成并成熟。 微软在EXCEL中开发的“规划求解”工具是以单纯形方法为基础的，使用起来比较方便。另外，芝加哥LINDO公司研制的Lindo软件在解决线性规划模型、整数规划模型、二次规划模型等方面功能比较强大。但目前尚无汉化版，需要学习者，可从LINDO公司的网址免费下载教学演示软件，如果要得到功能全面的软件，必须购买正版软件。 我们组织编写的经济计量分析与EXCEL应用一书，对“规划求解”略有介绍。由于规划理论是经济学中的一种重要方法，规划求解在实际经济管理和管理决策中应用广泛，我们特编一个参阅材料，仅供参考。第一节 EXCEL中的规划求解工具EXCEL中的规划求解工具设置了4个对话框。有的选项已有默认值，只是需要改变才需要选择。为便于大家选择，我们特将选项作些说明。一、关于“规划求解参数”对话框 【设置目标单元格】在此指定要设置为特定数值或者最大值或最小值的目标单元格。该单元格必须包含公式。【等于】在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定数值，请在右侧编辑框中键入该值。【可变单元格】在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。可变单元格必须直接或间接地与目标单元格相关联。在“设置目标单元格”框中，输入目标单元格的单元格引用或名称。目标单元格必须包含公式。在“可变单元格”框中，输入每个可变单元格的名称或引用，用逗号分隔不相邻的引用。可变单元格必须直接或间接与目标单元格相联系。最多可以指定 200 个可变单元格。 【推测】单击此按钮，自动推测“设置目标单元格”框中的公式所引用的所有非公式单元格，并在“可变单元格”框中定位这些单元格的引用。【约束】在此列出了规划求解的所有约束条件。【添加】显示“添加约束”对话框。【更改】显示“更改约束”对话框。【删除】删除选定的约束条件。【求解】对定义好的问题进行求解。【关闭】关闭对话框，不进行规划求解。但保留通过“选项”、“添加”、“更改”或“删除”按钮所做的更改。【选项】显示“规划求解选项”对话框。在其中可加载或保存规划求解模型，并对求解过程的高级属性进行控制。【全部重设】清除规划求解中的当前设置，将所有的设置恢复为初始值。二、关于“规划求解选项”对话框在本对话框中，可以设定规划求解过程的一些高级功能、加载或保存规划求解定义，以及为线性和非线性规划求解定义参数。每一选项都有默认设置，可以满足大多数情况下的要求。【最长运算时间】在此设定求解过程的时间。可输入的最大值为 32767（秒），默认值 100（秒）可以满足大多数小型规划求解要求。【迭代次数】在此设定求解过程中迭代运算的次数，限制求解过程的时间。可输入的最大值为 32767，默认值 100 次可满足大多数小型规划求解要求。【精度】在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。精度值必须表示为小数（0 到 1 之间），输入数字的小数位越多，精度越高。例如，0.0001 比 0.01 的精度高。【允许误差】在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只应用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。【收敛度】在此输入收敛度数值，当最近五次迭代后目标单元格中数值的变化小于“收敛度”框中设置的数值时，“规划求解”停止运行。收敛度只应用于非线性规划求解问题，并且必须表示为小数（0 到 1 之间）。设置的数值越小，收敛度就越高。例如，0.0001 表示比 0.01 更小的相对差别。收敛度越小，“规划求解”得到结果所需的时间就越长。【采用线性模型】当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解进程。【显示迭代结果】如果选中此复选框，每进行一次迭代后都将中断“规划求解”，并显示当前的迭代结果。【自动按比例缩放】如果选中此复选框，当输入和输出值量级差别很大时，可自动按比例缩放数值。例如，基于百万美元的投资将利润百分比最大化。【假定非负】如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没有设置下限的所有可变单元格，假定其下限为 0（零）。【估计】指定在每个一维搜索中用来得到基本变量初始估计值的逼近方案。【正切函数】使用正切向量线性外推。【二次方程】用二次方程外推法，提高非线性规划问题的计算精度。【导数】指定用于估计目标函数和约束函数偏导数的差分方案。【向前差分】 用于大多数约束条件数值变化相对缓慢的问题。【中心差分】 用于约束条件变化迅速，特别是接近限定值的问题。虽然此选项要求更多的计算，但在“规划求解”不能返回有效解时也许会有帮助。表1差分公式表阶数向前差分公式向后差分公式中心差分公式一阶二阶【搜索】指定每次的迭代算法，以确定搜索方向。【牛顿法】牛顿法的基本思想是利用目标函数f(x)在第三代点xk处的二次Taylor展开作为模型函数，并用这个二次模型函数小点序列去逼近目标函数的极小点。用准牛顿法迭代需要的内存比共轭法多，但所需的迭代次数少。【共轭法】比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代运算。当问题较大和内存有限，或步进迭代进程缓慢时，可用此选项。【装入模型】显示“装入模型”对话框，输入对所要加载的模型的引用。【保存模型】显示“保存模型”对话框，在其中可指定保存模型的位置。只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自动保存。三、约束条件（一）添加约束条件 1.在“规划求解参数”对话框的“约束”下，单击“添加”。2.在“单元格引用位置”框中，输入需要对其中数值进行约束的单元格引用或单元格区域的名称。3.单击希望在引用单元格和约束条件之间使用的关系（“=”、“Int”或“Bin”）。如果单击“Int”，则“约束值”框中会显示“整数”；如果单击“Bin”，则“约束值”框中会显示“二进制”。4.在“约束值”框中，键入数字、单元格引用或名称，或键入公式。5.执行下列操作之一：一是若要接受约束条件并要添加其他的约束条件，请单击“添加”；若要接受约束条件并返回“规划求解参数”对话框，请单击“确定”。 6.只能在对可变单元格的约束条件中应用“Int”和“Bin”关系。当“规划求解选项”对话框中的“采用线性模型”复选框被选中时，对约束条件的数量没有限制。对于非线性问题，每个可变单元格除了变量的范围和整数限制外，还可以有多达 100 个约束。(二)更改或删除约束条件1.在“规划求解参数”对话框的“约束”下，单击要更改或删除的约束条件。2.单击“更改”，并进行所需的更改，或单击“删除”。3.单击“求解”，再执行下列操作之一：若要在工作表中保存求解后的数值，请在“规划求解结果”对话框中，单击“保存规划求解结果”。 4.若要恢复原始数据，请单击“恢复为原值”。四、关于“规划求解结果”对话框显示完成消息和最接近的目标求解结果。【保存规划求解结果】单击此选项，接受求解结果，并将其放置到可变单元格中。【恢复为原值】单击此选项可在可变单元格中恢复初始值。【报告】创建指定类型的报告，并将每份报告放置于工作簿中单独的一张工作表上。【运算结果报告】列出目标单元格和可变单元格及其初始值和最终结果、约束条件以及有关约束条件的信息。【敏感性报告】提供有关求解结果对“规划求解参数”对话框的“目标单元格”框中所指定的公式的微小变化或约束条件的微小变化的敏感程度的信息。含有整数约束条件的模型不能生成该报告。对于非线性模型，该报告提供递减梯度和拉格朗日乘数；对于线性模型，该报告中将包含递减成本、阴影价格、目标式系数（允许的增量和允许的减量）以及约束右侧的区域。【极限值报告】列出目标单元格和可变单元格及其各自的数值、上下限和目标值。含有整数约束条件的模型不能生成该报告。下限是在保持其他可变单元格数值不变并满足约束条件的情况下，某个可变单元格可以取到的最小值。上限是在这种情况下可以取到的最大值。【保存方案】打开“保存方案”对话框，在其中可保存用于 Microsoft Excel“方案管理器”的单元格数值。五、规划求解常用函数表2规划求解常用函数表名称功能语法MDETERM返回一个数组的矩阵行列式的值MDETERM(array)Array：行数和列数相等的数值数组MIN VERSE返回数组矩阵的逆距阵MINVERSE(array)Array：是具有相等行数和列数的数值数组。MMULT返回两数组的矩阵乘积。结果矩阵的行数与 array1 的行数相同，矩阵的列数与 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 ak1 x1 + ak2 x2 + + akn xn ()bk x1 ，x2 ， ，xn 0用矩阵表示则化为求x，满足约束条件使目标函数f(x)=cx达到极大（或极小）。线性规划问题的标准形式可以通过对一般形式进行改造而得。（1）如果第k 个式子为： ak1 x1 + ak2 x2 + + akn xn ()bk，则加入xm+k0，改为：ak1 x1 + ak2 x2 + + akn xn xm+kbk。其他式子也如法炮制。xm+k为松弛变量。（2）如果问题是求目标函数max z = c1 x1 + c2 x2 + + cn xn ，则化为求目标函数min z= c1 x1 c2 x2 cn xn（3）如果对某变量xj没有非负限制，则引进两个非负变量xj0， x0，令xjxjx，代入约束条件和目标函数中，化为对全部变量都有非负限制。由此，线性规划的标准形式为： 式中，A为矩阵，b,c,x均为向量：我们把满足所有约束条件的一组值称为线性规划的可行解。所有可行解构成的集合称作可行解集，由于一般线性规划问题的可行解集构成n维空间的区域,因此可行解集也称作可行域。在所有的可行解中，使目标函数取得最大值或最小值的可行解称为线性规划问题的最优解。对应的目标函数的取值称为最优值。线性规划的运算方法很多，如图解法、表上作业法、图上作业法、匈牙利等等。其中最常用的是单纯形法。EXCEL的规划求解功能就是按单纯形法设计的。单纯形算法的原理是：从一个原始可行解x=(0,0,0,0)开始，每迭代一次确定一个新的基本可行解（从可行解集合的一个顶点转移到别一个顶点），使得目标函数值严格增加，经过有限次迭代，算法最后终止于一个最优基本解。一、运输问题一般地，设某种物资有m个产地：A1，A2，Am，联合供应n个销地：B1，B2，Bn。产地产量、各销地销量、各产地到销地单位运价如表3：表3运输问题规划求解表销地产地B1，B2，Bm产量（千克）A1A2AmC11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmna1 a2am销量（千克）b1 b2 bn表中：ai表示产地Ai的产量（i1，2，m）；bj表示销地Bj的销量（j1，1，n）；Cij表示AiBj的单位运价（元千克）（i1，2，m；j1，2，n）。假定产销平衡（aibj）。设xij表示由产地Ai运往销地Bj的物资数量，那么，上述运输问题的数学模型为：（）已知数据：cij、ai、bj均为常数；（）决策变量：xij；（）目标函数：min Sc11x11+c12x12+cmnxmn （）约束条件：如果在运输问题中，没有产销平衡这一限制，当产大于销（aibj）时，这一问题的数学模型为：（）已知数据：cij、ai、bj均为常数 ；（）决策变量：xij；（）目标函数：min （）约束条件：【例1】假定有某种物资要从、三个产地运到甲、乙、两、丁四个销地。三个产地的供应量分别为：1000t、800t、500t；四个销地的需要量分别为：500t、700t、800t、300t，各产地和销地之间每吨产品的运费如下表所示，要求计算如何组织运输才能运费最省？表4运费表销地甲销地乙销地丙销地丁产地1520330产地781420产地C1232025【解】利用EXCEL进行规划求解，具体步骤如下：第一步，建立模型（）已知数据：cij、ai、bj均为常数。其中cij为运费矩阵；ai为供应量，bj为需求量；（）决策变量：xij；（）目标函数：min Sc11x11+c12x12+cmnxmn 约束条件为：第二步，在xcel中建立工作表，并在可变单元格和目标单元格之间建立函数关系，如下：B11=B8+B9+B10，并复制到C11:E11； F8=B8+C8+D8+E8，并复制到F8:F10；F11=cx=SUMPRODUCT(B2:E4,B8:E10)。SUMPRODUCT( )为数组间对应元素乘积之和。图 物资调运运费最小计算表第三步，应用规划求解工具求解。在【设置目标单元格】填入$F$11；在【等于】点击“最小值”；在【可变单元格】输入B8:E10；并根据要求“添加”约束条件。约束条件：B8:E10；B11=500、C11=700、D11=800、E11=300；F8=1000、F9=800、F10=500。最后点击“求解”。 图 物资调运运费最小规划求解表点击“保存规划求解结果”，并“确定”。 图 规划解结果 图 物资调运运费最小计算结果表 最后，得到目标函数值为：16600元；运量安排见图1中的B8:E10。第四步，进行信息分析（主要是敏感性分析，在后面进行重点介绍）。【例】有两个煤厂、B，每月分别进煤 60吨、100吨。它们担负供应三个居民区用煤任务。这三个居民区每月需用煤分别为45吨、75吨、40吨。A厂离这三个居民区分别为10公里、5公里、6公里，B厂离这三个居民区分别为4公里、8公里、15公里。问这两煤厂如何分配供煤，才使运输量最小。【解】第一步，建立模型（）已知数据：cij为煤厂至居民区的距离即:；ai60,100为供应量；bi=45,75,40为需求量。（）决策变量：xij为运输数，即：。 （）目标函数：min Sc11x11+c12x12+cmnxmn （）约束条件： 第二步，在xcel中建立工作表，并在可变单元格和目标单元格之间建立函数关系，如下：E6 =B6+C6+D6，并复制到E7； B8 =B6+B7，并复制到C8:D0；E8=cx=SUMPRODUCT(B2:D3,B6:D7)。SUMPRODUCT( )为数组间对应元素乘积之和。第三步，规划求解 图 规划求解结果表二、布局问题设有n个地区A1，A2，An，在某一个计划期内，Ai生产某种原料ai吨，同时需要用这种原料加工的某种产品bi吨(i=1，2，n），已知k吨原料可制造1吨该产品。设这n个地区所产原料的总数恰好能生产各地区所需该产品的总数，即。 另外已知在Ai设厂加工该产品的加工费为每吨di元。在Ai设厂生产该产品数最多为ei吨，最少为fi吨（i=1,2，n）。从Ai运原料或产品到Aj（i，j=l，2，n）每吨运价为cij元。问应在何地设厂，生产多少该产品，才能既满足需要，又使生产费用（包括原料和产品运费、产品加工费）最少？在此，设Xij表示由Ai运到Aj的原料数（单位：吨）（i，j=1，2，n），其中j=i时表示Ai留用数；yij表示由Aj运到Ai的成品数（单位：吨）（i，j=l，2，n），其中j=i时，表示 Ai留用数；Zi表示Ai设厂的年产成品数（单位；吨）(i=1，2，n)。表5布局问题规划求解表A1A2AnA1A2An生产原料数生产成品数加工费A1c11c12c1nA2c21c22c2nAncn1cn2cnnA1x11x12x1ny11y12y1na1f1z1e1d1A1x21x22x2ny21y22y2na2f2z2e2d2Anxn1xn2xnnyn1yn2ynnanfnznendn需成品数b1b1bn需原料数kz1kz2kzn 因此，其数学模型如下：（）已知数据：cij、ai、bj、di均为常数；（）决策变量：xij、yij、zi；（）目标函数：min 约束条件 【例】设有某种原料产地Al，A，A，把这种原料经过加工，制成成品，再运往销地。假设用4吨原料可制成1吨成品。产地A年产原料30万吨，同时需要成品7万吨。产地A年产26万吨，同时需要成品13万吨。产地A年产24万吨，不需成品。A与A间距离150公里，A与A间距离100公里，A与A间距离200公里。又知原料运费为 03万元万吨公里，成品运费为 025万元万吨。且知在开设加工厂加工费为055万元万吨，在A为 04万元万吨，在A为 03万元万吨。因条件限制，在设厂规模不能超过年产成品5万吨，A和A可以不限制。问应在何地设厂，生产多少成品，才能使生产费用（包括原料运费、成品运费、加工费等）为最小。【解】第一步，建立数学模型（）已知数据：cij(i=1,2,3;j=1,2,3)为原材料运费即：；cij(i=1,2,3;j=4,5,6)为成品运费即E2：G3；ai30，26，24为生产原材料数；bi=7，13，0为成品需求量；k=4,即4吨原材料可生产1吨成品；d=0.55，0.4，0.3为加工费。（）决策变量： xij、yij、zi；（）目标函数：min （4）约束条件第二步，在xcel中建立工作表，并在可变单元格和目标单元格之间建立函数关系，如下： 1.工作表并输入有关数据H5=B5+C5+D5,并复制到H6:H7上； E8=E5+E7+E7, 并复制到F8:G8上; I5=E5+F5+G5, 并复制到I6:I7上;B9=B5+B6+B7, 并复制到C9:D9上;2.名称 :定义为“原料运费； :定义为“xij；E:G定义为“成品运费；5:定义为“Yij”；I9=SUMPRODUCT(原料运费,_xij)+SUMPRODUCT(成品运费,_yij)+I5*J5+I6*J6+I7*J7； 图6 建立规划求解工作表第三步，规划求解 目标单元格：I；等于“最小值”； 可变单元格：，：，：。 约束条件：，：； ； ； 4*I5;C9=4*I6;D9=4*I7. 图7 选择规划求解参数 三、分派问题 设有n件工作Bl，B，Bn分派给n人Al，A2，An去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为cij（i，j=1，2，n）。问应如何分派才使完成全部工作的总工时最少。 显然，设xij为Bj分派给Ai的情况:Bj分派给Ai时，xij=1;不分派给Ai时，xij=0（i，j=1，2，n）。那末这一问题的数学模型为：（）数据：cij、ai、bj均为已知常数；（）决策变量：xij；（）目标函数： （）约束条件： 【例4】将6项不同的工作分配给6个人去做，每个人都有能力完成其中的任何一项工作，但效率的高低不同。现将每人完成各项工作所需要的时间如图8所示，请提出6个人完成6项工作总的花费时间达到最少的方案。【解】这个分派问题是整数线性规划问题。通过求解的基本步骤为：第一步，建立模型设Ai为完成工作的人员；Bi为工作任务；cij为Ai完成 Bi所需要的时间。xij为Bi分配给Ai的情况。但xij1，xij=1或0。cijxij的值最小。（）数据：cij、ai、bj均为已知常数；（）决策变量：xij；（）目标函数： （）约束条件： 第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系（1）建立工作表；（2）H=B+C+D+E+F+G，并复制到H1：H1；（3）B15=B9+B10+B11+B12+B13+B14，并复制到C15：G15；（4）H15=SUMPRODUCT(B2:G7,B9:G14)。第三步，规划求解点击“规划求解”。选择“目标单格”即H15；等于“最小值”；可变单格为：B9:G14；约束条件为：B9:G140，B9:G14整数；H9:H141；B15:G151。求解得出结果。 图8 规划求解结果表四、生产组织与计划问题设用Al，A2，An种原料，可生产Bl，B2，Bn种产品。现有原料数(ai)、每单位产品所需原料数(cij)，及每单位产品可得利润数(bj)如表6。如何通过组织生产使利润最大。表6生产计划问题规划求解表产品原料B1，B2，Bm现有原料A1A2AmC11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmna1 a2am单位产品利润b1 b2 bn这一问题的数学模型为：（）数据：cij、ai、bj均为已知常数；（）决策变量：xij(i=1,2,m;j=1,2,n);（）目标函数： （）约束条件： 【例】某木器厂生产圆桌和衣柜两种产品。现有两种木料，第一种有 72立方米，第二种有 56立方米。假设生产每种产品都需要用两种木料。生产一只圆桌和一个衣柜所需木料如下表所示。每生产一只圆桌可获利润6元；生产一个衣柜可获利润10元。木器厂在现有木料条件下，圆桌和衣柜应各生产多少，才使获得利润最多。表7产品用材料数表产品木料（单位：立方米）第一种第二种圆桌衣柜0.180.090.080.28【解】第一步，建立模型cij为生产一只圆桌和一个衣柜所需木料， xj为生产圆桌、衣柜的数量；ai为可使用的木料量；bj为单位产品利润，目标函数maxzxjbj。这一问题的数学模型为：（）数据：cij、ai、bj均为已知；（）决策变量：xij(i=1,2,m;j=1,2,n);（）目标函数： （）约束条件：第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系B6=$B$9*B2，并复制到B7；C6=$C$9*C2，并复制到C7；E6=B6+C6,并复制到E7:E9；B10=B8*B9，并复制到C10；E10=B10+C10.第三步，规划求解 目标单元格：；等于“最大值”；可变单元格：:。 约束条件：:0,E672,E756。图9 规划求解结果表五、合理下料问题 设用某原材料（条村或板材）下零件Al，A2，An的毛坯。根据过去经验在一件原材料上有B1，B2，Bn种不同的下料方式，每种下料方式可得各种毛坯个数及每种零件需要量如表8所示。问应怎样安排下料方式，使得既能满足需要，用的原材料又最少。表8下料问题规划求解表 下料方式零件B1，B2，Bm零件需要量A1A2AmC11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmna1 a2am这一问题的数学模型为：（）数据：cij为各种方式下的零件个数： cij、ai均为已知常数；（）决策变量：xj(j=1,2,n);（）目标函数： （）约束条件： 【例】某工地要将7.3m长的圆钢截成2.9m长的毛坯200根、2.1m长的毛坯306根、1.5m长的毛坯92根。现有8种下料方法，每种方法截出各种毛坯的根数和残料的长度如图10，问怎样截法，才使所用的原材料最少。 图10 下料问题数据表【解】第一步，建立模型（）数据：cij为各种方式下的零件个数： cij、ai均为已知常数；（）决策变量：xj(j=1,2,n);（）目标函数： （）约束条件：第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系B7=$B$10*B2,并复制到B8:B9；C7=$C$10*C2,并复制到C8:C9；D7=$D$10*D2,并复制到D8:D9；E7=$E$10*E2,并复制到E8:E9；F7=$F$10*F2,并复制到F8:F9；J7=SUM(B7*H7),并复制到J8:J10； 图1 规划求解结果表第三步，规划求解 目标单元格：J；等于“最小值”；可变单元格：。 约束条件：J7K7; J8K8; J9K9。六、配料问题设用n种原料B1,B2，Bn制成具有m种成分A1，A2，Am的产品，其所含各成分需要量分别不低于a1，a2，am。各种原料的单价，以及各种原料所含成分的数量如表9所示。问应如何配料，才使产品成本最低。表9配料问题规划求解表原料成分名称B1，B2，Bm产品所含成分需要量A1A2AmC11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmna1 a2am单价b1 b2 bn这一问题的数学模型为：（）数据：cij为一单位原料所含成分的数量； cij、ai、bj均为已知常数；（）决策变量：xj(j=1,2,n);（）目标函数： （）约束条件： 【例】某铝金厂生产某种铝合金，拟从、种原料中选择搭配与铝熔合成。各种原料的主要化学成分和杂质的含量（i）（）、含量限制（）与进料价格如表10，要求规划求解找到合理配方，使原料成本达到最低。 表10 某种铝合金用料化学成分与进料价格表 1 各种原料产品所含成分限量2B1B2B3B4B53A10.06870 0.05142 0.04500 0.00220 0.97000 0.1170.11574A20.00500 0.01878 0.02700 0.00015 0 0.01930.02135A30.02050 0.00408 0.01200 0.00300 0.01000 0.00900 6A40.00250 0.00150 0.01300 0 0 0.01000 7A50.00108 0.00189 0.00170 0 0 0.00300 8A60.00250 0.00431 0.00300 0 0 0.00500 9A70.00084 0.00050 0.00128 0 0 0.00300 10A80.00100 0.00100 0.00200 0 0 0.00300 11单价2.71.9【解】第一步，建立数学模型设cij为一单位原料所含成分的数量；ai为含量限制、bj为单价。（）数据：cij为一单位原料所含成分的数量； cij、ai、bj均为已知常数；（）决策变量：xj(j=1,2,n);（）目标函数： （）约束条件：第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系 (1) B14$B$22*B3,并复制到B15:B21;(2) C14$C$22*C3,并复制到C15:C21;(3) D14$D$22*D3,并复制到D15:D21;(4) E14$E$22*E3,并复制到E15:E21;(5) F14$F$22*F3,并复制到F15:F21;建立总含量的函数：14（：）,并复制到15:21;建立成本函数关系：422*3,并复制到15:21;第三步，规划求解目标单元格G24（ ）；等于“最小值”。约束条件： 图2 规划求解结果表第三节 对偶问题与影子价格 一、对偶线性规划问题（一） 对偶概念每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。我们把线性规划问题（）Min s= c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2+ a1n xn b1 a21x1 + a22 x2 + a2n xn b2 ak1 x1 + ak2 x2 + + akn xn bk x1 ，x2 ， ，xn 0称为原始问题，则把() Max g= b1 y1 + b2 y2 + + bn yn s.t. a11 y1 + a21 y2+ am1 ym c1 a12y1 + a22 y2 + am2 ym c2 a1n y1 + a2n y2 + + amn ym cn y1 ，y2 ， ，ym 0称为对偶的线性问题，反过来说也一样。线性规划问题（）和（）用矩阵表示则为：（）Min s= c x () Max g= y b 显然，原始问题与其对偶问题的构造法则如下：一个问题求极小，另一个问题求极大；极小问题中有“”约束，对偶问题有“”约束；原始问题中有一个变量，对偶问题中就对应着有一个不等式约束；原始问题中的目标函数变量的系数，正是对偶问题约束条件的常数项；两个互为对偶问题的约束条件的系数矩阵是互为转置矩阵。（二）基本定理【定理1】如果线性规划问题（）中第k个约束条件是等式，那么它的对偶规划（）中的第k个变量yk无非负限制，反之也然。【定理2】如果设X、Y分别互为对偶线性规划问题（）和（）的可行解，那么它们对应的目标函数值间的关系是：SG，即（）的最小目标函数值也不小于（）的最大的目标函数值。【定理3】设X*、Y*分别是互为对偶线性规划问题（）和（）的可行解，当cX*=Y*b时，X*、Y*是（）和（）的最优解。【定理4】若原始问题有最优解，那么对偶问题也有最优解，且目标函数值相待。（三）影子价格在线性规划问题中约束条件常数项增加一个单位而产生的目标函数最优值的变化。如果约束条件常数项表示资源，目标函数表示最优收益，则影子价格是指资源增加对最优收益发生的影响，因此，影子价格是指一种经济结构中的有限资源在最优规划中的边际价值。实际上，对偶问题的最优解就是原始问题的影子价格。【例8】假如某种作物，全部生产过程中至少需要氮肥32公斤、磷肥24公斤、钾肥42公斤。已知甲、乙、丙、丁四种复合肥料，每公斤的价格，及含氮、磷、钾的数量，如表11所示。问应如何配合使用这些肥料，既能满足作物的需要，又能使成本最低？ 表11 四种复合肥料成分含量及价格表甲乙丙丁肥料需要量bi氮0.030.300.1532磷0.0500.20.124钾0.14000.0742价格0.03【解】 、求原始问题的最优解第一步，建立数学模型(1)已知数据：aij为四种复合肥料含氮、磷、钾的成分；cj为价格；bi为肥料需要量。(2)决策变量；xj为肥料使用量。(3)Min s= c x 第二步，建立工作表及可变单元格与目标单元格之间的函数关系 图3 原始问题规划求解结果表B7=$B$10*B2,并复制到B8:B9；C7=$C$10*C2,并复制到C8:C9；D7=$D$10*D2,并复制到D8:D9；E7=$E$10*E2,并复制到E8:E9；B12=B10*B11 ,并复制到C8:E9；F7=B7+C7+D7+E7,并复制到F8:F9；F12=B12+C12+D12+E12。第三步，规划求解目标单元格：F12；等于“最小值”；可变单元格：B10：E10；约束条件：B10：E10，F7：F9G7：G9。、求对偶问题的最优解第一步，建立数学模型这一对偶问题可以解释为，某肥料公司计划生产氮、磷、钾三种单成分肥料，肥料公司要为这三种肥料确定价格（y1、y2、y3）既要获得最大利润，同时又要与生产甲、乙、丙、丁四种复合肥料的公司竞争。因此，必须设想以成分化肥氮、磷、钾合成的甲、乙、丙、丁四种复合肥料的价格，即：yAc。第二步，建立工作表及可变单元格与目标单元格之间的函数关系复制原始问题规划求解表中的“A1：G5”，通过“选择性粘贴”（转置）建立以下工作表，并建立工作表有关单元格之间的函数关系。图4 选择性粘贴或转置B8=$B$12*B2,并复制到B9:B11；C8=$C$12*C2,并复制到C9:C11；D8=$D$12*D2,并复制到D9:D11；E8=$E$12*E2,并复制到E9:E11；B14=B12*B13 ,并复制到C14:D9；F8=B8+C8+D8,并复制到F9:F11；E14=B14+C14+D14.。第三步，规划求解目标单元格：F14；等于“最大值”；可变单元格：B12:D12；约束条件：B12:D12，E8:E11F8:F11。 图5 对偶问题规划求解结果表第四节线性规划的敏感度分析 我们在前文所讨论的线性规划问题，假定各项参数（cij、ai、bj）都是已知的常数。但在实际生活中，这些参数是经常变动的。然而，这些参数发生变动时，已求得的最优解会不会发生变化。或者说，在已取得的最优解的情况下，参数可以在多大幅度内变动。分析参数变动对最优解的影响程度，就是敏感度分析。在线性规划中参数可能发生变动的情况有：（1）目标函数系数（cij）的变动；（2）约束条件中常数项的变动；（3）添加新的变量；（4）添加新约束条件。如果用人工使用单纯形法进行分析是十分复杂的。而用EXCEL中“规划求解”工具进行运算就十分方便容易。当然，在EXCEL工作表中还可使用其他的方法。在这里，我们只介绍“规划求解”工具中的“敏感性报告”及其分析方法。【例9】甲工厂可以生产A、B、C三种产品，已知每生产1单位的A产品需要材料费用2元，占用劳动力6人，耗电5度，盈利4元；每生产1单位的B产品需要材料费用25元，占用劳动力1人，耗电5度，盈利6元；每生产1单位的C产品需要材料费用4元，占用劳动力8人，耗电10度，盈利10元。该厂现有劳动力640人，每天的材料费用为320元，每天电力只有750度。那么，该厂每天生产A、B、C产品各多少单位才能获得利润最大，并求其影子价格。【解】这也是一个线性规划问题。但与例8有一定区别。这里原始问题是求最