5运筹学课件整数线性规划

第六章整数线性规划整数线性规划模型及其与线性规划的区别整数规划的求解——分支定界法、割平面法0-1整数线性规划模型与求解指派问题模型与求解整数规划的应用——建模1第六章整数线性规划整数线性规划模型及其与线性规划的区别1一、整数线性规划的一般形式例1（P133）某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：货物体积(米3/箱)重量(百斤/箱)利润(百元/箱)甲乙54252010托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？第一节整数规划问题的提出2一、整数线性规划的一般形式例1（P133）某厂拟用集装箱托运1.整数线性规划模型的一般形式解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：xj部分或全部为整数31.整数线性规划模型的一般形式解：设托运甲、乙两种货物x1，（1）求解方法方面

2.ILP问题与一般LP问题的区别在例1中，ILP问题实际上，此ILP问题的最优解为：不考虑整数约束的最优解为：(1)X(1)=(5,0)T不是(1)的可行解X(2)=(4,0)T虽是可行解，但不是最优解4（1）求解方法方面2.ILP问题与一般LP问题的区做图分析例1的最优解(直观)ILP问题的可行域不是凸集（2）理论方面x1x24840

1235673

125x1+4x2=242x1+5x2=13(4.8,0)TZ=96(4,1)TZ=905做图分析例1的最优解(直观)ILP问题的可行域不是凸集（2二、整数线性规划的分类1.纯整数线性规划2.全整数线性规划在ILP问题（1）中，还要求aij,bi

全为整数。xj

全部为整数（1）4.0-1规划在ILP问题（1）中，要求xj＝0或1.3.混合整数线性规划在ILP问题（1）中，只要求部分xj为整数.6二、整数线性规划的分类1.纯整数线性规划2.全整数线性规划在一、几何解释适用范围：全整数线性规划、纯整数线性规划、混合整数线性规划例2（P135）求解整数线性规划问题第二节分支定界法

(BranchandBoundMethod)7一、几何解释适用范围：全整数线性规划、纯整数线性规划、例2（解：图解法。x1x2012345678910123456789x1+7x2=567x1+20x2=70BC问题B1Z1=349x1=4.00x2=2.10问题B2Z2=341x1=5.00x2=1.57x1<=[x(0)]x1>=[x(0)]+1X(0)=(4.81,1.82)Z0=3568解：图解法。x1x201234567891012345678二、分支规则情况2,4,5

找到最优解情况3

在缩减的域上继续分支定界法情况6

问题1的整数解作为界被保留，用于以后与问题2的后续分支所得到的解进行比较。9二、分支规则情况2,4,5找到最优解9满足要求?结束分支YN三、运算步骤解松弛问题10满足要求?结束分支YN三、运算步骤解松弛问题10例3

求解下列ILP问题

松弛问题的最优解为：X*=(5/2,2),Z*=23分支B1:

x1

2分支B2:x1

311例3求解下列ILP问题松弛问题的最优解为：X*=(5/2问题II的解即原整数问题的最优解可能存在两个分支都是非整数解的情况，则需要两边同时继续分支，直到有整数解出现，就可以进行定界过程。当存在很多变量有整数约束时，分支即广又深，在最坏情况下相当于组合所有可能的整数解。分支问题的松弛解货物问题I问题IIx1x229/431Z212212问题II的解即原整数问题的最优解可能存在两个分支都是非方法1：图解法x1x2012345678910123456782x1+x2=72x1+4x2=13X*=(5/2,2)Z*=23X*=(2,9/4)Z*=21X*=(3,1)Z*=2213方法1：图解法x1x20123456789101234567方法2：单纯形表cj

6400

CBXB

b

x1x2x3x44x2

6x125/2

011/3-1/310-1/62/3σj

-23

00-1/3-8/3松弛问题最优单纯形表如下：14方法2：单纯形表cj640将约束条件直接写入单纯形表：cj

6400

CBXBb

x1x2x3x44x2

6x1

25/2

011/3-1/310-1/62/3σj

-23

00-1/3-8/3cj

64000

CBXBb

x1x2x3x4

x54x2

6x1

0x525/2-1/2

011/3-1/3010-1/62/30001/6[-2/3]1σj

-23

00-1/3-8/300

x5210001x50000[1]15将约束条件直接写入单纯形表：cj64cj

64000

CBXBb

x1x2x3x4x54x2

6x1

0x49/423/4

011/40-1/21000100-1/41-3/2σj

-21

00-10-4将另一约束条件直接写入单纯形表：cj

6400

CBXBb

x1x2x3x44x2

6x1

25/2

011/3-1/310-1/62/3

σj

-23

00-1/3-8/30x6-3-10001x6000016cj6400cj

64000

CBXBb

x1

x2x3x4x64x2

6x1

0x625/2-1/2

011/3-1/3010-1/62/3000-1/62/31σj-23

00-1/3-8/30cj

64000

CBXBb

x1x2

x3x4x64x2

6x1

0x3133

010121000-1001-4-6σj-22

000-4-217cj640一、一个符号的说明适用范围：全整数线性规划第三节割平面法18一、一个符号的说明适用范围：全整数线性规划第三节割平面法二、Gomory约束的推导cj6400CBXBbx1x2x3x44x22011/3-1/36x15/210-1/62/3σj-2300-1/3-8/3例如1.令xi是松弛问题最优解中取值为分数的一个基变量，由最优单纯形表可得：19二、Gomory约束的推导cj6400CBXBbx1x2x把(2)(3)代入(1)并移项得：20把(2)(3)代入(1)并移项得：20例4

写出下列问题的Gomory约束cj6400CBXBbx1x2x3x44x22011/3-1/36x15/210-1/62/3σj-2300-1/3-8/3解：21例4写出下列问题的Gomory约束cj6400CBXBbAllxi

为整数?结束写出Gomory约束，并进行灵敏度分析YN例5三、计算步骤解松弛问题22Allxi为整数?结束写出Gomory约束，并进行解：cj

7900

CBXBb

x1

x2x3x49x2

7x1

7/29/2

017/221/2210-1/223/22

-63

00-28/11-15/110x5-1/200-7/22-1/221x50000解：由单纯形法计算得松弛问题的最优表23解：cj790cj

79000

CBXBb

x1x2x3x4x59x2

7x1

0x3332/711/7

010011001/7-1/70011/7-22/7-59

000-1-80x6-4/7000-1/7000x6001-6/7用对偶单纯形法进行计算，可得如下最优表24cj790cj

790000

CBXBb

x1x2

x3

x4x5

x6

9x2

7x1

0x30x43414

0100101000-110010-4100016-7

-55

0000-2-7同样用对偶单纯形法进行计算，可得如下最优表，此时xi的值都已经是整数，解题完成。25cj7900四、几何解释26四、几何解释26x1x201234567891012345678-x1+3x2=67x1+x2=35X(1)=(9/2,7/2)Z(1)=63x2=3X(2)=(32/7,3)Z(2)=59x1+x2=7X*=(4,3)Z*=5527x1x201234567891012345678-x1+3x一、问题的提出例6（P142例4）某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai供选择。规定

在东区，由A1,A2,A3三个点中至多选两个；在西区，由A4,A5两个点中至少选一个；在南区，由A6,A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择那几个点可使年利润为最大？则0-1规划模型为：第四节0-1整数线性规划28一、问题的提出例6（P142例4）某公司拟在市东、西、南三区0-1整数线性规划的一般形式290-1整数线性规划的一般形式293.不断更换过滤条件1.把目标函数的系数按升序排列[max]，约束条件做相应调整2.把所有的解按一定的次序排列例7（P144例6）用隐枚举法求解下列0-1规划问题二、隐枚举法求解0-1整数线性规划的思路303.不断更换过滤条件1.把目标函数的系数按升序排列[max]解：目标函数的系数按升序排列31解：目标函数的系数按升序排列31通过试探可行解(x1,x2,x3)=(1,0,0)引入下列过滤条件：点(x2,x1,x3)条件是否满足条件Z值

(0)

(1)

(2)

(3)

(4)

(0,0,0)(0,0,1)

05

-1

1

0

1

否是

0532通过试探可行解(x1,x2,x3)=(1,0,0)改进过滤条件：点(x2,x1,x3)条件是否满足条件Z值

(0‘)

(1)

(2)

(3)

(4)

(0,1,0)(0,1,1)

38

0

2

1

1否是

833改进过滤条件：点条改进过滤条件：点(x2,x1,x3)条件是否满足条件Z值

(0‘)

(1)

(2)

(3)

(4)

(1,0,0)(1,0,1)(1,1,0)(1,1,1)

-2316

否否否否

34改进过滤条件：点条1.结论任何一个非负整数y都可表示为2.0-1规划与全、纯整数线性规划的转换1)0-1规划问题就是全、纯整数线性规划问题2)全、纯整数线性规划问题可以利用上述结论转化为0-1规划问题三、0-1规划与全、纯整数线性规划的转换351.结论任何一个非负整数y都可表示为2.0-1规划与例8解：把代入纯整数规划的目标函数和约束条件即可。36例8解：把代入纯整数规划的目标函数和约束条件即可。36一、问题的提出例9

有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表所示，问如何分配任务使完成四项任务的总工时耗费最少？第五节指派问题任务工时人员ABCD人员甲乙丙丁109785877546523451111任务111137一、问题的提出例9有四个熟练工人，他们都是多面手，有四项任解：设则此指派问题的模型为：指派问题的一般形式：38解：设则此指派问题的模型为：指派问题的一般形式：38二、求解指派问题的理论依据定理1

在原指派问题的效率矩阵中同行或同列加上某一常数，所得指派问题与原问题同解。定理2

方阵中独立零元素的最多个数等于覆盖所有零元素的最少直线数。定理1的证明：39二、求解指派问题的理论依据定理1在原指派问题的效率矩阵以例1的求解为例：第一步：变换效率矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之三、匈牙利法步骤()()()()()40以例1的求解为例：第一步：变换效率矩阵，使每行每列至少有一个第二步：试指派1.逐行检查，若该行只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该行有二个或以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；

2.逐列检查，若该列只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该列有二个或以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；()*()*()*41第二步：试指派1.逐行检查，若该行只有一个未标记的零，对重复1、2后，可能出现三种情况：情况a：每行都有一个(0)，显然已找到最优解，令对应(0)位置的xij=1；情况b：仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用1、2中的方法继续标记。情况c：所有零都已标记，但标有()的零的个数少于n；划线过程：对没有标记()的行打

对打行上所有其它零元素对应的列打

再对打列上有()标记的零元素对应的行打

重复以上步骤，直至无法继续对没有打的行划横线，对所有打的列划竖线

3.打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记()；采用这种方法直至所有零都被标记，此时或出现情况a，或出现情况c。42重复1、2后，可能出现三种情况：划线过程：3.打破僵局。令未

划线后会出现两种情况：(1)标记()的零少于n个，但划有n条直线，说明矩阵中已存在n个不同行不同列的零，但打破僵局时选择不合理，没能找到。回到b重新标记；(2)少于n条直线，到第三步；43划线后会出现两种情况：43第三步：调整在未划线的元素中找最小者，设为

对未被直线覆盖的各元素减去

对两条直线交叉点覆盖的元素加上

只有一条直线覆盖的元素保持不变（以上步骤实际上仍是利用定理1）第四步：重新指派抹除所有标记，回到第二步，重新做标记；44第三步：调整第四步：重新指派44答：最优分配方案为x13=x21=x34=x42=1，其余为0，即甲

C，乙A，丙D，丁B，OBJ=20()*()**()*()45答：最优分配方案为x13=x21=x34=x42要求所有cij0若某些

cij<0

，则利用定理1进行变换，使所有

cij’

0要求目标函数为min型对于max型目标函数，将效率矩阵中所有

cij反号，则等效于求min型问题；再利用定理1进行变换，使所有

cij’0。例如：某公司要指派3名推销员去3个地区推销某种产品，各推销员在各地区推销该产品的预期收益见下表（单位：万元），试给出总收益最大的指派方案。

地区收益人员ABC甲乙丙151821192322261716注意46要求所有cij0例如：某公司要指派3名推销员去3个地区推例10（P149例8）求下列指派问题的最优解解：第一步，变换()()()()()47例10（P149例8）求下列指派问题的最优解解：第一步，变换第二步，试指派

()*()*()**()*48第二步，试指派()*()*()**(第三步，调整第四步，重新指派()*()*()*49第三步，调整第四步，重新指派()*()*(答：最优分配方案为x12=x23=x35=x44=x51=1，其余为0，

Z*=7+6+9+6+4=32()**()50答：最优分配方案为x12=x23=x35=x441.任务多、人少的情况分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表所示（单位：小时）。由于任务数多于人数，故规定其中有一个人可以完成两项任务，其余三人每人完成一项。试确定总花费时间最少的指派方案。思考任务时间人员ABCDE甲乙丙丁2529314237393826203334272840322442362345511.任务多、人少的情况分配甲、乙、丙、丁四个人假设增加一个人，记为戊，他完成各项工作的时间取甲、乙