运筹学第3版ppt-熊伟Ch3整数规划

1、2022-5-93.1 整数规划数学模型整数规划数学模型 Mathematical Model of IP3.2 纯整数规划的求解纯整数规划的求解 Solving Pure Integer Programming 3.3 01规划的求解规划的求解 Solving Binary Integer Programming Chapter 3 整数规划整数规划Integer Programming运筹学运筹学Operations Research2022-5-93.1 整数规划数学模型整数规划数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Prog

2、ramming 制作与教学 武汉理工大学管理学院 熊伟 Page 3 2022-5-9 一个规划问题中要求部分或全部决策变量是整数，则这一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。规划。 很多实际规划问题都属于整数规划问题很多实际规划问题都属于整数规划问题 1. 变

3、量是人数、机器设备台数或产品件数等都要求是整数变量是人数、机器设备台数或产品件数等都要求是整数2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变对某一个项目要不要投资的决策问题，可选用一个逻辑变量量 x，当，当x=1表示投资，表示投资，x=0表示不投资；表示不投资；3. 人员的合理安排问题，当变量人员的合理安排问题，当变量xij=1表示安排第表示安排第i人去做人去做j工作，工作，xij=0表示不安排第表示不安排第i人去做人去做j工作。逻辑变量也是只允许取整数工作。逻辑变量也是只允许取整数值的一类变量。值的一类变量。3.1 整数规划的数学模型整数规划的数学模型 Mathematical M

4、odel of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 4 2022-5-9【例【例3-1 】某人有一背包可以装】某人有一背包可以装10公斤重、公斤重、0.025m3的物品。他准备的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所所示。问两种物品各装多少件，所装物品的总价值最大？示。问两种物品各装多少件，所装物品的总价值最大？表表3-1【解】设甲、乙两种物品各装【解】设甲、乙两种物品各装x1、x2件，则数学模型为：件，则数学模型为：且均取

5、整数, 0,255 . 22108 . 02 . 134max21212121xxxxxxxxZ(3-1)3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 物品物品重量重量（公斤（公斤/每件）每件）体积体积（m3/每件）每件）价值价值(元元/每件每件)甲甲乙乙1.20.80.0020.002543 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 5 2022-5-9如果不考虑如果不考虑x1、x2取整数的约束（称为（取整数的约束（称为（3-1）的松弛问题），）的松弛问题），线性规划的

6、可行域如图线性规划的可行域如图3-1中的阴影部分所示。中的阴影部分所示。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 图图3-1 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 6 2022-5-9 用图解法求得点用图解法求得点B为最优解：为最优解：X(3.57，7.14)，Z35.7。由于由于x1，x2必须取整数值，实际上整数规划问题的可行解集只必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四是图中可行域内的那些整数点。用凑整法

7、来解时需要比较四种组合，但（种组合，但（4，7）、（）、（4，8）（）（3，8）都不是可行解，（）都不是可行解，（3，7）虽属可行解，但代入目标函数得）虽属可行解，但代入目标函数得Z=33,并非最优。实际上并非最优。实际上问题的最优解是（问题的最优解是（5，5），），Z=35。即两种物品各装。即两种物品各装5件，总价件，总价值值35元。元。 由图由图31知，点（知，点（5，5）不是可行域的顶点，直接用图解）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。数规划问题的最

8、优解需要采用其它特殊方法。 还有些问题用线性规划数学模型无法描述，但可以通过设还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。置逻辑变量建立起整数规划的数学模型。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 7 2022-5-9【例【例3-2 】在例】在例3-1中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量为为12公斤，其体积是公斤，其体积是0.02m3。背包和旅

9、行箱只能选择其一，建。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是别是4和和3，载重量和体积的约束为，载重量和体积的约束为2025 . 1126 . 08 . 12121xxxx【解】此问题可以建立两个整数规划模型，但用一个模型描述【解】此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入更简单。引入01变量（或称逻辑变量）变量（或称逻辑变量）yi，令，令2 , 10,

10、 1iiiyi种方式装载时不采用第，种方式装载时采用第i=1,2分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 8 2022-5-9（1） 由于所装物品不变，式由于所装物品不变，式(3-1)约束左边不变，整数规划数学约束左边不变，整数规划数学模型为模型为2 , 110, 0120255 . 2212108 . 02 . 134max212121212121iyxyyyyxxyy

11、xxxxZii或且取整数（2） 由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型为为121221211221211212max431.20.810( )1.80.612( )22.525( )1.5220( )1,0,01ZxxxxMyaxxMybxxMycxxMydyyx xy且均取整数或3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 9 2022-5-9式中式中M为充分大的正数。从上式可知，当使用背包时为

12、充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式，式(b)和和(d)是多余的；当使用旅行箱时是多余的；当使用旅行箱时(y1=0，y2=1)，式，式(a)和和(c)是多余的。上式也可以令：是多余的。上式也可以令：yyyy1,21 同样可以讨论对于有同样可以讨论对于有m个条件互相排斥、有个条件互相排斥、有m（m、m）个）个条件起作用的情形。条件起作用的情形。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 10 2022-

13、5-9（1)右端常数是右端常数是k个值中的一个时，类似式个值中的一个时，类似式(3-2)的约束条件为的约束条件为1111kiikiiinjjijyybxa，（2)2)对于对于m组组条件中有条件中有k（m）组起作用时，）组起作用时，类似式类似式(3-3)的的约束条件写成约束条件写成11nkijjiiijia xbMyymk，这里这里yi=1表示第表示第i组约束不起作用（如组约束不起作用（如y1=1式式(3-3b)、(3-3d)不起不起作用），作用），yi=0表示第表示第i个约束起作用。当约束条件是个约束起作用。当约束条件是“”符号符号时右端常数项应为时右端常数项应为iibMy（3) 对于对于m个

14、个条件中有条件中有k（m）个起作用时，约束条件写成）个起作用时，约束条件写成kmyMybxakiiiinjjij11，3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 11 2022-5-9【例【例3-3】试引入】试引入01变量将下列各题分别表达为一般线性约变量将下列各题分别表达为一般线性约束条件束条件（1）x1+x26或或4x1+6x210或或2x1+4x220 （2）若）若x15，则，则x20，否则，否则x28（3）x取值取值0，

15、1，3，5，7【解】【解】 （1）3个约束只有个约束只有1个起作用个起作用1211221231236461024202011,2,3jxxy Mxxy Mxxy Myyyyj或 ，3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 3 , 2 , 1101)1 (2042)1 (1064)1 (6321321221121jyyyyMyxxMyxxMyxxj，或或或 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 12 2022-5-9（3）右端常数是）右端常数是5个值中的个值中的1个

16、个123412343571011,2,3,4jxyyyyyyyyyj 或 ，10)1 (8)1 (552211或yMyxyMxMyxyMx3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP （2）两组约束只有一组起作用）两组约束只有一组起作用 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 13 2022-5-9【例【例3-4】企业计划生产】企业计划生产4000件某种产品，该产品可自己加工、件某种产品，该产品可自己加工、外协加工任意一种形式生产已知每种生产的固定费用、生产外协加工任意

17、一种形式生产已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表制如表32所示，怎样安排产品的加工使总成本最小所示，怎样安排产品的加工使总成本最小表表32 【解】设【解】设xj为采用第为采用第j（j=1,2,3）种方式生产的产品数量，生）种方式生产的产品数量，生产费用为产费用为)0(0)0()(jjjjjjjxxxckxC3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 固定成本固定成本（元）（元）变动成本变动成本（元件）（元件）最大加工数最大加工数（件）（件

18、）本企业加工本企业加工50081500外协加工外协加工80052000外协加工外协加工6007不限不限 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 14 2022-5-9式中式中kj是固定成本，是固定成本，cj是单位产品成本设是单位产品成本设01变量变量yj，令，令101,2,300jjjjxyjjx采用第 种加工方式，时不采用在第 种加工方式， 时)7600()5800()8500(min332211xyxyxyZ数学模型为数学模型为 3 , 2 , 101, 02000,150040003 , 2 , 1021321j

19、yxxxxxxjMyxjjjj，或3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP （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.0jjMyx Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管

20、理学院 熊伟 Page 15 2022-5-9作业：教材习题作业：教材习题 3.13.7 1.线性整数规划模型的特征线性整数规划模型的特征2.什么是纯（混合）整数规划什么是纯（混合）整数规划3.01规划模型的应用规划模型的应用3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 下一节：纯整数规划的求解下一节：纯整数规划的求解2022-5-93.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 P

21、age 17 2022-5-9分枝定界法的步骤：分枝定界法的步骤：1. 求整数规划的松弛问题最优解；求整数规划的松弛问题最优解；2. 若松弛问题的最优解满足整数要求，得到整数规划的最优若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；解，否则转下一步；3.任意选一个非整数解的变量任意选一个非整数解的变量xi，在松弛问题中加上约束，在松弛问题中加上约束xixi及及xixi+1组成两个新的松弛问题，称为分枝。新的松弛组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求

22、最小值时，目标值是分枝问题的下界；上界；当原问题是求最小值时，目标值是分枝问题的下界；4. 检查所有分枝的解及目标函数值，若某分枝的解是整数并检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（且目标函数值大于（max）等于其它分枝的目标值，则将其它）等于其它分枝的目标值，则将其它分枝剪去不再计算分枝剪去不再计算,若还存在非整数解并且目标值大于（若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。整数解的目标值，需要继续分枝，再检查，直到得到最优解。3.2.1求解纯整数规划的分枝定界法求解纯整数规划的分枝定界法3.2 纯整数规划的求解纯

23、整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 18 2022-5-9【例【例3-5 】用分枝定界法求解例】用分枝定界法求解例5.1【解】先求对应的松弛问题（记为【解】先求对应的松弛问题（记为LP0）：）： 0,255 . 22108 . 02 . 1:034max21212121xxxxxxLPxxZ用图解法得到最优解用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。如下图所示。且均取整数,0,255.22108.02.13

24、4max21212121xxxxxxxxZ3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 19 2022-5-98.3310108 . 02 . 121xx255 . 2221xx松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 2022-5-91010 x1x2oABC0,3255

25、. 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.50,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZ得到两个线性规划及增加约束4311xx2022-5-91010 x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.330,64255 . 22108 . 02 . 1:334max2121212121xxxxxxxxLPxxZ，不可行，得到线性规划，显然及进行分枝，增加约束选择目标值最

26、大的分枝7762222xxxLP6不可行72xLP1:X=(3,7.6),Z1=34.82022-5-91010 x1x2oACLP134可行域是一条线段即，, 40,464255 . 22108 . 02 . 1:434max121121212121xxxxxxxxxxLPxxZ：及，到线性规划及进行分枝，增加约束，选择由于545431113LPLPxxLPZZ60,65255 . 22108 . 02 . 1:534max2121212121xxxxxxxxLPxxZ，LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP

27、52022-5-9 尽管尽管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无可行解无可行解x27 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管

28、理学院 熊伟 Page 24 2022-5-9设纯整数规划设纯整数规划njxbxaxcZjinjjijnjjj, 10max11且为整数， 松弛问题松弛问题njxbxaxcZjinjjijnjjj, 10max11，的最优解的最优解TmTbbbbBbbBX),()0 ,(2111设设xi不为整数，不为整数，为非基变量kkkikiixxabx3.2.2 求解求解IP的割平面法的割平面法3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 P

29、age 25 2022-5-9将将 分离成一个整数与一个非负真分数之和：分离成一个整数与一个非负真分数之和：ikiab及 10 , 10 ,ikiikikikiiifffaafbb则有则有kkikkkijiiixfxafbxkkikikkijiixffxabx等式两边都为整数并且有等式两边都为整数并且有1ikkikifxff3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 26 2022-5-9加入松弛变量加入松弛变量si得

30、得ikkikifxfs此式称为以此式称为以xi行为源行（来源行）的割平面，或分数切割式，行为源行（来源行）的割平面，或分数切割式，或或R.E.Gomory(高莫雷高莫雷)约束方程。约束方程。 将将Gomory约束加入到松弛问题的最优表中，用对偶单纯约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。部为整数解。0kkikixff则则3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Program

31、ming 制作与教学 武汉理工大学管理学院 熊伟 Page 27 2022-5-9324313322354613651xxxxxx例如，例如，3246536511)1(xxxx1行：行：移项：移项：46536532411xxxx令令046536532xx加入松弛变量加入松弛变量s1得得324653651xxs同理，对于同理，对于x2行有：行有：324313312xxs3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 28 2

32、022-5-9【例【例3-6】 用割平面法求解下列用割平面法求解下列IP问题问题且为整数0,102304634max21212121xxxxxxxxZ【解】【解】 放宽变量约束，对应的松弛问题是放宽变量约束，对应的松弛问题是 0,102304634max21212121xxxxxxxxZ3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 29 2022-5-9加入松弛变量加入松弛变量x3及及x4后，用单纯形法求解，得到最优表后

33、，用单纯形法求解，得到最优表3-3。 最优解最优解X(0)(5/2，15/4),不是不是IP的最优解。选择表的最优解。选择表3-3的第一的第一行行(也可以选第二行也可以选第二行)为源行为源行252141431xxx3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Cj4300bCBXBx1x2x3x443x1x210011/41/81/23/45/215/4j005/81/4表表3-3 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 30 2022-5-9分离系数后改写成

34、分离系数后改写成212)211(41431xxx021412124341xxxx加入松弛变量加入松弛变量x5得到高莫雷约束方程得到高莫雷约束方程22543xxx将式将式(3-8)作为约束条件添加到表作为约束条件添加到表33中，用对偶单纯形法中，用对偶单纯形法计算，如表计算，如表34所示所示 3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 31 2022-5-9Cj43000bCBXBx1x2x3x4x5430 x1x2x5

35、1000101/41/811/23/42 0015/215/42j005/81/40430 x1x2x41000101/21/21/2001 1/43/81/2331j001/201/8最优解最优解X(1)(3，3)，最优值，最优值Z21。所有变量为整数，。所有变量为整数，X(1)就是就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算的最优解。如果不是整数解，需要继续切割，重复上述计算过程。过程。3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 表表34 如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛如果在对偶单纯

36、形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。变量所在列化为单位向量后就可以去掉该行该列，再切割。 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 32 2022-5-9作业：教材习题作业：教材习题 3.8，3.9 1.理解分枝与定界的含义理解分枝与定界的含义2.选择合适的选择合适的“ 枝枝”生生“ 枝枝”3.掌握何时停止生掌握何时停止生“ 枝枝”4.领会割平面法的基本原理领会割平面法的基本原理5.分离源行，求出分离源行，求出Gomory约束约束6.在最优表中增加在最优表中增

37、加Gomory约束，用约束，用 对偶单纯形法迭代对偶单纯形法迭代3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 下一节：下一节： 01规划的求解规划的求解2022-5-93.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 34 2022-5-93.3.1 求解求解01整数规划的隐枚举法整数规划的隐枚举法隐枚举法的步骤：隐枚举法的步骤： 1.找出任意一可行解，目标函数值为找出任意一可行解，目标函数值为Z0 2. 原问题求

38、最大值时，则增加一个约束原问题求最大值时，则增加一个约束1 1220(*)nnc xc xc xZ当求最小值时，上式改为小于等于约束当求最小值时，上式改为小于等于约束 3. 列出所有可能解，对每个可能解先检验式（列出所有可能解，对每个可能解先检验式（*），若满足再），若满足再检验其它约束，若不满足式（检验其它约束，若不满足式（*），则认为不可行，若所有约束），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值都满足，则认为此解是可行解，求出目标值 4. 目标函数值最大（最小）的解就是最优解目标函数值最大（最小）的解就是最优解 3.3 01规划的求解规划的求解Solving BIP

39、Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 35 2022-5-9【例例3-7】用隐枚举法求解下列】用隐枚举法求解下列BIP问题4 , 3 , 2 , 11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或【解】（【解】（1）不难看出，当所有变量等于）不难看出，当所有变量等于0或或1的任意组合时，的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到从约束条件中去掉。还能通过观察得到X0(1，0，0，1)是一是一个可行解，目标值个可行解，目标值Z011是是BIP问题的下界，构造一个约问题的下界，构造一个约束：束： ，原，原BIP问题变为问题变为115326432