大学精品课件：第六章 整数规划（5节）.ppt

1、第第1页页指派问题的标准形式：指派问题的标准形式：有有 n 个人和个人和 n 件事情，已知第件事情，已知第 i 人做第人做第 j 件事情的件事情的费用为费用为 cij（i,j=1,2,n），要求确定人和事之间的），要求确定人和事之间的 第第2页页一一对应的指派方案，使完成这一一对应的指派方案，使完成这 n 件事情的总费用件事情的总费用最少。最少。这类问题称为指派问题或分派问题（这类问题称为指派问题或分派问题（assignment problem）。）。第第3页页引入引入 n 2 个个 0 1 变量：变量：）（事事人人做做第第，不不指指派派第第事事人人做做第第指指派派第第njijijixij,.

2、,2,1,0 ,1 cij 第表示第第表示第 i 人做第人做第 j 件事情的费用；件事情的费用；第第4页页建立问题的数学模型：建立问题的数学模型：）（，或或）（，）（，3 ,.,2,1,102 ,.,2,111 ,.,2,11min1111njixnixnjxxczijnjijniijninjijij约束（约束（1）：每件事情必须有且只能有一个人去做；）：每件事情必须有且只能有一个人去做；约束（约束（2）：每个人必须且只能去做一件事情。）：每个人必须且只能去做一件事情。第第5页页1.系数矩阵系数矩阵 一般称矩阵一般称矩阵 nnnnnnnnccccccccccC.)(212222111211为指

3、派问题的系数矩阵（为指派问题的系数矩阵（coefficient matrix）。）。第第6页页第第 i 行中各元素表示第行中各元素表示第 i 人做各事的费用；人做各事的费用；第第 j 列各元素表示第列各元素表示第 j 事由各人做的费用。事由各人做的费用。2.解矩阵解矩阵 对于问题的每一个可行解，可用解矩阵的形式表示：对于问题的每一个可行解，可用解矩阵的形式表示：nnnnnnnnxxxxxxxxxxX.)(212222111211第第7页页解矩阵的特点：解矩阵的特点：每行各元素都有且只有一个每行各元素都有且只有一个1；每列各元素都有且只有一个每列各元素都有且只有一个1。指派问题共有（指派问题共有

4、（n!）个可行解。）个可行解。第第8页页标准指派问题是一类标准指派问题是一类整数规划问题整数规划问题，又是一个特殊，又是一个特殊的的 0 1 规划问题规划问题，同时又是一个特殊的，同时又是一个特殊的运输问题运输问题。可用整数规划的分支定界法、割平面法；可用整数规划的分支定界法、割平面法；0-1规划的规划的隐枚举法；运输问题解法来求解，但效率低下，没隐枚举法；运输问题解法来求解，但效率低下，没有充分利用指派问题自身的特点。有充分利用指派问题自身的特点。第第9页页1955年，库恩（年，库恩（W.W.Kuhn）引用了匈牙利数学家）引用了匈牙利数学家康尼格（康尼格（D.Knig）的关于矩阵中）的关于矩

5、阵中 0 元素的定理元素的定理（定理：系数矩阵中独立（定理：系数矩阵中独立 0 元素的最多个数等于能元素的最多个数等于能覆盖所有覆盖所有 0 元素的最少直线数），提出了指派问题元素的最少直线数），提出了指派问题的一种算法，习惯上称之为匈牙利法。的一种算法，习惯上称之为匈牙利法。第第10页页1.指派问题最优解的特性指派问题最优解的特性 指派问题最优解的特性：从指派问题的系数矩阵指派问题最优解的特性：从指派问题的系数矩阵 C=(cij)nn 的某行（某列）中的各元素分别减去该的某行（某列）中的各元素分别减去该行（该 列）的 最 小 元 素，得 到 新 的 系 数 矩行（该 列）的 最 小 元 素，

6、得 到 新 的 系 数 矩阵阵 ，那么以，那么以 C 和和 为系数矩阵为系数矩阵的两个指派问题有相同的最优解。的两个指派问题有相同的最优解。nnijcC )(C 第第11页页证明：由于系数矩阵的这种变化并不影响数学模型证明：由于系数矩阵的这种变化并不影响数学模型的约束方程组，而只是使目标函数值减少了常数的约束方程组，而只是使目标函数值减少了常数 k，所以最优解并不发生改变。所以最优解并不发生改变。njixnixnjxxczijnjijniijninjijij,.,2,1,10,.,2,11,.,2,11min1111，或或，njixnixnjxxczijnjijniijninjijij,.,2

7、,1,10,.,2,11,.,2,11min1111，或或，第第12页页2.匈牙利法的思路匈牙利法的思路思路：思路：利用指派问题最优解的特性，使原系数矩阵利用指派问题最优解的特性，使原系数矩阵C=(cij)nn 变换成含有很多变换成含有很多 0 元素的新系数矩元素的新系数矩阵阵 ，而最优解保持不变。，而最优解保持不变。nnijcC )(第第13页页如果能在新系数矩阵中找到如果能在新系数矩阵中找到 n 个位于不同行不同列个位于不同行不同列的的 0 元素，并令其对应的变量元素，并令其对应的变量 xij=1，其余变量取值，其余变量取值为为 0，将这样的一组解，将这样的一组解 X 代入目标函数中可得代

8、入目标函数中可得 z=0，它一定是使问题目标函数值最小的解，即指派问题它一定是使问题目标函数值最小的解，即指派问题的最优解。的最优解。独立独立 0 元素：位于不同行不同列的元素：位于不同行不同列的 0 元素。元素。第第14页页3.匈牙利法的步骤匈牙利法的步骤 第一步：变换系数矩阵第一步：变换系数矩阵 C，使其各行各列中都出现，使其各行各列中都出现0：（1）对系数矩阵）对系数矩阵 C 的每行元素分别减去该行的最的每行元素分别减去该行的最小元素；小元素；（2）对系数矩阵）对系数矩阵 C 的每列元素分别减去该列的最的每列元素分别减去该列的最小元素；小元素；第第15页页例：例：911871316149

9、1514410413152)(44ijcC 24104750111006211130 00102350960607130每行减去每行减去最小元素最小元素每列减去每列减去最小元素最小元素第第16页页第二步：确定独立第二步：确定独立 0 元素元素（1）选择只有一个）选择只有一个 0 元素的元素的行行，给这个，给这个 0 元素加元素加圈，记作圈，记作 0；然后划去；然后划去 0 所在所在列列的其他的其他 0 元素，记元素，记作作 0。（2）选择只有一个）选择只有一个 0 元素的元素的列列，给这个，给这个 0 元素加元素加圈，记作圈，记作 0；然后划去；然后划去 0 所在所在行行的其他的其他 0 元素

10、，记元素，记作作 0。第第17页页（3）反复进行（）反复进行（1）和（）和（2），直到所有），直到所有 0 元素都元素都被圈出和划掉为止。被圈出和划掉为止。（4）在（）在（1）和（）和（2）过程中，如不存在只有一个）过程中，如不存在只有一个 0元素的行和列，从元素的行和列，从 0 元素最少的行（列）开始，选元素最少的行（列）开始，选择择 0 元素最少的那列（行）的这个元素最少的那列（行）的这个 0 元素加圈，然元素加圈，然后划掉同行同列的其他后划掉同行同列的其他 0元素。此时问题有多重最元素。此时问题有多重最优解。优解。第第18页页（5）若）若 0 元素数目等于系数矩阵的阶数，那么得元素数目等

11、于系数矩阵的阶数，那么得出问题的最优解；否则转入步骤三。出问题的最优解；否则转入步骤三。第第19页页 00100052000607130例：例：每行和每列中每行和每列中 0 元素数量都不只一个，说明问元素数量都不只一个，说明问题有多个最优解。题有多个最优解。第第20页页 001000520006071300 元素数目为元素数目为4，等于系数矩阵阶数，等于系数矩阵阶数4，故得出问题，故得出问题最优解。问题有多个最优解。最优解。问题有多个最优解。第第21页页第三步：确定覆盖所有第三步：确定覆盖所有 0 元素的最少直线元素的最少直线（1）对没有）对没有 0 的行打的行打“”；（2）在已打）在已打“”

12、的行中，对的行中，对 0 所在的列打所在的列打“”；（3）在已打）在已打“”的列中，对的列中，对 0 所在的行打所在的行打“”；（4）重复（）重复（2）和（）和（3），直到再也找不到可以打），直到再也找不到可以打“”的行或列为止；的行或列为止；（5）对没有打）对没有打“”的行画一横线，对打的行画一横线，对打“”的的列画一垂线，从而得到覆盖所有列画一垂线，从而得到覆盖所有 0 元素的最少直线。元素的最少直线。第第22页页例：例：9107104106614159141217766698979712)(55ijcC解：第一步：解：第一步：9107104106614159141217766698979

13、712 56360400892751000003220205第第23页页第二步：第二步：563604008927510000032202050 元素数目为元素数目为4，不等于系数矩阵阶数，不等于系数矩阵阶数 5，故转第三，故转第三步。步。第第24页页第三步：第三步：56360400892751000003220205第第25页页第四步：继续变换系数矩阵：第四步：继续变换系数矩阵：（1）未被直线覆盖的部分中：找出最小元素；）未被直线覆盖的部分中：找出最小元素；（2）打）打“”的行：减去这个最小元素；的行：减去这个最小元素；（3）打）打“”的列：加上这个最小元素；的列：加上这个最小元素；（4）得到

14、新的系数矩阵，返回第二步。）得到新的系数矩阵，返回第二步。第第26页页解：解：56360400892751000003220205最小元素为最小元素为 2 3414240089053820003220205 34140400811053800003420207第第27页页 34140400811053800003420207每行和每列中每行和每列中 0 元素数量都不只一个，说明问元素数量都不只一个，说明问题有多个最优解。题有多个最优解。第第28页页 34140400811053800003420207第第29页页从而问题最优解为：从而问题最优解为：x12=1，x24=1，x35=1，x43=1

15、，x51=1；或或x12=1，x23=1，x35=1，x44=1，x51=1。第第30页页 17232119191617261822231924211815)(44ijcC解：第一步：解：第一步：17232119191617261822231924211815 06323001004419620 06423011004519630第第31页页 06323001004419620第二步：第二步：第第32页页 06323001004419620第三步：第三步：第第33页页 06323001004419620 15213001013309620第四步：第四步：052140010033010620第第

16、34页页 052140010033010620第五步：第五步：第第35页页 052140010033010620第六步：第六步：第第36页页 052140010033010620 23014000121128402第七步：第七步：030160012011010400第第37页页 030160012011010400第八步：第八步：每行和每列中每行和每列中 0 元素数量都不只一个，说明问元素数量都不只一个，说明问题有多个最优解。题有多个最优解。第第38页页 030160012011010400第第39页页1.最大化指派问题最大化指派问题 设最大化指派问题的系数矩阵为设最大化指派问题的系数矩阵为

17、C=(cij)nn，其中最，其中最大元素为大元素为 m=max cij ；令矩阵令矩阵 C=(m cij)mn，则以，则以 C 为系数矩阵的最为系数矩阵的最小化指派问题和以小化指派问题和以 C 为系数矩阵的最大化问题具有为系数矩阵的最大化问题具有相同的最优解，即相同的最优解，即 第第40页页 nnnnnnnnijccccccccccC.)(212222111211 nnnnnnnnijcmcmcmcmcmcmcmcmcmcC.)(212222111211第第41页页例：求同以例：求同以 9118713161491514410413152)(44ijcC为系数矩阵的最大化指派问题等价的最小化为系

18、数矩阵的最大化指派问题等价的最小化指派问题。指派问题。解：系数矩阵解：系数矩阵 C 中最大元素为中最大元素为 m=c33=16，故，故 第第42页页 916111681671613161616141691615161416416101641613161516216)(44ijcC 7589302712126123114则以则以 C 为系数矩阵的最大化指派问题和以为系数矩阵的最大化指派问题和以C 为系数的最小化指派问题具有相同的最优解。为系数的最小化指派问题具有相同的最优解。第第43页页2.人数和事数不等的指派问题人数和事数不等的指派问题（1）人数）人数 事数：添加虚拟人，令虚拟人做各事事数：添

19、加虚拟人，令虚拟人做各事的费用系数的费用系数=0。mnmmmmmmnmmnmmnmijccccccccccccccccC.)(1,2121,22222111,111211第第44页页 nnmnnmnnnmmmmmmmmnmmmmmmnmmnmmccccccccccccccccccccccccc.1,21,11,1,12,11,11,2121,22222111,111211因为因为 m 事数：添加虚拟事，令虚拟事被各人事数：添加虚拟事，令虚拟事被各人做的费用系数做的费用系数=0。nmijcC)(mnmmnnnnnnnnnnccccccccccccccc.21,11,11,121222211121

20、1第第46页页 mmnmmnmmmnnnnnnnnmnnnnnnmnnmnnccccccccccccccccccccccccc.1,21,11,1,12,11,11,2121,22222111,111211因为因为 m n，添加虚拟人，添加虚拟人 费用值均为费用值均为 0 第第47页页3.一个人可做几件事的指派问题一个人可做几件事的指派问题若第若第 i 人可做人可做 m 件事：将第件事：将第 i 人化作人化作 m 个人来接受个人来接受指派，这指派，这 m 个人的费用系数都一样。个人的费用系数都一样。设第设第 i 人可做人可做 m 件事，则件事，则 第第48页页 nnnniniinncccccc

21、ccccccC.21212222111211 nnnnniiiniiinncccccccccccccccCmmm.21,2,1,2,1,2222111211111其中：其中：niiiccc,2,1,111.niiimmmccc,2,1,.iniiccc.21=第第49页页4.某事不能由某人做的指派问题某事不能由某人做的指派问题 若第若第 j 件事不能由第件事不能由第 i 人做：令其相应的费用系数人做：令其相应的费用系数cij=M。nnnjnninijiinjnjccccccccccccccccC.2121222221111211 nnnjnniniinjnjcccccMccccccccccC.

22、2121222221111211第第50页页例：例：3 家建筑公司承建家建筑公司承建 5 家商店，允许每家建筑公家商店，允许每家建筑公司可承建司可承建 2 家商店，求总费用最少的指派方案。家商店，求总费用最少的指派方案。商店商店建筑公司建筑公司B1 B2B3B4B5A14 871512A279171410A3691287第第51页页解：解：（1）因为每家建筑公司可承建）因为每家建筑公司可承建 2 家商店，因此，把家商店，因此，把每家建筑公司化作相同的两家建筑公司，这样系数每家建筑公司化作相同的两家建筑公司，这样系数矩阵变为：矩阵变为：商店商店建筑公司建筑公司B1 B2B3B4B5A14 871

23、5124 871512A27917141079171410A36912876912871A 2A 3A 第第52页页 商店商店建筑公司建筑公司B1 B2B3B4B5A14 87151204 8715120A2791714100791714100A3691287069128701A 2A 3A（2）因为人数）因为人数 事数：增加虚拟事。事数：增加虚拟事。5B 第第53页页（3）第一步：第一步：00051200051203610130361013057000057000第第54页页 00051200051203610130361013057000057000第二步：第二步：第第55页页第三步：第三

24、步：00051200051203610130361013057000057000第第56页页第四步：第四步：00051200051203610130361013057000057000最小元素为最小元素为 1 000512000512125902125902057000057000 100512100512025902025902157000157000第第57页页 100512100512025902025902157000157000最优解为：最优解为：x11=1，x23=1，x36=1，x42=1，x54=1，x65=1z=4+7+0+9+8+7=35。第第58页页即：即：A1 承建承建 B1 和和 B3。A2 承建承建 B2。A3 承建承建 B4 和和 B5。