整数线性规划

1、教学要求教学要求：整数规划整数规划 掌握掌握线性整数规划的建模方法，特别是0-1变量的运用了解了解整数规划的求解方法掌握掌握指派问题的求解方法整数线性规划定义整数线性规划定义p要求全部或部分决策变量的取值为整数的规划问题，要求全部或部分决策变量的取值为整数的规划问题，称为整数规划称为整数规划( (Integer Programming) )。p要求全部或部分决策变量的取值为整数的要求全部或部分决策变量的取值为整数的线性线性规划规划问题，称为问题，称为整数线性规划整数线性规划( (Integer Linear Programming，ILP) )。n全部决策变量的取值都为整数，则称为全部决策变量

2、的取值都为整数，则称为全（纯）整数规划全（纯）整数规划n仅要求部分决策变量的取值为整数，则称为仅要求部分决策变量的取值为整数，则称为混合整数规划混合整数规划n要求决策变量只取要求决策变量只取0或或1值，则称值，则称0-1整数规划整数规划第一节第一节 整数规划问题整数规划问题整数规划的一般模型整数规划的一般模型应用与实例应用与实例 p在现实生活中，经常遇到一些需要变量取整数才有实际意义的问题，例如制定计划、规划时需要确定工人的人数，设备的台数等。p许多有名的最优化问题，如旅行商问题、背包问题、下料问题、工序安排问题等，也都可以归结为整数规划问题。整数规划建模举例整数规划建模举例产品资源甲乙现有量

3、A219B5735单台利润65例例1 1：某企业利用材料和设备生产甲乙产品，其工艺消耗某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示：系数和单台产品的获利能力如下表所示： 问如何安排甲、乙两产品的产量，使利润为最大。问如何安排甲、乙两产品的产量，使利润为最大。解：解：设设x1为甲产品的台数，为甲产品的台数，x2为乙产品的台数。为乙产品的台数。maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2 取整数取整数纯整数规划纯整数规划整数规划建模举例整数规划建模举例某财团有某财团有 万元的资金，经过其考察选中万元

4、的资金，经过其考察选中 个投资个投资项目，其中第项目，其中第 个项目需投资金额为个项目需投资金额为 万元，预万元，预计获利计获利 （ ）万元，由于种种原因，）万元，由于种种原因，有两个附加条件：第一，项目有两个附加条件：第一，项目2和项目和项目3至少选择一至少选择一个；第二项目个；第二项目5，6，7恰好选择两个。问应如何选恰好选择两个。问应如何选择项目使得总收益最大？择项目使得总收益最大？例例2：组合投资问题。：组合投资问题。Bnjcjanj.,2 , 1j要决策的是每个项目是否需要投资要决策的是每个项目是否需要投资10jjxj = 1,nj对项目 投资，()对项目 不投资1maxnjjjzc

5、 x例例2：组合投资问题。：组合投资问题。1235671. .210(1,2., )njjjja xBxxstxxxxjn或0-1整数规划整数规划例例3：某产品有某产品有n 个区域市场，各区域市场的需个区域市场，各区域市场的需求量为求量为 bj 吨吨/月；现拟在月；现拟在m 个地点中选址建生产厂，个地点中选址建生产厂，一个地方最多只能建一家工厂；若选一个地方最多只能建一家工厂；若选 i 地建厂，地建厂，生产能力为生产能力为 ai 吨吨/月，其运营固定费用为月，其运营固定费用为Fi 元元/月；月；已知址已知址i至至j区域市场的运价为区域市场的运价为 cij 元元/吨。如何选址吨。如何选址和安排调

6、运，可使总费用最小？和安排调运，可使总费用最小？解：解：选址建厂与否是个选址建厂与否是个0-1型决策变量，型决策变量， 设设 yi =1，选择第，选择第 i 址建厂，址建厂， yi=0，不选择第，不选择第 i 址建厂；址建厂；计划从计划从 i 址至区域市场址至区域市场 j 的运输运量的运输运量xij为实数型决为实数型决策变量。策变量。整数规划建模举例整数规划建模举例混合整数规划混合整数规划n特征特征变量整数性要求变量整数性要求n来源来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量的需要n性质性质可行域是离散集合可行域是离散集合整数规划整数规划松弛的线性规划松弛的线性规划整

7、数规划可行解是松弛问题可行域中的整数格点整数规划可行解是松弛问题可行域中的整数格点ILP最优值小于或等于松弛问题的最优值最优值小于或等于松弛问题的最优值第二节第二节 整数线性规划求解整数线性规划求解松弛问题无可行解，则整数规划无可行解；松弛问题无可行解，则整数规划无可行解；松弛问题最优解满足整数要求，则该最优解为整数松弛问题最优解满足整数要求，则该最优解为整数规划最优解；规划最优解；一、舍入化整法一、舍入化整法u为了满足整数解的要求，自然想到为了满足整数解的要求，自然想到“舍入舍入”或或“截尾截尾”处理，处理，以得到与最优解相近的整数解。以得到与最优解相近的整数解。 u这样做除少数情况外，一般

8、不可行，因为化整后的解有可能这样做除少数情况外，一般不可行，因为化整后的解有可能超出了可行域，成为非可行解；或者虽是可行解，却不是最超出了可行域，成为非可行解；或者虽是可行解，却不是最优解。优解。二、枚举整数法二、枚举整数法对于决策变量少，可行的整数解又较少时，这种枚对于决策变量少，可行的整数解又较少时，这种枚举法有时是可行的，并且也是有效的。举法有时是可行的，并且也是有效的。但对于大型的整数规划问题，可行的整数解数量很但对于大型的整数规划问题，可行的整数解数量很多，用枚举法求解是不可能的。多，用枚举法求解是不可能的。5x1 +7 x2 =352x1 + x2 =9x1x2123125344)

9、972,913(三、分支定界法三、分支定界法p不考虑整数限制先求出相应松弛问题的最优解，不考虑整数限制先求出相应松弛问题的最优解，n若松弛问题无可行解，则若松弛问题无可行解，则ILP无可行解；无可行解；n若求得的松弛问题最优解符合整数要求，则是若求得的松弛问题最优解符合整数要求，则是ILP的最优解；的最优解；p若不满足整数条件，则任选一个不满足整数条件若不满足整数条件，则任选一个不满足整数条件的变量的变量 来构造新的约束添加到松弛问题中形来构造新的约束添加到松弛问题中形成两个子问题成两个子问题n依次在缩小的可行域中求解新构造的线性规划依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述

10、过程，直到子问题无解的最优解，并重复上述过程，直到子问题无解或有整数最优解（被查清）。或有整数最优解（被查清）。0ix00;1iiiixxxx在分支的过程中，若当前已经得到的满足整数要求在分支的过程中，若当前已经得到的满足整数要求的最优值为的最优值为 ，则该，则该 就可是作为一个过滤条就可是作为一个过滤条件，对于最优值小于或等于件，对于最优值小于或等于 的子问题无需再分的子问题无需再分支，则这样的子问题称为被剪枝。未被剪枝的子问支，则这样的子问题称为被剪枝。未被剪枝的子问题需继续分支。题需继续分支。mzmzmz分支定界法的最终子问题要么被查清要么被剪枝。分支定界法的最终子问题要么被查清要么被剪

11、枝。11,P z22,P z12zz2P应该优先选取 进行分支。12121212max95114141s.t.23,0zxxxxxxx x且取整分支定界法求解举例分支定界法求解举例2x3 10,2301231231x7(1, )323(2,)92x3 10,2301231231x2x3 10,2301231231x33(,2)14104ILP3 ，所以子问题被剪枝，最优解为(2,2)或(3,1)最优值为4.122 23412,99L PxxZ：120 31 02 9,236L PxxZ：121 7101,33LPxxZ：4LP ：无解，查清1233 36 1,2 ,1 41 4L PxxZ：1

12、263,1,4L PxxZ：， 查 清x1 2x1 1x2 34 11 093x226 11 01 431252,2,4LPxxZ：， 查 清1 04 ,3L P 1被 剪 枝x12x1 3例例1 1 投资问题投资问题有有600万元投资万元投资5个项目，收益如表，求利润最大的方案？个项目，收益如表，求利润最大的方案？ 第三节第三节 0-10-1变量的使用变量的使用例例2 2、互斥约束问题、互斥约束问题 例如某种工序的约束条件为：例如某种工序的约束条件为： 企业也可以考虑一种新的加工工序：企业也可以考虑一种新的加工工序： 这两个工序只能选其一，是互相排斥的。引入这两个工序只能选其一，是互相排斥的

13、。引入01变量变量y，令，令 互斥问题可由下述的条件来代替，其中互斥问题可由下述的条件来代替，其中M是充分大的数。是充分大的数。 10y采用原工序采用新工序互斥约束的推广互斥约束的推广1(1,2, )nijjijpqa xb ip从下述 个约束条件中恰好选择 个约束条件0(1, )1iiyipi选第 个约束条件不选第 个约束条件11(1,2, )nijjiijpiia xbMyipypq互斥约束的推广互斥约束的推广1(1,2, )nijjijpqa xb ip从下述 个约束条件中恰好选择 个约束条件0(1, )1iiyipi选第 个约束条件不选第 个约束条件11(1,2, )nijjiijpi

14、ia xbMyipypq例例3 3 固定费用问题固定费用问题服装公司租用生产线拟生产T恤、衬衫和裤子。每年可用劳动力8200h，布料8800m2。T恤衬衫裤子劳动力326布料0.81.11.5售价250400600可变成本100180300生产线租金(万)201510假设：yj=1，要租用生产线j yj=0，不租用生产线j 第j 种服装生产量xj 例例4 4 逻辑变量逻辑变量0,3,5,7x可取中的一个123123357101(1,2,3)ixxxxxxxxi或例例5 5 二进制变量二进制变量012312342222xxxxx4x3x2x10 150 9x可取之间的整数012312341234

15、22229,01xxxxxx x x x 或第四节第四节 指派问题指派问题例例1 1甲乙丙丁四个人，甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？作，每项工作只由一人完成，问如何指派总时间最短？ 解：解： 引入引入0-1变量变量xij ， xij =1：第：第i人做第人做第j项工作项工作 xij =0：第：第i人不做第人不做第j项工作项工作 一项任务只由一个人完成一项任务只由一个人完成 一人只能完成一项任务一人只能完成一项任务指派问题标准形式指派问题标准形式有有 n 个人和个人和 n 项工作，已知第项工作，已

16、知第 i 个人做第个人做第 j 项工作项工作的代价为的代价为cij(i,j=1,n),要求每项工作只能交与其中一要求每项工作只能交与其中一人完成，每个人只能完成其中一项工作，问如何分配人完成，每个人只能完成其中一项工作，问如何分配可使总代价最少？可使总代价最少？111212122212()nnijn nnnnnccccccCcccciijj=指派问题的系数矩阵行元素第 个人完成各项工作的代价列元素各人完成第 项工作的代价指派问题数学模型指派问题数学模型1,1,0ijijxi jnij第 个人做第 项工作第 个人不做第 项工作111212122212()nnijn nnnnnxxxxxxXxxx

17、x=指派问题的解矩阵1.指派问题可行解中每行每列有且仅有一个1111min1(1, ). .1(1, )01( ,1, )nnijijijnijjnijiijzc xxinstxjnxi jn或指派问题的匈牙利解法的一般步骤指派问题的匈牙利解法的一般步骤Step1:系数矩阵的每行各元素减去该行中的最小系数矩阵的每行各元素减去该行中的最小元素；每列各元素减去该列中的最小元素使系数矩元素；每列各元素减去该列中的最小元素使系数矩阵的各行各列出现阵的各行各列出现0元素。转元素。转step2;Step2:若独立若独立0元素有元素有n个，则已得到最优解；否个，则已得到最优解；否则做出覆盖零元素的最少直线，

18、转则做出覆盖零元素的最少直线，转step3;Step3:在未被直线覆盖的元素中找出一个最小元在未被直线覆盖的元素中找出一个最小元素，对未被直线覆盖的元素所在行中各元素都减去素，对未被直线覆盖的元素所在行中各元素都减去该最小元素，对负元素所在列中各元素都加上该最该最小元素，对负元素所在列中各元素都加上该最小元素，转小元素，转step2.独立独立0 0元素的取法元素的取法圈出只有一个零元素的行（或列）中的圈出只有一个零元素的行（或列）中的0元素，同元素，同时把位于同列（或行）的其他零元素划去，如此反时把位于同列（或行）的其他零元素划去，如此反复，直至所有零元素都被圈或划去。若所有行与列复，直至所有

19、零元素都被圈或划去。若所有行与列中零元素都不止一个，可任选一个零元素加圈，同中零元素都不止一个，可任选一个零元素加圈，同时划去同行列的其他零元素。最后被圈的零元素即时划去同行列的其他零元素。最后被圈的零元素即是独立零元素。是独立零元素。若独立若独立0元素有元素有n个，则令零元素对应位置为个，则令零元素对应位置为1，其其余为余为0，得到的解矩阵即为最优解矩阵。，得到的解矩阵即为最优解矩阵。覆盖覆盖0 0元素的最少直线的做法元素的最少直线的做法（1）对没有圈）对没有圈0的行打的行打“”（2）已经打）已经打“”的行中，划掉的的行中，划掉的0所在列打所在列打“”（3）已经打）已经打“”的列中，圈出的的

20、列中，圈出的0所在行打所在行打“”（4）重复（）重复（2）（）（3），直至无法再打钩），直至无法再打钩 “”（5）对没有打）对没有打“”的行和打的行和打“”的列划线即可。的列划线即可。覆盖覆盖0元素的最少直线数等于独立元素的最少直线数等于独立0元素的个数元素的个数3584685425859252C=用匈牙利法求解例用匈牙利法求解例1 102512410036370300241240003537020113024101242703001303410024280300130341002428030102123011131803000203300013290310001001010000100所以该指派问题的最优解矩阵为即安排甲做工作即安排甲做