第一、二节提出问题及分枝与定界

1、第五章第五章 整数规划整数规划 在许多线性规划问题中,要求最优解必须取整数. 例如所求的解是机器的台数、人数、车辆和船只数等. 如果所得的解中有分数或小数则不符合实际问题的要求. 对于一个线性规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划; 如果仅要求部分决策变量取整数,称为混合整数规划问题. 有的问题要求决策变量仅取0或l两个值,称为0-1规划问题. 第五章第五章 整数规划整数规划5.15.1 整数规划问题的提出5.25.2 分枝定界法5.35.3 割平面法5.45.4 0 0-1 1规划及隐枚举法5.55.5 指派问题* *5.1 5.1 整数规划问题的提出自学5.25.2

2、 分枝定界法整数规划（A）松弛问题（B）1maxnjjjSc x 1(1,)nijjija xb im 0jx 且为整数且为整数1maxnjjjSc x 1(1,)nijjija xb im 0jx 则必有：（A）的可行域 （B）的可行域 （A）的最优值 （B）的最优值 例如例如 求解整数规划问题12121212max58 65945,0Sxxxxxxxx 且为整数()A()B12121212max58 65945,0Sxxxxxxxx 的可行域()B1234561234567891x2x12 6xx 12 5945xx (2.25,3.75)()B12121212max58 65945,0S

3、xxxxxxxx 的可行域()A1234561234567891x2x12 6xx 12 5945xx (2.25,3.75)12121212max58 65945,0Sxxxxxxxx 且为整数()A的可行域()A1234561234567891x2x12 6xx 12 5945xx (6,0)(5,1)(5,0)(4,2)(4,1)(4,0)(3,3)(3,2)(3,1)(3,0)(2,3)(2,2)(2,1)(2,0)(0,5)(0,4)(0,3)(0,2)(0,1)(0,0)(1,4)(1,3)(1,2)(1,1)(1,0)(2.25,3.75)12max58 Sxx 显然，对于整数规

4、划问题来说 ，先求其松弛问题的最优解是一个正确的方向 但是，用“舍入取整法”，把松弛问题的最优解临近的整数解作为原问题的最优解是不对的 分支定界法是解决整数规划比较有效的一个方法例例1 1 求解整数规划问题12121212max58 65945,0Sxxxxxxxx 且为整数()A0()B12121212max58 65945,0Sxxxxxxxx 解（1 1）用图解法或单纯形法求解问题 ， 得最优解为0()B1202.25,3.75,41.25xxS 下界 上界S S *041.25AS 121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max5

5、8 2059454,0Sxxxxxxxxx 1()B的最优解为0()B1202.25,3.75,41.25xxS 将问题 分解为 和 两个子问题23.75x 0()B1()B2()B23.753x 选 进行分枝，增加约束条件23.7514x 和121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max58 2059454,0Sxxxxxxxxx 1()B1213,3,39xxS 1221.8,4,41xxS 041.25SS 取新的下界,新的上界39S 41S 接下来对问题 进行分枝2()B11.81x 增加约束条件11.812x 和将问题 分解为

6、和 两个子问题4()B3()B2()B4()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B1212122112max58 20594542,0Sxxxxxxxxxx 123451,4,4099xxS 无可行解4()B取新的上界5409S 3941SS 接下来对问题 进行分枝3()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B123451,4,4099xxS 24x 增加约束条件25x 和将问题 分解为 和 两个子问题6()B5()B3()B6()B12121221212max58 205945414,0Sxxxxx

7、xxxxxx 5()B12121221212max58 205945415,0Sxxxxxxxxxxx 1251437xxS 1260540 xxS 3941SS 都是整数解56() ()BB、而 , 故为最优值.6SSS 分支定界法的主要内容就是分枝和定界而定界是指通过求解松弛问题及其子问题，确定原问题的上下界，并不断缩小其范围，最终得到原问题的最优值及最优解所谓分枝，就是通过不断增加约束条件，将松弛问题分成若干个子问题整数规划（A）松弛问题（B）1maxnjjjSc x 1(1,)nijjija xb im 0jx 且为整数1maxnjjjSc x 1(1,)nijjija xb im 0

8、jx 回到一般问题上： 首先，求解(B)，确定(A)的最优值的初始上下界，有三种情况： （1）若(B)无可行解，则(A)也无可行解,停止计算； （2）若(B)有最优解，且为整数，则(B)的最优解也是(A)的最优解，停止计算； （3）若(B)有最优解，但不全为整数，这时(B)的最优解不是(A)的可行解，但是(B)的最优值是(A)的最优值的上界分枝定界法的主要步骤设(B)的最优值为， (A)的最优值为*BS*AS则必有*0ABSS 定初始上界 ，初始下界*=BS S=0S即*ASSS 接下来通过分枝与定界不断提高下界，降低上界，缩小范围，最终确定的值*AS设（B）的最优解为：若其中不是整数，则必有

9、这时，增加约束条件 *12TnXxxx *kx* 1kkkxxx *kkxx *1kkxx 构造（B）的两个子问题 和1()B2().B 和子问题的解可能有如下三种情况：1.有整数最优解，但其最优值小于原来的下界2.有整数最优解，其最优值大于原来的下界3.无整数最优解则将其剪枝剪掉，不再考虑则将其值作为新的下界否则，选取最优值较大者作为新的上界，然后重复上述步骤，继续分枝若其最优值小于原来的下界，则将其剪掉； 如果某一个子问题无可行解或者最优值小于原来的下界，则称这个分支已经查清，将该枝剪掉，不再计算，所谓“剪枝”例例1 1 求解整数规划问题12121212max58 65945,0Sxxxx

10、xxxx 且为整数()A0()B12121212max58 65945,0Sxxxxxxxx 解（1 1）用图解法或单纯形法求解问题 ， 得最优解为0()B1202.25,3.75,41.25xxS 取下界,上界0S 41.25S 121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max58 2059454,0Sxxxxxxxxx 1()B的最优解为0()B1202.25,3.75,41.25xxS (2) (2) 分枝与定界将问题 分解为 和 两个子问题23.75x 0()B1()B2()B23.753x 选 进行分枝，增加约束条件23.7514

11、x 和121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max58 2059454,0Sxxxxxxxxx 1()B1213,3,39xxS 1221.8,4,41xxS 041.25SS 取新的下界,新的上界39S 41S 接下来对问题 进行分枝2()B问题 是整数解,已被查清1()B3941SS 4()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B1212122112max58 20594542,0Sxxxxxxxxxx 123451,4,4099xxS 无可行解4()B11.81x 增加约束条件11.8

12、12x 和将问题 分解为 和 两个子问题4()B3()B2()B4()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B1212122112max58 20594542,0Sxxxxxxxxxx 123451,4,4099xxS 无可行解4()B 无可行解,该问题已查清4()B3941SS 取新的上界5409S 395409SS 接下来对问题 进行分枝3()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B123451,4,4099xxS 24x 增加约束条件25x 和将问题 分解为 和 两个子问题6()B5()B3()B

13、6()B12121221212max58 205945414,0Sxxxxxxxxxxx 5()B12121221212max58 205945415,0Sxxxxxxxxxxx 1251437xxS 1260540 xxS 都是整数解,均已查清56() ()BB、但,故将该枝剪去.5SS 而 , 故为最优值.6SSS 395409SS 6()B5()B4()B3()B2()B1()B0()B041.252.25,3.75S （）1393,3S （）2411.8,4S （）无可行解3540941,49S （）5371,4S （）6400,5S （）()A23x 24x 11x 12x 24x

14、25x 请练习：请练习：100页 习题三 第3题（用分枝定界法求解）答案：122,14xxZ 注意：1、每一层子问题求解出来以后，都要随时修改上下界，不能只分支不定界；2、子问题是在上一层子问题（而不是在原始问题）的基础上，再增加约束条件；3、如果同一层的两个子问题都无整数最优解，则选其目标函数值较大者作为新的上界，下界不变（不能选目标函数值较小者作为新的下界）；4、上面两个子问题要分别再分枝求解，不能将目标函数值较小者剪掉；用分枝定界法求解整数规划问题12121212max 9511414123,0Zxxxxxxxx 且为整数 答案： 或122,4xxZ 123,1,4xxZ 胡运权习题集

15、5.7(a)解：12121212max 9511414123,0Zxxxxxxxx 且为整数 ()A0()B12121212max 9511414123,0Zxxxxxxxx 分枝定界过程如图所示6()B5()B4()B3()B1()B0()AB2()B8()B7()B11x 12x 23x 22x 23x 22x 12x 13x 029 63 2,10 3Z （）110 31,7 3Z （）241 92,23 9Z （）561 1433 14,2Z （）742,2Z （）84,1Z （3 3 ）331,2Z （）0,29 6ZZ 0,41 9ZZ 3,61 14ZZ 4AZ 初次分枝选 1x

16、12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 0B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 1()B2()B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 3()B2()B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 3()B5()B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 3()B7()B8()B4()B3()B1()B0()AB2()B6()B5()B24x 23x 11x 12x 22x 23x 029 63 2,10 3Z （）133 712 7Z （, ,3 3) )441 92,23 9Z （）53,2Z （1 1 ）0,29 6ZZ 0,33 7ZZ 0,41 9ZZ 4AZ 310 31,7 3Z （）8()B7()B22x 23x 761 1433 14,2Z （） 初次分枝选 2x10()B9(