运筹学第五章

1、1第五章第五章 整数规划整数规划第第五五章章 整数规划整数规划学时安排：学时安排：8学时教学目的：教学目的：掌握若干特殊整数规划的解法教学内容：教学内容：1.整数规划问题及特点2.分枝定界法与割平面法3.0-1规划4.指派问题 教学重点：教学重点：割平面法与指派问题 教学难点：教学难点：分枝定界法与割平面法2第第五五章章 整数规划整数规划教学内容第一节整数规划问题的提出第二节解纯整数规划的割平面法 第三节分支定界法 第四节 -整数规划 第五节指派问题3第一节 整数规划问题的提出1. 整数规划问题基本概念2. 整数规划问题的数学模型3. 整数规划解的特点第第五五章章 整数规划整数规划41. 基本

2、概念 整数规划：要求部分或全部决策变量取整数值的规划问题。 整数规划问题的松弛问题：不考虑整数条件的规划问题。 整数线性规划：整数规划为线性规划 纯整数线性规划（pure integer linear programming) 混合整数线性规划（mixed integer linear programming） 0-1整数线性规划(zero-one integer linear programming）注意：注意：后面提到的整数规划，一般指的都是整数线性规划。第第五五章章 整数规划整数规划52. 整数规划数学模型的一般形式部分或全部取整数值),2, 1(),2, 1(0),2, 1(),( .

3、max(min) 11njxnjxmibxatsxczjjnjijijnjjj第第五五章章 整数规划整数规划63. 整数规划解的特点问题：能否将松弛问题最优解的近似值（取整、四舍五入）作为整数规划问题的最优解？例1：求下述整数规划的最优解。且取整数0,5 .45 .0143223max21212121xxxxxxxxZ第第五五章章 整数规划整数规划7第第五五章章 整数规划整数规划 1 2 3 4 5 6 7x115234x2A (3.25,2.5)2x1+3x2=14X1+0.5x2 =4.5Z=3x1+2x2最优解为最优解为(4,1)且取整数0,5 .45 .0143223max212121

4、21xxxxxxxxZ8第第五五章章 整数规划整数规划结论：结论：不能把松弛问题的最优解通过不能把松弛问题的最优解通过“四舍五入四舍五入”或或“截尾截尾”（即凑整）处理后作为整数规划的（即凑整）处理后作为整数规划的最优解。不过，在变量取值很大时，用上述方最优解。不过，在变量取值很大时，用上述方法得到的解与最优解差别不大。法得到的解与最优解差别不大。点点(4,1)不是可行域的顶点，所以直接用图解不是可行域的顶点，所以直接用图解法或单纯形法无法求出整数规划问题的最优解法或单纯形法无法求出整数规划问题的最优解9第第五五章章 整数规划整数规划 整数线性规划的解与松弛问题的解既有联系，整数线性规划的解与

5、松弛问题的解既有联系，又有本质的区别。设又有本质的区别。设 IP的松弛问题的可行域为的松弛问题的可行域为C，IP的可行域为的可行域为C，则有，则有 CC 整数规划的可行解是松弛问题可行解集合的一整数规划的可行解是松弛问题可行解集合的一个子集。所以个子集。所以：IP的可行解一定是它的松弛问题的可行解。的可行解一定是它的松弛问题的可行解。 IP的最优值不会优于其松弛问题的最优值。的最优值不会优于其松弛问题的最优值。10第二节 割平面法1. 割平面方法的基本思想和步骤2. 构造割平面约束的方法3. 示例第五章第五章 整数规划整数规划21maxxxZ为整数2,12121210,431xxxxxxxx1

6、x2x112-x1+x2 =13x1+x2 =4maxZAA(3/4,7/4)C(1,1)1. 割平面方法的基本思想和步骤基本思想基本思想：在IP问题的松弛问题中依次引进线性约束（称Gomory约束或割平面），使问题的可行域逐步缩小，所割去的区域仅包含问题的部分非整数解；当规划问题的最优解恰好位于缩小的可行域的一个顶点时，算法结束。第第五五章章 整数规划整数规划求解步骤：求解步骤：第第五五章章 整数规划整数规划 求出松弛问题最优解，若为整数，则停止，否则转 构造割平面方程。构造的割平面约束应当具备两个性质：a) 已获得的非整数最优解不满足该线性约束，从而保证在以后的解中不可能再出现。b) 所有

7、的整数解皆满足该线性约束，从而保证整数最优解始终都保留在以后每次所形成的新的线性规划的可行域中。14第第五五章章 整数规划整数规划3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7jcjjzc X4=31/7不是整数，该行对应的方程是：不是整数，该行对应的方程是：731722)73(534xxxCBXBbx1x2x3x4x5x1x2x4第第五五章章 整数规划整数规划X4 - 3/7 x3 + 22/7 x5 = 31/7基变量（整数）基变量（整数） 非基变量（整数）非基变量（整数） -3/7 = -1+4/7 22/7=

8、 3 + 1/7 31/7= 4 + 3/7 在上述式子中，除第一部分在上述式子中，除第一部分X4 （即整数部（即整数部分）外，我们将后面变量的系数与常数项皆分）外，我们将后面变量的系数与常数项皆化为两部分：不超过该数的最大整数与非负化为两部分：不超过该数的最大整数与非负分数，即分数，即16第第五五章章 整数规划整数规划734)713 ()741(534xxx 将整数部分放在等式的左边将整数部分放在等式的左边,其余部分放在右边其余部分放在右边,得：得：5353471747343xxxxx731722)73(534xxx17第第五五章章 整数规划整数规划上式的左边是一个整数，右边是一个小于上式的

9、左边是一个整数，右边是一个小于的数，因此，右边是一个小于或等于的数，因此，右边是一个小于或等于的整数，即的整数，即071747353xx73717453xx通过分析，可以得出上式具有如下两个性质：通过分析，可以得出上式具有如下两个性质：松弛问题的非整数最优解不满足该式松弛问题的非整数最优解不满足该式IP的所有整数可行解都满足此式的所有整数可行解都满足此式18第第五五章章 整数规划整数规划构造割平面约束的一般方法如下：构造割平面约束的一般方法如下： 1、在松弛问题的最优表中，设、在松弛问题的最优表中，设b列的第列的第k个分量个分量bk为非整为非整数，可将它分解为整数和非整数部分之和，即数，可将它

10、分解为整数和非整数部分之和，即bk =Nk + fk ， Nk bk 且为整数，且为整数，0 fk 1。 2、然后，第、然后，第k行中的每一个非基变量行中的每一个非基变量 xj的系数的系数 akj也分解也分解为整数与非负数之和的形式，即为整数与非负数之和的形式，即 akj= Nkj + fkj ;Nkj akj ; 0 fk 1,则割平面方程为：则割平面方程为：kjkjfxfxj为非基变量为非基变量通常，从最优单纯形表中，选择具有通常，从最优单纯形表中，选择具有最大分数部分的非整最大分数部分的非整分量分量所在行构造割平面约束，可以提高切割效果，减少切所在行构造割平面约束，可以提高切割效果，减少

11、切割次数。割次数。19第第五五章章 整数规划整数规划例例：用用割平面法求解纯整数规划。割平面法求解纯整数规划。213maxxxZ为整数。2,1212121210,521045323xxxxxxxxxx解解: 1、用单纯形法求得松弛问题的最优表如下。、用单纯形法求得松弛问题的最优表如下。20第第五五章章 整数规划整数规划3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/776727153xx 松弛问题的最优解为非整数松弛问题的最优解为非整数,而在而在13/7=1+6/7 ，9/7=1+2/7 ， 31/7=4+3/7的非负分

12、数中的非负分数中,6/7最大。最大。所以，将所以，将13/7所在的行中非基变量所对应的系数进行所在的行中非基变量所对应的系数进行分解分解: 1/7=0+1/7 2/7=0+2/7。割平面方程为：。割平面方程为：jcjjzc CBXBbx1x2x3x4x5x1x2x421第第五五章章 整数规划整数规划3-100003-10013/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70jcjjzc 将割平面约束变为等式约束后，并入松弛问题的将割平面约束变为等式约束后，并入松弛问题的最优表中，见下表。最优表中，见下表

13、。CBXBbx1x2x3x4x5x1x2x4x6x622第第五五章章 整数规划整数规划3-100003-10015/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4利用对偶单纯形法求出最优解，见下表。利用对偶单纯形法求出最优解，见下表。CBXBbx1x2x3x4x5x1x2x3x5x6jcjjzc 23第第五五章章 整数规划整数规划由上表第四行产生的割平面约束为：由上表第四行产生的割平面约束为：43414164xx3-10000 03-100015/45/27/41000001000001000-1/4-1/21/4-

14、1/4000101 0-5/4 0-11/2 0-3/4 0-1/4 1000-1/40-17/4 0jcjjzc x1x2x4x6CBXBbx1x2x3x4x5x6x7-3/4x724第第五五章章 整数规划整数规划3-10000 03-1000124110000010000010000001000101 0-1 -1-5 -2-1 11 -400000-4 -1jcjjzc x1x2x4x6CBXBbx1x2x3x4x5x6x4 3x71max, 2, 121zxx25第第五五章章 整数规划整数规划3x1-2x2=35x1+4x2=102x1+x2=5ABCDmax1x2x 1 2 3152

15、34-1/7x3-2/7x5 -6/7x11-1/4x4-1/4x6 -3/4x1 +x2 3x11x1 +x2 3EF3x1-2x2 35x1+4x2 102x1+x2 5maxZ=3x1-x23x1-2x2 + x3= 35x1+4x2 x4 =102x1+x2 + x5 = 5maxZ=3x1-x2F26第第五五章章 整数规划整数规划案例案例32x1+x2 64x1+5x2 20 x1,x2 0且为整数且为整数maxZ=x1+x21、求出松弛问题的最优解、求出松弛问题的最优解2x1+x2 +x3 = 64x1+5x2 +x4 = 20 x1,x2 , x3,x4 0且为整数且为整数max

16、Z=x1+x227第第五五章章 整数规划整数规划110015/3105/6-1/618/301-2/31/300-1/6-1/6x1x2CBXBbx1x2x3x4jcjjzc 32656543xx2、构造割平面、构造割平面326565543xxx第第五五章章 整数规划整数规划1100 0 15/3105/6-1/6 018/301-2/31/3 0 0-2/300-5/6-5/6 100-1/6-1/6 0 x1x2CBXBbx1x2x3x4jcjjzc 326565543xxxx5x5第第五五章章 整数规划整数规划1100 0 11100-1 1116/50101 -4/5 04/50011

17、 -6/50000 -1/5x1x2CBXBbx1x2x3x4jcjjzc x3x554545x3、构造割平面、构造割平面545465xx第第五五章章 整数规划整数规划1100 0 0 11100-1 1 0116/50101 -4/5 0 04/50011 -6/5 0 0-4/50000 -4/5 10000 -1/5 0 x1x2CBXBbx1x2x3x4jcjjzc x3x5545465xxx6x6第第五五章章 整数规划整数规划1100 0 0 10100-1 0 5/41 40101 0 -1 0 20011 0 -3/2 010000 1 -5/40000 0 -1/4x1x2CB

18、XBbx1x2x3x4jcjjzc x3x5x5x6第第五五章章 整数规划整数规划2x1+x2 64x1+5x2 20 x1,x2 0且为整数且为整数maxZ=x1+x21x2x 1 2 3 4 51523462x1+x2 = 64x1+5x2 = 20maxZA(5/3,8/3)32656543xx52121xxB(1,16/5)C(9/5,12/9)54545x421xxD(0,4)E(2,2)F(1,3)第三节 分支定界法一、分支定界法步骤二、示例第第五五章章 整数规划整数规划第第五五章章 整数规划整数规划21maxxxz145114921xx31221xx且为整数0,21xxx x1

19、1x x2 25 54 43 32 21 1x x1 1+9/14x+9/14x2 2=51/14=51/14-2x-2x1 1 +x+x2 2=1/3=1/3maxmaxA(3/2,10/3)A(3/2,10/3)x1=1x1=1x1=2x1=2B BC C第第五五章章 整数规划整数规划LP2(CGE):LP2(CGE):C(2,23/9);Z=41/9C(2,23/9);Z=41/9LP1(BFD):LP1(BFD):B(1,7/3);Z=10/3B(1,7/3);Z=10/3不不可可能能区区域域x1x2maxABCx1=1x1=2EDFGMHLP21(HMEG):LP21(HMEG):M

20、(33/14,2);Z=61/14M(33/14,2);Z=61/14x1=3NLLP212(NEL):LP212(NEL):N(3,1);Z=4N(3,1);Z=4LP211(HG):LP211(HG):H(2,2);Z=4H(2,2);Z=436一、分支定界法步骤一、分支定界法步骤第第五五章章 整数规划整数规划1分支分支 假设松弛问题的最优解不是整数解，则选择一假设松弛问题的最优解不是整数解，则选择一个非整数分量构造两个约束条件：个非整数分量构造两个约束条件：iibx 1iibx分别加入松弛问题中，得到两个子问题分别加入松弛问题中，得到两个子问题LP1与与LP2, 即后继问题，并求解之。即

21、后继问题，并求解之。x1+9/14x2 51/14-2x1+x2 1/3x1 1x1,x2 0,且为整数且为整数maxZ=x1+x2LP1LP1x1+9/14x2 51/14-2x1+x2 1/3x1 2x1,x2 0,且为整数且为整数maxZ=x1+x2LP2LP237一、分支定界法步骤一、分支定界法步骤第第五五章章 整数规划整数规划2定界（以求极大值为例）定界（以求极大值为例） 以最优目标函数值中最大者（针对没有分支的以最优目标函数值中最大者（针对没有分支的线性规划问题而言）为上界，以符合整数条件线性规划问题而言）为上界，以符合整数条件的各子问题中目标函数值最大者作为下界。若的各子问题中目

22、标函数值最大者作为下界。若无整数解，在无整数解，在Z0的情况下，令的情况下，令Z=03比较与剪枝比较与剪枝若上界等于下界，则停止；否则，剪去小于若上界等于下界，则停止；否则，剪去小于下界的分支。对于大于下界的分支，继续重复下界的分支。对于大于下界的分支，继续重复（函数值较大的分支优先）。（函数值较大的分支优先）。38第第五五章章 整数规划整数规划X11X120 0z z6 62 29 9z z0 0z z9 94 41 1z zX22X230 0z z1 14 46 61 1z zX12X134 4z z4 4z zLP0S: X1=3/2；X2=10/3；Z0=29/6S2X1=1,X2=7

23、/3,Z =10/3LP1S1X1=2,X2=23/9,Z=41/9LP2S11X1=33/14,X2=2,Z =61/14LP21无可行解无可行解LP22S111X1=3,X2=1,Z =4LP211S112X1=2,X2=2,Z =4LP21239第第五五章章 整数规划整数规划使用范围使用范围:纯整数、混合整数规划纯整数、混合整数规划 9x1+7x2 567x1+20 x2 70 x1,x2 0,且为整数且为整数maxZ=40 x1+90 x2LPLP例例2:40第第五五章章 整数规划整数规划9x1+7x2 = 561 2 3 4 5 6 7 8 9x1x2123456787x1+20 x

24、2 =70maxZx1=4x1=5B(4,2.1);Z=349x2=2x2=3E(4,2);Z=340D(1.42,3);Z=327C(5,1.57);Z=341x2=1LP2(OGBH):BLP2(OGBH):BLP1(MKC):CLP1(MKC):CHMA(4.81,1.82)GOKF(5.44,1);Z=30841第第五五章章 整数规划整数规划X14X150 0z z3 3z z 560 0z z3 3z z 49X22X2340413 3z z3 3z zX21X2240403 3z z3 3z zLP0S: X1=4.81；X2=1.82；Z0=356S1X1=5,X2=1.57,Z

25、 =341LP1:CS2X1=4,X2=2.1,Z=349LP2 :BX1=4,X2=2,Z =340S21LP21 :EX1=1.42,X2=3,Z =327LP22 :DS11X1=5.44,X2=1,Z =308LP11 :FLP12无可行解无可行解第四节 0-1 整数规划一、0-1变量及其应用二、0-1规划的隐枚举法第五章第五章 整数规划整数规划43注：决策时，如果要考虑某个特定方案是否被选取（即多个方案不一定全用），可以使用0-1变量。【例1】某公司欲在东、西、南三区建立门市部，共有7个门市部可供选择。规定；在东区，由A1、A2、A3三个点中至多选两个；在西区，由A4、A5两点中至少

26、选一个；在南区，由A6、A7两点中至少选一个。选用Ai点，投资为bi元，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润最大？一、0-1变量及应用第五章第五章 整数规划整数规划44iiixcz71maxBxbiii712321xxx154xx176xx10或ix解：设10ixAi被选用Ai不被选用则问题变为第五章第五章 整数规划整数规划45【例2】含有相互排斥的约束条件问题120150100250工时限额（h/周）400.40.50.10.7A2250.20.30.20.3A1利润（元件）B3方式1 方式2B2B1工时/件 工序产品第五章第五章 整数规划整数规划46 要求

27、B3 3只能从加工方式与中选择一种，那么工厂应如何安排生产，才能使总利润最大？设生产两种产品分别为x1与x2件101y当工序B3选用加工方式，即满足1505 . 03 . 021xx当工序B3不选用加工方式102y当工序B3 3选用加工方式，即满足1204 . 02 . 021xx当工序B3 3不选用加工方式第五章第五章 整数规划整数规划4710,11204 . 02 . 01505 . 03 . 02121221121或yyyyMyxxMyxx101y1505 . 03 . 021xx当工序B3选用加工方式，即满足当工序B3不选用加工方式102y1204 . 02 . 021xx当工序B3选

28、用加工方式，即满足当工序B3不选用加工方式方式与中选择一种等价于第五章第五章 整数规划整数规划4810,11204 . 02 . 01505 . 03 . 01001 . 02 . 02507 . 03 . 04025max2121221121212121或取yyyyMyxxMyxxxxxxxxz则数学模型为：第五章第五章 整数规划整数规划49该问题也可以令：10y当工序B3采用加工方式当工序B3采用加工方式则从两种加工方式中选择一种等价于：MyxxMyxx)1(1204.02.01505.03.02121第五章第五章 整数规划整数规划50一般情形下，如果有 P个约束条件，q个起作用njjij

29、pibxai1),2, 1(可以令：10iy当第i个起作用当第i个不起作用则问题转化为：10111或者yqpyMybxapiinjijiji第五章第五章 整数规划整数规划51【例3】试利用0-1变量将下列各约束条件表示成一般的线性约束条件。221 xx83221xx或解： 设10y选第一个约束 选第二个约束则原命题等价于MyxxMyxx)1 (83222121第五章第五章 整数规划整数规划52x3只能取r1, r2, , rk中的一个。若x24,则x50；否则， x53设01iyx3取ri否则则1012122113或ikkkyyyyyryryrx设10y当x24；当x2 4 第五章第五章 整数

30、规划整数规划53则1 ,0)1(3)1(445522yMyxMyxMyxMyx（4）当变量可以取多个整数值时，可以用多个 0-1变量来表示， 例如， x9可以表示为 x=20y0+ 21y1 + 22y2 + 23y3 9 其中，y0, y1 , y2 ,y3是0-1变量。第五章第五章 整数规划整数规划54二、0-1规划的隐枚举法 枚举法是解0-1规划的一种算法。具体方法就是检查每个变量等于0或1的所有组合。满足所有约束条件，且使目标函数值达到最优的组合就是0-1规划的最优解。 由于当0-1 变量有n个时，须检查2n个变量组合，而当 n15时，这几乎是不可能的。所以有人提出隐枚举法。第五章第五

31、章 整数规划整数规划55 寻找一种方法，使问题在达到最优解之前，仅须依次检查所有可能变量组合的很少一部分。下面介绍两种这样的方法。求解步骤：【例4】求解321523maxxxxz)3 ,2, 1(1 ,064344223221321321ixxxxxxxxxxxi1 .隐枚举方法的求解思路和方法第五章第五章 整数规划整数规划56、先找一个可行解,如（0,0,0)，并将其目标函数值z=0 作为下界；、由上步得出过滤条件 3x1- 2x2+ 5x30、对某种变量的组合，检验其是否满足上述过滤条件，若满足且又是可行解，则修改过滤条件。重复步骤3。第五章第五章 整数规划整数规划57第五章第五章 整数规

32、划整数规划0z5z8z321523maxxxxz(x2,x1,x3)Z值值约束条件约束条件过滤条件过滤条件(0,0,0)0(0,0,1)5(0,1,1)8(1,1,1)64,3,2,11 ,064344223221321321ixxxxxxxxxxxi58第第五五章章 整数规划整数规划注意注意: :上述计算步骤还可以进一步得到改善，即对极上述计算步骤还可以进一步得到改善，即对极大化问题，若将目标函数中大化问题，若将目标函数中x xj j的价值系数按递增（不的价值系数按递增（不减）的次序排列（求极小，价值系数按照递减的次减）的次序排列（求极小，价值系数按照递减的次序排列）。即序排列）。即则可知则

33、可知(0,0,1)(0,0,1)的目标值一定不小于的目标值一定不小于(0,1,0)(0,1,0)及及(1,0,0)(1,0,0)的目标值。同样的目标值。同样(0,1,1)(0,1,1)的目标值一定不小的目标值一定不小于于(1,1,0)(1,1,0)与与(1,0,1)(1,0,1)的目标值。故若的目标值。故若(0,0,0)(0,0,0)、(0,0,1)(0,0,1)、(0,1,1)(0,1,1)、(1,1,1)(1,1,1)都为可行解，则其他变都为可行解，则其他变量的组合可不必考虑。量的组合可不必考虑。312532maxxxxz第五章第五章 整数规划整数规划59第五节指派问题一、指问题的标准形式

34、及数学模型一、指问题的标准形式及数学模型二、匈牙利方法二、匈牙利方法三、非标准形式的指派问题三、非标准形式的指派问题601、指派问题（、指派问题（assignment problem)假定假定n个人去做个人去做n件事，并指定每人完成其中一项，每项件事，并指定每人完成其中一项，每项交给其中一个人去完成（即人与事一一对应交给其中一个人去完成（即人与事一一对应)，问应如何分，问应如何分配才能使完成这件事的总费用最少。配才能使完成这件事的总费用最少。2、标准形式的数学模型、标准形式的数学模型指派问题的系数矩阵指派问题的系数矩阵设第设第i人完成第人完成第j件事的费用为件事的费用为cij ，则称，则称一、

35、指派问题的标准形式及数学模型一、指派问题的标准形式及数学模型nnijcC)(第第五五章章 整数规划整数规划61为指派问题的系数矩阵（为指派问题的系数矩阵（coefficient matrix)或效率矩阵。或效率矩阵。令令01ijx指派第指派第i人做第人做第j件事件事不指派第不指派第i人做第人做第j件事件事则数学模型则数学模型为：为：ninjijijxcz11minniijnjx1),2, 1(1njij,n),(ix1211), 2, 1,(1 , 0njixij第第五五章章 整数规划整数规划62 可以可以看出：看出： 标准标准形式的指派问题是特殊的运输问题形式的指派问题是特殊的运输问题。也。

36、也是特殊是特殊的的0-1整数规划问题。整数规划问题。每一个可行解可用一个解矩阵表示每一个可行解可用一个解矩阵表示nnnnnnnnijxxxxxxxxxxX212222111211)(X中每行及每列都有且仅有一个，所以共有中每行及每列都有且仅有一个，所以共有! npnn个可行解。个可行解。第第五五章章 整数规划整数规划63第第五五章章 整数规划整数规划 1、思想依据、思想依据如果系数矩阵的所有元素如果系数矩阵的所有元素cij0 ，而其中存在，而其中存在n个位于不同个位于不同行不同列的零元素，则对应的指派方案总费用为零，从而行不同列的零元素，则对应的指派方案总费用为零，从而也一定是最优的。也一定是

37、最优的。如如0141208302323020939140C令令144322311xxxx二二、匈牙利方法、匈牙利方法64问题：如何产生或者寻找n个位于不同行不同列的零元素定理1、如果从分配问题的系数矩阵nnijcC)(的每行（或每列）各元素分别减去(或加上)一个常数，得到一个新的矩阵nnijcC)(则以C和C为系数矩阵的两个指派问题有相同的最优解（见下页）。2、理论基础（康尼格定理）第第五五章章 整数规划整数规划65第第五五章章 整数规划整数规划minZ= c11 x11+ c12 x12+ cnn xnnx11+ x12+ x1n =1.xn1+ xn2+ xnn =1x11+ x21+ x

38、n1 =1x1n+ x2n+ xnn =1xij =0或或1minZ(1)= (c11 k)x11+ (c12 k) x12+ (c1n k)x1n + c21 x21+ cnn xnnminZ(1) = c11 x11+ c12 x12+ cnn xnn -k(x11 + x12+ + x1n ) = c11 x11+ c12 x12+ cnn xnn -k66第第五五章章 整数规划整数规划651141143452115281417023090032217067第第五五章章 整数规划整数规划若矩阵若矩阵C的元素可分成的元素可分成“”与非与非“”两两部分，则覆盖部分，则覆盖“”元素的最少直线数

39、目，等元素的最少直线数目，等于位于不同行不同列于位于不同行不同列独立零元素独立零元素的最大个数。的最大个数。417023090032217068第第五五章章 整数规划整数规划1、变换系数矩阵、变换系数矩阵对各行元素分别减去该行中的最小元素，再对各列元素分别减对各行元素分别减去该行中的最小元素，再对各列元素分别减去该列中的最小元素。直到每行每列都有去该列中的最小元素。直到每行每列都有0元素为止。元素为止。61012961061476781296101417971215784C04630408101263037102081134004320405001232037710811030三、匈牙利方法步

40、骤三、匈牙利方法步骤69第第五五章章 整数规划整数规划在零元素最少的行（或列）开始，选择一个在零元素最少的行（或列）开始，选择一个0元素，并元素，并加上标记：加上标记：独立零元素的含义是：它所在行的人，已经不能再安排独立零元素的含义是：它所在行的人，已经不能再安排其他的事情做；它所在列的事（工作），已经有人去做。其他的事情做；它所在列的事（工作），已经有人去做。 如此反复，直到所有的零元素都被划去为止。在此过程如此反复，直到所有的零元素都被划去为止。在此过程中，若存在零元素的闭回路，可任选其中一个零元素加标记，中，若存在零元素的闭回路，可任选其中一个零元素加标记，同时划去同行和同列中的其他零元素。同时划去同行和同列中的其他零元素。2、在变换后的矩阵中确定独立零元素、在变换后的矩阵中确定独立零元素 同时，划去此零元素所在行及其列的其他零元素。获同时，划去此零元素所在行及其列的其他零元素。获标记的零元素称为标记的零元素称为独立零元素独立零元素。70第第五五章章 整数规划整数规划0432040500123203771081103071第第五五章章 整数规划整数规划3、覆、覆 盖盖(1)对没有独立零元素的行打对没有独立零元素的行打 。(2)在已打在已打 的行中的行中,对对 元素所在的列打