《第四章整数规划与分配问题优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章整数规划与分配问题优秀课件.ppt（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章整数规划与分配问题第1页，本讲稿共80页第第4 4章章 整数规划与分配问题整数规划与分配问题第2页，本讲稿共80页第第4 4章章 整数规划与分配问题整数规划与分配问题一、整数线性规划问题的提出一、整数线性规划问题的提出二、整数规划问题的求解二、整数规划问题的求解1 1、分支定界解法、分支定界解法2 2、割平面解法、割平面解法三、三、0-10-1型整数线性规划问题的求解型整数线性规划问题的求解四、分配问题与匈牙利法四、分配问题与匈牙利法第3页，本讲稿共80页一、整数线性规划问题的提出一、整数线性规划问题的提出在前面讨论的线性规划问题中，有些最优解可能是分数或小数，在前面讨论的线性规划问题中
2、，有些最优解可能是分数或小数，在前面讨论的线性规划问题中，有些最优解可能是分数或小数，在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些问题，常要求解必须是整数但对于某些问题，常要求解必须是整数但对于某些问题，常要求解必须是整数但对于某些问题，常要求解必须是整数(称为整数解称为整数解称为整数解称为整数解)。（1 1 1 1）变量是人数、机器设备台数或产品件数等都要求是整数）变量是人数、机器设备台数或产品件数等都要求是整数）变量是人数、机器设备台数或产品件数等都要求是整数）变量是人数、机器设备台数或产品件数等都要求是整数（2 2 2 2）对某一个项目要不要投资的决策问题，可选用一
3、个对某一个项目要不要投资的决策问题，可选用一个对某一个项目要不要投资的决策问题，可选用一个对某一个项目要不要投资的决策问题，可选用一个逻辑变量逻辑变量逻辑变量逻辑变量 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
4、工作，工作，工作，工作，xij=0 xij=0 xij=0 xij=0表示不安排第表示不安排第表示不安排第表示不安排第i i i i人去做人去做人去做人去做j j j j工作。逻辑变量也是只允工作。逻辑变量也是只允工作。逻辑变量也是只允工作。逻辑变量也是只允许取整数值的一类变量。许取整数值的一类变量。许取整数值的一类变量。许取整数值的一类变量。第4页，本讲稿共80页一、整数线性规划问题的提出一、整数线性规划问题的提出整数线性规划问题的分类整数线性规划问题的分类整数线性规划问题的分类整数线性规划问题的分类根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为根
5、据对决策变量的要求不同，分为四种类型四种类型四种类型四种类型：纯整数规划：纯整数规划：纯整数规划：纯整数规划：所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。混合整数规划：混合整数规划：混合整数规划：混合整数规划：部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。0 0 0 0 1 1 1 1 整数规划：整数规划：整数规划：整数规划：所有决策变量均要求为所有决策变量均要求为所有决策变量均要求为所有决策变量均要求为0
6、 0 0 0或或或或1 1 1 1。混合混合混合混合 0 0 0 0 1 1 1 1 整数规划：整数规划：整数规划：整数规划：部分决策变量要求为部分决策变量要求为部分决策变量要求为部分决策变量要求为0 0 0 0或或或或1 1 1 1。第5页，本讲稿共80页 一、整数线性规划问题的提出一、整数线性规划问题的提出引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题例例例例4-14-14-14-1（生产组织计划问题）某工厂在一个计划期内拟生（生产组织计划问题）某工厂在一个计划期内拟生（生产组织计划问题）某工厂在一个计划期内
7、拟生（生产组织计划问题）某工厂在一个计划期内拟生产甲、乙两种大型设备。除了产甲、乙两种大型设备。除了产甲、乙两种大型设备。除了产甲、乙两种大型设备。除了A A A A、B B B B两种部件需要外部供两种部件需要外部供两种部件需要外部供两种部件需要外部供应且供应受到严格限制之外，该厂有充分的能力来加应且供应受到严格限制之外，该厂有充分的能力来加应且供应受到严格限制之外，该厂有充分的能力来加应且供应受到严格限制之外，该厂有充分的能力来加工制造这两种设备所需的其余零件，并且所需原材料工制造这两种设备所需的其余零件，并且所需原材料工制造这两种设备所需的其余零件，并且所需原材料工制造这两种设备所需的其
8、余零件，并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件和能源也可满足供应。每种设备所用部件数量和部件和能源也可满足供应。每种设备所用部件数量和部件和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表的供应限额以及设备的利润由表的供应限额以及设备的利润由表的供应限额以及设备的利润由表4-1-14-1-14-1-14-1-1给出。问该厂在给出。问该厂在给出。问该厂在给出。问该厂在本计划期内如何安排甲、乙设备的生产数量，才能获取最本计划期内如何安排甲、乙设备的生产数量，才能获取最本计划期内如何安排甲、乙设备的生产数量，才能获取最本计划期内如何安排甲、乙设备的生产数
9、量，才能获取最大利润？大利润？大利润？大利润？第6页，本讲稿共80页一、整数线性规划问题的提出一、整数线性规划问题的提出部件部件部件部件设备设备设备设备A A A AB B B B利润利润利润利润（百万）（百万）（百万）（百万）甲甲甲甲6 6 6 61 1 1 115151515乙乙乙乙4 4 4 43 3 3 320202020部件的最大部件的最大部件的最大部件的最大供应量供应量供应量供应量2525252510101010表表 4-1-14-1-1第7页，本讲稿共80页 例例例例4-14-14-14-1【解】【解】【解】【解】设设设设 x x x x1 1 1 1，x x x x2 2 2
10、2 分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，Z Z Z Z 为生产这两种设备可获得的总利润。依题意，给问题的数为生产这两种设备可获得的总利润。依题意，给问题的数为生产这两种设备可获得的总利润。依题意，给问题的数为生产这两种设备可获得的总利润。依题意，给问题的数学模型为：学模型为：学模型为：学模型为：max max max max Z Z Z Z=15=15=15=15x x x x1 1 1 1 20202020 x x x x2 2 2 2 s.t.6 s.t.6 s.t.6 s.
11、t.6x x x x1 1 1 1 4 4 4 4x x x x2 2 2 2 25 25 25 25 x x x x1 1 1 1 3 3 3 3x x x x2 2 2 2 10 10 10 10 x x x xii ii 0,1,2,0,1,2,0,1,2,0,1,2,这是一个这是一个这是一个这是一个纯整数规划问题纯整数规划问题纯整数规划问题纯整数规划问题。第8页，本讲稿共80页 一、整数线性规划问题的提出一、整数线性规划问题的提出引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题例例例例4-24-24-24-
12、2（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在 n n n n 个连锁店所在城市个连锁店所在城市个连锁店所在城市个连锁店所在城市中建立中建立中建立中建立 m m m m 个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。若在第若在第若在第若在第 i i i i 个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为 D D D D
13、ii ii，单位时间，单位时间，单位时间，单位时间的固定成本为的固定成本为的固定成本为的固定成本为 a a a ai i i i，i i i i=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。
14、应如何应如何应如何应如何选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划，才能得到经济上花，才能得到经济上花，才能得到经济上花，才能得到经济上花费最少的方案。费最少的方案。费最少的方案。费最少的方案。第9页，本讲稿共80页 例例例例4-24-24-24-2【解解解解】设在单位时间内，从配货中心设在单位时间内，从配货中心设在单位时间内，从配货中心设在单位时间内，从配货中心 i i i i 运往连锁店运往连锁店运往连锁店运往连锁店 j j j j 的的的的物资数量为物资数量为物资数量为物资数量为 x x x xijijijij
15、，Z Z Z Z 为单位时间内的总费用。引入为单位时间内的总费用。引入为单位时间内的总费用。引入为单位时间内的总费用。引入布尔变量布尔变量布尔变量布尔变量 则上述问题可归结为如下的数学模型：则上述问题可归结为如下的数学模型：则上述问题可归结为如下的数学模型：则上述问题可归结为如下的数学模型：第10页，本讲稿共80页例例例例4-2 4-2 4-2 4-2 可归结为如下的数学模型可归结为如下的数学模型可归结为如下的数学模型可归结为如下的数学模型这是一个混合这是一个混合这是一个混合这是一个混合 0 0 0 0 1 1 1 1 规划问题。规划问题。规划问题。规划问题。第11页，本讲稿共80页 例例例例
16、4-34-34-34-3某人有一背包可以装某人有一背包可以装某人有一背包可以装某人有一背包可以装10101010公斤重、公斤重、公斤重、公斤重、0.025m0.025m0.025m0.025m3 3 3 3的物的物的物的物品。他准备用来装甲、乙两种物品，每件物品的重品。他准备用来装甲、乙两种物品，每件物品的重品。他准备用来装甲、乙两种物品，每件物品的重品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表量、体积和价值如表量、体积和价值如表量、体积和价值如表4-3-14-3-14-3-14-3-1所示。问两种物品各装所示。问两种物品各装所示。问两种物品各装所示。问两种物品各装多少件，所
17、装物品的总价值最大？多少件，所装物品的总价值最大？多少件，所装物品的总价值最大？多少件，所装物品的总价值最大？物品物品物品物品重量重量重量重量（公斤（公斤（公斤（公斤/每件）每件）每件）每件）体积体积体积体积（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 4-3 4-3 解解解解 设甲、乙两种物品设甲、乙两种物品设甲、乙两种物
18、品设甲、乙两种物品各装各装各装各装x1x1x1x1、x2x2x2x2件件件件第12页，本讲稿共80页 在例在例在例在例4-34-34-34-3中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量为为为为12121212公斤，其体积是公斤，其体积是公斤，其体积是公斤，其体积是0.02m0.02m0.02m0.02m3 3 3 3。背包和旅行箱只能选择。背包和旅行箱只能选择。背包和旅行箱只能选择。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使其一，建立下列几种情形的数学模型，使其一，建立下
19、列几种情形的数学模型，使其一，建立下列几种情形的数学模型，使所装物品所装物品所装物品所装物品价值最大价值最大价值最大价值最大。情形一：所装物品不变；情形一：所装物品不变；情形一：所装物品不变；情形一：所装物品不变；情形二：如果选择情形二：如果选择情形二：如果选择情形二：如果选择旅行箱旅行箱旅行箱旅行箱，则只能装载丙和丁两种，则只能装载丙和丁两种，则只能装载丙和丁两种，则只能装载丙和丁两种物品，价值分别是物品，价值分别是物品，价值分别是物品，价值分别是4 4 4 4和和和和3 3 3 3，载重量和体积的约束为，载重量和体积的约束为，载重量和体积的约束为，载重量和体积的约束为第13页，本讲稿共80
20、页例例例例4-3 4-3 4-3 4-3【解解解解】引入引入引入引入0 0 0 01 1 1 1变量（或称逻辑变量）变量（或称逻辑变量）变量（或称逻辑变量）变量（或称逻辑变量）yi yi yi yi，令，令，令，令i i=1,2=1,2分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。情情情情形形形形一一一一：由由由由于于于于所所所所装装装装物物物物品品品品不不不不变变变变，约约约约束束束束左左左左边边边边不不不不变变变变，整整整整数数数数规规规规划划划划数数数数学学学学模模模模型为型为型为型为第14页，本讲稿共80页小结小结 通过设置逻辑变量建立整数规划的数学模型通过设置逻辑变量建立整
21、数规划的数学模型通过设置逻辑变量建立整数规划的数学模型通过设置逻辑变量建立整数规划的数学模型 约束条件的右端项可能是约束条件的右端项可能是约束条件的右端项可能是约束条件的右端项可能是r r r r个值中的某一个，即个值中的某一个，即个值中的某一个，即个值中的某一个，即 定义逻辑变量定义逻辑变量 则约束条件表示为则约束条件表示为第15页，本讲稿共80页情形二：情形二：情形二：情形二：由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型为为为为甲、乙：甲、乙：丙、丁：丙、丁：第16页，本讲稿共80页MM为充
22、分大的正数。为充分大的正数。当使用当使用背包背包时时(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)是多余的。是多余的。第17页，本讲稿共80页小结小结 mmmm个约束条件中只有个约束条件中只有个约束条件中只有个约束条件中只有k k k k个起作用个起作用个起作用个起作用 设设设设mmmm个约束条件可表示为个约束条件可表示为个约束条件可表示为个约束条件可表示为 定义定义 逻辑变量逻辑变量 又设又设MM为任意大的正数为任意大的正数 mm个约束
23、条件中只有个约束条件中只有k k个约束条件真正起到约束作用个约束条件真正起到约束作用第18页，本讲稿共80页一、整数线性规划问题的提出一、整数线性规划问题的提出综上，我们了解了整数线性规划的问题。但如何来求解整数综上，我们了解了整数线性规划的问题。但如何来求解整数综上，我们了解了整数线性规划的问题。但如何来求解整数综上，我们了解了整数线性规划的问题。但如何来求解整数线性规划问题呢？线性规划问题呢？线性规划问题呢？线性规划问题呢？为满足整数解的要求，初看起来，似乎只要把已得到的带有为满足整数解的要求，初看起来，似乎只要把已得到的带有为满足整数解的要求，初看起来，似乎只要把已得到的带有为满足整数解
24、的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过分数或小数的解经过分数或小数的解经过分数或小数的解经过“舍入化整舍入化整舍入化整舍入化整”就可以了。就可以了。就可以了。就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽但这常常是不行的，因为化整后不见得是可行解；或虽但这常常是不行的，因为化整后不见得是可行解；或虽但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。是可行解，但不一定是最优解。是可行解，但不一定是最优解。是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。因此，对求最优整数解的问题，有必要另行研究。因此，对求最优整数解
25、的问题，有必要另行研究。因此，对求最优整数解的问题，有必要另行研究。第19页，本讲稿共80页 例例例例4-4 4-4 4-4 4-4 说明整数规划问题的求解说明整数规划问题的求解说明整数规划问题的求解说明整数规划问题的求解不能不能不能不能直接在单纯形法最优解直接在单纯形法最优解直接在单纯形法最优解直接在单纯形法最优解的基础上四舍五入的基础上四舍五入的基础上四舍五入的基础上四舍五入 求下述整数规划问题的最优解（求下述整数规划问题的最优解（求下述整数规划问题的最优解（求下述整数规划问题的最优解（P85P85P85P85）：）：）：）：当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂
26、时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题结论：结论：例例例例4-44-44-44-4看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过“化整化整化整化整”来解原整来解原整来解原整来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，数线性规划，虽是最容易想到的，但常常得不
27、到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。第20页，本讲稿共80页例例例例4-4 4-4 4-4 4-4 设整数规划问题如下设整数规划问题如下设整数规划问题如下设整数规划问题如下 （也可参见教材（也可参见教材（也可参见教材（也可参见教材P85P85P85P85例例例例1 1 1 1）首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。首先不考虑整数约束，
28、得到线性规划问题（一般称为松弛问题）。第21页，本讲稿共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
29、),(2，3),3),3),3),(1(1(1(1，4),(24),(24),(24),(2，4)4)4)4)。显然，它们都不可能。显然，它们都不可能。显然，它们都不可能。显然，它们都不可能是整数规划的最优解。是整数规划的最优解。是整数规划的最优解。是整数规划的最优解。x1x233(3/2,10/3)按整数规划约束条件，其可行解按整数规划约束条件，其可行解按整数规划约束条件，其可行解按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且肯定在线性规划问题的可行域内且肯定在线性规划问题的可行域内且肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行为整数点。故整数规划问题的可行为整数
30、点。故整数规划问题的可行为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。解集是一个有限集，如右图所示。解集是一个有限集，如右图所示。解集是一个有限集，如右图所示。其中其中其中其中(2,2),(3,1)(2,2),(3,1)(2,2),(3,1)(2,2),(3,1)点的目标函数值最点的目标函数值最点的目标函数值最点的目标函数值最大，即为大，即为大，即为大，即为Z=4Z=4Z=4Z=4。第22页，本讲稿共80页二、纯整数规划的求解二、纯整数规划的求解整数规划的求解比一般线性规划的求解复杂，常用的整数规划的求解比一般线性规划的求解复杂，常用的整数规划的求解比一般线性规划的求解复杂，常用
31、的整数规划的求解比一般线性规划的求解复杂，常用的方法有完全枚举法、分支定界法，割平面法、隐枚举方法有完全枚举法、分支定界法，割平面法、隐枚举方法有完全枚举法、分支定界法，割平面法、隐枚举方法有完全枚举法、分支定界法，割平面法、隐枚举法和法和法和法和lagrangelagrangelagrangelagrange松弛法。松弛法。松弛法。松弛法。第23页，本讲稿共80页在在在在求求求求解解解解整整整整数数数数线线线线性性性性规规规规划划划划时时时时，如如如如果果果果可可可可行行行行域域域域是是是是有有有有界界界界的的的的，首首首首先先先先容容容容易易易易想想想想到到到到的的的的方方方方法法法法就就
32、就就是是是是穷穷穷穷举举举举所所所所有有有有可可可可行行行行的的的的整整整整数数数数解解解解，即即即即列列列列出出出出图图图图解解解解中中中中所所所所有有有有标标标标有有有有“+”的的的的整整整整数数数数点，然后比较它们的目标函数值，从而确定最优解。点，然后比较它们的目标函数值，从而确定最优解。点，然后比较它们的目标函数值，从而确定最优解。点，然后比较它们的目标函数值，从而确定最优解。例例例例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所所所所能能能能
33、取取取取的的的的整整整整数数数数值值值值为为为为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个个个个，穷穷穷穷举举举举法法法法还还还还是是是是勉勉勉勉强强强强可可可可用用用用的。的。的
34、。的。对对对对于大型于大型于大型于大型问题问题问题问题，可行的整数，可行的整数，可行的整数，可行的整数组组组组合数会很大。合数会很大。合数会很大。合数会很大。例例例例如如如如在在在在指指指指派派派派问问问问题题题题中中中中，将将将将n n n n项项项项任任任任务务务务指指指指派派派派n n n n个个个个人人人人去去去去完完完完成成成成，不不不不同同同同的的的的指指指指派派派派方方方方案案案案共共共共有有有有n!n!n!n!种种种种，当当当当n=10n=10n=10n=10时时时时，可可可可能能能能的的的的指指指指派派派派方方方方案案案案数数数数超超超超过过过过300300300300万万万
35、万；当当当当n=20n=20n=20n=20，超，超，超，超过过过过21021021021018181818。显显显显然，然，然，然，穷举穷举穷举穷举法是不可取的。法是不可取的。法是不可取的。法是不可取的。第24页，本讲稿共80页应应应应寻寻寻寻找找找找仅仅仅仅检检检检查查查查可可可可行行行行的的的的整整整整数数数数组组组组合合合合的的的的一一一一部部部部分分分分，就就就就能能能能定定定定出出出出最最最最优优优优的整数解的方法。的整数解的方法。的整数解的方法。的整数解的方法。分支定界解法分支定界解法分支定界解法分支定界解法就是其中之一。就是其中之一。就是其中之一。就是其中之一。分支定界法可用于
36、解分支定界法可用于解分支定界法可用于解分支定界法可用于解纯纯纯纯整数或混合整数整数或混合整数整数或混合整数整数或混合整数线线线线性性性性规规规规划划划划问题问题问题问题。20202020世世世世纪纪纪纪60606060年年年年代代代代初初初初由由由由Land Land Land Land DoigDoigDoigDoig和和和和DakinDakinDakinDakin等等等等提提提提出出出出，是解整数是解整数是解整数是解整数线线线线性性性性规规规规划的重要方法之一。划的重要方法之一。划的重要方法之一。划的重要方法之一。由由由由于于于于这这这这方方方方法法法法灵灵灵灵活活活活且且且且便便便便于于
37、于于用用用用计计计计算算算算机机机机求求求求解解解解，所所所所以以以以现现现现在在在在它已是解整数规划的重要方法。它已是解整数规划的重要方法。它已是解整数规划的重要方法。它已是解整数规划的重要方法。分枝定界解法分枝定界解法第25页，本讲稿共80页分枝定界解法分枝定界解法分枝定界法对可行域恰当地进行系统搜索，基本上是一种分枝定界法对可行域恰当地进行系统搜索，基本上是一种分枝定界法对可行域恰当地进行系统搜索，基本上是一种分枝定界法对可行域恰当地进行系统搜索，基本上是一种“分而治之分而治之分而治之分而治之”的策略。的策略。的策略。的策略。通常，它把可行域反复地划分为越来越小的一系列子域，称通常，它把
38、可行域反复地划分为越来越小的一系列子域，称通常，它把可行域反复地划分为越来越小的一系列子域，称通常，它把可行域反复地划分为越来越小的一系列子域，称之为之为之为之为分枝分枝分枝分枝；子域的一个；子域的一个；子域的一个；子域的一个边界为整数边界为整数边界为整数边界为整数，在子域上解线性规划。，在子域上解线性规划。，在子域上解线性规划。，在子域上解线性规划。对于最大值问题，线性规划解的目标函数值是整数规划的上界，对于最大值问题，线性规划解的目标函数值是整数规划的上界，对于最大值问题，线性规划解的目标函数值是整数规划的上界，对于最大值问题，线性规划解的目标函数值是整数规划的上界，整数规划任意可行点的目
39、标函数值是其下界，这称为整数规划任意可行点的目标函数值是其下界，这称为整数规划任意可行点的目标函数值是其下界，这称为整数规划任意可行点的目标函数值是其下界，这称为定界定界定界定界。在子域分解的过程中，上界非增，下界非减，经有限多次在子域分解的过程中，上界非增，下界非减，经有限多次在子域分解的过程中，上界非增，下界非减，经有限多次在子域分解的过程中，上界非增，下界非减，经有限多次分解即可得到整数规划的最优解。分解即可得到整数规划的最优解。分解即可得到整数规划的最优解。分解即可得到整数规划的最优解。第26页，本讲稿共80页分支定界法的基本步分支定界法的基本步分支定界法的基本步分支定界法的基本步骤骤
40、骤骤：第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解 松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题第第第第二二二二：若若若若松松松松弛弛弛弛问问问问题题题题的的的的最最最最优优优优解解解解满满满满足足足足整整整整数数数数要要要要求求求求，就就就就得得得得到到到到了了了了整整整整数数数数规规规规划划划划的最优解；否则，转下一步；的最优解；否则，转下一步；的最优解；否则，转下一步；的最优
41、解；否则，转下一步；第第第第三三三三：任任任任意意意意选选选选一一一一个个个个非非非非整整整整数数数数解解解解的的的的变变变变量量量量xixixixi，在在在在松松松松弛弛弛弛问问问问题题题题中中中中加加加加上上上上约约约约束束束束xixixixixixixixi及及及及xixi+1xixi+1xixi+1xixi+1组成两个新的松弛问题组成两个新的松弛问题组成两个新的松弛问题组成两个新的松弛问题，称为分枝。，称为分枝。，称为分枝。，称为分枝。新新新新的的的的松松松松弛弛弛弛问问问问题题题题具具具具有有有有特特特特征征征征：当当当当原原原原问问问问题题题题是是是是求求求求最最最最大大大大值值值
42、值时时时时，目目目目标标标标值值值值是是是是分分分分枝枝枝枝问问问问题题题题的的的的上上上上界界界界；当当当当原原原原问问问问题题题题是是是是求求求求最最最最小小小小值值值值时时时时，目目目目标标标标值值值值是是是是分分分分枝枝枝枝问问问问题题题题的的的的下界；下界；下界；下界；第27页，本讲稿共80页分枝定界解法分枝定界解法分支定界法的基本步分支定界法的基本步分支定界法的基本步分支定界法的基本步骤骤骤骤：第第第第四四四四：检检检检查查查查所所所所有有有有分分分分枝枝枝枝的的的的解解解解及及及及目目目目标标标标函函函函数数数数值值值值，若若若若某某某某分分分分枝枝枝枝的的的的解解解解是是是是整
43、整整整数数数数并并并并且且且且目目目目标标标标函函函函数数数数值值值值大大大大于于于于（maxmaxmaxmax）等等等等于于于于其其其其它它它它分分分分枝枝枝枝的的的的目目目目标值标值标值标值，则将，则将，则将，则将其它分枝剪去其它分枝剪去其它分枝剪去其它分枝剪去不再计算。不再计算。不再计算。不再计算。若若若若还还还还存存存存在在在在非非非非整整整整数数数数解解解解并并并并且且且且目目目目标标标标值值值值大大大大于于于于（maxmaxmaxmax）整整整整数数数数解解解解的的的的目目目目标标标标值值值值，需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。需要继续分枝
44、，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。第28页，本讲稿共80页例例例例4-5 4-5 4-5 4-5 教材教材教材教材P92P92P92P92用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题 解：解：解：解：第一步骤：求整数规划的松弛第一步骤：求整数规划的松弛第一步骤：求整数规划的松弛第一步骤：求整数规划的松弛问题最优解问题最优解问题最优解问题最优解即求解即求解即求解即求解的最优解的最优解的最优解的最优解L0L0L0L0：第29页，本讲稿共80页L0L0L0L0：采用图解法或者是单
45、纯形法计算出唯一最优解为采用图解法或者是单纯形法计算出唯一最优解为采用图解法或者是单纯形法计算出唯一最优解为采用图解法或者是单纯形法计算出唯一最优解为x1=3.25 x1=3.25 x1=3.25 x1=3.25；x2=2.5 Z0=14.75x2=2.5 Z0=14.75x2=2.5 Z0=14.75x2=2.5 Z0=14.75第第第第二二二二步步步步骤骤骤骤：若若若若松松松松弛弛弛弛问问问问题题题题的的的的最最最最优优优优解解解解满满满满足足足足整整整整数数数数要要要要求求求求，就就就就得得得得到到到到来来来来了了了了整数规划的最优解；否则，转下一步；整数规划的最优解；否则，转下一步；整
46、数规划的最优解；否则，转下一步；整数规划的最优解；否则，转下一步；我们直接转入第三步骤。我们直接转入第三步骤。我们直接转入第三步骤。我们直接转入第三步骤。第30页，本讲稿共80页x1=3.25 x1=3.25 x1=3.25 x1=3.25；x2=2.5x2=2.5x2=2.5x2=2.5第三步骤：任意选一个非整数解的变量第三步骤：任意选一个非整数解的变量第三步骤：任意选一个非整数解的变量第三步骤：任意选一个非整数解的变量xixixixi，在松弛问题中，在松弛问题中，在松弛问题中，在松弛问题中加上约束加上约束加上约束加上约束xixixixixixixixi及及及及xixi+1xixi+1xix
47、i+1xixi+1组成两个新的松弛问题组成两个新的松弛问题组成两个新的松弛问题组成两个新的松弛问题，称为分枝。称为分枝。称为分枝。称为分枝。选择选择选择选择x2x2x2x2按照按照按照按照x2 2x2 2x2 2x2 2和和和和x2 3x2 3x2 3x2 3进行分枝，将进行分枝，将进行分枝，将进行分枝，将L0L0L0L0问题划分为问题划分为问题划分为问题划分为了两个线性规划问题，分别为：了两个线性规划问题，分别为：了两个线性规划问题，分别为：了两个线性规划问题，分别为：L1L1L1L1：L2L2L2L2：第31页，本讲稿共80页再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解再用图解
48、法或单纯形法分别求解再用图解法或单纯形法分别求解L1L1L1L1和和和和L2L2L2L2的最优解为：的最优解为：的最优解为：的最优解为：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.5Z1=14.5 Z2=13.5Z1=14.5 Z2=13.5Z1=14.5 Z2=13.5进入第四步骤！进入第四步骤！进入第四步骤！进入第四步骤！L1L1L1L1：L2L2L2L2：第32页，本讲
49、稿共80页第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的解解解解是整数是整数是整数是整数并且并且并且并且目标函数值大于（目标函数值大于（目标函数值大于（目标函数值大于（maxmaxmaxmax）等于其它分枝的目标值）等于其它分枝的目标值）等于其它分枝的目标值）等于其它分枝的目标值，则将则将则将则将其它分枝剪去其它分枝剪去其它分枝剪去其它分枝剪去不再计算。不再计算。不再计算。不再计算。若若若若还还还还存存存存在在在在非非非非整整整整数数数数解解
50、解解并并并并且且且且目目目目标标标标值值值值大大大大于于于于（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发现：还没有满足发现：还没有满足发现：还