第四章整数规划与分配问题精选文档.ppt

《第四章整数规划与分配问题精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章整数规划与分配问题精选文档.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章整数规划与分配问题本讲稿第一页，共八十页第第4 4章章 整数规划与分配问题整数规划与分配问题本讲稿第二页，共八十页第第4 4章章 整数规划与分配问题整数规划与分配问题一、整数线性规划问题的提出一、整数线性规划问题的提出二、整数规划问题的求解二、整数规划问题的求解1 1、分支定界解法、分支定界解法2 2、割平面解法、割平面解法三、三、0-10-1型整数线性规划问题的求解型整数线性规划问题的求解四、分配问题与匈牙利法四、分配问题与匈牙利法本讲稿第三页，共八十页一、整数线性规划问题的提出一、整数线性规划问题的提出在前面讨论的线性规划问题中，有些最优解可能是分数或在前面讨论的线性规划问题中，有些

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 j工作

4、，工作，工作，工作，xij=0 xij=0 xij=0 xij=0表示不安排第表示不安排第表示不安排第表示不安排第i i i i人去做人去做人去做人去做j j j j工作。逻辑变量也是只允工作。逻辑变量也是只允工作。逻辑变量也是只允工作。逻辑变量也是只允许取整数值的一类变量。许取整数值的一类变量。许取整数值的一类变量。许取整数值的一类变量。本讲稿第四页，共八十页一、整数线性规划问题的提出一、整数线性规划问题的提出整数线性规划问题的分类整数线性规划问题的分类整数线性规划问题的分类整数线性规划问题的分类根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为根据对决策变量的要求不同，分为根据对

5、决策变量的要求不同，分为四种类型四种类型四种类型四种类型：纯整数规划：纯整数规划：纯整数规划：纯整数规划：所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。所有决策变量均要求为离散的非负整数。混合整数规划：混合整数规划：混合整数规划：混合整数规划：部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。部分决策变量要求为离散的非负整数。0 0 0 0 1 1 1 1 整数规划：整数规划：整数规划：整数规划：所有决策变量均要求为所有决策变量均要求为所有决策变量均要求为所有决策变量均要求为0 0

6、 0 0或或或或1 1 1 1。混合混合混合混合 0 0 0 0 1 1 1 1 整数规划：整数规划：整数规划：整数规划：部分决策变量要求为部分决策变量要求为部分决策变量要求为部分决策变量要求为0 0 0 0或或或或1 1 1 1。本讲稿第五页，共八十页 一、整数线性规划问题的提出一、整数线性规划问题的提出引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题例例例例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、排甲、乙设备的生产数量，才能获取最大利润？本讲稿第六页，共八十页一、整数线性规划问题的提出一、整数线性规划问题的提出部件部件部件部件设备设备设备设备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本讲稿第七页，共八十页 例例例例4-14-14-14-1【解】【解】【解】【解】设设设设 x x x x1 1 1 1，x x x x2 2 2 2

10、分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，分别为该计划期内甲、乙设备的生产数量，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.t.

11、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 xi i i i 0,1,2,0,1,2,0,1,2,0,1,2,这是一个这是一个这是一个这是一个纯整数规划问题纯整数规划问题纯整数规划问题纯整数规划问题。本讲稿第八页，共八十页 一、整数线性规划问题的提出一、整数线性规划问题的提出引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题例例例例4-24-24-24-

12、2（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在（选址问题）某商业连锁集团拟在 n n n n 个连锁店所在城市个连锁店所在城市个连锁店所在城市个连锁店所在城市中建立中建立中建立中建立 m m m m 个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。个配货中心，每个城市最多建立一个配货中心。若在第若在第若在第若在第 i i i i 个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为个城市建立配货中心，其配货能力为 D D D D

13、i i i i，单位时间的，单位时间的，单位时间的，单位时间的固定成本为固定成本为固定成本为固定成本为 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 i

14、j。应如何应如何应如何应如何选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划选择配货中心位置和安排运输计划，才能得到经济上花费，才能得到经济上花费，才能得到经济上花费，才能得到经济上花费最少的方案。最少的方案。最少的方案。最少的方案。本讲稿第九页，共八十页 例例4-24-2【解解】设在单位时间内，从配货中心设在单位时间内，从配货中心 i i 运往连锁店运往连锁店 j j 的的物资数量为物资数量为 x xijij，Z Z 为单位时间内的总费用。引入为单位时间内的总费用。引入布尔变量布尔变量 则上述问题可归结为如下的数学模型：则上述问题可归结为如下的数学模

15、型：本讲稿第十页，共八十页例例例例4-2 4-2 4-2 4-2 可归结为如下的数学模型可归结为如下的数学模型可归结为如下的数学模型可归结为如下的数学模型这是一个混合这是一个混合这是一个混合这是一个混合 0 0 0 0 1 1 1 1 规划问题。规划问题。规划问题。规划问题。本讲稿第十一页，共八十页 例例4-34-3某人有一背包可以装某人有一背包可以装1010公斤重、公斤重、0.025m0.025m3 3的物的物品。他准备用来装甲、乙两种物品，每件物品的重品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表量、体积和价值如表4-3-14-3-1所示。问两种物品各装所示。问两种物品各装

16、多少件，所装物品的总价值最大？多少件，所装物品的总价值最大？物品物品物品物品重量重量重量重量（公斤（公斤（公斤（公斤/每件）每件）每件）每件）体积体积体积体积（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 解解解解 设甲、乙两种物品各设甲、乙两种物品各设甲、乙两种物品各设甲、乙两种物品各装装装装x1x1x1x1

17、、x2x2x2x2件件件件本讲稿第十二页，共八十页 在例在例4-34-3中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量为为1212公斤，其体积是公斤，其体积是0.02m0.02m3 3。背包和旅行箱只能选择。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使其一，建立下列几种情形的数学模型，使所装物品所装物品价值最大价值最大。情形一：所装物品不变；情形一：所装物品不变；情形二：如果选择情形二：如果选择旅行箱旅行箱，则只能装载丙和丁两种，则只能装载丙和丁两种物品，价值分别是物品，价值分别是4 4和和3 3，载重量和体积的约束为，载重量和体积的约束为本讲稿第十三

18、页，共八十页例例例例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分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。情情情情形形形形一一一一：由由由由于于于于所所所所装装装装物物物物品品品品不不不不变变变变，约约约约束束束束左左左左边边边边不不不不变变变变，整整整整数数数数规规规规划划划划数数数数学学学学模模模模型型型型为为为为本讲稿第十四页，共八十页小结小结 通过设置逻辑变量建立整数规划的数学模型通过设置逻辑

19、变量建立整数规划的数学模型通过设置逻辑变量建立整数规划的数学模型通过设置逻辑变量建立整数规划的数学模型 约束条件的右端项可能是约束条件的右端项可能是约束条件的右端项可能是约束条件的右端项可能是r r r r个值中的某一个，即个值中的某一个，即个值中的某一个，即个值中的某一个，即定义逻辑变量定义逻辑变量定义逻辑变量定义逻辑变量则约束条件表示为则约束条件表示为则约束条件表示为则约束条件表示为本讲稿第十五页，共八十页情形二：情形二：情形二：情形二：由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型为为为为甲

20、、乙：甲、乙：丙、丁：丙、丁：本讲稿第十六页，共八十页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)是多余的。是多余的。本讲稿第十七页，共八十页小结小结 mmmm个约束条件中只有个约束条件中只有个约束条件中只有个约束条件中只有k k k k个起作用个起作用个起作用个起作用 设设设设mmmm个约束条件可表示为个约束条件可表示为个约束条件可表示为个约束条件可表示为定义定义定义定义 逻

21、辑变量逻辑变量逻辑变量逻辑变量又设又设又设又设MMMM为任意大的正数为任意大的正数为任意大的正数为任意大的正数mmmm个约束条件中只有个约束条件中只有个约束条件中只有个约束条件中只有k k k k个约束条件真正起到约束作用个约束条件真正起到约束作用个约束条件真正起到约束作用个约束条件真正起到约束作用本讲稿第十八页，共八十页一、整数线性规划问题的提出一、整数线性规划问题的提出综上，我们了解了整数线性规划的问题。但如何来求解整综上，我们了解了整数线性规划的问题。但如何来求解整综上，我们了解了整数线性规划的问题。但如何来求解整综上，我们了解了整数线性规划的问题。但如何来求解整数线性规划问题呢？数线性

22、规划问题呢？数线性规划问题呢？数线性规划问题呢？为满足整数解的要求，初看起来，似乎只要把已得到的带有为满足整数解的要求，初看起来，似乎只要把已得到的带有为满足整数解的要求，初看起来，似乎只要把已得到的带有为满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过分数或小数的解经过分数或小数的解经过分数或小数的解经过“舍入化整舍入化整舍入化整舍入化整”就可以了。就可以了。就可以了。就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可但这常常是不行的，因为化整后不见得是可行解；或虽是可但这常常是不行的，因为化整后不见得是可行解；或虽是可但这常常是不行的，因为化整后不见得是可行

23、解；或虽是可行解，但不一定是最优解。行解，但不一定是最优解。行解，但不一定是最优解。行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。因此，对求最优整数解的问题，有必要另行研究。因此，对求最优整数解的问题，有必要另行研究。因此，对求最优整数解的问题，有必要另行研究。本讲稿第十九页，共八十页 例例例例4-4 4-4 4-4 4-4 说明整数规划问题的求解说明整数规划问题的求解说明整数规划问题的求解说明整数规划问题的求解不能不能不能不能直接在单纯形法最优解直接在单纯形法最优解直接在单纯形法最优解直接在单纯形法最优解的基础上四舍五入的基础上四舍五入的基础上四舍五入的基础上四舍五入

24、求下述整数规划问题的最优解（求下述整数规划问题的最优解（求下述整数规划问题的最优解（求下述整数规划问题的最优解（P85P85P85P85）：）：）：）：当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题当整数规划问题暂时不考虑整数约束时，称为松弛问题结论：结论：例例例例4-44-44-44-4看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过看出，将其相应的线性规划的最优解经过“化整化整化整化整”来来来来解原整数线性规划，虽是最容易想到的，但常

25、常得不到整数线性解原整数线性规划，虽是最容易想到的，但常常得不到整数线性解原整数线性规划，虽是最容易想到的，但常常得不到整数线性解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规规划的最优解，甚至根本不是可行解。因此有必要对整数线性规规划的最优解，甚至根本不是可行解。因此有必要对整数线性规规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。划的解法进行专门研究。划的解法进行专门研究。划的解法进行专门研究。本讲稿第二十页，共八十页例例例例4-4 4-4 4-4 4-4 设整数规划问题如下设整数规划问题如下设整

26、数规划问题如下设整数规划问题如下 （也可参见教材（也可参见教材（也可参见教材（也可参见教材P85P85P85P85例例例例1 1 1 1）首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。本讲稿第二十一页，共八十页用图解法求出最优解为：用图解法求出最优解为：用图解法求出最优解为：用图解法求出最优解为：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现求整数解现求整数解现求整数解现

27、求整数解(最优解最优解最优解最优解):):):):如用舍入如用舍入如用舍入如用舍入取整法可得到取整法可得到取整法可得到取整法可得到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)按整数规划约束条件，其可行按整数规划约束条件，其可行按整数规划约束条件，其可行按

28、整数规划约束条件，其可行解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域内且为整数点。故整数规划问题内且为整数点。故整数规划问题内且为整数点。故整数规划问题内且为整数点。故整数规划问题的可行解集是一个有限集，如右的可行解集是一个有限集，如右的可行解集是一个有限集，如右的可行解集是一个有限集，如右图所示。其中图所示。其中图所示。其中图所示。其中(2,2),(3,1)(2,2),(3,1)(2,2),(3,1)(2,2),(3,1)点的目点的目点的目点的目标函数值最大，即为标函数值最大，即为标函数值最大，即为标函数值最大，即为Z=4Z

29、=4Z=4Z=4。本讲稿第二十二页，共八十页二、纯整数规划的求解二、纯整数规划的求解整数规划的求解比一般线性规划的求解复杂，常用的整数规划的求解比一般线性规划的求解复杂，常用的整数规划的求解比一般线性规划的求解复杂，常用的整数规划的求解比一般线性规划的求解复杂，常用的方法有完全枚举法、分支定界法，割平面法、隐枚举方法有完全枚举法、分支定界法，割平面法、隐枚举方法有完全枚举法、分支定界法，割平面法、隐枚举方法有完全枚举法、分支定界法，割平面法、隐枚举法和法和法和法和lagrangelagrangelagrangelagrange松弛法。松弛法。松弛法。松弛法。本讲稿第二十三页，共八十页在在在在求

30、求求求解解解解整整整整数数数数线线线线性性性性规规规规划划划划时时时时，如如如如果果果果可可可可行行行行域域域域是是是是有有有有界界界界的的的的，首首首首先先先先容容容容易易易易想想想想到到到到的的的的方方方方法法法法就就就就是是是是穷穷穷穷举举举举所所所所有有有有可可可可行行行行的的的的整整整整数数数数解解解解，即即即即列列列列出出出出图图图图解解解解中中中中所所所所有有有有标标标标有有有有“+”的整数点，然后比较它们的目标函数值，从而确定最优解。的整数点，然后比较它们的目标函数值，从而确定最优解。的整数点，然后比较它们的目标函数值，从而确定最优解。的整数点，然后比较它们的目标函数值，从而确

31、定最优解。例例例例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个个个个。因因因因此此此此所所所所有有有有可可可可能能能能的的的的整整整整数

32、数数数组组组组合合合合(不都是可行的不都是可行的不都是可行的不都是可行的)数是数是数是数是34=1234=1234=1234=12个，个，个，个，穷举穷举穷举穷举法法法法还还还还是勉是勉是勉是勉强强强强可用的。可用的。可用的。可用的。对对对对于大型于大型于大型于大型问题问题问题问题，可行的整数，可行的整数，可行的整数，可行的整数组组组组合数会很大。合数会很大。合数会很大。合数会很大。例例例例如如如如在在在在指指指指派派派派问问问问题题题题中中中中，将将将将n n n n项项项项任任任任务务务务指指指指派派派派n n n n个个个个人人人人去去去去完完完完成成成成，不不不不同同同同的的的的指指指

33、指派派派派方方方方案案案案共共共共有有有有n!n!n!n!种种种种，当当当当n=10n=10n=10n=10时时时时，可可可可能能能能的的的的指指指指派派派派方方方方案案案案数数数数超超超超过过过过300300300300万万万万；当当当当n=20n=20n=20n=20，超超超超过过过过21021021021018181818。显显显显然，然，然，然，穷举穷举穷举穷举法是不可取的。法是不可取的。法是不可取的。法是不可取的。本讲稿第二十四页，共八十页应应应应寻寻寻寻找找找找仅仅仅仅检检检检查查查查可可可可行行行行的的的的整整整整数数数数组组组组合合合合的的的的一一一一部部部部分分分分，就就就就

34、能能能能定定定定出出出出最最最最优优优优的的的的整整整整数解的方法。数解的方法。数解的方法。数解的方法。分支定界解法分支定界解法分支定界解法分支定界解法就是其中之一。就是其中之一。就是其中之一。就是其中之一。分支定界法可用于解分支定界法可用于解分支定界法可用于解分支定界法可用于解纯纯纯纯整数或混合整数整数或混合整数整数或混合整数整数或混合整数线线线线性性性性规规规规划划划划问题问题问题问题。2020世世纪纪6060年年代代初初由由Land Land DoigDoig和和DakinDakin等等提提出出，是解整数是解整数线线性性规规划的重要方法之一。划的重要方法之一。由由于于这这方方法法灵灵活活

35、且且便便于于用用计计算算机机求求解解，所所以以现现在在它已是解整数规划的重要方法。它已是解整数规划的重要方法。分枝定界解法分枝定界解法本讲稿第二十五页，共八十页分枝定界解法分枝定界解法分枝定界法对可行域恰当地进行系统搜索，基本上是一种分枝定界法对可行域恰当地进行系统搜索，基本上是一种分枝定界法对可行域恰当地进行系统搜索，基本上是一种分枝定界法对可行域恰当地进行系统搜索，基本上是一种“分分分分而治之而治之而治之而治之”的策略。的策略。的策略。的策略。通常，它把可行域反复地划分为越来越小的一系列子域，称之通常，它把可行域反复地划分为越来越小的一系列子域，称之通常，它把可行域反复地划分为越来越小的一

36、系列子域，称之通常，它把可行域反复地划分为越来越小的一系列子域，称之为为为为分枝分枝分枝分枝；子域的一个；子域的一个；子域的一个；子域的一个边界为整数边界为整数边界为整数边界为整数，在子域上解线性规划。，在子域上解线性规划。，在子域上解线性规划。，在子域上解线性规划。对于最大值问题，线性规划解的目标函数值是整数规划的上界，对于最大值问题，线性规划解的目标函数值是整数规划的上界，对于最大值问题，线性规划解的目标函数值是整数规划的上界，对于最大值问题，线性规划解的目标函数值是整数规划的上界，整数规划任意可行点的目标函数值是其下界，这称为整数规划任意可行点的目标函数值是其下界，这称为整数规划任意可行

37、点的目标函数值是其下界，这称为整数规划任意可行点的目标函数值是其下界，这称为定界定界定界定界。在子域分解的过程中，上界非增，下界非减，经有限多次在子域分解的过程中，上界非增，下界非减，经有限多次在子域分解的过程中，上界非增，下界非减，经有限多次在子域分解的过程中，上界非增，下界非减，经有限多次分解即可得到整数规划的最优解。分解即可得到整数规划的最优解。分解即可得到整数规划的最优解。分解即可得到整数规划的最优解。本讲稿第二十六页，共八十页分支定界法的基本步分支定界法的基本步分支定界法的基本步分支定界法的基本步骤骤骤骤：第一：求整数规划的松弛问题最优解第一：求整数规划的松弛问题最优解第一：求整数规

38、划的松弛问题最优解第一：求整数规划的松弛问题最优解 松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题松弛问题：即不考虑整数约束条件的线性规划问题第第第第二二二二：若若若若松松松松弛弛弛弛问问问问题题题题的的的的最最最最优优优优解解解解满满满满足足足足整整整整数数数数要要要要求求求求，就就就就得得得得到到到到了了了了整整整整数数数数规划的最优解；否则，转下一步；规划的最优解；否则，转下一步；规划的最优解；否则，转下一步；规划的最优解；否则，转下一步；第第第第三三三三：任任任任意意意意选选选选一一一一个个个个非非非

39、非整整整整数数数数解解解解的的的的变变变变量量量量xixixixi，在在在在松松松松弛弛弛弛问问问问题题题题中中中中加加加加上上上上约束约束约束约束xixixixixixixixi及及及及xixi+1xixi+1xixi+1xixi+1组成两个新的松弛问题组成两个新的松弛问题组成两个新的松弛问题组成两个新的松弛问题，称为分枝。，称为分枝。，称为分枝。，称为分枝。新新新新的的的的松松松松弛弛弛弛问问问问题题题题具具具具有有有有特特特特征征征征：当当当当原原原原问问问问题题题题是是是是求求求求最最最最大大大大值值值值时时时时，目目目目标标标标值值值值是是是是分分分分枝枝枝枝问问问问题题题题的的的的

40、上上上上界界界界；当当当当原原原原问问问问题题题题是是是是求求求求最最最最小小小小值值值值时时时时，目目目目标标标标值值值值是是是是分分分分枝枝枝枝问问问问题的下界；题的下界；题的下界；题的下界；本讲稿第二十七页，共八十页分枝定界解法分枝定界解法分支定界法的基本步分支定界法的基本步分支定界法的基本步分支定界法的基本步骤骤骤骤：第第第第四四四四：检检检检查查查查所所所所有有有有分分分分枝枝枝枝的的的的解解解解及及及及目目目目标标标标函函函函数数数数值值值值，若若若若某某某某分分分分枝枝枝枝的的的的解解解解是是是是整整整整数数数数并并并并且且且且目目目目标标标标函函函函数数数数值值值值大大大大于于

41、于于（maxmaxmaxmax）等等等等于于于于其其其其它它它它分分分分枝枝枝枝的的的的目目目目标标标标值值值值，则将则将则将则将其它分枝剪去其它分枝剪去其它分枝剪去其它分枝剪去不再计算。不再计算。不再计算。不再计算。若若若若还还还还存存存存在在在在非非非非整整整整数数数数解解解解并并并并且且且且目目目目标标标标值值值值大大大大于于于于（maxmaxmaxmax）整整整整数数数数解解解解的的的的目目目目标标标标值值值值，需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。需要继续分枝，再检查，直到得到最优解。本讲稿第二十八页，共八十

42、页例例例例4-5 4-5 4-5 4-5 教材教材教材教材P92P92P92P92用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题用分枝定界法求解下列纯整数规划问题 解：解：解：解：第一步骤：求整数规划的松弛问第一步骤：求整数规划的松弛问第一步骤：求整数规划的松弛问第一步骤：求整数规划的松弛问题最优解题最优解题最优解题最优解即求解即求解即求解即求解的最优解的最优解的最优解的最优解L0L0L0L0：本讲稿第二十九页，共八十页L0L0L0L0：采用图解法或者是单纯形法计算出唯一最优解为采用图解法或者是单纯形法计算出唯一最优解为采用图解法或者是单

43、纯形法计算出唯一最优解为采用图解法或者是单纯形法计算出唯一最优解为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第第第第二二二二步步步步骤骤骤骤：若若若若松松松松弛弛弛弛问问问问题题题题的的的的最最最最优优优优解解解解满满满满足足足足整整整整数数数数要要要要求求求求，就就就就得得得得到到到到来来来来了整数规划的最优解；否则，转下一步；了整数规划的最优解；否则，转下一步；了整数规划的最优解；否则，转下一步；了整数规划的最优解；否则，转下一步；我们直接转入第三步

44、骤。我们直接转入第三步骤。我们直接转入第三步骤。我们直接转入第三步骤。本讲稿第三十页，共八十页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+1xixi+1xixi+1组成两个新的松弛问组成两个新的松弛问组成两个新的松弛问组成两个新的

45、松弛问题题题题，称为分枝。，称为分枝。，称为分枝。，称为分枝。选择选择选择选择x2x2x2x2按照按照按照按照x2 2x2 2x2 2x2 2和和和和x2 3x2 3x2 3x2 3进行分枝，将进行分枝，将进行分枝，将进行分枝，将L0L0L0L0问题划分问题划分问题划分问题划分为了两个线性规划问题，分别为：为了两个线性规划问题，分别为：为了两个线性规划问题，分别为：为了两个线性规划问题，分别为：L1L1L1L1：L2L2L2L2：本讲稿第三十一页，共八十页再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解L1L1L1L1和和和和L2

46、L2L2L2的最优解为：的最优解为：的最优解为：的最优解为：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：本讲稿第三十二页，共八十页第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查

47、所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的第四步骤：检查所有分枝的解及目标函数值，若某分枝的解解解解是整数是整数是整数是整数并且并且并且并且目标函数值大于（目标函数值大于（目标函数值大于（目标函数值大于（maxmaxmaxmax）等于其它分枝的目标值）等于其它分枝的目标值）等于其它分枝的目标值）等于其它分枝的目标值，则将则将则将则将其它分枝剪去其它分枝剪去其它分枝剪去其它分枝剪去不再计算。不再计算。不再计算。不再计算。若若若若还还还还存存存存在在在在非非非非整整整整数数数数解解解解并并并并且且且且目目目目标标标标值值值值大大大大于于于于（maxmax

48、maxmax）整整整整数数数数解解解解的的的的目目目目标标标标值值值值，需需需需要继续分枝，再检查，直到得到最优解。要继续分枝，再检查，直到得到最优解。要继续分枝，再检查，直到得到最优解。要继续分枝，再检查，直到得到最优解。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都为整数的

49、约束，所以还需要继续分都为整数的约束，所以还需要继续分都为整数的约束，所以还需要继续分都为整数的约束，所以还需要继续分枝。枝。枝。枝。选择目标函数值较大的选择目标函数值较大的选择目标函数值较大的选择目标函数值较大的L1L1L1L1进行分枝：进行分枝：进行分枝：进行分枝：x1 3x1 3x1 3x1 3，x2 4x2 4x2 4x2 4将将将将L1L1L1L1问题划分为问题划分为问题划分为问题划分为L11L11L11L11和和和和L12L12L12L12两个线性规划问题。两个线性规划问题。两个线性规划问题。两个线性规划问题。本讲稿第三十三页，共八十页L11L11L11L11：L12L12L12L

50、12：再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解再用图解法或单纯形法分别求解L11L11L11L11和和和和L12L12L12L12的最优解为：的最优解为：的最优解为：的最优解为：L11L11L11L11（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本讲稿第三十四页，共八十页再用图解法或单