运筹学第三章课件

云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学

线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。

对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资。3.1整数规划的数学模型

纯整数规划(IP)：xj全部取整数混合整数规划(MIP)：xj部分取整数0-1整数规划(BIP)：整数变量只能取0或1分类2线性规划的决策变量取值可以是任意非负实数，但许多实际问【例3-1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，才能使所装物品的总价值最大？表3-1【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(3-1)物品重量（公斤/件）体积（m3/件）价值(元/件)甲乙1.20.80.0020.0025433.1整数规划的数学模型

3【例3-1】某人有一背包可以装10公斤重、0.025m3的

【补充例】投资决策问题。某公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表3.1整数规划的数学模型

该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：（1）在项目1、2和3中必须且只有一项被选中；（2）项目3和项目4最多只能选中一项；（3）项目5被选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，使投资收益最大？项目投资额（万元）投资收益（万元）1210160230021031506041308052601804【补充例】投资决策问题。某公司有5个项目被列入投资计划【解】设xj为选择第j（j=1,2,3,4,5)个项目的决策3.1整数规划的数学模型

5【解】设xj为选择第j（j=1,2,3,4,5)个项目的【例3-2】在例3-1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，每件物品的重量、体积和价值如下表所示3.1整数规划的数学模型

物品重量（公斤/件）体积（m3/件）价值(元/件)丙丁1.80.60.00150.002436【例3-2】在例3-1中，假设此人还有一只旅行箱，最大载重【解】（1）引入0－1变量yj，令j=1,2分别是采用背包及旅行箱装载。3.1整数规划的数学模型

(3-2)此问题也可以建立两个整数规划模型。7【解】（1）引入0－1变量yj，令j=1,2分别是采用（2）由于不同载体所装物品不一样，数学模型为3.1整数规划的数学模型

其中M为充分大的正数。当使用背包时(y1=1,y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0,y2=1)，式(a)和(c)是多余的。背包约束旅行箱约束8（2）由于不同载体所装物品不一样，数学模型为3.1整数规（1）右端常数是k个值中的一个时，类似式(3-2)的约束条件为3.1整数规划的数学模型

同样可以讨论对于有m个条件互相排斥、有m（≤m、≥m）个条件起作用的情形。9（1）右端常数是k个值中的一个时，类似式(3-2)的约束条件（2）对于m个（组）条件中有k（≤m）个（组）起作用时，类似式(3-3)的约束条件写成这里yi=1表示第i组约束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i个约束起作用。当约束条件是“≥”符号时右端常数项应为3.1整数规划的数学模型

10（2）对于m个（组）条件中有k（≤m）个（组）起作用时【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束条件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，则x2≥0，否则x2≤8（3）x2取值0，1，3，5，7【解】

（1）3个约束只有1个起作用或3.1整数规划的数学模型

如果要求至少一个条件满足，模型如何改变？11【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束（3）右端常数是5个值中的1个（2）两组约束只有一组起作用3.1整数规划的数学模型

(1)(2)(3)(4)12（3）右端常数是5个值中的1个（2）两组约束只有一组起作用3【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产。已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表3－2所示，怎样安排产品的加工使总成本最小。表3－2

固定成本（元）变动成本（元／件）最大加工数（件）本企业加工50081500外协加工Ⅰ80052000外协加工Ⅱ6007不限3.1整数规划的数学模型

13【例3-4】企业计划生产4000件某种产品，该产品可自己加工【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为3.1整数规划的数学模型

其中kj是固定成本，cj是可变成本。设0－1变量yj14【解】设xj为采用第j（j=1,2,3）种方式生产的产品数（3-4）用WinQSB软件求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=254003.1整数规划的数学模型

配合目标，使得只有选用第j种加工方式才产生相应成本，不选用第j种加工方式就没有成本。15（3-4）用WinQSB软件求解得到：3.1整数规划的数整数规划的一般形式：称线性规划模型（Ⅰ）

（Ⅱ）(LP)为（Ⅰ）的松弛问题。

每一个整数规划都对应一个松弛问题，整数规划比它的松弛问题约束得更紧。部分或全部取整3.1整数规划的数学模型

16整数规划的一般形式：称线性规划模型（Ⅰ）（Ⅱ）(LP)为3.1整数规划的数学模型

习题3.4【解】令运动员甲、乙、丙、丁、戊编号为1、2、3、4、5，项目高低杠、平衡木、鞍马、自由体操编号为1、2、3、4。设

项目运动员1234高低杠平衡木鞍马自由体操1甲x11x12x13x142乙x21x22x23x243丙x31x32x33x344丁x41x42x43x445戊x51x52x53x54173.1整数规划的数学模型习题3.4max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24+8.8x31

+8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52+8.2x53+7.7x54x11+x12+x13+x14≦3x21+x22+x23+x24≦3x31+x32+x33+x34≦3x41+x42+x43+x44≦3x51+x52+x53+x54≦3x11+x21+x31+x41+x51≧1x12+x22+x32+x42+x52≧1x13+x23+x33+x43+x53≧1x14+x24+x34+x44+x54≧1x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43+x44+x51+x52+x53+x54=10xij=0或1(i=1,2,3,4,5;j=1,2,3,4)3.1整数规划的数学模型

18max=8.6x11+9.7x12+8.9x13+9.4x11.整数规划模型的特征2.什么是纯（混合）整数规划3.0－1规划模型的应用下一节：纯整数规划的求解3.1整数规划的数学模型

本节学习要点191.整数规划模型的特征下一节：纯整数规划的求解3.1

整数规划解的特点整数规划（Ⅰ）的可行解集是其松弛问题（Ⅱ）的可行解集的子集。线性规划问题的可行解集是一个凸集（稠密的），但整数规划的可行解集不是凸集（离散型）。如果松弛问题（Ⅱ）的最优解是整数解，则一定是整数规划（Ⅰ）的最优解。整数规划（Ⅰ）的最优值不会优于松弛问题（Ⅱ）的最优值。3.2整数规划的求解20整数规划解的特点3.2整数规划的求解203.2整数规划的求解图3-1点B为最优解X＝(3.57，7.14)Z＝35.7用图解法求解例3-1的松弛问题整数规划问题的可行解集是图中可行域内的整数点。8.3310松弛问题的最优解X=(3.57,7.14),z=35.7x1x2oAC10B图3-1213.2整数规划的求解图3-1点B为最优解用图解法求解松弛问题的最优解X＝(3.57，7.14)，Z＝35.7“四舍五入”得X=(4,7)不是可行解；用“取整”法来解时，X=(3,7)虽属可行解，但代入目标函数得Z=33,并非最优。该整数规划问题的最优解是X=(5,5)，最优值是Z=35即甲、乙两种物品各装5件，总价值35元。

由图3－1知，点（5，5）不是LP可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。3.2整数规划的求解8.3310松弛问题的最优解X=(3.57,7.14),z=35.7x1x2oAC10B图3-122松弛问题的最优解X＝(3.57，7.14)，Z＝35【例3-5】用分支定界法求解例3-1【解】先求对应的松弛问题用图解法得到最优解X＝（3.57,7.14）,Z0=35.73.2.1分支定界法23【例3-5】用分支定界法求解例3-1【解】先求对应的松弛问8.3310松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2.1分支定界法248.3310松弛问题LP0的最优解X=(3.57,7.11010x1x20ABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5251010x1x20ABCLP1LP234LP1:X=(3,1010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP3:X=(4.33,6),Z3=35.33LP2LP3261010x10ACLP134LP1:X=(3,7.6),x1x11010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP2LP3LP5LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=35此为原IP最优解527x1x11010x10ACLP134LP1:X=(3,7.尽管LP1的解中x2不为整数，但Z5≧Z1，因此LP5的最优解就是原整数规划的最优解。若Z5≦Z1

，则要对LP1进行分支。3.2.1分支定界法28尽管LP1的解中x2不为整数，但Z5≧Z1，因此L上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5

无可行解x2≥7最优解3.2.1分支定界法29上述分枝过程可用下图表示LP0:X=(3.57,7.14分支定界法的步骤：1.求整数规划的松弛问题最优解；2.

若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；3.2.1分支定界法3.任意选一个非整数解的变量xi，在松弛问题中加上约束xi≤[xi]及xi≥[xi]+1组成两个新的松弛问题，称为分支。新的松弛问题具有特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题是求最小值时，目标值是分支问题的下界；30分支定界法的步骤：1.求整数规划的松弛问题最优解；3.4.

检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于（max）等于其它分支的目标值，则将其它分支剪去不再计算,若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分支，再检查，直到得到最优解。分支原则：始终选Z值大的，且xi中有分数的LP进行分支。定界原则：满足取整要求，且目标函数值较已定的“界”更优，则用该目标函数值替换，重新定界。

3.2.1分支定界法说明：

分支定界法适用于求解纯整数规划和混合整数规划314.

检查所有分支的解及目标函数值，若某分支的解是整数并且设纯整数规划

松弛问题的最优解3.2.2割平面法设xi=不为整数，32设纯整数规划松弛问题的最优解3.2.2割平面法设xi将分离成一个整数与一个非负真分数之和：则有等式两边都为整数,并且有3.2.2割平面法33将分离成一个整数与一个非负真分加入松弛变量si得此式称为以xi行为源行（来源行）的割平面方程，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部变量为整数。则3.2.2割平面法34加入松弛变量si得此式称为以xi行为源行（来源行）的割平面方例如，x1行：移项：加入松弛变量s1得割平面方程同理，对于x2行有：3.2.2割平面法35例如，x1行：移项：加入松弛变量s1得割平面方程同理，对于x【例3-6】用割平面法求解下列IP问题【解】对应的松弛问题是3.2.2割平面法36【例3-6】用割平面法求解下列IP问题【解】对应的松弛问加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。

最优解X(0)＝(5/2，15/4),不是IP的最优解。选择表中的第一行(也可以选第二行)为源行Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4表3-33.2.2割平面法37加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。分离系数后改写成加入松弛变量x5得到高莫雷约束方程将此式作为约束条件添加到表3－3中，用对偶单纯形法计算，如表3－4所示

3.2.2割平面法38分离系数后改写成加入松弛变量x5得到高莫雷约束方程将此式作为Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4－20015/215/4－2λj00－5/8－1/40430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最优解X(1)＝(3，3)，最优值Z＝21。表3－43.2.2割平面法39Cj43000bCBXBx1x2x3x4x54x1101/4x2x1ACBx1+2x2=100DC6x1+4x2=30Ex1+x2≤6几何意义

由约束条件得：x3=30-6x1-4x2,x4=10-x1-2x2代入割平面方程-x3-2x4≤-2，得x1+x2≤6

说明：利用割平面法求解整数规划问题时,若从最优单纯形表中选择具有最大小（分）数部分的非整分量所在行构造割平面方程，往往可以提高“切割”效率，减少“切割”次数。

3.2.2割平面法不含任何整数解40x2x1ACBx1+2x2=100DC6x1+4x2=30E5x15x1+9x2≤45x2x1+x2≤66960思考：

对于两个变量的纯整数规划问题是否可采用图解法。最优解x1=0,x2=53.2.3整数规划的图解法415x15x1+9x2≤45x2x1+x2≤66960思考：最步骤：1.作出松弛问题的可行域。2.在可行域内作出所有的整数网格。3.作目标函数等值线，将等值线平行移动，最后接触到的网格点（或平行移动到松弛问题的最优解点再往回移，首先接触到的网格点），就是整数规划的最优解。3.2.3整数规划的图解法42步骤：3.2.3整数规划的图解法421.理解分支与定界的含义2.选择合适的“枝”生“枝”3.掌握何时停止生“枝”4.领会割平面法的基本原理5.分离源行，求出Gomory约束6.在最优表中增加Gomory约束，用对偶单纯形法迭代下一节：0－1规划的求解3.2整数规划的求解本节学习要点431.理解分支与定界的含义下一节：0－1规划的求解3.23.3.1求解0－1整数规划的隐枚举法隐枚举法的步骤：

1.找出任意一可行解，目标函数值为Z0

2.

原问题求最大值时，则增加一个约束

作为过滤条件。当求最小值时，上式改为小于等于约束。列出所有可能解，对每个可能解先检验是否满足过滤条件，若满足再检验其它约束，若不满足约束，则不可行，若所有约束都满足，且目标值超过Z0,则应更换过滤条件。4.目标函数值最大（最小）的解就是最优解。3.30－1规划的求解443.3.1求解0－1整数规划的隐枚举法隐枚举法的步骤：1【例3-7】用隐枚举法求解下列BIP问题3.30－1规划的求解(1)(2)(3)(4)45【例3-7】用隐枚举法求解下列BIP问题3.30－1规jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)Zj1(0,0,0,0)

9(1,0,0,0)

2(0,0,0,1)10(1,0,0,1)3(0,0,1,0)

11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)5(0,1,0,0)

13(1,1,0,0)6(0,1,0,1)

14(1,1,0,1)7(0,1,1,0)

15(1,1,1,0)

8(0,1,1,1)16(1,1,1,1)表3－5最优解：X＝(1,0,1,1)T，最优值Z＝143.30－1规划的求解√×√√√√z≧53√√√√275√×

106√√√×16√√√√z≧119√√√√z≧14813118z≥846jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)3.3.2分枝－隐枚举法求解BIP问题

将分枝定界法与隐枚举法结合起来用，得到分枝－隐枚举法。计算步骤如下：（1）将BIP问题的目标函数的系数化为非负，如3.30－1规划的求解473.3.2分枝－隐枚举法求解BIP问题将分枝定界法当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；（4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法搜索可行解和最优解。分枝－隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。(2)变量重新排序：变量依据目标函数系数值按升排序；3.30－1规划的求解48当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝停止分枝和需要继续分枝的原则：（1）当某一子问题是可行解时则停止分枝并保留；（2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；（3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝；（4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。3.30－1规划的求解49停止分枝和需要继续分枝的原则：3.30－1规划的求解4【例3-8】用分枝－隐枚举法求解下列BIP问题3.30－1规划的求解50【例3-8】用分枝－隐枚举法求解下列BIP问题3.30【解】（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.30－1规划的求解51【解】（1）目标函数系数全部非负，直接对变量重新排序（2）求表3-8令x2=1同时令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1时只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝过程结束。整个计算过程可用图3－2和表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不可行52表3-8令x2=1同时令x3=0得到分枝4，X4是可行解，搜索到3个可行解，3个目标值中Z3最大，因此X3是最优解，转换到原问题的最优解为X＝（1，0，1，1），最优值Z＝14，计算结束。图3－23.30－1规划的求解53搜索到3个可行解，3个目标值中Z3最大，因此X3是最【例3-9】用分枝－隐枚举法求解下列BIP问题【解】（1）令x2=1－x'2及x5=1－x'5，代入模型后整理得3.30－1规划的求解54【例3-9】用分枝－隐枚举法求解下列BIP问题【解】（1）（2）目标函数系数按升序将对应的变量重新排列得到模型（3）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解X1＝（0，0，0，0，0），Z1＝－7，检验约束条件知X1不可行，进行分枝。（4）取x1=1和x1=0，分别其它变量等于“1”和

“0”分枝，判断可行性，计算过程参见表3－6及图3－3。3.30－1规划的求解55（2）目标函数系数按升序将对应的变量重新排列得到模型（3）求分枝j上一分枝Xj=(x1,x4,x'2,x'5,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)√√√×√××××√－7－5－4－3－1不可行不可行不可行不可行可行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)√×√√√××××√－6－4－3－20不可行不可行不可行不可行可行表3－63.30－1规划的求解56分枝j上一分枝Xj=(x1,x4,x'2,x'5,x由表3－6知，分枝5和分枝10两个问题可行，分枝5优于分枝10，其它不可行子问题尽管目标值优于分枝5，由约束(3-11b)知，继续分枝不可能得到其它可行解，因此停止分枝，计算结束。分枝5的解X5＝(x1,x4,x'2,x'5,x3)＝（0，0，0，0，1），原BIP的最优解为X＝(x1,x2,x3,x4,x5)＝(0，1，1，0，1),最优值Z＝－1。图3－33.30－1规划的求解57由表3－6知，分枝5和分枝10两个问题可行，分枝5优于分枝1在分枝－隐枚举法的计算过程中，由于变量已经按目标函数系数从小到大重新排序，因此在选择子问题分枝的原则是按排序后的变量顺序分枝，但变量较多时搜索可行解的过程可能非常漫长。针对转换后的目标函数特征，极大值问题的解中“1”越多越优，极小值问题的解中“0”越多越优，因此在选择变量分枝时尽可能采用避“0”或“1”的方法，请观察表3－8及3－6.3.30－1规划的求解58在分枝－隐枚举法的计算过程中，由于变量已经按目标函数

长江综合商场有5000m2营业面积招租，拟吸引以下5类商店入租。已知各类商店开设一个店铺占用的面积，在该商场内最多与最少开设的个数，以及每类商店开设不同个数时每个商店的每月预计利润见表。商场除按租用面积每月收取100元/m2租金外，还按利润的10%按月收取屋业管理费。问该商场应招租上述各类商店各多少个，使预期收入为最大？代号商店类别一个铺面面积(m2)开设数开设不同数时一个店铺利润(万元)最少最多1231服装250139872鞋帽35012109-3百货600132720204书店300021610-5餐饮40013171512思考商场招租59长江综合商场有5000m2营业面积招租，拟吸引以代号商店类别开设不同个数店铺1231服装x11x12x132鞋帽x21x22x233百货x31x32x334书店x41x42x435餐饮x51x52x53思考商场招租60代号商店开设不同个数店铺1231服装x11x12x132鞋帽maxZ=100(250y1+350y2+600y3+300y4+400y5)+10%(9x11+8×2x12+7×3x13+10x21+9×2x22+…+12×3x53)x11+2x12+3x13=y1x21+2x22+3x23=y2x31+2x32+3x33=y3x41+2x42+3x43=y4x51+2x52+3x53=y5x11+x12+x13=1x21+x22+x23=1x31+x32+x33=1x41+x42+x43≤1x51+x52+x53=1x23=0x43=0250y1+350y2+600y3+300y4+400y5≤5000xij=0或1（i=1,2,3,4,5;j=1,2,3),yi≥0(i=1,…，5）61maxZ=100(250y1+350y2+600y3+300用LINDO软件计算，得最优解

x12=x22=x33=x42=x53=1，其余xij=0

最优值Z=63（万元）最优方案：招租服装店2个，鞋帽店2个，百货店3个，书店2个，餐饮店3个，预期收入最大，为63万元思考商场招租62用LINDO软件计算，得最优解思考商场招租621.用隐枚举法求0-1规划的最优解2.用分枝－隐枚举法求解0-1规划的最优解TheEndofChapter33.30－1规划的求解本节学习要点631.用隐枚举法求0-1规划的最优解TheEndof【案例C-3】证券营业网点设置问题【解】引入0－1变量

令bj表示在第j号城市建一家网点的平均投资额，rj表示第j号城市每一家网点的平均市场占有率，cj表示第j号城市每一家网点的平均利润额。64【案例C-3】证券营业网点设置问题【解】引入0－1变量6565谢谢！谢谢！云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学运筹学第三章云南农业大学

线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。

对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资。3.1整数规划的数学模型

纯整数规划(IP)：xj全部取整数混合整数规划(MIP)：xj部分取整数0-1整数规划(BIP)：整数变量只能取0或1分类68线性规划的决策变量取值可以是任意非负实数，但许多实际问【例3-1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，才能使所装物品的总价值最大？表3-1【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(3-1)物品重量（公斤/件）体积（m3/件）价值(元/件)甲乙1.20.80.0020.0025433.1整数规划的数学模型

69【例3-1】某人有一背包可以装10公斤重、0.025m3的

【补充例】投资决策问题。某公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表3.1整数规划的数学模型

该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：（1）在项目1、2和3中必须且只有一项被选中；（2）项目3和项目4最多只能选中一项；（3）项目5被选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，使投资收益最大？项目投资额（万元）投资收益（万元）12101602300210315060413080526018070【补充例】投资决策问题。某公司有5个项目被列入投资计划【解】设xj为选择第j（j=1,2,3,4,5)个项目的决策3.1整数规划的数学模型

71【解】设xj为选择第j（j=1,2,3,4,5)个项目的【例3-2】在例3-1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，每件物品的重量、体积和价值如下表所示3.1整数规划的数学模型

物品重量（公斤/件）体积（m3/件）价值(元/件)丙丁1.80.60.00150.0024372【例3-2】在例3-1中，假设此人还有一只旅行箱，最大载重【解】（1）引入0－1变量yj，令j=1,2分别是采用背包及旅行箱装载。3.1整数规划的数学模型

(3-2)此问题也可以建立两个整数规划模型。73【解】（1）引入0－1变量yj，令j=1,2分别是采用（2）由于不同载体所装物品不一样，数学模型为3.1整数规划的数学模型

其中M为充分大的正数。当使用背包时(y1=1,y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0,y2=1)，式(a)和(c)是多余的。背包约束旅行箱约束74（2）由于不同载体所装物品不一样，数学模型为3.1整数规（1）右端常数是k个值中的一个时，类似式(3-2)的约束条件为3.1整数规划的数学模型

同样可以讨论对于有m个条件互相排斥、有m（≤m、≥m）个条件起作用的情形。75（1）右端常数是k个值中的一个时，类似式(3-2)的约束条件（2）对于m个（组）条件中有k（≤m）个（组）起作用时，类似式(3-3)的约束条件写成这里yi=1表示第i组约束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i个约束起作用。当约束条件是“≥”符号时右端常数项应为3.1整数规划的数学模型

76（2）对于m个（组）条件中有k（≤m）个（组）起作用时【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束条件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，则x2≥0，否则x2≤8（3）x2取值0，1，3，5，7【解】

（1）3个约束只有1个起作用或3.1整数规划的数学模型

如果要求至少一个条件满足，模型如何改变？77【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束（3）右端常数是5个值中的1个（2）两组约束只有一组起作用3.1整数规划的数学模型

(1)(2)(3)(4)78（3）右端常数是5个值中的1个（2）两组约束只有一组起作用3【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产。已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表3－2所示，怎样安排产品的加工使总成本最小。表3－2

固定成本（元）变动成本（元／件）最大加工数（件）本企业加工50081500外协加工Ⅰ80052000外协加工Ⅱ6007不限3.1整数规划的数学模型

79【例3-4】企业计划生产4000件某种产品，该产品可自己加工【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为3.1整数规划的数学模型

其中kj是固定成本，cj是可变成本。设0－1变量yj80【解】设xj为采用第j（j=1,2,3）种方式生产的产品数（3-4）用WinQSB软件求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=254003.1整数规划的数学模型

配合目标，使得只有选用第j种加工方式才产生相应成本，不选用第j种加工方式就没有成本。81（3-4）用WinQSB软件求解得到：3.1整数规划的数整数规划的一般形式：称线性规划模型（Ⅰ）

（Ⅱ）(LP)为（Ⅰ）的松弛问题。

每一个整数规划都对应一个松弛问题，整数规划比它的松弛问题约束得更紧。部分或全部取整3.1整数规划的数学模型

82整数规划的一般形式：称线性规划模型（Ⅰ）（Ⅱ）(LP)为3.1整数规划的数学模型

习题3.4【解】令运动员甲、乙、丙、丁、戊编号为1、2、3、4、5，项目高低杠、平衡木、鞍马、自由体操编号为1、2、3、4。设

项目运动员1234高低杠平衡木鞍马自由体操1甲x11x12x13x142乙x21x22x23x243丙x31x32x33x344丁x41x42x43x445戊x51x52x53x54833.1整数规划的数学模型习题3.4max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24+8.8x31

+8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52+8.2x53+7.7x54x11+x12+x13+x14≦3x21+x22+x23+x24≦3x31+x32+x33+x34≦3x41+x42+x43+x44≦3x51+x52+x53+x54≦3x11+x21+x31+x41+x51≧1x12+x22+x32+x42+x52≧1x13+x23+x33+x43+x53≧1x14+x24+x34+x44+x54≧1x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43+x44+x51+x52+x53+x54=10xij=0或1(i=1,2,3,4,5;j=1,2,3,4)3.1整数规划的数学模型

84max=8.6x11+9.7x12+8.9x13+9.4x11.整数规划模型的特征2.什么是纯（混合）整数规划3.0－1规划模型的应用下一节：纯整数规划的求解3.1整数规划的数学模型

本节学习要点851.整数规划模型的特征下一节：纯整数规划的求解3.1

整数规划解的特点整数规划（Ⅰ）的可行解集是其松弛问题（Ⅱ）的可行解集的子集。线性规划问题的可行解集是一个凸集（稠密的），但整数规划的可行解集不是凸集（离散型）。如果松弛问题（Ⅱ）的最优解是整数解，则一定是整数规划（Ⅰ）的最优解。整数规划（Ⅰ）的最优值不会优于松弛问题（Ⅱ）的最优值。3.2整数规划的求解86整数规划解的特点3.2整数规划的求解203.2整数规划的求解图3-1点B为最优解X＝(3.57，7.14)Z＝35.7用图解法求解例3-1的松弛问题整数规划问题的可行解集是图中可行域内的整数点。8.3310松弛问题的最优解X=(3.57,7.14),z=35.7x1x2oAC10B图3-1873.2整数规划的求解图3-1点B为最优解用图解法求解松弛问题的最优解X＝(3.57，7.14)，Z＝35.7“四舍五入”得X=(4,7)不是可行解；用“取整”法来解时，X=(3,7)虽属可行解，但代入目标函数得Z=33,并非最优。该整数规划问题的最优解是X=(5,5)，最优值是Z=35即甲、乙两种物品各装5件，总价值35元。

由图3－1知，点（5，5）不是LP可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。3.2整数规划的求解8.3310松弛问题的最优解X=(3.57,7.14),z=35.7x1x2oAC10B图3-188松弛问题的最优解X＝(3.57，7.14)，Z＝35【例3-5】用分支定界法求解例3-1【解】先求对应的松弛问题用图解法得到最优解X＝（3.57,7.14）,Z0=35.73.2.1分支定界法89【例3-5】用分支定界法求解例3-1【解】先求对应的松弛问8.3310松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2.1分支定界法908.3310松弛问题LP0的最优解X=(3.57,7.11010x1x20ABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5911010x1x20ABCLP1LP234LP1:X=(3,1010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP3:X=(4.33,6),Z3=35.33LP2LP3921010x10ACLP134LP1:X=(3,7.6),x1x11010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP2LP3LP5LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=35此为原IP最优解593x1x11010x10ACLP134LP1:X=(3,7.尽管LP1的解中x2不为整数，但Z5≧Z1，因此LP5的最优解就是原整数规划的最优解。若Z5≦Z1

，则要对LP1进行分支。3.2.1分支定界法94尽管LP1的解中x2不为整数，但Z5≧Z1，因此L上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5

无可行解x2≥7最优解3.2.1分支定界法95上述分枝过程可用下图表示LP0:X=(3.57,7.14分支定界法的步骤：1.求整数规划的松弛问题最优解；2.

若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；3.2.1分支定界法3.任意选一个非整数解的变量xi，在松弛问题中加上约束xi≤[xi]及xi≥[xi]+1组成两个新的松弛问题，称为分支。新的松弛问题具有特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题是求最小值时，目标值是分支问题的下界；96分支定界法的步骤：1.求整数规划的松弛问题最优解；3.4.

检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于（max）等于其它分支的目标值，则将其它分支剪去不再计算,若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分支，再检查，直到得到最优解。分支原则：始终选Z值大的，且xi中有分数的LP进行分支。定界原则：满足取整要求，且目标函数值较已定的“界”更优，则用该目标函数值替换，重新定界。

3.2.1分支定界法说明：

分支定界法适用于求解纯整数规划和混合整数规划974.

检查所有分支的解及目标函数值，若某分支的解是整数并且设纯整数规划

松弛问题的最优解3.2.2割平面法设xi=不为整数，98设纯整数规划松弛问题的最优解3.2.2割平面法设xi将分离成一个整数与一个非负真分数之和：则有等式两边都为整数,并且有3.2.2割平面法99将分离成一个整数与一个非负真分加入松弛变量si得此式称为以xi行为源行（来源行）的割平面方程，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部变量为整数。则3.2.2割平面法100加入松弛变量si得此式称为以xi行为源行（来源行）的割平面方例如，x1行：移项：加入松弛变量s1得割平面方程同理，对于x2行有：3.2.2割平面法101例如，x1行：移项：加入松弛变量s1得割平面方程同理，对于x【例3-6】用割平面法求解下列IP问题【解】对应的松弛问题是3.2.2割平面法102【例3-6】用割平面法求解下列IP问题【解】对应的松弛问加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。

最优解X(0)＝(5/2，15/4),不是IP的最优解。选择表中的第一行(也可以选第二行)为源行Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4表3-33.2.2割平面法103加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。分离系数后改写成加入松弛变量x5得到高莫雷约束方程将此式作为约束条件添加到表3－3中，用对偶单纯形法计算，如表3－4所示

3.2.2割平面法104分离系数后改写成加入松弛变量x5得到高莫雷约束方程将此式作为Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4－20015/215/4－2λj00－5/8－1/40430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最优解X(1)＝(3，3)，最优值Z＝21。表3－43.2.2割平面法105Cj43000bCBXBx1x2x3x4x54x1101/4x2x1ACBx1+2x2=100DC6x1+4x2=30Ex1+x2≤6几何意义

由约束条件得：x3=30-6x1-4x2,x4=10-x1-2x2代入割平面方程-x3-2x4≤-2，得x1+x2≤6

说明：利用割平面法求解整数规划问题时,若从最优单纯形表中选择具有最大小（分）数部分的非整分量所在行构造割平面方程，往往可以提高“切割”效率，减少“切割”次数。

3.2.2割平面法不含任何整数解106x2x1ACBx1+2x2=100DC6x1+4x2=30E5x15x1+9x2≤45x2x1+x2≤66960思考：

对于两个变量的纯整数规划问题是否可采用图解法。最优解x1=0,x2=53.2.3整数规划的图解法1075x15x1+9x2≤45x2x1+x2≤66960思考：最步骤：1.作出松弛问题的可行域。2.在可行域内作出所有的整数网格。3.作目标函数等值线，将等值线平行移动，最后接触到的网格点（或平行移动到松弛问题的最优解点再往回移，首先接触到的网格点），就是整数规划的最优解。3.2.3整数规划的图解法108步骤：3.2.3整数规划的图解法421.理解分支与定界的含义2.选择合适的“枝”生“枝”3.掌握何时停止生“枝”4.领会割平面法的基本原理5.分离源行，求出Gomory约束6.在最优表中增加Gomory约束，用对偶单纯形法迭代下一节：0－1规划的求解3.2整数规划的求解本节学习要点1091.理解分支与定界的含义下一节：0－1规划的求解3.23.3.1求解0－1整数规划的隐枚举法隐枚举法的步骤：

1.找出任意一可行解，目标函数值为Z0

2.

原问题求最大值时，则增加一个约束

作为过滤条件。当求最小值时，上式改为小于等于约束。列出所有可能解，对每个可能解先检验是否满足过滤条件，若满足再检验其它约束，若不满足约束，则不可行，若所有约束都满足，且目标值超过Z0,则应更换过滤条件。4.目标函数值最大（最小）的解就是最优解。3.30－1规划的求解1103.3.1求解0－1整数规划的隐枚举法隐枚举法的步骤：1【例3-7】用隐枚举法求解下列BIP问题3.30－1规划的求解(1)(2)(3)(4)111【例3-7】用隐枚举法求解下列BIP问题3.30－1规jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)Zj1(0,0,0,0)

9(1,0,0,0)

2(0,0,0,1)10(1,0,0,1)3(0,0,1,0)

11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)5(0,1,0,0)

13(1,1,0,0)6(0,1,0,1)

14(1,1,0,1)7(0,1,1,0)

15(1,1,1,0)

8(0,1,1,1)16(1,1,1,1)表3－5最优解：X＝(1,0,1,1)T，最优值Z＝143.30－1规划的求解√×√√√√z≧53√√√√275√×

106√√√×16√√√√z≧119√√√√z≧14813118z≥8112jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)3.3.2分枝－隐枚举法求解BIP问题

将分枝定界法与隐枚举法结合起来用，得到分枝－隐枚举法。计算步骤如下：（1）将BIP问题的目标函数的系数化为非负，如3.30－1规划的求解1133.3.2分枝－隐枚举法求解BIP问题将分枝定界法当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；（4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法搜索可行解和最优解。分枝－隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。(2)变量重新排序：变量依据目标函数系数值按升排序；3.30－1规划的求解114当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝停止分枝和需要继续分枝的原则：（1）当某一子问题是可行解时则停止分枝并保留；（2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；（3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝；（4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。3.30－1规划的求解115停止分枝和需要继续分枝的原则：3.30－1规划的求解4【例3-8】用分枝－隐枚举法求解下列BIP问题3.30－1规划的求解116【例3-8】用分枝－隐枚举法求解下列BIP问题3.30【解】（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.30－1规划的求解117【解】（1）目标函数系数全部非负，直接对变量重新排序（2）求表3-8令x2=1同时令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1时只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝过程结束。整个计算过程可用图3－2和表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不可行118表3-8令x2=1同时令x3=0得到分枝4，X4是可行解，搜索到3个可行解，3个目标值中Z3最大，因此X3是最优解，转换到原问题的最优解为X＝（1，0，1，1），最优值Z＝14，计算结束。图3－23.30－1规划的求解119搜索到3个可行解，3个目标值中Z3最大，因此X3是最【例3-9】用分枝－隐枚举法求解下列BIP问题【解】（1）