1整数规划的数学模型2分枝定界法3割平面法40-1型整数规课件

1.整数规划的数学模型2.分枝定界法3.割平面法4.0-1型整数规划5.指派问题第五章整数规划2023/10/5整数规划的数学模型max(min)(c1

x1+c2x2+…+

cnxn)a11

x1+a12x2+…+a1nxn(=,)

b1a21

x1+a22x2+…+a2nxn(=,)

b2……...am1

x1+am2x2+…+amnxn(=,)

bmx1~n

0

且取整数纯整数规划:所有变量都有取整约束混合整数规划:只有部分变量有取整约束2023/10/5分枝定界法1.分枝定界法的基本思路2.第65页例5-13.练习题2023/10/5分枝定界法的基本思路

2023/10/5分枝定界法的基本思路2023/10/5第65页例5-1maxz=40x1+90x29x1+7x2567x1+20x270x1，x20且取整

2023/10/5用分枝定界法解例5-11.求解相应的线性规划L0maxz=40x1+90x29x1+7x2567x1+20x270x1，x202023/10/5用分枝定界法解例5-1

x2

59x1+7x2=56

4

3

27x1+20x2=70

1

0

12345678910

x1L0:x*=(4.81,1.82),Z*=356

2023/10/5用分枝定界法解例5-12.将L0分解为L1和L2L1：maxz=40x1+90x29x1+7x2567x1+20x270

x1

4x1，x20L2：maxz=40x1+90x29x1+7x2567x1+20x270

x1

5x1，x20L1：X*=(4,2.10),Z*=349

L2：X*=(5,1.57),Z*=341

2023/10/5用分枝定界法解例5-13.分解L1形成L3、L4，其中：

L3={L1,x22}L4={L1,x23}

L3:X*=(4,2),Z*=340

L4:X*=(1.42,3),Z*=327(1)取下界min=340(L3);(2)舍弃L42023/10/5用分枝定界法解例5-14.分解L2形成L5、L6，其中：

L5={L2,x21}L6={L2,x22}

L5:X*=(5.44,1),Z*=308

L6:无可行解(1)舍弃L5、L6；(2)得最优解X*=(4,2),Z*=340。

2023/10/5例5-1求解过程示意图L0(4.81，1.82)356L1(4，2.1)349L2(5，1.57)341L3(4，2)340L4(1.42，3)327L5(5.44，1)308L6无可行解2023/10/5练习题maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整2023/10/5求解练习题首先求解线性规划L0:maxz=2x1+5x2+4x3x1+x2+x3+x4=12x1+2x2+x5=154x1+5x3+x6=26x1~602023/10/5求解练习题

2023/10/5求解练习题

2023/10/5求解练习题

2023/10/5求解练习题

2023/10/5求解练习题L0（0，15/2，9/2）111/2

L1（0，7，5）55

L2无可行解2023/10/5割平面法1.割平面法的基本思路2.例3.练习题2023/10/5割平面法的基本思路同分枝定界法一样，割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。2023/10/5例maxz=x1+x2-x1+x213x1+x24x1，x20且取整

2023/10/5用割平面法解例1.求解相应的线性规划L0maxz=x1+x2-x1+x213x1+x24x1，x20

2023/10/5用割平面法解例非整数解，为建立割平面，首先考虑非整数解中余数最大的基变量，此例中x1、x2的余数均为3/4，不妨选取x2：x2+3/4x3+1/4x4=7/4

2023/10/5用割平面法解例

x2+3/4x3+1/4x4=7/4现将各系数分成整数和非负真分数两部分，从而可得：(1+0)x2+(0+3/4)x3+(0+1/4)x4=(1+3/4)将整数部分的变量移至等式右端有：3/4x3+1/4x4=3/4+（1-x2）非负整数解(1-x2)为整数，左端非负故有：3/4x3+1/4x4=3/4+非负整数从而：3/4x3+1/4x4

3/4或x2

1以x2

1为割平面可使可行域减少一个包括A点在内的三角形。

2023/10/5x2A1

01x1用割平面法解例

2023/10/5用割平面法解例2023/10/5练习题maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整

2023/10/5求解练习题

2023/10/5求解练习题选取x2：1/2x1+x2+1/2x5=15/21/2x1+1/2x5=1/2+（7-x2）

于是有割平面：1/2x1+1/2x5

1/2或

x272023/10/5求解练习题

2023/10/5求解练习题2023/10/50-1型整数规划1.0-1规划：0-1规划是整数规划的特例，是所有决策变量仅取0和1的整数规划问题。2.引例（1）第69页例5-3（2）引例23.0-1规划的隐枚举法（1）隐枚举法的基本步骤（2）第70页例5-4（3）第71页例5-52023/10/5第69页例5-3

某公司拟在东、西、南三个区建立销售门市部，拟议中有7个场点A1~7可供选择。东区的三个点A1~3最多选两个，西区的两个点A4~5最少选一个，南区的两个点A6~7最少选一个。如果建设Ai点，需要投资bi元，年可获利ci元，公司可筹集到的投资总额为B元，问应如何决策才能使年利潤最大。

2023/10/5例5-3

令xi=0或1，其中：

xi=0表示第I个点未被选取

xi=1表示第I个点被选取其数学模型为：

x1+x2+x32x4+x51

x6+x71

2023/10/5引例2

两种运输方式的限制条件分别为：6x1+4x2307x1+3x240互斥的约束统一于一个模型中：6x1+4x230+Mx37x1+3x240+M(1-x3)

其中x3为0-1变量。2023/10/5隐枚举法的基本步骤

1.目标函数极小化；2.目标函数系数非负化，如果xj的系数为负数，可令xj=1-xj

；3.决策变量按其目标函数系数的大小排列；4.令所有变量为“0”，检查该解的可行性，如果可行此解即为最优解，如果不可行进入下一步；5.按变量的顺序依次令各变量分别取“0”或“1”，根据分枝定界的原理进行剪枝，直至结束。2023/10/5第70页例5-4Maxz=3x1-2x2+5x3

x1+2x2-x32x1+4x2+x34x1~3=0或1第一步：Minw=-3x1+2x2-5x3

x1+2x2-x32x1+4x2+x34x1~3=0或1

2023/10/5例5-4第二步：令x1=1-x1，x3=1-x3Minw=3x1+2x2+5x3

-8-x1+2x2+x32-x1+4x2-x32x1~3=0或1第三步：Minw=2x2+3x1+5x3

-8

2x2-x1+x32

4x2-x1-x32x1~3=0或1第四步：令所有变量为“0”，得可行解，所以原问题的最优解为（1，0，1），最优值为8。2023/10/5maxz=8x1+2x2-4x3-7x4-5x5

3x1+3x2+x3+2x4+3x54

5x1+3x2-2x3-x4+x54

x1~5=0或1经前三步有：令x1=1-x1，x2=1-x2minw=2x2+

4x3+5x5+7x4+8x1-10

3x2-x3-3x5-2x4+3x12

3x2+2x3-x5+x4+5x14

x1~5=0或1

第71页例5-52023/10/5

例5-5

w=-8

x2=12

w=-101

x2=0

w=-63

2023/10/5

例5-5

w=-44(可行解)

w=-8x3=1x2=12w=-10x3=0w=-315x2=0w=-632023/10/5例5-5

w=-6x5=18w=-1x3=16x5=0w=-69w=1w=23x3=0w=-5x4=112w=-5x5=1107x5=0w=-3x4=0w=311132023/10/5指派问题

1.指派问题的内涵2.指派问题的数学模型3.指派问题的求解4.指派问题的扩展2023/10/5指派问题的内涵

有m项工作，恰好有m个人来完成，一个人只完成一项工作，一项工作只由一个人来完成，由于个人的专长不同，完成任务的效率也就不同，于是产生了应指派哪个人去完成哪项任务，才能使完成m

项任务的总效率最高的问题，此类问题称为指派问题或分派问题。指派问题同运输问题一样，是具有一定模型特征一类问题的总称，如m项加工任务如何在m台机床上分配；m

条航线如何指定m

艘船去航行等等。指派问题是运输问题的特例，也是0-1规划问题的特例。这一点可由指派问题的数学模型体现出来。2023/10/5指派问题的数学模型2023/10/5指派问题的求解－匈牙利法2.匈牙利法的基本步骤(1)第73页例5-6(2)第74页例5-7(3)基本步骤总结2023/10/5指派问题的扩展

1.人员与工作不匹配：引入假想的工作或人员由于假想的工作或人员代表的是剩余的工作或人员，所以其对应的效率矩阵元素全都为零。

例2.目标函数求极大值：效率矩阵的每一元素乘“-1”，并进一步使其非负化。

第73页例5-62023/10/5第73页例5-6

2023/10/5例5-62023/10/5第74页例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-72023/10/5基本步骤总结

1.每行减去一个最小元素；2.每列减去一个最小元素；经此两步，效率矩阵每行、列都至少有一个“0”。3.每行、列若只有一个“0”元素，打上“（）”，同时划去与其同列、行的其它零元素，先前已被划去的零元素不计算在内，如果出现零元素的闭合回路，则任选一个零元素打上“（）”，同时划掉与其同行和同列的零元素。经过第三步可能出现两种结果：(1)每行均有打“()”的零元素,此时已得最优解;(2)并非每行均有打“()”的零元素，进入第四步。4.给没有“(0)”的行做标记“”；5.在做“”标记的行上对所有“0”所在的列做标记“”；6.覆盖掉没有“”标记行上的所有元素和有“”标记列上的所有元素。经过此步矩阵中的所有“0”均被覆盖掉了，只留下了部分非零元素。7.每一非零元素减去它们中的最小值，并给同时处在被覆盖掉行和被覆盖掉列的元素加上这一最小值。8.重复3~7直至得到最优解。2023/10/5例1279798966671712141215146610

2023/10/5例127979896667171214121514661000000

2023/10/5例5(0)20223(0)00(0)10575980(0)40000(0)方案1:甲-B、乙-C、丙-A、丁-D工作E剩余，minz=26

2023/10/5例502(0)22300(0)