目录
1.关于“规划求解”
2.如何加载“规划求解”
3.“规划求解”各参数解释和设置
4.“规划求解”的步骤
5.“规划求解”疑难解答
6.利用“规划求解”解线性规划问题
7.利用“规划求解”解整数规划问题
8.利用“规划求解”解目标规划问题
9.利用“规划求解”解运输问题
10.利用“规划求解”解最短路径问题
11.利用“规划求解”解最大流问题
12.利用“规划求解”解数据包络分析（DEA）问题
13.利用“规划求解”解其他运筹学问题
1、关于“规划求解”
“规划求解”是Excel中的一个加载宏，借助“规划求解”，可求
得工作表上某个单元格（被称为目标单元格）中公式（公式：单元
格中的一系列值、单元格引用、名称或运算符的组合，可生成新的值。
公式总是以等号(=)开始。）的最优值。“规划求解”将对直接或间
接与目标单元格中公式相关联的一组单元格中的数值进行调整，最终
在目标单元格公式中求得期望的结果。“规划求解”通过调整所指定
的可更改的单元格（可变单元格）中的值，从目标单元格公式中求得
所需的结果。在创建模型过程中，可以对“规划求解”模型中的可变
单元格数值应用约束条件（约束条件：“规划求解”中设置的限制条
件。可以将约束条件应用于可变单元格、目标单元格或其他与目标单
元格直接或间接相关的单元格。而且约束条件可以引用其他影响目标
单元格公式的单元格。使用“规划求解”可通过更改其他单元格来确
定某个单元格的最大值或最小值。
MicrosoftExcel的“规划求解”工具取自德克萨斯大学奥斯汀分
校的LeonLasdon和克里夫兰州立大学的AllanWaren共同开发的
GeneralizedReducedGradient(GRG2)非线性最优化代码。线性和整
数规划问题取自FrontlineSystems公司的JohnWatson和Dan
Fylstra提供的有界变量单纯形法和分支边界法。
2、如何加载“规划求解”
安装office的时候，系统默认的安装方式不会安装宏程序，需要
用户根据自己的需求选择安装。
下面是加载“规划求解”宏的步骤：
1)在“工具”菜单上，单击“加载宏”。
2)在弹出的对话框中的“可用加载宏”列表框中，选定待添加的加
载宏“规划求解”选项旁的复选框，然后单击“确定”。单击“确
定”以后，“工具”菜单下就会出现一项“规划求解”。如果需要
其他功能，也可以用鼠标勾选。提醒一句，加载的宏越多，excel
启动的时候就会越慢，所以请根据自己的需要选择。
3)如果要卸载已经加载的宏，请在“可用加载宏”列表框中，选定
待添加的加载宏选项旁的复选框，然后单击“确定”。
3、“规划求解”各参数解释和设置
单击“规划求解”按钮，将会出现以下的规划求解参数的对话框。
设置目标单元格：一些单元格、具体数值、运算符号的组合。注
意：目标单元格一定要是公式，即一定是以“=”开始。类似于线
性规划中的目标函数。
最大值、最小值：在此指定是否希望目标单元格为最大值、最小
值或某一特定数值。如果需要指定数值，请在右侧编辑框中键入
该值。
可变单元格：在此指定可变单元格。求解时其中的数值不断调整，
直到满足约束条件并且“设置目标单元格”框中指定的单元格达
到目标值。可变单元格必须直接或间接地与目标单元格相关联。
类似于线性规划中的变量。
推测：单击此按钮，自动推测“设置目标单元格”框中的公式所
引用的所有非公式单元格，并在“可变单元格”框中定位这些单
元格的引用。
约束：在此列出了规划求解的所有约束条件。
添加：显示“添加约束”对话框。
更改：显示“更改约束”对话框。注意：单击此按钮的时候，要
先选择需要更改的约束。
删除：删除选定的约束条件。同样单击此按钮前，要先选择需要
删除的约束。
求解：对定义好的问题进行求解。
关闭：关闭对话框，不进行规划求解。但保留通过“选项”、“添
加”、“更改”或“删除”按钮所做的更改。也就是说，当你下次
再次单击“规划求解”按钮后，对话框显示上回所设置的参数。
选项：显示“规划求解选项”对话框。在其中可加载或保存规划
求解模型，并对求解过程的高级属性进行控制。
最长运算时间：在此设定求解过程的时间。可输入的最大值为
32767（秒），默认值100（秒）可以满足大多数小型规划求解
要求。
迭代次数：在此设定求解过程中迭代运算的次数，限制求解过
程的时间。可输入的最大值为32767，默认值100次可满足
大多数小型规划求解要求。
精度：在此输入用于控制求解精度的数字，以确定约束条件单
元格中的数值是否满足目标值或上下限。精度值必须表示为小
数（0到1之间），输入数字的小数位越多，精度越高。例如，
0.0001比0.01的精度高。
允许误差：在此输入满足整数约束条件并可被接受的目标单元
格求解结果与真实的最佳结果间的百分偏差。这个选项只应用
于具有整数约束条件的问题。设置的允许误差值越大，求解过
程就越快。
收敛度：在此输入收敛度数值，当最近五次迭代后目标单元格
中数值的变化小于“收敛度”框中设置的数值时，“规划求解”
停止运行。收敛度只应用于非线性规划求解问题，并且必须表
示为小数（0到1之间）。设置的数值越小，收敛度就越高。
例如，0.0001表示比0.01更小的相对差别。收敛度越小，“规
划求解”得到结果所需的时间就越长。
采用线性模型：当模型中的所有关系都是线性的，并且希望解
决线性优化问题时，选中此复选框可加速求解进程。
显示迭代结果：如果选中此复选框，每进行一次迭代后都将中
断“规划求解”，并显示当前的迭代结果。
自动按比例缩放：如果选中此复选框，当输入和输出值量级差
别很大时，可自动按比例缩放数值。例如，基于百万美元的投
资将利润百分比最大化。
假定非负：如果选中此复选框，则对于在“添加约束”对话框
的“约束值”框中没有设置下限的所有可变单元格，假定其下
限为0（零）。
估计：指定在每个一维搜索中用来得到基本变量初始估计值的
逼近方案。
正切函数：使用正切向量线性外推
二次方程：用二次方程外推法，提高非线性规划问题的计算精
度。
导数：指定用于估计目标函数和约束函数偏导数的差分方案。
向前差分：用于大多数约束条件数值变化相对缓慢的问题。
中心差分：用于约束条件变化迅速，特别是接近限定值的问题。
虽然此选项要求更多的计算，但在“规划求解”不能返回有效
解时也许会有帮助。
搜索：指定每次的迭代算法，以确定搜索方向。
牛顿法：用准牛顿法迭代需要的内存比共轭法多，但所需的迭
代次数少。
共轭法：比牛顿法需要的内存少，但要达到指定精度需要较多
次的迭代运算。当问题较大和内存有限，或步进迭代进程缓慢
时，可用此选项。
装入模型：显示“装入模型”对话框，输入对所要加载的模型
的引用。
保存模型：显示“保存模型”对话框，在其中可指定保存模型
的位置。只有需要在工作表上保存多个模型时，才单击此命令。
第一个模型会自动保存。
4、“规划求解”的步骤
1)首先在表格上建立模型，然后单击“规划求解”按钮，出
现“规划求解参数”的对话框。
2)在“设置目标单元格”框中，输入目标单元格的单元格引
用（单元格引用：用于表示单元格在工作表上所处位置的
坐标集。例如，显示在第B列和第3行交叉处的单元格，
其引用形式为“B3”。）或名称（名称：代表单元格、单
元格区域、公式或常量值的单词或字符串。名称更易于理
解，例如，“产品”可以引用难于理解的区域
“Sales!C20:C30”。）。目标单元格必须包含公式（公式：
单元格中的一系列值、单元格引用、名称或运算符的组合，
可生成新的值。公式总是以等号(=)开始。）。可以单击
选择单元格。
3)若要使目标单元格中数值最大，请单击“最大值”。若要
使目标单元格中数值最小，请单击“最小值”。若要使目标
单元格中数值为确定值，请单击“值为”，再在编辑框中键
入数值。
4)在“可变单元格”框中，输入每个可变单元格的名称或引
用，用逗号分隔不相邻的引用。可变单元格必须直接或间
接与目标单元格相联系。最多可以指定200个可变单元
格。若要使“规划求解”基于目标单元格自动设定可变单
元格，请单击“推测”。
5)在“规划求解参数”对话框的“约束”下，单击“添加”。
6)在“单元格引用位置”框中，输入需要对其中数值进行约
束的单元格引用（单元格引用：用于表示单元格在工作表
上所处位置的坐标集。例如，显示在第B列和第3行交
叉处的单元格，其引用形式为“B3”。）或单元格区域的名
称（名称：代表单元格、单元格区域、公式或常量值的单
词或字符串。名称更易于理解，例如，“产品”可以引用难
于理解的区域“Sales!C20:C30”。）。
7)单击希望在引用单元格和约束条件（约束条件：“规划求
解”中设置的限制条件。可以将约束条件应用于可变单元
格、目标单元格或其他与目标单元格直接或间接相关的单
元格。）之间使用的关系（“<=”、“=”、“>=”、“Int”或“Bin”）。
如果单击“Int”，则“约束值”框中会显示“整数”；如果
单击“Bin”，则“约束值”框中会显示“二进制”。
8)在“约束值”框中，键入数字、单元格引用或名称，或键
入公式（公式：单元格中的一系列值、单元格引用、名称
或运算符的组合，可生成新的值。公式总是以等号(=)开
始。）。
9)若要接受约束条件并要添加其他的约束条件，请单击“添
加”。若要接受约束条件并返回“规划求解参数”对话框，
请单击“确定”。
10)注意：只能在对可变单元格的约束条件中应用“Int”和“Bin”
关系。当“规划求解选项”对话框中的“采用线性模型”
复选框被选中时，对约束条件的数量没有限制。对于非线
性问题，每个可变单元格除了变量的范围和整数限制外，
还可以有多达100个约束。
11)更改或者删除约束。在“规划求解参数”对话框的“约束”
下，单击要更改或删除的约束条件（约束条件：“规划求
解”中设置的限制条件。可以将约束条件应用于可变单元
格、目标单元格或其他与目标单元格直接或间接相关的单
元格。）。单击“更改”，并进行所需的更改，或单击“删除”。
12)单击“求解”，再执行下列操作之一：若要在工作表中保
存求解后的数值，请在“规划求解结果”对话框中，单击
“保存规划求解结果”；若要恢复原始数据，请单击“恢复
为原值”。注意：按Esc可以中止求解过程，Microsoft
Excel将按最后找到的可变单元格的数值重新计算工作
表。若求出解,请在“报告”框中单击一种报表类型，再单
击“确定”。报表保存在工作簿中新生成的工作表上。
5、“规划求解”疑难解答
尚未找到满足要求的结果，“规划求解”即停止了运行。
由于下列任意一个原因，“规划求解”在找到答案前，可能停止
运行：
中断了求解过程。
在单击“求解”之前，选中了“规划求解选项”对话框中的“显
示迭代结果”选项。
在单步迭代过程中，或达到最长运算时间或最大迭代次数时，
单击了“停止”按钮。
选中了“规划求解选项”对话框中的“采用线性模型”复选框，
但问题是非线性的。
在“规划求解参数”对话框的“设置目标单元格”框中指定的
数值不收敛地增加或减少。
需要让“规划求解”运行更长的时间以求得结果。请调整“规
划求解选项”对话框中的“最长运算时间”或“迭代次数”的
设置。
对于具有整数约束条件的问题，应该减小“规划求解选项”对
话框中的“允许误差”的设置，使“规划求解”找到更好的整
数解。
对于非线性问题，应该减小“规划求解选项”对话框中的“收
敛度”的设置，使目标单元格数值变化缓慢时，“规划求解”
仍可以运行，最终找到较好的结果。
应该选中“规划求解选项”对话框中的“自动按比例缩放”复
选框，可能一些输入数值相差几个数量级，或输入和输出数值
相差几个数量级。
当“规划求解”停止运行时，在“规划求解结果”对话框中显
示出完成信息。单击“保存规划求解结果”或“恢复为原值”，
进行所需的更改，然后再运行一次。
可变单元格与约束条件或目标单元格中的数值差别很大。
当可变单元格的典型数值与约束单元格或目标单元格中的数
值相差几个数量级时，请选中“规划求解选项”对话框中的“自
动按比例缩放”复选框。对于非线性问题，在单击“规划求解
参数”对话框中的“求解”之前，请确认可变单元格的初始数
值与期望的最终数值的数量级相同。
未得到预期的结果。
对于非线性问题，在可变单元格中尝试不同的初始值可能会有
帮助，特别是在“规划求解”结果与期望的数值差别很大时。预先将
可变单元格的数值设置为预期的最优值，可以减少求解时间。
对于线性模型（也就是当“规划求解选项”对话框的“采用线
性模型”复选框被选中时），改变可变单元格的初始值不会影响最终
数值或求解时间。
“规划求解”得到的结果与以前的结果不同。
“规划求解”显示如下消息：“规划求解已收敛到当前结果。满
足所有约束条件”。这表明目标单元格中的数值在最近五次求解过程
中的变化量小于“规划求解选项”对话框中“收敛度”设置的值。“收
敛度”中设置的值越小，“规划求解”在计算时就会越精细，但求解
过程将花费更多的时间。
“规划求解”不能达到最优解。
“规划求解”不能改进当前解。所有约束条件都得到了满足。
这表明仅得到近似值，迭代过程无法得到比显示结果更精确
的数值；或是无法进一步提高精度，或是精度值设置得太小，请在
“规划求解选项”对话框中试着设置较大的精度值，然后再运行一
次。
求解达到最长运算时间后停止
这表明在达到最长运算时间限制时，没有得到满意的结果。若
要保存当前结果并节省下次计算的时间，请单击“保存规划求解”
或“保存方案”选项。
求解达到最大迭代次数后停止
这表明在达到最大迭代次数时，没有得到满意的结果。增加迭
代次数也许有用，但是应该先检查结果数值来确定问题的原因。若
要保存当前值并节省下次计算的时间，请单击“保存规划求解”或
“保存方案”选项。
目标单元格中的数值不收敛
这表明即使满足全部约束条件，目标单元格数值也只是有增或
有减但不收敛。这可能是在设置问题时忽略了一项或多项约束条
件。请检查工作表中的当前值，确定数值发散的原因，并且检查约
束条件，然后再次求解。
“规划求解”未找到合适结果
这表明在满足约束条件和精度要求的条件下，“规划求解”无
法得到合理的结果，这可能是约束条件不一致所致。请检查约束条
件公式或类型选择是否有误。
“规划求解”应用户要求而中止
这表明在暂停求解过程之后，或在单步执行规划求解时，单击
了“显示中间结果”对话框中的“停止”。
无法满足设定的“采用线性模型”条件
这表明求解时选中了“采用线性模型”复选框，但是“规划求
解”最后计算结果并不满足线性模型。计算结果对工作表中的公式
无效。若要验证问题是否为非线性的，请选中“自动按比例缩放”
复选框，然后再运行一次。如果又一次出现同样信息，请清除“采
用线性模型”复选框，然后再运行一次。
“规划求解”在目标或约束条件单元格中发现错误值
这表明在最近的一次运算中，一个或多个公式的运算结果有
误。请找到包含错误值的目标单元格或约束条件单元格，更改其中
的公式或内容，以得到合理的运算结果。
还有可能是在“添加约束”或“改变约束”对话框中键入了
无效的名称或公式，或者在“约束”框中直接键入了“integer”或
“binary”。若要将数值约束为整数，请在比较运算符列表中单击
“Int”。若要将数值约束为二进制数，请单击“Bin”。
内存不足以求解问题
MicrosoftExcel无法获得“规划求解”所需的内存。请关闭
一些文件或应用程序，再试一次。
其他的MicrosoftExcel实例正在使用SOLVER.DLL
这表明有多个MicrosoftExcel会话正在运行，其中一个会
话正在使用SOLVER.DLL。SOLVER.DLL同时只能供一个会话使
用。
6、利用“规划求解”解线性规划问题
下面我们以一个例子说明如何在excel建立线性规划模型及求解。
max
z=x
1
-2x
2
+x
3
s.t.x
1
+x
2
+x
3
≤12
2x
1
+x
2
-x
3
≤6
-x
1
+3x
2
≤9
x
1
,x
2
,x
3
≥0
1)在excel上建立线性规划模型，如下图
2)单击“工具”菜单下的“规划求解”，在弹出的“规划求解参数”
对话框中输入各项参数。
3)设置目标单元格和选择最大值。
4)设置可变单元格。
5)添加约束。
x
1
+x
2
+x
3
≤12
2x
1
+x
2
-x
3
≤6
-x
1
+3x
2
≤9
x
1
,x
2
,x
3
≥0
6)参数设置完毕，如下：
7)由于这个例子比较简单，系统默认的选项参数可以满足求解功能，
所以不需要设置“选项”里面的参数。
8)求解结果。点击右面的报告选项，可以生成相应的报告。
全部求解过程结束，请读者自己练习下面的题目：
minz=-2x
1
-x
2
+3x
3
-5x
4
s.tx
1
+2x
2
+4x
3
-x
4
≤6
2x
1
+3x
2
-x
3
+x
4
≤12
x
1
+x
3
+x
4
≤4
x
1
,x
2
,x
3
,x
4
≥0
7、利用“规划求解”解整数规划问题
整数规划在实际的工作中有很广泛的应用。利用“规划求解”功
能求解整数规划的过程和解线性规划的过程差不多，只不过需要设置
变量为整数而已。
仍然以上面的例子为例，看一下如何求解整数规划问题。我们假
设上述问题x1,x2,x3均是整数，我们只需再添加一个约束就行了，如
下图：
求解结果如下：
“规划求解”还可以用来求0-1整数规划问题，即变量都是0或1的
线性规划问题。我们只要在整数规划的基础上再添加两个约束就
可以求解0-1整数规划问题了。令所有变量大于等于0且小于等于
1，并且为整数，实际上就限定了变量只能为0或者1。
下面是一道0-1整数规划的题，请读者自己练习。
123
1234
1234
124
1234
37
.
21
68
535
01
4
Minxxxx
st
xxxx
xxxx
xxx
xxxx
=+?+
?+?≥
?++≥
++≥
=
：
，，，或
答案：x1=1,x2=0,x3=1,x4=1,min=3
8、利用“规划求解”解目标规划问题
目标规划是一种十分有用的多目标规划工具，有着广泛的应用。
目标规划的数学模型实际上就是最小化型的线性规划，可以用单纯型
法求解，既可以用规划求解功能求解。
下面以一个例子求解
1112233432
1211
122
233
-+
12ii
min{p(dd),pd,pd,p(5d3d)}
st.
xxd-d800
5xd-d2500
3xd-d1400
x,x,d,d0(i1,2,3)
?+??++
?+
?+
?+
++
++=
+=
+=
≥=
首先在excel上建模
添加约束
求解
9、利用“规划求解”解运输问题
如下算例，A1、A2、A3为产地，B1、B2、B3、B4为销地，各
个产地的产量和各个销地的销量及从产地运送一单位货品到各个销
地的费用如图所示。我们用excel的“规划求解”功能求解这个运输
问题。
B1B2B3B4产量
A141241116
A22103910
A38511822
销量8141214
1)首先在excel表格上建立运输问题的模型，如图所示。图中绿色部
分是变量，代表从某产地运到某销地的产品数量。各部分的解释
已经标注在图上，不再详述。特别要说明的是用于计算目标值的
函数SUMPRODUCT，它计算的是两个矩阵各个相对应元素乘积
的和。在这里我们要求的运输成本最小，就是所有产地i到销地j
的运输单位成本乘上运量的和最小。
2)添加目标单元格，变量，约束。
约束1：产量
约束2：销量
约束3：变量大于0
最后参数设置如下：
3)求解结果
指派问题，即有n个人和n件事，已知第i人做第j事的费用为
cij，要求确定人和事之间的一一对应指派关系，使完成这n件事的总
费用最少，其实就属于0-1整数规划问题，它的模型和运输问题的模
型基本相同，下面是其中一个模型，请读者自己练习。
B1B2B3B4B5
A14871512
A279171410
A3691287
A46714610
A56912106
B1B2B3B4B5总计
A1001001=
A2-3.6E-101000
A3100-3.6E-108.96E-111=1
A400010
A5-2E-1102E-11011=1
总计11111
11111minz=34
1
10、利用“规划求解”解最短路径问题
有如下的网络图。需要计算从v1点到v8点的最短路经。用excel
求解最短路径的原理是：令变量为0或者1。即如果最短路经通过
v1v2，v2v4.......，则设变量为1，不通过则为0，除起点和终点之外，
每个点的进出权数和是0，起点的进出权数和是1，终点是-1，目标
函数是各边权数和对应变量乘积的和。于是得到一组等式约束，通过
求解可以得到最短路经和最短路程。
在excel上建立模型如下，
添加约束
求解结果
图中变量是1的边就是最短路经通过的边，即
v1v2-----v2v5----v5v7----v7v8,最短路程是15。注意：1E-06表示接近
0，可以看作0，可以通过调节“选项”中的精度一项达到。如把精
度降到0.01就可以得到变量全为0或1。请读者自己调节。
11、利用“规划求解”解最大流问题
（1，1）
在excel上建立模型如下：
添加约束：
最后求解得到最大流为14（请读者自行练习）
12、利用“规划求解”解数据包络分析（DEA）问题
数据包络分析(dataenvelopmentanalysis,DEA)是美国著名运筹
（4，2）
（5，3）
（2，2）
（8，3）
（7，6）
（4，3）
VV
（4，3）
（3，2）
V3
（3，2）
（3，2）
（10，
V
V
V
V5
学家A.Charnes等人以相对效率概念为基础发展起来的一种效率评
价方法。具有单输入单输出的过程或决策单元其效率可简单的定义
为：输出/输入，A.Charnes等人将这种思想推广到具有多输入多输出
生产有效性分析上。对具有多输入多输出的生产过程或决策单元，其
效率可类似定义为：输出项加权和/输入项加权，形成了仅仅依靠分
析生产决策单元(DMU)的投入与产出数据，来评价多输入与多输出决
策单元之间相对有效性的评价体系。这种评价体系以数学规划为工
具，综合分析输入输出数据，通过线性优化得出每个指标的最优权重
及DMU效率的相对指标，据此将所有DMU定级排队，确定相对有
效的DMU，并指出其他DMU非有效的原因和程度。
以上是很苦涩的说法，没有看过专业文献的人很难看懂。下面举
个例子来说，如何评价大学的办学有效性呢？对于大学办学而言，需
要投入的是教师人数、科研经费、校园面积等，产出的有学生人数、
专利数目、论文数目等。但是这些指标的单位不统一，这时候怎么评
估呢？用到的是DEA的线性规划模型。
在DEA中通常称衡量绩效的组织为决策单元（decisionmaking
unit,DMU）,设有n个决策单元（j=1，2，3......），每个决策单元有相
同的m项投入（i=1，2，3......m）和相同的s项产出（r=1，2，3........s）。
用xij表示第j单元的第i项投入，有rij表示第j单元的第r项产出。
现在要衡量某一决策单元的j0是否DEA有效，即是否处在包络线组
成生产前沿面上，为此先构造一个由n个决策单元线性组成的假想决
策单元，这个假想决策单元的第i项投入为且
n
jij
j1
x(i1,2,.....m)λ
=
=
∑
n
jj
j1
1(0)λλ
=
=≥
∑
，决策单元的第r项产出为且
。如果这个假想单元的各项产出均不低于j0决策单元的
各项产出，它的各项投入均低于j0决策单元的各项投入，即有
n
jrj
j1
y(r1,2,.....s)λ
=
=
∑
n
jj
j1
1(0)λλ
=
=≥
∑
n
jrjrj0
j1
n
jijij0
j1
n
jj
j1
minE
ST
yy(r1,2,.....s)
xEx(i1,2,.....m)
1(0)(j1,2,3.....n)
λ
λ
λλ
=
=
=
≥=
≤?=
=≥=
∑
∑
∑
这是一个线性规划模型，求解之后如果E<1,则决策单元j0非决策
DEA有效，否则决策单元j0DEA有效。
例：某银行的4个分理处的投入产出情况如下，确定个分理处是
否DEA有效。
首先确定分理处一的运行是否DEA有效，写出线性规划模型如
下：
1234
1234
1234
1234
1234
1234
j
minE
st
180010008009001800
200350450420200
16001000130015001600
1520212015E
140130120135140E
=1
0(j1,2,3.....n)
λλλλ
λλλλ
λλλλ
λλλλ
λλλλ
λλλλ
λ
+++≥
+++≥
+++≥
+++≤
+++≥
+++
≥=
在excel上建模如下
添加约束
求解得到
E=1
就是说分理处一的运行DEA有效。请读者朋友自行计算其他分理处
的有效性情况。最后只有分理处2运行非DEA有效。
13、利用“规划求解”解其他运筹学问题
运筹学在实际运用中很广泛，比如生产排程、军事物流等，其
实，在实际应用中，很多问题都可以建立运筹学模型，用线性规划求
解，下面举几个例子，希望对读者有所启发。
1.精确重心法求解
学过设施规划的人应该都知道精确重心法，它是设施选址常用
的方法，什么是精确重心法？简单地说，在一个直角坐标系上有若干
个点，已知他们的坐标，要求一点，使这一点到这些点的直线距离之
和最小。
假设有5个点，其坐标分别是（3，1）（5，2）（4，3）（2，4）
（1，5），另外赋予每个点不同的权重1，7，3，3，6。我们用欧几里
德距离计算公式计算两点间的距离。即
5
22
iisis
i=1
minm(xx)(yy)?+?
∑
然后在excel表格上建立模型如上图
添加约束得
求解之后得
即所求点是（3.93，2.98），最短距离是40.65
2、TSP问题
TSP问题是单回路运输问题最为典型的一个模型，全称是
Travelingsalemanproblem,也叫旅行商问题。它是一个典型的NP-hard
问题。Tsp模型可以如下描述：在一个n顶点网格，要求找出一个包含
所有n个顶点的最小耗费的环路。任何一个包含网络中所有n个顶点的
环路被称作一个回路。在旅行商问题中，要设法找到一条最小耗费的
回路。既然回路是包含所有顶点的一个循环，故可以把任何一个点作
为起点（也是终点），这也是tsp模型的一个特点。
Tsp数学模型如下：
顶点间的距离为，
ij
C
mn
ijij
i=1j=1
n
ij
j1
m
ij
i=1
ij
ij
mincx
st.
x1i=1,2,3........
x1j=1,2,3...........
x{0,1}
1ij
x
0ij
=
=
=
=
?
=
?
?
∑∑
∑
∑
变量：
，从到有通路
，从到无通路
中小规模的tsp问题可以用整数规划的方法求解，这也是我们为
什么可以用excel规划求解功能求解它的原因。下面我们通过一个例子
来说明。
例：某公司需要向7个城镇供货，所有货品可以用一辆车一次送
完。8个城市之间有公路直接连接，其距离矩阵如下表，设计一条送
货行驶距离最短的路经使运费最低。
元素v1v2v3v4v5v6
v1-1068715
v2-5201516
v3-1478
v4-412
v5-6
v6-
在excel上建立模型如下，图中黄色部分为变量。
添加约束
注意必须使对角线上的数字为0。
后记
终于完成了，做得很匆忙，其中必定有很多错误，若有
不明白之处，可以来email（jhgk7@163.com）交流。Good
luck!
京华孤客
2005/6/30
|
|
