第四章整数规划与分配问题优秀PPT.ppt

第四章整数规划与分配问题第一页，本课件共有80页第第4 4章章 整数规划与分配问题整数规划与分配问题第二页，本课件共有80页第第4 4章章 整数规划与分配问题整数规划与分配问题一、整数线性规划问题的提出一、整数线性规划问题的提出二、整数规划问题的求解二、整数规划问题的求解1 1、分支定界解法、分支定界解法2 2、割平面解法、割平面解法三、三、0-10-1型整数线性规划问题的求解型整数线性规划问题的求解四、分配问题与匈牙利法四、分配问题与匈牙利法第三页，本课件共有80页一、整数线性规划问题的提出一、整数线性规划问题的提出在前面讨论的线性规划问题中，有些最优解可能是分数或小在前面讨论的线性规划问题中，有些最优解可能是分数或小在前面讨论的线性规划问题中，有些最优解可能是分数或小在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些问题，常要求解必须是整数数，但对于某些问题，常要求解必须是整数数，但对于某些问题，常要求解必须是整数数，但对于某些问题，常要求解必须是整数(称为整数解称为整数解称为整数解称为整数解)。（1 1 1 1）变量是人数、机器设备台数或产品件数等都要求是整）变量是人数、机器设备台数或产品件数等都要求是整）变量是人数、机器设备台数或产品件数等都要求是整）变量是人数、机器设备台数或产品件数等都要求是整数数数数（2 2 2 2）对某一个项目要不要投资的决策问题，可选用一个逻辑对某一个项目要不要投资的决策问题，可选用一个逻辑对某一个项目要不要投资的决策问题，可选用一个逻辑对某一个项目要不要投资的决策问题，可选用一个逻辑变量变量变量变量 x x x x，当，当，当，当x=1x=1x=1x=1表示投资，表示投资，表示投资，表示投资，x=0 x=0 x=0 x=0表示不投资；表示不投资；表示不投资；表示不投资；（3 3 3 3）人员的合理安排问题，当变量）人员的合理安排问题，当变量）人员的合理安排问题，当变量）人员的合理安排问题，当变量xij=1xij=1xij=1xij=1表示安排第表示安排第表示安排第表示安排第i i i i人去做人去做人去做人去做j j j j工作，工作，工作，工作，xij=0 xij=0 xij=0 xij=0表示不安排第表示不安排第表示不安排第表示不安排第i i i i人去做人去做人去做人去做j j j j工作。逻辑变量也是只允工作。逻辑变量也是只允工作。逻辑变量也是只允工作。逻辑变量也是只允许取整数值的一类变量。许取整数值的一类变量。许取整数值的一类变量。许取整数值的一类变量。第四页，本课件共有80页一、整数线性规划问题的提出一、整数线性规划问题的提出整数线性规划问题的分类整数线性规划问题的分类整数线性规划问题的分类整数线性规划问题的分类根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为四种类型四种类型四种类型四种类型：纯整数规划：纯整数规划：纯整数规划：纯整数规划：所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。混合整数规划：混合整数规划：混合整数规划：混合整数规划：部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。0 0 0 0 1 1 1 1 整数规划：整数规划：整数规划：整数规划：所有决策变量均要求为所有决策变量均要求为所有决策变量均要求为所有决策变量均要求为0 0 0 0或或或或1 1 1 1。混合混合混合混合 0 0 0 0 1 1 1 1 整数规划：整数规划：整数规划：整数规划：部分决策变量要求为部分决策变量要求为部分决策变量要求为部分决策变量要求为0 0 0 0或或或或1 1 1 1。第五页，本课件共有80页 一、整数线性规划问题的提出一、整数线性规划问题的提出引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题例例4-14-1（生产组织计划问题）某工厂在一个计划期内（生产组织计划问题）某工厂在一个计划期内拟生产甲、乙两种大型设备。除了拟生产甲、乙两种大型设备。除了A A、B B两种部件需要两种部件需要外部供应且供应受到严格限制之外，该厂有充分的能力外部供应且供应受到严格限制之外，该厂有充分的能力来加工制造这两种设备所需的其余零件，并且所需原材来加工制造这两种设备所需的其余零件，并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件料和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表的供应限额以及设备的利润由表4-1-14-1-1给出。问该厂在给出。问该厂在本计划期内如何安排甲、乙设备的生产数量，才能获取本计划期内如何安排甲、乙设备的生产数量，才能获取最大利润？最大利润？第六页，本课件共有80页一、整数线性规划问题的提出一、整数线性规划问题的提出部件部件设备设备A AB B利润利润（百万）（百万）甲甲6 61 11515乙乙4 43 32020部件的最大部件的最大供应量供应量25251010表表 4-1-14-1-1第七页，本课件共有80页 例例4-14-1【解】【解】设设 x x1 1，x x2 2 2 2 分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，Z Z Z Z 为生产这两种设备可获得的总利润。依题意，给问题的为生产这两种设备可获得的总利润。依题意，给问题的为生产这两种设备可获得的总利润。依题意，给问题的为生产这两种设备可获得的总利润。依题意，给问题的数学模型为：数学模型为：数学模型为：数学模型为：max max Z Z=15=15x x1 1 20202020 x x2 2 2 2 s.t.6 s.t.6x x1 1 4 4x x2 2 2 2 25 25 x x x x1 1 3 3x x x x2 2 2 2 10 10 10 10 x xii 0,1,2,0,1,2,0,1,2,0,1,2,这是一个这是一个纯整数规划问题纯整数规划问题。第八页，本课件共有80页 一、整数线性规划问题的提出一、整数线性规划问题的提出引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题例例例例4-24-24-24-2（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在 n n n n 个连锁店所在城个连锁店所在城个连锁店所在城个连锁店所在城市中建立市中建立市中建立市中建立 m m m m 个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。若在第若在第若在第若在第 i i i i 个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为 D D D Dii ii，单位时间的，单位时间的，单位时间的，单位时间的固定成本为固定成本为固定成本为固定成本为 a a a ai i i i，ii ii=1=1=1=1，n n n n，第第第第 j j j j 个连锁店的需求量为个连锁店的需求量为个连锁店的需求量为个连锁店的需求量为 b b b bj j j j，j j j j=1=1=1=1，n n n n。从第从第从第从第 i i i i 个配货中心到第个配货中心到第个配货中心到第个配货中心到第 j j j j 个连锁店的单位运输成本为个连锁店的单位运输成本为个连锁店的单位运输成本为个连锁店的单位运输成本为 c c c cij ij ij ij。应如何应如何应如何应如何选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划，才能得到经济上花，才能得到经济上花，才能得到经济上花，才能得到经济上花费最少的方案。费最少的方案。费最少的方案。费最少的方案。第九页，本课件共有80页 例例4-24-2【解解】设在单位时间内，从配货中心设在单位时间内，从配货中心 i i 运往连锁店运往连锁店 j j 的的物资数量为物资数量为 x xijij，Z Z 为单位时间内的总费用。引入为单位时间内的总费用。引入布尔变量布尔变量 则上述问题可归结为如下的数学模型：则上述问题可归结为如下的数学模型：第十页，本课件共有80页例例例例4-2 4-2 4-2 4-2 可归结为如下的数学模型可归结为如下的数学模型可归结为如下的数学模型可归结为如下的数学模型这是一个混合这是一个混合这是一个混合这是一个混合 0 0 0 0 1 1 1 1 规划问题。规划问题。规划问题。规划问题。第十一页，本课件共有80页 例例4-34-3某人有一背包可以装某人有一背包可以装1010公斤重、公斤重、0.025m0.025m3 3的物的物品。他准备用来装甲、乙两种物品，每件物品的重品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表量、体积和价值如表4-3-14-3-1所示。问两种物品各装所示。问两种物品各装多少件，所装物品的总价值最大？多少件，所装物品的总价值最大？物品物品物品物品重量重量重量重量（公斤（公斤（公斤（公斤/每件）每件）每件）每件）体积体积体积体积（m m m m3 3 3 3/每件）每件）每件）每件）价值价值价值价值(元元元元/每件每件每件每件)甲甲甲甲乙乙乙乙1.21.21.21.20.80.80.80.80.0020.0020.0020.0020.00250.00250.00250.00254 4 4 43 3 3 3表表4-3-1例例例例4-3 4-3 解解解解 设甲、乙两种物品各设甲、乙两种物品各设甲、乙两种物品各设甲、乙两种物品各装装装装x1x1x1x1、x2x2x2x2件件第十二页，本课件共有80页 在例在例4-34-3中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量为为1212公斤，其体积是公斤，其体积是0.02m0.02m3 3。背包和旅行箱只能选择。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使其一，建立下列几种情形的数学模型，使所装物品所装物品价值最大价值最大。情形一：所装物品不变；情形一：所装物品不变；情形二：如果选择情形二：如果选择旅行箱旅行箱，则只能装载丙和丁两种，则只能装载丙和丁两种物品，价值分别是物品，价值分别是4 4和和3 3，载重量和体积的约束为，载重量和体积的约束为第十三页，本课件共有80页例例4-3 4-3【解解解解】引入引入0 01 1变量（或称逻辑变量）变量（或称逻辑变量）yi yi，令，令i i=1,2=1,2分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。情情情情形形形形一一一一：由由由由于于于于所所所所装装装装物物物物品品品品不不不不变变变变，约约约约束束束束左左左左边边边边不不不不变变变变，整整整整数数数数规规规规划划划划数数数数学学学学模模模模型为型为型为型为第十四页，本课件共有80页小结小结 通过设置逻辑变量建立整数规划的数学模型通过设置逻辑变量建立整数规划的数学模型通过设置逻辑变量建立整数规划的数学模型通过设置逻辑变量建立整数规划的数学模型 约束条件的右端项可能是约束条件的右端项可能是约束条件的右端项可能是约束条件的右端项可能是r r r r个值中的某一个，即个值中的某一个，即个值中的某一个，即个值中的某一个，即定义逻辑变量定义逻辑变量定义逻辑变量定义逻辑变量则约束条件表示为则约束条件表示为则约束条件表示为则约束条件表示为第十五页，本课件共有80页情形二：情形二：由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型为为为为甲、乙：甲、乙：丙、丁：丙、丁：第十六页，本课件共有80页MM为充分大的正数。为充分大的正数。当使用当使用背包背包时时(y y1 1=1=1，y y2 2=0)=0)，式，式(b b)和和(d d)是多余的；是多余的；当使用当使用旅行箱旅行箱时时(y y1 1=0=0，y y2 2=1)=1)式式(a a)和和(c c)是多余的。是多余的。第十七页，本课件共有80页小结小结 mmmm个约束条件中只有个约束条件中只有个约束条件中只有个约束条件中只有k k k k个起作用个起作用个起作用个起作用 设设设设mmmm个约束条件可表示为个约束条件可表示为个约束条件可表示为个约束条件可表示为定义定义定义定义 逻辑变量逻辑变量逻辑变量逻辑变量又设又设又设又设MMMM为任意大的正数为任意大的正数为任意大的正数为任意大的正数mmmm个约束条件中只有个约束条件中只有个约束条件中只有个约束条件中只有k k k k个约束条件真正起到约束作用个约束条件真正起到约束作用个约束条件真正起到约束作用个约束条件真正起到约束作用第十八页，本课件共有80页一、整数线性规划问题的提出一、整数线性规划问题的提出综上，我们了解了整数线性规划的问题。但如何来求解整综上，我们了解了整数线性规划的问题。但如何来求解整综上，我们了解了整数线性规划的问题。但如何来求解整综上，我们了解了整数线性规划的问题。但如何来求解整数线性规划问题呢？数线性规划问题呢？数线性规划问题呢？数线性规划问题呢？为满足整数解的要求，初看起来，似乎只要把已得到的为满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过带有分数或小数的解经过“舍入化整舍入化整”就可以了。就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。因此，对求最优整数解的问题，有必要另行研究。第十九页，本课件共有80页 例例例例4-4 4-4 4-4 4-4 说明整数规划问题的求解说明整数规划问题的求解说明整数规划问题的求解说明整数规划问题的求解不能不能不能不能直接在单纯形法最优解直接在单纯形法最优解直接在单纯形法最优解直接在单纯形法最优解的基础上四舍五入的基础上四舍五入的基础上四舍五入的基础上四舍五入 求下述整数规划问题的最优解（求下述整数规划问题的最优解（求下述整数规划问题的最优解（求下述整数规划问题的最优解（P85P85P85P85）：）：）：）：当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题结论：结论：例例例例4-44-44-44-4看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过“化整化整化整化整”来来来来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性解原整数线性规划，虽是最容易想到的，但常常得不到整数线性解原整数线性规划，虽是最容易想到的，但常常得不到整数线性解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规规划的最优解，甚至根本不是可行解。因此有必要对整数线性规规划的最优解，甚至根本不是可行解。因此有必要对整数线性规规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。划的解法进行专门研究。划的解法进行专门研究。划的解法进行专门研究。第二十页，本课件共有80页例例例例4-4 4-4 4-4 4-4 设整数规划问题如下设整数规划问题如下设整数规划问题如下设整数规划问题如下 （也可参见教材（也可参见教材（也可参见教材（也可参见教材P85P85P85P85例例例例1 1 1 1）首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。第二十一页，本课件共有80页用图解法求出最优解为：用图解法求出最优解为：用图解法求出最优解为：用图解法求出最优解为：x x x x1 1 1 13/2,3/2,3/2,3/2,x x x x2 2 2 2=10/3=10/3=10/3=10/3，且有，且有，且有，且有Z=29/6Z=29/6Z=29/6Z=29/6现求整数解现求整数解现求整数解现求整数解(最优解最优解最优解最优解):):):):如用舍入如用舍入如用舍入如用舍入取整法可得到取整法可得到取整法可得到取整法可得到4 4 4 4个点即个点即个点即个点即(1(1(1(1，3),(23),(23),(23),(2，3),3),3),3),(1(1(1(1，4),(24),(24),(24),(2，4)4)4)4)。显然，它们都不。显然，它们都不。显然，它们都不。显然，它们都不可能是整数规划的最优解。可能是整数规划的最优解。可能是整数规划的最优解。可能是整数规划的最优解。x1x233(3/2,10/3)按整数规划约束条件，其可行按整数规划约束条件，其可行按整数规划约束条件，其可行按整数规划约束条件，其可行解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域内且为整数点。故整数规划问题内且为整数点。故整数规划问题内且为整数点。故整数规划问题内且为整数点。故整数规划问题的可行解集是一个有限集，如右的可行解集是一个有限集，如右的可行解集是一个有限集，如右的可行解集是一个有限集，如右图所示。其中图所示。其中图所示。其中图所示。其中(2,2),(3,1)(2,2),(3,1)(2,2),(3,1)(2,2),(3,1)点的目点的目点的目点的目标函数值最大，即为标函数值最大，即为标函数值最大，即为标函数值最大，即为Z=4Z=4Z=4Z=4。第二十二页，本课件共有80页二、纯整数规划的求解二、纯整数规划的求解整数规划的求解比一般线性规划的求解复杂，常用整数规划的求解比一般线性规划的求解复杂，常用的方法有完全枚举法、分支定界法，割平面法、隐的方法有完全枚举法、分支定界法，割平面法、隐枚举法和枚举法和lagrangelagrange松弛法。松弛法。第二十三页，本课件共有80页在在在在求求求求解解解解整整整整数数数数线线线线性性性性规规规规划划划划时时时时，如如如如果果果果可可可可行行行行域域域域是是是是有有有有界界界界的的的的，首首首首先先先先容容容容易易易易想想想想到到到到的的的的方方方方法法法法就就就就是是是是穷穷穷穷举举举举所所所所有有有有可可可可行行行行的的的的整整整整数数数数解解解解，即即即即列列列列出出出出图图图图解解解解中中中中所所所所有有有有标标标标有有有有“+”的的的的整数点，然后比较它们的目标函数值，从而确定最优解。整数点，然后比较它们的目标函数值，从而确定最优解。整数点，然后比较它们的目标函数值，从而确定最优解。整数点，然后比较它们的目标函数值，从而确定最优解。例例例例4-44-44-44-4（P85P85P85P85）中中中中，变变变变量量量量只只只只有有有有x x x x1 1 1 1和和和和x x x x2 2 2 2，x x x x1 1 1 1所所所所能能能能取取取取的的的的整整整整数数数数值值值值为为为为0 0 0 0、1 1 1 1、2 2 2 2、3 3 3 3共共共共4 4 4 4个个个个；x x x x2 2 2 2所所所所能能能能取取取取的的的的整整整整数数数数值值值值为为为为0 0 0 0、1 1 1 1、2 2 2 2共共共共3 3 3 3个个个个。因因因因此此此此所所所所有有有有可可可可能能能能的的的的整整整整数数数数组组组组合合合合(不不不不都都都都是是是是可可可可行行行行的的的的)数数数数是是是是34=1234=1234=1234=12个个个个，穷穷穷穷举举举举法法法法还还还还是是是是勉勉勉勉强强强强可可可可用的。用的。用的。用的。对对对对于大型于大型于大型于大型问题问题问题问题，可行的整数，可行的整数，可行的整数，可行的整数组组组组合数会很大。合数会很大。合数会很大。合数会很大。例例例例如如如如在在在在指指指指派派派派问问问问题题题题中中中中，将将将将n n n n项项项项任任任任务务务务指指指指派派派派n n n n个个个个人人人人去去去去完完完完成成成成，不不不不同同同同的的的的指指指指派派派派方方方方案案案案共共共共有有有有n!n!n!n!种种种种，当当当当n=10n=10n=10n=10时时时时，可可可可能能能能的的的的指指指指派派派派方方方方案案案案数数数数超超超超过过过过300300300300万万万万；当当当当n=20n=20n=20n=20，超，超，超，超过过过过21021021021018181818。显显显显然，然，然，然，穷举穷举穷举穷举法是不可取的。法是不可取的。法是不可取的。法是不可取的。第二十四页，本课件共有80页应应寻寻找找仅仅检检查查可可行行的的整整数数组组合合的的一一部部分分，就就能能定定出出最最优优的整数解的方法。的整数解的方法。分支定界解法分支定界解法就是其中之一。就是其中之一。分分支支定定界界法法可可用用于于解解纯纯整整数数或或混混合合整整数数线线性性规规划划问问题题。2020世世纪纪6060年年代代初初由由Land Land DoigDoig和和DakinDakin等等提提出出，是解整数是解整数线线性性规规划的重要方法之一。划的重要方法之一。由由于于这这方方法法灵灵活活且且便便于于用用计计算算机机求求解解，所所以以现现在在它已是解整数规划的重要方法。它已是解整数规划的重要方法。分枝定界解法分枝定界解法第二十五页，本课件共有80页分枝定界解法分枝定界解法分枝定界法对可行域恰当地进行系统搜索，基本上是一分枝定界法对可行域恰当地进行系统搜索，基本上是一分枝定界法对可行域恰当地进行系统搜索，基本上是一分枝定界法对可行域恰当地进行系统搜索，基本上是一种种种种“分而治之分而治之分而治之分而治之”的策略。的策略。的策略。的策略。通常，它把可行域反复地划分为越来越小的一系列子域，称之通常，它把可行域反复地划分为越来越小的一系列子域，称之通常，它把可行域反复地划分为越来越小的一系列子域，称之通常，它把可行域反复地划分为越来越小的一系列子域，称之为为为为分枝分枝分枝分枝；子域的一个；子域的一个；子域的一个；子域的一个边界为整数边界为整数边界为整数边界为整数，在子域上解线性规划。，在子域上解线性规划。，在子域上解线性规划。，在子域上解线性规划。对于最大值问题，线性规划解的目标函数值是整数规划的对于最大值问题，线性规划解的目标函数值是整数规划的对于最大值问题，线性规划解的目标函数值是整数规划的对于最大值问题，线性规划解的目标函数值是整数规划的上界，整数规划任意可行点的目标函数值是其下界，这称上界，整数规划任意可行点的目标函数值是其下界，这称上界，整数规划任意可行点的目标函数值是其下界，这称上界，整数规划任意可行点的目标函数值是其下界，这称为为为为定界定界定界定界。在子域分解的过程中，上界非增，下界非减，经有限多次分在子域分解的过程中，上界非增，下界非减，经有限多次分在子域分解的过程中，上界非增，下界非减，经有限多次分在子域分解的过程中，上界非增，下界非减，经有限多次分解即可得到整数规划的最优解。解即可得到整数规划的最优解。解即可得到整数规划的最优解。解即可得到整数规划的最优解。第二十六页，本课件共有80页分支定界法的基本步分支定界法的基本步分支定界法的基本步分支定界法的基本步骤骤骤骤：第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解 松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题第第第第二二二二：若若若若松松松松弛弛弛弛问问问问题题题题的的的的最最最最优优优优解解解解满满满满足足足足整整整整数数数数要要要要求求求求，就就就就得得得得到到到到了了了了整整整整数规划的最优解；否则，转下一步；数规划的最优解；否则，转下一步；数规划的最优解；否则，转下一步；数规划的最优解；否则，转下一步；第第第第三三三三：任任任任意意意意选选选选一一一一个个个个非非非非整整整整数数数数解解解解的的的的变变变变量量量量xixixixi，在在在在松松松松弛弛弛弛问问问问题题题题中中中中加加加加上上上上约约约约束束束束xixixixixixixixi及及及及xixi+1xixi+1xixi+1xixi+1组组组组成成成成两两两两个个个个新新新新的的的的松松松松弛弛弛弛问问问问题题题题，称称称称为为为为分分分分枝。枝。枝。枝。新新新新的的的的松松松松弛弛弛弛问问问问题题题题具具具具有有有有特特特特征征征征：当当当当原原原原问问问问题题题题是是是是求求求求最最最最大大大大值值值值时时时时，目目目目标标标标值值值值是是是是分分分分枝枝枝枝问问问问题题题题的的的的上上上上界界界界；当当当当原原原原问问问问题题题题是是是是求求求求最最最最小小小小值值值值时时时时，目目目目标标标标值值值值是是是是分分分分枝枝枝枝问问问问题的下界；题的下界；题的下界；题的下界；第二十七页，本课件共有80页分枝定界解法分枝定界解法分支定界法的基本步分支定界法的基本步骤骤：第第四四：检检查查所所有有分分枝枝的的解解及及目目标标函函数数值值，若若某某分分枝枝的的解解是是整整数数并并且且目目标标函函数数值值大大于于（maxmax）等等等等于于于于其其其其它它它它分分分分枝枝枝枝的目标值的目标值的目标值的目标值，则将，则将其它分枝剪去其它分枝剪去不再计算。不再计算。若若还还存存在在非非整整数数解解并并且且目目标标值值大大于于（maxmaxmaxmax）整整整整数数数数解解解解的的的的目目目目标值，需要继续分枝，再检查，直到得到最优解。标值，需要继续分枝，再检查，直到得到最优解。标值，需要继续分枝，再检查，直到得到最优解。标值，需要继续分枝，再检查，直到得到最优解。第二十八页，本课件共有80页例例4-5 4-5 教材教材P92P92P92P92用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题 解：解：第一步骤：求整数规划的松弛第一步骤：求整数规划的松弛问题最优解问题最优解即求解即求解的最优解的最优解L0L0L0L0：第二十九页，本课件共有80页L0L0：采用图解法或者是单纯形法计算出唯一最优解为采用图解法或者是单纯形法计算出唯一最优解为x1=3.25 x1=3.25；x2=2.5 Z0=14.75x2=2.5 Z0=14.75第第二二步步骤骤：若若松松弛弛问问题题的的最最优优解解满满足足整整数数要要求求，就就得到来了整数规划的最优解；否则，转下一步；得到来了整数规划的最优解；否则，转下一步；我们直接转入第三步骤。我们直接转入第三步骤。我们直接转入第三步骤。我们直接转入第三步骤。第三十页，本课件共有80页x1=3.25 x1=3.25；x2=2.5x2=2.5第三步骤：任意选一个非整数解的变量第三步骤：任意选一个非整数解的变量xixixixi，在松弛问，在松弛问题中加上约束题中加上约束xixixixi及及及及xixi+1xixi+1组成两个新的组成两个新的松弛问题松弛问题，称为分枝。，称为分枝。选择选择选择选择x2x2按照按照x2 2x2 2和和x2 3x2 3进行分枝，将进行分枝，将L0L0L0L0问题划分问题划分为了两个线性规划问题，分别为：为了两个线性规划问题，分别为：L1L1：L2L2：第三十一页，本课件共有80页再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解L1L1L1L1和和L2L2的最优解为：的最优解为：L1L1（3.53.53.53.5，2 2），），L2L2（2.52.52.52.5，3 3 3 3）再分别计算其目标函数值为：再分别计算其目标函数值为：Z1=14.5 Z2=13.5Z1=14.5 Z2=13.5进入第四步骤！进入第四步骤！L1L1：L2L2：第三十二页，本课件共有80页第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的解是解是解是解是整数整数整数整数并且并且并且并且目标函数值大于（目标函数值大于（目标函数值大于（目标函数值大于（maxmaxmaxmax）等于其它分枝的目标值）等于其它分枝的目标值）等于其它分枝的目标值）等于其它分枝的目标值，则将则将则将则将其它分枝剪去其它分枝剪去其它分枝剪去其它分枝剪去不再计算。不再计算。不再计算。不再计算。若若若若还还还还存存存存在在在在非非非非整整整整数数数数解解解解并并并并且且且且目目目目标标标标值值值值大大大大于于于于（maxmaxmaxmax）整整整整数数数数解解解解的的的的目目目目标标标标值值值值，需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。L1L1L1L1（3.53.53.53.5，2 2 2 2），），），），L2L2L2L2（2.52.52.52.5，3 3 3 3）,Z1=14.5,Z2=13.5,Z1=14.5,Z2=13.5,Z1=14.5,Z2=13.5,Z1=14.5,Z2=13.5发现：还没有满足发现：还没有满足发现：还没有满足发现：还没有满足x1x1x1x1和和和和x2x2x2x2都为整数的约束，所以还需要都为整数的约束，所以还需要都为整数的约束，所以还需要都为整数的约束，所以还需要继续分枝。继续分枝。继续分枝。继续分枝。选择目标函数值较大的选择目标函数值较大的选择目标函数值较大的选择目标函数值较大的L1L1L1L1进行分枝：进行分枝：进行分枝：进行分枝：x1 3x1 3x1 3x1 3，x2 4x2 4x2 4x2 4将将将将L1L1L1L1问题划分为问题划分为问题划分为问题划分为L11L11L11L11和和和和L12L12L12L12两个线性规划问题。两个线性规划问题。两个线性规划问题。两个线性规划问题。第三十三页，本课件共有80页L11L11L11L11：L12L12：再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解L11L11L11L11和和L12L12L12L12的最优解为：的最优解为：L11L11L11L11（3 3 3 3，2 2），），L12L12（4 4，1 1）再分别计算其目标函数值为：再分别计算其目标函数值为：Z11=13 Z12=14Z11=13 Z12=14第三十四页，本课件共有80页再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解L11L11L11L11和和和和L12L12的最优解为：的最优解为：L11L11L11L11（3 3 3 3，2 2），），L12L12L12L12（4 4，1 1 1 1）再分别计算其目标函数值为：再分别计算其目标函数值为：Z11=13 Z12=14Z11=13 Z12=14我们将以上的过程用树形结构来表示为：我们将以上的过程用树形结构来表示为：L0L0：（3.253.25，2.52.5）z=14.75z=14.75L1L1：（3.53.5，2 2）z=14.5z=14.5L2L2：（2.52.5，3 3）z=13.5z=13.5L11L11：（3 3，2 2）z=13z=13L12L12：（4 4，1 1）z=14z=14第三十五页，本课件共有80页第四步骤：检查所有分枝的解及目标函数值，若第四步骤：检查所有分枝的解及目标函数值，若某分枝的某分枝的解是整数解是整数并且并且目标函数值大于（目标函数值大于（maxmax）等于其它分枝的目标值等于其它分枝的目标值，则将，则将其它分枝剪去其它分枝剪去不再不再计算。计算。L0L0：（3.253.25，2.52.5）z=14.75z=14.75L1L1：（3.53.5，2 2）z=14.5z=14.5L2L2：（2.52.5，3 3）z=13.5z=13.5L11L11：（3 3，2 2）z=13z=13L12L12：（4 4，1 1）z=14z=14整数规划问题的整数规划问题的最优解最优解若这个分枝的若这个分枝的14.5如何处理？如何处理？第三十六页，本课件共有80页分枝定界解法分枝定界解法例例4-6 4-6 求解求解问题问题 max z=40 xmax z=40 x1 1 1 1+90 x+90 x+90 x+90 x2 2 9x 9x1 1+7x+7x2 2 2 256 56 56 56 7x 7x 7x 7x1 1+20 x+20 x+20 x+20 x2 270 70 x x1 1，x x x x2 20 0 x x1 1，x x2 2 2 2整数整数 第三十七页，本课件共有80页分枝定界解法分枝定界解法解：先不考虑条件先不考虑条件，即解相应的线性规划，即解相应的线性规划B,B,(见图见图4-6-1)4-6-1)，得最优解，得最优解x x1 1=4.81=4.81，x x2 2=1.82=1.82，z z0 0=356=356 图图4-6-14-6-1（4.81，1.82）第三十八页，本课件共有80页分枝定界解法分枝定界解法首首首首先先先先注注注注意意意意到到到到相相相相应应应应的的的的线线线线性性性性规规规规划划划划问问问问题题题题的的的的解解解解中中中中有有有有一一一一个个个个非非非非整整整整数数数数变变变变量量量量，如如如如x x x x1 1 1 1=4.81=4.81=4.81=4.81。于于于于是是是是，在在在在原原原原问问问问题题题题中中中中增增增增加加加加两两两两个个个个约约约约束束束束条条条条件件件件：x x x x1 1 1 14444和和和和x x x x1 1 1 15555，将将将将原原原原问问问问题题题题分解分解分解分解为为为为两个子两个子两个子两个子问题问题问题问题B B B B1 1 1 1和和和和B B B B2 2 2 2(即两支即两支即两支即两支)。给给给给每每每每支支支支增增增增加加加加一一一一个个个个约约约约束束束束条条条条件件件件后后后后，如如如如图图图图4-6-24-6-24-6-24-6-2所所所所示示示示，并并并并不不不不影影影影响响响响问问问问题题题题的可行域。的可行域。的可行域。的可行域。第三十九页，本课件共有80页图图4-6-24-6-2x x14141414x x1515仍然不考虑整数条件约仍然不考虑整数条件约束，解问题束，解问题B1B1B1B1和和B2B2B2B2，得，得，得，得到最优解为：到最优解为：到最优解为：到最优解为：问题问题问题问题B1B1B1B1问题问题问题问题B2B2B2B2z1=349z1=349z1=349z1=349z2=341z2=341z2=341z2=341x1=4.00 x1=4.00 x1=4.00 x1=4.00 x1=5.00 x1=5.00 x1=5.00 x1=5.00 x2=2.10 x2=2.10 x2=2.10 x2=2.10 x2=1.57x2=1.57x2=1.57x2=1.57第四十页，本课件共有80页分枝定界解法分枝定界解法继继续续对对问问题题B B B B1 1和和B B B B2 2进进进进行行行行分分分分解解解解。因因因因z z z z1 1z z z z2 2，故故先先分分解解L L1 1 1 1为为两两支支。增增加加条条件件x x2 22222，称称为为问问题题B B3 3 3 3；增增加