运筹学第五章整数规划

1、整数规划整数规划v整数规划的数学模型及解的特点v解纯整数规划的割平面法*v分支定界法v0-1型整数规划*v指派问题例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见下表.问每集装箱中两种货物各装多少箱,可使所获利润最大?1 整 数 规 划的数学模型一、问题的提出货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413表 3.1货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413解 设 分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题 .其数学模型为:21,xx211020maxxxZ整数, 0,13

2、522445.212121xxxxxxts 在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等.如果所得的解中决策变量为分数或小数则不符合实际问题的要求. 且部分或全部为整数或 n)1.2(j 0)2 .1( .)min(max11jnjijijnjjjxmibxastxcZZ二、整数规划问题的数学模型 对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题. 整数规划简称为IP问题.这里主要讨论的是整数线性规划问题,简称为ILP问题

3、. 形线性规划混合整数线性规划纯整数线性规划整数线性规划问题10(pure integer linear programming)(mixed integer linear programming)(zero-one integer linear programming)若不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题（slack problem）且部分或全部为整数或 n)1.2(j 0)2.1( .)min(max11jnjijijnjjjxmibxastxcZZ整数线性规划数学模型的一般形式 n)1.2(j 0)2.1( .)min(max11jnji

4、jijnjjjxmibxastxcZZ或该整数规划问题的松弛问题三、整数规划问题解的特点对于整数线性规划问题,为了得到整数解,初看起来,似乎只要先不管整数要求,而求线性规划的解,然后将求得的非整数最优解“舍零取整”就可以了.但实际上,这个想法却常常行不通,有时“舍零取整”后的整数解根本就不是可行解,有的虽然为可行解,却不是最优解 .例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见下表.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413解 设 分别为甲、乙两种货物的托运箱数.则这是

5、一个纯整数规划问题 .其数学模型为:21,xx211020maxxxZ整数, 0,13522445.212121xxxxxxts（1）若暂且不考虑 取整数这一条件.则(1)就变为下列线性规划 : 21,xx211020maxxxZ0,13522445.212121xxxxxxts（2）我们将式(2)称为(1)的松弛问题.解(2)得到最优解:, 8 . 4*1x, 0*2x.96*Z（3）但它不满足(1)的整数要求.因此它不是(1)的最优解,若把解(3)“舍零取整”,如取X1=(5,0)T,但它不是式(1)的可行解.因为它不满足 (1) 中的约束条件。若取X2=(4,0)T，X2是 (1) 的可

6、行解, 但它却不是(1) 的最优解, 因为当X2=(4,0)T 时,Z2 = 80, 但当X3 = (4,1)T 时,Z3 = 90 Z2。 即伴随规划的最优解通过 “ 舍零取整 ” 得到的X1,X2 都不是 (1) 的最优解 .因此通过松弛问题最优解的 “ 舍零取 整 ” 的办法 , 一般得不到原整数规划问题的最优解 .对上面的问题，我们从几何的角度来观察：若松弛问题(2)的可行域 K 是有界的,则原整数规划(1)的可行域 K 0应是K中有限个格点(整数点）的集合.见图1, 图中“* 为整数点(格点).图1 中四边形 OABC 是松弛问题(2)的可行域.它的最优解为 C 点(4.8, 0)。

7、而 (1) 的可行域为k0 = (0,0),(0,1), (0,2), (1,0),(1, l),(1,2), (2,0), (2,1),(3,0), (3,1),(4,0),(4, l) . 将C点“舍零取整”后得到的X1=(5.0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点左侧（4，1）。112348 . 421x2xACBO当然, 我们也会想到能否用“穷举法”来求解整数规划.如(1)问题,将 K0 中所有整数点的目标函数值都计算出来,然后逐一比较找出最优解.这种方法对变量所能取的整数值个数较少时,勉强可以应用.如本例 可取 0,1,2,3,4共5

8、个数值。而 只能取0,1,2共三个数值,因此其组合最多为15个(其中有不可行的点).1x2x但对大型问题,这种组合数的个数可能大得惊人! 如在指派问题中,有n 项任务指派n个人去完成,不同的指派方案共有n! 种 .当 n=20 时 ,这个数超过21018. 如果用穷举法每一个方案都计算一遍 , 就是用每秒百万次的计算机,也要几万年 . 显然 “穷举法” 并不是一种普遍有效的方法因此研究求解整数规划的一般方法是有实际意义的. 穷举法舍零取整求解整数规划整数规划解的特点整数线性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别。 松弛问题作为一个线性规划问题，其可行解的集合

9、是一个凸集，任意两个可行解的凸组合仍为可行解。整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集，任意两个可行解凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解是其松弛问题的可行解的子集，所以，其松弛问题的最优解目标函数值是整数规划问题目标函数值的上界。 在一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然也不是整数规划的最优解。112348 . 421x2xACBO但松弛问题的最优解恰好满足变量的整数约束条件，那么它必然同时是整数规划问题和其松弛问题的最优解。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划

10、的方法有： l 分支定界法和割平面法；分支定界法和割平面法；l 对于特别的对于特别的01规划问题采用隐枚举法和匈牙利法。规划问题采用隐枚举法和匈牙利法。自20世纪60年代以来, 已发展了一些常用的解整数规划的算法,如各种类型的割平面法、分枝定界法、解 0-1 规划的隐枚举法、分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法,也取得了较好的效果 .背景11max1,2.01,2.1,2,.njjjnijjijjjZc xa xbims txjnxjn取整数2 解纯整数规划的割平面法考虑纯整数规划问题纯整数规划的松弛问题是一个线性规划问题，可用单纯形法求解。在松

11、弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合，则m个约束方程可示为：QibxaxijKjiji5.4式而对应的最优解X*=(x1*,x2*, ,xn*)，其中KjQjbxjj0*若各 皆为整数，则X* 满足整数约束，因而就是纯整数规划的最优解；若 不全为整数，则 X* 不满足整数约束，因而就不是纯整数规划的可行解，自然也不是该整数规划的最优解。)(Qjbj)(Qjbj割平面法的基本思想：用割平面法(cutting plane approach)解整数规划时，若其松弛问题的最优解不满足整数约束，则从X*的非整分量中选取一个，用以构造一个线性约束条件，将其加入

12、原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数最优解为止。为最终获得整数最优解，每次增加的线性约束条件应当具备两个基本性质： 已获得的不符合整数要求的松弛问题最优解不满足该线性约束条件，从而不可能在以后的解中再出现。 凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次形成的松弛问题（线性规划）可行域中。我们应该怎样构造新的约束条件？为此，若 不是整数，在（5.4）中对应的约束方程为QibxaxijKjjii00)(00Qibi其中 按假设不是整数； 可能是整数，也可能不是整数。 0ib)(0Kja

13、ji0ibjia010,)( 10,000000000000ijiiiijijijijijijijifbNfNbKjfaNfNa其中其中5.6式5.7式5.8式分解 和 成两部分。一部分是不超过该数的最大整数，另一部分是余下的小数即将（5.7）和（5.8）式代入（5.6）式，移项以后得：KjKjjjiiijjiixffNxNx000005.9式对5.9式分别讨论当前解（非整数解）和可行域中整数解的情况：对于当前解5.9式右端有1000Kjjjiixff对于整数解5.9式左端表明 为整数，又因为 本身不能 1，故Kjjjiixff00Kjjjiixff00000Kjjjiixff由此我们以 （5

14、.10式）作为标尺来，将当前不满足整数约束的最优解去掉，而完全保留了原整数规划问题的可行解。000Kjjjiixff 综上所述，线性约束条件(5.10)式具备上述的两个性质。将其与原整数规划的松弛问题合并，构成一个新的线性规划。 记R为原松弛问题可行域，R为新的线性规划可行域。从几何意义上看，(5.10)式实际上对R做了一次“切割”，在留下的R 中，保留了整数规划的所有可行解，但不符合整数要求的X*被“切割”掉了。随着“切割”过程的不断继续，整数规划最优解最终有机会成为某个线性规划可行域的顶点，作为该线性规划的最优解而被解得。 割平面法在1958年由高莫瑞（R.E.Gomory）首先提出，故又

15、称Gomory割平面法。在割平面法中，每次增加得用于“切割”的线性约束称为割平面约束或Gomory约束. 构造割平面约束的方法很多，但（5.10）式是最常用的一种，它可以从相应线性规划的最终单纯形表中直接产生。实际解题时，经验表明若从最终单纯行表中选择具有最大分数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数例：用割平面法求解整数规划问题 且为整数且为整数0,023623 max2121212xxxxxxxZ解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201j010

16、0Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4j00-1/4 -1/4割平面约束：34111442xx加入割平面约束后得到的新的线性规划问题为：0,214141023623 max543215434213212xxxxxxxxxxxxxxxZ我们可用使用单纯行法从头开始解这个线性规划问题。但更简便的方法是使用对偶单纯形法：将生成的割平面条件加入松弛变量，然后加到表中21414143xx割平面约束：214141543xxxCj01000CBXBbx1x2x3x4x50 x11101/6-1/601x23/2011/41/400 x5-1/200-

17、1/4-1/41j00-1/4-1/40CBXBbx1x2x3x4x50 x12/3100-1/32/31x21010010 x320011-4j0000-1将 x3=6-3x1-2x2 , x4=3x1-2x2 ,带入 中，得到等价的割平面条件： x21 见下图。21414143 xxx1x233第一个割平面第一个割平面 此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：32323254xx将生成的割平面条件加入松弛变量，然后加到表中：323232654xxxCBXBbx1x2x3x4x5x60 x12/3100-1/32/301x210100100

18、 x320011-400 x6-2/3000-2/3-2/31j-10000-10CBXBbx1x2x3x4X5x60 x10100-1011x20010-103/20 x3600150-60 x5100011-3/2j000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这也是原问题的最优解。 32323254xx等价的约束割平面条件为x1 x2 x1x233第一个割平面第一个割平面第二个割平面第二个

19、割平面3 分枝定界法v在20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝定界法.由于该方法灵活且便于用计算机求解,所以目前已成为解整数规划的重要方法之一。v适用范围：分枝定界法既可用来解纯整数规划,也可用来解混合整数规划.分枝定界法由来： 混合整数规划问题一般有无限多个可行解。即使是纯整数规划问题，随着问题规模的扩大，其可行解的数目也将急剧增加。因此通过枚举全部可行解，并从中筛选出最优解的算法无实际应用价值。分枝定界法（branch and bound）是一种隐枚举或部分枚举法，是在枚举法基础上的改进。分枝定界法的关键是分枝和定界。分枝定界法的基本思想：( 分枝和定界的思

20、想) 若整数规划的松弛问题的最优解不符合整数要求，假设 不符合整数要求， 是不超过 的最大整数，则构造两个约束条件 。分别将其并入上述松弛问题中，从而形成两个分枝，即两个后续问题。 ibibib1iiiibxbx和这就是所谓分枝。 两个后续问题的可行域中包含原整数规划问题的所有可行解。而在原松弛问题可行域中，满足的一部分区域在以后的求解过程中被遗弃了，让而它不包含整数规划的任何可行解。根据需要，各后续问题可用类似地产生自己的分枝，即自己的后续问题。 1iiibxb“分枝”为整数规划最优解的出现创造了条件*(4,4)35XZ*(5,3)20XZ什么是定界： 所谓“定界”，是在分枝过程中，若某个后

21、续问题的最优解恰巧获得整数规划问题的一个可行解（即其解满足整数约束），那么，它的目标函数值就是一个“界限”，可作为衡量处理其他分枝的一个依据。 因为整数规划问题的可行解集是其松弛问题的可行解集的一个子集，所以其松弛问题的最优解目标函数值是原整数规划问题的上界。所以，对于那些相应松弛问题最优解的目标函数值比上述“界限”值差的后续问题，就可以剔除而不再考虑。 当然，如果在以后的分枝过程中出现了更好的“界限”，则以它来取代原来的界限，这样可以提高定界的效果。“定界”则可用提高搜索的效率*(4,4)35XZ*(5,3.17)20XZ“分枝”为整数规划最优解的出现创造了条件，而“定界”则可用提高搜索的效

22、率。下面，通过例子来阐明分枝定界法的基本思想和一般步骤:例 求解整数规划问题1212121,212m ax57724843218. .0,Zxxxxxxs tx xxx为 整 数解：去掉整数要求，得其相应得线性规划（在分枝定界法中，将此记为B，称其为原整数规划A的松弛问题）：1212121,2m ax5772484.32180Zxxxxs txxx x用任一种方法解问题B得最优解和最优值为：x1=4.55, x2=2.17, Z=37.97B的可行解集记为R0,如图所示：A(4.55,2.17)Y 轴612943上面B的最优解不满足整数要求，即不是整数规划的最优解。为寻求原整数规划的最优解，我

23、们把B划分为两个子问题（分枝）。 任选一个不满足整数约束的变量，这里我们取x1构造两个约束条件：在B中分别增加上述约束条件，得到B的两个子问题：5411xx和04182384327.75max2,11212121xxxxxxxtsxxZ05182384327.75max2,11212121xxxxxxxtsxxZ问题问题x1=4, x2=2.33, Z= 36.33x1=5, x2=1.5, Z= 35.5此时，B的可行解被分成了三个部分，即问题的可行解R1, 问题的可行解R2，以及不含整数可行解的4x15的部分Y 轴6129434 5LP1x1=4, x2=2.33Z(1) 36.33LPx

24、1=4.55, x2=2.17Z(0) 37.97LP2x1=5, x2=1.5Z(2) 35.5x14x15整个求解过程问题B问题问题由于问题和问题的最优解仍不满足整数要求，则把和继续进行类似的划分。 由于的最优值较大，则其包含原整数规划最优解的可能形更大些，因此先分解。在中分别增加约束条件得到的两个子问题和。3222xx和04182384327.75max2,11212121xxxxxxxtsxxZ问题在中分别增加 两个约束，得到的两个子问题和3222xx和024182384327.75max2,121212121xxxxxxxxtsxxZ034182384327.75max2,12121

25、2121xxxxxxxxtsxxZ问题问题x1=4, x2=2, Z=34x1=1.71, x2=3, Z=29.57Y 轴6129434 52此时，问题1的可行域被分成三部分，即的可行集R3, 的可行解集R4，以及不含整数可行解的2x2 34，即的可行解集中还有可能含有原整数规划的最优解（比的最优解目标函数值大的整数解）。 2122xx和因此需要考察问题，分别增加约束条件得到问题的两个子问题和05182384327.75max2,11212121xxxxxxxtsxxZ问题015182384327.75max2,121212121xxxxxxxxtsxxZ025182384327.75max

26、2,121212121xxxxxxxxtsxxZ问题问题引入约束2122xx和x1=5.33, x2=1,Z=33.67无可行解问题的可行域R5问题无可行解此时，问题的可行域被分成两部分部分，即的可行集R5,和不含整数可行解的1x2所有分枝末梢的Z值，则得最优解。否则， 取Z值最大的非整数解，继续分解，Go to 3iixb1iijixbxb 和LP1x1=4, x2=2.33Z(1) 36.33LPx1=4.55, x2=2.17Z(0) 37.97LP2x1=5, x2=1.5Z(2) 35.5x14x15问题问题x22x13x21x22LP3x1=4, x2=2Z(3) 34LP4x1=

27、1.71, x2=3Z(4) 29.57LP5x1=5.33, x2=1Z(5) 33.67LP6无可行解无可行解练习例：用分枝定界法求解整数规划问题（可用图解法求解）且且为为整整数数0,143292)(23max21212121xxxxxxIPxxZ树形图如下：树形图如下：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) 14x22x23x13x143 0-1型整数规划一、 0-1变量及其应用

28、若变量只能取0或1，则称其为0-1变量。 0-1变量作为逻辑变量(logical variable),常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。例如 01xP当决策取方案P时当决策不取方案P时（即取 时）01jx若Ej选择Aj若Ej选择jAJ=1,2,n那么，向量(x1,x2,xn)就描述了问题的特定状态或方案即：TnnTTnnTTnnTTnnTTnAAAAAAAAAAAAAAAAxxx),.,(,)0 , 0,.0 , 0(),.,(,)0 , 0,.0 , 1 (),.,(,)0 , 1,.1 , 1 (),.,(,) 1 , 1,.1 , 1 (),.,(121

29、12112121211若选择若选择若选择若选择当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述。一般地，设问题有有限项要素E1,E2,En,其中每项Ej有两种选择Aj和 ，则可令jA投资场所选择问题某城市拟在其东、西、南三个区域设立邮局，各地区都由几个具体的地点可供选择。要求不超过总投资100万元的条件下，建立盈利最大化0-1规划。地区东区西区南区约束地点A1 A2A3 A4 A5A6 A7投资B1 B2B3 B4 B5B6 B7100万元盈利C1 C2C3 C4 C5C6 C7选点数121分析：令xj(j1,2.7)为0-1变量二、 0-1 整数规划举例其数学模型为：)

30、.2, 1(10121100.max76543217171njxxxxxxxxxBtsxCZjiiiiii或在应用中，有时会遇到变量可以取多个整数值的问题。这时，利用0-1变量是二进值变量（binary variable）的性质，可以用一组0-1变量来取代该变量。例如，变量x可取09之间的任意整数时，可令9222233221100 xxxxx其中x0,x1,x2,x3皆为01变量0-1变量不仅广泛应用于科学技术问题，在经济管理问题中也有十分重要的应用1互斥问题2 固定费用问题3 工件排序问题 含有相互排斥的约束条件的问题假设工序B的每周工时约束条件为 现在假设工序B还有一种新的加工方式，相应的

31、每周工时约束变成: 如果工序B只能从两种加工方式中选择一种，那么（1）式和（2）式就成为两个相互排斥的约束条件。为了统一在一个问题中，就需要 引入01变量 ）（ 11505 . 03 . 021xx）（21205 . 02 . 021xx102y101y工序B采用原加工方式工序B不采用原加工方式工序B采用新加工方式工序B不采用新加工方式于是，通过引入0-1变量，可以将相互排斥的约束条件(1)和(2)统一起来：）（）（）（5141204 . 02 . 031505 . 03 . 02122211121yyyMxxyMxx其中M1和M2都是充分大的数。由于（5）式决定了y1和y2中必定有一个是1，

32、另一个是0（互斥条件）。若y1=1，而y2=0，即采用新的加工方式。此时由于M1是一个充分大的数，则(3)式无效。反之，若y1=0,而y2=1，即采用原加工方式。此时由于M2是一个充分大的数，则(4)式无效。一般地，若需要从p个约束条件).2, 1(1pibxainjjij中恰好选择q个约束条件，则可用引入p个0-1向量10iy若选择第i个约束条件若不选择第i个约束条件那么，约束条件组pjiiiinjjijqpyyMbxa11就可用达到这个目的。因为上述约束条件组保证了在p个0-1变量中有p-q个为1，q个为0。凡取0值的yi对应的约束条件即为原约束条件，而取1的yi对应的约束条件无效。固定费

33、用问题有三种资源被用于生产三种产品，资源量、产品单件费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求定制一个生产计划，使总收益最大。IIIIII资源量A248500B234300C123100单件费用456单件售价81012固定费用100150200建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生下面借助0-1变量解决这个困难设xj是第j种产品的产量, j=1,2,3;再设01iy生产第 j 种产品(即xj 0)不生产第 j 种产品(即xj 0)则问题的整数规划数学模型是：3 , 2 , 1, 103 , 2 , 1,01003230043

34、2500842. .200150100)612() 510()48(max333222111321321321321321jyjxyMxyMxyMxxxxxxxxxxtsyyyxxxZjj或且为整数如果生产第j种产品，则其产量xj 0。此时由约束条件xj Mjyj，知yj=1。因此相应的固定费用在目标函数中将被考虑。 如果不生产第j种产品，则其产量xj = 0,此时由约束条件xj Mjyj可知，yj可以是0也可以是1。但yj=1不利于目标函数的最大化，因而在问题的最优解中必然是yj=0，从而相应的固定费用将不再被考虑工件排序问题用4台机床加工3件产品。各产品的机床加工顺序，以及产品 i 在机床

35、 j 上的加工工时 aij 见下表产品产品1a11 a13 a14 机床机床1 机床机床3 机床机床4 产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3 a32 a33 机床机床2 机床机床3由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。解：设 xij 表示产品 i 在机床 j 上开始加工的时间(i=1,2,3;j=1,2,3,4)下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间，故应有：产品产品

36、1：及及xax141313xax131111产品产品2：及及xax242222xax222121产品产品3：xax3332322、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床1，有两种加工顺序。或先加工产品1，后加工产品2；或反之。对于其它3台机床，情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入0-1变量)4 , 3 , 2 , 1(10jyj先加工另一件产品先加工某件产品则每台机床上的加工产品的顺序可用下列四组约束条件来保证：机床1：及)1 (1112121yMxaxyMxax1211111机床2：及)

37、1 (2223232yMxaxyMxax2322222机床4：及)1 (4142424yMxaxyMxax4241414机床3：及)1 (3133333yMxaxyMxax3331313各yj的意义是明显的。如当y1=0时，表示机床1先加工产品1，后加工产品2，当y1=1时，表示机床1先加工产品2，后加工产品1。3、产品2的加工时间约束产品2的开始加工时间是x21，结束加工时间是x24+a24，故应有：dxax2124244、目标函数的建立设全部产品加工完毕的结束时间为W，由于三件产品的加工结束时间分别为x14+a14， x24+a24， x33+a33，故全部产品的实际加工结束时间为：),m

38、ax(333324241414axaxaxW转化为线性表达式axWaxWaxWWZ333324241414min综上所述，例题的整数规划模型为：4, 3 ,2, 1, 100,)1 ()1 ()1 ()1 (.min333224222114131133332424141421242441424244241414313333333313132223232232222211121211211111333232242222222121141312121111jyWxxxxxxxxaxWaxWaxWdxaxyMxaxMyxaxyMxaxMyxaxyMxaxMyxaxyMxaxMyxaxxaxxaxxa

39、xxaxxaxtsWzj或 0-1型整数规划是一种特殊的整数规划，若含有n个变量，则可能产生 2n 个可能的变量组合。当n 较大时，采用完全枚举法解题几乎是不可能的。已有的求解0-1型整数规划的方法一般都属于隐枚举法三、 0-1型整数规划的解法 在2n个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件。 对于可行解，其目标函数值也有优劣之分。若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性。在以后的求解过程中，每当发现比原来更好的可行解，则以此替换原来的过滤条件

40、。 上述这些做法，都可用减少运算次数，使最优解能较快地被发现。例 求解0-1整数规划1231231231223123max3252244. .346,01Zxxxxxxxxxstxxxxx x x或10,6434422.523max3213221321321321或xxxxxxxxxxxxxtsxxxZ解 求解过程可以列表表示(x1,x2,x3)Z值约束条件（a b c d）过滤条件(0,0,0)0 Z0(0,0,1)5 Z5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8 Z8abcd(x1,x2,x3)Z值约束条件（a b c d）过滤条件(1,1,0)1(1,1,1)6

41、接上表所以，最优解（x1,x2,x3）T=(1,0,1)T,max Z = 8由于采用上述算法，实际只作了20次运算。例 求解01整数规划104, 3, 2, 15423158443621143212. .432713min或xxxxxxxxxxxxxxxtsxxxxzZ解：采用上例那样的算法，解此例共需作36次运算。为了进一步减少运算量，常按目标函数中各变量系数的大小顺序重新排列各变量，以便最优解有可能较早出现。对于最大化问题，可按由小到大的顺序排列；对于最小化问题，则相反本例可写成下列形式：10,55386412.37min3412412341234123412或xxxxxxxxxxxxx

42、xxtsxxxxZ采取这样的形式用上法解此例，只需作30次运算。一般问题的规模越大，这样做的好处就越明显。篮球队需要选择5名队员组成出场阵容参加比赛. 8 名队员的身高及擅长位置见下表:队员12345678身高1.921.901.881.861.851.831.801.78擅长位置中锋中锋前锋前锋前锋后卫后卫后卫出场阵容应满足以下条件:1) 只能有一名中锋上场2) 至少有一名后卫3) 如1号和4号均上场, 则6号不上场4) 2号和8号至少有一个不出场问: 应当选择哪5名队员上场,才能使出场队员平均身高最高? 试建立数学模型有五项设计任务可供选择.各项设计任务的预期完成时间分别为3, 8, 5,

43、 4, 10 (周), 设计报酬分别为 7, 17, 11, 9, 21 (万元). 设计任务只能一项一项地进行, 总的期限是 20 周.选择任务时必须满足下面要求:1 至少完成 3 项设计任务;2 若选择任务 1, 必须同时选择任务 2;3 任务3 和 任务4不能同时选择应当选择那些设计任务, 才能使总的设计报酬最大?(试建立数学模型)整数规划v整数规划的数学模型及解的特点v解纯整数规划的割平面法*v分支定界法v0-1型整数规划*v指派问题5 指派问题指派问题是整数规划的一类重要问题。也是在实际生活中经常遇到的一种问题：由n项不同的工作或任务，需要n个人去完成（每人只能完成一项工作）。由于每

44、人的知识、能力、经验等不同，故各人完成不同任务所需的时间（或其它资源）不同。问应只排哪个人完成何项工作所消耗的总资源最少？一。 指派问题的数学模型引进0-1变量01ijx表示按排第i个人完成第j项工作表示不安排第i个人完成第j项工作则决策变量矩阵可表示为：nnnnnnxxxxxxxxxX212222111211用 表示第i个人完成第j项工作所需的资源数，称之为效率系数（或价值系数）。表示为nnnnnncccccccccC212222111211ijc效率矩阵（Coefficient matrix）则指派问题的数学模型为ninjijijxcZ11minnjxnixtsniijnjij, 2 ,

45、11, 2 , 11. .110ijx或1注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。下用目前认为最简洁的方法匈牙利法求解。例1：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司 对新商店 的建造报价（万元）为 ，见表5-9。商业公司应当对5家建筑公司怎样分配建筑任务，才能使总的建筑费用最少？)5 , 2 , 1(iAi)5 , 2 , 1(jBj)5 , 2 , 1,(jicijC54321AAAAA54321BBBBB8106961081476106129671417971215784这是一个标准的指派问题。若设0-1变量01ij

46、x当 承建 时iAjB当 不承建 时iAjB则问题的数学模型为11125455min48108Zxxxx5, 2 , 115, 2 , 11. .5151jxixtsiijjij0ijx或1C810696108147610612967141797121578454321AAAAA54321BBBBB0010000010010001000000001*X若单说让谁建，不让谁建。C810696108147610612967141797121578454321AAAAA54321BBBBB-414022328023062208112359110-6-7 -6-70010000010010001000

47、000001*X从而导出匈牙利解法的思想：匈牙利法是1955年由库恩（W.W.Kuhn）根据匈牙利数学家狄考尼格（d.konig)关于矩阵中独立零元素的定理发明的。匈牙利法的基本原理：定理1 将效率矩阵的某一行（或某一列）的各个元素都减去同一个常数t (t可正可负），得到新的矩阵，则以新矩阵为效率矩阵的指派问题与原指派问题的最优解相同。但其最优值比原最优值减少t 。解：设效率矩阵C为二。匈牙利解法nnnnknkknnccccccccccccC21212222111211nnnnknkknnccctctctcccccccC21212222111211记新指派问题的目标函数为 ，则有Zninjnk

48、iinjnjkjkjijijijijxcxcxcZ11111njkjnkiinjnkiinjnjkjkjijijnjkjkjijijxtxcxcxtcxc1111111)(ninjijijtZtxc111 .注意到njijx11所以原式因此有tZtZZmin)min(min而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。推论 若将指派问题的效率矩阵每一行及每一列分别减去各行各列的最小元素，则得到的新的指派问题与原指派问题有相同的最优解。证明：证明：结论是显然的。只要反复运用定理1便可得证。注：当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最

49、小元素，则最后得到新效率矩阵 中必然出现一些零元素。设 =0，从第i行看，它表示第 i 人去干第 j 项工作效率（相对）最好，而从第j列来看，它表示第 j 项工作让第 i 人来干效率（相对）最高。Cijc 问题是：能否找到位于不同行、不同列的n个0元素？定义 在效率矩阵C中，有一组处于不同行、不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。例 已知0084765000320205C则0, 0, 0, 043312412cccc是一个独立零元素组，0, 0, 0, 043312412cccc分别称为独立零元素。0084765000320205C也是一个独立零元素组。008476

50、5000320205C不是一个独立零元素组。根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的 =1，其余的 =0。就可找到指派问题的一个最优解。ijxijx就上例中(1)0100000110000010X就是一个最优解。同理(2)0100001010000001X也是一个最优解。3084065070320205C 但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。已知效率矩阵3084065070320205C怎么办？定理 效率矩阵C中独立零元素的最多个数等于能

51、覆盖所有零元素的最少直线数。本定理由匈牙利数学家狄考尼格证明的。证明的内容已超出所需学的范围。下面通过例子说明上述定理的内容例 已知矩阵0084765000320205C3084065070320205C至于如何找覆盖零元素的最少直线，通过例子来说明。例1 现有一个44的指派问题，其效率矩阵为：9118713161491514410413152C求解该指派问题。步骤1：变换系数矩阵，使得每行及每列至少产生一个零元素。9118713161491514410413152C-2-4-9-724104750111006211130-4-2100102350960607130C步骤2：用圈0法确定 中的

52、独立0元素。若独立零元素个素有n个，则已得最优解。若 独立零元素的个数 n, 则转入步骤3。1C1, 1, 1, 143312214xxxx其余全为0。在只有一个0元素的行（或列）加圈，表示此人只能做该事（或此事只能由该人来做），每圈一个“0”，同时把位于同列（或同行）的其他零元素划去。表示此时已不能再由他人来做（或此人已不能做其它事）。如此反复，直到矩阵中所有零元素都被圈去或划去为至。在遇到所有行和列中，零元素都不止一个时，可任选其中一个加圈，然后划去同行、同列其他未被标记的零元素。例0080760000320205C步骤3： 若矩阵已不存在未被标记的零元素，但圈零的个数m n ，作最少直线

53、覆盖当前零元素。已知例1(工程承包)中的系数矩阵变为48715127917141069128767146106912106C-4-7-6-6-6046304081012630371020811340-1 -3变换系数矩阵043204050012320377108110301C 确定独立零元素. 作最少直线覆盖当前所有零元素。由于独立零元素个数4 5. 对没有圈0的行打“”。 在已打“”的行中，对零元素所在的列打“”。 在已打“”的列中，对圈0元素所在的行打“”。043204050012320377108110301C 重复和，直到再也找不到可以打“”的行或列为止 对没有打“”的行画一横线，对已

54、打“”的列画一纵线，即得覆盖当前0元素的最少直线数目的集合。043204050012320377108110302C 继续变换系数矩阵，以增加0元素。在未被直线覆盖的元素中找出一个最小的元素。对未被直043204050012320377108110301C043204050012320377108110302C线覆盖的元素所在的行（或列）中各元素都减去这一元素。这样，在未被直线覆盖的元素中势必会出现0元素，但同时却又使已覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素。返回。043204050012320377108110302C-1-1043204

55、05000121126601811030+1304321405010121026600811031C 中已有5个独立0元素，故可确定指派问题的最优方案。3C, 1, 1, 1, 1,xxxx其余全为0。304321405010121026600811031C 中已有5个独立0元素，故可确定指派问题的最优方案。3C, 1, 1, 1, 1,xxxx其余全为0。48715 1279 17 14 1069 128767 1461069 12 106也就是说，最优指派方案是：让 承建 ， 承建1A3B2A1B 承建 ， 承建 。这样安排能使总的建造费

56、用最少，总的建造费用为7+9+6+6+6=34（万元）。4A4B5A5B课堂练习某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示求最优生产配置方案 表表5-1产品产品1产品产品2产品产品3产品产品4工厂工厂工厂27550150230工厂工厂36570170250工厂工厂48255200280第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有 556550582802005582250170706523015050752601806958min22514502718510550180100025202122110第二

57、步：找出矩阵每列的最小元素，再分别从每列中减去，有 4545027555000025222211022514502718510550180100025202122110第三步：用最少的直线覆盖所有“0”，得01122222500005552704545第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k5直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵4545032000000030171760第四步等价于第第四步等价于第1、3行减去行减去5，同时第，同时第1列加上列加上5得到的结果得到的结果-5-5+

58、54545032000000030171760第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素容易看出4个“0”的位置 4545032000000030171760或或4545032000000030171760得到两个最优解 11111111)2()1(，XX有两个最优方案第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2；第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 产品总成本Z5815025055513 三。非标准形式的指派问题在实际应用中，经常遇到非标准形式的指

59、派问题。处理方法：化标准，再按匈牙利访法求解。 最大化指派问题例13 有4种机械要分别安装在4个工地，它们在4个工地工作效率（见下表）不同。问应如何指派安排，才能使4台机械发挥总的效率最大？ 工地机器甲 乙 丙 丁30 25 40 3232 35 30 36 35 40 34 2728 43 32 38解：设最大化的指派问题系数矩阵 ，其中最大元素为m（本例种m=43），令矩阵nnijcC)(nnijnnijcmbB)()(本例中38324328273440353630353232402530C511015169387138111131813B-3-7-3-051101513605061480

60、1510-451101113601061080156圈0覆盖打511011136010610801561B-1-1+141001012500062080166圈02B此时m=n=4,因此决策变量矩阵为0010000110000100X即指派机械安装在工地丙，机械安装在工地丁，机械安装在工地甲，机械安装在工地乙，才能使4台机器发挥总的效率最大。其总效率为38324328273440353630353232402530 人数和事数不等的指派问题若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚