运筹学-4整数规划

引言在线性规划问题中，所有的解都假设为具有连续型的数值，即解可以是整数、分数或带有小数点的实数。但对于某些具体的问题，常要求最优解是整数的情形。例如，所求的解是机器台数，完成工作的人数或装货的车数等，这时，分数或小数的解答就不符合要求。为了满足整数解的要求，初看起来，似乎只要把已求得的解经过“舍入化整”就可以，但这常常是不可行的。因为化整后不见得是可行解。或虽然是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。本章内容分支定界法0－1型整数规划3整数规划的数学模型及解的特点124指派问题第一节整数规划的数学模型

及解的特点一、整数规划的数学模型的一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划（全整数规划）、混合整数规划、0－1整数规划。

本章仅讨论整数线性规划。

纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。

混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。

0－1整数规划：所有决策变量只能取0或1两个整数。整数规划问题类型二、整数规划的例子

例2

某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定，服务员连续工作8h为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。时段12345678服务员最少数量10891113853

解：设在j时段开始上班的服务员人数为xj。由于第j时段开始时上班的服务员将在第（j+3）时段结束下班，所以决策变量只需考虑x1,x2,x3,x4,x5。

问题的数学模型为：纯整数规划问题40－1整数规划问题三、整数规划解特点整数线性规划及其松驰问题，从解的特点来看，二者之间既有密切的联系，又有本质的区别。整数规划放松的线性规划∩≤松弛问题的最优值是原整数规划的目标函数值的上界整数规划解的特点最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多于顶点，枚举法不可取注释从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。整数规划=相关的线性规划+整数约束整数规划是约束得更紧的问题,它的可行域是其相关线性规划问题可行域的一个子集；整数解的数目远少于线性规划的解，只要可行域有界，整数解的数目有限；整数规划的求解难度远大于线性规划。总结：整数规划与线性规划的关系例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题。用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3)

因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。其中（2，2）（3，1）点为最大值，Z=4。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。x1x2⑴⑵33(3/2,10/3)求解整数规划方法穷举法：方法简单，只可解小问题，计算量很大；对0-1整数规划，计算量为2n，按指数增长；四舍五入法：解的质量差，有时无法得到可行解分枝定界:

计算效率高,应用广泛;割平面法:

有理论意义,但计算效率较低；启发算法:

效率高,但不能保证找到最优解,可解大规模问题。第二节分支定界法一、基本思想

分支定界法可用于解纯整数或混合的整数线性规划问题。由于此方法灵活且便于用计算机求解，所以现在它已是解整数线性规划的重要方法。

设有最大化的整数线性规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界；而A的任意可行解的目标函数值将是z*的一个下界。分支定界法就是将B的可行域分成子区域(称为分支)的方法，不断降低上界，提高下界，最后使得上下界相等，即求得最优解z*。定界基本思想检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于（max)其他分支的目标函数值，则将其他减去不再计算；若还存在非整数解并且目标函数值大于（max)整数解的目标值，需要继续分支，再检查，直到得到最优解。隐枚举法求解放松问题最优解为整数最优值比界差最优解为非整数

最优值比界好分支边界分支定界舍弃二、具体解题步骤1.先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：

⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。

⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。

⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：若(LP)的最优解不符合整数要求，假设xi=

（不为整数），以[]表示不超过的最大整数。构造两个约束条件

xr≤[]

和xr≥[]

＋1将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2),从而形成两个分支。2.分支3.定界（修改上下界）

定界：是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可作为衡量处理其他分支的一个依据。按照以下两点规则进行：⑴.在各分枝问题中，找出目标函数值最大者作为新的上界；⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。4.比较与剪支各分枝的目标函数值中，若有小于下界者，则剪掉此分支，表明此子问题已经探清，不必再分支了;否则继续分枝。如此反复进行，直到得到下界等于上界为止，即得最优解X*

。补充例子：用分枝定界法求解整数规划问题（用图解法计算）记为（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≥2

x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。12有下式：现在只要求出（LP1）和（LP2）的最优解即可。

先求（LP1）,如图所示。此时B

在点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。同理求（LP2）

,如图所示。在C

点取得最优解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原问题有比（－16）更小的最优解，但x2不是整数，故利用

3≥10/3≥4

加入条件。x1x2⑴⑵33(18/11,40/11)⑶11BAC加入条件：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以上的求解过程可以用一个树形图表示如右：例（p132)用分枝定界法求解整数规划问题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＃＃＃＃分枝定界法计算过程总结：上界x1≤[x*01]x1≥[x*01]+1用分枝定界法求解下题【解】先求对应的松弛问题（记为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>Z因此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从分支定界法的原理和步骤可知，它也适用于求解混合整数规划问题。补充说明：第三节0－1型整数规划0-1变量作为逻辑变量，可以数量化地描述开与关、取与弃、有与无等逻辑现象。一些其它非0-1规划可以化为0-1规划来处理。0－1整数规划是一种特殊形式的整数规划，这时的决策变量xi

只取两个值0或1。一、0－1变量及其应用逻辑变量逻辑（0-1）变量在建立数学模型中的作用（1）m个约束条件中只有k

个起作用设

m

个约束条件可以表示为：定义逻辑变量又设

M

为任意大的正数，则约束条件可以改写为：定义逻辑变量：此时约束条件可以改写为：（2）约束条件的右端项可能是r个值中的某一个即（3）两组条件满足其中一组若x1≤4，则x2≥1（第一组条件）；否则当x1>4时，x2≤3（第二组条件）.定义逻辑变量：又设M

为任意大正数，则问题可表达为：需注意，当约束为大于时，右端项中用减号。10做第i件事不做第i件事n件事中必须做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要条件是做第j件事做第i件事的充要条件是不做第j件事只在做了第i件事前提下才考虑是否做第j件事

0-1规划的实例－例1某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）A1,A2,…,A7

可供选择。规定

在东区：由A1,A2,A3三个点中至多选两个；

在西区：由A4,A5两个点中至少选一个；在南区：由A6,A7两个点中至少选一个。

如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？解：解题时先引入0－1变量Xi(i=1,2,…,7)令

数学模型为：该公司只有600万资金可用于投资，由于技术上的原因，投资受到以下约束：

1、在项目1、2和3中必须有一项被选中

2、项目3和4只能选中一项且必须选中一项；

3、项目5被选中的前提是项目1被选中;如何在满足上述条件下选择一个最好的投资方案，使投资收益最大？例2（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收益（万元）12101502300210310060413080526018010投资第i个项目不投资第i个项目Z表示投资效益投资项目模型：试引入0－1变量将下列各题分别表达为一般线性约束条件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，则x2≥0，否则x2≤8（3）x2取值0，1，3，5，7【解】（1）3个约束只有1个起作用

0-1规划的实例－例3（3）右端常数是5个值中的1个（2）两组约束只有一组起作用例4（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140

请为该市制定一个最节省的计划在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型：例5.固定费用问题（FixedCostProblem）

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。

有三种资源被用于生产三种产品，资源约束、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表，要求制定一个生产计划，使总收益最大。IIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012解：总收益＝销售输入－（固定费用＋可变费用）建模的困难：事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生？其中Mj为对应xj的某个上界;这是处理xj与yj一对变量之间逻辑关系的特殊约束当xj>0时，yj＝1，当xj＝0时,为使得Z具有最大值，有yj＝0。解0-1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大（例如n>10），这几乎是不可能的。

因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（ImplicitEnumeration）。?0－1型整数规划的求解二、0－1型整数规划的解法在2n个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。对于可行解，其目标函数值也有优劣之分，若已发现一个可行解，则根据它的目标函数值可以产生一个“过滤条件”。对于目标函数值比它差的变量组合就不必再去检验它的可行性，在以后的求解过程中，每当发现比原来更好的可行解，则以此替换原来的过滤条件。例、求解下列0－1规划问题

解：完全枚举法由上表可知，问题的最优解为X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1

是一个可行解，为尽快找到最优解，可将3

x1－2x2＋5x3≥5作为一个约束，凡是目标函数值小于5的组合不必讨论，如下表。隐枚举法Z过滤条件Z≥Z≥6改进的算法：为减少运算量，常按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解有可能较早出现。对于最大化问题，可按由小到大的顺序排列；对于最小化问题，则相反。72

0-1规划的隐枚举法是一种特殊的分枝定界法，其基本思想是利用变量只能为0或1两个值的特性，进行分枝定界，以减少枚举而达到求出最优解之目的。该法适用于任何0-1规划问题的求解，包括指派问题。了解内容：0-1规划的隐枚举法

隐枚举法首先要将问题化为规范形。（1）0-1规划的规范形为73（2）化规范形的方法：1）如果目标函数为求极小值，则对目标函数两边乘以-1，化为求极大值；2）若目标函数中某变量xj的系数cj>0，则令xj=1-yj3）如果约束条件是“”形，则可两边乘-1，改为“”形；4）若某个约束条件为“=”形，则化为两个“”的不等式,如74例、用隐枚举法求解下列0-1规划解：令x1=1-y1,x3=1-y3,x5=1-y5,x2=y2,x4=y4化为规范形得：75其求解过程如下图所示：y4=0y5=101234567810911121314Z=11y3=1y3=0y4=1y5=1y5=0y2=1y2=0y4=0y4=1y5=0y1=0y1=1可行解z=3可行解z=1可行解z=2不可行子域不可行子域可行解z=6可行解z=2不可行子域由此可知，最优解为x3=x4=x5=1,x1=x2=0,maxz=6用隐枚举法求解下列问题【解】（1）不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到X0＝(1，0，0，1)是一个可行解，目标值Z0＝11是该问题的下界，构造一个约束：

，原问题变为课后练习：0－1规划求解(2)列出变量取值0和1的组合，共24＝16个，分别代入约束条件判断是否可行。首先判断式（3.9）是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见下表所示。jXj3.9a3.9b3.9c3.9dZjjXj3.9a3.9b3.9c3.9dZj1(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)由上表知，问题的最优解：X＝（1，0，1，1），最优值Z＝14第五节指派问题如何分配合适的事情给合适的人，是领导才能有的事情没有人做有的人没有事情做如何人尽其才？？？原理：从人的角度思考……..考虑人最适合的工作从工作的角度思考…….考虑工作最适合的人一、指派问题的标准形式及其数学模型（一）、指派问题的数学模型设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（或时间、费用最少）最高？

被指派的人数与任务的数目相等。每个被指派的人员只完成一项任务，而且每项任务必有一人去完成。第i个被指派的人去完成第j项任务的费为cij

。指派问题的要解决的问题是：如何指派任务，可以使总费用最少？

在指派问题中假设:

设决策变量

1分配第i个人去做第j件工作

xij=0相反(I,j=1.2.…n)其数学模型为：表明每件事必有且只有一个人去做表明每个人必做且只做一件事例：红旗超市计划开办5家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。请问应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？B1B2B3B4B5

A14871512A279171410A3691287

A46714610

A56912106已知数据应为什么？建筑公司Ai(i＝1,2,…,5)对新商店Bj(j=1,2,…,5)的建造费用的报价（万元）为cij(I,j=1,2,…,5),解：

设决策变量

1当Ai承建Bj时

xij=0当Ai不承建Bj时(i,j=1.2.…n)商店公司B1B2B3B4B5任务A1（4）（8）（7）（15）（12）1A2（7）(9)(17)(14)(10)1A3(6)(9)(12)(8)(7)1A4(6)(7)(14)(6)(10)1A5(6)(9)(12)(10)(6)1所选的公司数111115例：有一份中文说明书，需译成英、日、德、俄四种文字（记作E、J、G、R）。现有甲、乙、丙、丁四人，他们将说明书翻译成不同文字所需要的时间如表一所示。问应指派何人去完成哪一项工作，使所需总时间最少？效率矩阵

任务人员ABCD甲67112乙4598丙31104丁5982二、指派问题的解法——匈牙利解法问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）匈牙利解法成立的基础【定理1】如果从分配问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[bij]，其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解，这里cij、bij均非负．【证】两个目标函数相差一个常数u+v,约束条件不变,因此最优解不变。原理：对C的行和列减去某个常数，将C化的尽可能简单，简单到可一眼看出该问题的最优解当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵中必然出现一些零元素。设=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作以第i人来干效率(相对)最高。也是一个独立零元素组。不是一个独立零元素组。问题是：能否找到位于不同行、不同列的n个0元素？定义在效率矩阵C中，有一组处于不同行、不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。例已知则是一个独立零元素组，但有的效率矩阵独立零元素的个数不到n,很难找到最优指派方案。已知效率矩阵怎么办？【定理2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立0元素）的最大个数．如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值为0，得到最优解．匈牙利解法的步骤

第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，具体进行两步操作：

(1)从（cij）的每行元素都减去该行的最小元素；

2497得到的0表示：这个0所在的行对应的人最适合的工作是这个0所在的列对应的事这一列有三个0，表示这一列的事有三个人适合作(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。42第二步：试分派n较小时，可用观察法、试探法找n个独立元素，n较大时，用下面方法：(1)从只有一个0元素的行(列)开始，对0元素加框，化去0所在列（行)的其它0元素，记作×(2)反复进行(1)，直到不再有0元素可圈和划去。(3)当同行(列)有两个或两个以上0元素时，试探法(4)若加框0元素的数目m=n，已得最优解，即令这些加框0元素对应xij=1,其它0元素xij=0◎Ø◎ØØ◎◎这时已经找到了4个位于不同行不同列上的0元素，所以，该问题的最优解矩阵是：3、以最少的直线划去所有0元素n较小时，可用观察法，n较大时，用下面方法(1)对没有加框的0所在的行打√(2)对已打√的行中所有含0元素列打√(3)再对打有√的列中含框的0元素行打√(4)重复（2）和（3）直到得不出新的打√号的行，列为止.(5)对没有打√号的行画一横线,有打√号的列画一纵线,这就得到覆盖所有0元素的最少直线数.若m<n，转下步。某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如表5-35所示．求最优生产配置方案．表5-35产品1产品2产品3产品4工厂27550150230工厂36570170250工厂48255200280【解】问题求最小值。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有例：指派问题第二步：找出矩阵每列的最小元素，再分别从每列中减去，有第三步：找独立零元素，用最少的直线覆盖所有“0”，得第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算．从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k＝5．直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵第四步等价于第2、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丁598