运筹学课件Ch3整数规划.ppt

3.1整数规划数学模型整数规划数学模型MathematicalModelofIP3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming3.301规划的求解规划的求解SolvingBinaryIntegerProgrammingChapter3整数规划整数规划IntegerProgramming运筹学运筹学OperationsResearch12/18/20223.1整数规划数学模型整数规划数学模型MathematicalModelofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 3 一个规划问题中要求部分或全部决策变量是整数，则这一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。规划。很多实际规划问题都属于整数规划问题很多实际规划问题都属于整数规划问题1.变量是人数、机器设备台数或产品件数等都要求是整数变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变对某一个项目要不要投资的决策问题，可选用一个逻辑变量量x，当，当x=1表示投资，表示投资，x=0表示不投资；表示不投资；3.人员的合理安排问题，当变量人员的合理安排问题，当变量xij=1表示安排第表示安排第i人去做人去做j工作，工作，xij=0表示不安排第表示不安排第i人去做人去做j工作。逻辑变量也是只允许取整数值工作。逻辑变量也是只允许取整数值的一类变量。的一类变量。3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 4【例例3.1】某某人人有有一一背背包包可可以以装装10公公斤斤重重、0.025m3的的物物品品。他他准准备备用用来来装装甲甲、乙乙两两种种物物品品，每每件件物物品品的的重重量量、体体积积和和价价值值如如表表3-1所所示。问两种物品各装多少件，所装物品的总价值最大？示。问两种物品各装多少件，所装物品的总价值最大？表表3-1【解】设甲、乙两种物品各装【解】设甲、乙两种物品各装x1、x2件，则数学模型为：件，则数学模型为：(3.1)3.1整数规划的数学模型整数规划的数学模型 MathematicalModelofIP物品物品重量重量（公斤（公斤/每件）每件）体积体积（m3/每件）每件）价值价值(元元/每件每件)甲甲乙乙1.20.80.0020.00254312/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 5 如如果果不不考考虑虑x1、x2取取整整数数的的约约束束（称称为为（3.1）的的松松弛弛问问题题），线性规划的可行域如图线性规划的可行域如图3-1中的阴影部分所示。中的阴影部分所示。3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP图图3-112/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 6 用用图图解解法法求求得得点点B为为最最优优解解：X(3.57，7.14)，Z35.7。由由于于x1，x2必必须须取取整整数数值值，实实际际上上整整数数规规划划问问题题的的可可行行解解集集只只是是图图中中可可行行域域内内的的那那些些整整数数点点。用用凑凑整整法法来来解解时时需需要要比比较较四四种种组组合合，但但（4，7）、（4，8）（3，8）都都不不是是可可行行解解，（3，7）虽虽属属可可行行解解，但但代代入入目目标标函函数数得得Z=33,并并非非最最优优。实实际际上上问问题题的的最最优优解解是是（5，5），Z=35。即即两两种种物物品品各各装装5件件，总总价值价值35元。元。由由图图31知知，点点（5，5）不不是是可可行行域域的的顶顶点点，直直接接用用图图解解法法或或单单纯纯形形法法都都无无法法求求出出整整数数规规划划问问题题的的最最优优解解，因因此此求求解解整整数规划问题的最优解需要采用其它特殊方法。数规划问题的最优解需要采用其它特殊方法。还还有有些些问问题题用用线线性性规规划划数数学学模模型型无无法法描描述述，但但可可以以通通过过设设置逻辑变量建立起整数规划的数学模型。置逻辑变量建立起整数规划的数学模型。3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 7【例例3.2】在在例例3.1中中，假假设设此此人人还还有有一一只只旅旅行行箱箱，最最大大载载重重量量为为12公公斤斤，其其体体积积是是0.02m3。背背包包和和旅旅行行箱箱只只能能选选择择其其一一，建建立下列几种情形的数学模型，使所装物品价值最大。立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是是4和和3，载重量和体积的约束为，载重量和体积的约束为【解解】此此问问题题可可以以建建立立两两个个整整数数规规划划模模型型，但但用用一一个个模模型型描描述述更简单。引入更简单。引入01变量（或称逻辑变量）变量（或称逻辑变量）yi，令，令i=1,2分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 8（1）由由于于所所装装物物品品不不变变，式式(3.1)约约束束左左边边不不变变，整整数数规规划划数数学学模型为模型为（2）由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型为为3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 9 式式中中M为为充充分分大大的的正正数数。从从上上式式可可知知，当当使使用用背背包包时时(y1=1，y2=0)，式式(b)和和(d)是是多多余余的的；当当使使用用旅旅行行箱箱时时(y1=0，y2=1)，式式(a)和和(c)是多余的。上式也可以令：是多余的。上式也可以令：同同样样可可以以讨讨论论对对于于有有m个个条条件件互互相相排排斥斥、有有m（m、m）个个条件起作用的情形。条件起作用的情形。3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 10（1)右端常数是右端常数是k个值中的一个时，类似式个值中的一个时，类似式(3.2)的约束条件为的约束条件为（2)2)对于对于m组组条件中有条件中有k（m）组起作用时，）组起作用时，类似式类似式(3.3)的的约束条件写成约束条件写成这里这里yi=1表示第表示第i组约束不起作用（如组约束不起作用（如y1=1式式(3.3b)、(3.3d)不不起作用），起作用），yi=0表示第表示第i个约束起作用。当约束条件是个约束起作用。当约束条件是“”符符号时右端常数项应为号时右端常数项应为（3)对于对于m个个条件中有条件中有k（m）个起作用时，约束条件写成）个起作用时，约束条件写成3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 11【例【例3.3】试引入】试引入01变量将下列各题分别表达为一般线性约变量将下列各题分别表达为一般线性约束条件束条件（1）x1+x26或或4x1+6x210或或2x1+4x220（2）若）若x15，则，则x20，否则，否则x28（3）x2取值取值0，1，3，5，7【解】【解】（1）3个约束只有个约束只有1个起作用个起作用3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP或或12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 12（3）右端常数是）右端常数是5个值中的个值中的1个个3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP（2）两组约束只有一组起作用）两组约束只有一组起作用12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 13【例【例3.4】企业计划生产】企业计划生产4000件某种产品，该产品可自己加工、件某种产品，该产品可自己加工、外协加工任意一种形式生产已知每种生产的固定费用、生产外协加工任意一种形式生产已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表制如表32所示，怎样安排产品的加工使总成本最小所示，怎样安排产品的加工使总成本最小表表32【解】设【解】设xj为采用第为采用第j（j=1,2,3）种方式生产的产品数量，生）种方式生产的产品数量，生产费用为产费用为3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP固定成本固定成本（元）（元）变动成本变动成本（元件）（元件）最大加工数最大加工数（件）（件）本企业加工本企业加工50081500外协加工外协加工80052000外协加工外协加工6007不限不限12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 14 式中式中kj是固定成本，是固定成本，cj是单位产品成本设是单位产品成本设01变量变量yj，令，令数学模型为数学模型为 3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP（3.4）式（式（3.4）中）中是处理是处理xj与与yj一对变量之间逻辑关系的特殊约束，一对变量之间逻辑关系的特殊约束，当当xj0时时yj=1,当当xj0时，为使时，为使Z最小化，有最小化，有yj=0。例例3.4是混合整数规划问题用是混合整数规划问题用WinQSB软件求解得到：软件求解得到：X(0，2000，2000)T，Y(0，1，1)T，Z=25400.12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 15 作业：教材作业：教材P751,2，3，4，5，61.线性整数规划模型的特征线性整数规划模型的特征2.什么是纯（混合）整数规划什么是纯（混合）整数规划3.01规划模型的应用规划模型的应用3.1整数规划的数学模型整数规划的数学模型 Mathematical Model ofIP下一节：纯整数规划的求解下一节：纯整数规划的求解12/18/20223.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 17 分枝定界法的步骤：分枝定界法的步骤：1.求整数规划的松弛问题最优解；求整数规划的松弛问题最优解；2.若若松松弛弛问问题题的的最最优优解解满满足足整整数数要要求求，得得到到整整数数规规划划的的最最优优解，否则转下一步；解，否则转下一步；3.任任意意选选一一个个非非整整数数解解的的变变量量xi，在在松松弛弛问问题题中中加加上上约约束束xixi及及xixi+1组组成成两两个个新新的的松松弛弛问问题题，称称为为分分枝枝。新新的的松松弛弛问问题题具具有有特特征征：当当原原问问题题是是求求最最大大值值时时，目目标标值值是是分分枝枝问问题题的的上上界；当原问题是求最小值时，目标值是分枝问题的下界；界；当原问题是求最小值时，目标值是分枝问题的下界；4.检检查查所所有有分分枝枝的的解解及及目目标标函函数数值值，若若某某分分枝枝的的解解是是整整数数并并且且目目标标函函数数值值大大于于（max）等等于于其其它它分分枝枝的的目目标标值值，则则将将其其它它分分枝枝剪剪去去不不再再计计算算,若若还还存存在在非非整整数数解解并并且且目目标标值值大大于于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。整数解的目标值，需要继续分枝，再检查，直到得到最优解。求解纯整数规划的分枝定界法求解纯整数规划的分枝定界法3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 18【例【例3.5】用分枝定界法求解例】用分枝定界法求解例5.1【解】先求对应的松弛问题（记为【解】先求对应的松弛问题（记为LP0）：）：用图解法得到最优解用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。如下图所示。3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 19 8.3310松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/20221010 x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.512/18/20221010 x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336LP1:X=(3,7.6),Z1=34.812/18/20221010 x1x2oACLP1346LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP512/18/2022尽管尽管LP1的解中的解中x1不为整数，但不为整数，但Z5Z因此因此LP5的最优解的最优解就是原整数规划的最优解。就是原整数规划的最优解。上述分枝过程可用下图表示上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解无可行解x2712/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 24 设纯整数规划设纯整数规划松弛问题松弛问题的最优解的最优解设设xi不为整数，不为整数，3.2.2求解求解IP的割平面法的割平面法3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 25 将将分离成一个整数与一个非负真分数之和：分离成一个整数与一个非负真分数之和：则有则有等式两边都为整数并且有等式两边都为整数并且有3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 26 加入松弛变量加入松弛变量si得得此式称为以此式称为以xi行为源行（来源行）的割平面，或分数切割式，行为源行（来源行）的割平面，或分数切割式，或或R.E.Gomory(高莫雷高莫雷)约束方程。约束方程。将将Gomory约束加入到松弛问题的最优表中，用对偶单纯约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。部为整数解。则则3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 27 例如，例如，x1行：行：移项：移项：令令加入松弛变量加入松弛变量s1得得同理，对于同理，对于x2行有：行有：3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 28【例【例3.6】用割平面法求解下列用割平面法求解下列IP问题问题【解】【解】放宽变量约束，对应的松弛问题是放宽变量约束，对应的松弛问题是3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 29 加入松弛变量加入松弛变量x3及及x4后，用单纯形法求解，得到最优表后，用单纯形法求解，得到最优表3-3。最优解最优解X(0)(5/2，15/4),不是不是IP的最优解。选择表的最优解。选择表3-3的第的第一行一行(也可以选第二行也可以选第二行)为源行为源行3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgrammingCj4300bCBXBx1x2x3x443x1x210011/41/81/23/45/215/4j005/81/4表表3-312/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 30 分离系数后改写成分离系数后改写成加入松弛变量加入松弛变量x5得到高莫雷约束方程得到高莫雷约束方程将式将式(3.8)作为约束条件添加到表作为约束条件添加到表33中，用对偶单纯形法中，用对偶单纯形法计算，如表计算，如表34所示所示3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 31 Cj43000bCBXBx1x2x3x4x5430 x1x2x51000101/41/811/23/420015/215/42j005/81/40430 x1x2x41000101/21/21/20011/43/81/2331j001/201/8最优解最优解X(1)(3，3)，最优值，最优值Z21。所有变量为整数，。所有变量为整数，X(1)就就是是IP的最优解。如果不是整数解，需要继续切割，重复上述计的最优解。如果不是整数解，需要继续切割，重复上述计算过程。算过程。3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming表表34如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。量所在列化为单位向量后就可以去掉该行该列，再切割。12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 32 作业：教材作业：教材P76T7，81.理解分枝与定界的含义理解分枝与定界的含义2.选择合适的选择合适的“枝枝”生生“枝枝”3.掌握何时停止生掌握何时停止生“枝枝”4.领会割平面法的基本原理领会割平面法的基本原理5.分离源行，求出分离源行，求出Gomory约束约束6.在最优表中增加在最优表中增加Gomory约束，用约束，用对偶单纯形法迭代对偶单纯形法迭代3.2纯整数规划的求解纯整数规划的求解SolvingPureIntegerProgramming下一节：下一节：01规划的求解规划的求解12/18/20223.301规划的求解规划的求解SolvingBIP 12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 34 3.3.1求解求解01整数规划的隐枚举法整数规划的隐枚举法隐枚举法的步骤：隐枚举法的步骤：1.找出任意一可行解，目标函数值为找出任意一可行解，目标函数值为Z02.原问题求最大值时，则增加一个约束原问题求最大值时，则增加一个约束当求最小值时，上式改为小于等于约束当求最小值时，上式改为小于等于约束3.列出所有可能解，对每个可能解先检验式（列出所有可能解，对每个可能解先检验式（*），若满足再），若满足再检验其它约束，若不满足式（检验其它约束，若不满足式（*），则认为不可行，若所有约束），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值都满足，则认为此解是可行解，求出目标值4.目标函数值最大（最小）的解就是最优解目标函数值最大（最小）的解就是最优解3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 35【例例3.7】用隐枚举法求解下列】用隐枚举法求解下列BIP问题【解解】（1）不不难难看看出出，当当所所有有变变量量等等于于0或或1的的任任意意组组合合时时，第第一一个个约约束束满满足足，说说明明第第一一个个约约束束没没有有约约束束力力，是是多多余余的的，从从约约束束条条件件中中去去掉掉。还还能能通通过过观观察察得得到到X0(1，0，0，1)是是一一个个可可 行行 解解，目目 标标 值值 Z0 11是是 BIP问问 题题 的的 下下 界界，构构 造造 一一 个个 约约 束束：，原，原BIP问题变为问题变为3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 36(2)列列出出变变量量取取值值0和和1的的组组合合，共共2416个个，分分别别代代入入约约束束条条件件判判断断是是否否可可行行。首首先先判判断断式式（3.9a）是是否否满满足足，如如果果满满足足，接接下下来判断其它约束，否则认为不可行，计算过程见表来判断其它约束，否则认为不可行，计算过程见表37所示。所示。3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 37 jXj3.9a3.9b3.9c3.9dZjjXj3.9a3.9b3.9c3.9dZj1(0,0,0,0)9(1,0,0,0)2(0,0,0,1)10(1,0,0,1)113(0,0,1,0)11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)145(0,1,0,0)13(1,1,0,0)6(0,1,0,1)14(1,1,0,1)137(0,1,1,0)15(1,1,1,0)8(0,1,1,1)16(1,1,1,1)表表35(3)由表由表3-5知，知，BIP问题的最优解：问题的最优解：X（1，0，1，1），最），最优值优值Z143.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 38 选择不同的初始可行解，计算量会不一样。一般地，当目选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于标函数求最大值时，首先考虑目标函数系数最大的变量等于1，如例，如例3.8。当目标函数求最小值时，先考虑目标函数系数最。当目标函数求最小值时，先考虑目标函数系数最大的变量等于大的变量等于0。在表在表37的计算过程中，当目标值等于的计算过程中，当目标值等于14时，将其下界时，将其下界11改改为为14，可以减少计算量。，可以减少计算量。3.3.2分枝隐枚举法求解分枝隐枚举法求解BIP问题问题将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计算步骤如下：算步骤如下：（1）将）将BIP问题的目标函数的系数化为非负，如问题的目标函数的系数化为非负，如3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 39 当变量作了代换后，约束条件中的变量也相应作代换。当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝：目标函数是）求主枝：目标函数是max形式时令所有变量等于形式时令所有变量等于1，得到，得到目标值的上界；目标函数是目标值的上界；目标函数是min形式时令所有变量等于形式时令所有变量等于0，得到，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；否则转下一步；（4）分枝与定界：从第一个变量开始依次取）分枝与定界：从第一个变量开始依次取“1”或或“0”，求极大值时其后面的变量等于求极大值时其后面的变量等于“1”，求极小值时其后面的变，求极小值时其后面的变量等于量等于“0”，用分枝定界法搜索可行解和最优解。，用分枝定界法搜索可行解和最优解。分枝隐枚举法是从非可行解中进行分枝搜索可行解，第分枝隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（）步到第（3）步用了隐枚举法的思路，第（）步用了隐枚举法的思路，第（4）步用了分）步用了分枝定界法的思路。枝定界法的思路。3.301规划的求解规划的求解SolvingBIP(2)变量重新排序：变量依据目标函数系数值按升排序；变量重新排序：变量依据目标函数系数值按升排序；12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 40 停止分枝和需要继续分枝的原则：停止分枝和需要继续分枝的原则：（1）当某一子问题是可行解时则停止分枝并保留；）当某一子问题是可行解时则停止分枝并保留；（2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；（3）后续分枝变量无论取）后续分枝变量无论取“1”或或“0”都不能得到可行解时停止分枝并剪都不能得到可行解时停止分枝并剪枝；枝；（4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。继续分枝。【例【例3.8】用分枝隐枚举法求解下列】用分枝隐枚举法求解下列BIP问题问题3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 41 解解（1）目标函数系数全部非负，直接对变量重新排序）目标函数系数全部非负，直接对变量重新排序（2）求主枝：令）求主枝：令X(1，1，1，1)得到主枝得到主枝1，检查约束条件知，检查约束条件知(3.10c)不不满足，则进行分枝。满足，则进行分枝。（3）令）令x2=0同时令同时令x3=0及及x3=1得到分枝得到分枝2和分枝和分枝3，X2和和X3是可行解，分枝是可行解，分枝停止并保留，如表停止并保留，如表3-8及图及图3-8所示。所示。3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 42 表表3.8令令x2=1同时令同时令x3=0得到分枝得到分枝4，X4是可行解，分枝停止并保留。是可行解，分枝停止并保留。令令x2=1、x3=1，x4取取“0”和和“1”得到分枝得到分枝5和和6，分枝，分枝5不可行不可行并且并且Z511小于小于Z3和和Z4，分枝停止并剪枝。注意到分枝，分枝停止并剪枝。注意到分枝6，x41时只有时只有x10（x11就是主枝），就是主枝），X6不可行并且不可行并且Z610小于小于Z3和和Z4，分枝停止并剪枝，分枝过程结束。整个计算过程可用图，分枝停止并剪枝，分枝过程结束。整个计算过程可用图32和表和表3.8表示。表示。分分枝枝(x2,x3,x4,x1)3.10a3.10b3.10cZj可可行行性性1(1,1,1,1)16不不可可行行2(0,0,1,1)11可可行行3(0,1,1,1)14可可行行4(1,0,1,1)13可可行行5(1,1,0,1)11不不可可行行6(1,1,1,0)10不不可可行行3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 43 搜索到搜索到3个可行解，个可行解，3个目标值中个目标值中Z3最大，因此最大，因此X3是最优解，转是最优解，转换到原问题的最优解为换到原问题的最优解为X（1，0，1，1），最优值），最优值Z14，计，计算结束。算结束。图图323.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 44【例【例3.9】用分枝隐枚举法求解下列】用分枝隐枚举法求解下列BIP问题问题解解（1）令）令x2=1x2及及x5=1x5，代入模型后整理得，代入模型后整理得3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 45（2）目标函数系数按升序将对应的变量重新排列得到模型）目标函数系数按升序将对应的变量重新排列得到模型（3）求主枝。由于目标函数求最小值，令所有变量等于零，得）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解到主枝的解X1（0，0，0，0，0），），Z17，检验约束条件，检验约束条件知知X1不可行，进行分枝。不可行，进行分枝。（4）取）取x1=1和和x1=0，分别其它变量等于，分别其它变量等于“1”和和“0”分枝，分枝，判断可行性，计算过程参见表判断可行性，计算过程参见表36及图及图33。3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 46 分枝分枝j上一上一分枝分枝Xj=(x1,x4,x2,x5,x3)3.11a3.11bZj可行性可行性12345主枝主枝1111(0,0,0,0,0)(0,1,0,0,0)(0,0,1,0,0)(0,0,0,1,0)(0,0,0,0,1)75431不可行不可行不可行不可行不可行不可行不可行不可行可行可行67891016666(1,0,0,0,0)(1,1,0,0,0)(1,0,1,0,0)(1,0,0,1,0)(1,0,0,0,1)64320不可行不可行不可行不可行不可行不可行不可行不可行可行可行表表363.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 47 由表由表36知，分枝知，分枝5和分枝和分枝10两个问题可行，分枝两个问题可行，分枝5优于分枝优于分枝10，其它不可行子问题尽管目标值优于分枝其它不可行子问题尽管目标值优于分枝5，由约束，由约束(3.11b)知，继知，继续分枝不可能得到其它可行解，因此停止分枝，计算结束。分枝续分枝不可能得到其它可行解，因此停止分枝，计算结束。分枝5的解的解X5(x1,x4,x2,x5,x3)（0，0，0，0，1），原），原BIP的的最优解为最优解为X(x1,x2,x3,x4,x5)(0，1，1，0，1),最优值最优值Z1。图图333.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 48 在分枝隐枚举法的计算过程中，由于变量已经按目标在分枝隐枚举法的计算过程中，由于变量已经按目标函数系数从小到大重新排序，因此在选择子问题分枝的函数系数从小到大重新排序，因此在选择子问题分枝的原则是按排序后的变量顺序分枝，但变量较多时搜索可原则是按排序后的变量顺序分枝，但变量较多时搜索可行解的过程可能非常漫长。针对转换后的目标函数特征，行解的过程可能非常漫长。针对转换后的目标函数特征，极大值问题的解中极大值问题的解中“1”越多越优，极小值问题的解中越多越优，极小值问题的解中“0”越多越优，因此在选择变量分枝时尽可能采用避越多越优，因此在选择变量分枝时尽可能采用避“0”或或“1”的方法，请观察表的方法，请观察表38及及36.3.301规划的求解规划的求解SolvingBIP12/18/2022Ch3整数规划整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 49 作业：作业：P76T9，101.用隐枚举法求用隐枚举法求0-1规划的最优解规划的最优解2.用分枝隐枚举法求解用分枝隐枚举法求解0-1规划的最优解规划的最优解3.301规划的求解规划的求解SolvingBIPTheEndofChapter33.9(1)3.9(2)12/18/2022