第三章整数规划

1、整整 数数 规规 划划 3.1 3.1 整数规划问题的提出整数规划问题的提出一、整数规划问题的特征：一、整数规划问题的特征： 变量取值范围是离散的，经典连续数学中变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规的理论和方法一般无法直接用来求解整数规划问题。划问题。二、建模中常用的处理方法：二、建模中常用的处理方法： 1 1、资本预算问题：、资本预算问题： 设有设有n n个投资方案，个投资方案，c cj j为第为第j j个投资方案的收个投资方案的收益。投资过程共分为益。投资过程共分为m m个阶段，个阶段，b bi i为第为第i i个阶段个阶段的投资总量，的投资总量，a

2、aijij为第为第i i阶段第阶段第j j项投资方案所项投资方案所需要的资金。目标是在各阶段资金限制下使需要的资金。目标是在各阶段资金限制下使3.13.1二、建模中常用的处理方法：二、建模中常用的处理方法： （续）（续）整个投资的总收益最大。整个投资的总收益最大。njxmibxatsxczjxjnjijijnjjjj,2,110,2,1.max0,111或得到模型：，否则项投资对第设决策变量3.13.1二、建模中常用的处理方法：二、建模中常用的处理方法： （续）（续）1000nijjijijijijiiia xbiaijaabibb约 束反 映 第 阶 段 资 金 增 长 量 的 平 衡 。代

3、 表 在 第 时 期 内 第 项 投 资 的 净 资 金 流 量 ：表 示 需 附 加 资 金 ；表 示 产 生 资 金表 示 第 阶 段 外 源 资 金 流 量 的 增 长 量 ：表 示 有 附 加 资 金表 示 要 抽 回 资 金3.13.1二、建模中常用的处理方法：二、建模中常用的处理方法： （续）（续）2 2、指示变量：指示不同情况的出现、指示变量：指示不同情况的出现 例例. .有有m m个仓库，要决定动用哪些仓库，满足个仓库，要决定动用哪些仓库，满足n n个顾客对货物的需要，并决定从各仓库分别个顾客对货物的需要，并决定从各仓库分别向不同顾客运送多少货物？向不同顾客运送多少货物？顾客运

4、送的货物量到从仓库为指示变量否则仓库动用令jixymiiyijii:)(,2,1013.13.1二、建模中常用的处理方法：二、建模中常用的处理方法： （续）（续）费用：费用： f fi i: :动用动用i i仓库的固定运营费（租金等）仓库的固定运营费（租金等） c cijij: :从仓库从仓库i i到到j j顾客运送单位货物的运费顾客运送单位货物的运费约束条件：约束条件： i)i)每个顾客的需要量每个顾客的需要量d dj j必须得到满足；必须得到满足； ii)ii)只能从动用的仓库运出货物。只能从动用的仓库运出货物。3.13.1二、建模中常用的处理方法：二、建模中常用的处理方法： （续）（续）

5、njmiyxnjxymidyxnjdxtsyfxcfiijijinjnjjiijmijijminjmiiiijij, 1;, 2 , 110, 0), 2 , 1, 00(, 10, 2 , 1. .min111111或时，当3.线性规划模型的附加约束线性规划模型的附加约束(1)控制约束条件是否需要：控制约束条件是否需要：) 1() 1(1020, 1101111个变量取至多个变量取至少或）（成立），则原约束失效（永远即原约束需要的上界为，或取kkxkkxxyxaMyMbMyxanjjnjjjinjjijiinjiiiijij（求最小）在目标函数中加入一项于是，把约束变为：否则约束取处理：引入

6、其中：约束离散的资源变化：kiiikiinjkiiijjiikijjnjybyybxabybbbbkibxa111121011001,1 ,0,)3(3.1 3.1 三、整数规划解法概述三、整数规划解法概述.2),2, 1)()(,2, 1,)()(2);()()()(1:,),(,2121mmjPmPjimjiPSPSPSPSPSPSPPPmPSPjjimm常用的分解又常称为分枝。较之和，个子问题分解为称满足个子问题有可行解集）设规划问题（一、分解：常用的主要技术：3.1 3.1 三、整数规划解法概述三、整数规划解法概述( (续续）.)(),(.)(3;)()(2)(),()(1min,)(

7、)()(optPxPSxoptPfffPfPPPPSPSPPP的是则的若的一个下界，即最优值是最优值无可行解；）无可行解，则特别若（那么，有下列性质：是求设问题）。可得到松弛问题（删去某些约束，把约束条件放宽问题二、松弛：3.1 3.1 三、整数规划解法概述三、整数规划解法概述( (续续）)(, 2 , 1|min)()(. 1,)()(,)()( ,)(., 2 , 1,),( ,),(),()(21约束得到的子问题是原问题上增加下界新，可计算：分解之后的上下界问题问题为最优目标值的上、下界及的最优值为及的最优值记）（各子问题分解为子问题设问题三、剪枝：ffmjffffffPffffPPfP

8、PfPmiPPPPPjjjjjjjjjjjm3.1 3.1 三、整数规划解法概述三、整数规划解法概述( (续续）大大。再再分分解解只只能能使使目目标标值值增增大大。再再分分解解只只能能使使目目标标值值增增当当前前的的若若。肯肯定定子子问问题题解解集集均均为为在在分分解解是是增增加加约约束束，故故说说明明无无可可行行解解，即即若若式式进进行行。用用逐逐步步分分解解子子问问题题的的方方计计算算整整数数规规划划问问题题常常采采分分解解，即即称称剪剪枝枝：以以下下几几种种情情况况，不不必必再再上上界界新新的的可可行行解解对对应应目目标标值值。有有可可取取各各子子问问题题,3,);(.)(2,)(,)(

9、)(1.2,min)(1jjjjjjjjjjmjjjfffffPSxoptPPSPSPfffffffPf 3.2 3.2 整数规划的分枝定界法整数规划的分枝定界法LPXbAXtsAXCfBnjxXbAXtsXCfATjT标准问题的松弛为整数，设线性整数规划问题：0.min)(,2,10.min)(3.23.2整数规划的分枝定界法整数规划的分枝定界法 （续）（续）)(,)(22)()(),(,)()(,)B()()(),(1xffSxAAxffASxxBiiiASxxiiABiBAA那么取任一最优值的一个下界：可找最优值的的下界，转为而有最优解若的解。得到则停（剪枝）且有最优解若无可行解；）说明

10、无可行解，则停（剪枝若求解）分枝定界法：（一般步3.2 3.2 整数规划的分枝定界法整数规划的分枝定界法 （续）（续）重复上述求解过程。中得到两个子问题分别加入把构造两个约束条件：找不等于整数的分量）分枝：对于上述（分枝与定界：以下进行分枝和定界：),(),()()(),()(1)(,1.1212121AAAcccxxcxxxSxstepiiiiiA3.23.2整数规划的分枝定界法整数规划的分枝定界法 （续）（续）最最优优解解。界界对对应应的的解解即即原原问问题题的的均均得得到到剪剪枝枝时时，当当前前上上部部子子问问题题述述过过程程进进行行分分枝枝。当当全全对对于于未未剪剪枝枝问问题题重重复复

11、上上，”的的方方法法考考察察剪剪枝枝问问题题三三按按“比比较较与与剪剪枝枝。和和下下界界层层的的上上界界”的的方方法法找找到到当当前前三三定定界界（估估界界）：按按“22 . 8. 212 . 8)2(stepff3.23.2整数规划的分枝定界法整数规划的分枝定界法 （续）（续）)(31857.2)(2857.222)3,2(714.29)857.3,857.2()()(,0,45592443.45min)(21112121212121cxcxfffxBBxxxxxxxxtsxxfATT分枝约束：得上界找一可行解记得解：先解为整数例：3.23.2整数规划的分枝定界法整数规划的分枝定界法 （续）

12、（续）)(,0,345592443. .45min)()(,0,245592443. .45min)(22121121212121212112121211Bxxxxxxxxxt sxxfABxxxxxxxxxt sxxfA整数整数两个子问题：3.43.4割平面法割平面法割割平平面面法法。的的解解。的的整整数数解解即即直直到到得得到到弛弛问问题题。重重复复这这个个过过程程的的可可行行解解，得得到到新新的的松松但但不不丢丢失失任任何何不不可可行行，约约束束使使不不是是整整数数解解，增增加加一一个个，若若解解解解松松弛弛问问题题取取整整数数一一、基基本本思思想想：GomoryAAAxxBBxXbAX

13、tsXCAjT)()()()()(0.min)( 8.48.4割平面法割平面法 （ 续）续）最后单纯形表为：设的解。为即当的非负小数部分，即）表示（其中取为非基变量。为基变量，其中的解为无妨设二、求割平面方程：, 0)()(0)()()( ,),(),max()(),()(212121rrmrijTnmmmxAxxxxxxyxyyyxxxxB8.48.4割平面法割平面法 （ 续）续） x1 xr xm ym+1 ym+2 yn RHS 0 0 0 m+1 m+2 nf*x1.xr.xm1 0 0 a1m+1 a1m+2 a1n . 0 1 0 ar m+1 ar m+2 ar n . 0 0

14、1 am m+1 a m m+2 am nb1.br.bm8.48.4割平面法割平面法 （ 续）续）于于是是数数。均均为为整整，即即当当（最最优优）解解为为整整数数时时）（式式两两端端部部分分与与小小数数部部分分移移到到等等把把右右端端的的各各系系数数整整数数根根据据单单纯纯形形法法原原理理知知：ijnmjjrjrrnmjjrjrnmjjrjrryxyabxyabyabx,)(111 8.48.4割平面法割平面法 （ 续）续）附附加加约约束束）（得得到到又又是是整整数数，小小于于）于于是是（由由整整数数）（ 0)(.11)()(0)(0, 1)(0)(1111nmjjrjrrnmjjrjrnm

15、jjrjjrjnmjjrjryabbyabyayayab8.48.4割平面法割平面法 （ 续）续）纯形表：解：松弛问题的最优单取整数例：0,431. .min432142132121xxxxxxxxxxtsxxf x1 x2 x3 x4RHS 0 0 -1/2 -1/2-5/2x1 x21 0 -1/4 1/4 0 1 3/4 1/43/4 7/43.53.5割平面法割平面法 （ 续）续）为为松松弛弛变变量量得得附附加加约约束束：或或取取0434143025. 075. 075. 0)1(275. 0)()(55434321 xxxxxxrxx得到新的对偶单纯形表得到新的对偶单纯形表 x1 x

16、2 x3 x4 x5 RHS 0 0 -1/2 -1/2 0-5/2x1 x2 x31 0 -1/4 1/4 0 0 1 3/4 1/4 0 0 0 -3/4 -1/4 1 3/4 7/4 -3/4 进一步得到最优单纯形表进一步得到最优单纯形表: : x1 x2 x3 x4 x5 RHS 0 0 0 -1/3 -2/3-2x1 x2 x31 0 0 1/3 -1/3 0 1 0 0 1 0 0 1 1/3 -4/31 1 12)0,0, 1, 1, 1( fxT最最优优解解3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法min( ). .011,2,( )01.01Tjmm nTjjf

17、C XAstAXbxjnAbRBxfC XxAXb一、隐枚举法的基本思想：问题或其中矩阵，松弛问题固定或 ，求利用分别固定或 进行分枝，根据目标函数值及约束来决定是否剪枝。3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 （续）（续）101min( ). .0,1,1,njjjjfc xPs tAxbxjn二、用于隐枚举法的线性规划标准形式：其中，目标函数系数其中，目标函数系数 cj 0.以下讨论一般形式的以下讨论一般形式的01规划如何化为标规划如何化为标准形式：准形式：3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )111012kkknijjijnijjij

18、nijjijcyxa xba xbaxb 当某时，取代换即可。当某时，可产生 个不等式（）（）3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )11( ),.000(0)00,010,()( )AxfxfAXbffxxfxxA三、隐枚举法：设的最优解为最优值为首先，时，是不考虑约束时的最小解，故有是 的一个下界此时若是可行解，则得到最优解否则取及其余变量仍取零 不变把分解为两个子问题。3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )123,01010111011.011jxxxkkxk一般迭代步：从 开始，逐步向后分别对取 与 进行分枝，在每一

19、个点的基础上，第 个变量取 或 后，前个不再变化。考察当前的点（“”解，选定前 个分量）情况若已知在子域（在当前“”解的基础上再增加 的分量）上均不可行，剪枝；3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )1112.,;3()41 31,0,TTkkkAxbfc xfffc xfxxx情况当前解满足线性约束则不必再分枝，当前的目标值为一个上界，即情况当前解的函数值当前最小上界 ，剪枝；情况若非上述情况，则继续对下一变量进行分枝，即令分成两枝。3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )12312312313231232( ),.max3

20、25. .22441.346,0,1Afxzxxxs txxxxxxxxxxx xx按某一顺序考察各点，当各分枝均被剪枝时，最小的上界即的最优值其对应的解为最优解例或3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )1231122331233251,132588fzxxxyx yx yxfyyyf 解：先化标准形取令得到问题记3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )1231231231223123m in325. .2242245,0100,0(1, 0,1)8Tfyyys tyyyyyyyyyyyyyyyfxzf 或由 于可 行 ，

21、于 是3.3 0-13.3 0-1规划的隐枚举法规划的隐枚举法 ( (续续) )12341234123412342341234min100304045. .5030251020722442.21021,01(0,1,0,1)75Tfyyyys tyyyyyyyyyyyyyyyyyyyyf 例或解：得3.4 3.4 指派问题指派问题nnAssignmentproblemnnnn一、指派问题（分派问题）：项任务要分配给 个人（每人一项）去完成，各人对完成不同任务的效率不同，决定如何指派可使总效率最高。类似有：台机床加工 项任务；条航线有 艘船去航行等。11111.0 :10min. .1,1,()

22、1,1,01ijijnnijijijnijinijjijcijijxfc xs txjnPxinx一般模型：设第 个人完成第 项任务的效率（时间成本等）第 个人完成第 项任务引入否则模型：每项任务一人每人一项任务或3.43.4指派问题指派问题 ( (续续) )111212122212nnnnnnccccccCccc数据集中在下列系数矩阵上：3.43.4指派问题（续）指派问题（续） kiackicbakCproofBbBaCPkjijijnmij那那么么，行行各各元元素素加加上上的的第第设设从从与与原原问问题题有有相相同同的的解解。为为系系数数矩矩阵阵的的分分派派问问题题以以那那么么得得到到矩矩

23、阵阵加加上上同同一一个个实实数数素素中中的的一一行行（或或一一列列）各各元元若若从从矩矩阵阵的的最最优优解解的的性性质质：关关于于问问题题,.,)()(. 23.4 3.4 指派问题（续）指派问题（续）响最优解。目标函数的常数项不影目标函数：afxaxcxbfnkiinjkjnjijijninjijij11111347100320460315310),2(),5(),2(),2(43219322875982537532列列减减第第得得行行分分别别加加，第第例例：性性质质应应用用： C11233452(0)13213(0)3402(0)0(0)141228214xxxxfn 得显然是一组最优解，

24、相应最小费用注：可行解特征：各行有一个零，且仅有一个零各列有一个零，且仅有一个零称之为有 个独立的零。3.43.4指派问题（续）指派问题（续）3.( .)013420603.059332706D KonigEx关于独立元素的定理匈牙利系数矩阵中独立零元素的最多个数等于覆盖所有零元素的最少直线数。至少有 个独立零元素至少 条直线覆盖所有零l3.43.4指派问题（续）指派问题（续）nmmn注：这里提供的一种“对偶”关系找最多的独立零个数 （独立零个数为 ）找最少的覆盖全部零的直线数（覆盖零的直线数 ）有l3.43.4指派问题（续）指派问题（续）min,01.2.1(0) ,0stepstep二、匈

25、牙利法求解分派问题：设求各元素对矩阵的每一行（每一列）分别减去该行（列）各元素的最小值，反复进行，至每行、每列均有零元素；试派，即找独立零元素：对每行检查，若当前行中只有一个零元素，则给它加圈，标为“” 同时把该元素所在列的其他零元素划去，标为“ ”；l3.43.4指派问题（续）指派问题（续）2(0(0),01 2对每列检查，若当前列中只有一个零元素 划去的零 不算），给它加圈，标为同时把该元素所在的行的其它零元素划去，标为“ ”；反复执行 ，直到所有行、列中单个零元素均被处理。3.43.4指派问题（续）指派问题（续）31(0) ,01 2 3.1,0,3.ijijmmnxxmnstep若同行

26、（列）中零元素均多于 个，类似上述办法：选零元素个数较少的行或列，把其中任一个零元素加圈“”同时把该元素所在的行与列的其它零元划去“ ”；反复进行 ，直至所有的零元素被处理。记加圈零的个数为当时，停止，所加圈零对应的其余即为最优解。当时，转3.43.4指派问题（续）指派问题（续）3.1203(0)2 3step确定覆盖全部零元素的最小直线数。对无加圈零元素的行作记号，无妨记“ “；对有“ ”行中，划去零“ ”元素所在列，记“ ”；再对有“ ”列中，加圈零“”元素所在行，记“ ”；重复，直到得不出新记“ ”的行，列为止。l3.4 3.4 指派问题及解法（续）指派问题及解法（续）4.4.2()ll

27、nsteplnstep对所有无“ ”的行画一横线；对所有有“ ”的列画一纵线，记总线数当时，转当时，转说明试探不成功，重新试派l3.33.3指派问题（续）指派问题（续）4.2.stepstep变换矩阵，以增加零元素的个数，但不得出现负元。设无直线覆盖部分中的最小元素为 ，对所有记“ ”的行中各元素减去 ，所有记“ ”的列中各元素加上 。转l3.43.4指派问题（续）指派问题（续）7 6 7 6 4127979896661. 71712149151466104107109减各行最小元，例l3.43.4指派问题（续）指派问题（续）50202230000105729800406365l3.43.4分

28、派问题及解法（续）分派问题及解法（续）5(0)2024230(0)04(0)10572298(0)0406365mll3.43.4指派问题（续）指派问题（续）*1223354451*7(0)20243(0)000835(0)1180(0)4(0)414317696432xxxxxf 11011110100111110001111100011111111000011110000111110001111111002例例 11)0(111101)0(011111)0(001111100011111111000)0(1111)0(0001111100)0(11111110)0(试试派派!1101111)0(1)0(01111100)0(11111)0(0011111111)0(00011110)0