运筹学胡运权第五版课件(第4章)

1、第4章 整数规划与分配问题Integer Programming and 4.1 整数规划的特点与作用例例 某厂拟用集装箱托运甲、乙两种货物，每箱的某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？示，问如何托运能使总收益最大？货物体积(米3/箱) 重量(吨/箱) 利润(千元/箱)甲乙 2 2 3 3 1 2 14（米3） 9 （吨）托运限制解：建模如下设托运甲货物设托运甲货物x1箱，乙货物箱，乙货物x2箱箱12121212max322314. . 2 9,0,zxxxxstxxx

2、x且均为整数部分或全部为整数）或（iixxbAXtsCXz, 0. .max2 2、整数规划的一般形式、整数规划的一般形式1 1、整数规划、整数规划（Integer Programming）决策变量部分或全部取值为整数的线性规决策变量部分或全部取值为整数的线性规划问题，称为整数线性规划或简称整数规划问题，称为整数线性规划或简称整数规划，常记为划，常记为IP。纯整数规划纯整数规划 所有决策变量要求取非负整数。所有决策变量要求取非负整数。混合整数规划混合整数规划 只有一部分的决策变量要求取非负整数，只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。另一部分可以取非负实数。3 3、整数规划

3、的分类、整数规划的分类例如例如12121212max322314. . 2 9,0zxxxxstxxx x，且均为整数该问题是纯整数规划该问题是纯整数规划. .在整数规划在整数规划IPIP中去掉变量取整限制得到的线性规划问中去掉变量取整限制得到的线性规划问题称为松弛问题，常用题称为松弛问题，常用L L0 0表示。表示。4、整数规划的松弛问题12121212max322314. . 2 9,0zxxxxstxxx x，且均为整数12121212max322314. . 2 9,0zxxxxstxxx x例例 求解下列整数求解下列整数线性规划。线性规划。解：其松弛问题为解：其松弛问题为先求松弛问题

4、的最优解；先求松弛问题的最优解；再用四舍五入的方法求整再用四舍五入的方法求整数规划的最优解数规划的最优解24624(3.25, 2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=6松弛问题的最优解松弛问题的最优解ABCD取整得到取整得到4个整数解：个整数解：A(3,2)B(4,2)C(4,3)D(3,3)不可行不可行可行解可行解,此时此时z=13但但A不是该整数规划的最优解！不是该整数规划的最优解！P该问题共有该问题共有19个整数可行解个整数可行解,注意：可行域不是凸集！注意：可行域不是凸集！其中其中P(4,1)是最优解是最优解 zmax=145 5、整数规划、整数规划IPI

5、P与其松弛问题与其松弛问题L L0 0的关系的关系l若若L L0 0无可行解，则无可行解，则IPIP无可行解；无可行解；l若若L L0 0有整数最优解，则有整数最优解，则IPIP有相同的最优解；有相同的最优解；l若若L L0 0有非整数最优解，则有非整数最优解，则IPIP的最优解不能确定。的最优解不能确定。注意：注意：求解求解IP时，不能通过先解时，不能通过先解L0再通过凑整的方法进行；再通过凑整的方法进行； IP的可行域不再是凸集。的可行域不再是凸集。6、0-1变量（逻辑变量）取值只能为取值只能为0 0或者或者1 1的决策变量。的决策变量。注意：注意：0-10-1变量通常用来表示只有两种结果

6、的选择性决策。变量通常用来表示只有两种结果的选择性决策。1 0 jx决策者选择一种结果决策者选择另一种结果7 7、 0-1变量在实际问题中的应用管理问题管理问题整数线性规划整数线性规划引入引入0-10-1变量变量 01规划规划 所有决策变量只能取所有决策变量只能取 0 - 1 变量。变量。（1）表示选择性约束121223541xxxx“或”例例 用用0-10-1变量将变量将表示成一般线性约束条件。表示成一般线性约束条件。121122120 11 i1,20 i23541 10,1(1,2)iiyixxMyxxMyyyyi 解：引入2个变量第 个约束不起作用（）第 个约束起作用8、0-1变量在表

7、示线性约束条件中的应用一般的，已知一般的，已知m个约束条件个约束条件1(1,2,)nijjija xb im若只有若只有k个起作用，则个起作用，则1121 i0 1 1,2,0 i1,2, 0,1(1,2,)inijjiijmimyima xbMy imyyymkyim第 个约束不起作用引入 个变量（）第 个约束起作用（）（2）表示选择性取值35 7 9x“ 只能取 ， ， ， 中的一个值”例例 用用0-10-1变量将变量将表示成一般线性约束条件。表示成一般线性约束条件。123412340 11 i1,2 3 40 i3579 10,11,2 3 4iixyixxyyyyyyyyyi解：引入4

8、个变量取第 个值（,）不取第 个值（,）一般的，若约束条件的右端项（或变量一般的，若约束条件的右端项（或变量x）只）只能取能取r个值个值b1,b2,br中的一个值中的一个值112211221120 1 1 1,2,0 .(.) 10,1(1,2, )iiinijjrrrrjrirxibyirxiba xb yb yb yxb yb yb yyyyyir 引入 个变量右端项（或 ）取第 个值（）右端项（或 ）不取第 个值或（3）表示两组条件中仅有一组满足122413xxx“若，则；否则”例例 用用0-10-1变量将变量将表示成一般线性约束条件。表示成一般线性约束条件。11211222120 11

9、 i1,20 i414 310,1(1,2)iiyixMyxMyxMyxMyyyyi 解：引入2个变量第 个约束不起作用（）第 个约束起作用4.2 分配问题及匈牙利法2-1 2-1 问题的提出与数学模型问题的提出与数学模型例例 有一份说明书，要分别翻译有一份说明书，要分别翻译成英、日、德、俄四种文字，交给成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成，因甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所文字所需要的时间（小时）如表所示。规定每项工作只能交给其中一示。规定每项工作只能交给其中一个人完成，每个人只能完成

10、其中一个人完成，每个人只能完成其中一项工作。项工作。 问：如何分配，能使所需的总问：如何分配，能使所需的总时间最少？时间最少？译译英英译译日日译译德德译译俄俄甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811119 9人人工作工作解:建立如下模型设设 xij=10甲：x11+ x12 + x13 + x14 =1乙：x21+ x22 + x23 + x24 =1丙：x31+ x32 + x33 + x34 =1丁：x41+ x42 + x43 + x44 =1译英：x11+ x21 + x31 + x41 =1译日：x12+

11、 x22 + x32 + x42 =1译德：x13+ x23 + x33 + x43 =1译俄：x14+ x24 + x34 + x44 =1xij =0或1 (i=1,2,3,4; j=1,2,3,4)min z= aijxiji=1j=14 4第i个人完成第j项工作第i个人不完成第j项工作用aij表示第 i个人完成第j项任务的时间 有有m项工作要交给项工作要交给m个人完成，规定每项工个人完成，规定每项工作只能交给其中一个人完成，而每个人只能完作只能交给其中一个人完成，而每个人只能完成其中一项工作。成其中一项工作。 问：如何分配，可使所需的总时间最少？问：如何分配，可使所需的总时间最少？（或

12、总效率最高？）（或总效率最高？）1 1、分配问题或指派问题、分配问题或指派问题（Assignment Problem）2 2、分配问题的已知条件、分配问题的已知条件 m个人，用个人，用i=1,2,=1,2,m表示；表示； m项工作，用项工作，用j=1,2,=1,2,m表示；表示； aij为第为第i个人完成第个人完成第j项工作所需花费的资源（即时间或项工作所需花费的资源（即时间或效率）效率） 将将m阶矩阵（阶矩阵（aij）称为该分配问题的效率矩阵（此处）称为该分配问题的效率矩阵（此处效率也包括时间），此时该问题称为效率也包括时间），此时该问题称为m阶分配问题。阶分配问题。3 3、分配问题的表格形

13、式、分配问题的表格形式 工作工作人人12m1a11a12a1m2a21a22a2m.mam1am2 amm4 4、标准分配问题、标准分配问题求目标函数的极小值求目标函数的极小值效率矩阵的元素全非负效率矩阵的元素全非负aij05、标准分配问题的数学模型1111min1(1,2,). . 1(1,2,)0 1( ,1,2,)mmijijijmijjmijiijza xximstxjmxi jm或第第i个个人完成一项工作人完成一项工作第第j项工作由一个人完成项工作由一个人完成1 0 ijijxij第 个人完成第 项任务设第 个人不完成第 项任务分配问题是分配问题是0-10-1整数规划的特例，也是运输

14、问题的特例。整数规划的特例，也是运输问题的特例。分配问题一定有最优解。分配问题一定有最优解。2-2 匈牙利法4 (0) 5 6 5 4 (0) 5 7 6 3 (0) (0) 5 6 2 例例 已知某分配问题的已知某分配问题的效率矩阵如右：效率矩阵如右：12233441min10 xxxxz当，其他变量时，=01 1、特殊情况、特殊情况 在标准形式的分配问题中，若在标准形式的分配问题中，若m阶效率矩阵中阶效率矩阵中存在存在m个不同行不同列的个不同行不同列的0 0元素（称之为独立的元素（称之为独立的0 0元元素），则令这些素），则令这些0 0元素对应位置上的变量的值为元素对应位置上的变量的值为1

15、 1，其他变量的值为其他变量的值为0 0，得到该问题的最优解。，得到该问题的最优解。2 2、基本原理、基本原理（1 1）如果从效率矩阵如果从效率矩阵 aij 的每一行元素中分别减的每一行元素中分别减去去( (或加上或加上) )一个常数（称之为行位势，记做一个常数（称之为行位势，记做ui ）, ,或者从每一列中分别减去或者从每一列中分别减去( (或加上或加上) )一个常数（称之一个常数（称之为列位势，记做为列位势，记做vj ）, ,得到一个新的效率矩阵得到一个新的效率矩阵 bij,其中其中bij= =aij-ui-vj, ,则以则以 bij 为效率矩阵的最优解等价为效率矩阵的最优解等价于以于以

16、aij 为效率矩阵的最优解为效率矩阵的最优解. .（2 2）系数矩阵中独立系数矩阵中独立0 0元素的最多个数元素的最多个数= =能够覆盖所能够覆盖所有有0 0元素的最少直线数。元素的最少直线数。定理（1）的证明以以aij为效率矩阵的目标函数值：为效率矩阵的目标函数值： z0= aijxij以以bij为效率矩阵的目标函数值：为效率矩阵的目标函数值： z=bijxij m mi=1j=1i=1j=1 m mbij=aij-ui-vj z= (aij-ui-vj)xij= aijxij - uixij - vjxij =z0- uixij - vjxijm mm mm mm m m m =z0- u

17、i- vj=z0-常数mmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1m m故以故以 bij为效率矩阵的分配问题的最优解等价于以为效率矩阵的分配问题的最优解等价于以 aij 为效率矩阵的分配问题的最优解为效率矩阵的分配问题的最优解. .3 3、匈牙利法、匈牙利法 由匈牙利数学家克尼格（由匈牙利数学家克尼格（Konig）建立的用于求）建立的用于求解分配问题的计算方法。解分配问题的计算方法。4 4、匈牙利法的步骤、匈牙利法的步骤第一步第一步 造造0 0：变换效率矩阵，使每行每列至少有一个变换效率矩阵，使每行每列至少有一个0 0 找出每行最小元素（即该行的行位

18、势找出每行最小元素（即该行的行位势ui），从该行各），从该行各元素中减去元素中减去ui 找出每列最小元素（即该列的列位势找出每列最小元素（即该列的列位势vj），从该列各），从该列各元素中减去元素中减去vj 第二步第二步 划直线划直线：计算独立：计算独立0 0元素的个数元素的个数、逐列检查、逐列检查若该列只有一个未标记的若该列只有一个未标记的0 0，对其加，对其加( )( )标记标记（表明这（表明这项工作必须由对应的人完成），项工作必须由对应的人完成），同时划一条直线覆盖同时划一条直线覆盖该行的所有元素该行的所有元素（表明此人不能再完成其他工作）。（表明此人不能再完成其他工作）。否则轮空，否则轮

19、空，转下一列检查，直到所有列检查完；转下一列检查，直到所有列检查完；、逐行检查、逐行检查若该行只有一个未标记的若该行只有一个未标记的0 0，对其加，对其加( )( )标记标记（表明这（表明这个人必须对应的工作），个人必须对应的工作），同时划一条直线覆盖该列同时划一条直线覆盖该列的所有元素的所有元素（表明此项工作不能再由其他人完成）（表明此项工作不能再由其他人完成）。否则轮空，转下一行检查，直到所有行检查完；否则轮空，转下一行检查，直到所有行检查完；、在未被直线覆盖的元素中重复、在未被直线覆盖的元素中重复，直至再划不，直至再划不出这样的直线，转入出这样的直线，转入。、可能出现三种情况：、可能出现

20、三种情况：情况情况1 1： 打（打（0 0）的个数）的个数= =m，即每行均有（，即每行均有（0 0），），则令（则令（0 0）对应的变量）对应的变量xij=1=1，其他变量，其他变量=0=0，得到该，得到该问题的最优解，计算总时间，结束。问题的最优解，计算总时间，结束。情况情况2 2： 打（打（0 0）的个数）的个数 m，且，且未被直线覆盖的未被直线覆盖的0 0元元素构成闭回路，则沿该回路对每个间隔的素构成闭回路，则沿该回路对每个间隔的0 0打（打（ ），），同时划去该同时划去该0 0所在的一列。所在的一列。情况情况3： 打（打（0 0）的个数）的个数 工作数工作数增加假想的工作，建立标准分

21、配问题如下：增加假想的工作，建立标准分配问题如下： 工作工作人人一一二二三三四四五五六六13 36 62 26 60027 71 14 44 40033 36 65 58 80046 64 43 37 70055 52 24 43 30065 57 76 62 200最优分配最优分配人人123456工作工作三三二二一一四四总时间总时间z zminmin=2+1+3+2=8=2+1+3+2=8（1 1）任务）任务E E必须完成必须完成, , 其他其他4 4项任务可任选项任务可任选3 3项完成项完成. .（2 2）其中有）其中有1 1人完成人完成2 2项项, , 其他每人完成其他每人完成1 1项项

22、. .（3 3）任务）任务A A由甲或丙完成，任务由甲或丙完成，任务C C由丙或丁完成，任务由丙或丁完成，任务E E由甲或乙由甲或乙或丁完成，且规定或丁完成，且规定4 4人中丙或丁完成人中丙或丁完成2 2项任务，其它每人完成项任务，其它每人完成1 1项。项。14 . 6 分配甲, 乙, 丙, 丁四人完成A, B, C, D, E 五项任务,每人完成各项任务的时间如下表. 4523364224丁3240282734丙3320263839乙3742312925甲EDCBA考虑以下三种情况, 分别确定最优分配方案(总时间最小).（1 1）任务）任务E E必须完成必须完成, , 其他其他4 4项任务可

23、任选项任务可任选3 3项完成项完成. 其中有其中有1 1人完成人完成2 2项项, , 其他每人完成其他每人完成1 1项项. .（3）任务）任务A由甲或丙完成，任务由甲或丙完成，任务C由丙或丁完成，由丙或丁完成，任务任务E由甲或乙或丁完成，且规定由甲或乙或丁完成，且规定4人中丙或丁完人中丙或丁完成成2项任务，其它每人完成项任务，其它每人完成1项。项。例 已知分配问题的效率矩阵如下，试求总效率最高的分配方案。 工作 人一二三1362271433652-3 两点说明1 1人数与工作数不等的处理人数与工作数不等的处理 当人数当人数工作数时：增加假想的工作，使得工作数工作数时：增加假想的工作，使得工作数

24、与人数能够匹配与人数能够匹配, 对应的效率设定为对应的效率设定为0。 当工作数当工作数人数时：增加假想的人，使得人数与工作人数时：增加假想的人，使得人数与工作数能够匹配数能够匹配, 对应的效率设定为对应的效率设定为0或或M或其它。或其它。2 2若目标函数为求若目标函数为求max z z的处理的处理（例如已知每个人完成各项工作的效率）（例如已知每个人完成各项工作的效率）令 z=-z 等价于求解等价于求解 min z =(-aij)xiji=1 j=1 m m再利用第再利用第1个基本原理减去行（列）位势，化为效率矩个基本原理减去行（列）位势，化为效率矩阵非负的情形。阵非负的情形。4.3 分枝定界法

25、二、分枝定界法二、分枝定界法 用来求解整数线性规划的方法。用来求解整数线性规划的方法。一、整数线性规划一、整数线性规划（IP）的特征的特征 1、可行域不是凸集；、可行域不是凸集； 2、可行解的个数是有限的；、可行解的个数是有限的； 3、当可行解个数不多时，可以用穷举法求解。、当可行解个数不多时，可以用穷举法求解。三、原理三、原理 在求解某问题时，先放宽或取消其中某些在求解某问题时，先放宽或取消其中某些约束，求解一个较简单的替代问题，而且总是约束，求解一个较简单的替代问题，而且总是保证原问题的可行域包含在替代问题的可行域保证原问题的可行域包含在替代问题的可行域中。中。四、步骤四、步骤且为整数),

26、 2 , 1( , 0), 2 , 1( )(max 11njxmibxaIPxcZjnjijijnjjj以纯整数规划为例，已知以纯整数规划为例，已知), 2 , 1( , 0), 2 , 1( )(max 101njxmibxaLxcZjnjijijnjjj其松弛问题为：其松弛问题为： 第一步第一步 求解松弛问题（求解松弛问题（L L0 0） 先不考虑整数约束，解先不考虑整数约束，解( ( IP ) )的松弛问题的松弛问题( ( L0 ) )，可能得到以下情况之一：可能得到以下情况之一： 若若( ( L0 ) )无可行解，则无可行解，则( ( IP ) )也无可行解，结束。也无可行解，结束。

27、 若若( ( L0 ) )有最优解，并符合有最优解，并符合( ( IP ) )的取整条件，则的取整条件，则( ( L0 ) )的最优解即为的最优解即为( ( IP ) )的最优解，结束。的最优解，结束。 若若( ( L0 ) )有最优解，但不符合有最优解，但不符合( ( IP ) )的整数条件，的整数条件，转入下一步。转入下一步。 为讨论方便，设为讨论方便，设( ( L0 ) )的最优解为：的最优解为： 不全为整数其中), 2 , 1()0 , 0 ,( 21)0(mibbbbbXiTmr第二步第二步 分枝与定界分枝与定界 记记( ( IP ) )的目标函数最优值为的目标函数最优值为Z* 。

28、以松弛问题（以松弛问题（L L0 0）的最优解）的最优解X（0）对应的目标对应的目标函数值函数值Z0作为作为Z* 的上界。的上界。 在在( L0 )的最优解的最优解 X(0)中，任选一个不符合整数条件中，任选一个不符合整数条件的变量，例如的变量，例如xr= = （不为整数），以（不为整数），以 表示不超过表示不超过 的最大整数。构造两个约束条件的最大整数。构造两个约束条件 xr 和和xr 1 1rb rbrb rb rb 将这两个约束条件分别加入问题将这两个约束条件分别加入问题( ( L0 ) ) ，形，形成两个子问题成两个子问题 ( ( L1 ) )和和( ( L2 ) ) 。注意：（注意：

29、（L L1 1）和（）和（L L2 2）的可行域之并集包含（）的可行域之并集包含（IP IP ) )的全部可行解。的全部可行解。 依次求解两个子问题（依次求解两个子问题（L L1 1）和（）和（L L2 2） ，将出现，将出现两种情况：两种情况： 某个子问题的最优解满足变量取整的要求，某个子问题的最优解满足变量取整的要求，即为原（即为原（IPIP）的整数可行解，进入第三步；）的整数可行解，进入第三步； 两个子问题的最优解均非整数可行解，则选两个子问题的最优解均非整数可行解，则选目标函数值较大的子问题继续分枝求解，直至出现目标函数值较大的子问题继续分枝求解，直至出现某个子问题的最优解满足变量取整

30、要求，即为原某个子问题的最优解满足变量取整要求，即为原（IPIP）的整数可行解，进入第三步。）的整数可行解，进入第三步。 第三步第三步 比较与剪枝比较与剪枝 若出现两个或更多整数可行解，则仅保留目标若出现两个或更多整数可行解，则仅保留目标函数值较大的一个。函数值较大的一个。 将各分枝的目标函数值与保留的整数可行解进将各分枝的目标函数值与保留的整数可行解进行比较，并把目标函数值小于整数可行解的目标函行比较，并把目标函数值小于整数可行解的目标函数值的分枝剪去，将出现两种情况：数值的分枝剪去，将出现两种情况： 仅保留整数可行解，其他分枝均被剪去，则仅保留整数可行解，其他分枝均被剪去，则该整数可行解即

31、为原（该整数可行解即为原（IPIP）的最优解，结束；）的最优解，结束； 除保留整数可行解外，还有其他未被剪去的除保留整数可行解外，还有其他未被剪去的分枝，则取目标函数值最大的继续分枝，直至出现分枝，则取目标函数值最大的继续分枝，直至出现新的整数可行解，重复第三步。新的整数可行解，重复第三步。 当存在若干变量有取整约束时，分枝既广且深，当存在若干变量有取整约束时，分枝既广且深，在最坏的情况下相当于组合所有可能的整数解。在最坏的情况下相当于组合所有可能的整数解。 一般整数规划问题属于一类未解决的难题，称为一般整数规划问题属于一类未解决的难题，称为NP-completeNP-complete，只有少

32、数特殊问题有好的算法，例如，只有少数特殊问题有好的算法，例如分配问题。分配问题。 注意：注意： 12121212max322314. . 2 9,0zxxxxstxxx x，且均为整数012121212max322314. . 2 9,0Lzxxxxstxxx x：例例 求解下列整数线性规划。求解下列整数线性规划。解：其松弛问题为解：其松弛问题为24624(3.25, 2.5)x1x22x1+3x2=142x1+x2=9松弛问题的最优解松弛问题的最优解12121212max322314. . 2 9,0zxxxxstxxx x松弛问题：松弛问题：选选x2 2=2.5=2.5分枝，引入条件分枝，

33、引入条件x2 22,2,x2 23,3,得到两个子问题：得到两个子问题：1121212212:max3223142 9. . 2,0Lzxxxxxxstxx x2121212212:max3223142 9. . 3,0Lzxxxxxxstxx x24624(3.25, 2.5)x1x22x1+3x2=142x1+x2=9松弛问题的最优解松弛问题的最优解AB点点A A（3.5,23.5,2）为）为L L1 1的最优解，此时的最优解，此时z=14.5z=14.5点点B B（2.5,32.5,3）为）为L L2 2的最优解，此时的最优解，此时z=13.5z=13.5都不是原都不是原IPIP的可行解

34、，的可行解，取边界值较大的取边界值较大的z=14.5z=14.5，对，对x1 1=3.5=3.5继续分枝。继续分枝。12max32zxx选选x1 1分枝，引入条件分枝，引入条件x1 13,3,x1 14,4,得到两个子问题：得到两个子问题：111212122112:max3223142 9. . 2 3,0Lzxxxxxxstxxx x121212122112:max3223142 9. . 2 4,0Lzxxxxxxstxxx x24624(3.25, 2.5)x1x22x1+3x2=142x1+x2=9松弛问题的最优解松弛问题的最优解AB点点C C（3,23,2）为）为L L1111的最优

35、解，此时的最优解，此时z=13z=13点点D D（4,14,1）为）为L L1212的最优解，此时的最优解，此时z=14z=14都是原都是原IPIP的可行解，的可行解，取边界值较大的取边界值较大的z=14z=14，开始剪枝。，开始剪枝。CD12max32zxxL0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L11：z3=13L12：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x22x23x13x14舍舍舍舍取取综上，原综上，原IPIP的最优解为的最优解为max414.1Xz 当时，L0：z0=14.75x1

36、=3.25，x2=2.5L1：z1=43/3L2：z2=14L11：z3=13L12：z4=38/3x1=3，x2=8/3x1=4，x2=1x1=3，x2=2x1=2，x2=10/3x13x14x22x23舍舍舍舍取取综上，原综上，原IPIP的最优解为的最优解为max414.1Xz 当时，本例也可以先对本例也可以先对x1 1=3.25=3.25分枝：分枝：例例 用分枝定界法求解整数规划问题（用图解法计算）用分枝定界法求解整数规划问题（用图解法计算）且全为整数且全为整数0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题

37、解：首先去掉整数约束，变成一般线性规划问题0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（LP）用图解法求用图解法求（LP）的最的最优解，如图所示。优解，如图所示。x1x233(18/11,40/11)对于对于x118/111.64， 取约束条件取约束条件x1 1， x1 2将（将（IP）划分为（）划分为（IP1）和（）和（IP2）相应的，将相应的，将（LP）划分为（）划分为（LP1）和（）和（LP2） x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最小值的下最小值的下限。限。即有：即有：且为整数且为整数0,1

38、 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且为整数且为整数0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 下面求（下面求（LP1）和（）和（LP2）的最优解。）的最优解。x1x233(18/11,40/11) 先求先求（LP1）, ,如图所示。如图所示。此时此时B 在点取得最优解。在点取得最优解。x11, x2 =3, Z(1)16找到整数解，问题已探找到整数解，问题已探明，此枝停止计算。明，此枝停止计算。11再求再求（LP2） ,如图所示。如图所示。在在C 点取得最优解。点取得最优解。即即x12, x2 =10/3

39、, Z(2) 56/318.7 Z2 Z116 原问题有比原问题有比（16）更小的最优解，但）更小的最优解，但 x2 不是整数，故利用不是整数，故利用 3 10/34 加入条件。加入条件。BAC加入条件：加入条件： x23, x24 有下式：有下式：且为整数且为整数0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且为整数且为整数0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ下面求（下面求（LP3）和（）和（LP4）的最优解。）的最优解。x1x233(18/11,40/11)11BAC先求先求（LP3）, ,如图所示。如图所示。此时此时D 在点取得最优解。在点取得最优解。即即 x112/52.4, x2 =3, Z(3)-87/5-17.4 Z(5) F 如对如对 Z(6) 继续分解，其最小值也不会低于继续分解，其最小值也不会低于15.5，问题探明问题探明, ,剪枝。剪枝。 至此，原问题至此，原问题（IP）的最优