卫生管理运筹学特殊的线性规划

第三章 特殊的线性规划问题

第一节 运 输 问 题

人员、物资的流动在社会生产实践中是极其频繁且普遍的. 我们经常需要把某些货物从一些地方运送到另一些地方，在制定运输方案时，考虑最多的是运输费用是否最低？例如：要从甲、乙两地向A、B运送100t药材，每吨运费（单位：百元）及供需情况见表3-1：

表3-1 药材供应、需求量和单位运价表

单 位 运 供 应 费 点 需 求 点 A城 B城 供应量（t） 甲地 乙地 需求量(t) 1 5 30 2 10 70 40 60 通常人们总是将单位运费最低的优先安排，其次考虑运费次低的线路. 这样从甲地运30t到A城，运10t到B城；从乙地运60t到B城，该方案的总费用为: 30×1+10×2+60×10=650（百元）.

值得注意的是，我们虽然每次都优先考虑运费最小的线路，但最终方案的总费用未必最少. 如上面问题可安排从甲地运40t给A城，乙地分别运30t给A、B两城，从而总费用为: 40×2+30×5+30×10=530（百元）．

出现这种现象主要是因为局部最优不等于全局最优，或者说局部最优的简单相加不等于全局最优，所以我们有必要研究运输问题. 事实上它属于线性规划问题的范畴，但由于其约束方程组的系数矩阵具有特殊的结构，可以找到一种比单纯形法更简便的求解方法——表上作业法.

一、运输问题的模型和特征

运输问题的一般提法是这样的：某种物资有m个产地：A1, A2, ??, Am.

- 1 -

需要运到n个销地B1, B2, ??, Bn；Ai的产量为ai ；Bj的销量为bj，并且

?a??b（即供需平衡． 若供需不平衡可以经过适当调整，转化为供需平衡

iji?1j?1mn问题来解决）．若已知货物从Ai运到Bj的单位运费为cij (i =1、2??m, j=1、2??n), 试问如何组织调运，既能满足供销需要，又能使总运费为最少？

令决策变量xij表示从Ai运到Bj的物资数量，则该问题为求解所有xij使总的运输费用??cijxij达到最少．该问题的数学模型可写为

i?1j?1mnMinZ???cijxij

i?1j?1mn?m??xij?bj,j??,?,?,n?i???ns.t.??xij?ai,i??,?,?,m

?j???x??,对所有的i,j?ij?很显然，运输问题是一个有m×n个变量、m +n个约束方程的线性规划问题，其系数矩阵A如下：

x11x12?x1nx21x22?x2n?xm1xm2?xmn

????m行???????n行????11?1???11?1???????11?1? A???1 1 1??? 1 1 1??? ? ? ???? 1 1 1????

与前面各节遇到的规划相比，运输问题的特征是：①在产销平衡时，运输问题一定有可行解，且有最优解. ②当产量与销量均为整数时，必存在决策变量为整数的最优解. ③决策变量的系数只有0和1，系数矩阵A有m +n行、m n列，秩为m+n-1，从而有m+n-1个基变量. ④运输问题的m+n-1个基变量不构成

- 2 -

闭回路.

所谓“闭回路”是指当运输问题用下面的表格形式（表3-2）给出时，一组变量能连成如下形式，如图3-1所示，我们就称该变量组构成闭回路.

其实闭回路就是一条封闭折线，每个顶点都是转角点. 设m =4,n =5,将变量组?x21,x22,x32,x35,x15,x13,x43,x41,x21?表示为图3-2. 显然，该变量组形成一闭回路.

表3-2 运 输 表

销地 产地 A1 ?? Am 销量 x11 xm1 b1 cm1 B1 c11 x12 xm2 b2 cm2 ?? B2 c12 ?? xmn bn ?? ?? x1n cmn Bn c1n 产量 a1 ?? am x11x12x11x12x22x23x31x13x14x34x21x22x31x33图3-1 闭回路类型图

x41x43

?x21 x41 ? ? x22 x32 ? x13 ? ?x43 ? x15 ?x35 图3-2 闭回路示意图

定理3-1 运输问题的m+n-1个变量构成基变量的充要条件是不含闭回

- 3 -

路．（证明略）．相应地从一个非基变量出发，存在且惟一存在一条闭回路．

二、用表上作业法求解运输问题

基于运输问题的上述特殊性，求解运输问题的单纯形法就可以大大简化，对求极小化问题来说，这种解法能在表上进行——表上作业法．其基本步骤是：

1．编制初始调运方案（即确定初始基本可行解） 常用的方法有西北角法和最小元素法；

2．最优性检验（即求出相应的检验数） 常用方法有闭回路法和位势法； 3．解的改进 根据检验数确定方案是否最优，是则终止，否则采用闭回路法调整，再返回到第2步，直至最优．

（一）编制初始调运方案

以一个实例介绍初始基本可行解的确定．

例3-1 某省医疗队从A1、 A2 、A3三所省级医院抽调骨干医护人员配备必要设备去B1、B2、B3、B4四个贫困县进行巡回医疗扶贫，各医院抽调的人数、各县需要人数、以及从医院到各县的人均（包括设备交通）费用如表3-3所示，问如何安排可使总费用最小？

表3-3 运输问题的人均费用表

B1 B2 B3 B4 人均费用（单位：百元）

A1 A2 A3 县需求人数

医院抽出人数

2 9 10 7 9 1 3 4 2 5 8 4 2 5 7 3 8 4 6

初始调运方案就是找到一组初始可行基，即找到m＋n－1=3＋4－1=6个正整数填入它的运输表3-4，使满足约束条件．

（1）西北角法 所谓西北角法就是从表3-4的左上角第一格开始安排运输计划． 方法是：取其对应医院抽出数与县城需要数的最小值作为初始基本可行解的第一个分量值（x11?min?a1,b1?）． 这样第一列的需求已经满足，用线划去第一列，再看第二列、第一行，由于抽出数还有9-3=6，与B2的需求数8比较，

- 4 -

取最小值6（x12?min?a1?x11,b2?）填入该格． 依此次序进行，即可得到第一个基本可行解，见表3-4．

表3-4 运输问题作业表——西北角法

县城 医院 A1 3 A2 A3 医院抽B1 2 1 8 3 8 2 4 6 3 1 4 B2 9 3 4 2 B3 10 6 B4 7 出人数 9 2 5 5 7 县需人数 6 （2）最小费用法 西北角法的优点是简单、易实现，但没有考虑最小费用． 可能要经过许多次迭代才能得到最优解． 而最小费用法的基本思想是就近供应， 优先考虑最小单位运费对应的xij， 这样得到的方案会更接近最优方案．以例3-1来说明具体步骤．

表3-5 运输问题作业表——最小费用法

县城 医院 A1 医院抽B1 2 1 8 ③ 3 8 4 ⑤ 3 ④ 4 B2 9 4 2 B3 10 ④ ② B4 7 出人数 9 2 5 5 7 A2 A3 ③ 县需人数 6 在运输表3-5中，单位运费cij最小的是c21?1. 这个格子处于A2行B1列，因而最多可供5人，但需求量为3人，于是，在这个格子里填上尽可能大的数是

- 5 -

x21?min?a2,b1??min?3,5??3. 这个格子填上数后，B1的要求满足了，可用线划去该列.于是只需考虑B2、B3、B4的需求. 从表3-5看到，在未划线的格子中

cij最小者是c24?c33?2. 任选一个，比如考虑c33所在的格子. 此处的供求情况是：最多可供7，但最多需要4. 于是应填入的数是x33?min?a3,b3??min?7,4??4. 这样B3的需求也满足了，用线划去该列.后面只需考虑B2和B4的需求. 这时最小的cij（≠c11，≠c13）是c24=2. 此处，最大可供量为5－3=2（c21处已占用了），需求量为6，从而应令x24?min?a2?x21,b4??min?5?3,6??2. 这时A2的供应量用完了，用线划去该行. 后面只需考虑A1和A3的供应、B2和B4需求了，??这样依次分析下去，便得到：

x32?min?a3?x33,b2??min?7?4,8??3 x14?min?a1,b4?x24??min?9,6?2??4 x12?min?a1?x14,b2?x32??min?9?4,8?3??5

将上述六个数填在运输表内（为了与其它数字相区别，用圈号标记），其余为非基变量取0值，就可作为初始调运方案（见表3-5）.

从表3-5容易算出，这个初始方案的总运费是 5×9+4×7+3×1+2×2+3×4+4×2 =100（百元）， 即10000元.

（3）以上两种方法在求初始基可行解时，均会遇到一些特殊情况，一般称为“退化”. 大致有两种情况：①当选定元素xij后，发现该元素所在行的供给量等于需求量时，此时只能划去一行或一列，不能同时划去. ②当选定元素xij后，发现对应供给量ai和需求量bj均为0，那么xij?min?ai,bj??0，此时仍应把

xij作为基变量，把0值填入相应格子中（即基变量取0，退化）.

（二）最优性检验

上面已经得到初始基可行解，那是否为最优解呢？需要验证. 依单纯形法原理，要求出各变量的检验数；由于基变量的检验数恒为0，所以只要求出非基变量的检验数. 另外运输问题是极小化的线性规划问题，只要检验数全部非负即达最优解. 在表上作业法中常有闭回路法和位势法.

- 6 -

（1）闭回路法 我们试从定义出发计算检验数. 先看x11的检验数C11，分析一个闭回路（表3-6中虚线所示）. 由于供求条件的限制，当从0增加到1时，将引起连锁反应：x21减少1，x24增加1，x14减少1. 于是根据检验数的定义得到C11=1c11+（-1）c21+1c24+（-1）c14= c11-c21+c24-c14=2-1+2-7= -4，即x11每增加1个单位，将使运费减少4个单位，这说明初始解非最优. 类似地，我们可以求出其他非基变量的检验数，但是，一般说来这种求检验数的方法是比较繁琐的. 例如，求x31的检验数时，必须考虑下面那样的复杂闭回路(表3-6中实线所示)．

表3-6 运输问题作业表

县城 医院 A1 医院抽B1 2 1 8 ③ 3 8 4 ⑤ 3 ④ 4 B2 9 4 2 B3 10 ④ ② B4 7 出人数 9 2 5 5 7 x11 A2 A3 县需人数 ③ x31 6 （2） 用位势法 位势法又叫U-V法，它是由解运输问题的对偶问题引出来的. 平衡型运输问题的对偶问题为：

MaxY??aiui??bivji?1j?1mn

s.t.ui?vj?cij(i?1,?,m;j?1,?,n)对偶模型里的变量ui与m个供应约束方程对应，vj与n个需求约束方程对应，分别称它们为原问题变量xij的行位势和列位势.

定理3-2 运输问题的决策变量xij的检验数Cij?cij?(ui?vj). (证明略) 由于基变量的检验数等于0，所以对于基变量xij有： ui?vj?cij. 而平衡型

- 7 -

运输问题中的基变量个数为m?n?1，从而得到m?n?1个类似ui?vj?cij这样方程构成的方程组. 但它有m?n个未知量，要解出这个方程组，必须给其中一个自由未知量赋值，比如令u1?0（这样不会影响结果），就可求出所有变量的位势，进而算出所有非基变量的检验数. 仍用例3-1来说明具体求法. 对于最小费用法得到的初始基本可行解（见表3-5），得到方程组

?u1?v2?9?u?v?74?1?u1?0,u2??5,u3??5,???u2?v1?1 令 ，解得：u?0??1u?v?24?v?6,v?9,v?7,v?7?2234?1?u3?v2?4???u3?v3?2

计算非基变量的检验数：C11?c11?(u1?v1)?2?0?6??4，与闭回路法结果一致，其它检验数可类似求出填入作业表中，用（ ）圈起来，见表3-7.

表3-7 运输问题作业表——位势法求检验数

县城 医院 0 A1 （-4） -5 A2 -5 A3 县需人数 （7） 3 ③ 8 1 6 B1 2 9 B2 ⑤ （-1） ③ 8 4 3 9 （3） 4 7 B3 10 ④ ② （3） 6 2 5 （2） ④ 4 2 7 B4 7 医院抽出人数 9 5 7 从表3-7可以看出，x11的检验数C11=-4（与前面用定义求得的结果是一致的）是所有检验数中负值最小者. 这说明应当让x11进基，以改进表3-5中的初始方案.

（三）用闭回路法调整运输方案——改进基本可行解

如果经过检验所得的解不是最优的，就需要对基变量进行迭代. 前面已经有选取进基变量的规则，即在所有非基变量中取检验数是负值最小者为进基变量.

- 8 -

下面，用闭回路法选取出基变量及基变量取值的调整量，以实现解的改进. 步骤是：① 找出入基变量所在的闭回路，并以该变量所在格为起点，沿闭回路顶点依次交替把它们所取的值前面加“+”、“-”号. 如表3-8所示； ② 所有被标“-”号格子中变量xij取值最小者作为出基变量，即被标“-”号的圆圈中数字最小者：

??min{闭回路顶点上所有标\号的xij的取值}. 在表3-8中??min?3,4??3.

表3-8 基变量迭代调整表

县城 医院 + 0 A1 （-4） -5 A2 - ③ -5 A3 县需人数 （7） 3 8 1 6 B1 2 9 B2 ⑤ （-1） ③ 8 4 3 9 （3） 4 7 B3 10 - ④ + ② （3） 6 2 5 （2） ④ 4 2 7 B4 7 医院抽出人数 9 5 7 表3-9 迭代后的运输方案表

县城 医院 0 A1 ③ -5 A2 （4） -5 A3 县需人数 （11） 3 8 1 2 B1 2 9 B2 ⑤ （-1） ③ 8 4 3 9 （3） 4 7 B3 10 ① ⑤ （3） 6 2 5 （2） ④ 4 2 7 B4 7 医院抽出人数 9 5 7 ③ 进行基的迭代,出基变量当然取值为0，即将所有带“+” 号的格子原取值加

?，带“-”号的格子原取值减?,就得到一个新的调运方案（闭回路不涉及的基变量取值不变动，见表3-9）. 再求检验数，重复上述步骤，直至最优.

- 9 -

从表3-9中容易算出，这个方案的总运费是 3×2+5×9+1×7+5×2+3×4+4×2 =88（百元）， 即8800元. 比初始表的方案优秀了，但在表中求出各非基变量的检验数显示，它还不是最优的. x22要作为入基变量. 再经过迭代得到调运方案如表3-10所示.

表3-10 再次迭代后的运输方案表

县城 医院 0 A1 ③ -5 A2 （4） -5 A3 县需人数 （11） 3 8 1 2 B1 2 9 B2 -⑤ + 3 9 （3） 4 7 B3 10 -⑤ （3） 6 +① 7 B4 7 9 <6> 2 5 （-1） <5> ③ 8 4 （2） ④ 4 2 医院抽出人数 <0> 5 7 从表3-10容易得出，x11?3,x14?6,x22?5,x32?3,x33?4,其它非基变量为0；这时的总费用为：3×2+6×7+5×3+3×4+4×2 =83（百元）， 即8300元. 这时算出非基变量的所有检验数均非负，从而是最优的运输方案.

在计算过程中需要注意的是，可能会有非基变量（空格）的检验数为0的情况，这时，该供销平衡的运输问题存在无穷多最优解. 在已得到的一个最优解的表格中，从这样的空格出发做闭回路重新进行调整，可以得到另一个最优解.

三 、其他运输问题的处理

前面的讨论都是以供销平衡（即?ai??bj）为前提的. 但在实际问题中，

i?1j?1mn这一条件常常不能满足，称为不平衡型运输问题.此时有“供大于销”和“供小于销” 两种情形. 下面只讨论第一种，另一种情况可类似推出. 由于“供大于销”有：?ai??bj．这时可虚设一个销地Bn?1，Bn?1的需求量为总供给与总

i?1j?1mn- 10 -

需求的差，即bn?1??ai??bj,单位运费cin?1?0(i?1,2,?,m)；这样原问题就

i?1j?1mn转化成供销平衡模型的运输问题了.另一种情况可类似虚设一个供给地.

容易理解，这里虚设了一个运费等于零的销地Bn+1,因为运费为零物资是运不走的.所以本质上多余的物资，仍留在产地.

另外运输问题也可以由计算机求解，在第十三章中介绍了一种用计算机求解运输问题的方法．

第二节 0—1 规 划 问 题

人们在探讨线性规划问题时，常常会有实际问题要求全部或部分决策变量必须为非负整数. 例如决策变量表示人数、车辆数、机床数等，这样的线性规划问题，称为整数规划（integer programming）. 解决的方法常有分支定界法和割平面法．鉴于本书篇幅所限，不作介绍，有兴趣的读者可参阅有关文献. 但作为整数规划中的一个特殊情况——0-1规划和指派问题，因为有特殊解法，下面作简要介绍．同样整数规划的计算机求解也是很成功的，见第十三章.

一、0—1规划的概念

整数规划中若有变量的取值被限制为0或1的，称此变量为0-1变量. 在讨论线性规划问题时，如果研究的对象具有互相对立的两种可能情况，那么引入0-1变量，将有助于问题的解决．对于全部变量都是0-1变量的线性规划问题，就称为0-1规划问题. 0-1规划是特殊的整数规划，自然可以用分支定界法或割平面法求解，这里从略.

我们建立下述实例的数学模型，并给出0-1规划问题的标准型.

例3-2 在暑假期间，某同学准备徒步回家探亲．他把要带的物品装进包后，觉得还能多放5个单位重量的东西． 为此，他列出了拟放物品的清单，见表3-11． 他认为：应使所增加的物品总价值为最大．基于以上的考虑，他到底还要带哪些

东西呢？ 表3-11 物品重量、价值表

- 11 -

?0,不带j号物品解 设：xj??

?1,带j号物品y为所增加的物品总价值，于是该问 题的数学模型为

MaxY?6x1?3xx?2?35x4编号 名称 重量 价

值

1 书籍 5 6 2 诱饵 2 3 3 电筒 1 1 4 食物 3 5

?3x?5 ??5x1?2x2?x34s.t?.?1,2,3,4)??xj?0,1.j(一般地，称下面形式的数学模型为0-1规划的标准型

MaxY??cjxjj?1n ?nax?b(i?1,2,,?,m)i??ijjs.t.?j?1?x?0,1.(j?1,2,?,n)?j如果0-1规划模型不是标准型，总可以通过适当的变换，使其化为标准型.

二、0—1规划的解法

从理论上讲，求解0-1规划问题，有比单纯形法更简单的方法——枚举法，即检查变量取值为0或1的每一个组合是否满足所有约束条件，再比较目标函数值，以求得最优解，对于n个变量就需要检查2n个取值组合．当n＞10时，即使经历漫长的计算过程找到了最优解，也会由于时过境迁而失去应用价值．现介绍隐枚举法（implicit enumeration）求解0-1规划问题，它只须检查(x1,x2,?,xn)取值的一部分，即可找到最优解．

以例3-2说明求解步骤．

首先，采取试探法找出它的一个可行解：(x1,x2,x3,x4)=（1，0，0，0）． 随后算出相应的目标函数值：y = 6．这是一个求y的最大值问题，当然可以认为ymax?6．因此就有：6x1?3x2?x3?5x4?6． 将这个不等式加到约束条件中． 这个新的约束条件具有滤掉非最优解的功能，所以称为过滤条件(filtering constraint)．我们把这个过滤条件和原有的约束条件5x1?2x2?x3?3x4?5依次记作(0)和(1)，而把它们左边的取值分别写成(0)?和(1)?．由于该问题有4个决策变

- 12 -

量，所以(x1,x2,x3,x4)共有2种不同的取值．据此，我们列出表3—12．其中：

4

(x1,x2,x3,x4)是2种取值，(0)?和(1)?是将(x1,x2,x3,x4)取值代入后的计算结

4

果．继而考查它们是否满足(0)和(1)：当不满足某个约束条件时，同行以下的各项就不再考虑，这表明(x1,x2,x3,x4)不是可行解；当满足全部约束条件时，这表明(x1,x2,x3,x4)是可行解， 然后求出这些可行解对应的目标函数的最大值：

ymax?max?6,8??8．

表3-12 隐枚举法计算表

(x1,x2,x3,x4)

(0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 1, 0) (0, 0, 1, 1) (0, 1, 0, 0) (0, 1, 0, 1) (0, 1, 1, 0) (0, 1, 1, 1) (1, 0, 0, 0) (1, 0, 0, 1) (1, 0, 1, 0) (1, 0, 1, 1) (1, 1, 0, 0) (1, 1, 0, 1) (1, 1, 1, 0) (1, 1, 1, 1)

(0)′ 0 5 1 6 3 8 4 9 6 11 7 12 9 14 10 15

（1）′ 4 5 6 8 9 7 10 8 11

是（√）否 （×）可行解？ × × × √ × √ × × × × × × × ×

y

6 8

于是,该问题的最优值ymax =8．从而最优解(x1,x2,x3,x4)=（0，1，0，1）．这表明，该同学还要带诱饵和食物．

从提高隐枚举法的效率着想，当求解最大（小）化0-1规划时，若遇到y值大（小）于（0）式的右边，应随即让（0）式的右边改取这个y值．求解0-1规划，不要墨守成规，应视具体情况选择适当的解法，以期收到事半功倍的效果．

例3-3 求下面0-1规划的解.

- 13 -

MaxY?3x1?2x2?5x3?x1?2x2?x3?2 (1)? (2)?x1?4x2?x3?4 ?s.t.?x1?x2?3 (3)?4x2?x3?6 (4)???xj?0或1.(j?1,2,3,)解 首先用试探的方法找一个可行解(x1,x2,x3)?(100)，它满足约束条件（1）到（4），且对应的目标函数值y=3．于是过滤条件为：

3x1?2x2?5x3?3(0)

用全部枚举法，3个变量共有23=8个解，原来4个约束条件共需32次运算，现在用隐枚举法，将5个约束条件按（0）~（4）顺序排好（见表3-13），对每个解依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件可不必再检查，因而就减少了运算次数. 本例实际只作18次运算．最优解(x1,x2,x3)?(101),maxy?8．

表3-13 隐枚举法计算表

满足√

否则× × √ × × × √ × ×

(x1,x2,x3)

(0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1)

(0) 0 5 -2 3 3 8 1 6

（1） -1 0

（2） 1 2

（3） 0 1

（4） 1 1

y 5 8

第三节 指 派 问 题

指派问题（assignment problem）也称为分配问题，是0-1规划的特殊情况，对人员和设备的科学管理具有重要的意义．

一、指派问题的概念

指派问题就是人员和设备的任务安排问题．设某部门需完成n项任务，恰好

- 14 -

有n个人可以承担这些任务，每人分别完成其中一项．因工作性质和个人专长的差异，每个人完成各个任务的时间或收益不同．于是便提出这样的问题：指派哪个人完成哪项任务，可使他们完成n项任务的总时间最短或总收益最大？

凡是能同这个典型事例比照的问题，诸如：有n项加工任务，如何指定n台机器分别来完成，可使它们总的加工时间最短？有n条航线，怎样分配n艘船舶各自去航行，能让它们总的经济效益最大？等等，统称为典型的指派问题．

例3-4 某医院的四名化验员（甲、乙、丙、丁）完成四项化验任务（A、B、C、D）所消耗的时间见表3-14. 问哪个化验员担当哪项化验任务，可使所需总时间最少？ 表3-14 化验工作所需时间（min）

分析：为了方便叙述和建立数学模型. 设： i =1，2，3，4分别表示化验员

甲，乙，丙，丁；

j =1, 2, 3, 4分别表示A，B，

甲

乙 丙 丁

A 2 10 9 7

B 15 4 14 8

C 13 8 16 15

D 4 15 13 9

C，D四项化验任务；

bij 表示第i名化验员完成第j项任务所需要的时间； ?1,表示第i名化验员担任第j项化验任务, xij???0,表示第i名化验员不担任第j项化验任务,四名化验员所消耗的总时间为y，于是数学模型为

15 13 4 ??? ??4415??10 4 8 MinY???bijxij 其中： ?bij???? 9 14 16 13i?1j?1??? 7 8 15 9????4??xij?1,?i?1?4s.t.??xij?1,?j?1?x?0或 1 ?ij??j?1, 2, 3, 4??i?1, 2, 3, 4? ?i, j?1, 2, 3, 4?

由于目标函数是求y的最小值，所以本例也称为最小化指派问题. 一般地，最小化指派问题的数学模型是:

- 15 -

MinY???bijxij ?bij?0?

i?1j?1nns.t.?n??xij?1 ?j?1, 2, ?, n??i?1?n??xij?1 ?i?1, 2, ?, n? ?j?1?x?0, 1 ?i, j?1, 2, ?, n??ij??b11 b12 ? b1n???b b ? b?21222n?其中：?bij??? ，称为效率矩阵. 约束条件中的第一个等式表示

? ? ? ?????b b ? b?nn??n1n2第j项任务只能由一个人去完成；第二个等式表示第i个人只能去作一项任务.这种问题的实质就是：找出效率矩阵?bij?中位于不同行、不同列的n个元素，使其和最小. 另一方面，它既可视作0-1规划，也可视作运输问题. 所以解法很多，这里仅根据它的特殊性，介绍一种手工算法——匈牙利法. 至于机器解法可参见第十三章.

二、指派问题的匈牙利算法

匈牙利数学家科尼格（Konig）利用指派问题的特点，给出一种简便、有效，也是十分常用的方法. 基本原理是：如果效率矩阵?bij?中某行各元素，分别减去

??，则两效率矩阵的最优解相同. 对于列也具一个常数K，得到新的效率矩阵?bij有这样的性质. 这个原理不难理解，对任何一项任务来说，n个人完成这项任务的效率表现在效率矩阵中该任务对应的一列上，效率高的人，所用的时间少，效率低的人所用的时间多. 如果对这些时间都加上或减去一个常数K，并不改变n个人完成这项任务的快慢顺序，因此不影响指派方案. 同理对任何一个人来说，他完成各项任务的效率表现在效率矩阵相应的一行上，对这一行所有的时间加上或减去同一个常数K,只会影响完成任务的总时间，不会改变他完成各项任务的快慢顺序，所以也不影响指派方案.

这个原理也可由指派问题的数学模型直接推出，如在例3-4的效率矩阵第2

- 16 -

列每个元素加上常数K，则目标函数变为

y??2x11?(15?K)x12?13x13?4x14?10x21?(4?K)x22?8x23?15x24?9x31?(14?K)x32?16x33?13x34?7x41?(8?K)x42?15x43?9x44容易看出它与原目标函数y相比，多了一项:K(x12?x22?x32?x42),但由约束条件得：x12?x22?x32?x42?1，因此，目标函数只多了一个常数K，约束条件没有变化，所以不会改变最优解，只会使目标函数值增加常数K.

下面就例3-4说明求解最小化指派问题的匈牙利算法的具体步骤： 第一步：修改效率矩阵 在效率矩阵?bij?中，让每行（列）元素减去该行（列）元素的最小值，使每行、每列都至少有一个0元素. 得到矩阵?cij? .

15 13 4 ?-2 11 2 ??2 ?0 13 ?0 13 7 0???????

-4 10 4 8 156 0 4 116 0 0 9?????

? ?bij???????b?c?ijij? 9 ?0 5 7 4??0 5 3 2? 14 16 13?-9 ??????? 7 8 15 9?-7 ?0 ??1 4 0????1 8 2??0 ?

-4 -2

第二步：试求最优指派方案 根据指派问题的实质和求解原理，只要能在修改后的效率矩阵中找到n个不同行、不同列的0元素 ，并令它们所对应的xij?1，其它元素对应的xij?0，这样的指派方案就是最优的. 在矩阵?cij?中，首先找出含0最少的行(列)，并且把其中的一个0括起来，即（0）；然后划掉与（0）同行、同列的0元素，即?.

? 13 7 0?? 13 7 (0)?? 13 7 (0)?? 0? 0? 0?????? 6 0 0 9 6 (0) 0 9 6 0 0 9?????? ?cij????(0) 5 3 2??(0) 5 3 2??(0) 5 3 2?

?????????? 0?1 4 01 4 01 4 0?? ??? ???? ? 0? 0?对于效率矩阵为n阶方阵的最小化指派问题，此时若能得到n个（0）元素，则相应的最优指派方案就确定了. 若所得（0）元素的个数小于n，就要修改效率矩阵，进入下一步骤.

第三步：继续修改效率矩阵 ① 在第二步的最后一个效率矩阵中，过每个（0）元素划一条水平线或竖直线，以覆盖所有0元素（包含（0）、?及0），直

- 17 -

线的个数应与（0）元素个数相同. ② 在直线不穿过（没有覆盖）的所有元素中找出最小元素，记作θ. ③ 没有划水平线的行中各元素减θ，在划竖直线的列中各元素加θ，对所得新的效率矩阵，重新选0元素，回到第二步.

13 7 (0)?-1 ? ? 12 6 (0)?? 0?0 12 6 0?? 0?????? 6 (0) 0 97 0 0 10 7 0 (0) 10???? ?? ??

?(0) 5 3 2?-1 ?0 4 2 ?(0) 4 2 1?1???????? 0??????-1 ? (0) 3 0???? 1 4 0?0 0 3 0?? 0?+1 +1

例3-4的效率矩阵到此已能找到4个不同行、不同列的0元素. 从而相应的最优解为

?0?0?x??ij??1??0000101001??0? ?0?0?将最优解代入目标函数y，可得最优值为：miny?4?8?9?8?29(min)． 这表明，让化验员甲、乙、丙、丁分别担当化验任务D、C、A、B，可使他们总的消耗时间最短，只消耗29min，就能完成四项化验工作.

三、其它类型指派问题的求解

1．最大化指派问题 匈牙利法实质上是一种求最小化指派问题的方法，如果给我们的效率矩阵?bij?中的bij是第i个人去作第j项任务的收益，我们该怎样指派，才能使总收益最大呢？

例3-5 某卫生防疫站准备选拔防疫科、食品科、总务科的三名科长. 几经筛选，仅剩下赵、钱、孙三名候选人. 根据民主评议的统计结果，他们主持各个科的工作能力（以得分多少来衡量）如表3—15所示. 试从工作能力出发，确定各科长的指定方案，使总体效能最大. 表3—15 工作能力表

分析： 用i=1,2,3 分别表示赵、钱、孙三人；用j=1,2,3 分别表示防疫、食品、总务三个科. 则可以设

赵 钱 孙

防疫 35 37 38

食品 30 35 28

总务 27 29 32

工 作 能 力（分）

- 18 -

?1, 表示第i人担任第j科的科长, xij???0, 其他, 于是数学模型为

Max Y???bij xij

i?1j?133?3??xij?1,?i?1?3s.t.??xij?1,?j?1?x?0或 1 ?ij??j?1, 2, 3??i?1, 2, 3? ?i, j?1, 2, 3??353027???其中:?bij???373529?

?382832???实际上，只要找出效率矩阵?bij?中的最大元素b，用b减去矩阵中的每个元素bij，得到的矩阵?cij?我们称为原矩阵对应的缩减矩阵（cij?b?bij）. 易见cij越小表示原效率矩阵中第i个人去作第j项任务的收益越大，反之则收益越小. 因此求?bij?的最大化问题解，等价于求它对应的缩减矩阵?cij?最小化问题的解.

?353027???解 由于?bij???373529?中的最大元素为:b?38,所以它对应的缩减矩

?382832???阵为?cij??b?bij???3811?????139?. 用匈牙利法求?cij?的最优解 ?0106???1?1??3 8 11 ?-3 ?0 5 8 ??0 3 ?(0) 3 ????????-1 1? ? (0) ?cij??? 1 3 9? ?0 2 8? ?0 0 1? ? 0?0 10 7??0 8 0?? 0? 0 10 6?8 (0)????????? ? -2 -7

可见最优解为

?100??010?xij?????，这也是原最大化指派问题的最优解，即派赵、钱、孙分?001???别担任防疫科、食品科和总务科的科长，这样可使总的工作能效达到最大值102分.

2. 效率矩阵不是方阵 在实践中，往往出现人少任务多或人多任务少的情

- 19 -

况. 对效率矩阵来说，表现为矩阵不是方阵. 甚至要求某人不能完成某项任务或某项工作不能由某人去作. 这都需要作适当改进，再应用匈牙利法去解决.

对于效率矩阵不是方阵，可以虚设几行或几列，使其构成方阵，虚设的行（列）的元素要根据目标函数的具体情况确定. 对于后一问题，只要将效率矩阵相应的元素取得充分大（极小问题）或充分小（极大化问题），使得最优指派方案不可能取在该元素上.

例3-6 某研究“SARS”的课题组有三名博士研究员甲、乙、丙，估计他们完成5个子课题A、B、C、D、E的研究任务，能获得利润（单位：万元）分别如表3-16所示，要求每人只能作一个子课题，每项子课题也只能由一个人作，怎样安排工作，可使课题组的总收入最高？ 表3-16 课题研究获利情况 解 3个人要完成5项任务，现虚设2人，构成5人完成5项任务；由于虚设的人是不可能完成任务、获得收益的，因

甲

乙 丙

A 6 8 4

B 5 7 6

C 4 5 7

D 7 4 8

E 6 7 5

而获利为0，这样在效率矩阵中补两行0元素即方阵?bij?，可用匈牙利法求解.

?23?6 5 4 7 6????8 7 5 4 7?01??4 6 7 8 5? b?8 ?cij??b?bij??42?bij??????0 0 0 0 0?88???88?0 0 0 0 0??????412?-1 ?341? 103? ?888?-8 888??-8 10100200??240?002?

?010?010??

?12301??123(0)???01341???(0)13442103? ?4210??cij???????00000?(0)0?0????0?00000??0?(0)0?????0 +1 +1

1?-1 ?1??1?-1 ?03? -1 ?4??0??-8 ?1?0???-8 ?1

?11???(0)0?41??1(0)?10??2(0)0???11??240????(0)0(0)0?2? 或：?41??0?10???1(0)?100?1(0)????20?(0)??240??0?(0)2?

?0?10??(0)10???- 20 -

本文来源：https://www.bwwdw.com/article/zrg6.html