1、7/28/2022第第4 4章章 整数规划整数规划1 CONTENTS目录7/28/20224.1 问题及其数学模型4.2 分支定界法4.3 割平面法4.4 整数规划4.5 指派问题4.6 整数规划案例24.1 问题及数学模型4.1.1 整数规划问题引例货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲19542乙273403托运限制1365（立方英尺）140（百千克）例例4.1 4.1 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如表4.1所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。表4.1 单位货物体积、重量及
2、利润7/28/20224121212112max2319527313654401404,0zxxxxxxs.t.xx x且均为整数4.1.1 整数规划问题引例7/28/20225纯整数规划：所有决策变量为非负整数；全整数规划：所有变量、系数和常数均为整数；混合整数规划：只有一部分决策变量为非负整数，其余变量可为非负实数；0-1整数规划：所有决策变量只能取0获1两个整数。11()1,2,.0,1,2,njjjnijjijjMax MinZc xa xbimstxjn且部分或全部为整数4.1.2 整数规划的数学模型7/28/20226例例4.24.2 设整数规划问题如下 12121212Maxz1
3、4951s.t.631,0 xxxxxxxx且为整数首先不考虑整数约束，得到线性规划问题（一般称为松弛问松弛问题题）。12121212Maxz14951s.t.631,0 xxxxxxxx4.1.3 整数规划与线性规划的关系7/28/20227用图解法求出最优解最优解x13/2,x2=10/3且有z=29/6现求整数解（最优解）：如用“舍舍入取整法入取整法”可得到4个点，即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集有限集，如图所示。因此，可将集合内的整数
4、点一一找出，其最大目标函数的值为最优解，此法为完全枚举完全枚举法法。4.1.3 整数规划与线性规划的关系7/28/202284.2 分枝定界法 基本思路 4.2 分支定界法11max().01,;1,njjjnijjijjzc xa xb IPstxim jn.且为整数,11max.01,1,njjjnijjijjzc xa xb LPstximjn7/28/2022101 1）先不考虑整数约束，解）先不考虑整数约束，解(IP IP)的松弛问题的松弛问题(LPLP)，可能得到以下情况，可能得到以下情况之一：之一：.若(LP)没有可行解，则(IP)也没有可行解，停止计算。.若(LP)有最优解，并
5、符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：不不全全为为整整数数其其中中目目标标函函数数最最优优值值为为)m,2,1i(b.z)0,0,b,b,b,b(xi(0)Tmr21)0(分支定界法的步骤如下：4.2 分支定界法7/28/2022112 2）定定界：界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为 Z(0)。再用观察法找的一个整数可行解 X，并以其相应的目标函数值 Z作为Z*的下界，记为Z Z，也可以令Z，则有：Z Z*ZZ3 3）分枝分枝：在
6、(LP)的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以 表示不超过 的最大整数。构造两个约束条件 xr 和 xr 1rbrbrb rb rb将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。4.2 分支定界法7/28/202212如此反复进行，直到得到如此反复进行，直到得到 Z Z Z Z*为止为止，即得最优解，即得最优解X X*。4 4）修改修改上、下界：按照以下两点规则进行。上、下界：按照以下两点规则进行。.在各分枝问题中，找出目标函数值最大者作为新的上界；.从已符合整数条件的分枝中，
7、找出目标函数值最大者作为新的下界。5 5）比较）比较与剪枝与剪枝 各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。Z4.2 分支定界法7/28/202213分支定界法是一种隐枚举方法隐枚举方法（implicit enumeration）或部分枚举方法部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。其关键是分支分支和定界定界。例例4.34.3 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1，X2 0 X1，X2 取整数s.t.4.2 分支定界法7/28/202214分支定界法图解分支定界法图解整数规划整数
8、规划例例4.34.3分支定界求解过程（一）分支定界求解过程（一）松弛问题 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1，X2 0该整数规划松弛问题的解为：（X1，X2）=（3/2，10/3）Z0=29/64.2 分支定界法7/28/202215松弛问题松弛问题 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1，X2 0（3/2，10/3）Z0=29/6LP1 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X1，X2 0LP2 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 1
9、X1，X2 0LP2：解：解（1，7/3）Z2=10/3LP1：解：解（2，23/9）Z1=41/9例例4.34.3分支定界求解过程（分支定界求解过程（二二）4.2 分支定界法7/28/202216（3/2，10/3）Z0=29/6LP1 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X1，X2 0LP2：解：解（1，7/3）Z2=10/3LP1：解：解（2，23/9）Z1=41/9LP11 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 3 X1，X2 0LP12 Max Z=X1+X2 14X1+9X2 51 -6X1
10、+3X2 1 X1 2 X2 2 X1，X2 0LP12：解：解（33/14，2）Z12=61/14例例4.34.3分支定界求解过程（三）分支定界求解过程（三）4.2 分支定界法7/28/202217（3/2，10/3）Z0=29/6LP2：解：解（1，7/3）Z2=10/3LP12 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1，X2 0LP12：解：解（33/14，2）Z12=61/14LP121 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 3 X2 2 X1，X2 0LP122 Max Z=X1+X2 14X
11、1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1，X2 0LP121：解：解（3，1）Z121=4LP122：解：解（2，2）Z122=4LP1：解：解（2，23/9）Z1=41/9例例4.34.3分支定界求解过程（四）分支定界求解过程（四）4.2 分支定界法7/28/202218LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11 无可无可行解行解LP122（2，2）Z122=4LP121（3，1）Z121=41x12x12x23x23x12x1#LP22（1，2）Z2
12、2=3LP21 无可无可行解行解2x23x2#例例4.34.3分支搜索法流程分支搜索法流程4.2 分支定界法7/28/202219LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11 无可无可行解行解LP122（2，2）Z122=4LP121（3，1）Z121=41x12x12x23x23x12x10ZZZ00Z941Z0Z1461Z4ZZ4Z2x2x3x1x2121或或最优解最优解#例例4.34.3分支定界法流程分支定界法流程4.2 分支定界法7/28/20222012121212Ma
13、x3229s.t.2314,0ZxxxxIPxxx x且为整数3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表初始表最终表最终表例例4.44.4 用分支定界法求解整数规划问题（单纯形法）4.2 分支定界法7/28/202221 x1=13/4 x2=5/2 Z(0)=59/414.75 选 x2 进行分枝，即增加两个约束，2 x2 3 有下
14、式：121212212M32292314(1)2,0ax ZxxxxxxIPxx x且为整数121212212M32292314(2)3,0ax ZxxxxxxIPxx x且为整数分别在(LP1)和(LP2)中引入松弛变量松弛变量x x5 5和x x6 6，将新加约束条件加入上表计算。即 x2+x5=2,x2+x6=3 得下表:4.2 分支定界法7/28/20222232000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/
15、200 x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2 Z(1)=14.5继续分枝，加入约束3 x1 4LP14.2 分支定界法7/28/20222332000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-
16、5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3 Z(2)=13.5 Z Z(2)(2)Z Z(1)(1)先不考虑分先不考虑分枝枝7/28/202224接接(LP1LP1)继续分枝，加入约束继续分枝，加入约束 4 4 x x1 1 3 3，有下式：，有下式：且为整数且为整数0 x,x3 x 2x 14x3x29x x2)3IP(x2x3ZaxM2112212121 且为整数且为整数0 x,x4 x 2x 14x3x29x x2)4IP(x2x3ZaxM2112212121分别引入松弛变量分
17、别引入松弛变量x x7 7 和和 x x8 8，然后进行计算。，然后进行计算。4.2 分支定界法7/28/202225CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3x1=3,x2=2 Z(3)
18、=13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP37/28/202226CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1x1=4x2=1 Z(4)=14找到整
19、数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP47/28/202227树形图如下：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)14x22x23x13x14#4.2 分支定界法7/28/2022284.3 割平面法min.()()0()()()()TjC XstAXbABXxBxxAAAGomory取整数解松弛问题，若解 不是整数解，增加一个约束使 不可行，但不丢失任何的可行解，得到新的
20、松弛问题。重复这个过程直到得到的整数解即的解。割平面法。4.3.1 基本思想7/28/2022301 1）用用单纯形法求解单纯形法求解(IP IP)对应的松弛问题对应的松弛问题(LPLP)：.若(LP)没有可行解，则(IP)也没有可行解，停止计算。.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。2 2）从从(LP)(LP)的最优解中，任选一个不为整数的分量的最优解中，任选一个不为整数的分量x xr r,将最优单纯形表中将最优单纯形表中该行的系数该行的系数 和和 分解为整数部分和小数部
21、分之和，并以该行为分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：源行，按下式作割平面方程：rjarb4.3.2 求解步骤7/28/202231r1mn1mjrjrjn1mjrjrjrrn1mjrjrjrrrn1mjrjrjrjrrn1mjrjrjrfxxf0 xffNxNxfNxfNxbxax3 3）将将所得的割平面方程作为一个新的约束条件置于最优单纯形表所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回返回1 1。4.3.2 求解步骤7/28/20
22、2232例例4.54.5 用割平面法求解整数规划问题且为整数且为整数0 x,x0 x2x36x2x3 xZaxM2121212解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/200-1/4-1/44.3.2 求解步骤7/28/202233此题的最优解为：X X (1,3/2(1,3/2)，Z Z=3/2=3/2 。以x2 为源行生成割平面，由于 1/4=0+1/4,3/2=1+1/2,
23、我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:21414143 xx也即：)x41x41(211x211x41x41x23x41x41x4324324324.3.2 求解步骤7/28/2022340)4141(21 43 xx将 x3=6-3x1-2x2,x4=3x1-2x2 ,代入 中，得到等价的割平面条件：x2 1 见下图。21414143 xxx1x233第一个割平面第一个割平面4.3.2 求解步骤7/28/202235Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200
24、-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：214141143 sxxCBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-17/28/202236此时，X1(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：32323214 sx用上表的约束解出x4 和s1，将它们带入上式得到等价的割平面条件：x1 x2，见图：x1x233第一个割平面第一个割平面第二个割平面第二个割平面4.3.2 求解步骤7/28/202237将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松
25、弛变量，然后加到表中：323232214 ssxCBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/27/28/202238CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最优表，其最优解为至此得到最优表，
26、其最优解为 X X=(1,1),Z=1=(1,1),Z=1,这也是原问题的最这也是原问题的最优解。优解。有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。性，因此，这个算法也称为分数对偶割平面算法。7/28/202239例例4.64.6 用割平面法求解数规划问题 且为整数且为整数0 x,x 20 x5x46xx2xxZaxM21212121Cj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/6
27、1/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表4.3.2 求解步骤7/28/202240在松弛问题最优解中，x1,x2 均为非整数解，由上表有：383132356165432431 xxxxxx将系数和常数都分解成整数和非负真分数之和 32231)311(321)651(65432431 xxxxxx4.3.2 求解步骤7/28/202241以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：)(313224332xxxx 32)(3143 xx引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。32313114
28、3 sxx4.3.2 求解步骤7/28/202242Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/601 x10100101x24010120 x3200113Z400001/2得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X X=(0,4),=(0,4),Z Z=4=4,或 X X=(2,2),=(2,2),Z Z=4=4。4.3.2 求解步骤7/28/202243()01Z.01jmm njjMaxZCXAXbAs.tx0 or 1 j1,2,nAbRBxC
29、XxAXb隐枚举法的基本思想：问题其中矩阵，松弛问题固定或，求利用分别固定或 进行分枝，根据目标函数值及约束来决定是否剪枝。4.4 0-1整数规划7/28/202244例例4.84.8 求解下列01 规划问题 10 x,x,x4 6xx4 3 3 x x2 4xx4x1 2xx2xx5x2x3ZaxM3213221321321321或或4.4.1 建模与求解思想7/28/202245解：解：对于01 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条
30、件，就能较快的求得最优解。x1.x2.x3约束条件约束条件满足条件满足条件Z 值值 (1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 00(0.0.1)1 1 0 15(0.1.0)2 4 1 42(1.0.0)1 1 1 03(0.1.1)1 5(1.0.1)0 2 1 18(1.1.0)3(1.1.1)2 64.4.1 建模与求解思想7/28/202246由上表可知，问题的最优解为 X*=(x1=1 x2=0 x3=1)由上表可知：x1=0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x12 x25 x3 5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，
31、如下表。x1.x2.x3约束条件约束条件满足条件满足条件Z 值值 (0)(1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 0 00(0.0.1)5 1 1 0 15(0.1.0)-2(0.1.1)3(1.0.0)3(1.0.1)8 0 2 1 18(1.1.0)1(1.1.1)44.4.1 建模与求解思想7/28/20224710 1Min().0,1,1,njjjjfc xPAxbstxjn用于隐枚举法的线性规划标准形式：以下讨论一般形式的01规划如何化为标准形式：111012kkknijjijnnijjiijjijjcyxa xba xbaxb 当某时，取代换即可。当某时，可产
32、生 个不等式和（）（）4.4.2 标准0-1整数规划的隐枚举法求解步骤7/28/202248例例4.94.9 求解下列01 规划问题123451234512345M105842324424501(1.2.3.4.5)jinZxxxxxxxxxxxxxxxxj 或解：解：令 y1=x5,y2=x4,y3=x2,y4=x3,y5=x1 得到下式 123451234512345M2458102434 1425 201(1.2.3.4.5)jinZyyyyyyyyyyyyyyyyj 或4.4.2 标准0-1整数规划的隐枚举法求解步骤7/28/202249y1.y2.y3.y4.y5约束条件满足条件Z
33、值(1)(2)是否(0.0.0.0.0)00(1.0.0.0.0)1-1(0.1.0.0.0)-11(0.0.1.0.0)-21(0.0.0.1.0)4-48(1.1.0.0.0)00(1.0.1.0.0)-10所以，Y*=（0.0.0.1.0），原问题的最优解为：X X*（0.0.1.0.00.0.1.0.0），），Z Z*=8=84.4.2 标准0-1整数规划的隐枚举法求解步骤7/28/202250,Assignmentproblemnnnnnn分配问题（指派问题）：项任务要分配给 个人（每人一项）去完成，各人对完成不同任务的效率不同，决定如何指派可使总效率最高。类似有：台机床加工 项任务
34、；条航线有 艘船去航行等。4.5 指派问题7/28/20225111110:10MZ1,1,().1,1,01ijijnnijijijnijinijjijcijijxinc xxjnPstxinx设第 个人完成第 项任务的效率 时间成本等第 个人完成第 项任务引入否则每项任务一人模型：每人一项任务或4.5.1 指派问题模型7/28/202252111212122212nnnnnnccccccCccc数据集中在下列系数矩阵 效益矩阵,ijm nPCaBbB关于问题的最优解的性质：若从矩阵 的一行（或一列）各元素中加上同一个实数 得到矩阵那么以 为系数矩阵的分派问题与原问题有相同的解。4.5.1
35、指派问题模型7/28/20225311111nnijijijnnnijijkjijji kfb xc xaxfa目标函数：目标函数的常数项不影响最优解。,ijijkjCkacikbcaik证：设从 的第 行各元素加上那么，4.5.1 指派问题模型7/28/202254 指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。第一步：变换指派问题的系数矩阵（第一步：变换指派问题的
36、系数矩阵（c cijij）为）为(b bijij)，使在，使在(b bijij)的各行的各行各列中都出现各列中都出现0 0元素，元素，即 (1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。4.5.2 匈牙利法7/28/202255第二第二步：进行试指派，以寻求最优解。步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作。然后划去 所在
37、列(行)的其它0元素，记作；这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给只有一个0元素的列(行)中的0元素加圈，记作；然后划去 所在行的0元素，记作 (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。4.5.2 匈牙利法7/28/202256 (4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若 元素的数目m 等于矩阵的
38、阶数n，那么这指派问题的最优解已得到。若m n,则转入下一步。第三步：作最少的直线覆盖所有0元素。(1)对没有的行打号；(2)对已打号的行中所有含元素的列打号；(3)再对打有号的列中含 元素的行打号；4.5.2 匈牙利法7/28/202257 (4)重复(2)，(3)直到得不出新的打号的行、列为止；(5)对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 lm n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元
39、素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。4.5.2 匈牙利法7/28/202258例例4.114.11 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁59824.5.2 匈牙利法7/28/202259第一第一步，变换系数矩阵：步，变换系数矩阵：2142 289541013895421176)c(ij0
40、67339024510095401733402401004545第二步，试指派：第二步，试指派：17334241454找到 3 个独立零元素 但 m=3 n=44.5.2 匈牙利法7/28/202260第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素：17334241454独立零元素的个数m等于最少直线数l，即lm=3n=4；第四步，变换矩阵第四步，变换矩阵(b bijij)以增加以增加0 0元素：没有被直线覆盖的所有元素元素：没有被直线覆盖的所有元素中的最小元素为中的最小元素为1 1，然后打，然后打各行都减去各行都减去1 1；打；打各列都加上各列都加上1 1，得如，得
41、如下矩阵，并转第二步进行试指派：下矩阵，并转第二步进行试指派：4.5.2 匈牙利法7/28/202261 6244251343000 0 00 0100001000011000得到4个独立零元素，所以最优解矩阵为：17334241454 06244251343 6244251343Z=154.5.2 匈牙利法7/28/202262在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。1.最大化指派问题设最大化指派问题系数矩阵 C=(cij)，其中最大元素为 m。令矩阵 B=(bij)=(m-cij)，则以 B 为系数矩阵的最小化指派问题和以
42、 C 为系数矩阵的最大化指派问题有相同最优解。2.人数和事数不等的指派问题若人少事多，则添加一些虚拟的“人”，其费用系数取 0，若人多事少，则添加一些虚拟的“事”，其费用系数取 0。3.一个人可做几件事的指派问题若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。4.某事一定不能由某人做的指派问题若某事一定不能由某人做，则可将相应的费用系数取为足够大的数 M。4.5.3 非标准形式的指派问题7/28/202263例例4.124.12 从甲、乙、丙、丁、戊五人中选四人去完成四项任务，每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原
43、因，甲必须被分配一项任务，丁不承担第4项任务，试确定总花费时间最少的分派方案。人任务甲乙丙丁戊11023159251015243155147154201513684.5.3 非标准形式的指派问题7/28/202264解：解：增加虚设任务5，各人该项任务时间为0，某人不完成某任务时，取时间M（充分大的时间）：人任务甲乙丙丁戊11023159251015243155147154201513685M00004.5.3 非标准形式的指派问题7/28/2022654.6 整数规划案例4.6 整数规划案例4.6.1 4.6.1 配送配送系统设计系统设计配送系统是物流系统的重要组成部分，该系统将生产厂的产品
44、运送至分配中心，然后由这些分配中心将产品运至用户。其中，合理地选择生产厂与分配中心对降低物流成本至关重要。配送系统设计就是要综合考虑生产厂和分配中心的固定成本、生产厂至分配中心的运费、分配中心至用户的运费、生产厂的生产能力、满足需求等因素的基础上，对系统进行优化，以使得总成本最小。7/28/2022674.6.2 案例简介某时尚女装品牌考虑生产一种女装系列。女装产品将先运至分配中心，再由分配中心将产品运送至分销店。该品牌有五家工厂均可生产这类女装，有三家分配中心可以分配女装产品，有四家分销店可以经营女装产品。这些工厂和分配中心的年固定成本如表4.16所示。从各工厂至分配中心的运费与各工厂的生产
45、能力如表4.17所示。从各分配中心至分销店的的运费与各分销店对女装的需求量如表4.18所示。假定各分配中心的库存政策为“零库存”，即分配中心将从工厂得到产品均分配给分销店，不留作库存。品牌商要设计一种女装分配系统，在满足需求的前提下，确定使用哪些工厂与分配中心进行女装的生产与分配，以使得总成本最小。7/28/202268单位工厂1工厂2工厂3工厂4工厂5分配中心1分配中心2分配中心3年固定成本（元）3500045000400004200040000400002000060000表4.16 工厂与分配中心的固定成本终点起点运输成本（元/箱）生产能力（箱）分配中心1分配中心2分配中心3工厂1800
46、10001200300工厂2700500700200工厂3800600500300工厂4500600700200工厂5700600500400表4.17 各工厂运至分配中心的运输成本与生产能力4.6.2 案例简介7/28/202269终点起点运输成本（元/箱）分销店1分销店2分销店3分销店4分销中心140809050分销中心270406080分销中心380305060需求量（箱）200300150250表4.18 从分配中心运至分销店的运输成本和各分销店需求量4.6.2 案例简介7/28/2022704.6.3 整数规划建模1 1）建模思路）建模思路 4.6.2节中的案例可以用网络图来描述如下
47、：60503080804060705080904050060070070060050050060080070050070012001000800工厂1工厂2工厂3工厂4工厂5中心1中心2中心3分店1分店2分店3分店4生产能力需求量3002003002004002003001502507/28/2022712）最终模型）最终模型1112132122233132334142435152531112131421222324min8001000120070050070080060050050060070070060050040809050704060808zxxxxxxxxxxxxxxxyyyyyyy
48、y313233341234512311121312122232313233303050603500045000400004200040000400002000060000300200.300yyyyfffffdddxxxf (xxxf (stxxxf (工厂1生产能力约束）工厂2生产能力约束）41424345152535200400 xxxf (xxxf (5工厂3生产能力约束）工厂4生产能力约束）工厂 生产能力约束）4.6.3 整数规划建模7/28/202272112131415111121314122232425221222324132333435331323334111213141900
49、 xxxxx=yyyy 1xxxxx=yyyy xxxxx=yyy+y yyyyd (1（分配中心 接收量与运出量均衡约束）（分配中心2接收量与运出量均衡约束）（分配中心3接收量与运出量均衡约束）分配中心212223242313233343112131122232132333142434900900200300150250)yyyyd ()yyy+yd ()yyy y+yy y+yy yy+y 最大运出量约束分配中心2最大运出量约束分配中心3最大运出量约束（满足分销店1需求约束）（满足分销店2需求约束）（满足分销店3需求约束）（满01012 3iiijijf xj=yj=足分销店4需求约束）或
50、（i=1,5）,d或（i=1,2,3）(0-1整数变量约束)（i=1,5；1，2，3），（i=1,，；1，2，3，4）（非负约束）4.6.3 整数规划建模7/28/2022734.6.4 模型求解结果分析通过使用Excel等求解工具求解，可得到本问题的最优解如表4.19和表4.20所示工厂分配中心1分配中心2分配中心3工厂130000工厂2000工厂300300工厂4000工厂500300表4.19 从各工厂运至各分配中心的产品产量（箱）分配中心分销店1分销店2分销店3分销店4分配中心120000100分配中心20000分配中心30300150150表4.20 从各分配中心运至各分销店的产品产
