运筹学-4-整数规划

运筹学运筹帷幄之中决胜千里之外整数规划IntegerProgramming第四章第四章整数规划本章主要内容：整数问题规划及其数学模型整数规划问题的求解0-1型整数规划问题指派问题第四章整数规划在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。

整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。第四章整数规划线性规划模型：实际问题要求xi为整数！如机器的台数，人数等第四章整数规划例:胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？第四章整数规划纯整数规划第四章整数规划例（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有m件物品，第i件件物品的重量为bi，价值为ci，问题就变成：在携带的物品总重量不超过b公斤的条件下，携带哪些物品可使总价值最大?第四章整数规划9解：Z表示所带物品的总价值携带物品的总重量数学模型：0-1规划第四章整数规划第四章整数规划解：数学模型：混合型整数规划第四章整数规划例

工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。第四章整数规划解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：第四章整数规划混合整数规划问题第四章整数规划整数线性规划问题的种类：

纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。第四章整数规划纯整数规划的数学模型：0--1规划的数学模型：第四章整数规划例×√√√√Z=130√√√√，可行且Z=140不可行可行第四章整数规划（IP）（IP）问题的松弛问题第四章整数规划∩≤松弛问题的最优值是原整数规划的目标函数值的上界第四章整数规划例

设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。第四章整数规划用图解法求出最优解为：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。第四章整数规划-分支定界法1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束：xi≤[xi]和xi≥[xi]+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。分支定界法的解题步骤：上界x1≤[x*01]x1≥[x*01]+1当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求的最优解一、分枝定界法的原理：1、分枝··················012345678·松弛问题的可行域增加x1≤3增加x1≥4L1L2x1≤3x1≥4父问题子问题结论1：（IP）的最优解一定在某个子问题中父问题的最优值≤3：子问题中的整数解都是（IP）的可行解子问题的最优解2：子问题的可行域父问题的可行域∩2、定界1、（LP）的最优值是(IP)的最优值的上界IP松弛问题L0L1L2通过对（L0）分枝，使（IP）的最优值的上界不断下降，L3L4L5L6下界不断上升，上界=下界得最优值··················012345678·x1≤3x1≥4z=30x1+20x24x1+x2=16.52x1+3x2=14.5x2≤2x2≥3x1≤2x1≥3混合型x1≤3x1≥4L0的最优单纯型表：x1x2x3x4常数项检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5100013000x1≤3x1≥4x1≤2x1≥3x2≤2x2≥3x1x2x3x4解检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5100013000x1x2x3x4解检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5001/10-3/101-1/2000x1x2x3x4解检00-20/30-50/3Z-440/3x2011/30-2/317/6x110001300-1/31-10/35/3x4x5x2≤2x2+x6=2x1x2x3x4x5

解检00-20/30-50/3Z-440/3x2011/30-2/317/6x1100013x400-1/31-10/35/3x60100012x60000x1x2x3x4x5

x6

解检00-20/30-50/30Z-440/3x2011/30-2/3017/6x11000103x400-1/31-10/305/3x600-1/302/31-5/6x1x2x3x4x5

x6

解检0000-30-20Z-130x20100012x11000103x40001-4-15/2x30010-2-35/2x2≥3X2-x6=3x1x2x3x4x5

解检00-20/30-50/3Z-440/3x2011/30-2/317/6x1100013x400-1/31-10/35/3x60-10001-3x60000x1x2x3x4x5

x6

解检00-20/30-50/30Z-440/3x2011/30-2/3017/6x11000103x400-1/31-10/305/3x6001/30-2/31-1/6-X2+x6=-3x1x2x3x4x5

x6

解检00-1500-25Z-285/2x201000-13x1101/2003/211/4x400-210-55/2x500-1/201-3/21/4x1x2x3x4x5

x6

解检00-1500-25Z-285/2x201000-13x1101/2003/211/4x400-210-55/2x500-1/201-3/21/4x1≤2x1+x7=2X700000x710000012x1x2x3x4x5

x6

x7

解检00-20/3000-50/3Z-130x2011/3000-2/37/2x110000012x400-1/3100-10/35x5000010-11x6001/3001-2/31/200-1/200-3/21-3/4如何选择分枝的节点及分枝变量？1、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点，提高搜索效率。方法：（1）深探法：（2）广探法：最后打开的节点最先选择选择有最大目标函数值的节点继续向下分枝2、分枝变量选择的原则：寻找那些对问题影响最大的变量首先分枝（1）按目标函数系数选择：选择目标函数系数绝对值最大的变量首先分枝（2）按非整数变量选择：选择与整数值相差最大的非整数变量进行分枝（3）按人为给定的顺序选择x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3第四章整数规划-割平面法割平面法的基本思想：若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.················割平面39问题：如何寻找割平面？增加的约束方程须满足什么条件才能使：1、割掉松弛规划的最优解2、保留所有的整数解40二、割平面法41L0的最优单纯形表：x1…xi…xmxm+1…xm+j…xn解检0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0源方程42------对应于生成行i的割平面43L0的最优单纯形表：x1…xi…xmxm+1…xm+j…xn解检0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0生成行对应于生成行i的割平面非基变量44b010.500-0.5100-1.75103.255.500-1011310-0.25000.751.500-0.500-1.5z-9对应第2行的割平面：对应第4行的割平面：45非基变量46如何求解？47x1…xi…xmxm+1…xm+j…xn解检0…0…0c1…cm+j…cnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0ss0…0…0-fim+1…-fim+j…-fin1–fi0

00︰0︰0对偶单纯形法48割平面计算步骤第一步：用单纯形法解整数问题IP的松弛问题L0若L0没有最优解，则IP没有最优解。停止若L0有最优解X0:(1)X0是整数解，则X0也是IP的最优解，停止(2)X0不是整数解，转第二步第二步：求割平面方程49第三步：将割平面加到L0得L1第四步：解L1在L0的最优单纯形表中增加一行一列，得L1的单纯形表，用对偶单纯形法求解，若其解是整数解，则该解也是原整数规划的最优解否则将该解记为X0，返回第二步50例用割平面法求解IP解：IP问题的松弛规划的标准型：X1X2X3X400-2.25-1.75Z-37.5X2010.25-0.251.5X1100.1250.3753.75

X5000X500-0.125-0.3751-0.75X1X2X3X4X5ZX2

X1

X4

000.3331-2.6672100013010.3330-0.667200-1.6670-4.667z-34整数最优值：Z=3451

例：用割平面法求解解：IP的松弛规划的标准型X1X2X3X400-28/11-15/11Z-63X2017/221/227/2X110-1/223/229/2

X500-7/22-1/221-1/2X5000X1X2X3X4X5X2

X1X3

0011/7-22/7

11/71001/7-1/732/7010013000-1-8Z-59非整数52X1X2X3X4X5X2

X1X3

0011/7-22/711/71001/7-1/732/7010013000-1-8Z-59X6000-1/7-6/71-4/7X60000X1X2X3X4X5X60000-2-7Z-55X20100113X11000-114X30010-411X4

00016-7

4整数最优值：Z=5553作业：分别用分枝定界法和割平面法求解整数规划：最优值为：Z=454第四章整数规划-0-1整数规划0—1型整数规划是整数规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0—1变量，或称二进制变量。xi仅取值0或1这个条件可由下述约束条件：

xi≤1

xi≥0，整数所代替，和一般整数规划的约束条件形式一致的。第四章整数规划-0-1整数规划投资场所的选择—相互排斥的计划例：某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai（i=1，2，…，7）可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为Ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？第四章整数规划-0-1整数规划令xi=1，2，…，7（三点中最多选两点）（两点中至少选一点）（两点中至少选一点）决策变量：投资项目AiORnot投资项目Ai利润第四章整数规划-0-1整数规划（1）两个约束中，只有一个起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

例

含有相互排斥的约束条件的问题解：引入0-1变量Y1,Y2和足够大的正数M，则a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=1第四章整数规划-0-1整数规划（2）互相排斥的多个约束中，只有一个起作用ai1x1+ai2x2+…+ainxn

bi(i=1,…,m)互相排斥m个约束，只有一个起作用:ai1x1+…+ainxn

bi+yiM

(i=1,…,m)y1+…+ym=m-1yi为0或1M>0（3）若a个约束条件中只能有b个起作用。则令0－1变量之和为a-b。注意：可用统一M，但M的取值必须足够的大。第四章整数规划-0-1整数规划1问题的提出:已知：两种货物装箱每种货物装箱利润体积限制重量限制决策变量:两种货物各多少箱MaxZ=利润最大？箱数不能为分数货物X1货物X2限量体积5424重量2513利润2010相互排斥的约束条件第四章整数规划-0-1整数规划互相排斥的约束条件（假设有车、船2种运输方式）用车运的体积约束用船运的体积约束第四章整数规划-0-1整数规划固定费用的问题在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。第四章整数规划-0-1整数规划例

固定费用问题解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。

单耗量产品资源IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012第四章整数规划-0-1整数规划maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X35002X1+3X2+4X3300X1+2X2+3X3100X1

M1Y1X2

M2Y2X3

M3

Y3X1,

X2,

X30整数Y1,Y2,Y3为0－1变量，M1,M2,M3为任意大正数。

s.t.第四章整数规划-隐枚举法在整数规划模型中，若变量取值为0或1两个特殊的数值，则称此类模型为0—1的使用及建立模型的方法。隐枚举法基本思想：隐枚举法是分枝定界法思想的延伸。通过放松主约束条件（而非变量符号限制条件）求得最优解，再检查是否满足约束条件，再经过分枝与剪枝等工作迭代出最优解。第四章整数规划-隐枚举法在2n个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。对于可行解，其目标函数值也有优劣之分。若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合不必再去检验它的可行性。在以后的求解过程中，每当发现比原来更好的可行解，则替换原来的过滤条件。第四章整数规划-隐枚举法0-1规划求解MaxZ=3X1－2X2

＋5X3X1+2X2

－X3<=2（1）X1+4X2+X3<=4（2）X1+X2<=3（3）

4X2+X3<=6（4）X1,X2,X3=0或者1（5）解：观察（X1,X2,X3

）＝（1，0，0）满足约束（1）－（5）相应Z=3增加一个约束,目标值>=33X1－2X2

＋5X3>=3（*）称为过滤条件（FilteringConstraint）第四章整数规划-隐枚举法

逐一检查如下点是否满足约束条件？

约束条件（左边）满足约束条件?Z值约束（*）左约束（1）左约束（2）左约束（3）左约束（4）左（0，0，0）0不（0，0，1）5－1101是5（0，1，0）-2不（1，0，0）31110是（0，1，1）31不（1，0，1）80211是8（1，1，0）1不（1，1，1）62不于是最优解（X1,X2,X3

）＝（1，0，1）MaxZ=83X1－2X2

＋5X3>=3（*）称为过滤条件（FilteringConstraint）第四章整数规划-隐枚举法MaxZ=－2X2

＋3X1

＋5X3

目标函数按系数递增（－2，3，5）

约束条件也按上面决定的顺序－2X2

＋3X1

＋5X3>=3

（*）

2X2

＋X1－X3<=2（1）

4X2+

X1＋X3<=4（2）

X2

＋X1

<=3

（3）

4X2+

X3<=6

（4）

X1,X2,X3=0或者1

（5）解：变量（X1,X2,X3）按下面顺序容易更早发现最优解：（0，0，0）（0，0，1）（0，1，0）（0，1，1）…….

逐一检查如下点是否满足约束条件？

约束条件（左边）满足条件?Z值（*）左（1）左（2）左（3）左（4）左（0，0，0）0<3不（0，0，1）5>3－1101是5改进过滤条件，用：3X1－2X2

＋5X3>=5（*）为过滤条件

逐一检查如下点是否满足约束条件？

约束条件（左边）满足条件?Z值（*）左（1）左（2）左（3）左（4）左（0，1，0）3不（0，1，1）80211是8这里已经更换了x1,x2的位置(x2,x1,x3)再改进过滤条件，用：3X1－2X2

＋5X3>=8（*）为过滤条件

逐一检查如下点是否满足约束条件？

约束条件（左边）满足条件?Z值（*）左（1）左（2）左（3）左（4）左（1，0，0）-2<8不

（1，0，1）3<8不

（1，1，0）1<8不（1，1，1）6<8不这里已经更换了x1,x2的位置(x2,x1,x3)MaxZ=－2X2＋3X1

＋5X3

目标函数按系数递增（－2，3，5）约束条件也按上面决定的顺序－2X2＋3X1

＋5X3>=3（*）

2X2＋X1－X3<=2（1）

4X2+

X1＋X3<=4

（2）

X2

＋X1

<=3（3）

4X2+

X3

<=6（4）

X1,X2,X3=0或者1

（5）解：变量（X1,X2,X3

）按下面顺序容易更早发现最优解：（1，0，1）对应目标函数系数（3，-2，5）负系数的Xi取0，正系数的Xi取1这时目标函数达到最大值，但不一定满足约束条件；如果满足约束条件，则不必检验其他解，一步直达。这里已经更换了x1,x2的位置第四章整数规划-隐枚举法在解决0-1规划问题时，为了进一步减少运算量，常按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解有可能较早出现。

对于最大化问题，可按目标函数中各变量系数由小到大的顺序排列。对于最小化问题，可按目标函数中各变量系数由大到小的顺序排列。第四章整数规划-隐枚举法求解0—1整数规划

maxf(x)=3x1-2x2+5x3

s.t.x1+2x2-x3≤2

x1+4x2+x3≤4

x1+x2

≤3

4x2+x3≤6

x1,x2,x3=0或1

第四章整数规划-隐枚举法求解0-1整数规划

minf(x)=3x1+7x2-x3+x4s.t.2x1-x2+

x3-

x4

≥1

x1-x2+6x3+

4x4

≥8

5x1+3x2+

x4

≥5

x1,x2,x3,x4=0或1

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…n指派问题模型：i=1,2,…,nj=1,2,…,n第i个人做第j件事Z表示总费用i=1,2,…,n;j=1,2,…,n第i个人不做第j件事1、指派问题的数学模型76i=1,2,…,nj=1,2,…,n当n=4时，有16变量，8个约束方程77例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。工作人费用123412343545676889810101091110第i人做第j件事Z表示总费用i=1,2,3,4;j=1,2,3,4第i人不做第j件事782、费用矩阵

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…ncij表示第i个人做第j件事的费用费用矩阵79例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人收费用1234123435456768898101010911费用矩阵对应一个5个人5个工作的指派问题第2个人做第4个工作的费用5第4个人做第2个工作的费用080定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。n个人n个工作的指派问题1-b3、匈牙利法n个人n个工作的指派问题281i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n-b8283-bi=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n84任务：对C的行和列减去某个常数，将C化的尽可能简单，简单到可一眼看出该问题的最优解-b85指派问题的最优解：若C中有n个位于不同行不同列的零元素，则令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解i=1,2,3,4j=1,2,3,4可行解最优解86匈牙利法的基本思路：对费用矩阵C的行和列减去某个常数，将C化成有n个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，即得指派问题的最优解87例：有一份说明书要分别译成英、日、德、俄四种文字，现交给甲、乙丙、丁四个人去完成，每人完成一种。由于个人的专长不同，翻译成不同文字所需的时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？工作人时间英日德俄甲乙丙丁2151341041415914161378119-2-4-9-7最优方案：

甲翻译俄文，乙翻译日文丙翻译英文，丁翻译德文总费用：28小时-4-288-2-4-9-7-4-2最优解的取法：从含0元素最少的行或列开始，圈出一个0元素，用○表示，然后划去该○所在的行和列中的其余0元素，用×表示，依次类推，若能得到n个○，则得最优解X089例：求费用矩阵为右表的指派问题的最优解工作人费用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4得4个○，且不存在没打×的0修改方法！90对n阶费用矩阵C，若C有n个位于不同行不同列的零元素，即可得最优解X0。否则，对C进行调整。-2+2-2最优指派方案：甲做B工作，乙做C工作丙做A工作，丁做D工作戊做E工作？？91当C没有n个位于不同行不同列的零元素时，对C进行调整。第一步：做能复盖所有0元素的最小直线集合：1）对没有○的行打√号2）对打√号的行上所有0元素的列打√号3）再对打√号的列上所有○的行打√号4）重复以上步骤直到得不出新的打√号为止5）对没有打√号的行画横线，所有打√号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合具体步骤：√√√92第二步：在没有被直线复盖的元素中找出最小元素，让打√号的列加上这个元素，打√号的行减去这个元素第三步：对所得到的矩阵画○，若能得到n个○，则得最优解，否则重复以上步骤，直至得到n个○。√√√+2-2-293例：求费用矩阵为下表的指派问题的最优解工作人费用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4√√√+2-2-2最优指派方案：甲做B工作乙做C工作,丙做A工作丁做D工作,戊做E工作=3294匈牙利法的具体步骤：第一步：变换指派问题的费用矩阵，使其在各行各列都出现0元素：方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画○）方法：从含0元素最少的行或列开始，圈出一个0

元素，用○表示，然后划去该○所在的行和列中的其余0元素，用×表示，依次类推。若矩阵中的○的个数等于n，则得最优解若矩阵中的○的个数<n，则进行第三步95第三步：做能覆盖所有0元素的最小直线集合：1）对没有○的行打√号2）对打√号的行上所有0元素的列打√号3）再对打√号的列上所有○的行打√号4）重复以上步骤直到得不出新的打√号为止5）对没有打√号的行画横线，所有打√号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合第四步：在没有被直线复盖的元素中找出最小元素，让打√号的列加上这个元素，打√号的行减去这个元素。转第一步96

例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人收费用1234123415182124192322182617161919212317最优方案：第一个人做第一件事；

第二个人做第四件事；第三个人做第三件事；第四个人做第二件事；总费用：7097√√√√√√√√984、一般的指派问题(1)求maxZ的指派问题(2)人数与工作数不等的指派问题(3)一个人可做几件事的指派问题(4)某事一定由（不能由）某人做的指派问题99收益12…j…n12…i…n指派问题模型：i=1,2,…,nj=1,2,…,n第i个人做第j人件事Z表示总收益i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的收益,求总收益最大的指派方案。(1)求maxZ的指派问题100工作人收益12…j…n12…i…n指派问题最大化的数学模型：i=1,2,…,nj=1,2,…,n指派问题最小化的数学模型：i=1,2,…,nj=1,2,…,n用匈牙利法101i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n102对maxZ的指派问题工作人收益12…j…n12…i…n用匈牙利法求C