第3章整数线性规划

1、第第3章章 整数线性规划整数线性规划整数线性规划问题整数线性规划问题Gomory割平面方法割平面方法分枝定界方法分枝定界方法0-1规划规划3.1 整数线性规划问题整数线性规划问题引例引例建立整数线性规划模型建立整数线性规划模型整数线性规划的数学模型整数线性规划的数学模型整数线性规划问题的求解整数线性规划问题的求解应用案例应用案例 投资组合问题投资组合问题 旅游售货员问题旅游售货员问题 背包问题背包问题投资组合问题投资组合问题 背背 景景 实实 例例 模模 型型背背 景景 证券投资证券投资：把一定的资金投入到合适的：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利有价证券上以规避风险并

2、获得最大的利润。润。 项目投资项目投资：财团或银行把资金投入到若：财团或银行把资金投入到若干项目中以获得中长期的收益最大干项目中以获得中长期的收益最大。案案 例例 某财团有某财团有 万元的资金，经出其考察选中万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其个投资项目，每个项目只能投资一个。其中第中第 个项目需投资金额为个项目需投资金额为 万元，预计万元，预计5年后获利年后获利 （ ）万元，问应如何）万元，问应如何选择项目使得选择项目使得5年后总收益最大？年后总收益最大？Bnjcjbnj.,2 , 1j模模 型型 变量变量每个项目是否投资每个项目是否投资 约束约束总金额不超过限制

3、总金额不超过限制 目标目标总收益最大总收益最大0 , 1 jxnj.,2 , 1 Bxbnjjj 1 njjjxc1max njxBxbtsxcjnjjjnjjj.,2 , 1; 0 , 1.max11旅游售货员问题旅游售货员问题 背景背景 案例案例 模型模型背背 景景 旅游线路安排旅游线路安排 预定景点走且只走一次预定景点走且只走一次 路上时间最短路上时间最短 配送线路配送线路货郎担问题货郎担问题 送货地到达一次送货地到达一次 总路程最短总路程最短案案 例例 有一旅行团从有一旅行团从 出发要遍游城市出发要遍游城市 ，已知从，已知从 到到 的旅费的旅费为为 ，问应如何安排行程使总费，问应如何安

4、排行程使总费用最小？用最小？0vnvvv,.,21jvivijc模模 型型 变量变量是否从是否从i第个城市到第第个城市到第j个城市个城市 约束约束 每个城市只能到达一次、离开一次每个城市只能到达一次、离开一次; 0 , 1ijxnjxnixniijnjij,.2 , 1; 1,.2 , 1; 100 避免出现断裂避免出现断裂 每个点给个位势每个点给个位势 除了初始点外要求前除了初始点外要求前点比后点大点比后点大 目标目标总费用最小总费用最小ijninjijxc00njnixnjinnxuunjxnixtsxcijijjiniijnjijijninjij,.,2 , 1,.,2 , 1, 0 ,

5、 11 ; 1,.,2 , 1; 1,.,2 , 1; 1. .min0000背包问题背包问题 背景背景 案例案例 模型模型背背 景景 邮递包裹邮递包裹 把形状可变的包裹用尽量少的车辆运走把形状可变的包裹用尽量少的车辆运走 旅行背包旅行背包 容量一定的背包里装尽可能的多的物品容量一定的背包里装尽可能的多的物品实实 例例 某人出国留学打点行李，现有三个旅行包，容某人出国留学打点行李，现有三个旅行包，容积大小分别为积大小分别为1000毫升、毫升、1500毫升和毫升和2000毫毫升，根据需要列出需带物品清单，其中一些物升，根据需要列出需带物品清单，其中一些物品是必带物品共有品是必带物品共有7件，其体

6、积大小分别为件，其体积大小分别为400、300、150、250、450、760、190、（单位毫、（单位毫升）。尚有升）。尚有10件可带可不带物品，如果不带将件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。把物品放在三个旅行包里。 物品物品12345678910体积体积200350500430320120700420250100价格价格154510070

7、5075200902030问题分析问题分析 变量变量对每个物品要确定是否带同时要确定对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设的总容量就很难写成变量的函数。为此我们设变量为第变量为第i个物品是否放在第个物品是否放在第j个包裹中个包裹中3 , 2 ,

8、1,17.,2 , 1; 0 , 1jixij 约束约束3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131ixjij包裹容量限制包裹容量限制必带物品限制必带物品限制选带物品限制选带物品限制 目标函数目标函数未带物品购买费用最小未带物品购买费用最小17.,2 , 8;131ixjij)1 (31178jijiixp模模 型型)1 (min31178jijiixp3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131ixjij3 , 2 , 1,17.,2 , 1; 0 , 1jixij

9、例例 某公司拟建设某公司拟建设A A、B B两种类型的生产基地若干个，两两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问产能力及现有资源情况如下表所示。问A A、B B类型基地各类型基地各建设多少个，可使总生产能力最大？建设多少个，可使总生产能力最大？A AB B资源限制资源限制占地（占地（m m2 2）费用（万元）费用（万元）200020005 5500050004 413000130002424生产能力生产能力20002000100010002 整数线性规划的数学模型整数线性规划的

10、数学模型 nJiIxxxci,2 , 1, 0 b Axs.t. min T 整数整数线性规划模型线性规划模型,.2 , 1 , 0, IRARbRcRxnmmnn其其中中简称：简称：ILP问题（问题（integer linear programming） 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、数规划、混合整数规划、0 01 1整数规划。整数规划。例：设整数规划问题例：设整数规划问题0,13651914. .min21212121xxxxxxtsxxz且为整数且为整数3 整数线性规划问题的求解整数线性规划问题的求解思路

11、思路1：可否解决相应的线性规划问题，最后舍入到最：可否解决相应的线性规划问题，最后舍入到最近的整数解？近的整数解？x1x233(3/2,10/3)0,13651914. .min21212121xxxxxxtsxxz3 整数线性规划问题的求解整数线性规划问题的求解思路思路2：由于纯整数线性规划的可行集合就是一些离散：由于纯整数线性规划的可行集合就是一些离散的格点，可否用穷举的方法寻找最优解？的格点，可否用穷举的方法寻找最优解？当格点个数较少时，这种方法可以；当格点个数较少时，这种方法可以；对一般的对一般的ILP问题，穷举方法无能为力。问题，穷举方法无能为力。目前，常用的求解整数规划的方法有：目

12、前，常用的求解整数规划的方法有： 割平面法和分枝定界法；割平面法和分枝定界法；对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈牙利法。规划问题采用隐枚举法和匈牙利法。3 整数线性规划问题的求解整数线性规划问题的求解3.2 Gomory割平面方法割平面方法割平面方法的基本思想割平面方法的基本思想割平面方法的实现割平面方法的实现例题例题 算法思想算法思想 算法步骤算法步骤 算例算例割平面算法割平面算法算算 法法 思思 想想 由放松问题的可行由放松问题的可行域向整数规划的可域向整数规划的可行域逼近行域逼近 方法方法利用超平面利用超平面切除切除 要求要求 整数解保留整数解保留 放松问题最优值增

13、加放松问题最优值增加问题问题P和和P0的关系：的关系：P的可行区域是的可行区域是P0的可行区域的子集；的可行区域的子集；如果如果P0无可行解，则无可行解，则P无可行解；无可行解；P0的最优值是的最优值是P的最优值的一个下界；的最优值的一个下界；若若P0的最优解为整数向量，则它也是的最优解为整数向量，则它也是P的最优解；的最优解； 为为整整数数向向量量xxxc 0 b Axs.t. min T（P） 0 b Axs.t. min Txxc（p0）割平面生成方法割平面生成方法 条件条件-保留整数解删除最优解保留整数解删除最优解rNjjrjrbxaxNB1IN0BbBcB101bBBxNxrNjjr

14、jrbxaxrNjjrjrbxax rNjjrjrbxax rNjjrjrbxaxrjrjrjfaarjrjaa rrrfbb rrbb 整数可行解整数可行解最优基可行解最优基可行解为整数xxbAxtsxc, 0. .min 为整数xxbxaxbAxtsxcNjrrjrjr, 0. .min 为整数xxbsxaxbAxtsxcNjrrrjrjr, 0. .min 1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbbBcB11xnx2x1mxmx0111mabBcB101m00110nna11mmamna1bmbrx011rmarnarbr

15、s000011rmarna1 rb1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs000011rmrmaarnrnaa1 rrbbbBcB101xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs00001rmfrnf1rfbBcB100rf正则解正则解算算 法法 步步 骤骤求放松问题的求放松问题的最优基可行解最优基可行解判断是否判断是否为整数解为整数解是停止是停止得到最优解得到最优解否否在单纯性表中加入在单纯性表中加入一列利用对偶单纯一列利用对偶单纯性算法求最优解性算法求最优

16、解算算 例例整数, 0,023623. .max2121212xxxxxxtsx(1,1.5) 0,023623. min43214213212xxxxxxxxxxtsx1x3x2x4x010 0031206310021x3x2x4x005 . 0061165 . 15 . 000105 . 11x3x2x4x006/16/1414/12/3101104/14/12/31s000010111001432sxxx0011x3x2x4x006/16/1414/12/3101104/14/12/31x3x2x4x006/16/1414/12/3101104/14/12/31s00002/114/14

17、/101x3x2x4x003/1101011s3/2024011001103/20011x3x2x4x003/1101011s3/2024011001103/20012s000032323210001x3x2x4x00101011s01501001100012s002/ 300011102/ 3012/ 113.3 分枝定界方法分枝定界方法分枝定界方法的基本思想分枝定界方法的基本思想分枝定界方法的实现分枝定界方法的实现例题例题1 分枝定界方法的基本思想分枝定界方法的基本思想如果松弛问题如果松弛问题(P0)无解，则无解，则(P)无解；无解；如果如果(P0)的解为整数向量，则也是的解为整数向量，则

18、也是(P)的解；的解；如果如果(P0)的解含有非整数分量，则对问题的解含有非整数分量，则对问题分枝分枝：将将ILP问题问题(P)分为几个子问题，试图做到：要么找分为几个子问题，试图做到：要么找到某个子问题的最优解，要么判断原问题到某个子问题的最优解，要么判断原问题(P)的最的最优解一定不在子问题的可行区域内。优解一定不在子问题的可行区域内。2 分枝定界方法的实现分枝定界方法的实现例题例题 整数整数, 0 , 11 24 124- s.t. )( - min 21212121xxxxxxxx例：例：0 x1x2x0 x1x2x3x5例：例：解：解：1、先解其松弛问题：、先解其松弛问题：12121

19、212min -() s.t. -421 42 11 ,0 xxxxxxxx 整数整数, 0 , 11 24 124- s.t. )(- min 21212121xxxxxxxx易得其最优解为易得其最优解为(3/2,5/2),最优值为最优值为-42、由于最优解为非整向量，取非整分量由于最优解为非整向量，取非整分量x1=3/2,引进两个约引进两个约束束 (它们将它们将x1=3/2排除在外排除在外)，得到两个子问题：，得到两个子问题：2, 111 xx1212112112min -() s.t.-421(P ) 42 11 1 , 0,xxxxxxxxxInteger 1212212112min

20、-() s.t.-421(P ) 42 11 2 , 0,xxxxxxxxxInteger P1P2P11 x21 x12121212min -() s.t. -421 42 11 ,0 xxxxxxxx 3、分别解这两个子问题的松弛问题：、分别解这两个子问题的松弛问题：121212112min -() s.t.-421 42 11 1 ,0 xxxxxxxx x 121212112min -() s.t.-421 42 11 2 ,0 xxxxxxxxx 最优解为最优解为(1,3/2),最优值为最优值为-5/2最优解为最优解为(2,3/2),最优值为最优值为-7/2均需进一步分枝，称为均需进

21、一步分枝，称为“活点活点”P1P2P11 x21 x接下来怎么做？接下来怎么做？4、选取目标函数较优、选取目标函数较优(-7/2)的那个点先分枝的那个点先分枝(即第二个子问题即第二个子问题)，引进，引进 得：得：2, 122 xx12121231212min -() s.t.-421 42 11(P ) 2 1 , 0,xxxxxxxxxxInteger 12121241212min -() s.t.-421 42 11(P ) 2 2 , 0,xxxxxxxxxxInteger P1P2P11 x21 x4P3P12 x22 x5、解这两个子问题的松弛问题：、解这两个子问题的松弛问题：121

22、2121212min -() s.t.-421 42 11 2 1 ,0 xxxxxxxxxx 1212121212min -() s.t.-421 42 11 2 2 , 0 xxxxxxxxxx 最优解为最优解为(2.25,1),最优值为最优值为-3.25无解无解树叶树叶继续分枝继续分枝P1P2P11 x21 x4P3P12 x22 x接下来呢？接下来呢？6、对第一个子问题继续分枝，引进、对第一个子问题继续分枝，引进约束条件约束条件 得到：得到：3, 211 xx121212512112min -() s.t.-421 42 11(P ) 2 1 2 , 0,xxxxxxxxxxxInte

23、ger 121212612112min -() s.t.-421 42 11(P ) 2 1 3 , 0,xxxxxxxxxxxInteger P1P2P11 x21 x4P3P12 x22 x6P5P21 x31 x7、解这两个子问题的松弛问题：、解这两个子问题的松弛问题：12121212112min -() s.t.-421 42 11 2 1 2 , 0 xxxxxxxxxxx 12121212112min -() s.t.-421 42 11 2 1 3 , 0 xxxxxxxxxxx 最优解为最优解为(2,1),最优值为最优值为-3无解无解树叶树叶P1P2P11 x21 x4P3P1

24、2 x22 x6P5P21 x31 xTx) 1 , 2(3Pmin5 8、再看另一个分枝：、再看另一个分枝：9、得到此整数规划问题的最优解为、得到此整数规划问题的最优解为(2,1)T,最优值为最优值为-3。P1P2P11 x21 x4P3P12 x22 x6P5P21 x31 xTx) 1 , 2(3Pmin5 25Pmin1 由于其松弛问题的最优值为由于其松弛问题的最优值为-5/2，所以所以-5/2就是这一分枝的下界就是这一分枝的下界.目前已经得到一个整数最优解，其最优目前已经得到一个整数最优解，其最优值为值为-3，好于另一分枝的下界，所以可以，好于另一分枝的下界，所以可以将之将之剪枝剪枝

25、。此点称为。此点称为死点死点。3.4 0-1规划规划引例引例建立建立0-1整数线性规划模型整数线性规划模型隐枚举方法隐枚举方法指派问题指派问题匈牙利方法匈牙利方法例例 某公司拟在市东城、西城、海淀三区建立门市部。拟议中某公司拟在市东城、西城、海淀三区建立门市部。拟议中有有7个位置个位置(点点)Ai(i=1,2,7)可供选择。规定可供选择。规定在东城区，由在东城区，由A1,A2,A3三个点中至多选两个；三个点中至多选两个；在西城区，由在西城区，由A4,A5中至少选一个；中至少选一个；在海淀区，由在海淀区，由A6,A7中至少选一个中至少选一个.假设选用假设选用Ai点，设备投资估计为点，设备投资估计

26、为bi元，每年获利估计元，每年获利估计ci元，但元，但是总投资额不超过是总投资额不超过B元。问应该选择哪几个点可以使年利润元。问应该选择哪几个点可以使年利润最大？最大？1 引例引例建立建立0-1整数线性规划模型整数线性规划模型问题分析问题分析东城区东城区西城区西城区海淀区海淀区A1A2A3A4A5A6A7如图，如何确定选择哪些点？有多少种可能？如图，如何确定选择哪些点？有多少种可能？试一试试一试枚举枚举法法Get into troubleGet into trouble！专门的解法研究专门的解法研究 隐枚举法隐枚举法每一个投资项目都有被选择和不被选择两种可能，为此设每一个投资项目都有被选择和不

27、被选择两种可能，为此设 没被选用没被选用当点当点被选用被选用当点当点iiA, 0A, 1ix7,.,2,1 i目标函数目标函数资金限制资金限制三条规定三条规定772211.maxxcxcxcz Bxbxbxb 772211.2321 xxx154 xx176 xx建立数学模型建立数学模型1122771122771234567max. .21101,1,2,.,7izc xc xc xs tb xb xb xBxxxxxxxxi oror建立数学模型建立数学模型在这一问题中，所有变量只在这一问题中，所有变量只有两个取值，有两个取值，0或或1，即，即0-1变变量，或叫二进制变量量，或叫二进制变量(

28、binary variable)，或叫逻辑变量，或叫逻辑变量（logical variable）这样的）这样的问题称为问题称为0-1规划问题。规划问题。 如何求解？如何求解？2 隐枚举方法隐枚举方法例例 求解求解0-1规划规划 3 , 2 , 1, 1064322422.523max3221321321321iorxxxxxxxxxxxtsxxxzi编号编号 2 6( 1, 1, 1 ) 3( 1, 1, 0 )8 0 2 1 1( 1, 0, 1 ) 1 5( 0, 1, 1 )3 1 1 1 0( 1, 0, 0 ) 2 4( 0, 1, 0 )5 1 1 0 1( 0, 0, 1 )0

29、0 0 0 0( 0, 0, 0 )是是 否否 (1) (2) (3) (4)z 值值满足条件满足条件约束条件约束条件x1,x2,x32 枚举方法枚举方法8502 隐枚举方法隐枚举方法 6(1, 1, 1) 1(1, 1, 0) 8 0 2 1 1(1, 0, 1) 3(1, 0, 0) 3(0, 1, 1)-2(0, 1, 0) 5 1 1 0 1(0, 0, 1) 0 0 0 0 0(0, 0, 0)是是 否否(0) (1) (2) (3) (4)z 值值满足条件满足条件约束条件约束条件x1 , x2, x3 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n n 项不项不

30、同的任务，需要同的任务，需要n n 个人分别完成其中的一项，个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成派哪个人去完成哪项任务，使完成 n n 项任务的项任务的总效率最高（或所需时间最少），这类问题称总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。为指派问题或分派问题。 (Assignment problem)3 指派问题指派问题例例

31、 有一份中文说明书，需译成英、日、德、俄有一份中文说明书，需译成英、日、德、俄四种文字四种文字,分别记为分别记为E、J、G、R. 有甲、乙、丙、有甲、乙、丙、丁四人丁四人.他们将中文说明书翻译成不同语种说明他们将中文说明书翻译成不同语种说明书的所需时间如下表，问应该指派何人去安排何书的所需时间如下表，问应该指派何人去安排何工作，使所需总时间最少？工作，使所需总时间最少？3 指派问题指派问题工工作作时时间间表表 任务任务人员人员EJGR甲甲乙乙丙丙丁丁2109715414813141611415139试建立数学模型？能否给出可行解？试建立数学模型？能否给出可行解？3 指派问题指派问题指派问题最优

32、解的性质指派问题最优解的性质 若从系数矩阵若从系数矩阵(cij)的一行的一行(列列)各元素中分各元素中分别减去该行别减去该行(列列)的最小元素，得到新的矩阵的最小元素，得到新的矩阵(bij),那么以那么以(bij)为系为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。数矩阵求得的最优解和用原系数矩阵求得的最优解相同。独立独立0元素元素 位于不同行不同列的元素。位于不同行不同列的元素。最优解的确定最优解的确定 若能在系数矩阵若能在系数矩阵(bij)中找出中找出n个独立的个独立的0元素，则元素，则令解矩阵令解矩阵(xij)中对应这中对应这n个独立的个独立的0元素的元素取值为元素的元素取值为1，其他元，其他元素为素为0.4 匈牙利方法匈牙利方法每行分别减去该行的最小元素每行分别减去该行的最小元素 9118713161491514410413152 2410475011100621113024974 匈牙利方法匈牙利方法 00102350960607130 2410475011100621113042每列分别减去该列的最小元素每列分别减去该列的最小元素4 匈牙利方法匈牙利方法