2024年4月7日发(作者：嬴心怡)

第十三章 运筹学问题的Excel建模及求解

学习运筹学的目的在于学会用运筹学的方法解决实践中的管理问题.注重学

以致用.很多实际问题利用人工计算要经过长时间的艰苦工作才能完成甚至根本

无法求解.但若使用运筹学软件则瞬间就能解决.因此在学习过程中不仅要掌握

运筹学的基本理论和计算方法.还要充分利用现代化的手段和技术.

微软的电子表格软件（Microsoft Excel）为展示和分析许多运筹学问题提

供了一个功能强大而直观的工具.它现在已经被应用于管理实践中.

本章将重点介绍如何建立和求解规划问题的电子表格模型.对于解决大量的

中、小规模的实际规划问题.电子表格软件是远远优于传统的代数算法的.

第一节 Excel中的规划求解工具

本节中.我们将举例说明如何使用微软Excel以电子表格的形式建立线性规

划模型.并利用Excel中的规划求解工具对模型求解.

一、在Excel中加载规划求解工具

要使用Excel应首先安装Microsoft

Office.然后从屏幕左下角的[开始]—

[程序]中找到Microsoft Excel并启动.

在Excel的主菜单中点击[工具]—[加载

宏].选择“规划求解”.如图13-1所示.

点击[确定]后.在工具菜单中将增加[规

划求解]选项.

图 13-1

二、在Excel中建立线性规划模型

我们以例2-1为例说明如何在电子表格中建立该问题的线性规划模型.建立

电子表格模型时既可以直接利用问题中所给的数据和信息.也可以利用已建立的

代数模型.本例的代数模型为：

. .

目标函数

max Z200x

1

300x

2



2x

1

2x

2

12



x2x8

12





s.t.



4x

1

16



4x12

2







x

1

,x

2

0

图 13-2

图 13-3

图13-2显示了将该例的数据转送到电子表格中后所建立的电子表格数学模

型（本例是一个线性规划模型）.其中显示数据的单元格称为数据单元格.包括生

产每单位药品Ⅰ和Ⅱ所需要的4种设备的台时数（单元格C5：D8）.药品Ⅰ和Ⅱ

的单位利润（单元格C9：D9）.4种设备可用的台时数（单元格G5：G8）.

我们要做的决策是两种药品各生产多少；对这一决策的约束条件是生产两种

药品所需的4种设备台时的限制；判断这些决策的优劣程度的指标是生产这两种

药品所获得的总利润（决策目标）.

如图13-3所示.将决策变量（药品Ⅰ、Ⅱ的产量）分别放入单元格C10和

D10.正好在两种药品所在列的数据单元格的下面.由于不知道这些产量会是多少.

故在图13-3中均设为零（空白的单元格默认取值为零.实际上.除负值外的任何

一个试验解都可以）.以后在寻找产量最佳组合时这些数值会被改变.因此.含有

需要做出决策的单元格称为可变单元格.

两种药品所需的4种设备台时总数分别放入单元格E5至E8.正好在对应数

据单元格的右边.由于所需的各种设备台时总数取决两种药品的实际产量.如：

E5=C5×C10+D5×D10（可直接将公式写入E5.也可利用SUMPRODUCT 函

数.E5=SUMPRODUCT（C5：D5.C10：D10）.此函数可以计算若干维数相同的数组的

彼此对应元素乘积之和）.因此当产量为零时所需各种设备台时的总数也为零.

由于E5至E8单元格每个都给出了依赖于可变单元格（C10和D10）的输出结果.

它们因此被称为输出单元格.作为输出单元格的结果.4种设备台时数的总需求

. .

量不应超过其可用台时数的限制.所以用F列中的



来表示.

两种药品的总利润作为决策目标进入单元格E9.正好位于用来帮助计算总

利润的数据单元格的右边.类似于E列的其他输出单元格.E9 = C9×C10+D9×D10

或E9 = SUMPRODUCT（C9：D9.C10：D10）.由于它是在对产量做出决策时目标值

定为尽可能大的特殊单元格.所以被称为目标单元格.

根据对上述建模过程的总结.在电子表格中建立线性规划模型的步骤可归纳

如下：

1．收集问题的数据.并将数据输入电子表格的数据单元格；

2．确定需要做出的决策.并且指定可变单元格显示这些决策；

3．确定对这些决策的限制（约束条件）.并将以数据和决策表示的被限制的

结果放入输出单元格；

4．选择要输入目标单元格的以数据和决策表示的决策目标.

三、应用电子表格求解线性规划模型

上例的求解过程可通过在Excel的工具菜单中选择“规划求解”开始.“规

划求解”对话框如图13-4所示.

“规划求解”开始前.可通过

键入单元格地址或选中单元格

的方式确定模型的每个组成部

分设置在电子表格的何处（单击

暂时隐藏对话框.再从工作表

中选定单元格.然后再次单击

）.如目标单元格地址为E9.可变单元格

地址范围为C10：D10.并选中最大值（M）

表示要最大化目标单元格.

约束条件的设定可通过点击对话框中的

图 13-5

图 13-4

“添加”按钮.弹出图13-5所示的添加约束对话框.由于各种设备台时的总需求

量均不应超过可用台时数的限制.故单元格E5到E8必须小于或等于对应的单元

格G5到G8.即在添加约束对话框的左端输入范围E5：E8（可用选中单元格的方

. .

式）.中间选择<=（点开下拉列表进行选择）.右端输入范围G5：G8.如果模型中

还包含其他类型的函数约束.则可点击“添加”按钮以弹出一个新的添加约束对

话框.根据输出单元格与约束值之间的关系在对话框中间的下拉列表中选择适当

的约束类型.以增加新的约束.但本例中已无其他约束了.所以只要点击“确定”

按钮返回“规划求解”对话框.如果需要修改或删除已添加的约束.可选中该约束

后点击“更改”或“删除” 按钮.

到现在为止“规划求解”对话框

已根据图13-3的电子表格描述了整

个模型（见图13-4）.但在求解模型

前还需要进行最后一个程序.点击“选

项”按钮弹出图13-6所示的选项对话

框.这个对话框中是一些关于如何求

解问题的细节的选项.对于决策变量取

图 13-6

值非负的线性规划模型.最主要的选项是“采用线性模型”和“假定非负”选项.

（见图13-6）.关于其他选项.对小型问题来说接受图中所示的默认值通常比较

合适.点击“确定”按钮返回“规划求解”对话框.

现在可以点击“规划求解”对话框中的“求解”按钮了.它会在后台开始对

问题进行求解.对于一个小型问题.几秒钟之后“规划求解”就会显示运行结果.

如图13-7所示.它会显示已经找到了一

个最优解.如果模型没有可行解或没有最

优解.对话框会显示“规划求解找不到可

行解”或“设定的单元格值不能集中”.

图 13-7

对话框还显示了产生各种报告

的选项.后面将会介绍.选择“保

存规划求解结果” 并点击“确

定” 按钮.返回电子表格模型.

求解模型之后.如图13-8所

示.“规划求解”用最优解和最

图 13-8

. .

优值代替了可变单元格和目标单元格中的初始值.因此.最优解是生产4公斤药

品Ⅰ和2公斤药品Ⅱ.最优值为1400元.与图解法的结果一致.

图13-9显示的是例2-2的电子表格模型及求解过程.

图 13-9

这个问题的电子表格模型建立与求解过程与例2-1描述的基本相同.数据单

元格（C5：E8）、（C9：E9）和（H5：H8）分别存放三种原料

B

1

、B

2

、B

3

每斤所含

四种营养成分的数量、每斤原料的单价以及食品所要求的最低营养成分的含量限

制.可变单元格（C10：E10）存放三种原料配比情况（图13-9的左上部分）.输

出单元格（F5：F8）给出了食品中实际的营养成分含量.目标单元格（F9）显示

了该种食品的总成本（图13-9的左下部分）.

图13-9的右下角显示了“规划求解”对话框的主要部分.包括为目标单元格

和可变单元格设定的地址.约束条件F5



H5.F6



H6.F7



H7和F8



H8通过“添加

约束”对话框显示在“规划求解” 对话框中.由于目标是最小化总成本.所以选

择了“最小值（N）”.

图13-9的右上角显示了点击“规划求解” 对话框的“选项”按钮后所选择

的选项.“采用线性模型”先期定义了这个模型是线性规划模型.“假定非负”选

项定义了可变单元格必须是非负约束.因为食品的配比不可能出现负值.

点击“规划求解” 对话框的求解按钮后.得到了图13-9中电子表格的可变

单元格中显示的最优解.即该食品配比为原料

B

1

是1.94斤.原料

B

3

是2.36斤.

成本为109.72元.与单纯形法人工求解不同.如果输出单元格、可变单元格或目

标单元格结果不是整数.电子表格是以小数而非分数形式显示的.本例结果以四

. .

舍五入的方式保留了两位小数.

第二节 线性规划的应用问题

一、合理用料问题

这是第二章第五节的第一个问题.由于原料胶管的长度为15分米.而输液

管、止血带和听诊器胶管分别长5.7、4.2和3.1分米.所以每根原料胶管最多可

截三种材料依次为2根、3根和4根.即总的截法不超过3×4×5 = 60（种）.

又由于每种截法的料头不能超过2分米.所以可先通过电子表格进行试算以选择

其中可行的几种截法.再利用线性规划的方法找出用料根数最少的方案.如图

13-10的左上部分所示.单元格C4至E4显示三种胶管的长度；C5至E5输入不同

的方法截出每种胶管的根数；F4为对应C5至E5的不同截法所剩料头的长度. F5

通过判断剩余料头的长度是否在0到2之间显示出该种解法是否可行.单元格F4

和F5的公式见图13-10的左下部分.

图 13-10

不断变换C5至E5的可能取值并选择其中可行的截法（共6种）.在电子表

格中建立该问题的线性规划模型.数据单元格为C9：H11、C12：H12和K9：K12.

分别显示每种截法截一根原料胶管时得到三种不同材料的数量、每种截法截取一

次所用胶管的数量和三种材料的需要量；可变单元格C13：H13显示采用每种截

法所截的胶管原料数；输出单元格I9：I12列出了某一截取方案实际获得的三种

材料数量.每种材料的数量等于各种截法截得该材料数与对应截法所截原料数的

乘积之和.如输液管的数量I9 = SUMPRODUCT(C9:H9,C13:H13)；目标单元格I12

. .

为总用料数.应等于各种截法所截原料数之和,即I12 = SUM(C13:H13).

图13-10的右半部分显示了“规划求解”对话框及“选项”对话框的内容.

该问题的目标是所用的胶管原料的总根数最少.因此设置目标单元格为I12等于

最小值.由于实际获得的材料数量必须满足需求量的要求.考虑到最优方案（各种

截法的某一组合）不一定能使截出的三种材料数量恰好等于需要的数量.而某种

材料超过需求量是允许的.故在添加约束时可设置实际截得的数量大于等于需求

量.即I9：I12>=K9：K12（本题中.该约束取“>=”和“=”的结果是相同的）；

又由于截出的各种材料数量均为整数.因此约束中应包括决策变量取整数的限制.

即C13:H13=整数.

图13-10的左上部分显示了该问题的最优方案为：分别用第二种、第四种和

第五种截法截取原料40、60和10根.共用原料110根.与第二章中用大

M

法求

解的结果一致.

二、放射科的业务安排

图13-11显示了第二章问题二的电子表格模型及求解过程.该问题的数据包

括：进行三种检查

的单位时间（C5：

E5）.三种检查设备

每月的可用时间

（C9：E9）.三项业

务每月最多提供量

（H6）以及每项业

务的单位利润

（C10：E10）.可变

单元格为C6至E6.

图 13-11

给出三项业务每月的实际发生数量.输出单元格为C7至E7和F6.分别表示根据

各项业务的实际发生数量产生的设备使用时间及实际的总业务量.目标单元格

F10显示由每项业务的单位利润及每月实际发生数量计算的总利润.图13-11的

左下部分给出了输出单元格及目标单元格的公式.

. .

图13-11右下部分的“规划求解”对话框显示了求解时应注意的问题：求目

标单元格的最大值（利润最大）；约束为设备的实际使用时间小于等于设备的可

用时间及实际总业务量小于等于总业务提供量的限制.

打开“选项”对话框.仍选择“采用线性模型”和“假定非负”.回到“规划

求解”并按“求解”按钮.得到问题的最优方案为：每月X线及CT检查的业务量

分别为1320人次和480人次.磁共振业务量为0.即不必购买该设备；按最优方

案安排业务每月可获利55200元.

在电子表格上建立线性规划或其它问题模型的方式是非常灵活的.不必拘泥

于一种固定的模式.本书仅提供了一种建立模型的思路.读者可根据不同问题的

特点以及个人的习惯或喜好建立不同风格的电子表格模型.

第三节 线性规划的灵敏度分析

前面指出线性规划模型的许多参数.都只是对实际数据的大致估计.而不可

能在研究的时候就获得精确的数值.通过灵敏度分析可以得出每一个估计的数据

需要精确到何种程度.才能保持解的最优性.

回忆例2-1某制药厂的生产计划问题.其求解结果如图13-8所示.即生产4

公斤药品Ⅰ和2公斤药品Ⅱ.总利润为1400元.但该最优解是在假设所有的模型

参数都准确的前提下做出的.在此基础上.管理层如果进一步考虑下列问题：

1．如果在该厂生产的药品中.有一个单位利润的估计值是不准确的.将会发

生怎样的情况？

2．如果该工厂两种药品的单位利润的估计都是不准确的.又将会怎样？

3．如果改变该厂某种设备可用于生产的时间.会对结果产生什么影响？

4．如果四种设备可用于生产的时间同时改变.又会对结果产生何种影响？

在本节中.我们将重点介绍如何利用“规划求解”中的“敏感性报告”对目

标函数系数

c

j

以及约束条件右端值

b

i

的变动进行灵敏度分析.分析的内容主要是

系数在什么范围内变化时.已得到的最优解保持不变.即发现哪些系数不太敏感

（由于在较大范围内变化时.最优解保持不变.故可以进行粗略估计）.哪些系数

比较敏感（即使微小的改变都会对最优解产生影响.故必须对其精确定义）.

. .

一、目标函数系数变动的灵敏度分析

首先介绍目标函数系数的灵敏度分析.回顾一下就可以知道.这些系数表示

各种决策对总目标的单位贡献.下面以例2-1某药厂的生产计划问题的目标函数

系数变动情况进行讨论.

问题1：如果该药厂一种药品的单位利润的估计是不精确的.结果怎样？

首先看一下.如果药品Ⅱ的单位利润300元的估计是不精确的情况.假设：

药品Ⅱ的单位利润 = 电子表格中D9单元格中的数据

现在.

c

2

=300元.下面我们来分析一下在保持最优解

(x

1

,x

2

)(4,2)

不变的

条件下.

c

2

可能的最大值与最小值.这样.也就可以看出

c

2

为300元的这一估计能

够在多大程度上偏离实际值而不会改变解的最优性.

（一）使用电子表格进行灵敏度分析

电子表格的一个强大的优点就是可以方便互动地展开各种形式的灵敏度分

析.通过运用规划求解工具来求解最优解.模型参数值的改变所造成的影响一下

子就可以显示出来.

为了说明这一点.图13-12显示了药品Ⅱ的单位利润从开始的

c

2

=300元降到

c

2

=250元的情况.与图13-8相比.最优解没有丝毫的变化.事实上.该问题唯一的

变动是电子表格中C9单元格

中的数据从300元降到250

元.以及E9单元格总利润减

少了100元（因为每单位药

品Ⅱ所提供的利润减少了50

图 13-12

元）.因为最优解没有变动.

我们可以知道在不影响最优

解的前提下.药品Ⅱ的单位利

润

c

2

=300元的最初估计是较

高的.

图 13-13

. .

那么.如果这一估计值较低又会怎样呢？图13-13表示了将

c

2

=300元增加到

c

2

=350元的情况.同样.最优解没有发生变化.

因为.增加或减少最初的

c

2

=300元均不会对最优解产生任何影响.

c

2

就不是

很敏感的系数.也就不需要为了保证最优解不会改变.而花很大力气去得到

c

2

的

更精确的值.但是对

c

2

的研究至此并没有结束.因为实际值很可能会超出250到

350元这一范围.那么在保持最优解不变的条件下.

c

2

到底可以在什么样的范围

内取值呢？当然可以在电子表格中采取试验的方法.不断增加或减少的

c

2

值.直

到最优解发生改变.以找到最优解发生变化时对应的

c

2

值.但是.这样计算太麻烦

了.是否有简便一些的方法呢？答案是肯定的.

（二）利用敏感性报告进行目标系数的灵敏度分析

如图13-7所示.在求得最优解之后.规划求解工具会给出相应的信息.同时.

在其右边列出了它可以提供的三个报告.选择第二项敏感性报告的选项.就可以

得到灵敏度的分析报告.它显示在模型的工作表之前.

图13-14显示了本例敏感性报告中的一部分.终值一栏表明了问题的最优解.

第二栏给出了递减成本.递减

成本提供了为使决策变量取

正值.相应的目标系数需要减

图 13-14

少的数量.对于本例.由于两决策变量的取值均为正数.故递减成本均为零.第三

栏表示了目标函数的现值.最后两栏表示为使最优解保持不变.目标系数允许增

加与减少的最大值.

例如.考虑决策变量

X

1

的目标系数

c

1

.从图13-14中表示产品Ⅰ的一行中可

知.

c

1

可以减少50.可以增加1E+30.在电子表格中1E+30是10

30

的缩写.Excel使

用这一极大的数值来表示无穷大.因此.从灵敏度的分析报告中可知：

c

1

的现值： 200

c

1

的允许增加值： 无穷大 此时

c

1

无上限

. .

c

1

的允许减少值： 50 此时

c

1

20050150

c

1

的变化范围：

c

1

150

因此.只要在上面的变化范围内变动.并且不改变模型的其他任何内容.最优

解将始终保持在

(x

1

,x

2

)(4,2)

不变.该药厂的另一药品的单位利润的变化范围

也可以用同样的方法得出.

c

2

是药品Ⅱ的单位利润.表中表示药品Ⅱ的第二行给

出了下面关于

c

2

的信息：

c

2

的现值： 300

c

2

的允许增加值： 100 此时

c300100400

2

c

2

的允许减少值： 300 此时

c3003000

2

c

2

的变化范围：

0c400

2

目标函数的两个系数的允许变化范围都很大.因此.尽管药品Ⅰ和药品Ⅱ的

单位利润可能仅仅是实际值的一个粗略估计.我们也可以相信.这个估计值对最

优解的正确性不会有影响.

但在一些线性规划模型中.目标系数微小的变动都可能会影响最优解.这样

的系数称为敏感参数.灵敏度的分析报告中会直接显示目标中哪些系数是敏感的.

这些系数允许的变化区域很小.因此.必须格外小心.尽量取得这些数据的精确

值.

在求得模型的最优解之后.目标系数的允许变化范围还有一个很重要的用途.

在问题的线性规划分析结束之后.如果外界的环境发生了一定的变化.灵敏度分

析可以在无需重新求解的情况下.表明模型参数的变化是否造成了最优解的改变.

例如经过一段时间以后.如果药品的单位利润发生了较大的变化.通过其允许变

化范围.可以一眼看出原来的最优组合是否依然适用.有了目标系数的允许变化

范围.在判断问题时.就不需要重新建模与求解.这一点对线性规划问题的解决是

有很大帮助的.特别是在处理一个大型模型时.

（三）目标系数的同时变动

因为存在许多不确定性因素.目标函数系数的值.如单位利润.通常都只是对

. .

实际值的估计.上面所讨论的是只有一个系数变动时的情况.这类问题在求解一

个系数的允许变化范围时.假设其他所有系数都是正确的.研究的系数是唯一可

能与实际值不符的变动的系数.但事实上.所有的系数（至少一个以上）可能同时

都是不准确的.如果这样的话.是否可能会导致求得的最优解不正确呢？这是最

关键的问题.如果可能对最后的结果产生影响.就必须对这些系数作进一步的分

析.另一方面.如果灵敏度分析表明目前的参数估计不会影响最优解的正确性.那

么.管理者可以增加对该模型及其所提供的解决方法的信心.

以下将介绍如何在不重新求解模型的条件下.确定如果目标函数的几个系数

同时变化.可能造成的对最优解的影响．我们仍利用例2-1提出如下问题：

问题2：如果该药厂两种药品的单位利润的估计都是不准确的.将会对结果

产生怎样的影响？

例如.原来药品Ⅰ和药品Ⅱ的单位利润分别为200元和300元.现在由于原料

成本的变化.每公斤药品Ⅰ和药品Ⅱ的单位利润分别变为180元和355元.最优解

是否发生变化？在分析多个系数同时变动的情况时.仍然要使用敏感性报告中提

供的每个系数的允许增加值和减少值数据.下面介绍多个系数同时变动的百分之

百法则.

首先定义

c

j

的允许增加（减少）百分比为

c

j

的增加量（减少量）除以

c

j

的

允许增加量（允许减少量）的值.这样我们可以计算出

c

1

的允许减少百分比为

(200180)/5040%

.

c

2

的允许增加百分比为

(355300)/10055%

.

c

2

的允

许减少百分比与

c

2

的允许增加百分比之和为

40%55%95%

.

目标函数系数同时变动的百分之百法则：如果目标函数的系数同时变动.当

其所有允许增加百分比和允许减少百分比之和不超过百分之百时.最优解不会改

变.如果超过百分之百.则不能确定最优解是否改变.

因为本例中

c

1

的允许减少百

分比与

c

2

的允许增加百分比之和

为95%不超过100%.所以当每公斤

药品Ⅰ的利润减少为180元.每公

图 13-15

. .

斤药品Ⅱ的利润增加为355元时.此线性规划最优解仍然为药品Ⅰ生产4公斤和

药品Ⅱ生产2公斤（即

x

1

4,x

2

2

）.此时有最大利润为

180435527207101430

（元）.如图13-15所示.

这一法则并没有表示出.在变动百分比之和超过百分之百的情况下.可能的

结果.这一结果还有赖于系数变动的方向.但是.只要变动百分比之和不超过百分

之百.最优解是肯定不会改变的.记住.我们可以让单一的目标函数系数在整个允

许范围内变动.但这只有在其他目标函数系数都不变的情况下才有效.如果多个

系数同时变动.我们必须研究各个系数的变动百分比.

二、约束右端值的灵敏度分析

之所以要分析函数约束右端值变动的原因与前面一样.因为在建模时.还不

能得到模型的这些参数的精确值.只能对其作粗略的估计.因此.我们希望知道在

这些估计不准确的情况下会产生怎样的后果.除此之外一个更主要的理由是因为.

这些常数（通常代表资源的可用量）往往不是由外界决定的而是管理层的政策决

策.因此管理者希望知道如果改变这些决策是否会提高最终的收益.影子价格分

析就是为管理者提供这方面的信息.

下面是关于例2-1的第三个问题：

问题3：如果改变该厂某设备可用于生产的时间.结果将如何？

（一）约束右端值的影子价格分析

回忆第二章中关于影子价格的经济含义.我们知道影子价格代表单位资源在

最优利用的条件下所产生的经济效果.即在模型获得最优解的情况下.约束条件

右端值在一定范围内每增加（减少）一个单位.使目标函数值增加（减少）的量.

其中.一定范围是指保持影子价格不变的右端值变化范围.

在影子价格分析中.每次分析一个函数约束.可以将该函数约束右端值的常

数增加一个单位后重新求解.观察目标函数值增加的量来确定影子价格.也可以

利用灵敏度报告中提供的关于每一个函数约束的影子价格数据.

从一个约束的影子价格中就可以直接看出.决策改变而引起的约束常数的

改变所造成的影响.只要约束常数的变动不大.那么目标函数值的变动就等于约

束常数的变动（正或负）乘以影子价格.为了说明影子价格的含义.我们以第二章

. .

第五节中的第二

个应用.即放射科

的业务安排问题

为例来加以讨论.

该问题最初的线

性规划模型如图

13-16上半部分所

示.单元格H6及

C9至E9中的值

图 13-16

1800.300.120.12

0分别表示总业务提供量以及三种设备的可用时间的限制.可变单元格C6至E6

中的最优解表明放射科每月安排1320人次的X线检查和480次的CT检查.目标

单元格F10显示如此安排后每月的总利润为55200元.

得到这些信息后.科室的领导可能希望知道增加一单位资源的可用量对总利

润的影响.即影子价格.首先从业务提供量H6开始分析.图13-16的下半部分表示

了放射科可以提供的业务量由1800增至1801时.对结果的影响.将图13-16上下

两表中的目标单元格H10进行对比.可看出利润的增加量为：

利润的变化量 = 55220元-55200元 = 20元

从而计算出业务提供量的影子价格为20元/每人次.即增加1人次的业务提

供量对总利润的贡献是20元.

用上述方法计算影子价格简单明了.但需要对每个约束进行试算.且有时可

能得到错误的结果（后面将讨论）.此外.我们还可以采用“规划求解”结果给出

的敏感性报告直接得到各个约束的影子价格.图13-17显示了灵敏度分析中与函

数约束有关的部分.其中的第四栏给出了各约束的影子价格.结果如下：

业务提供量的影子价格 = 20元/人次

X线检查的影子价格 = 0 元/小时

CT检查的影子价格 = 160元/小时

磁共振检查的影子价格 = 0元/小时

. .

图 13-17

这些影子价格都是资源增加一个单位引起的总利润的增加量.为什么X线检

查的影子价格为0？可以通过比较图13-16上表中C7和C9来说明.X线检查设备

的可用时间有300小时.而按最优解的业务量使用该设备的时间仅为132小时.

已有168小时的闲置.因此.即使再增加设备的可用时间也不会改变最优解和总

利润.同样可以解释磁共振检查的影子价格也为0的原因.

（二）影子价格的灵敏度分析

图13-7的第六、七栏给出了每一约束限制值在什么范围内变化时.该约束的

影子价格是不变的.这一范围称为影子价格的有效区域.可以看出：

业务提供量的影子价格的有效区域的上限为：1800+1680=3480.下限为：

1800-1320=480.其有效区域为：

480b

1

3480

.即当业务提供量在此范围内变

化时.每增加（减少）一人次.总利润也会相应地增加（减少）20元；类似可得X

线使用时间、CT使用时间以及磁共振使用时间的影子价格有效区域分别为：

b

2

300168132

.

1201200b

3

120330450

.

b

4

1201200

.

我们再来看第二章的例2-1.该

问题最初的线性规划模型如图

13-8所示.G栏中的常数

（12.8.16.12）表示四种设备可用

的台时数.当我们将设备B的可用时

间从8小时增加到9小时时.我们发

图 13-18

现总利润增加了100元（从1400元增加到了1500元）.如图13-18所示.但100

元并不是设备B可用时间的影子价格.

图13-16显示了其敏感性报告的第二部分.终值栏给出了输出单元格E5至

E8的终值分别为12.8.16.8（如图13-8的E栏所示）；约束限制值一栏即表13-8

中G5至G8中的常数.从阴影价格一栏中可以看出.设备B可用时间的影子价格为

. .

150元.通过分析其影子价格的有效区域可知.可用时间在4—8小时之间时.每增

加（减少）一个小时的可用时间.总利润会相应增加（减少）150元.但由于设备

B的可用时间正好为8小时.

所以再继续增加1个小时的

可用时间后.约束限制值已

经超过了影子价格的有效

区域.故总利润的增加值只

图 13-19

有100元而不是150元.从图13-9中还可以看出.设备A和设备D的影子价格均

b

1

12

.

8b

3

16

.

b

4

8

. 为0.设备C的影子价格为12.5元.有效区域分别为：

（三）约束右端值同时变动的情况

函数约束右端值的有效区域表示的是.约束右端值的变动在有效区域内时.

该约束的影子价格就可用于评估约束右端值改变造成的影响.但必须注意的是.

只有在仅一个约束右端值变动而其他约束右端值均不变的情况下.该约束右端值

的有效区域才是完全有效的.而实际上.由于管理层在约束右端值上的决策往往

是相关的.因此约束右端值经常会同时变动.如果多个约束右端值同时变动.那么

如何评估可能造成的影响呢？

仍以放射科的业务安排问题为例.我们已经知道放射科已有X线及CT检查设

备.且CT检查设备使用时间具有最大的影子价格为160元.X线使用时间的影子

价格为0元.科室领导希望减少X线的可用时间而相应增加CT检查的可用时间.

假设减少X线的可用时间3小时可相应增加CT检查的可用时间1小时.在这种同

时变动的情况下.会产生怎样的后果呢？

根据影子价格分析.将X线的可用时间减少3小时.并将CT检查时间增加1

小时.所产生的结果如下：

CT检查时间： 120→121 总利润的变化量= 影子价格 = 160元

X线检查时间：300→297 总利润的变化量= - 影子价格×3=-0×3= -0元

总利润的净变化 =160元

但是.我们现在还不能确定.两个约束右端值这样改变以后.原先的影子价

格是否依然有效.

检验有效性的一种

. .

方便快捷的方法就是将这些数据代入电子表格的相应单元格中去.重新求解.图

13-20所示的电子表格显示出总利润的净增量确实为160元（从55200元增加到

55360元）.因此.影子价格在上面约束右端值同时变动的情况下是有效的.

如果我们继续减少

图 13-20

X线检查时间而相应增加CT检查时间.结果会如何呢？当然可以将数据代入电子

表格后再重新求解.但这种方法是不切实际的.特别是有两个以上的约束右端值

同时变动的情况.幸好.有与处理目标系数同时变动类似的百分之百法则.

约束右端值同时变动的百分之百法则：对于所有变化的约束条件右边常数值.

当其所有允许增加百分比和允许减少百分比之和不超过百分之百时.其影子价格

是有效的.其中约束右端值的允许增加（减少）百分比的定义同目标系数的允许

增加（减少）百分比一样.为约束右端值的增加量（减少量）除以约束右端值的

允许增加量（减少量）的值.

为了解释这一法则.仍然考虑图13-20的情形.将X线的可用时间减少3小时.

并将CT检查时间增加1小时.按照百分之百法则.计算如下：

CT检查时间：120→121

121120

占允许增加量的百分比

()100%0.03%

330

X线检查时间：300→297

占允许减少量的百分比

(

300297

)100%1.79%

168

总和

1.82%

因为变动百分比之和1.82%小于百分之百.所以用影子价格来预测这些变动

的影响是有效的.

上面求得的变动百分比之和为1.82%.表明即使将原先的变动扩大50倍也不

会使影子价格失效.

第四节 特殊形式的线性规划问题

在本节中.我们将重点讨论三类特殊类型的线性规划问题——运输问题、0-1

规划问题及指派问题的Excel模型及求解.

一、运输问题

. .

（一）运输问题的模型及参数

运输问题的描述见本教材第三章.

一般的运输问题（表2-1）就是要解决把某种产品从若干个产地调运到若

干个销地.在每个产地的供应量与每个销地的需求量已知.并知道各产销地之间

的运输单价的前提下.如何确定一个使得总的运输费用最小的方案.

实际上运输问题的模型在供应量和需求量两方面做出了如下的假设：

产销平衡假设：每一个产地都有一个固定的供应量.所有的供应量都必须运

输到销地；与之相类似.每一个销地都有一个固定的需求量.整个需求量都必须由

产地满足.即总供应量等于总需求量.

对于运输问题而言.当且仅当供应量的总和等于需求量的总和时.问题才有

可行解.

某些实际的问题并不符合产销平衡的假设.供应量实际上代表着所要运输的

产品的最大数量（而不是一个固定的数值）.需求量实际上也是代表着所接受的

最大数量（也不是一个固定的数值）.这些问题并不符合运输问题模型.所以它们

是运输问题的变形.

表3-1的中间部分给出了运送货物的单位运费.关于运费对于任何一个运输

问题都有下面的一个基本假设.

运输费用假设：从任何一个出发地到任何一个目的地的货物运费与所运输的

数量成线性比例关系.因此总运费就等于单位运费乘以所运输的数量.

运输问题所需要的数据仅仅是供应量、需求量和单位运费.这些就是模型参

数.所有的这些参数都可以总结在一个表格中.这个表格就叫做参数表.表3-1就

是典型的运输问题的参数表.而表3-3则是运输问题例3-1的参数表.

运输问题模型：如果一个问题可以完全描述成如表3-1所示的参数表形式.

并且符合产销平衡假设和运输费用假设.那么这个问题（不管其中是否涉及到运

输）都适用于运输问题模型.最终目标都是要使总运费最小.这个模型的所有参数

都包含在参数表中.

（二）运输问题的Excel模型及求解

在建立了运输问题的线性规划模型之后.我们可以使用Excel来描述和解决

. .

运输问题.以例3-1为例.首先.我们需要在电子表格中输入两个表格.第一个表

格是参数表.提供有关这一问题的所有参数；第二个就是求解表格.包含了从每个

医院到每个贫困县的人员安排情况.图13-21显示了这两个表格.以及求解本例

所需要附加的公式.

在这个电子表格中需要包含运输问题的两类约束.即供应约束和需求约束.

对于供应约束来说.图13-21求解表格中的H列算出了每家医院抽出的医务人员

总数.它是其相应行所有决策变量单元格数据的总和.例如.在H15单元格中的等

式就是“H15=D15+E15+F15+G15”或者是“H15=SUM（D15：G15）”.每家医院所能

抽出的人员数均包含在J列中.因此.H列的单元格中的数据应该等于相应的J列

的单元格中的数据.

对于需求约束来说.向每一个贫困县派出的医务人员总数在电子表格的第

18行列出.是其相应列的所有决策变量单元格数据之和.例如.D18=SUM（D15：

D17）.每县的实际需要人数在第20行中给出.

图 13-21

注：某省医疗队巡回医疗扶贫问题的Excel模型.图中从第3行到第9行显示了参数表.

从第12行到第20行显示了求解表格.本模型利用“规划求解”处理得到了最优的人员安排

计划.图的底部及右侧分别给出了输出单元格的公式以及建立“规划求解”所需要的说明.

H18单元格计算出了总费用.它是参数表和求解表主体部分每一相应单元格

乘积的和.即H18 = SUMPRODUCT（D6：G8.D15：G17）.

图13-21的右上半部分是“规划求解”对话框中输入的内容.这些内容说明

. .

了“规划求解”工具通过改变人员安排（决策变量单元格D15到G17）.按照派

到每一个贫困县的人员数量等于它的总需求量（D18：G18=D20：G20）以及从每

一所医院抽出的总人数等于其所能抽出的人员数（H15：H17=J15：J17）的约束

条件对总费用进行最小化处理（单元格H18计算出了结果）.图13-21的右下半

部分显示了“规划求解选项”.（采用线性模型）说明运输问题同样也是一个线

性规划问题.（假定非负）说明所有的决策变量（派出人员数）必须是非负的.

决策变量的值（派出人员数）在单元格（D15：G17）中.对于每一个单元格

来说.可以先输入任意数值（如0）或不输入（默认为0）.在按下“规划求解”

对话框的求解按钮后.“规划求解”工具就会确定出每一个决策变量的具体数值.

最优解及所得到的最小总费用如图13-21所示.

（三）其他运输问题的处理

前面的讨论都是以供销平衡为前提的. 对于产销不平衡的运输问题.即总需

求量与总供应量不相等的运输问题.显然是没有可行解的.因此.对于产销不平衡

的运输问题.我们可以先化为产销平衡的运输问题然后再求解.

将例3-1稍作修改.其参数表变为表13-1：

表13-1 修改后运输问题的人均费用

B

1

B

2

B

3

B

4

医院抽出人数

人均费用（单位：百元）

A

1

A

2

A

3

县需求人数

2 9 10 7 9

1 3 4 2 7

8 4 2 5 7

3 8 4 6 21 23

与例3-1比较.只是医院

A

2

的抽出人数增加了两人.这样一来总抽出人数为

23人.大于总需求人数21人.是一个产大于销的运输问题. 为此再建立一个假想

的县

B

5

.

B

5

的需求人数为2人.而从

A

1

、

A

2

、

A

3

派往

B

5

不需要花费.所以可令

c

15

c

25

c

35

0

.即对应的人均费用为0. 这样就得到了修改后问题的产销平衡

的参数表.将产大于销的运输问题化成了产销平衡的运输问题（见表13-2）.

表13-2 修改后产销平衡运输问题的人均费用

B

1

B

2

B

3

B

4

B

5

医院抽出人数

. .

人均费用（单位：百元）

A

1

A

2

A

3

县需求人数

2 9 10 7 0 9

1 3 4 2 0 7

8 4 2 5 0 7

3 8 4 6 2 23

利用电子表格对其求解.可得到如图13-22所示的最优解和最小总费用.

类似地.如果是销大于产的运输问题.则可以采用增设虚拟产地的办法使之

化为产销平衡的运输问题来处理.

产销不平衡的运输问题还有一种情况.一个销地同时存在着最小需求和最大

需求.于是所有在这两个数值之间的数量都是可以接收的.

图 13-22

在例3-1中将问题的要求作如下变化：各医院抽出的人员总数不变为21人.

而

B

1

、

B

2

、

B

3

、

B

4

四个县的最小需求人数分别为3、6、2、4人.最大需求分别为

5、9、5、6人.最大总需求人数为25人.由于总需求比可以抽出的人数多出4人.

为了化成产销平衡的运输问题.可在参数表中增加虚拟医院

A

4

这一行.可抽调人

数为4人.另外.为了区别必须满足的需求量（最小需求量）与可以不满足的需求

量.可将每个县分为两列.如

B

1

县的第一列为

B

11

.它的需求量是必须要满足的3人.

第二列为

B

12

.它的需求量是可以不满足的2人.显然.必须满足的最小需求不能从

虚拟的医院抽调人员.为了必须满足

B

11

的3人.我们将虚拟医院到

B

11

的人均费用

定为

M

（是一个足够大的正数）.如果虚拟医院抽调到

B

11

的员数为

x

41

0

.则为

. .

此付出的费用将为

Mx

41

.是个很大的正数.这显然不符合总费用最小的目标.这

样就保证了

x

41

0

.但对于

c

42

则可以定为0.因为虚拟的医院并没有抽出人员.人

均费用当然为零.又因为

B

12

的需求2人可以不满足.所以

x

42

可以为正数.另

外.

c

12

c

11

2

.

c

22

c

21

1

.

c

32

c

31

8

.对其他的三个县也进行了同样的处理.

该问题的参数表见表13-3.

表13-3 有最小需求的运输问题的人均费用表

B

11

B

12

B

21

B

22

B

31

B

32

B

41

B

42

医院抽出人数

人均费用（单位：百元）

A

1

2 2 9 9 10 10 7 7 9

A

2

A

3

1 1 3 3 4 4 2 2 5

8 8 4 4 2 2 5 5 7

A

4

县需求人数

M

0

M

0

M

0

M

0 4

3 2 6 3 2 3 4 2

在用电子表格对该问题建模及求解时.表中的

M

可以输入一个足够大的数.

如10000.如图13-23.

图 13-23

二、整数规划及0—1规划问题

（一）整数规划问题的计算机求解

. .

在线性规划问题中.最优解可能是整数.也可能不是整数.但对于某些实际问

题.要求决策变量必须取整数.即整数规划问题.如：

例13-1

maxz3x

1

x

2

3x

3



x

1

2x

2

x

3

4

.



4x3x1

23





s.t.



x

1

3x

2

2x

3

3



x,x,x0

123







x

1

,x

2

,x

3

为整数

.

利用电子表格对该整数规划问题求解的方法与线性规划问题类似.只是在

“规划求解”对话框的约束一栏中.增加对决策变量

x

1

,x

2

,x

3

的整数约束.利用电

子表格对该问题求解的结果见图13-24.

图 13-24

（二）0—1规划问题的计算机求解

以例3-2为例.根据其代数模型可建立如图13-5的电子表格模型：

图 13-25

该电子表格模型中可变单元格为（C7：F7）.其取值为1（0）时表示携带（不

携带）相应的物品.即决策变量为0—1变量.因此.应有决策变量为二进制的约束

. .

限制（见图13-25的左下部分）.该模型仅包含一个关于所携带物品重量的约束.

该同学所携带物品的总重量（显示在G5）为所携带的所有物品的重量之和.即G5

= SUMPRODUCT(C5:F5,C7:F7).其值不应超过背包的重量限制5.故有G5≤I5.其携

带物品的总价值（目标单元格）为G8 = SUMPRODUCT(C6:F6,C7:F7).在“规划求

解选项”对话框中.仍选择“采用线性模型”和“假定非负”.

读者可将例3-3作为练习.

三、指派问题

（一）指派问题的模型及计算机求解

指派问题既是0-1规划的特殊情况.也是与运输问题密切相关的一类特殊的

线性规划问题.其电子表格模型与运输问题类似.

指派问题也需要满足一些假设：

1．被指派者的数量和任务的数量是相同的.

2．每一个被指派者完成且只完成一项任务.

3．每一项任务必须且只能由一个被指派者来完成.

4．每一个被指派者和每一项任务的组合都会有一个相关的成本（收益）.

5．问题的目标是要确定怎样进行指派才能使得总成本达到最小（总收益最

大）.

以例3-4为例.我们需要确定的是将哪项化验任务指派给哪位化验员.能够

使所需总时间最少？该问题的电子表格模型见图13-26.

与运输问题类似.指派问题的模型也需要在电子表格中输入两个表格.即参

数表和求解表.参数表主体部分（D6：G9）给出了四位化验员分别完成四种化验

所需要的时间.而求解表主体部分（D16：G19.初值均为0）给出了具体的人员安

排情况.决策变量单元格取值为1或0时.分别表示指派或不指派某位化验员完成

某项化验.如D18=1表示指派丙完成化验A.而E16=0则表示不指派甲完

. .

图 13-26

成化验B（见图13-26的左上部分）.指派问题也有两类约束.提供量约束：根据

第二条假设.每位化验员只完成一项化验任务.即求解表中每一行的四个单元格

中.只能有一个为1.其余均为0.每行之和（列入单元格H16：H19）为1；需求量

约束：根据第三条假设.每种化验只能由一位化验员完成.即求解表的每列之和

（列入单元格D20：G20）为1.

H20单元格计算出了总时间.它是参数表和求解表主体部分每一相应单元格

乘积的和.即H20 = SUMPRODUCT（D6：G9.D16：G19）.

图13-26的右上半部分是“规划求解”对话框中输入的内容.除提供量约束

（H16：H19=J16：J19）和需求量约束（D20：G20=D22：G22）外.由于指派问题

的决策变量也为0—1变量.应有决策变量为二进制的约束.指派问题也属于线性

规划.故仍选择“采用线性模型”和“假定非负”.问题的最优解及所得到的最少

时间如图13-26所示.

例3-5是一个最大化的指派问题.其电子表格模型与例3-4完全一致.区别仅

在于“规划求解”对话框中.设置目标单元格等于“最大值”.

（一）指派问题的变形

我们经常会遇到指派问题的变形.之所以称它们为变形.因为它们都不满足

前述指派问题所有假设之中的一个或者多个.如：

1．有一些被指派者并不能完成某一些任务.

2．虽然每一个被指派者完成一项任务.但是任务比被指派者多.所以其中某

些任务并没有得到执行.

3．虽然每一项任务只由一个被指派者完成.但是这里被指派者比要完成的任

. .

务多.所以.其中有一些被指派者没有指派到任务.

4．每一个被指派者可以同时被指派给多于一个的任务.

5．每一项任务都可以由多个被指派者共同完成.

在此.我们仅就情况2展开详细讨论.以例3-6为例.

图 13-27

该问题的电子表格模型与一般指派问题的不同之处在于.需求量约束不是严

格的等式约束.由于研究人员少而课题任务多.且每人只能承担一项研究.所以会

出现有些课题无人承担的情况.由于决策变量取值为0或1.某项课题无人承担时.

求解表中对应列之和为0.有1人承担时和为1.因此.可将需求约束设定为每列之

和小于等于1（见图13-27的左上部分）.

如果指派问题中出现人员多而任务少的情况（情况3）.则在模型的求解表

中需求量约束仍保持严格的等式约束.即每项任务都必须指派一人完成.而提供

量约束设定为每行之和小于等于1.即有些人员没有被分配任务.

如果一个人可以被分配多于一个的任务（情况4）.可取消模型中对于提供

量的约束限制；如果一项任务可以由多个人共同承担（情况5）.则应视具体情

况建立模型.

在指派问题中.也可能出现某人不能完成某项任务的情况（情况1）.则在约

束中应加入相应的决策变量等于零的限制.例如在例3-6中增加一条件：甲不能

. .

承担课题B.则在图13-27的模型参数表中.E6单元格中以“—”取代原来的数字

“5”.而在“规划求解”对话框中.添加约束“E15=0”.这样可保证在最终求解

结果中.不会出现指派甲承担课题B的情况.

第五节 目标规划问题

目标规划的电子表格模型在结构及处理方式上与线性规划模型是相同的.

主要的区别一是目标规划中引入了正负偏差变量

d

i



及d

i



.这些偏差变量用于反

映目标的实现情况.在模型中可以作为决策变量处理；二是由于要按照一定的次

序实现多个目标.于是在目标函数中引入了优先因子

P

1

.

P

2

.….

P

n

并规定

P

k

»

P

k+1

.

表示

P

k

比

P

k+1

具有绝对的优先权.但应注意在电子表格中不能用字母来表示这种

优先因子.而只能由具体的数字去代替.为了保证

P

k

»

P

k+1

.可将

P

k

和

P

k+1

的取值相

n

差10 倍以上.

n

可视具体情况取1.2或3等.如果各目标约束的右端期望值相差

不大.

n

可只取到1.如取

P

k

=10.取

P

k+1

=1.但是.由于各目标期望值

e

i

的单位不同.

期望值

e

i

之间可能相差悬殊.这种情况下为保证第

k

级目标先于第

k+

1级目标被

满足.

n

的取值就应适当放大.

例如.例4-4的目标规划问题为



minzP

1

d

1



P

2

d

2

P

3

d

3



s.t



5x

1

10x

2

60







x

1

2x

2

d

1

d

1

0







4x

1

4 x

2

d

2

d

2

36





6x8x dd48

1233





x

1

,x

2

0,d

i



,d

i



0,(i1,2,3)



其电子表格模型如图13-28所示.

图中可变单元格C8：D8显示的是决策变量的取值.输出单元格E4表示约束

条件的左端值.而单元格L4给出了第一个约束条件的右端值.在约束条件中后

. .

图 13-28

三个属于目标约束.E5：E7中的等式表示了在这些变量下.目标约束中各目标的

实际值.可变单元格H5：I7表示的是各目标实际值低于或超过期望目标值的偏差

值. L5：L7是各目标约束右端的期望目标值.第J列的公式表示目标的实际值加

未达到值再减超出值应等于期望值.

该问题的目标分为三个优先级来实现.单元格E10：E12中给出了优先因子的

取值.相邻的两个因子之间相差10倍.1.E+03是科学计数法.表示10

3

.单元格

G10：G12中的公式表示了各级的具体目标是使哪个偏差值或哪些偏差值的组合

达到最小.本例目标函数中第一、二、三级目标分别是使偏差值

d

1



,d

2



,d

3



达到最

小.因此在G10：G12中分别引用了可变单元格H5.I6和H7.目标单元格J12 =

SUMPRODUCT（E10：E12.G10：G12）应取最小值.并通过对优先因子的控制保证目

标按优先顺序实现.

该问题是一个线性规划模型.所有的可变单元格数据都要求是非负的.这些

可以通过“规划求解”的选项对话框来实现.此外要满足约束条件E4



E6和J5：

J7=L5：L7.但对输出单元格E5：E7没有限制.因为并不要求目标约束中的实际值

与期望值完全相等.

按下“规划求解” 对话框的求解按钮后.电子表格中显示最优解对应的决策

变量为



x

1

,x

2





(4.8,2.4)

.问题的三级目标均得以实现.因此目标函数值为0.

但实际上.通过第四章对该问题用图解法分析我们得知.其最优解有无穷多个（其

最优解域为一个四边形）.但利用电子表格我们只能找到其中的一个最优解.

. .

我们再来看例4-5.原问题的代数模型如下：



minfP

1

d

1



P

2

d

2

P

3

d

3



x

1

x

2

d

1



d

1



10







2x

1

x

2

d

2

d

2

26

s.t.







x

1

2 x

2

d

3

d

3

6



x,x0,d



,d



0,(i1,2,3)

ii



12

该问题的电子表格模型及求解过程如图13-29所示.

图 13-29

该问题的建模及求解过程.包括模型中所涉及的单元格公式的解释与例3-4

基本相同.但本模型中只有目标约束而没有普通约束.通过求解发现该问题的三

级目标中.只有第一级的目标被实现.而其他两级目标均未实现.当决策变量的取

值



x

1

,x

2





(10,0)

时.

d

1



0

而

d

2



取值最小为6.

如果将目标约束2的期望值由26降至14.再重新求解.则三级目标均可实现.

此时问题的最优解为



x

1

,x

2



(4.4,5.2)

.结果如图13-30所示.



. .

图 13-30

第六节 网络优化问题

许多网络最优化问题实质上是线性规划问题的特殊类型．比如运输问题和

指派问题.都可以用网络规划来描述．而本节所讨论的典型的网络优化问题如：

最小费用流问题、最大流问题以及最短路问题等也可以转化为特殊的线性规划问

题．因此对于许多小型的网络优化问题.我们仍有可能利用Excel 的“规划求解”

加以解决.而对于较大型的问题.可以利用其他线性规划的商业软件包中的网络

单纯形法来处理.

一、最小费用流问题

我们首先从一个例子开始.例6-12中的图6-19给出了最小费用流所需的网

络.在解决这个问题前.我们先来介绍一些有关最小费用流的术语.

1．最小费用流问题的模型可以用带有通过其中的流的网络来表示.网络中

的圆圈被称为节点.箭头称为弧.

2．如果节点产生的净流量（流出减去流入）是一个确定的正数的话.这个

节点称为供应点（本例中节点1是供应点.其净流量为7）.

3．如果节点产生的净流量是一个确定的负数的话.那么这个节点就称为需

求点（本例中节点6就是需求点.其净流量为-7）.

4．如果节点产生的净流量恒为零.那么这个节点就称为转运点（本例中节

点2至5均为转运点）.

6．允许通过某一条弧的最大流量称为该弧的容量（本例中.每条弧旁括号

中的前一个数字表示了该弧的容量）.

7．通过某一条弧的单位流量均产生一定的费用.称为单位成本（本例中.

每条弧旁括号中的后一个数字表示了该弧的单位成本）.

一般来说.最小费用流问题具有如下特征：

1．最小费用流问题都至少有一个供应点和一个需求点.其余所有节点均为

转运点.

. .

2．通过弧的流只允许沿着箭头的方向流动.通过弧的最大流量取决于该弧

的容量.

3．网络中有足够的弧提供足够的容量.使得所有在供应点中产生的流都能

够到达需求点.

4．在流的单位成本已知的前提下.通过每一条弧的流的成本和流量成正比.

5．最小费用流问题的目标是在满足给定需求（即流量一定）的条件下.使

得通过网络运输的总成本最小.

解最小费用流问题.实际上是要确定每一条弧上的流量.这个流量不应超过

该弧的容量.并使总的运输成本最小.此外.转运点的净流量应为零.而供应点的

总流出量应等于需求点的总流入量.

按照上述要求.我们来建立最小费用流问题的电子表格模型.并利用“规划求

解”对其求解.

图13-31的

上半部分给出了

该问题的电子表

格模型.该模型

由两张表构成.

第一张表给出与

网络中的弧有关

的数据及限制.

首先将以节点的

序号表示的网络

中的所有弧列在

B和C两列.起

图13-31

始点的序号按由小到大的顺序列在B列.终点的序号列于C列；数据单元格（F4：

F12）和（G4：G12）分别是对应于某一弧的容量限制和单位成本；可变单元格（D4：

D12）给出了通过弧的流量.是需要通过求解模型来确定的量.其初始值可设为0.

显然.某一条弧的流量不应超过其容量.E列的“



”显示了这种关系.模型的第二

张表则给出了关于网络中节点的限制.将网络中所有的节点序号列于单元格（I4：

. .

I9）；数据单元格（L4：L9）给出了对应节点的净流量限制.供应点和需求点的净

流量分别为7和-7.转运点的净流量为0；输出单元格（J4：J9）是各节点的实

际净流量.某一节点的净流量等于该节点的流出量减流入量.如节点2的净流量

就等于弧（2.3）和（2.4）的流量减去弧（1.2）的流量.即J5=D6+D7-D4；其他

各节点的实际净流量公式如图13-30的左下部分所示.K列显示它们应等于净流

量的限制值.

该问题是求使总运费最小的各弧流量.目标单元格D14给出了总费用的计

算公式.它等于各弧实际流量与对应的单位成本乘积的和.公式如图13-30左下

角所示.

图13-31的右下部分显示了“规划求解”对话框的内容以及选项对话框的

内容.约束包括两类.即弧的容量限制约束和节点的净流量限制.最小费用流问题

仍属于线性规划问题.而弧中的流量不应小于零.所以选项对话框中仍选择采用

线性模型和假定非负.

点击求解键后得到该问题的最优解.如图13-31：

流量：

f

12

7,f

13

0,f

23

5,f

24

2,f

34

5,f

35

0,f

45

5,f

46

2,f

56

5.

最小费用：

b(f*)91

二、网络最大流问题

最大流问题的特征与最

小费用流问题的特征是非常

相似的.但它们之间也有一些

细微的差异.

我们以例6-10为例进行

讨论.图13-32给出了以图

13-31的形式描述的该问题的

电子表格中模型.这个模型与

图13-31模型基本构成是相同

的.其主要区别是它的目标发

生了变化.由于目标不再是使

图13-32

. .

得网络中流的总成本最小.因此我们删除了图13-31中的G列.目标单元格D14

中的数据是由节点

v

s

流出的流量.由于流量的是不确定的.所以除了转运点的净

流量必须为0.节点

v

s

和

v

t

的流量不需要限制.从“规划求解”对话框中可以看出

可变单元格为D4：D12.即弧的流量；约束为容量及节点的流量限制；目标为求

流量的最大值.由于最大流仍属于线性规划问题.故在选项中仍选择使用线性模

型和假定非负.对该模型求解的结果是：

流量：

f

s1

3,f

s2

2,f

12

0,f

13

3,f

24

2,f

41

0,f

43

0,f

3t

3,f

4t

2.

最大流量：

f*5.

网络最大流问题有如下的假设.

1．网络中所有流起源于一个节点.这个节点叫做源.所有的流终止于另一个

点.这个节点叫做汇.（本例中

v

s

为源.

v

t

为汇）

2．其余所有的节点叫做转运点.转运点的流入量等于流出量.（如节点

v

1

、

v

2

、

v

3

、

v

4

都是转运点.）

3．通过每一个弧的流只允许沿着弧的箭头所指方向流动.由源发出的所有的

弧背向源.而所有终结于汇的弧都指向汇.

4．最大流问题的目标是使得从源到汇的总流量最大.这个流量的大小可以用

两种等价的方法来衡量.分别叫做从源出发的流量和进入汇的流量（图13-31中

的单元格D4=I4使用的是从源点出发的方法）.

三、最小费用最大流问题

如果同时考虑网络的流量以及费用问题就是最小费用最大流问题．所谓最小

费用最大流问题就是：给了一个带收发点的网络.对每一条弧

v

ij

.除了给出了容

量

c

ij

外.还给出了这条弧的单位成本

b

ij

.要求一个最大流

f

.并使得相应的总运

输费用最小.

最小费用问题要求网络的流量是确定的.因此.最小费用最大流问题的解法

是先不考虑费用.将其作为最大流问题处理；求出问题的最大流后.再利用最小费

. .

用问题的解法.求出该最大流对应的最小费用.

图13-33是对图13-31的网络流问题求其相应的最小费用最大流．从图中的

电子表格模型可以看出.其求解的过程是分两部分进行的：

图13-33

1．先按照求网络最大流的方法.求出该网络的最大流量；

2．以求得的最大流量为确定流量.按照求最小费用流的方法求其对应的最小

费用流及相应的最小费用.

从图上可以看出.最小费用最大流问题在电子表格中建立了两个模型.即最

大流模型及最小费用模型.通过求解第一个模型得到该网络的最大流量为17；再

以17为流量利用第二个模型求出其相应的最小费用为311．比较两个模型的求

解结果发现.两个最优解对应的各弧的流量是相同的（由于即使在有多重最优解

的情况下.电子表格也只能找到一个最优解.所以这种情况下不能确定最大流问

. .

题有几个最优解）.但有时两个模型的最优解是不同的.这意味着最大流问题有多

重最优解.而通过求解第二个模型得到了相应的费用最小的那个最优解.

四、最短路径问题

最短路径问题的最普遍的应用是在网络中的两个点之间寻找最短路．因此.

最短路径问题都有如下假设：

1．在网络中选择一条路.这条路始于某一节点.这节点叫做起点.它终于另一

个节点.这个节点叫做终点.

2．连接两个节点的连线通常叫做边（允许双方向行进）或弧（只允许沿着

箭头所指方向行进）.

3．和每条边（弧）相关的一个非负数.叫做该边（弧）的长度.

4．目标是为了寻找从起点到终点的最短路（总长度最小的路）.

首先来分析例6-7.我们希望找到从

v

1

到

v

7

的最短路线．图中给出了从

v

1

到

v

7

途经的所有中间节点以及连接节点之间弧及其长度.

观察最短路问题的特点.我们发现它实际上可以被认为是最小费用流问题的

一种特殊类型.在最短路问题中.起点相当于供应量为1的供应点.终点相当于需

求量为1需求点.所有其余的节点都是转运点.所以每一个所产生的净流量为0；

弧的长度可以看作是网络中流的单位成本；如果我们选择的路经过某一特定的弧.

则认为该弧的流量为1.否

则流量为0.这样一来.使

某条路的总长度最短就等

价于网络流的总费用最小.

因此.我们可以用处理最小

费用流的方法处理最短路

问题.

图13-34是按照上述解

释给出的例6-7最短路问

题的电子表格模型及其求

解过程.该模型与图13-31

. .

图13-34

模型的主要区别在于各弧的容量没有了限制.但弧的流量变成了0-1变量.因此

约束条件中包含了H4：H15二进制的限制；另外.图13-31中G列的单位成本被

本模型E列中各弧的距离取代了.

除此之外.图13-34最短路模型的形式基本与图13-31的最小费用流问题的

模型一致.可变单元格（D4：D15）给出流量为1.表示对应的弧被选为从

v

1

到

v

7

的

路.为0则没被选中.目标单元格D17给出了该路线的总长度.B列和C列给出了

所有的弧.J列显示了每个节点需要产生的净流量.使用该图左下角的公式后.将

H列每一个单元格都加上流出量并减去流入量.得到通过该节点的实际净流量.

对应的限制条件.即H4：H10=J4：J10.在“规划求解”对话框中作定义.在“选

项”对话框中仍选择“采用线性模型”和“假定非负”.

通过求解在模型中的D列显示了那些流量为1的弧就是最短路径中的弧.即

最短路径为.

v

1

→

v

2

→

v

3

→

v

5

→

v

6

→

v

7

.长度为13.

(戴力辉)

. .

2024年4月7日发(作者：嬴心怡)

第十三章 运筹学问题的Excel建模及求解

学习运筹学的目的在于学会用运筹学的方法解决实践中的管理问题.注重学

以致用.很多实际问题利用人工计算要经过长时间的艰苦工作才能完成甚至根本

无法求解.但若使用运筹学软件则瞬间就能解决.因此在学习过程中不仅要掌握

运筹学的基本理论和计算方法.还要充分利用现代化的手段和技术.

微软的电子表格软件（Microsoft Excel）为展示和分析许多运筹学问题提

供了一个功能强大而直观的工具.它现在已经被应用于管理实践中.

本章将重点介绍如何建立和求解规划问题的电子表格模型.对于解决大量的

中、小规模的实际规划问题.电子表格软件是远远优于传统的代数算法的.

第一节 Excel中的规划求解工具

本节中.我们将举例说明如何使用微软Excel以电子表格的形式建立线性规

划模型.并利用Excel中的规划求解工具对模型求解.

一、在Excel中加载规划求解工具

要使用Excel应首先安装Microsoft

Office.然后从屏幕左下角的[开始]—

[程序]中找到Microsoft Excel并启动.

在Excel的主菜单中点击[工具]—[加载

宏].选择“规划求解”.如图13-1所示.

点击[确定]后.在工具菜单中将增加[规

划求解]选项.

图 13-1

二、在Excel中建立线性规划模型

我们以例2-1为例说明如何在电子表格中建立该问题的线性规划模型.建立

电子表格模型时既可以直接利用问题中所给的数据和信息.也可以利用已建立的

代数模型.本例的代数模型为：

. .

目标函数

max Z200x

1

300x

2



2x

1

2x

2

12



x2x8

12





s.t.



4x

1

16



4x12

2







x

1

,x

2

0

图 13-2

图 13-3

图13-2显示了将该例的数据转送到电子表格中后所建立的电子表格数学模

型（本例是一个线性规划模型）.其中显示数据的单元格称为数据单元格.包括生

产每单位药品Ⅰ和Ⅱ所需要的4种设备的台时数（单元格C5：D8）.药品Ⅰ和Ⅱ

的单位利润（单元格C9：D9）.4种设备可用的台时数（单元格G5：G8）.

我们要做的决策是两种药品各生产多少；对这一决策的约束条件是生产两种

药品所需的4种设备台时的限制；判断这些决策的优劣程度的指标是生产这两种

药品所获得的总利润（决策目标）.

如图13-3所示.将决策变量（药品Ⅰ、Ⅱ的产量）分别放入单元格C10和

D10.正好在两种药品所在列的数据单元格的下面.由于不知道这些产量会是多少.

故在图13-3中均设为零（空白的单元格默认取值为零.实际上.除负值外的任何

一个试验解都可以）.以后在寻找产量最佳组合时这些数值会被改变.因此.含有

需要做出决策的单元格称为可变单元格.

两种药品所需的4种设备台时总数分别放入单元格E5至E8.正好在对应数

据单元格的右边.由于所需的各种设备台时总数取决两种药品的实际产量.如：

E5=C5×C10+D5×D10（可直接将公式写入E5.也可利用SUMPRODUCT 函

数.E5=SUMPRODUCT（C5：D5.C10：D10）.此函数可以计算若干维数相同的数组的

彼此对应元素乘积之和）.因此当产量为零时所需各种设备台时的总数也为零.

由于E5至E8单元格每个都给出了依赖于可变单元格（C10和D10）的输出结果.

它们因此被称为输出单元格.作为输出单元格的结果.4种设备台时数的总需求

. .

量不应超过其可用台时数的限制.所以用F列中的



来表示.

两种药品的总利润作为决策目标进入单元格E9.正好位于用来帮助计算总

利润的数据单元格的右边.类似于E列的其他输出单元格.E9 = C9×C10+D9×D10

或E9 = SUMPRODUCT（C9：D9.C10：D10）.由于它是在对产量做出决策时目标值

定为尽可能大的特殊单元格.所以被称为目标单元格.

根据对上述建模过程的总结.在电子表格中建立线性规划模型的步骤可归纳

如下：

1．收集问题的数据.并将数据输入电子表格的数据单元格；

2．确定需要做出的决策.并且指定可变单元格显示这些决策；

3．确定对这些决策的限制（约束条件）.并将以数据和决策表示的被限制的

结果放入输出单元格；

4．选择要输入目标单元格的以数据和决策表示的决策目标.

三、应用电子表格求解线性规划模型

上例的求解过程可通过在Excel的工具菜单中选择“规划求解”开始.“规

划求解”对话框如图13-4所示.

“规划求解”开始前.可通过

键入单元格地址或选中单元格

的方式确定模型的每个组成部

分设置在电子表格的何处（单击

暂时隐藏对话框.再从工作表

中选定单元格.然后再次单击

）.如目标单元格地址为E9.可变单元格

地址范围为C10：D10.并选中最大值（M）

表示要最大化目标单元格.

约束条件的设定可通过点击对话框中的

图 13-5

图 13-4

“添加”按钮.弹出图13-5所示的添加约束对话框.由于各种设备台时的总需求

量均不应超过可用台时数的限制.故单元格E5到E8必须小于或等于对应的单元

格G5到G8.即在添加约束对话框的左端输入范围E5：E8（可用选中单元格的方

. .

式）.中间选择<=（点开下拉列表进行选择）.右端输入范围G5：G8.如果模型中

还包含其他类型的函数约束.则可点击“添加”按钮以弹出一个新的添加约束对

话框.根据输出单元格与约束值之间的关系在对话框中间的下拉列表中选择适当

的约束类型.以增加新的约束.但本例中已无其他约束了.所以只要点击“确定”

按钮返回“规划求解”对话框.如果需要修改或删除已添加的约束.可选中该约束

后点击“更改”或“删除” 按钮.

到现在为止“规划求解”对话框

已根据图13-3的电子表格描述了整

个模型（见图13-4）.但在求解模型

前还需要进行最后一个程序.点击“选

项”按钮弹出图13-6所示的选项对话

框.这个对话框中是一些关于如何求

解问题的细节的选项.对于决策变量取

图 13-6

值非负的线性规划模型.最主要的选项是“采用线性模型”和“假定非负”选项.

（见图13-6）.关于其他选项.对小型问题来说接受图中所示的默认值通常比较

合适.点击“确定”按钮返回“规划求解”对话框.

现在可以点击“规划求解”对话框中的“求解”按钮了.它会在后台开始对

问题进行求解.对于一个小型问题.几秒钟之后“规划求解”就会显示运行结果.

如图13-7所示.它会显示已经找到了一

个最优解.如果模型没有可行解或没有最

优解.对话框会显示“规划求解找不到可

行解”或“设定的单元格值不能集中”.

图 13-7

对话框还显示了产生各种报告

的选项.后面将会介绍.选择“保

存规划求解结果” 并点击“确

定” 按钮.返回电子表格模型.

求解模型之后.如图13-8所

示.“规划求解”用最优解和最

图 13-8

. .

优值代替了可变单元格和目标单元格中的初始值.因此.最优解是生产4公斤药

品Ⅰ和2公斤药品Ⅱ.最优值为1400元.与图解法的结果一致.

图13-9显示的是例2-2的电子表格模型及求解过程.

图 13-9

这个问题的电子表格模型建立与求解过程与例2-1描述的基本相同.数据单

元格（C5：E8）、（C9：E9）和（H5：H8）分别存放三种原料

B

1

、B

2

、B

3

每斤所含

四种营养成分的数量、每斤原料的单价以及食品所要求的最低营养成分的含量限

制.可变单元格（C10：E10）存放三种原料配比情况（图13-9的左上部分）.输

出单元格（F5：F8）给出了食品中实际的营养成分含量.目标单元格（F9）显示

了该种食品的总成本（图13-9的左下部分）.

图13-9的右下角显示了“规划求解”对话框的主要部分.包括为目标单元格

和可变单元格设定的地址.约束条件F5



H5.F6



H6.F7



H7和F8



H8通过“添加

约束”对话框显示在“规划求解” 对话框中.由于目标是最小化总成本.所以选

择了“最小值（N）”.

图13-9的右上角显示了点击“规划求解” 对话框的“选项”按钮后所选择

的选项.“采用线性模型”先期定义了这个模型是线性规划模型.“假定非负”选

项定义了可变单元格必须是非负约束.因为食品的配比不可能出现负值.

点击“规划求解” 对话框的求解按钮后.得到了图13-9中电子表格的可变

单元格中显示的最优解.即该食品配比为原料

B

1

是1.94斤.原料

B

3

是2.36斤.

成本为109.72元.与单纯形法人工求解不同.如果输出单元格、可变单元格或目

标单元格结果不是整数.电子表格是以小数而非分数形式显示的.本例结果以四

. .

舍五入的方式保留了两位小数.

第二节 线性规划的应用问题

一、合理用料问题

这是第二章第五节的第一个问题.由于原料胶管的长度为15分米.而输液

管、止血带和听诊器胶管分别长5.7、4.2和3.1分米.所以每根原料胶管最多可

截三种材料依次为2根、3根和4根.即总的截法不超过3×4×5 = 60（种）.

又由于每种截法的料头不能超过2分米.所以可先通过电子表格进行试算以选择

其中可行的几种截法.再利用线性规划的方法找出用料根数最少的方案.如图

13-10的左上部分所示.单元格C4至E4显示三种胶管的长度；C5至E5输入不同

的方法截出每种胶管的根数；F4为对应C5至E5的不同截法所剩料头的长度. F5

通过判断剩余料头的长度是否在0到2之间显示出该种解法是否可行.单元格F4

和F5的公式见图13-10的左下部分.

图 13-10

不断变换C5至E5的可能取值并选择其中可行的截法（共6种）.在电子表

格中建立该问题的线性规划模型.数据单元格为C9：H11、C12：H12和K9：K12.

分别显示每种截法截一根原料胶管时得到三种不同材料的数量、每种截法截取一

次所用胶管的数量和三种材料的需要量；可变单元格C13：H13显示采用每种截

法所截的胶管原料数；输出单元格I9：I12列出了某一截取方案实际获得的三种

材料数量.每种材料的数量等于各种截法截得该材料数与对应截法所截原料数的

乘积之和.如输液管的数量I9 = SUMPRODUCT(C9:H9,C13:H13)；目标单元格I12

. .

为总用料数.应等于各种截法所截原料数之和,即I12 = SUM(C13:H13).

图13-10的右半部分显示了“规划求解”对话框及“选项”对话框的内容.

该问题的目标是所用的胶管原料的总根数最少.因此设置目标单元格为I12等于

最小值.由于实际获得的材料数量必须满足需求量的要求.考虑到最优方案（各种

截法的某一组合）不一定能使截出的三种材料数量恰好等于需要的数量.而某种

材料超过需求量是允许的.故在添加约束时可设置实际截得的数量大于等于需求

量.即I9：I12>=K9：K12（本题中.该约束取“>=”和“=”的结果是相同的）；

又由于截出的各种材料数量均为整数.因此约束中应包括决策变量取整数的限制.

即C13:H13=整数.

图13-10的左上部分显示了该问题的最优方案为：分别用第二种、第四种和

第五种截法截取原料40、60和10根.共用原料110根.与第二章中用大

M

法求

解的结果一致.

二、放射科的业务安排

图13-11显示了第二章问题二的电子表格模型及求解过程.该问题的数据包

括：进行三种检查

的单位时间（C5：

E5）.三种检查设备

每月的可用时间

（C9：E9）.三项业

务每月最多提供量

（H6）以及每项业

务的单位利润

（C10：E10）.可变

单元格为C6至E6.

图 13-11

给出三项业务每月的实际发生数量.输出单元格为C7至E7和F6.分别表示根据

各项业务的实际发生数量产生的设备使用时间及实际的总业务量.目标单元格

F10显示由每项业务的单位利润及每月实际发生数量计算的总利润.图13-11的

左下部分给出了输出单元格及目标单元格的公式.

. .

图13-11右下部分的“规划求解”对话框显示了求解时应注意的问题：求目

标单元格的最大值（利润最大）；约束为设备的实际使用时间小于等于设备的可

用时间及实际总业务量小于等于总业务提供量的限制.

打开“选项”对话框.仍选择“采用线性模型”和“假定非负”.回到“规划

求解”并按“求解”按钮.得到问题的最优方案为：每月X线及CT检查的业务量

分别为1320人次和480人次.磁共振业务量为0.即不必购买该设备；按最优方

案安排业务每月可获利55200元.

在电子表格上建立线性规划或其它问题模型的方式是非常灵活的.不必拘泥

于一种固定的模式.本书仅提供了一种建立模型的思路.读者可根据不同问题的

特点以及个人的习惯或喜好建立不同风格的电子表格模型.

第三节 线性规划的灵敏度分析

前面指出线性规划模型的许多参数.都只是对实际数据的大致估计.而不可

能在研究的时候就获得精确的数值.通过灵敏度分析可以得出每一个估计的数据

需要精确到何种程度.才能保持解的最优性.

回忆例2-1某制药厂的生产计划问题.其求解结果如图13-8所示.即生产4

公斤药品Ⅰ和2公斤药品Ⅱ.总利润为1400元.但该最优解是在假设所有的模型

参数都准确的前提下做出的.在此基础上.管理层如果进一步考虑下列问题：

1．如果在该厂生产的药品中.有一个单位利润的估计值是不准确的.将会发

生怎样的情况？

2．如果该工厂两种药品的单位利润的估计都是不准确的.又将会怎样？

3．如果改变该厂某种设备可用于生产的时间.会对结果产生什么影响？

4．如果四种设备可用于生产的时间同时改变.又会对结果产生何种影响？

在本节中.我们将重点介绍如何利用“规划求解”中的“敏感性报告”对目

标函数系数

c

j

以及约束条件右端值

b

i

的变动进行灵敏度分析.分析的内容主要是

系数在什么范围内变化时.已得到的最优解保持不变.即发现哪些系数不太敏感

（由于在较大范围内变化时.最优解保持不变.故可以进行粗略估计）.哪些系数

比较敏感（即使微小的改变都会对最优解产生影响.故必须对其精确定义）.

. .

一、目标函数系数变动的灵敏度分析

首先介绍目标函数系数的灵敏度分析.回顾一下就可以知道.这些系数表示

各种决策对总目标的单位贡献.下面以例2-1某药厂的生产计划问题的目标函数

系数变动情况进行讨论.

问题1：如果该药厂一种药品的单位利润的估计是不精确的.结果怎样？

首先看一下.如果药品Ⅱ的单位利润300元的估计是不精确的情况.假设：

药品Ⅱ的单位利润 = 电子表格中D9单元格中的数据

现在.

c

2

=300元.下面我们来分析一下在保持最优解

(x

1

,x

2

)(4,2)

不变的

条件下.

c

2

可能的最大值与最小值.这样.也就可以看出

c

2

为300元的这一估计能

够在多大程度上偏离实际值而不会改变解的最优性.

（一）使用电子表格进行灵敏度分析

电子表格的一个强大的优点就是可以方便互动地展开各种形式的灵敏度分

析.通过运用规划求解工具来求解最优解.模型参数值的改变所造成的影响一下

子就可以显示出来.

为了说明这一点.图13-12显示了药品Ⅱ的单位利润从开始的

c

2

=300元降到

c

2

=250元的情况.与图13-8相比.最优解没有丝毫的变化.事实上.该问题唯一的

变动是电子表格中C9单元格

中的数据从300元降到250

元.以及E9单元格总利润减

少了100元（因为每单位药

品Ⅱ所提供的利润减少了50

图 13-12

元）.因为最优解没有变动.

我们可以知道在不影响最优

解的前提下.药品Ⅱ的单位利

润

c

2

=300元的最初估计是较

高的.

图 13-13

. .

那么.如果这一估计值较低又会怎样呢？图13-13表示了将

c

2

=300元增加到

c

2

=350元的情况.同样.最优解没有发生变化.

因为.增加或减少最初的

c

2

=300元均不会对最优解产生任何影响.

c

2

就不是

很敏感的系数.也就不需要为了保证最优解不会改变.而花很大力气去得到

c

2

的

更精确的值.但是对

c

2

的研究至此并没有结束.因为实际值很可能会超出250到

350元这一范围.那么在保持最优解不变的条件下.

c

2

到底可以在什么样的范围

内取值呢？当然可以在电子表格中采取试验的方法.不断增加或减少的

c

2

值.直

到最优解发生改变.以找到最优解发生变化时对应的

c

2

值.但是.这样计算太麻烦

了.是否有简便一些的方法呢？答案是肯定的.

（二）利用敏感性报告进行目标系数的灵敏度分析

如图13-7所示.在求得最优解之后.规划求解工具会给出相应的信息.同时.

在其右边列出了它可以提供的三个报告.选择第二项敏感性报告的选项.就可以

得到灵敏度的分析报告.它显示在模型的工作表之前.

图13-14显示了本例敏感性报告中的一部分.终值一栏表明了问题的最优解.

第二栏给出了递减成本.递减

成本提供了为使决策变量取

正值.相应的目标系数需要减

图 13-14

少的数量.对于本例.由于两决策变量的取值均为正数.故递减成本均为零.第三

栏表示了目标函数的现值.最后两栏表示为使最优解保持不变.目标系数允许增

加与减少的最大值.

例如.考虑决策变量

X

1

的目标系数

c

1

.从图13-14中表示产品Ⅰ的一行中可

知.

c

1

可以减少50.可以增加1E+30.在电子表格中1E+30是10

30

的缩写.Excel使

用这一极大的数值来表示无穷大.因此.从灵敏度的分析报告中可知：

c

1

的现值： 200

c

1

的允许增加值： 无穷大 此时

c

1

无上限

. .

c

1

的允许减少值： 50 此时

c

1

20050150

c

1

的变化范围：

c

1

150

因此.只要在上面的变化范围内变动.并且不改变模型的其他任何内容.最优

解将始终保持在

(x

1

,x

2

)(4,2)

不变.该药厂的另一药品的单位利润的变化范围

也可以用同样的方法得出.

c

2

是药品Ⅱ的单位利润.表中表示药品Ⅱ的第二行给

出了下面关于

c

2

的信息：

c

2

的现值： 300

c

2

的允许增加值： 100 此时

c300100400

2

c

2

的允许减少值： 300 此时

c3003000

2

c

2

的变化范围：

0c400

2

目标函数的两个系数的允许变化范围都很大.因此.尽管药品Ⅰ和药品Ⅱ的

单位利润可能仅仅是实际值的一个粗略估计.我们也可以相信.这个估计值对最

优解的正确性不会有影响.

但在一些线性规划模型中.目标系数微小的变动都可能会影响最优解.这样

的系数称为敏感参数.灵敏度的分析报告中会直接显示目标中哪些系数是敏感的.

这些系数允许的变化区域很小.因此.必须格外小心.尽量取得这些数据的精确

值.

在求得模型的最优解之后.目标系数的允许变化范围还有一个很重要的用途.

在问题的线性规划分析结束之后.如果外界的环境发生了一定的变化.灵敏度分

析可以在无需重新求解的情况下.表明模型参数的变化是否造成了最优解的改变.

例如经过一段时间以后.如果药品的单位利润发生了较大的变化.通过其允许变

化范围.可以一眼看出原来的最优组合是否依然适用.有了目标系数的允许变化

范围.在判断问题时.就不需要重新建模与求解.这一点对线性规划问题的解决是

有很大帮助的.特别是在处理一个大型模型时.

（三）目标系数的同时变动

因为存在许多不确定性因素.目标函数系数的值.如单位利润.通常都只是对

. .

实际值的估计.上面所讨论的是只有一个系数变动时的情况.这类问题在求解一

个系数的允许变化范围时.假设其他所有系数都是正确的.研究的系数是唯一可

能与实际值不符的变动的系数.但事实上.所有的系数（至少一个以上）可能同时

都是不准确的.如果这样的话.是否可能会导致求得的最优解不正确呢？这是最

关键的问题.如果可能对最后的结果产生影响.就必须对这些系数作进一步的分

析.另一方面.如果灵敏度分析表明目前的参数估计不会影响最优解的正确性.那

么.管理者可以增加对该模型及其所提供的解决方法的信心.

以下将介绍如何在不重新求解模型的条件下.确定如果目标函数的几个系数

同时变化.可能造成的对最优解的影响．我们仍利用例2-1提出如下问题：

问题2：如果该药厂两种药品的单位利润的估计都是不准确的.将会对结果

产生怎样的影响？

例如.原来药品Ⅰ和药品Ⅱ的单位利润分别为200元和300元.现在由于原料

成本的变化.每公斤药品Ⅰ和药品Ⅱ的单位利润分别变为180元和355元.最优解

是否发生变化？在分析多个系数同时变动的情况时.仍然要使用敏感性报告中提

供的每个系数的允许增加值和减少值数据.下面介绍多个系数同时变动的百分之

百法则.

首先定义

c

j

的允许增加（减少）百分比为

c

j

的增加量（减少量）除以

c

j

的

允许增加量（允许减少量）的值.这样我们可以计算出

c

1

的允许减少百分比为

(200180)/5040%

.

c

2

的允许增加百分比为

(355300)/10055%

.

c

2

的允

许减少百分比与

c

2

的允许增加百分比之和为

40%55%95%

.

目标函数系数同时变动的百分之百法则：如果目标函数的系数同时变动.当

其所有允许增加百分比和允许减少百分比之和不超过百分之百时.最优解不会改

变.如果超过百分之百.则不能确定最优解是否改变.

因为本例中

c

1

的允许减少百

分比与

c

2

的允许增加百分比之和

为95%不超过100%.所以当每公斤

药品Ⅰ的利润减少为180元.每公

图 13-15

. .

斤药品Ⅱ的利润增加为355元时.此线性规划最优解仍然为药品Ⅰ生产4公斤和

药品Ⅱ生产2公斤（即

x

1

4,x

2

2

）.此时有最大利润为

180435527207101430

（元）.如图13-15所示.

这一法则并没有表示出.在变动百分比之和超过百分之百的情况下.可能的

结果.这一结果还有赖于系数变动的方向.但是.只要变动百分比之和不超过百分

之百.最优解是肯定不会改变的.记住.我们可以让单一的目标函数系数在整个允

许范围内变动.但这只有在其他目标函数系数都不变的情况下才有效.如果多个

系数同时变动.我们必须研究各个系数的变动百分比.

二、约束右端值的灵敏度分析

之所以要分析函数约束右端值变动的原因与前面一样.因为在建模时.还不

能得到模型的这些参数的精确值.只能对其作粗略的估计.因此.我们希望知道在

这些估计不准确的情况下会产生怎样的后果.除此之外一个更主要的理由是因为.

这些常数（通常代表资源的可用量）往往不是由外界决定的而是管理层的政策决

策.因此管理者希望知道如果改变这些决策是否会提高最终的收益.影子价格分

析就是为管理者提供这方面的信息.

下面是关于例2-1的第三个问题：

问题3：如果改变该厂某设备可用于生产的时间.结果将如何？

（一）约束右端值的影子价格分析

回忆第二章中关于影子价格的经济含义.我们知道影子价格代表单位资源在

最优利用的条件下所产生的经济效果.即在模型获得最优解的情况下.约束条件

右端值在一定范围内每增加（减少）一个单位.使目标函数值增加（减少）的量.

其中.一定范围是指保持影子价格不变的右端值变化范围.

在影子价格分析中.每次分析一个函数约束.可以将该函数约束右端值的常

数增加一个单位后重新求解.观察目标函数值增加的量来确定影子价格.也可以

利用灵敏度报告中提供的关于每一个函数约束的影子价格数据.

从一个约束的影子价格中就可以直接看出.决策改变而引起的约束常数的

改变所造成的影响.只要约束常数的变动不大.那么目标函数值的变动就等于约

束常数的变动（正或负）乘以影子价格.为了说明影子价格的含义.我们以第二章

. .

第五节中的第二

个应用.即放射科

的业务安排问题

为例来加以讨论.

该问题最初的线

性规划模型如图

13-16上半部分所

示.单元格H6及

C9至E9中的值

图 13-16

1800.300.120.12

0分别表示总业务提供量以及三种设备的可用时间的限制.可变单元格C6至E6

中的最优解表明放射科每月安排1320人次的X线检查和480次的CT检查.目标

单元格F10显示如此安排后每月的总利润为55200元.

得到这些信息后.科室的领导可能希望知道增加一单位资源的可用量对总利

润的影响.即影子价格.首先从业务提供量H6开始分析.图13-16的下半部分表示

了放射科可以提供的业务量由1800增至1801时.对结果的影响.将图13-16上下

两表中的目标单元格H10进行对比.可看出利润的增加量为：

利润的变化量 = 55220元-55200元 = 20元

从而计算出业务提供量的影子价格为20元/每人次.即增加1人次的业务提

供量对总利润的贡献是20元.

用上述方法计算影子价格简单明了.但需要对每个约束进行试算.且有时可

能得到错误的结果（后面将讨论）.此外.我们还可以采用“规划求解”结果给出

的敏感性报告直接得到各个约束的影子价格.图13-17显示了灵敏度分析中与函

数约束有关的部分.其中的第四栏给出了各约束的影子价格.结果如下：

业务提供量的影子价格 = 20元/人次

X线检查的影子价格 = 0 元/小时

CT检查的影子价格 = 160元/小时

磁共振检查的影子价格 = 0元/小时

. .

图 13-17

这些影子价格都是资源增加一个单位引起的总利润的增加量.为什么X线检

查的影子价格为0？可以通过比较图13-16上表中C7和C9来说明.X线检查设备

的可用时间有300小时.而按最优解的业务量使用该设备的时间仅为132小时.

已有168小时的闲置.因此.即使再增加设备的可用时间也不会改变最优解和总

利润.同样可以解释磁共振检查的影子价格也为0的原因.

（二）影子价格的灵敏度分析

图13-7的第六、七栏给出了每一约束限制值在什么范围内变化时.该约束的

影子价格是不变的.这一范围称为影子价格的有效区域.可以看出：

业务提供量的影子价格的有效区域的上限为：1800+1680=3480.下限为：

1800-1320=480.其有效区域为：

480b

1

3480

.即当业务提供量在此范围内变

化时.每增加（减少）一人次.总利润也会相应地增加（减少）20元；类似可得X

线使用时间、CT使用时间以及磁共振使用时间的影子价格有效区域分别为：

b

2

300168132

.

1201200b

3

120330450

.

b

4

1201200

.

我们再来看第二章的例2-1.该

问题最初的线性规划模型如图

13-8所示.G栏中的常数

（12.8.16.12）表示四种设备可用

的台时数.当我们将设备B的可用时

间从8小时增加到9小时时.我们发

图 13-18

现总利润增加了100元（从1400元增加到了1500元）.如图13-18所示.但100

元并不是设备B可用时间的影子价格.

图13-16显示了其敏感性报告的第二部分.终值栏给出了输出单元格E5至

E8的终值分别为12.8.16.8（如图13-8的E栏所示）；约束限制值一栏即表13-8

中G5至G8中的常数.从阴影价格一栏中可以看出.设备B可用时间的影子价格为

. .

150元.通过分析其影子价格的有效区域可知.可用时间在4—8小时之间时.每增

加（减少）一个小时的可用时间.总利润会相应增加（减少）150元.但由于设备

B的可用时间正好为8小时.

所以再继续增加1个小时的

可用时间后.约束限制值已

经超过了影子价格的有效

区域.故总利润的增加值只

图 13-19

有100元而不是150元.从图13-9中还可以看出.设备A和设备D的影子价格均

b

1

12

.

8b

3

16

.

b

4

8

. 为0.设备C的影子价格为12.5元.有效区域分别为：

（三）约束右端值同时变动的情况

函数约束右端值的有效区域表示的是.约束右端值的变动在有效区域内时.

该约束的影子价格就可用于评估约束右端值改变造成的影响.但必须注意的是.

只有在仅一个约束右端值变动而其他约束右端值均不变的情况下.该约束右端值

的有效区域才是完全有效的.而实际上.由于管理层在约束右端值上的决策往往

是相关的.因此约束右端值经常会同时变动.如果多个约束右端值同时变动.那么

如何评估可能造成的影响呢？

仍以放射科的业务安排问题为例.我们已经知道放射科已有X线及CT检查设

备.且CT检查设备使用时间具有最大的影子价格为160元.X线使用时间的影子

价格为0元.科室领导希望减少X线的可用时间而相应增加CT检查的可用时间.

假设减少X线的可用时间3小时可相应增加CT检查的可用时间1小时.在这种同

时变动的情况下.会产生怎样的后果呢？

根据影子价格分析.将X线的可用时间减少3小时.并将CT检查时间增加1

小时.所产生的结果如下：

CT检查时间： 120→121 总利润的变化量= 影子价格 = 160元

X线检查时间：300→297 总利润的变化量= - 影子价格×3=-0×3= -0元

总利润的净变化 =160元

但是.我们现在还不能确定.两个约束右端值这样改变以后.原先的影子价

格是否依然有效.

检验有效性的一种

. .

方便快捷的方法就是将这些数据代入电子表格的相应单元格中去.重新求解.图

13-20所示的电子表格显示出总利润的净增量确实为160元（从55200元增加到

55360元）.因此.影子价格在上面约束右端值同时变动的情况下是有效的.

如果我们继续减少

图 13-20

X线检查时间而相应增加CT检查时间.结果会如何呢？当然可以将数据代入电子

表格后再重新求解.但这种方法是不切实际的.特别是有两个以上的约束右端值

同时变动的情况.幸好.有与处理目标系数同时变动类似的百分之百法则.

约束右端值同时变动的百分之百法则：对于所有变化的约束条件右边常数值.

当其所有允许增加百分比和允许减少百分比之和不超过百分之百时.其影子价格

是有效的.其中约束右端值的允许增加（减少）百分比的定义同目标系数的允许

增加（减少）百分比一样.为约束右端值的增加量（减少量）除以约束右端值的

允许增加量（减少量）的值.

为了解释这一法则.仍然考虑图13-20的情形.将X线的可用时间减少3小时.

并将CT检查时间增加1小时.按照百分之百法则.计算如下：

CT检查时间：120→121

121120

占允许增加量的百分比

()100%0.03%

330

X线检查时间：300→297

占允许减少量的百分比

(

300297

)100%1.79%

168

总和

1.82%

因为变动百分比之和1.82%小于百分之百.所以用影子价格来预测这些变动

的影响是有效的.

上面求得的变动百分比之和为1.82%.表明即使将原先的变动扩大50倍也不

会使影子价格失效.

第四节 特殊形式的线性规划问题

在本节中.我们将重点讨论三类特殊类型的线性规划问题——运输问题、0-1

规划问题及指派问题的Excel模型及求解.

一、运输问题

. .

（一）运输问题的模型及参数

运输问题的描述见本教材第三章.

一般的运输问题（表2-1）就是要解决把某种产品从若干个产地调运到若

干个销地.在每个产地的供应量与每个销地的需求量已知.并知道各产销地之间

的运输单价的前提下.如何确定一个使得总的运输费用最小的方案.

实际上运输问题的模型在供应量和需求量两方面做出了如下的假设：

产销平衡假设：每一个产地都有一个固定的供应量.所有的供应量都必须运

输到销地；与之相类似.每一个销地都有一个固定的需求量.整个需求量都必须由

产地满足.即总供应量等于总需求量.

对于运输问题而言.当且仅当供应量的总和等于需求量的总和时.问题才有

可行解.

某些实际的问题并不符合产销平衡的假设.供应量实际上代表着所要运输的

产品的最大数量（而不是一个固定的数值）.需求量实际上也是代表着所接受的

最大数量（也不是一个固定的数值）.这些问题并不符合运输问题模型.所以它们

是运输问题的变形.

表3-1的中间部分给出了运送货物的单位运费.关于运费对于任何一个运输

问题都有下面的一个基本假设.

运输费用假设：从任何一个出发地到任何一个目的地的货物运费与所运输的

数量成线性比例关系.因此总运费就等于单位运费乘以所运输的数量.

运输问题所需要的数据仅仅是供应量、需求量和单位运费.这些就是模型参

数.所有的这些参数都可以总结在一个表格中.这个表格就叫做参数表.表3-1就

是典型的运输问题的参数表.而表3-3则是运输问题例3-1的参数表.

运输问题模型：如果一个问题可以完全描述成如表3-1所示的参数表形式.

并且符合产销平衡假设和运输费用假设.那么这个问题（不管其中是否涉及到运

输）都适用于运输问题模型.最终目标都是要使总运费最小.这个模型的所有参数

都包含在参数表中.

（二）运输问题的Excel模型及求解

在建立了运输问题的线性规划模型之后.我们可以使用Excel来描述和解决

. .

运输问题.以例3-1为例.首先.我们需要在电子表格中输入两个表格.第一个表

格是参数表.提供有关这一问题的所有参数；第二个就是求解表格.包含了从每个

医院到每个贫困县的人员安排情况.图13-21显示了这两个表格.以及求解本例

所需要附加的公式.

在这个电子表格中需要包含运输问题的两类约束.即供应约束和需求约束.

对于供应约束来说.图13-21求解表格中的H列算出了每家医院抽出的医务人员

总数.它是其相应行所有决策变量单元格数据的总和.例如.在H15单元格中的等

式就是“H15=D15+E15+F15+G15”或者是“H15=SUM（D15：G15）”.每家医院所能

抽出的人员数均包含在J列中.因此.H列的单元格中的数据应该等于相应的J列

的单元格中的数据.

对于需求约束来说.向每一个贫困县派出的医务人员总数在电子表格的第

18行列出.是其相应列的所有决策变量单元格数据之和.例如.D18=SUM（D15：

D17）.每县的实际需要人数在第20行中给出.

图 13-21

注：某省医疗队巡回医疗扶贫问题的Excel模型.图中从第3行到第9行显示了参数表.

从第12行到第20行显示了求解表格.本模型利用“规划求解”处理得到了最优的人员安排

计划.图的底部及右侧分别给出了输出单元格的公式以及建立“规划求解”所需要的说明.

H18单元格计算出了总费用.它是参数表和求解表主体部分每一相应单元格

乘积的和.即H18 = SUMPRODUCT（D6：G8.D15：G17）.

图13-21的右上半部分是“规划求解”对话框中输入的内容.这些内容说明

. .

了“规划求解”工具通过改变人员安排（决策变量单元格D15到G17）.按照派

到每一个贫困县的人员数量等于它的总需求量（D18：G18=D20：G20）以及从每

一所医院抽出的总人数等于其所能抽出的人员数（H15：H17=J15：J17）的约束

条件对总费用进行最小化处理（单元格H18计算出了结果）.图13-21的右下半

部分显示了“规划求解选项”.（采用线性模型）说明运输问题同样也是一个线

性规划问题.（假定非负）说明所有的决策变量（派出人员数）必须是非负的.

决策变量的值（派出人员数）在单元格（D15：G17）中.对于每一个单元格

来说.可以先输入任意数值（如0）或不输入（默认为0）.在按下“规划求解”

对话框的求解按钮后.“规划求解”工具就会确定出每一个决策变量的具体数值.

最优解及所得到的最小总费用如图13-21所示.

（三）其他运输问题的处理

前面的讨论都是以供销平衡为前提的. 对于产销不平衡的运输问题.即总需

求量与总供应量不相等的运输问题.显然是没有可行解的.因此.对于产销不平衡

的运输问题.我们可以先化为产销平衡的运输问题然后再求解.

将例3-1稍作修改.其参数表变为表13-1：

表13-1 修改后运输问题的人均费用

B

1

B

2

B

3

B

4

医院抽出人数

人均费用（单位：百元）

A

1

A

2

A

3

县需求人数

2 9 10 7 9

1 3 4 2 7

8 4 2 5 7

3 8 4 6 21 23

与例3-1比较.只是医院

A

2

的抽出人数增加了两人.这样一来总抽出人数为

23人.大于总需求人数21人.是一个产大于销的运输问题. 为此再建立一个假想

的县

B

5

.

B

5

的需求人数为2人.而从

A

1

、

A

2

、

A

3

派往

B

5

不需要花费.所以可令

c

15

c

25

c

35

0

.即对应的人均费用为0. 这样就得到了修改后问题的产销平衡

的参数表.将产大于销的运输问题化成了产销平衡的运输问题（见表13-2）.

表13-2 修改后产销平衡运输问题的人均费用

B

1

B

2

B

3

B

4

B

5

医院抽出人数

. .

人均费用（单位：百元）

A

1

A

2

A

3

县需求人数

2 9 10 7 0 9

1 3 4 2 0 7

8 4 2 5 0 7

3 8 4 6 2 23

利用电子表格对其求解.可得到如图13-22所示的最优解和最小总费用.

类似地.如果是销大于产的运输问题.则可以采用增设虚拟产地的办法使之

化为产销平衡的运输问题来处理.

产销不平衡的运输问题还有一种情况.一个销地同时存在着最小需求和最大

需求.于是所有在这两个数值之间的数量都是可以接收的.

图 13-22

在例3-1中将问题的要求作如下变化：各医院抽出的人员总数不变为21人.

而

B

1

、

B

2

、

B

3

、

B

4

四个县的最小需求人数分别为3、6、2、4人.最大需求分别为

5、9、5、6人.最大总需求人数为25人.由于总需求比可以抽出的人数多出4人.

为了化成产销平衡的运输问题.可在参数表中增加虚拟医院

A

4

这一行.可抽调人

数为4人.另外.为了区别必须满足的需求量（最小需求量）与可以不满足的需求

量.可将每个县分为两列.如

B

1

县的第一列为

B

11

.它的需求量是必须要满足的3人.

第二列为

B

12

.它的需求量是可以不满足的2人.显然.必须满足的最小需求不能从

虚拟的医院抽调人员.为了必须满足

B

11

的3人.我们将虚拟医院到

B

11

的人均费用

定为

M

（是一个足够大的正数）.如果虚拟医院抽调到

B

11

的员数为

x

41

0

.则为

. .

此付出的费用将为

Mx

41

.是个很大的正数.这显然不符合总费用最小的目标.这

样就保证了

x

41

0

.但对于

c

42

则可以定为0.因为虚拟的医院并没有抽出人员.人

均费用当然为零.又因为

B

12

的需求2人可以不满足.所以

x

42

可以为正数.另

外.

c

12

c

11

2

.

c

22

c

21

1

.

c

32

c

31

8

.对其他的三个县也进行了同样的处理.

该问题的参数表见表13-3.

表13-3 有最小需求的运输问题的人均费用表

B

11

B

12

B

21

B

22

B

31

B

32

B

41

B

42

医院抽出人数

人均费用（单位：百元）

A

1

2 2 9 9 10 10 7 7 9

A

2

A

3

1 1 3 3 4 4 2 2 5

8 8 4 4 2 2 5 5 7

A

4

县需求人数

M

0

M

0

M

0

M

0 4

3 2 6 3 2 3 4 2

在用电子表格对该问题建模及求解时.表中的

M

可以输入一个足够大的数.

如10000.如图13-23.

图 13-23

二、整数规划及0—1规划问题

（一）整数规划问题的计算机求解

. .

在线性规划问题中.最优解可能是整数.也可能不是整数.但对于某些实际问

题.要求决策变量必须取整数.即整数规划问题.如：

例13-1

maxz3x

1

x

2

3x

3



x

1

2x

2

x

3

4

.



4x3x1

23





s.t.



x

1

3x

2

2x

3

3



x,x,x0

123







x

1

,x

2

,x

3

为整数

.

利用电子表格对该整数规划问题求解的方法与线性规划问题类似.只是在

“规划求解”对话框的约束一栏中.增加对决策变量

x

1

,x

2

,x

3

的整数约束.利用电

子表格对该问题求解的结果见图13-24.

图 13-24

（二）0—1规划问题的计算机求解

以例3-2为例.根据其代数模型可建立如图13-5的电子表格模型：

图 13-25

该电子表格模型中可变单元格为（C7：F7）.其取值为1（0）时表示携带（不

携带）相应的物品.即决策变量为0—1变量.因此.应有决策变量为二进制的约束

. .

限制（见图13-25的左下部分）.该模型仅包含一个关于所携带物品重量的约束.

该同学所携带物品的总重量（显示在G5）为所携带的所有物品的重量之和.即G5

= SUMPRODUCT(C5:F5,C7:F7).其值不应超过背包的重量限制5.故有G5≤I5.其携

带物品的总价值（目标单元格）为G8 = SUMPRODUCT(C6:F6,C7:F7).在“规划求

解选项”对话框中.仍选择“采用线性模型”和“假定非负”.

读者可将例3-3作为练习.

三、指派问题

（一）指派问题的模型及计算机求解

指派问题既是0-1规划的特殊情况.也是与运输问题密切相关的一类特殊的

线性规划问题.其电子表格模型与运输问题类似.

指派问题也需要满足一些假设：

1．被指派者的数量和任务的数量是相同的.

2．每一个被指派者完成且只完成一项任务.

3．每一项任务必须且只能由一个被指派者来完成.

4．每一个被指派者和每一项任务的组合都会有一个相关的成本（收益）.

5．问题的目标是要确定怎样进行指派才能使得总成本达到最小（总收益最

大）.

以例3-4为例.我们需要确定的是将哪项化验任务指派给哪位化验员.能够

使所需总时间最少？该问题的电子表格模型见图13-26.

与运输问题类似.指派问题的模型也需要在电子表格中输入两个表格.即参

数表和求解表.参数表主体部分（D6：G9）给出了四位化验员分别完成四种化验

所需要的时间.而求解表主体部分（D16：G19.初值均为0）给出了具体的人员安

排情况.决策变量单元格取值为1或0时.分别表示指派或不指派某位化验员完成

某项化验.如D18=1表示指派丙完成化验A.而E16=0则表示不指派甲完

. .

图 13-26

成化验B（见图13-26的左上部分）.指派问题也有两类约束.提供量约束：根据

第二条假设.每位化验员只完成一项化验任务.即求解表中每一行的四个单元格

中.只能有一个为1.其余均为0.每行之和（列入单元格H16：H19）为1；需求量

约束：根据第三条假设.每种化验只能由一位化验员完成.即求解表的每列之和

（列入单元格D20：G20）为1.

H20单元格计算出了总时间.它是参数表和求解表主体部分每一相应单元格

乘积的和.即H20 = SUMPRODUCT（D6：G9.D16：G19）.

图13-26的右上半部分是“规划求解”对话框中输入的内容.除提供量约束

（H16：H19=J16：J19）和需求量约束（D20：G20=D22：G22）外.由于指派问题

的决策变量也为0—1变量.应有决策变量为二进制的约束.指派问题也属于线性

规划.故仍选择“采用线性模型”和“假定非负”.问题的最优解及所得到的最少

时间如图13-26所示.

例3-5是一个最大化的指派问题.其电子表格模型与例3-4完全一致.区别仅

在于“规划求解”对话框中.设置目标单元格等于“最大值”.

（一）指派问题的变形

我们经常会遇到指派问题的变形.之所以称它们为变形.因为它们都不满足

前述指派问题所有假设之中的一个或者多个.如：

1．有一些被指派者并不能完成某一些任务.

2．虽然每一个被指派者完成一项任务.但是任务比被指派者多.所以其中某

些任务并没有得到执行.

3．虽然每一项任务只由一个被指派者完成.但是这里被指派者比要完成的任

. .

务多.所以.其中有一些被指派者没有指派到任务.

4．每一个被指派者可以同时被指派给多于一个的任务.

5．每一项任务都可以由多个被指派者共同完成.

在此.我们仅就情况2展开详细讨论.以例3-6为例.

图 13-27

该问题的电子表格模型与一般指派问题的不同之处在于.需求量约束不是严

格的等式约束.由于研究人员少而课题任务多.且每人只能承担一项研究.所以会

出现有些课题无人承担的情况.由于决策变量取值为0或1.某项课题无人承担时.

求解表中对应列之和为0.有1人承担时和为1.因此.可将需求约束设定为每列之

和小于等于1（见图13-27的左上部分）.

如果指派问题中出现人员多而任务少的情况（情况3）.则在模型的求解表

中需求量约束仍保持严格的等式约束.即每项任务都必须指派一人完成.而提供

量约束设定为每行之和小于等于1.即有些人员没有被分配任务.

如果一个人可以被分配多于一个的任务（情况4）.可取消模型中对于提供

量的约束限制；如果一项任务可以由多个人共同承担（情况5）.则应视具体情

况建立模型.

在指派问题中.也可能出现某人不能完成某项任务的情况（情况1）.则在约

束中应加入相应的决策变量等于零的限制.例如在例3-6中增加一条件：甲不能

. .

承担课题B.则在图13-27的模型参数表中.E6单元格中以“—”取代原来的数字

“5”.而在“规划求解”对话框中.添加约束“E15=0”.这样可保证在最终求解

结果中.不会出现指派甲承担课题B的情况.

第五节 目标规划问题

目标规划的电子表格模型在结构及处理方式上与线性规划模型是相同的.

主要的区别一是目标规划中引入了正负偏差变量

d

i



及d

i



.这些偏差变量用于反

映目标的实现情况.在模型中可以作为决策变量处理；二是由于要按照一定的次

序实现多个目标.于是在目标函数中引入了优先因子

P

1

.

P

2

.….

P

n

并规定

P

k

»

P

k+1

.

表示

P

k

比

P

k+1

具有绝对的优先权.但应注意在电子表格中不能用字母来表示这种

优先因子.而只能由具体的数字去代替.为了保证

P

k

»

P

k+1

.可将

P

k

和

P

k+1

的取值相

n

差10 倍以上.

n

可视具体情况取1.2或3等.如果各目标约束的右端期望值相差

不大.

n

可只取到1.如取

P

k

=10.取

P

k+1

=1.但是.由于各目标期望值

e

i

的单位不同.

期望值

e

i

之间可能相差悬殊.这种情况下为保证第

k

级目标先于第

k+

1级目标被

满足.

n

的取值就应适当放大.

例如.例4-4的目标规划问题为



minzP

1

d

1



P

2

d

2

P

3

d

3



s.t



5x

1

10x

2

60







x

1

2x

2

d

1

d

1

0







4x

1

4 x

2

d

2

d

2

36





6x8x dd48

1233





x

1

,x

2

0,d

i



,d

i



0,(i1,2,3)



其电子表格模型如图13-28所示.

图中可变单元格C8：D8显示的是决策变量的取值.输出单元格E4表示约束

条件的左端值.而单元格L4给出了第一个约束条件的右端值.在约束条件中后

. .

图 13-28

三个属于目标约束.E5：E7中的等式表示了在这些变量下.目标约束中各目标的

实际值.可变单元格H5：I7表示的是各目标实际值低于或超过期望目标值的偏差

值. L5：L7是各目标约束右端的期望目标值.第J列的公式表示目标的实际值加

未达到值再减超出值应等于期望值.

该问题的目标分为三个优先级来实现.单元格E10：E12中给出了优先因子的

取值.相邻的两个因子之间相差10倍.1.E+03是科学计数法.表示10

3

.单元格

G10：G12中的公式表示了各级的具体目标是使哪个偏差值或哪些偏差值的组合

达到最小.本例目标函数中第一、二、三级目标分别是使偏差值

d

1



,d

2



,d

3



达到最

小.因此在G10：G12中分别引用了可变单元格H5.I6和H7.目标单元格J12 =

SUMPRODUCT（E10：E12.G10：G12）应取最小值.并通过对优先因子的控制保证目

标按优先顺序实现.

该问题是一个线性规划模型.所有的可变单元格数据都要求是非负的.这些

可以通过“规划求解”的选项对话框来实现.此外要满足约束条件E4



E6和J5：

J7=L5：L7.但对输出单元格E5：E7没有限制.因为并不要求目标约束中的实际值

与期望值完全相等.

按下“规划求解” 对话框的求解按钮后.电子表格中显示最优解对应的决策

变量为



x

1

,x

2





(4.8,2.4)

.问题的三级目标均得以实现.因此目标函数值为0.

但实际上.通过第四章对该问题用图解法分析我们得知.其最优解有无穷多个（其

最优解域为一个四边形）.但利用电子表格我们只能找到其中的一个最优解.

. .

我们再来看例4-5.原问题的代数模型如下：



minfP

1

d

1



P

2

d

2

P

3

d

3



x

1

x

2

d

1



d

1



10







2x

1

x

2

d

2

d

2

26

s.t.







x

1

2 x

2

d

3

d

3

6



x,x0,d



,d



0,(i1,2,3)

ii



12

该问题的电子表格模型及求解过程如图13-29所示.

图 13-29

该问题的建模及求解过程.包括模型中所涉及的单元格公式的解释与例3-4

基本相同.但本模型中只有目标约束而没有普通约束.通过求解发现该问题的三

级目标中.只有第一级的目标被实现.而其他两级目标均未实现.当决策变量的取

值



x

1

,x

2





(10,0)

时.

d

1



0

而

d

2



取值最小为6.

如果将目标约束2的期望值由26降至14.再重新求解.则三级目标均可实现.

此时问题的最优解为



x

1

,x

2



(4.4,5.2)

.结果如图13-30所示.



. .

图 13-30

第六节 网络优化问题

许多网络最优化问题实质上是线性规划问题的特殊类型．比如运输问题和

指派问题.都可以用网络规划来描述．而本节所讨论的典型的网络优化问题如：

最小费用流问题、最大流问题以及最短路问题等也可以转化为特殊的线性规划问

题．因此对于许多小型的网络优化问题.我们仍有可能利用Excel 的“规划求解”

加以解决.而对于较大型的问题.可以利用其他线性规划的商业软件包中的网络

单纯形法来处理.

一、最小费用流问题

我们首先从一个例子开始.例6-12中的图6-19给出了最小费用流所需的网

络.在解决这个问题前.我们先来介绍一些有关最小费用流的术语.

1．最小费用流问题的模型可以用带有通过其中的流的网络来表示.网络中

的圆圈被称为节点.箭头称为弧.

2．如果节点产生的净流量（流出减去流入）是一个确定的正数的话.这个

节点称为供应点（本例中节点1是供应点.其净流量为7）.

3．如果节点产生的净流量是一个确定的负数的话.那么这个节点就称为需

求点（本例中节点6就是需求点.其净流量为-7）.

4．如果节点产生的净流量恒为零.那么这个节点就称为转运点（本例中节

点2至5均为转运点）.

6．允许通过某一条弧的最大流量称为该弧的容量（本例中.每条弧旁括号

中的前一个数字表示了该弧的容量）.

7．通过某一条弧的单位流量均产生一定的费用.称为单位成本（本例中.

每条弧旁括号中的后一个数字表示了该弧的单位成本）.

一般来说.最小费用流问题具有如下特征：

1．最小费用流问题都至少有一个供应点和一个需求点.其余所有节点均为

转运点.

. .

2．通过弧的流只允许沿着箭头的方向流动.通过弧的最大流量取决于该弧

的容量.

3．网络中有足够的弧提供足够的容量.使得所有在供应点中产生的流都能

够到达需求点.

4．在流的单位成本已知的前提下.通过每一条弧的流的成本和流量成正比.

5．最小费用流问题的目标是在满足给定需求（即流量一定）的条件下.使

得通过网络运输的总成本最小.

解最小费用流问题.实际上是要确定每一条弧上的流量.这个流量不应超过

该弧的容量.并使总的运输成本最小.此外.转运点的净流量应为零.而供应点的

总流出量应等于需求点的总流入量.

按照上述要求.我们来建立最小费用流问题的电子表格模型.并利用“规划求

解”对其求解.

图13-31的

上半部分给出了

该问题的电子表

格模型.该模型

由两张表构成.

第一张表给出与

网络中的弧有关

的数据及限制.

首先将以节点的

序号表示的网络

中的所有弧列在

B和C两列.起

图13-31

始点的序号按由小到大的顺序列在B列.终点的序号列于C列；数据单元格（F4：

F12）和（G4：G12）分别是对应于某一弧的容量限制和单位成本；可变单元格（D4：

D12）给出了通过弧的流量.是需要通过求解模型来确定的量.其初始值可设为0.

显然.某一条弧的流量不应超过其容量.E列的“



”显示了这种关系.模型的第二

张表则给出了关于网络中节点的限制.将网络中所有的节点序号列于单元格（I4：

. .

I9）；数据单元格（L4：L9）给出了对应节点的净流量限制.供应点和需求点的净

流量分别为7和-7.转运点的净流量为0；输出单元格（J4：J9）是各节点的实

际净流量.某一节点的净流量等于该节点的流出量减流入量.如节点2的净流量

就等于弧（2.3）和（2.4）的流量减去弧（1.2）的流量.即J5=D6+D7-D4；其他

各节点的实际净流量公式如图13-30的左下部分所示.K列显示它们应等于净流

量的限制值.

该问题是求使总运费最小的各弧流量.目标单元格D14给出了总费用的计

算公式.它等于各弧实际流量与对应的单位成本乘积的和.公式如图13-30左下

角所示.

图13-31的右下部分显示了“规划求解”对话框的内容以及选项对话框的

内容.约束包括两类.即弧的容量限制约束和节点的净流量限制.最小费用流问题

仍属于线性规划问题.而弧中的流量不应小于零.所以选项对话框中仍选择采用

线性模型和假定非负.

点击求解键后得到该问题的最优解.如图13-31：

流量：

f

12

7,f

13

0,f

23

5,f

24

2,f

34

5,f

35

0,f

45

5,f

46

2,f

56

5.

最小费用：

b(f*)91

二、网络最大流问题

最大流问题的特征与最

小费用流问题的特征是非常

相似的.但它们之间也有一些

细微的差异.

我们以例6-10为例进行

讨论.图13-32给出了以图

13-31的形式描述的该问题的

电子表格中模型.这个模型与

图13-31模型基本构成是相同

的.其主要区别是它的目标发

生了变化.由于目标不再是使

图13-32

. .

得网络中流的总成本最小.因此我们删除了图13-31中的G列.目标单元格D14

中的数据是由节点

v

s

流出的流量.由于流量的是不确定的.所以除了转运点的净

流量必须为0.节点

v

s

和

v

t

的流量不需要限制.从“规划求解”对话框中可以看出

可变单元格为D4：D12.即弧的流量；约束为容量及节点的流量限制；目标为求

流量的最大值.由于最大流仍属于线性规划问题.故在选项中仍选择使用线性模

型和假定非负.对该模型求解的结果是：

流量：

f

s1

3,f

s2

2,f

12

0,f

13

3,f

24

2,f

41

0,f

43

0,f

3t

3,f

4t

2.

最大流量：

f*5.

网络最大流问题有如下的假设.

1．网络中所有流起源于一个节点.这个节点叫做源.所有的流终止于另一个

点.这个节点叫做汇.（本例中

v

s

为源.

v

t

为汇）

2．其余所有的节点叫做转运点.转运点的流入量等于流出量.（如节点

v

1

、

v

2

、

v

3

、

v

4

都是转运点.）

3．通过每一个弧的流只允许沿着弧的箭头所指方向流动.由源发出的所有的

弧背向源.而所有终结于汇的弧都指向汇.

4．最大流问题的目标是使得从源到汇的总流量最大.这个流量的大小可以用

两种等价的方法来衡量.分别叫做从源出发的流量和进入汇的流量（图13-31中

的单元格D4=I4使用的是从源点出发的方法）.

三、最小费用最大流问题

如果同时考虑网络的流量以及费用问题就是最小费用最大流问题．所谓最小

费用最大流问题就是：给了一个带收发点的网络.对每一条弧

v

ij

.除了给出了容

量

c

ij

外.还给出了这条弧的单位成本

b

ij

.要求一个最大流

f

.并使得相应的总运

输费用最小.

最小费用问题要求网络的流量是确定的.因此.最小费用最大流问题的解法

是先不考虑费用.将其作为最大流问题处理；求出问题的最大流后.再利用最小费

. .

用问题的解法.求出该最大流对应的最小费用.

图13-33是对图13-31的网络流问题求其相应的最小费用最大流．从图中的

电子表格模型可以看出.其求解的过程是分两部分进行的：

图13-33

1．先按照求网络最大流的方法.求出该网络的最大流量；

2．以求得的最大流量为确定流量.按照求最小费用流的方法求其对应的最小

费用流及相应的最小费用.

从图上可以看出.最小费用最大流问题在电子表格中建立了两个模型.即最

大流模型及最小费用模型.通过求解第一个模型得到该网络的最大流量为17；再

以17为流量利用第二个模型求出其相应的最小费用为311．比较两个模型的求

解结果发现.两个最优解对应的各弧的流量是相同的（由于即使在有多重最优解

的情况下.电子表格也只能找到一个最优解.所以这种情况下不能确定最大流问

. .

题有几个最优解）.但有时两个模型的最优解是不同的.这意味着最大流问题有多

重最优解.而通过求解第二个模型得到了相应的费用最小的那个最优解.

四、最短路径问题

最短路径问题的最普遍的应用是在网络中的两个点之间寻找最短路．因此.

最短路径问题都有如下假设：

1．在网络中选择一条路.这条路始于某一节点.这节点叫做起点.它终于另一

个节点.这个节点叫做终点.

2．连接两个节点的连线通常叫做边（允许双方向行进）或弧（只允许沿着

箭头所指方向行进）.

3．和每条边（弧）相关的一个非负数.叫做该边（弧）的长度.

4．目标是为了寻找从起点到终点的最短路（总长度最小的路）.

首先来分析例6-7.我们希望找到从

v

1

到

v

7

的最短路线．图中给出了从

v

1

到

v

7

途经的所有中间节点以及连接节点之间弧及其长度.

观察最短路问题的特点.我们发现它实际上可以被认为是最小费用流问题的

一种特殊类型.在最短路问题中.起点相当于供应量为1的供应点.终点相当于需

求量为1需求点.所有其余的节点都是转运点.所以每一个所产生的净流量为0；

弧的长度可以看作是网络中流的单位成本；如果我们选择的路经过某一特定的弧.

则认为该弧的流量为1.否

则流量为0.这样一来.使

某条路的总长度最短就等

价于网络流的总费用最小.

因此.我们可以用处理最小

费用流的方法处理最短路

问题.

图13-34是按照上述解

释给出的例6-7最短路问

题的电子表格模型及其求

解过程.该模型与图13-31

. .

图13-34

模型的主要区别在于各弧的容量没有了限制.但弧的流量变成了0-1变量.因此

约束条件中包含了H4：H15二进制的限制；另外.图13-31中G列的单位成本被

本模型E列中各弧的距离取代了.

除此之外.图13-34最短路模型的形式基本与图13-31的最小费用流问题的

模型一致.可变单元格（D4：D15）给出流量为1.表示对应的弧被选为从

v

1

到

v

7

的

路.为0则没被选中.目标单元格D17给出了该路线的总长度.B列和C列给出了

所有的弧.J列显示了每个节点需要产生的净流量.使用该图左下角的公式后.将

H列每一个单元格都加上流出量并减去流入量.得到通过该节点的实际净流量.

对应的限制条件.即H4：H10=J4：J10.在“规划求解”对话框中作定义.在“选

项”对话框中仍选择“采用线性模型”和“假定非负”.

通过求解在模型中的D列显示了那些流量为1的弧就是最短路径中的弧.即

最短路径为.

v

1

→

v

2

→

v

3

→

v

5

→

v

6

→

v

7

.长度为13.

(戴力辉)

. .