第五章整数规划

第五章整数规划整数规划数学模型纯整数规划的求解0－1规划的求解分支定界法割平面法指派问题非标准形式的指派问题一、整数规划的模型很多实际规划问题都属于整数规划问题1.变量是人数、机器设备台数或产品件数等都要求是整数；2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。例合理下料问题设用某型号的圆钢下零件A1,

A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件方个数式零件零件毛坯数设：xj

表示用Bj(j=1.2…n)种方式下料根数模型：零件方个数式零件零件毛坯数单销地厂址价生产能力建设费用销量例某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi

(i=1.2…m),又有n个地点B1,B2,…Bn需要销售这种产品，其销量分别为b1.b2…bn

。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？设：

xij

表示从工厂运往销地的运量(i=1.2…m、j=1.2…n),1在Ai建厂又设Yi＝（i=1.2…m）0不在Ai建厂模型：例机床分配问题设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。设：1分配第i台机床加工第j种零件；

xij＝（i=1.2…m,j=1.2…n）0相反。于是，第i台机床加工各种零件的总时间为：又由于一个零件只能在一台机床上加工，所以有

因此，求xij，使得例投资项目选取问题

某单位拟利用闲置资金15

万元进行对外投资，现有5个投资项目可供选择，所需资金及投资回报收益期望值为项目所需资金（万元）收益期望值（万元）

ABCDE

64245

108769A，B，C，D，E之间的关系是：①A、C、E三项中需且只能选一项；②B、D两项中需且只能选一项；③选C必须先选D。问题：如何选择投资决策，使总投资期望值最大？解用xj分别表示A，B，C，D，E的被选情况，则于是投资总收益期望值：约束条件：①资金总额限制：②A，C，E选且只选一项：项目所需资金（万元）收益期望值（万元）

ABCDE

64245

108769④选C必须先选D：于是数学模型为以下0－1规划：Þ31x=,41x=Þ,40x=30x=或③B，D选且只选一项：例某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表所示。问两种物品各装多少件，所装物品的总价值最大？解设甲、乙两种物品各装x1、x2件，则数学模型为：物品重量(公斤/每件)体积(m3/每件)价值(元/每件)甲乙1.20.80.0020.002543例在上例中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。(1)所装物品不变；(2)如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为解此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入0－1变量yi，令i=1,2分别是采用背包及旅行箱装载。由于所装物品不变,上例约束左边不变,整数规划数学模型为(2)

不同载体所装物品不一样，数学模型为

M为充分大的正数。可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令(1)右端常数是k个值中的一个时，约束条件为(2)对于m组条件中有k（≤m）组起作用时，约束条件写成这里yi=1表示第i组约束不起作用，yi=0表示第i个约束起作用。当约束条件是“≥”符号时右端常数项应为(3)对于m个条件中有k(≤m)个起作用时，约束条件写成一般地:同样可以讨论对于有m个条件互相排斥、有m(≤m、≥m)个条件起作用的情形。例试引入0－1变量将下列各题分别表达为一般线性约束条件:(1)x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20;(2)若x1≤5，则x2≥0，否则x2≤8;(3)x1取值0，1，3，5，7。解(1)3个约束只有1个起作用或(3)右端常数是5个值中的1个(2)两组约束只有一组起作用(2)若x1≤5，则x2≥0，否则x2≤8;(3)x1取值0，1，3，5，7。整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。整数规划与线性规划的关系

从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。

因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。

目前，常用的求解整数规划的方法有：

分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。分支定界法是一种隐枚举法或部分枚举法，是枚举法基础上的改进。分支定界法的关键是分支和定界。“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。

所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可作为衡量处理其它分支的一个依据。

若整数规划的松驰问题的最优解不符合整数要求，不妨假设不符合整数要求,则可构造两个约束条件和如此不断继续，直到获得整数规划的最优解。这就是所谓的“分支”分支定界法基本思想：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解.通过对松弛问题的分枝，不断降低（IP）最优值的上界，提高下界，当上界等于下界时，得到最优解。1求解纯整数规划的分支定界法IP的松驰问题：②检验与分支：①求解LP:③求解LP1,LP2

：设其解及最优值分别为故对LP1剪支.的最优值均满足：(i)如则LP1及由LP1分支的所有子问题剪支及上下界改进分析(ii)如满足IP的要求时，则当是IP的可行解，故改进下界同理，此时LP1剪支.注意到IP的最优解必是LP1或LP2的可行解,于是或改进上界：④对中不满足IP整数要求的分量，继续分支.例用分支定界法求解下列整数规划模型：解先求对应的松弛问题(记为LP0)：

用图解法得到最优解X＝（3.57,7.14）,Z0=35.7,如下图所示:8.3310松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC101010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.81010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP5尽管LP1的解中x1不为整数，但Z5>Z1因此LP5的最优解就是原整数规划的最优解。上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)

Z1=34.8LP2:X=(4,6.5)

Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)

Z3=35.33x2≤6LP4:X=(4,6)

Z4=34LP5:X=(5,5)

Z5=35x1≤4x1≥5无可行解x2≥7例用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33(18/11,40/11)⑶对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，取值x2

≤3，x2

≥4先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。有下式：现在只要求出（LP1）和（LP2）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如图所示。此时B在点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。11同理求（LP2）,如图所示。在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z2<Z1＝－16∴原问题有比（－16）更小的最优解，但x2不是整数，故利用BAC加入条件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如图所示。此时D在点取得最优解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整数，可继续分枝。即3≤x1≤2。D求（LP4），如图所示。无可行解，不再分枝。在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如图所示。此时E在点取得最优解。即x1＝2,x2=3,Z(5)＝－17找到整数解，问题已探明，此枝停止计算。E求（LP6），如图所示。此时F在点取得最优解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如对Z(6)继续分解，其最小值也不会低于－15.5，问题探明,剪枝。至此，原问题（IP）的最优解为：

x1=2，x2=3,

Z*=Z(5)

＝－17以上的求解过程可以用一个树形图表示如右：LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP3x1=12/5,x2=3Z(3)＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)＝－17LP6x1=3,x2=5/2Z(6)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃用分枝定界法求解整数规划问题LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)＝3LP6无可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)＝61/14LP4无可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤2x1≥3＃＃LP1x1=1,x2=7/3Z(1)＝10/3LPx1=2/3,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9LP3x1=33/14,x2=2Z(3)＝61/14LP4无可行解LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例用分枝定界法求解整数规划问题（单纯形法）x1=13/4

x2=5/2Z(0)=59/4≈14.75

选x2进行分枝，即增加两个约束，2≥x2≥3有下式：分别在(LP1)和(LP2)中引入松弛变量x5和x6

，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3

得下表:32000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2

Z(1)=29/2=14.5继续分枝，加入约束

3≥x1≥4LP132000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵Z(2)<Z(1)∴先不考虑分枝接(LP1)继续分枝，加入约束4≤x1≤3，有下式：分别引入松弛变量x7和x8，然后进行计算。CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3x1=3,x2=2

Z(3)=13找到整数解，问题已探明，停止计算。LP3CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1x1=4,x2=1

Z(4)=14找到整数解，问题已探明，停止计算。LP4树形图如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4＃＃＃练习：用分枝定界法求解整数规划问题

（单纯形法）cj-1-5000cBxBbx1x2x3x4x50x32-111000x4

30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1

18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/110LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP3x1=12/5,x2=3Z(3)＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)＝－17LP6x1=3,x2=5/2Z(6)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃先不考虑整数约束，按一般线性规划问题求其最优解，线性规划问题的最优基本可行解是解集的一个极点，这个极点的的坐标未必都是整数，若不是整数解，可增加一条约束，相当于增加一个平面将这个极点割掉，称这种方法为割平面法。割平面法的基本思想例求解整数线性规划问题

CB

sOAx1

x2解引入松驰变量将其化为标准形式，利用单纯形法求其最优解。最优单纯形表如下

从最优单纯形表中看出约束条件变成

变形得上式分别记为

都应小于等于0的整数。引进多余变量

1100

111

00.2500100.252.752.500-0.25-0.25

用对偶单纯形法求解

110000

1100100.250000100.250000-0.25010000-0.25012.752.5-0.75-0.5

00-0.25-0.2500

取i=3为主元行,k=3为主元列,进行换基迭代。再取i=4为主元行，k=4为主元列，进行换基迭代得表。

110000

11001000100100010010-4000010-422320000-1-1

最优基本可行解为：

设纯整数规划松弛问题的最优解2求解IP的割平面法单纯形法最终表设xi不为整数，将分离成一个整数与一个非负真分数之和：则有上式两边都为整数并且有加入松弛变量si得此式称为以xi行为源行(来源行)的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束方程加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则例如，x1行：移项：令加入松弛变量s1得同理，对于x2行有：例用割平面法求解下列IP问题解放宽变量约束，对应的松弛问题是加入松弛变量x3及x4后，用单纯形法求解，得到最优表

最优解X(0)＝(5/2，15/4),不是IP的最优解。选择表的第一行(也可以选第二行)为源行Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4分离系数后改写成加入松弛变量x5得到高莫雷约束方程将上式作为约束条件添加到上表中，用对偶单纯形法计算，如表所示:Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4[－2]0015/215/4－2→λj00－5/8－1/4↑0430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最优解X(1)＝(3，3)，最优值Z＝21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。

如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。正则解1求解0－1整数规划的隐枚举法（适合于变量个数较少的0-1规划）隐枚举法的步骤：1.找出任意一可行解，目标函数值为Z0；

2.

原问题求最大值时，则增加一个约束当求最小值时，上式改为小于等于约束；

3.列出所有可能解，对每个可能解先检验式(*)，若满足再检验其它约束，若不满足式(*)，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值；

4.目标函数值最大(最小)的解就是最优解。0－1规划的求解

例用隐枚举法求解下列BIP问题解(1)不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到X0＝(1，0，0，1)是一个可行解，目标值Z0＝11是BIP问题的下界，构造一个约束：原BIP问题变为(2)列出变量取值0和1的组合，共24＝16个，分别代入约束条件判断是否可行。首先判断式(a)是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见下表所示。

3.列出所有可能解，对每个可能解先检验式(*)，若满足再检验其它约束，若不满足式(*)，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值；jXjabcdZjjXjabcdZj1(0,0,0,0)×

9(1,0,0,0)×

2(0,0,0,1)×

10(1,0,0,1)√√√√113(0,0,1,0)×

11(1,0,1,0)×

4(0,0,1,1)×

12(1,0,1,1)√√√√145(0,1,0,0)×

13(1,1,0,0)×

6(0,1,0,1)×

14(1,1,0,1)√√√√137(0,1,1,0)×

15(1,1,1,0)√×

8(0,1,1,1)×

16(1,1,1,1)√√√×

(3)由上表知，BIP问题的最优解：X＝(1，0，1，1)，最优值Z＝14。注：(1)选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于1。当目标函数求最小值时，先考虑目标函数系数最大的变量等于0；(2)在上表的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。指派问题例人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人．经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088解设1数学模型数学模型为：甲乙丙丁ABCD

假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij≥0，效率矩阵为[cij]，如何分配工作使效率最佳(min或max)的数学模型为2解指派问题的匈牙利算法匈牙利法的条件：问题求最小值、人数与工作数相等及效率非负

定理1如果从分配问题效率矩阵[cij]的某一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从某一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵[bij]，其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解，这里cij、bij均非负．定理2若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素(称为独立元素)的最大个数．如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解．例某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本(元/件)如表所示．求最优生产配置方案．产品1产品2产品3产品4工厂27550150230工厂36570170250工厂48255200280解问题求最小值。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有第二步：找出矩阵每列的最小元素，再分别从每列中减去，有

第三步：用最少的直线覆盖所有“0”，得第四步：这里直线数等于3(等于4时停止运算)，要进行下一轮计算．从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k＝5．

直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵第四步等价于第1、3行减去5，同时第1列加上5得到的结果第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素．容易看出4个“0”的位置()()()()或()()()()得到两个最优解有两个最优方案第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2；第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；单件产品总成本Z＝58＋150＋250＋55＝513例有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982求解过程如下：第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=3<n=

4第三步，作最少的直线覆盖所有0元素：

◎