大学精品课件：运筹学（五）.ppt

1、第五章第五章整整 数数 规规 划划主要内容：主要内容：第一节第一节 整数规划的数学模型及解的特点整数规划的数学模型及解的特点第二节第二节 解纯整数规划的割平面法解纯整数规划的割平面法第三节第三节 分支定界法分支定界法第四节第四节 0-10-1型整数规划型整数规划第五节第五节 指派问题指派问题第一节第一节整数规划的数学模型及解的特点整数规划的数学模型及解的特点一、整数规划问题举例一、整数规划问题举例 例例1 1（纯整数规划）（纯整数规划）：某个中型百货商场对售货人员（周工某个中型百货商场对售货人员（周工资资200200元）的需求经统计如下表：元）的需求经统计如下表：为了保证销售人员充分休息，销售

2、人员每周工作为了保证销售人员充分休息，销售人员每周工作5 5天，休息天，休息2 2天天（这两天是连续的）。问应如何安排销售人员的工作时间，使（这两天是连续的）。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？得所配售货人员的总费用最小？星期星期一一二二三三四四五五六六七七人数人数12151214161819 解解：设：设x xj j为在星期为在星期j j开始上班的销售人员数目，开始上班的销售人员数目，则该问题的数学模型为：则该问题的数学模型为：71200minjjxz 例例2 2（0-10-1整数规划）整数规划）：某公司有：某公司有5 5个投资项目被列入投资计划，个投资项目被列入

3、投资计划，各项目需要的投资额和期望的收益见下表：各项目需要的投资额和期望的收益见下表：已知该公司只有已知该公司只有600600万元资金可用于投资，由于技术上的原因，投资万元资金可用于投资，由于技术上的原因，投资受到以下约束：受到以下约束：（1 1）项目）项目1 1、项目、项目2 2和项目和项目3 3至少应有一项选择；至少应有一项选择；（2 2）项目）项目3 3和项目和项目4 4最多只能选一项；最多只能选一项；（3 3）项目）项目5 5选中的前提是项目选中的前提是项目1 1必须选中。必须选中。问如何选择一个最好的投资方案使得总的投资收益最大。问如何选择一个最好的投资方案使得总的投资收益最大。项目

4、项目投资额投资额/万元万元期望收益期望收益/万元万元121015023002103100604130805260180 解解：每一个投资项目都有被选择和不被选择两：每一个投资项目都有被选择和不被选择两种可能，因此令：种可能，因此令：则该问题的数学模型为：则该问题的数学模型为：543211808060210150maxxxxxxz 5,4,3,2,11011600260130100300210.154332154321jxxxxxxxxxxxxxstj，或或 不投资）不投资）（对项目（对项目投资）投资）对项目对项目j 0j(1jx5,4,3,2,1 j 例例3 3（混合整数规划）（混合整数规划）

5、：工厂：工厂A1A1和和A2A2生产两种物资。由于该种物资供不生产两种物资。由于该种物资供不应求，需要再建立一家年生产能力为应求，需要再建立一家年生产能力为200kt200kt的工厂，相应的建厂方案有的工厂，相应的建厂方案有A3A3和和A4A4两个。这种物资的需求地有两个。这种物资的需求地有B1,B2,B3,B4B1,B2,B3,B4四个。各工程年生产能力、四个。各工程年生产能力、各地需求量、各厂至各需求地的单位物资运费见下表：各地需求量、各厂至各需求地的单位物资运费见下表：工厂工厂A3A3或或A4A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为12001200万元或万元或

6、15001500万元。万元。现要决定建设工厂现要决定建设工厂A3A3还是还是A4,A4,才能使今后每年的总费用最少。才能使今后每年的总费用最少。B1B2B3B4A12934400A28357600A37612200A44525200350400300150 解解：设：设x xijij表示从表示从A Ai i厂运往厂运往B Bj j地的物资数量，再设：地的物资数量，再设：则该问题的数学模型为：则该问题的数学模型为：厂）厂）（建（建）建建4 03(1AAy厂 4141)1(15001200minijijijyyxcz 104,3,2,1;4,3,2,1,0)1(200200600400150300

7、400350.4443424134333231242322211413121144342414433323134232221241312111或或yjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxstij二、整数规划问题的数学模型二、整数规划问题的数学模型 njjjxcz1min)max(或或 整数整数个变量中部分或全部为个变量中部分或全部为），或或n),1(0),1(.1njxmibxastjnjijij规划变量规划整数变量整数变量整数或全部为个混合整数不全部为个纯整数规划全部为个10 10n n n三、整数规划问题的解的特点三、整数规划问题的解的特点 整数整数个变

8、量中部分或全部为个变量中部分或全部为），或或n),1(0),1(.1njxmibxastjnjijij njjjxcz1min)max(或或 ),1(0),1(.1njxmibxastjnjijij），或或整数规划问题整数规划问题整数规划问题的松弛问题整数规划问题的松弛问题1、整数规划问题的可行解一定是其松弛问题的可行解；、整数规划问题的可行解一定是其松弛问题的可行解；2、若目标函数求极大（、若目标函数求极大（小小），整数规划问题的最优解对），整数规划问题的最优解对应的目标函数值一定小（应的目标函数值一定小（大大）于等于其松弛问题最优解对）于等于其松弛问题最优解对应的目标函数值。应的目标函数值

9、。njjjxcz1min)max(或或3、不能把其松弛问题的最优解取整作为该整数规划问题、不能把其松弛问题的最优解取整作为该整数规划问题的最优解。的最优解。214maxxxz 且取整数且取整数0,82332.212121xxxxxxst第二节第二节求解纯整数规划的割平面法求解纯整数规划的割平面法一、割平面法的思路一、割平面法的思路1、求出整数规划问题的、求出整数规划问题的松弛问题的最优解。松弛问题的最优解。2、若得到最优解满足整数要求，则该最优解就、若得到最优解满足整数要求，则该最优解就是整数规划问题的最优解；是整数规划问题的最优解；若最优解不满足整数要求，则若最优解不满足整数要求，则增加一个

10、约增加一个约束条件（建立割平面方程）束条件（建立割平面方程），使得最优解不，使得最优解不满足该约束条件，而所有的整数规划的可行满足该约束条件，而所有的整数规划的可行解仍满足该约束条件。解仍满足该约束条件。3、重新求解增加约束条件后的最优解，回到、重新求解增加约束条件后的最优解，回到2。二、割平面法计算步骤二、割平面法计算步骤例：用割平面法求解纯整数规划例：用割平面法求解纯整数规划213maxxxz 为整数为整数2121212121,0,521045323.xxxxxxxxxxst213maxxxz 0,521045323.21212121xxxxxxxxst松弛松弛问题问题-3/70-5/70

11、022/71-3/70031/703/70-2/7109/7-12/701/70113/73000-13jjzc jcBCBxb2x2x3x4x5x1x1x4x解：解：（1 1）求解其松弛问题的最优解求解其松弛问题的最优解。用单纯形法。用单纯形法进行求解，得到最优单纯形表如下（进行求解，得到最优单纯形表如下（x3,x4,x5x3,x4,x5为松为松弛变量）：弛变量）：该最优解不满足整数要求，因此需要建立割平面方程。该最优解不满足整数要求，因此需要建立割平面方程。（2 2）建立割平面方程）建立割平面方程：最终单纯形表第一行：最终单纯形表第一行：5317271713xxx 5317271761xx

12、x 1727176153 xxx072717653 xx因为因为x x1 1为整数，故为整数，故x x1 1-1-1也为整数，因此等号左边的也为整数，因此等号左边的式子也为整数。又因为式子也为整数。又因为6/76/7小于小于1 1，x x3 3和和x x5 5都大于等都大于等于于0 0，故该整数一定小于等于零。，故该整数一定小于等于零。即：即：（割平面约束）（割平面约束）引入松弛变量引入松弛变量x6,x6,建立割平面方程：建立割平面方程：767271653 xxx76727153 xx3-10000313/7101/702/70-19/701-2/703/70031/700-3/7122/70

13、0-6/700-1/70-2/7100-5/70-3/70jjzc jcBCBxb1x3x4x5x6x1x2x2x6x4x用对偶单纯形法继续求解，得到新的最优解用对偶单纯形法继续求解，得到新的最优解：（3 3）把割平面方程加入到上个最终单纯形表中，得到）把割平面方程加入到上个最终单纯形表中，得到：3-1000031100001-15/4010-1/40-5/405/2001-1/20-11/207/40001/41-3/4000-1/40-17/4jjzc jcBCBxb1x3x4x5x5x1x2x2x6x3x该最优解仍不满足整数要求，因此还需要建立割平面方程。该最优解仍不满足整数要求，因此还

14、需要建立割平面方程。最终单纯形表第四行：最终单纯形表第四行：654434147xxx 66454141431xxxx 14141436564 xxxx041414364 xx43414164 xx（割平面约束）（割平面约束）引入松弛变量引入松弛变量x7,x7,建立割平面方程：建立割平面方程：434141764 xxx（4 4）建立割平面方程）建立割平面方程：3-100000311000010-15/4010-1/40-5/4005/2001-1/20-11/2007/40001/41-3/400-3/4000-1/40-1/41000-1/40-17/40jjzc jcBCBxb1x3x4x5

15、x5x1x2x2x6x3x7x311000010-1201000-1-10400100-5-20100001-1103000101-400000-4-11x5x2x3x4xjjzc 7x（5 5）将割平面方程带入上个最优单纯形表中，用对偶单纯形法求解）将割平面方程带入上个最优单纯形表中，用对偶单纯形法求解：该最优解满足整数要求，即为整数规划的最优解。该最优解满足整数要求，即为整数规划的最优解。76727153 xx43414164 xx 521045323521421321xxxxxxxxx 215214213251045233xxxxxxxxx76)25(72)233(712121 xxxx

16、6)25(2)233(2121 xxxx11x767271653 xxx76)25(72)233(7162121 xxxxx161xx 43)1(41)1045(41121 xxx311045121 xxx321 xx（第（第1 1个割平面方程个割平面方程）（第（第2 2个割平面方程个割平面方程）考察割平面方程的几何意义：考察割平面方程的几何意义：BACD11xEFABCDE(1,5/4)AGHF321 xxGHD(13/7,9/7)ABEFH(1,2)三、注意三、注意 整数规划模型的约束条件中，若约束条件中整数规划模型的约束条件中，若约束条件中变量的系数或右端常数取值不为整数时，首变量的系数

17、或右端常数取值不为整数时，首先要把它们变为整数）先要把它们变为整数）保证松弛变量或剩余变量保证松弛变量或剩余变量的取值也为整数。的取值也为整数。第三节第三节分分 支支 定定 界界 法法一、分支定界法的思路一、分支定界法的思路 分支分支：若整数规划的松弛问题的最优解不符合整数要若整数规划的松弛问题的最优解不符合整数要求，假设求，假设 不符合整数要求，不符合整数要求，是不超过是不超过 的最的最大整数，则构造两个约束条件：大整数，则构造两个约束条件：和和 ，分别将其并入松弛问题中，从而形成两个后继问，分别将其并入松弛问题中，从而形成两个后继问题，即两个分支。题，即两个分支。iibx ibib iib

18、x 1iibx为整数规划的最优解的为整数规划的最优解的出现创造了条件出现创造了条件（不是整数）松弛问题最优解中iibx x1x2X1=2.5X1=2X1=3定界定界：在分支过程中，若某个后继问题恰巧获得整数规：在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个划问题的一个可行解，那么，它的目标函数值就是一个“界限界限”，可以作为衡量处理其它分支的一个依据（当，可以作为衡量处理其它分支的一个依据（当某个分支的最优解的目标函数值比该界限差，则这个分某个分支的最优解的目标函数值比该界限差，则这个分支可以剔除不计）。当出现更优的支可以剔除不计）。当出现更优的“界

19、限界限”，则用新界，则用新界限代替原来的界限。限代替原来的界限。提高了最优解的搜索效率提高了最优解的搜索效率二、分支定界法的步骤二、分支定界法的步骤例：用分支定界法求解整数规划例：用分支定界法求解整数规划21maxxxz 为整数为整数21212121,0,3121451149.xxxxxxxxst松弛松弛问题问题21maxxxz 0,3121451149.212121xxxxxxst解解：（：（1）求解其松弛问题。）求解其松弛问题。得到最优解得到最优解 (3/2,10/3)，不满足整数要求。，不满足整数要求。x1x2A(3/2,10/3)S （2）分支。）分支。选择选择x1=3/2进行分支进行

20、分支。构造两个约束条件：构造两个约束条件：x111和和x1x12进行分支进行分支。x1x2（1，7/3）BC（2，23/9）S1S2 得到两个后继问题：得到两个后继问题：LP1LP1和和LP2LP2。（3）继续分支。）继续分支。因为因为LP1和和LP2所得到的最优解都不满足整数所得到的最优解都不满足整数要求，需要继续分支要求，需要继续分支。考虑到。考虑到LP2的最优解对应的的最优解对应的目标函数值较大些，因此，选择目标函数值较大些，因此，选择LP2进行分支。进行分支。LP2最优解中最优解中x2=23/9不满足整数要求，需要不满足整数要求，需要进行分支。构造两个约束条件：进行分支。构造两个约束条

21、件：x22和和x23 x1x2（1，7/3）BD（33/14，2）S1S21 得到两个后继问题：得到两个后继问题：LP21LP21和和LP22LP22。（4）继续分支。）继续分支。LP22无可行解；无可行解；LP21所得到的最优解所得到的最优解（33/14，2）不满足整数要求，需要继续分支）不满足整数要求，需要继续分支。考虑到考虑到LP21的最优解对应的目标函数值较大些，的最优解对应的目标函数值较大些，因此，选择因此，选择LP21的的x1进行分支。进行分支。构造两个约束条件：构造两个约束条件：x12和和x13.x1x2（1，7/3）BF（2，2）S1S212S211E（3，1）得到两个后继问题

22、：得到两个后继问题：LP211LP211和和LP212LP212。（5）定界）定界 LP211和和LP212所得到的最优解（所得到的最优解（2，2）和（和（3，1）都满足整数要求，且对应的目标值相）都满足整数要求，且对应的目标值相同，都为同，都为4，因此可以给目标函数定下界，因此可以给目标函数定下界4。考虑考虑LP1，其最优解对应的目标函数为，其最优解对应的目标函数为10/3，小于下界小于下界4，因此不用对其进行分支，因此不用对其进行分支。所以，该整数规划问题的最优解为（所以，该整数规划问题的最优解为（2，2）和）和（3，1）。6/293/10,2/321zxxA S3/103/7,121zx

23、xC S19/419/23,221zxxB S214/612,14/3321zxxD S21 无可行解S22)442,221Z(zxxFS21141,321zxxE S21211x 21x 21x 31x 22x 32x 上述求解过程可以总结如下图：上述求解过程可以总结如下图：第四节第四节0-1 0-1 整整 数数 规规 划划一、一、0-10-1规划的举例规划的举例1 1、选址问题（布点问题）、选址问题（布点问题）要选取投资场所，已知要选取投资场所，已知：区名区名Ai可供选择的点可供选择的点投资投资（元）（元）年利润年利润（元）（元）总资金总资金（元）（元）东区东区 A1b1c1B A2（最多

24、选两个点）（最多选两个点）b2c2 A3b3c3西区西区 A4b4c4 A5b5c5南区南区 A6b6c6 A7b7c7（至少选一个点）（至少选一个点）（至少选一个点）（至少选一个点）问如何布点，使总利润最大？问如何布点，使总利润最大？解：设解：设)7,2,1 0(1 iAAxiii（处不设点）处不设点）（在（在处设点）处设点）在在iiixcZ 71max7,2,1,10112765432171 ixxxxxxxxBxbiiii或或2 2、两个约束中选取一个约束的问题、两个约束中选取一个约束的问题设工序设工序B的每周工时约束条件为：的每周工时约束条件为：1505.03.021 xx还有一种加工

25、方式，相应工序还有一种加工方式，相应工序B的每周工时约束条件为：的每周工时约束条件为：1204.02.021 xx如果工序如果工序B只能从两种加工方式中选择一种，则设：只能从两种加工方式中选择一种，则设：种加工方式）种加工方式）（选择第（选择第种加工方式）种加工方式）选择第选择第2 01(1y假设假设M为充分大的数，则上述问题可表述为：为充分大的数，则上述问题可表述为：10,0,1204.02.0)1(1505.03.0212121或或yxxMyxxyMxx3 3、p p个约束中选取个约束中选取q q个约束的问题个约束的问题设有设有p个约束：个约束：),2,1(1pibxainjjij 从中选

26、取从中选取q个约束。个约束。),2,1 i(1i(0piyi （个约束）个约束）若不选择第若不选择第个约束）个约束）若选择第若选择第),2,1(11piqpyyMbxapiiiiinjjij 且设且设Mi为充分大的数，则该问题可表述为：为充分大的数，则该问题可表述为：若引入若引入p个个0-1变量：变量：4 4、固定费用问题、固定费用问题有三种资源被用于生产三种产品，资源量、产品单件可有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定生产计划，使总收益最大。费用见下表。要求制定生产计

27、划，使总收益最大。资源量资源量A248500B234300C123100单位可变费用单位可变费用456固定费用固定费用100150200单件售价单件售价81012单耗量单耗量资源资源产品产品解解：设：设xj是第是第j种产品的产量，种产品的产量，j=1,2,3，再设：，再设：)3,2,1 i(0i(1 jyi（个产品）个产品）若不生产第若不生产第个产品）个产品）若生产第若生产第该问题的整数规划模型为：该问题的整数规划模型为：321321200150100654maxyyyxxxZ 3,2,1,103,2,1,010032300432500842.333222111321321321jyjxyMx

28、yMxyMxxxxxxxxxxstjj或或二、0-1整数规划的解法o 完全枚举法完全枚举法o 隐枚举法隐枚举法9 9（1 1，1 1，1 1）5 5（1 1，1 1，0 0）6 6（1 1，0 0，1 1）2 2（1 1，0 0，0 0）7 7（0 0，1 1，1 1）3 3（0 0，1 1，0 0）z z444 4（0 0，0 0，1 1）0 0（0 0，0 0，0 0）过滤条件过滤条件约束条件约束条件z z(x1,x2,x3)(x1,x2,x3)321432maxxxxZ 321101334435232321321,i或xxxxxxxxxi 求解求解0-1规划规划：第五节第五节指指 派派

29、问问 题题一、标准形式的指派问题及其数学模型一、标准形式的指派问题及其数学模型 有有n n个人和个人和n n件事，已知第件事，已知第i i个人做第个人做第j j件事的件事的费用（时间）为费用（时间）为c cijij（i i，j=1j=1，2 2，n n），要求），要求每个人只能做一件事情。怎样把每个人只能做一件事情。怎样把n n件事情分配给件事情分配给n n个人，才能使得总费用（时间）最少。个人，才能使得总费用（时间）最少。标准形式的指派问题：标准形式的指派问题：引入引入n n2 2个个0-10-1变量：变量：标准形式指派问题的数学模型：标准形式指派问题的数学模型：n n),1 1,2 2,j

30、 j （i i,第第j j件件事事情情）(若若不不指指派派第第i i个个人人做做 0 0j j件件事事情情）(若若指指派派第第i i个个人人做做第第 1 1 ijx 则该问题的数学模型为：则该问题的数学模型为：ninjijijxcz11min njixnxnxstijnjijniij,2,1,10.11或或矩阵矩阵C=（cij）nn称为指派问题的系数称为指派问题的系数矩阵矩阵指派问题是特殊的指派问题是特殊的0-10-1规划问题；规划问题；也是特殊的运输问题。也是特殊的运输问题。某商业公司计划开办某商业公司计划开办5 5家新商店。为了尽早建成营业，家新商店。为了尽早建成营业，商业公司决定有商业公

31、司决定有5 5家建筑公司分别承建。已知建筑公司家建筑公司分别承建。已知建筑公司A Ai i（i=1i=1，2 2，5 5）对新商店）对新商店B Bj j （j=1j=1，2 2，5 5）的建）的建造费用的报价为造费用的报价为c cijij （i i，j=1j=1，2 2，5 5），如下表所，如下表所示。该商业公司应如何给示。该商业公司应如何给5 5个建筑公司分配建造任务，才个建筑公司分配建造任务，才能使总建造费用最少。能使总建造费用最少。例例1 1：B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106cijAiBj解：解：这是一个标准形

32、式的指派问题。引入这是一个标准形式的指派问题。引入0-1变量：变量：,5),5)1,2,1,2,j j （i,（i,）B BA A(若不指派(若不指派 0 0）B BA A(若指派(若指派 1 1 jiji承建商店承建商店建筑公司建筑公司承建商店承建商店建筑公司建筑公司ijx该问题的数学模型为：该问题的数学模型为：5151minijijijxcz 5,2,1,1011.5151jixxxstijjijiij或或二、匈牙利解法二、匈牙利解法 03047402506503101、匈牙利解法的思路：、匈牙利解法的思路：如果系数矩阵的所有元素满足如果系数矩阵的所有元素满足c cijij00，而其中，而

33、其中有有n n个位于不个位于不同行不同列的一组同行不同列的一组0 0元素元素，则只要令对应于这些，则只要令对应于这些0 0元素位置元素位置的的x xijij1 1，其余的，其余的x xijij0 0，就得到最优解。，就得到最优解。如：如：因此可以通过变换系数矩阵使因此可以通过变换系数矩阵使得系数矩阵中出现满足要求的得系数矩阵中出现满足要求的0元素。元素。指派问题是特殊的运输问题，若指派问题的系数矩阵指派问题是特殊的运输问题，若指派问题的系数矩阵C C的某行（或某列）的各元素减去一个常数的某行（或某列）的各元素减去一个常数k k，得到新的矩，得到新的矩阵阵CC，则以，则以C C和和CC为系数矩阵

34、的两个指派问题有相同的为系数矩阵的两个指派问题有相同的最优解。最优解。那么，如何使系数矩阵出现那么，如何使系数矩阵出现n n个位于不同行不同列的一组个位于不同行不同列的一组0 0元素？元素？2、匈牙利解法的步骤：、匈牙利解法的步骤：第一步：变换系数矩阵第一步：变换系数矩阵，使每行每列都出现，使每行每列都出现0 0元素，但不元素，但不出现负元素。出现负元素。(1)(1)系数矩阵的各行分别减去各行中的最小元系数矩阵的各行分别减去各行中的最小元素；素；(2)(2)所得系数矩阵的各列再分别减去各列中的最小元素。所得系数矩阵的各列再分别减去各列中的最小元素。第二步：第二步：在变换后的系数矩阵中在变换后的

35、系数矩阵中确定独立零元素，并判确定独立零元素，并判断是否为最优解断是否为最优解。(1)(1)给只有一个给只有一个0 0元素（不含划去的元素（不含划去的0 0）的行中的）的行中的“0”0”加圈（记为加圈（记为 ），），划去与划去与同列的其它同列的其它“0”0”（记为（记为）；）；(2)(2)给只有一个给只有一个0 0元素（不含划去的元素（不含划去的0 0）的列中的）的列中的“0”0”加圈，划去与加圈，划去与同行的其它同行的其它“0”0”；(3)(3)重复重复(1)(1)、(2)(2)，直到所有的，直到所有的0 0 元素都被加圈或划去，则已得到最多元素都被加圈或划去，则已得到最多的的（称为独立零元

36、素称为独立零元素）.注意：若在这个过程中出现所有的行和列中，注意：若在这个过程中出现所有的行和列中，0 0元素都不止一个时元素都不止一个时(存存在在0 0元素的闭回路），可在元素的闭回路），可在0 0元素的闭回路中任选一个元素的闭回路中任选一个0 0元素加圈，同元素加圈，同时划去同行和同列的其它时划去同行和同列的其它0 0元素。元素。若独立零元素的个数为若独立零元素的个数为n n，则已经得到最优解。，则已经得到最优解。若独立零元素的个数少于若独立零元素的个数少于n n，则转入下一步。，则转入下一步。第三步：用最少的直线覆盖所有第三步：用最少的直线覆盖所有0 0元素元素。(1)(1)给无给无的行

37、打的行打“”；(2)(2)给打给打“”行中，对行中，对 所在的列打所在的列打“”；(3)(3)给打给打“”列中，对列中，对所在的行打所在的行打“”；(4)(4)重复重复(2)(2)、(3)(3)，直到无新的，直到无新的“”打出。打出。(5)(5)给没有打给没有打的行画横线，给打的行画横线，给打的列画纵线。的列画纵线。第四步：继续变换系数矩阵，增加第四步：继续变换系数矩阵，增加0 0元素。元素。在未被直线在未被直线覆盖的其它元素中找出最小元素，各打覆盖的其它元素中找出最小元素，各打“”行减去行减去最小元素，各打最小元素，各打“”列加上最小元素，转第二步。列加上最小元素，转第二步。3、用匈牙利解法

38、求解例、用匈牙利解法求解例1 第一步：变换系数矩阵第一步：变换系数矩阵 61012961061476781296101417971215784C 各行减本行各行减本行 最小元素最小元素 046304081012630371020811340 04320405001232037710811030C 第二步：确定独立零元素第二步：确定独立零元素 04320405001232037710811030 C 各列减本列各列减本列 最小元素最小元素独立零元素个数独立零元素个数为为4，小于，小于n=5。第三步：用最少的直线覆盖所有第三步：用最少的直线覆盖所有0 0元素。元素。0432040500123203

39、7710811030 C第四步：继续变换系数矩阵，增加第四步：继续变换系数矩阵，增加0 0元素元素。04320405000121126601811030C未被直线覆盖的未被直线覆盖的最小元素为最小元素为1 1C 04321405010121026600811031第五步：重新确定独立零元素第五步：重新确定独立零元素。04321405010121026600811031C独立零元素个数为独立零元素个数为5 5，等于，等于n n，因此得到最优解，因此得到最优解。1000001000000010001000100*XA1A1承建承建B3B3A2A2承建承建B2B2A3A3承建承建B1B1A4A4承建

40、承建B4B4A5A5承建承建B5B5最小费用为：最小费用为：7+9+6+6+6=347+9+6+6+6=34（万元）（万元）三、非标准形式的指派问题三、非标准形式的指派问题1、最大化指派问题、最大化指派问题2、人数和事数不相等的指派问题、人数和事数不相等的指派问题3、一个人可以做几件事情的问题、一个人可以做几件事情的问题4、某事一定不能由某人来做的指派问题、某事一定不能由某人来做的指派问题1、最大化指派问题：、最大化指派问题：nnnnnncccccccccC212222111211 nnnnnncmcmcmcmcmcmcmcmcmC212222111211求系数为求系数为C的最大化指派问题相当

41、于求系数为的最大化指派问题相当于求系数为C的最小化指派问题（的最小化指派问题（m为矩阵为矩阵C中的最大元素）：中的最大元素）：4457556473049352 1111108101091181215116121013C例例2 2：求如下系数矩阵的最大化指派问题：求如下系数矩阵的最大化指派问题：解：该问题可转化为求如下系数矩阵的最小化指派问题：解：该问题可转化为求如下系数矩阵的最小化指派问题：111511151015815101510159151115815121515151115615121510151315C其余步骤略。其余步骤略。2 2、人数和事数不相等的指派问题：、人数和事数不相等的指派

42、问题：人少事多，一人只能做一件事情：增加虚拟人。人少事多，一人只能做一件事情：增加虚拟人。人多事少，一人只能做一件事情：增加虚拟事情。人多事少，一人只能做一件事情：增加虚拟事情。系数矩阵中增加的系数均为系数矩阵中增加的系数均为0 0。320514473425 0320051404730425如：如：又如：又如：625145467317425 0000000000625145467317425人多事少，增加虚拟人多事少，增加虚拟事情，系数矩阵为：事情，系数矩阵为：人少事多，增加虚人少事多，增加虚拟人，系数矩阵为拟人，系数矩阵为:3 3、一个人可以做几件事情的指派问题：、一个人可以做几件事情的指派

43、问题：把一个看做是几个相同的人。把一个看做是几个相同的人。例：例：某商业公司计划开办某商业公司计划开办5 5家新商店。为了尽早建成营业，家新商店。为了尽早建成营业，商业公司决定有商业公司决定有3 3家建筑公司分别承建。已知建筑公司家建筑公司分别承建。已知建筑公司AiAi（i=1i=1，2 2，3 3）对新商店）对新商店BjBj （j=1j=1，2 2，5 5）的建造费用）的建造费用的报价为的报价为cijcij （i=1i=1，2 2，3 3；j=1j=1，2 2，5 5），如下表所，如下表所示。示。每个建筑公司都可以承建一项或两项工程每个建筑公司都可以承建一项或两项工程，该商业公，该商业公司应

44、如何给司应如何给3 3个建筑公司分配建造任务，才能使总建造费用个建筑公司分配建造任务，才能使总建造费用最少。最少。B1B2B3B4B5A14871512A279171410A3691287cijAiBj解：解：每个建筑公司都看成相同的两个建筑公司，系数矩阵为：每个建筑公司都看成相同的两个建筑公司，系数矩阵为：078129607812960101417970101417970121578401215784332211AAAAAA654321BBBBBB人数大于事数，增加虚拟商店人数大于事数，增加虚拟商店B6B6，系数矩阵为：，系数矩阵为：78129678129610141797101417971

45、2157841215784332211AAAAAA54321BBBBB其余步骤略。其余步骤略。4 4、某事一定不能由某人来做的指派问题：、某事一定不能由某人来做的指派问题：例：例：某商业公司计划开办某商业公司计划开办4 4家新商店。为了尽早建成营业，家新商店。为了尽早建成营业，商业公司决定有商业公司决定有3 3家建筑公司分别承建。已知建筑公司家建筑公司分别承建。已知建筑公司AiAi（i=1i=1，2 2，3 3）对新商店）对新商店BjBj （j=1j=1，2 2，3 3，4 4）的建造费用）的建造费用的报价为的报价为cijcij （i=1i=1，2 2，3 3；j=1j=1，2 2，3 3，4

46、 4），如下表所，如下表所示。由于实际原因，示。由于实际原因，建筑公司建筑公司A2A2必须承建一个商店，公司必须承建一个商店，公司A1A1和和A3A3可以承建一个或两个商店且可以承建一个或两个商店且A1A1不能承建商店不能承建商店B3B3，该，该商业公司应如何给商业公司应如何给3 3个建筑公司分配建造任务，才能使总建个建筑公司分配建造任务，才能使总建造费用最少。造费用最少。B1B2B3B4A148M15A2791714A369128cijAiBj系数矩阵中对应的元素取系数矩阵中对应的元素取M（M为充分大的数）。为充分大的数）。解：解：把建筑公司把建筑公司A1A1和和A3A3分别看成相同的两个建筑公司，系数分别看成相同的两个建筑公司，系数矩阵为：矩阵为：81296812961417971584158433211MMAAAAA4321BBBB人数多于事数，引入虚拟事情人数多于事数，引入虚拟事情B5B5，系数矩阵为，系数矩阵为：081296081296141797015840158433211MMMAAAAA54321BBBBB其余步骤略。其余步骤略。作业：作业：5.13（1）5.14