运筹学数学电子表格操作实例

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

解

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

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

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

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

微软的电子表格软件(MicrosoftExcel)为展示和分析许多运筹学问题提供

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

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

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

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

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

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

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

要使用Excel应首先安装Microsoft

Office,然后从屏幕左下角的［开始］一［程

序］中找到MicrosoftExcel并启动.在

Excel的主菜单中点击［工具］一［加载

宏］,选择“规划求解”，如图13T所示.

点击［确定］后，在工具菜单中将增加［规

划求解］选项.

图13-1

二、在Excel中建立线性规划

模型

我们以例2T为例说明如何在电子表格中建立该间撅的线性规划模型.建立

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

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

目标函数maxZ=200x.+3OOx2

211+2X2<12

2+2X2<8

4.r,416

4x2<12

x1,x2>0

单位产量所得贷源

药品1药品11总需求量可用贡源曼

12

8

y9单位利润200JOO

1010决策粗■

图13-2图13-3

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

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

生产每单位药品I和II所需要的4种设备的台时数（单元格C5：D8）,药品I和

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

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

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

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

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

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

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

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

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

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

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

E5X5XC10+D5XD10（可直接将公式写入E5,也可利用SUMPRODUCT函数，

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

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

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

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

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

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

利润的数据单元格的右边.类似于E列的其他输出单元格，E9=C9XC10+D9XD10

或E9=SUMPRODUCT（C9：D9,CIO：DIO）.由于它是在对产量做出决策时目

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

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

如下：

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

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

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

结果放入输出单元格；

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

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

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

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

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

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

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

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

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

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

图13-4

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

添加约束2JX

变单元格地址范围为CIO：D10,并选中最单元格引用位置约束值©:

|$E$5.$E$85J|<=2]l=$G$5:$GJ8lKJ

大值（M）表示要最大化目标单元格.确定|取消|添加®|，助QD|

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

点击“确定”按钮，返回电子表格模型.

求解模型之后，如图13-8所示，“规划求解”用最优解和最优值代替了可变

单元格和目标单元格中的初始图"-8

值.因此，最优解是生产4公斤药品I和2公斤药品II,最优值为1400元，与图

解法的结果一致.

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

ABCDEFGH

1食品配制问题1炊包求解诜攻

2

长运时同画秒

3单位原料为营养成分含量营养成分的食品的营养16if1I）.

4B1B2B3实际含量最低含量送代次数9：lioo-

5蛋白质56828.6115情度①：IOCOOOl

6脂肪34620.0020允许误差QI5-

7糖85425.0025股效度®10001

8维生素1012838.3330P常用状性侵型mr自瑚

9原料单价202530109.72P暇定率负（Q）「是京

10原料用量1.940.002.36

E

用直目后单兀格CE）：1耐■工1

5二SUMPRODUCT(C5:E5,C10:E10)

6=SUMPRODUCT(C6:E6,Cl0:El0)等于r最大值如"是小值®「值为GOB

7=SUMPRODUCT(C7:E7,Cl0:El0)推汕l（G

8二SUMPRODUCT(C8:E8,Cl0:El0)约束Q

9=SUMPRODUCT(C9:E9,C1O:E10)|SF$5$FS8>=$M$5$HS8_|添加g

图13-9

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

元格（C5：E8）、（C9：E9）和（H5：H8）分别存放三种原料Bz、以每斤所含

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

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

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

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

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

格和可变单元格设定的地址，约束条件F52H5,F6>H6,F7和7和F82H8通过“添

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

选择了“最小值（N）”.

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

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

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

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

单元格中显示的最优解，即该食品配比为原料办是1.94斤，原料公是2.36斤，

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

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

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

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

一、合理用料问题

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

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

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

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

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

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

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

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

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

ABCDEFGHITK■投划求解参数I

1合理用料问题

2设置1目标单元格⑥：1西・山

3输液管止血带听诊器得头

45.74.23.10.5

5依截方法201可行可支单元格团

6

7旺种苗法获得各种材料的根数各种材料约束国）：

8截法1截法2截法3截法4嵌法5截法6实际数量需求量

|iCri3:$MS13=整数

9输液管211100100100

10止血带021021100100

11听诊器胶管101323200200也钊求解诔攻

12需用科根数111111no

13实际用料数040060100最长运U好同（X）：画片

迭代次数9：fioo一

M庆•|OOWOl

I

允详误差ID：|5-

F9二SUMPRODUCT(C9:H9,C13:I113

4=15-SUMPR0DUCT(C4:E4.C5:E5)10=SU»PRODUCT(Cl0:Hl0,C13:Hl3)收缴度。10001

5=IF<F4>=0.IF(F4<=2J'可行”「不可行"）."不可行”）11=SUJIPRODUCT(C11:H11.C13:H13)口来用次性模型如「自潮

12=SUJI(C13:H13：P暇定率负⑥厂是存

图13-10

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

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

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

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

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

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

乘积之和,如输液管的数量19二SUMPRODUCT（C9:H9,C13:H13）；目标单元格

112为总用料数，应等于各种截法所截原料数之和，即112=SUM（C13:H13）.

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

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

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

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

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

求量,即19：I12>=K9：K12（本题中,该约束取“〉二”和“二”的结果是相同的）;

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

即C13:II13二整数.

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

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

求解的结果一致.

二、放射科的业务安排

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

ABCD1EFGH

括：进行三种检查1放射科业务安排问题

2

的单位时间（C5：3放射科业务

4X线检查C7检查磁共振检查

E5）,三种检查设备5每人次检杳时间0.10.2510.5总业务量业务提供量

5每月业务量13201800<1800

7实际业务时间132

每月的可用时间3<

9机器可用时间300320120总利涧

（C9：E9）,三项业10每人次检查利润2050110155200

|规划求解方数

务每月最多提供量

F设百目标单元格H）：1丽汨・

6=SUM(C6:E6)

（H6）以及每项业等于：6最大值如「最小值如r值为g|o-

10=SUMPR0DUCT(C6:E6,C10:E10)

可变单元格⑹

务的单位利润|$C$6$E$6iJ推测⑥

CDE约束@)：

|$C$7$E$7<=$C$9,$E$9_d添加®1

（CIO：E10）.可变7=C5*C6=D5*D6=E5*E6|$F$6<=$H$6

-i

单元格为C6至E6,图13-11

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4公斤药品I和2公斤药品H,总利润为1400元但该最优解是在假设所有的模

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

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

发生怎样的情况？

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

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

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

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

标函数系数”以及约束条件右端值瓦的变动进行灵敏度分析.分析的内容主要

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

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

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

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

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

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

系数变动情况进行讨论.

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

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

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

现在，5=300元，下面我们来分析一下在保持最优解3,七）=（4,2）不变的

条件下，力可能的最大值与最小值.这样，也就可以看出0为3（）（）元的这一估计

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

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

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

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

子就可以显示出来.

为了说明这一点，图13-12显示了药品1［的单位利润从开始的%=300元降

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

ABCDEFG

唯一的变动是电子表格中C91某制药厂的生产计划问题

2

单元格中的数据从300元降3单位产量所需资源

4药品1药品11总需求量可用资源蚩

5设备A221212

到250元，以及E9单元格总6设备B1288

7设备C401616

利润减少了100元（因为每单Q2至nnAQ1Q

ABCDEFG

位药品H所提供的利润减少1某制药厂的生产计划问题

2

3单位产量所需资源

了5（）元）.因为最优解没有变4药品I药品n总需求量可用资源量

5设备A2212<12

动，我们可以知道在不影响最6设备B128<8

7设备C4016<16

优解的前提下，药品II的单位8设备DC48<12

9单位泳陶2C0,.3501500

10决策变量4怪③13

利润c,=300元的最初估计是较高的.

那么，如果这一估计值较低又会怎样呢？图13-13表示了将％=300元增加

到外二350元的情况.同样，最优解没有发生变化.

因为，增加或减少最初的％=300元均不会对最优解产生任何影响，仁就不

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

的更精确的值.但是对力的研究至此并没有结束，因为实际值很可能会超出250

到350元这一范围，那么在保持最优解不变的条件下，%到底可以在什么样的

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

值，直到最优解发生改变，以找到最优解发生变化时对应的外值.但是，这样计

算太麻烦了，是否有简便一些的方法呢？答案是肯定的.

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

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

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

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

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

第二栏给出了递减成本，递减;可变单兀格冢羽反目标式允许的允许的

单元格名字值成本系数增量减量

成本提供了为使决策变量取$C$10决策变量上品I402001E+3050

$D$10决策变量药品II20300100300

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

Lx|n13-u14

少的数量.对于本例，由于两

决策变量的取值均为正数，故递减成本均为零.第三栏表示了目标函数的现值，

最后两栏表示为使最优解保持不变，目标系数允许增加与减少的最大值.

例如，考虑决策变量X的目标系数从图13-14中表示产品I的一行中

可知，q可以减少50,可以增加1E+30.在电子表格中1E+30是1（严的缩写,

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

c.的现值:200

G的允许增加值：无穷大此时Q无上限

Q的允许减少值：50此时G2200-50=15。

。的变化范围：c,>150

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

优解将始终保持在（巧,七）-（42）不变.该药厂的另一药品的单位利润的变化范围

也可以用同样的方法得出，c2是药品H的单位利润，表中表示药品II的第二行

给出了下面关于%的信息：

c2的现值：300

02的允许增加值：100此时q£300+100=400

的允许减少值：300此时2300-300=0

。2的变化范围：04620400

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

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

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

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

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

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

值.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

产生怎样的影响？

例如，原来药品I和药品II的单位利润分别为200元和300元，现在由于原

料成本的变化，每公斤药品I和药品II的单位利润分别变为180元和355元，最

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

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

分之百法则.

首先定义%的允许增加（减少）百分比为乙的增加量（减少量）除以、的

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

（200-180）/50=40%,Q的允许增力口百分比为（355-300）/100=55%,%的允

许减少百分比与%的允许增加百分比之和为40%+55%=95%.

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

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

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

因为本例中5的允许减少百CDEFG

1某制药厂的生产计划问题

2

3单位产量所需资源

分比与外的允许增加百分比之和4药品药品总需求量可用资源量

—

设备A2I2n

5182182

备

设12B

备

为95%不超过100%,所以当每公设rcB40

18616

7备

区设D0412

斤药品I的利润减少为180元，每

单位利润1803551430

10

公斤药品H的利润增加为355元

图13-15

时，此线性规划最优解仍然为药品

I生产4公斤和药品n生产2公斤（即七=4,±=2）,此时有最大利润为

180x4+355x2=720+710=1430（元），如图13—15所示.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

从一个约束

ABCDEF1GH

1放射科业务安排,啜I

的影子价格中就2

3放射科业务

可以直接看出，决4X线检查CT检查磁共振检查

5每人次检查时间0.10.250.5总业务量业务提供量

策改变而引起的6每月业务量13204800180011800

7实际业务时间1321200

8<<《

约束常数的改变9机器可用时间300120120总利润

10每人次检查利润206010552001

所造成的影响.只1放射科业务安排问题

2

要约束常数的变3放射科业务

4X线检查CT检查遂共振检查

5每人次检告时间0.10.250.5总业务量业务提供量

动不大，那么目标6每月业务量132148001801<1801

7实际业务时间132.10

函数值的变动就8<

9机器可用町间120总利润

10每人次检杳利润1055220

等于约束常数的

图13-16

变动（正或负）乘

以影子价格.为了说明影子价格的含义，我们以第二章第五节中的第二个应用，

即放射科的业务安排问题为例来加以讨论.该问题最初的线性规划模型如图13-

16上半部分所示.单元格H6及C9至E9中的值1800,300,120,120分别表示

总业务提供量以及三种设备的可用时间的限制.可变单元格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元/小时

约工

影

终阴约束允许的允许的

格

价

单元格名字值限制值增量减量

$F$6每月业务量总业务量180020180016801320

$C$7实际业务时间段检查13203001E+30163

$D$7实际业务时间C7检查120160120330120

$E$7实际业务时间破共振检查001201E+30120

图13-17

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

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

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

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

和总利润，同样可以解释磁共振检查的影子价格也为()的原因.

(-)影子价格的灵敏度分析

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

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

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

1800-1320=480,其有效区域为：480</?,<34«0,即当业务提供量在此范围内变

化时，每增加(减少)一人次，总利润也会相应地增加(减少)20元；类似可得

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

b2之300-168=132,120T20=0<<120+330=450,/2120-120=0.

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

1某制药厂的生产计划问题

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

13-3单位产量所需资源

4药品I药品11总需求量可用资源量

8所示.G栏中的常数(12,8,16,5设备A221212

6设备B1299

12)表示四种设备可用的台时数.当7设备C401216

8设备D041212

9单位和同2003001500

我们将设备B的可用时间从8小时10决策变量33

增加到9小时时,我们发现总利润增加了100元（从1400元增加到了1500元）,

如图1378所示.但100元并不是设备B可用时间的影子价格.

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

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

13-8中G5至G8中的常数.约束

终阴影约束允许的允许的

从阴影价格一栏中可以看单元格名字值价格限制值增量减量

$E$5设备A总需求量120121E+300

出，设备B可用时间的影子$E$6设备B总需求量8150804

$E$7设备C总需求量1612.51608

$E$8设备D总需求量80121E+304

价格为150元.通过分析其

影子价格的有效区域瓦知，图13-19

可用时间在4—8小时之间时，每增加（减少）一个小时的可用时间，总利润会

相应增加（减少）150元.但由于设备B的可用时间正好为8小时，所以再继续

增加1个小时的可用时间后，约束限制值已经超过了影子价格的有效区域，故总

利润的增加值只有100元而不是150元.从图13-9中还可以看出，设备A和设

备D的影子价格均为0,设备C的影子价格为12.5元,有效区域分别为：々之12,

8</?3<16,&>8.

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

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

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

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

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

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

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

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

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

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

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

在这种同时变动的情况下，会产生怎样的后果呢？

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

1小时，所产生的结果如下:

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

X线检查时间：300—297总利润的变化量二-影子价格X3=0X3=二心

总利润的净变化=160元

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

格是否依然有效.

检验有效性的一种方便快捷的方法就是将这些数据代入电子表格的相应单

元格中去，重新求解.图13-20所示的电子表格显示出总利润的净增量确实为160

兀（从55200兀增加到ABC1D1EFG1H

1放射科业务安排问题

55360元），因此，影子价L.2j

3放射科业务

4X线检查CT检查遂共振检查

格在上面约束右端值同5每人次检查时间0.10.250.5总业务量业务提供量

6每月业务量131648401800<1800

时变动的情况下是有效7实际业务时间131.61210

_8j<<|<

_9J机器可用时间297121120总种同

的.10每人次检杳利润20601055360

如果我们继续减少图13-20

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

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

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

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

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

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

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

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

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

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

CT检查时间：120—121

占允许增加量的百分比=（⑵T20xlOO%=0.03%

330

X线检查时间:300f297

占允许减少量的百分比=（300~297）x100%=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来描述和解决