第四章整数规划

1、第四章第四章 整数规划整数规划 (Integer Programming，IP) 在线性规划问题的求解过程中，最优解可在线性规划问题的求解过程中，最优解可能是整数，也可能不是整数。在一些情况下，能是整数，也可能不是整数。在一些情况下，某些实际问题要求最优解必须是整数，例如，某些实际问题要求最优解必须是整数，例如，若所求得的解是安排上班的人数，需要采购若所求得的解是安排上班的人数，需要采购的机器台数等。的机器台数等。 用前面介绍的线性规划方法求解时，不用前面介绍的线性规划方法求解时，不一定能得到整数解。为解决这一类变量为整一定能得到整数解。为解决这一类变量为整数的实际问题，出现了整数规划模型。数

2、的实际问题，出现了整数规划模型。 在所建模型中，在所建模型中，决策变量决策变量全为整数全为整数的问题称为的问题称为纯整数规划纯整数规划( (Pure Integer Programming) )或或全整数规划全整数规划( (All Integer Programming) )；决策变量决策变量中部分为整数、部分为非整数中部分为整数、部分为非整数的问题的问题称为称为混合整数规划混合整数规划( (Mixed Integer Programming) )；变量取值为变量取值为0 0或或1 1的问题称为的问题称为0-10-1整数规划。整数规划。 对于求整数解的线性规划问题，能否对于求整数解的线性规划问

3、题，能否采用采用四舍五入或者去尾四舍五入或者去尾的方法将求得的非的方法将求得的非整数解加以解决呢？如果不能，有无有效整数解加以解决呢？如果不能，有无有效的解决方案呢？的解决方案呢？4.1 4.1 整数规划的数学建模整数规划的数学建模 4.1.1 4.1.1 装箱问题装箱问题 例例4.1 4.1 某厂拟用集装箱托运甲、乙两种货物，每箱某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表的体积、重量、可获利润以及托运所受限制如表4 41 1所示。问两种货物各托运多少箱，可使获得利润为最所示。问两种货物各托运多少箱，可使获得利润为最大？大？表表 4 41 1货物货物体积（

4、米体积（米3 3/ /箱）箱）重量（百公斤重量（百公斤/ /箱）箱） 利润（百元利润（百元/ /箱）箱）甲甲5 52 22020乙乙4 45 51010托运限制托运限制2424米米3 31313百公斤百公斤解：解： 设设 、 分别为甲、乙两种货物的托运箱分别为甲、乙两种货物的托运箱数，则数学模型可以表示为：数，则数学模型可以表示为：其中，目标函数表示追寻最大的利润，约束条件其中，目标函数表示追寻最大的利润，约束条件分别表示装箱的体积和重量限制，决策变量要求分别表示装箱的体积和重量限制，决策变量要求装箱数必须为整数。装箱数必须为整数。1212121212max201054242513,0,zxx

5、xxxxxxxx整 数1x2x例例4.2 4.2 某公司拟在市东、西、南三区建立门市某公司拟在市东、西、南三区建立门市部，有部，有7 7个位置个位置 （ ）可供选择，考虑）可供选择，考虑到各地区居民消费水平及居民居住密集度，公司到各地区居民消费水平及居民居住密集度，公司制定了如下规定：制定了如下规定：在东区，由在东区，由 ， ， 三个点中至多选两个；三个点中至多选两个；在西区，由在西区，由 ， 两个点中至少选一个；两个点中至少选一个；在南区，由在南区，由 ， 两个点中至少选一个。两个点中至少选一个。如选用点如选用点 ，设备投资预计为，设备投资预计为 元，每年可获利元，每年可获利润预计为润预计为

6、 元，由于公司的投资能力及投资策略元，由于公司的投资能力及投资策略限制，要求投资总额不能超过限制，要求投资总额不能超过B B元。问应如何选元。问应如何选择可使年利润为最大？择可使年利润为最大？iA1,2,7i 1A2A3A4A5A6A7AiAibic4.1.2 4.1.2 工厂选址问题工厂选址问题解：设解：设 表示是否在位置表示是否在位置i i 建立门市建立门市部，有部，有 则可以建立如下的数学模型：则可以建立如下的数学模型：(1,2,7)iix10iiiAxA，当 点被选用，当 点没被选用1,2,7i 71711234567m ax2.1101iiiiiiizc xBb xxxxs txxx

7、xx 或 其中，目标函数表示其中，目标函数表示寻求获利最大的设点方案，寻求获利最大的设点方案，第一个约束条件表示投资第一个约束条件表示投资总额限制，之后的三个约总额限制，之后的三个约束条件分别表示在东、西束条件分别表示在东、西和南区的设点数限制，决和南区的设点数限制，决策变量取值策变量取值0 0或或1 1。4.1 4.1 整数规划的数学建模整数规划的数学建模 4.1.1 4.1.1 装箱问题装箱问题 例例4.1 4.1 某厂拟用集装箱托运甲、乙两种货物，每箱某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表的体积、重量、可获利润以及托运所受限制如表4 41 1所示

8、。问两种货物各托运多少箱，可使获得利润为最所示。问两种货物各托运多少箱，可使获得利润为最大？大？表表 4 41 1货物货物体积（米体积（米3 3/ /箱）箱）重量（百公斤重量（百公斤/ /箱）箱） 利润（百元利润（百元/ /箱）箱）甲甲5 52 22020乙乙4 45 51010托运限制托运限制2424米米3 31313百公斤百公斤解：解： 设设 、 分别为甲、乙两种货物的托运箱分别为甲、乙两种货物的托运箱数，则数学模型可以表示为：数，则数学模型可以表示为：其中，目标函数表示追寻最大的利润，约束条件其中，目标函数表示追寻最大的利润，约束条件分别表示装箱的体积和重量限制，决策变量要求分别表示装箱

9、的体积和重量限制，决策变量要求装箱数必须为整数。装箱数必须为整数。1212121212max201054242513,0,zxxxxxxxxxx整 数1x2x 能否采用四舍五入或者去尾法求得整数解？能否采用四舍五入或者去尾法求得整数解？ 以例以例4.14.1的求解为例，先不考虑的求解为例，先不考虑 为整数的条为整数的条件，采用单纯形法求解该问题，得到：件，采用单纯形法求解该问题，得到： 若对若对 采用四舍五入法求解，则有采用四舍五入法求解，则有 ，此解，此解不是可行解不是可行解； 而去尾法得到而去尾法得到 ，目标函数，目标函数 ，该解是否是最优解呢？实际上，当该解是否是最优解呢？实际上，当 时

10、，时， ，表明，表明，去尾法得到的解并非最优解去尾法得到的解并非最优解。 4.2 4.2 整数规划的求解算法整数规划的求解算法12,x x124.8,0,96xxz12,xx125,0 xx124,0 xx80z 124,1xx90z 【例】【例】 设整数规划问题如下设整数规划问题如下 且且为为整整数数0,13651914max21212121xxxxxxxxZ首先不考虑整数约束，得到线性规划问题（一般称为松弛问首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。题）。 0,13651914max21212121xxxxxxxxZ 用图解法求出最优解为：用图解法求出最优解为：x13/2,

11、 x2 = 10/3，且，且有有Z = 29/6现求整数解现求整数解(最优解最优解):如用如用舍入取整法可得到舍入取整法可得到4个点即个点即(1，3),(2，3),(1，4),(2，4)。显然，。显然，它们都不可能是整数规划的它们都不可能是整数规划的最优解。最优解。x1x233(3/2,10/3)其中其中(2,2),(3,1)点的目标函数值点的目标函数值最大，即为最大，即为Z=4。 整数规划问题的求解方法：整数规划问题的求解方法： 分支定界法和割平面法分支定界法和割平面法4.2.14.2.1分支定界算法分支定界算法 下面通过例子说明分支定界方法的算法思想下面通过例子说明分支定界方法的算法思想和

12、步骤。和步骤。例例4.3 4.3 对如下整数规划对如下整数规划1212121212max4090975672070.,0,zxxxxxxs txxxx整数解：先不考虑整数条件，解相应的线性规划，解：先不考虑整数条件，解相应的线性规划，得最优解：得最优解： 。该解不。该解不符合整数条件。符合整数条件。 对其中一个非整数变量解，如对其中一个非整数变量解，如 ，显，显然，若要满足整数条件，必定有然，若要满足整数条件，必定有 于是，对原问题增加两个新约束条件，将原于是，对原问题增加两个新约束条件，将原问题分为两个子问题，即有问题分为两个子问题，即有14.81x 1204.81=1.82356xxz，1

13、154xx或（B B）121212112max4090975672070.4,0zxxxxxxs txx x121212112max4090975672070.5,0zxxxxxxs txx x（A A） 问题（问题（A A）和（）和（B B）的可行域中包含了原整数规）的可行域中包含了原整数规划问题的所有整数可行解，而在划问题的所有整数可行解，而在 中不可中不可能存在整数可行解。能存在整数可行解。145x 分别求解这两个线性规划问题，得到的解是：分别求解这两个线性规划问题，得到的解是： 和和 变量变量 仍不满足整数的条件，对问题（仍不满足整数的条件，对问题（A A），），必有必有 ，将（，将（

14、A A）增加约束条件，得到）增加约束条件，得到 124,2.1,349xxz125,1.57,341xxz1212121212m a x4 09 0975 672 07 0.42,0zxxxxxxs txxxx1212121212m ax4090975672070.43,0zxxxxxxs txxxx2x2232xx或（A1A1）（A2A2） 求解（求解（A1A1），得到），得到 ; ;求解（求解（A2A2），得到），得到 。由于。由于（A2A2）的最优值小于（）的最优值小于（A1A1）的最优值，原问题的最）的最优值，原问题的最优值必大于等于优值必大于等于340340，尽管（，尽管（A2A2）

15、的解仍然不满足）的解仍然不满足整数条件，（整数条件，（A2A2）已无必要继续分解。）已无必要继续分解。124,2,340 xxz121.42,3,327xxz2x22xx2或1125.44,1,308xxz 对（对（B B），）， 不满足整数条件，必有不满足整数条件，必有 ，将这两个约束条件分别加到（，将这两个约束条件分别加到（B B）中，得到（中，得到（B1B1）和（）和（B2B2），求解得到：（），求解得到：（B1B1）的）的最优解为最优解为 ，（，（B2B2）无可行）无可行解。至此，原问题的最优解为解。至此，原问题的最优解为： 上述求解过程称为分支定界算法，求解过程上述求解过程称为分支定

16、界算法，求解过程用图用图4 41 1表示：表示：124,2,340 xxz 无可行解无可行解图41 123564.81,1.82zxx14x 15x 123494,2.1zxx123415,1.57zxx22x 23x 123404,2zxx123271.42,3zxx21x 22x123085.44,1zxx 将要求解的整数规划问题称为问题将要求解的整数规划问题称为问题A A，将与，将与之相应的线性规划问题称为问题之相应的线性规划问题称为问题B B（与问题（与问题A A 相相比较，仅不含有比较，仅不含有“变量为整数变量为整数”的约束条件），的约束条件），B B称为原问题称为原问题A A 的松

17、弛问题。解问题的松弛问题。解问题B B，可能得到，可能得到以下情况之一：以下情况之一： B B 没有可行解，这时没有可行解，这时A A 也没有可行解，则也没有可行解，则停止。停止。 B B 有最优解，并符合问题有最优解，并符合问题A A的整数条件，的整数条件，B B的最优解即为的最优解即为A A的最优解，则停止。的最优解，则停止。 B B 有最优解，并不符合问题有最优解，并不符合问题A A的整数条件，的整数条件，记它的目标函数值为记它的目标函数值为 。 0z 用观察法找问题用观察法找问题A A的一个整数可行解，一的一个整数可行解，一般可取般可取 试探，求试探，求得其目标函数值，并记得其目标函数

18、值，并记 。以。以 表示问题表示问题A A的最优目标函数值；这时有的最优目标函数值；这时有 ，然后按下述步骤进行迭代。然后按下述步骤进行迭代。0,1,jxjn z*z*0zzz 分支过程。在分支过程。在B B 的最优解中任选一个不符的最优解中任选一个不符合整数条件的变量合整数条件的变量 ，若其值为，若其值为 ，以，以 表示小于表示小于 的最大整数，构造两个约束条件的最大整数，构造两个约束条件： 。将这两个约束条件，。将这两个约束条件，分别加入问题分别加入问题B B ，得到后续规划问题，得到后续规划问题 。不考虑整数条件求解这两个后续问题。不考虑整数条件求解这两个后续问题。 定界过程。以每个后续

19、问题为一分支标明求定界过程。以每个后续问题为一分支标明求解的结果，在其他问题解的结果中，找出最优解的结果，在其他问题解的结果中，找出最优目标函数值最大者作为新的上界目标函数值最大者作为新的上界 。从已符合。从已符合整数条件的各分支中，找出目标函数值最大者整数条件的各分支中，找出目标函数值最大者作为新的下界作为新的下界 ，若无可行解，则，若无可行解，则 。jxjbjbjb1jjjjxbxb和12BB和zz0z 步骤步骤1 1：分支定界过程：分支定界过程步骤步骤2 2： 比较与剪支。各分支的最优目标函数中若比较与剪支。各分支的最优目标函数中若有小于有小于 者，则剪掉这支，以后不再考虑者，则剪掉这支

20、，以后不再考虑这个分支。若大于这个分支。若大于 ，且不符合整数条，且不符合整数条件，则重复步骤件，则重复步骤1 1，直到最后得到，直到最后得到 为止，得到最优整数解：为止，得到最优整数解：zz*zz*,1,jxjn。 例：例： 用分枝定界法求解用分枝定界法求解 且且均均取取整整数数,0,255.22108.02.134max21212121xxxxxxxxZ解解: 先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35

21、.7,如下图所示。如下图所示。1010108 . 02 . 121 xx255 . 2221 xx松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABC得得到到两两个个线线性性规规划划及及增增加加约约束束4311 xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.510 x1x2

22、oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max2121212121xxxxxxxxLPxxZ，不不可可行行，得得到到线线性性规规划划，显显然然及及进进行行分分枝枝，增增加加约约束束选选择择目目标标值值最最大大的的分分枝枝7762222 xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，10 x1x2oACLP134可可行行域域是是一一条条线线段段即即，, 40,464255 . 22108 . 02 . 1:21

23、134max121121212121 xxxxxxxxxxLPxxZ：及及，得得线线性性规规划划及及进进行行分分枝枝，增增加加约约束束，选选择择由由于于212211542111121LPLPxxLPZZ 6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z2

24、1=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22无可行解无可行解x27作业：课本P127 T6（2）第三章第三章 案例分析案例分析 1、610人一组，自由组合人一组，自由组合 2、完成课本、完成课本P100，案例，案例3.5.1 3、建立线性问题数学模型并利用、建立线性问题数学模型并利用软件求解软件求解 4、小组为单位上交、小组为单位上交word电子版求电子版求解结果解结果 5、文件中请注明每个人的分工情、文件中请注明每个人的分工情况况 4.2.2割平面方法割平面方法 割平面法的思想是，求解不含整数条件的割平面法的思想

25、是，求解不含整数条件的线性规划，然后不断增加适当的线性约束线性规划，然后不断增加适当的线性约束条件，割掉原可行域中不含整数可行解的条件，割掉原可行域中不含整数可行解的一部分，最终得到一个具有整数坐标的极一部分，最终得到一个具有整数坐标的极点的可行域，而该极点恰好是原整数规划点的可行域，而该极点恰好是原整数规划问题的最优解。问题的最优解。例例4.4 4.4 对如下整数规划对如下整数规划1212121212max1.34,0,zxxxxstxxx xx x为整数下面通过例子求解过程说明割平面法的应用步骤。下面通过例子求解过程说明割平面法的应用步骤。步骤步骤1 1：不考虑整数条件，引入松弛变量不考虑

26、整数条件，引入松弛变量 ，化为标准形式，用单纯形法求解得到：化为标准形式，用单纯形法求解得到： 表表4 42 234,x x1x2x3/43/41 10 0-1/4-1/41/41/47/47/40 01 13/43/41/41/40 00 0-1/2-1/2-1/2-1/2最优解为：最优解为： 。Bxb3x4x1x2x123 / 4,7 / 4xx步骤步骤2 2： 根据单纯形表，可得根据单纯形表，可得 将上式中将上式中-1/4-1/4写成写成整数和非负真分数整数和非负真分数之和的形之和的形式，有式，有 变换成如下形式：变换成如下形式： 该式中，由于该式中，由于 为整数，为整数， 为整数，为整

27、数，必有必有 ，化简得：，化简得：1341/41/43/4xxx13343/41/43/4xxxx13343/43/41/4xxxx13,xx343/ 41/ 4xx343/4 3/41/40 xx3433xx 对对 ，切割掉了非整数最，切割掉了非整数最优解，但是并没有切割掉整数解，因为相应的优解，但是并没有切割掉整数解，因为相应的线性规划任意整数可行解都满足该条件，故称线性规划任意整数可行解都满足该条件，故称之为之为:“:“割平面割平面” ” 。 引入松弛变量，得到引入松弛变量，得到: : 将此约束方程加到表将此约束方程加到表4 42 2中，得到表中，得到表4 43 3：3433xx3453

28、3xxx 表表4 43 3b1x2x3x4x5xBx1x2x5x3/43/41 10 0- -1/41/41/41/40 07/47/40 01 13/43/4 1/41/40 0-3-30 00 0-3-3-1-11 10 00 0- -1/21/2- -1/21/20 0 由表由表4 43 3，可采用，可采用对偶单纯形法对偶单纯形法进行求解，进行求解，得到表得到表4 44 4： 换出基变量的确定规则。换出基变量的确定规则。 一般单纯形方法是以一般单纯形方法是以最大检验数最大检验数对应的非基变量对应的非基变量作为作为换出换出基变量，然后将已得到的基变量的值与基变量，然后将已得到的基变量的值与

29、换入基变量所在的列的正分量相除，以最小比值换入基变量所在的列的正分量相除，以最小比值对应的基变量作为换出基变量。对应的基变量作为换出基变量。 在对偶单纯形求解时，以在对偶单纯形求解时，以基变量的负值中最小基变量的负值中最小的的对应的为对应的为换出换出基变量，将检验数与换出基变量所基变量，将检验数与换出基变量所在行的负分量相除，然后选取最小比值对应的非在行的负分量相除，然后选取最小比值对应的非基变量为换入基变量。基变量为换入基变量。表表4 44 4b1x2x4x5xBx3x1x2x3x1 11 10 00 01/31/31/121/121 10 01 10 00 01/41/41 10 00 0

30、1 1-1-1-1/3-1/30 00 00 0-1/3-1/3-1/6-1/6由表由表4 44 4， ，满足整数，满足整数条件。条件。1231,1,1xxx将上述步骤归纳如下：将上述步骤归纳如下：步骤步骤1 1： 不考虑整数规划中的整数条件，依据单纯形不考虑整数规划中的整数条件，依据单纯形法求解线性规划。法求解线性规划。步骤步骤2 2： 寻求切割方程。若最优解存在但不满足整数寻求切割方程。若最优解存在但不满足整数条件，根据最优单纯形表中最优解为分数值的一条件，根据最优单纯形表中最优解为分数值的一个基变量，写成个基变量，写成 ，其中，其中， 为基变量，为基变量， 为非基变量。将为非基变量。将

31、写成整数部写成整数部分分N N与非负真分数与非负真分数 （ ）之和的形式，即）之和的形式，即 iikkikxaxbixkx,ikiabif01if,iiiikikikbNf aNf 将该式代入得到：将该式代入得到：则有切割方程则有切割方程 。步骤步骤3 3： 将切割方程增加松弛变量，加入最优单纯将切割方程增加松弛变量，加入最优单纯形表进行迭代计算。若所得到的解为非整数，形表进行迭代计算。若所得到的解为非整数，则转到步骤则转到步骤2 2继续迭代，直到找到最优的整数继续迭代，直到找到最优的整数解。解。iikkiiikkkkxNxNffx0iikkkffx. .max21tsxxZ均为整数0,521

32、02321221xxxxxcj1100XBbx1x2x3x4X15/3101/3-1/3X25/20101/200-1/3-1/6以以x1所在的行为源行，得到相应割平面所在的行为源行，得到相应割平面03231-3243xx 加入松弛变量加入松弛变量 用对偶单纯形法求解用对偶单纯形法求解3232-31-543 xxxcj3-1-100XBbx1x2x3x4x5x15/3101/3-1/30 x25/20101/20X5-2/300-1/3-2/3100-1/3-1/60cj3-1-100XBbx1x2x3x4x5x12101/20-1/2x2201-1/403/4X41001/21-3/200-

33、1/40-1/4增加约束条件后增加约束条件后LP问题的最优解（问题的最优解（2,2,0,1,0），），因此原整数规划问题的最优解为（因此原整数规划问题的最优解为（2,2），其最优），其最优值为值为Z=44.2.3 0-14.2.3 0-1规划及隐枚举法规划及隐枚举法 在实际建模过程中，经常遇到要求模型解决在实际建模过程中，经常遇到要求模型解决“是、否是、否”或者或者“有、无有、无”等问题，这类问题一等问题，这类问题一般可以借助引入数值为般可以借助引入数值为0 0或者或者1 1的决策变量加以解的决策变量加以解决，例决，例4.24.2就是此类问题，这类问题被称为就是此类问题，这类问题被称为0-10

34、-1整整数规划。被引入的数规划。被引入的0-10-1决策变量一般定义为：决策变量一般定义为： 下面举例说明求解下面举例说明求解0-10-1整数规划的隐枚举法。整数规划的隐枚举法。1,0iixi执行决策“是”，“有”，不执行决策，“否”，“无”例例4.5 4.5 有有0-10-1整数规划问题：整数规划问题：1251231231213123max3252244.346,01zxxxxxxxxxstxxxxx x x或解：采用试探的方法找到一个可行解，容易看出解：采用试探的方法找到一个可行解，容易看出 符合约束条件，目标函数符合约束条件，目标函数值值 。 对于极大化问题，应有对于极大化问题，应有 ，

35、于是增加一，于是增加一个约束条件：个约束条件： 新增加的约束条件称为过滤条件。原问题的线新增加的约束条件称为过滤条件。原问题的线性约束条件就变成性约束条件就变成5 5个，个，3 3个变量共有个变量共有 个解，个解，原来原来4 4个约束条件共需个约束条件共需3232次运算，增加了过滤条件次运算，增加了过滤条件后，将后，将5 5个约束条件按个约束条件按（4 4）的顺序排好（表）的顺序排好（表4 45 5），），123()(1,0,0)x ,x ,x3z 3z 1233253xxx328点点条件条件满足条件满足条件? ?是是()()否否( () )z z值值(0(0，0 0，0)0)0 0(0(0，

36、0 0，1)1)5 5-1-11 10 01 15 5(0(0，1 1，0)0) -2-2(0(0，1 1，1)1)3 31 15 5(1(1，0 0，0)0)3 31 11 11 10 03 3(1(1，0 0，1)1)8 80 02 21 11 18 8(1(1，1 1，0)0)1 1(1(1，1 1，1)1)6 62 26 6 对每个解，依次代入约束条件左侧，求出数对每个解，依次代入约束条件左侧，求出数值，看是否满足不等式条件，如某一条件不适合，值，看是否满足不等式条件，如某一条件不适合，同行以下条件就不必再检查，因而可以减少运算同行以下条件就不必再检查，因而可以减少运算次数。于是求得最

37、优解次数。于是求得最优解 在计算过程中，若遇到在计算过程中，若遇到z z值已超过条件值已超过条件右右边的值，应改变条件边的值，应改变条件，使右边为迄今为止的最，使右边为迄今为止的最大大z z，继续检查。例如，当检查点（，继续检查。例如，当检查点（0 0，0 0，1 1）时）时因因z=53z=53，所以应将条件，所以应将条件换成换成 这种对过滤条件的改进，可以减少计算量。这种对过滤条件的改进，可以减少计算量。1233255xxx123(,)(0,1,0)xxxmax8z 用隐枚举法求下列用隐枚举法求下列01整数规划的最优解整数规划的最优解3 , 2 , 110)3(42)2(253) 1 (32

38、326max321321321321jxxxxxxxxxxxxxZj或【解】容易求得【解】容易求得X(1,0,0)是一可行解，是一可行解，Z06。加一个约束。加一个约束6326321xxx (0)由于由于3个变量每个变量取个变量每个变量取0或或1，共有，共有8种组合，用列表的方法检验每种组合，用列表的方法检验每种组合解是否可行解，满足约束打上记号种组合解是否可行解，满足约束打上记号“”，不满足约束打上记，不满足约束打上记号号“ ”，计算如表，计算如表53所示。所示。表53变量组合变量组合约束约束(0)约束约束(1)约束约束(2)约束约束(3)Z（0，0，0） （0，0，1） （0，1，0） （

39、0，1，1） （1，0，0）（1，0，1）（1，1，0） （1，1，1） 由表由表53知，知，X（1，0，1）是最优解，最优值）是最优解，最优值Z9。69第四章第四章 案例分析案例分析 1、610人一组，自由组合人一组，自由组合 2、完成课本、完成课本P122，案例，案例4.3.1 3、建立线性问题数学模型并利用、建立线性问题数学模型并利用软件求解软件求解 4、小组为单位上交、小组为单位上交word电子版求电子版求解结果解结果 5、文件中请注明每个人的分工情、文件中请注明每个人的分工情况况 作业作业 教材教材P127 第第6题题(2)。 6、(2) 解：求相应的线性规划（解：求相应的线性规划（

40、LP） 得（得（LP）的最优解）的最优解212maxxxz0,212605.21212121xxxxxxxxts75. 7,25. 2,75. 221zxx 首先注意其中一个非整数变量的解，如首先注意其中一个非整数变量的解，如 ，在松弛问题中的解，于是原问题增加两个在松弛问题中的解，于是原问题增加两个约束条件约束条件2x22x32x将两个约束分别并入原问题的松弛问题（将两个约束分别并入原问题的松弛问题（LP）中，）中，形成两个分支，即后继问题（形成两个分支，即后继问题（LP1）和）和(LP2)，这并，这并不影响原问题的可行域。不影响原问题的可行域。 解（解（LP1），得最优解为），得最优解为3

41、/23, 2, 6/1721zxx再解（再解（LP2），无最优解。），无最优解。 继续对（继续对（LP1）进行分解。对（）进行分解。对（LP1）增加）增加两个约束条件两个约束条件21x31x将两个约束分别并入（将两个约束分别并入（LP1）中，形成两个分）中，形成两个分支，即后继问题（支，即后继问题（LP11）和）和(LP12)，这并不影，这并不影响（响（LP1）的可行域。）的可行域。解（解（LP11），得最优解为），得最优解为6, 2, 221zxx再解（再解（LP12），得最优解为。），得最优解为。5 . 7, 5 . 1, 321zxx 继续对（继续对（LP12）进行分解。对（）进行分解。

42、对（LP12）增）增加两个约束条件加两个约束条件12x22x 将两个约束分别并入（将两个约束分别并入（LP12）中，形成两）中，形成两个分支，即后继问题（个分支，即后继问题（LP121）和）和（LP122），这并不影响（），这并不影响（LP12）的可行）的可行域。解（域。解（LP121），得最优解为），得最优解为7/22, 1, 6/1921zxx再解（再解（LP122），无最优解。），无最优解。继续对（继续对（LP121）进行分解。对（）进行分解。对（LP121）增加两个约）增加两个约束条件束条件31x41x将两个约束分别并入（将两个约束分别并入（LP121）中，形成两个分支，即后）中，形成

43、两个分支，即后继问题（继问题（LP1211）和（）和（LP1212）。）。解（解（LP1211），得最优解为。），得最优解为。7, 1, 321zxx再解（再解（LP1212），无最优解。），无最优解。因此得原问题的最优解为因此得原问题的最优解为 7, 1, 321zxx 在生活中经常会遇到这样的问题：某单位需完在生活中经常会遇到这样的问题：某单位需完成成 项任务，恰好有项任务，恰好有 个人可承担这些任务。个人可承担这些任务。每每个人只做一项工作，同时，每项工作只由一个人完成。个人只做一项工作，同时，每项工作只由一个人完成。由于每人的专长不同，各人完成任务所需的时间由于每人的专长不同，各人完成

44、任务所需的时间也不同。问题是，应指派哪个人去完成哪项任务，也不同。问题是，应指派哪个人去完成哪项任务，使完成项任务的总时间最小（或者使完成项任务的总时间最小（或者总效率最高总效率最高）？）？这类问题称为指派问题或分配问题（这类问题称为指派问题或分配问题（assignment problem）。）。 nn4.2.4 4.2.4 指派问题及匈牙利法指派问题及匈牙利法例例4.64.6有一份中文说明书，需译成英、日、有一份中文说明书，需译成英、日、德、俄四种文字，分别记作德、俄四种文字，分别记作E E、J J、G G、R R。现。现有甲乙丙丁四人。他们将中文说明书翻译成有甲乙丙丁四人。他们将中文说明书

45、翻译成不同语种说明书所需时间如表不同语种说明书所需时间如表4 46 6所示。问，所示。问，若要求每一翻译任务只分配给一人去完成，若要求每一翻译任务只分配给一人去完成，每一个人只接受一项任务，应指派何人去完每一个人只接受一项任务，应指派何人去完成何工作，使所需时间最少？成何工作，使所需时间最少？表表4 46 6 任务任务人员人员E EJ JG GR R甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811119 9一般地，称表一般地，称表4 46 6为效率矩阵或者系数矩阵，为效率矩阵或者系数矩阵，其元素其元素 表示指派第表示指派第

46、 个人去完成第个人去完成第 项任务所需的时间，或者称项任务所需的时间，或者称为完成任务的工作效率（或时间、成本等）。为完成任务的工作效率（或时间、成本等）。0( ,1,2, )ijci jnij解：引入0-1变量 ， 由此可得到指派问题的数学模型：ijx1,ijijxij指 派 第 人 去 完 成 第 项 任 务0 ,不 指 派 第 人 去 完 成 第 项 任 务m in1,1, 2,. .1,1, 2,10ijijijijiijjijzc xxjns txinx 或 目标函数表示目标函数表示 个人完成任务所需的时间最个人完成任务所需的时间最少（或效率最高）；第一个约束条件说明第少（或效率最高

47、）；第一个约束条件说明第 项任务只能由项任务只能由1 1人去完成；第二个约束条件说明人去完成；第二个约束条件说明第第 人只能完成人只能完成1 1项任务。项任务。易得，上述问题可行解易得，上述问题可行解 可写成表格或矩阵可写成表格或矩阵形式，如例形式，如例4.64.6的一个可行解矩阵是的一个可行解矩阵是njiijx0100001010000001ijx（） 可以看出，解矩阵可以看出，解矩阵 是各行和各列只能是各行和各列只能有一个元素是有一个元素是1 1，其他元素是，其他元素是0 0的的n n 阶方阵。阶方阵。 回顾运输问题的数学模型，运输问题中若回顾运输问题的数学模型，运输问题中若产量和销量分别

48、等于产量和销量分别等于1 1，实际上所得到的数学模，实际上所得到的数学模型与指派问题相同，也即指派问题是运输问题型与指派问题相同，也即指派问题是运输问题的特例，因而可以用运输问题的表上作业法求的特例，因而可以用运输问题的表上作业法求解。另外，指派问题也是解。另外，指派问题也是0 01 1规划的特例。规划的特例。 本节利用指派问题的特点介绍一种更为简本节利用指派问题的特点介绍一种更为简便的算法。便的算法。ijx（） 指派问题的最优解有这样的性质：若从系数指派问题的最优解有这样的性质：若从系数矩阵矩阵 的某一行（列）各元素中分别减去该的某一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵行

49、（列）的最小元素，得到新矩阵 ，那么，那么以以 为系数矩阵求得的最优解和用原系数矩为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。阵求得的最优解相同。 以例以例4.64.6来理解上述性质，对甲来说，只能来理解上述性质，对甲来说，只能完成一项任务，若其无论完成哪项任务都减少相完成一项任务，若其无论完成哪项任务都减少相同的时间，这种时间变动并不改变甲在四项任务同的时间，这种时间变动并不改变甲在四项任务中的最佳选择；若完成某项任务的四个人都减少中的最佳选择；若完成某项任务的四个人都减少相同的时间，同样，这种时间的节省并不改变任相同的时间，同样，这种时间的节省并不改变任务对完成人的最佳选择。务对

50、完成人的最佳选择。 ijc（）ijb（）ijb（） 利用这个性质，可使原系数矩阵变换为含利用这个性质，可使原系数矩阵变换为含有很多有很多0 0元素的新系数矩阵，而最优解保持不变。元素的新系数矩阵，而最优解保持不变。在系数矩阵在系数矩阵 中，一般称位于不同行不同列中，一般称位于不同行不同列的的0 0元素为独立的元素为独立的0 0元素。若能在系数矩阵元素。若能在系数矩阵 中找出个独立的中找出个独立的0 0元素，令解矩阵元素，令解矩阵 中对应中对应这个独立的这个独立的0 0元素的元素取值为元素的元素取值为1 1，其他元素取，其他元素取值为值为0 0，则将其代入目标函数中得到的，则将其代入目标函数中得

51、到的 ，它一定是最小，这就是以它一定是最小，这就是以 为系数矩阵的指为系数矩阵的指派问题的最优解，也就得到了原问题的最优解。派问题的最优解，也就得到了原问题的最优解。ijb（）ijb（ ）ijb（）ijx（）0bz 1955年库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.Konig）一个关于矩阵中0元素的定理，提出了指派问题的解法，称为匈牙利法。该定理证明了以下结论：系数矩阵中独立元素0元素的最多个数等于能覆盖所有0元素的最小直线数。下面用例4.6来说明该方法的应用步骤。第一步：第一步：使指派问题的系数矩阵经变换，在各行使指派问题的系数矩阵经变换，在各行各列中都出现各列中都出现0 0元素

52、。元素。 （1 1）从系数矩阵的每行元素减去该行的最小元素； （2 2）再从所得系数矩阵的每列元素中减去该列的最小元素。min2 15 134 20 13 11 20 13 7 0104 14 15 460 10 11606 9( )( )9 14 16 13 90574053 278119 70142010 042minijijcb例例4.64.6的计算结果为：的计算结果为：第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵（ ）中的元素为1，其余为0，这就得

53、到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找，常用的步骤为：（1 1）从只有一个0元素的行（列）开始，给这个0元素加圈，记作。这表示对这行所代表的人，只有一种任务可指派。然后划去所在列（行）的其他0元素，记作 。这表示这列所代表的任务已指派完，不必再考虑别人。ijx（2 2）给只有一个0元素列（行）的0元素加圈，记作；然后划去所在行的0元素，记作 。（3 3）反复进行（1），（2）两步，直到所有0元 素都被圈出和划掉为止。（4 4）若仍有没有画圈的0元素，且同行（列）的0元素至少有两个（表示对这个可以从两项任务中指派其一）。则从剩有0元素最少

54、的行（列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的）。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5 5）若元素的数目 等于矩阵的阶数 ，那么指派问题的最优解已得到。若 ，则转入第三步。 按步骤（1），先给 加圈，然后给 加圈，划掉 ；按步骤（2），给 加圈，划掉 ，最后给 加圈，得到mnmn22b31b4111, bb43b44b14b 由于 ，所以得最优解为 （ ） 这表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文，所需总时间最少 （小时）。4 nmijx010000010

55、01010000minijijijbxbz28min14432231ccccxczijijij例例4.7 4.7 求表47所示效率矩阵的指派问题的最小解。表47 任务人员ABCDE甲127979乙89666丙71712149丁15146610戊4107109解：解：按上述第一步，将这系数矩阵进行变换。 56360400892751000003220205467679107104106614159141217766698979712按第二步，得到： 这里的个数 ，而 ；解题没有完成，应按以下步骤继续进行。 4m5n第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0 0元素，以确定元素，以

56、确定该系数矩阵中能找到最多的独立元素数。为此该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：按以下步骤进行：（1 1）对没有）对没有的行打的行打号；号；（2 2）对已打）对已打号的行中所有含号的行中所有含 元素的列打元素的列打号；号；（3 3）再对打有）再对打有号的列中含号的列中含元素的行打元素的行打号；号；（4 4）重复（）重复（2 2），（），（3 3）直到得不出新的打）直到得不出新的打号号的行、列为止；的行、列为止；（5 5）对没有打）对没有打号的行画一横线，有打号的行画一横线，有打号的号的列画一纵线，这就得到覆盖所有列画一纵线，这就得到覆盖所有0 0元素的最少直元素的最少直线数

57、。线数。 令这直线数为令这直线数为 。若。若 ，说明必须再，说明必须再变换当前的系数矩阵，才能找到变换当前的系数矩阵，才能找到 个独立的个独立的0 0元素，为此转第四步：若元素，为此转第四步：若 ，而，而 ，应回到第二步（应回到第二步（4 4），另行试探。），另行试探。 llnnnl mn 在例在例4.74.7中，对矩阵按以下次序进行：中，对矩阵按以下次序进行： 先在第五行旁打先在第五行旁打号，接着在第一列打号，接着在第一列打号，号，接着在第三列旁打接着在第三列旁打号。经检查不能再打号。经检查不能再打号了。号了。对没有打对没有打行，画一直线以覆盖行，画一直线以覆盖0 0元素，已打元素，已打的列

58、画一直线以覆盖的列画一直线以覆盖0 0元素。得元素。得 由此可见由此可见 。所以应继续对矩阵。所以应继续对矩阵进行变换，转第四步。进行变换，转第四步。 第四步：该步进行矩阵变换的目的是增加第四步：该步进行矩阵变换的目的是增加0 0元素。在没有被直线覆盖的部分中找出最小元素。元素。在没有被直线覆盖的部分中找出最小元素。然后在打然后在打行各元素中都减去这最小元素，而在行各元素中都减去这最小元素，而在打打列的各元素都加上这最小元素，以保证原来列的各元素都加上这最小元素，以保证原来0 0元素不变。这样得到新系数矩阵（它的最优解元素不变。这样得到新系数矩阵（它的最优解和原问题相同）。若得到个独立的和原问

59、题相同）。若得到个独立的0 0元素，则已元素，则已得最优解，否则回到第三步重复进行。得最优解，否则回到第三步重复进行。 4ln34140400811053800003420207 它具有它具有 个独立的个独立的0 0元素。这就得到了最优元素。这就得到了最优解，相应的解矩阵为解，相应的解矩阵为：n 在没有被覆盖部分（第在没有被覆盖部分（第3 3、5 5行）中找出最小元行）中找出最小元素为素为2 2，然后在第，然后在第3 3、5 5行各元素分别减行各元素分别减2 2，给第一，给第一列各元素加列各元素加2 2，得到新矩阵。按第二步，找出所有，得到新矩阵。按第二步，找出所有独立的独立的0 0元素，得到

60、：元素，得到：0000100100100000100000010 由解矩阵得最优指派方案：甲由解矩阵得最优指派方案：甲BB，乙，乙DD，丙，丙EE，丁丁CC，戊，戊AA。本例还可以得到另一最优指派方案：。本例还可以得到另一最优指派方案：甲甲BB，乙，乙CC，丙，丙EE，丁，丁DD，戊，戊AA。所需总时间。所需总时间为为 。 当指派问题的系数矩阵，经过变换得到了同行和同当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上列中都有两个或两个以上0 0元素时，这时可以任选一行元素时，这时可以任选一行（列）中某一个（列）中某一个0 0元素，再划去同行（列）的其他元素，再划去同行（列）的其