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