整数规划与分配问题

1、第四章整数规划与分配问题§4.1 整数规划的特点及作用用单纯形法求解线性规划的结果往往得到分数或小数解。但在很多实际问题中，全部或部分变量的取值必须是整数，如人或者机器设备不可分割。此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x ，令 x1 表示在该地建厂，x0 表示不在该地建厂，逻辑变量也只允许取整数值的一类变量。在一个整数规划中要求全部变量取整数值的，称 纯整数线性规划 或纯整数规划 ；只要求一部分变量取整数值的，称为混合整数（线性）规划 ；在纯整数规划问题中，若所有变量只允许取0，1 两个值，则称其为 0-1 规划 。有人认为，对整数规划问题的求解可以先不考虑对

2、变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整数寻找最优解，其实这种方法是不可行的，原因有以下两点：一、用凑整的方法计算量很大，而况还不一定能找到最优解。如某线性规划问题的最优解为x1x24.65.5 ，用凑整数的方法时需比较与x1, x2 的上述数值最接近的四种组合：(4,5),(5,5),(4,6),(5,6)如果问题中有 10 个变量，就要比较 2101024 个整数解组合，而且最优解还不一定在这些组合中。二、放松约束也无法求出其最优解max z3x12x2例2x13x214st.x10.5x24.5x1 , x20,整数x2x10.5x24.5x13.25

3、, x22.52x13x214ox1如果不考虑整数约束，称为上述线性规划问题的松弛问题，松弛问题的最优解为：1x13.25, x22.5取整以后 x13, x22 是可行解，但 x13, x23; x1 4, x2 2; x1 4, x2 3 都不是可行解，而 x13, x22 对应的目标函数值 z3x12x213 却不是最优解，然而最优解是x1 4, x21,max z3x12x2 14 。直接对松弛问题进行求解都无法求得整数规划问题的最优解， 这就需要对整数线性规划问题有特殊的求解方法。此外，整数线性规划问题的数学模型的研究有着重要的意义，很多管理问题无法归纳为线性规划问题的数学模型，但却

4、可以设置逻辑变量建立起整数规划问题的数学模型。下面举例说明逻辑变量在解决问题中的重要作用。1. m 个约束条件中只有 k 个起作用设 m 个约束条件可以表示为naij xjbi ,( i1,2, m)j 1定义1假设第 i个约束条件不起作用1,2, , m)yi，（ i0假设第 i个约束条件起作用又 M 为任意大的正数，则naij x jbiMyi(i 1,2,m)j 1y1 y2ym mky1, y2 , , ym或0 1n因为若 yi0 ，则aij xjbi 条件起作用j1nn若 yi1，则aij xjbiM ，aij x jbi条件不起作用j1j 12. 约束条件的右端项可能是 r 个值

5、 (b1 ,b2 ,br ) 中的某一个，即naij x jb1或 b2或 或 brj1定义yi1假定约束条件右端项为 bi0否则由此，上述约束条件可以表示成：2naij xjb1 y1b2 y2br yrj 1y1 y2yr1y1 , y2 , yr0或13. 两组条件中满足其中一组若 x14 ，则 x21；否则（即 x1 4 时）， x23定义1第i 组条件不起作用1,2)yi，（ i0第 i组条件起作用又 M 为任意大的正数，则问题可表达为：x14My1x21My1x14My 2x23My2y1y21y1, y20,14. 用以表示含固定费用的函数例如用 x j 代表产品 j 的生产数量

6、，其生产费用函数通常可表示为：C j(x jK j cj xj( x j0)( xj0)0式中 K j 是同产量无关的生产准备费用。问题的目标是使所有产品的总生产费用为最小，即：min znC j ( xj )j1令y j1x j00x j，那么 xj My j0nmin zj 1cj x jK j y j使问题化为：xjMy j0(M 为充分大的正数）st.或1,2,y j01) j, n)一般整数规划问题建模：例1某饭店 24小时中需要服务员数量如下：如果每个服务员连续工作8小时，试问在 2点、 6点、 10点、 14点、 18点、 22点钟开始上班的服务员为多少时，一天所需服务员人数最少

7、？3时间2-66-1010-1414-1818-2222-2最少服务员48107124设在 2点、6点、10点、14点、18点、22点钟开始上班的服务员分别为x1 , x2 , x3 , x4 , x5 , x6 ,则可建立整数规划数学模型min Zx1 x2x3x4x5 x6x1x64x1x28x2x310s.tx3x47x4x512x5x64x1 ,x2 ,x3 ,x4 ,x5x6 0 整数利用 LINGO 求解整数线性规划问题，得Min=x1+x2+x3+x4+x5+x6;x1+x6>=4;x1+x2>=8;x2+x3>=10;x3+x4>=7 ;x4+x5>

8、;=12;x5+x6>=4;gin(x1); gin(x2);gin(x3);gin(x4);gin(x5);gin(x6); Global optimal solution found.Objective value:26.00000Extended solver steps:0Total solver iterations:6VariableValueReduced CostX14.0000001.000000X24.0000001.000000X36.0000001.000000X41.0000001.000000X511.000001.000000X60.0000001.0000

9、00RowSlack or SurplusDual Price126.00000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000077.0000000.0000002. 在高校篮球联赛中，某学院男子篮球队要从 8 名队员中选择平均身高最高的出场阵容，队员的号码、身高及擅长的位置如表所示：队员号码12345678身高（ cm）1.92 1.90 1.881.861.851.831.801.78位置中锋中锋前锋前锋前锋后卫后卫后卫同时要求出场阵容满足以下条件：4

10、（1）中锋只能有一个上场；（2）至少有一名后卫；（3）如果 1 号队员和 4 号队员都上场，则6 号队员不能上场；（4）2 号队员和 6 号队员必须保留一个不出场。写出该问题的数学模型。解：设 xj1第 j号队员出场( j1,2,3,4,5,6,7,8)0第 j号队员不出场则可建立整数规划模型：max Z1.92x11.90x21.88x31.86x41.85x5 1.83x6 1.80x7 1.78x8x1x2x3x4 x5x6x7x85x1x21s.tx6x7x81x4x62x1x2x61x1 , x2 , x3 , x4 , x5 , x6 , x7 , x80或1利用 LINGO进行求

11、解 0 1 规划问题，得Max=1.92*x1+1.9*x2+1.88*x3+1.86*x4+1.85*x5+1.83*x6+1.8*x7+1.78*x8;x1+x2+x3+x4+x5+x6+x7+x8=5;x1+x2=1;x6+x7+x8>=1;x1+x4+x6<=2;x2+x6<=1;bin(x1); bin(x2); bin(x3); bin(x4); bin(x5); bin(x6); bin(x7); bin(x8); Global optimal solution found.Objective value:9.310000Extended solver step

12、s:0Total solver iterations:0VariableValueReduced CostX11.000000-1.920000X20.000000-1.900000X31.000000-1.880000X41.000000-1.860000X51.000000-1.850000X60.000000-1.830000X71.000000-1.800000X80.000000-1.7800003.某工厂生产 A1 、 A2 两种产品，产品分别由B1 、 B2 两种部件组装而成，每件产品所用部件数和有关部件的产量限额以及产品利润由下表所示。问怎样安排A1、 A2 的生产数量，该厂才

13、能有最大利润？部件B1B 2利润（元）产品A16115A24320部件的最大产量2510解：设生产 A1 、 A2 分别为 x1 、 x2 件，则5max Z15 x120x26x14x225s.t x13x210x1 , x20, 整数很容易用LINGO10.0 求出它的最优解。Max=15*x1+20*x2;6*x1+4*x2<=20;x1+3*x2<=10;gin(x1);gin(x2);下料问题也是典型的整数规划问题下面讲指派问题6§4.2分配问题（指派问题）与匈牙利法2-1 问题的提出与数学模型分配问题也称指派问题（Assignment Problem）, 是一

14、种特殊的整数规划问题，假定有 m 项任务分配给 m 个人去完成，并指定每人完成其中一项， 每项只交给其中一个人去完成。例：有 m 个人，去完成 m 项任务，不同的人完成不同的任务效率如下表：B1B2BmA1a11a12a1mA2a21a22a2mAmam1am2amm如何分配任务，使花费的总时间最少？a11a12a1ma21a22a2m 称为分配问题的效率矩阵。am1am2amm令 xij1分配第 i个人去完成第 j项任务（i, j 1,2, , m)0不分配第 i个人去完成第 j项任务则分配问题的数学模型一般可以写为：mmmin zaijxiji 1j 1mj 1xij1(i1,2, m)m

15、st.xij1( j1,2, m)i 1xij或1(i , j1,2, m)02-2匈牙利法理论上，这也是运输问题，但是它比运输问题更特殊，可以用更特殊的方法加以解决。可以用求解运输问题的表上作业法求解分配问题，但通常更有效的是用匈牙利方法求解。解分配问题的匈牙利方法是从这样一个明显的事实出发的： 如果效率矩阵的所有元素 aij 0 ，而其中存在一组位于不同行不同列的零元素，则只要令对应于这些元素位置1 其余的 xijmm的 xij0 ，则 zaij xij 就是问题的最优解。如效率矩阵为：i 1j 1701493100092002300102303，010就是指派问题的最优解。8001214

16、00001但问题是如何产生并寻找这些位于不同行不同列的零元素。匈牙利数学家克尼格（ Konig）证明了下面两个基本定理，为解决以上问题奠定了基础。因此，基于这两个定理基础上所建立的求解分配问题的计算方法被称为 匈牙利法 。定理 1 如果从分配问题的效率矩阵 (aij ) 中的某一行分别减去（或加上）一个常数 ui（被称为该行的位势），从某一列分别减去（或加上）一个常数v j （称为该列的位势），得到一个新的效率矩阵 (bij) ，若其中 bijaijui v j ，则以 (bij ) 为效率矩阵分配问题的最优解等价于以 ( aij ) 为效率矩阵分配问题的最优解。证明：mmmmzbij xij

17、(aijuivj )xiji 1j 1i1j 1mmmmmaij xijuixijv jxiji1i 1j 1j 1i 1mmmaij xijuivj( 后两项是常数 )i1i 1j 1mmmm所以minbij xijminaij xiji 1j 1i 1j 1例：现有四人每人都能完成四项工作中的一项，但由于各自对不同工作的熟练程度或技术专长的不同，完成每项工作花费的时间也不同。如下表B1B2B3B4A1314105A21041210A39141513A478119匈牙利方法的步骤：1. 变换效率矩阵，使变换后的效率矩阵每行、每列至少有一个“0”元素3141050117211303080104

18、1210660444566(aij )1415130452(bij )991402781190210074022. 试求最优解（通过标注零的方法）所以可以求得80001(xij01005491129)00,min z100010A1B4, A2B2,A3B1, A4B3例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间如下表，应如何分配，使这四个人分别完成这四项任务的总时间为最短。甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文4151391. 每一行均减去该行的最小值，每一列均减去该列

19、的最小值，使每行每列至少有一个零元素（变换效率矩阵）210970875825201001541481140544351113141611203001111924151390511454502. 试求最优解0*825110*54230*0011453. 作覆盖所有零元素的最少直线集合（1）对没有 0* 的行打（2）对打了的行上 0 元素所在的列打（3）对打了的列上 0* 所在的行打（4）对打了的行上0 元素所在的列打直至打不出新的行和新的列对没有打的行划横线，对打了的列划竖线，这样就得到能够覆盖所有零元素的最少直线组合。定理 2 若矩阵 A 可分为“ 0”与非“ 0”两部分，则覆盖“ 0”元素的

20、最少直线数等于位于不同行不同列的“ 0”元素的最大个数。恰好等于我们标出 0* 的个数。证明 : 已知矩阵中有若干个 0 元素，设覆盖全部 0 元素最少需要 m 条直线，又设位于不同行不同列的 0 有 M 个，因覆盖每个 0 至少用一条直线，故有9mM下面要证明 Mm ，假定覆盖所有0 元素的 m 条直线有 r 行（用 i1 ,i2 ,ir 表示）c 列（用 j1, j2 , , jc 表示）， m r c ；显然在每一行上至少存在一个不在 j1 , j2 , , jc 列上的 0 元素；设某一行上这些不在 j1, j2 , , jc 列上的 0 元素下标的集合为Si l ail0,lj1 ,

21、 j2 , jc 对 i1,i2 , ,i r 行分别有集合 Si1 , Si2 , , Si r ，从这些集合中任取 k 个（ k r ），其集合中的不同元素个数必不少于 k ，否则这 k 行的直线可用少于 k 条列线代替，与 m 是覆盖 0 元素的最少直线的假定矛盾。由此可知，在 r 条行线上存在不少于r 个位于不同的列， 且这些 0 不位于 j1 , j 2 , jc列上。同理可以证明在c 条列线上存在不少于c 个位于不同行的0，且这些0 不位于i1, i2 , ir 行上。若上述两部分 0 的个数总和为 S ，则 S m ，又显然 S M ，故有 M m 从而有 M m ，定理得证。4

22、. 继续变换效率矩阵，试求最优解，回到第二步。从未被直线覆盖的所有元素中找出一个最小元素k ，然后将效率矩阵未划横线的行均减去这个最小元素，划竖线的列均加上这个最小元素。再试求最优解，继续。060*30010130*54( xij0100430最优解为)0010*00*9231000min z 9 411428, 或者 min z 2411 4522228例：求下列指派问题的最优解人（工件）B1B2B3B4B5A1127979A289666A3717121412A415146610A5410710612797 950*20270*20289 66623 0*00430*0071712 1412

23、0*105750*8353151466109800*411800*441071060636204140*100100000100( xij )10000最优解0001000001min z76766 32或 min z 7 6 7 6 4 2 2 2 32两点说明1. 分配问题中如果人数和工作任务数不相等时的处理方法。举例来说，如果人员数大于任务数，可以增加虚的任务，使总的任务数与总的人员数相等，不过每个人完成虚任务的时间为 0，效益当然也为 0；当人员数小于任务数，可增加虚的人员，使人员总数等于任务总数。 虚人员完成各任务的效率与效益均为 0，这时可能有的任务无法落实。如：136260027

24、144003365800464370055243006576200362600050*40071440040*22003658000*5360064370033150*0524300212100*5762002640*00min z213282. 如果把效率矩阵改为效益矩阵， 把求指派问题的最小值化为求指派问题的最大值即可。mm如 max zaij xiji 1j 1等价于 min z'mm( aij ) xij ，由于 (aij ) 为负，不容易比较，现在将每一个数zi1j 1都加上 M ，等价于 min wmm(M aij ) xij , Mmax aij 化为一般的最小化指派问题

25、。i 1j 1例：一个公司要分派5 个推销员去 5 个地区推销某种产品， 5 个推销员在各个地区推销这种产品的预期利润如下表所示。若每个推销员只能去一个地区，应如何分派这5个推销员才能使公司的利润最大？11ABCDE甲1510121012乙1112999丙1020151712丁18179913戊713101312max aij 205108108053539811111110333(20aij )100538100538231111701995137107860301050*5 205 0*3 01003210010*10 0*23 710 0*2 1 50*16940*16726 000*0

26、8220*00010000001( xij )01000,max z12 9201813 721000000010例：某车队有 5 辆汽车，将驶往 3 个目的地运货。一地的货物只需一辆车送，其运费（元）如下表：（1）试求最优指派的调运方案（2）若表中数字表示所得利润，则应如何指派？（3）若车 2 载不下 A 地所需货物，车5 爬不上通往 B 地必经之路上的坡，对（1）（ 2）的最优解有什么影响？汽车1汽车2汽车3汽车4汽车5A1012141113B1320231521C861075相应的作业 P125， 4.3 （a） (b)P125 4.5 提示以后让学生自己完成要真正弄懂(a) 将最后一列

27、先减去一个数如30，使 E 列占优势，这就保证了任务E 必须能完成，12252931427393826203也无妨。然后再增加一个虚的人272840，再增加一行 03422442362315（b）取每列的最小值，放至最后一行，作为第5 个人，然后在任务分派时将第 5个人的任务再还原。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032（ c）将不能完成任务的人、任务对应时间放至 M 100 ，然后再从丙、丁行的最小值放至下一行，分配完任务以后，与 (b) 一样进行还原。ABCDE甲 25 29 100 42 37乙 100 3

28、8 100 20 33丙34272840100丁10042362345戊3427282345这样即可达到目的。13§ 4.3分枝定界法在线性规划问题中，变量 x 是在一个连续的范围内取值，因此可行解个数无限多。但在整数规划问题中变量只能取离散的整数值，可行解的总数是有限的。从有限多的可行解中寻找最优解的最直观、最简单的方法是枚举法，但方法不可行。分枝定界法 (branch and bound method) 就是为求解同整数规划具有类似性质的一大类问题而设计的一种较好的方法。第一步：寻找替代问题并求解。方法是放宽约束条件， 去掉整数约束。如果非整数线性规划问题的最优解就是整数，则已求

29、得整数问题的最优解；否则，这个最优解是原整数线性规划问题最优解的一个上界（求最大值）或者下界（求最小值） 。max z3x12x2max z3x12x22x13x214放松约束条件，求解如下问题2x13x214（ LP1）st. x10.5x24.5st. 2x1x29x1 , x20,整数x1 , x2 0基解x1x2x3x4x3142310x492101z03200x35021-1x19/211/201/2z-27/201/20-3/2x25/2011/2-1/2x113/410-1/43/4z-59/400-1/4-5/413, x2559（ LP1）最优解 x1,max z442max

30、 z3x12x2max z3x12x22x13x2142x13x2142x1x29（ LP12）st.2x1x29（ LP13）st.2x23x2x1 , x20x1 , x2 0基解x1x2x3x4x5x25/2011/2-1/20x113/410-1/43/40x5-1/200-1/21/21z -59/400-1/4-5/4014x2201001x17/21001/2-1/2x31001-1-2z-29/2000-3/2-1/2（ LP12）最优解 x17 , x22,max z29max z3x12x222max z3x12 x22x13x2142x13x2142x1x29（ LP12

31、1）2x1x29（ LP122）s.t x22s.t x22x13x14x1 , x2 0x1, x20基解x1x2x3x4x5x6x22010010x17/21001/2-1/20x31001-1-20x6-1/2000-1/21/21z-29/2000-3/2-1/20x22010010x13100001x320010-3-2x410001-1-2z-130000-2-3（ LP121）最优解为 x13, x22,max z13, z13基解x1x2x3x4x5x6x22010010x17/21001/2-1/20x31001-1-20x6-4-100001z-29/2000-3/2-1/

32、20x22010010x17/21001/2-1/20x31001-1-20x6-1/20001/2-1/21z-29/2000-3/2-1/20x21010102x1410000-1x33001-30-4x61000-11-2z-14000-20-115（ LP122）最优解为 x1 4, x21,max z14, z14基解x1x2x3x4x5x25/2011/2-1/20x113/410-1/43/40x5-30-1001z-59/400-1/4-5/40x25/2011/2-1/20x113/410-1/43/40x5-1/2001/2-1/21z-59/400-1/4-5/40x23

33、0100-1x15/2101/203/2x4100-11-2z-54/400-3/20-5/2（ LP13）最优解 x15 , x2 3,max z2713.5 14 ，尽管不是整数解，但它的目标函数的最大22值小于 14，不必分枝，因此该整数线性规划问题的最优解为：x14, x2 1,max z 1416max z3x1 2x22x13x2 142x1x29x1, x20x1 13/ 4, x25/ 2,max z 59 / 4max zmax z3x1 2x23x1 2x23x2142 x13x22x114x292 x1x22x193x22x2x1 , x20x1, x20x1 5 / 2, x23,max z 27 / 4 14x1 7/ 2, x22,max z 29 / 2不用分枝max z3x1 2x2max z3x1 2x22x13x2 142x13x2 14