运筹学课件Ch3整数规划

3.1整数规划数学模型

MathematicalModelofIP3.2纯整数规划的求解

SolvingPureIntegerProgramming

3.3

0－1规划的求解

SolvingBinaryIntegerProgramming

Chapter3整数规划IntegerProgramming运筹学OperationsResearch1/12/20233.1整数规划数学模型

MathematicalModelofIP1/12/2023

一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。

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

MathematicalModelofIP

1/12/2023【例3.1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，所装物品的总价值最大？表3-1【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(3.1)3.1整数规划的数学模型

MathematicalModelofIP

物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.0025431/12/2023如果不考虑x1、x2取整数的约束（称为（3.1）的松弛问题），线性规划的可行域如图3-1中的阴影部分所示。3.1整数规划的数学模型

MathematicalModelofIP

图3-11/12/2023

用图解法求得点B为最优解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。

由图3－1知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。3.1整数规划的数学模型

MathematicalModelofIP

1/12/2023【例3.2】在例3.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为【解】此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入0－1变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。3.1整数规划的数学模型

MathematicalModelofIP

1/12/2023（1）

由于所装物品不变，式(3.1)约束左边不变，整数规划数学模型为（2）

由于不同载体所装物品不一样，数学模型为3.1整数规划的数学模型

MathematicalModelofIP

1/12/2023式中M为充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：

同样可以讨论对于有m个条件互相排斥、有m（≤m、≥m）个条件起作用的情形。3.1整数规划的数学模型

MathematicalModelofIP

1/12/2023（1)右端常数是k个值中的一个时，类似式(3.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整数规划的数学模型

MathematicalModelofIP

1/12/2023【例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整数规划的数学模型

MathematicalModelofIP

或1/12/2023（3）右端常数是5个值中的1个3.1整数规划的数学模型

MathematicalModelofIP

（2）两组约束只有一组起作用1/12/2023【例3.4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表3－2所示，怎样安排产品的加工使总成本最小．表3－2【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为3.1整数规划的数学模型

MathematicalModelofIP

固定成本（元）变动成本（元／件）最大加工数（件）本企业加工50081500外协加工Ⅰ80052000外协加工Ⅱ6007不限1/12/2023式中kj是固定成本，cj是单位产品成本．设0－1变量yj，令数学模型为

3.1整数规划的数学模型

MathematicalModelofIP

（3.4）式（3.4）中是处理xj与yj一对变量之间逻辑关系的特殊约束，当xj>0时yj=1,当xj＝0时，为使Z最小化，有yj=0。例3.4是混合整数规划问题．用WinQSB软件求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=25400.1/12/2023作业：教材P751,2，3，4，5，61.线性整数规划模型的特征2.什么是纯（混合）整数规划3.0－1规划模型的应用3.1整数规划的数学模型

MathematicalModelofIP

下一节：纯整数规划的求解1/12/20233.2纯整数规划的求解SolvingPureIntegerProgramming1/12/2023分枝定界法的步骤：1.求整数规划的松弛问题最优解；2.

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

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

1/12/2023【例3.5】用分枝定界法求解例5.1【解】先求对应的松弛问题（记为LP0）：

用图解法得到最优解X＝（3.57,7.14）,Z0=35.7,如下图所示。3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/20238.3310松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/20231010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②1/12/20231010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.81/12/20231010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP51/12/2023尽管LP1的解中x1不为整数，但Z5>Z因此LP5的最优解就是原整数规划的最优解。上述分枝过程可用下图表示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≥71/12/2023设纯整数规划松弛问题的最优解设xi不为整数，3.2.2求解IP的割平面法3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/2023将分离成一个整数与一个非负真分数之和：则有等式两边都为整数并且有3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/2023加入松弛变量si得此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。

将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/2023例如，x1行：移项：令加入松弛变量s1得同理，对于x2行有：3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/2023【例3.6】用割平面法求解下列IP问题【解】放宽变量约束，对应的松弛问题是

3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/2023加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。

最优解X(0)＝(5/2，15/4),不是IP的最优解。选择表3-3的第一行(也可以选第二行)为源行3.2纯整数规划的求解SolvingPureIntegerProgramming

Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4表3-31/12/2023分离系数后改写成加入松弛变量x5得到高莫雷约束方程将式(3.8)作为约束条件添加到表3－3中，用对偶单纯形法计算，如表3－4所示

3.2纯整数规划的求解SolvingPureIntegerProgramming

1/12/2023Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4[－2]0015/215/4－2→λj00－5/8－1/4↑0430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最优解X(1)＝(3，3)，最优值Z＝21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。3.2纯整数规划的求解SolvingPureIntegerProgramming

表3－4如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。1/12/2023作业：教材P76T7，8

1.理解分枝与定界的含义2.选择合适的“枝”生“枝”3.掌握何时停止生“枝”4.领会割平面法的基本原理5.分离源行，求出Gomory约束6.在最优表中增加Gomory约束，用对偶单纯形法迭代3.2纯整数规划的求解SolvingPureIntegerProgramming

下一节：0－1规划的求解1/12/20233.30－1规划的求解SolvingBIP

1/12/20233.3.1求解0－1整数规划的隐枚举法隐枚举法的步骤：

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

2.

原问题求最大值时，则增加一个约束当求最小值时，上式改为小于等于约束

3.列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值

4.目标函数值最大（最小）的解就是最优解3.30－1规划的求解SolvingBIP

1/12/2023【例3.7】用隐枚举法求解下列BIP问题【解】（1）不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到X0＝(1，0，0，1)是一个可行解，目标值Z0＝11是BIP问题的下界，构造一个约束：，原BIP问题变为3.30－1规划的求解SolvingBIP

1/12/2023(2)列出变量取值0和1的组合，共24＝16个，分别代入约束条件判断是否可行。首先判断式（3.9a）是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见表3－7所示。3.30－1规划的求解SolvingBIP

1/12/2023jXj3.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)√√√×

表3－5(3)由表3-5知，BIP问题的最优解：X＝（1，0，1，1），最优值Z＝143.30－1规划的求解SolvingBIP

1/12/2023选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于1，如例3.8。当目标函数求最小值时，先考虑目标函数系数最大的变量等于0。在表3－7的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。3.3.2分枝－隐枚举法求解BIP问题将分枝定界法与隐枚举法结合起来用，得到分枝－隐枚举法。计算步骤如下：（1）将BIP问题的目标函数的系数化为非负，如3.30－1规划的求解SolvingBIP

1/12/2023当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；（4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法搜索可行解和最优解。分枝－隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。3.30－1规划的求解SolvingBIP

(2)变量重新排序：变量依据目标函数系数值按升排序；1/12/2023停止分枝和需要继续分枝的原则：（1）当某一子问题是可行解时则停止分枝并保留；（2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；（3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝；（4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。

【例3.8】用分枝－隐枚举法求解下列BIP问题3.30－1规划的求解SolvingBIP

1/12/2023解（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规划的求解SolvingBIP

1/12/2023表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不可行3.30－1规划的求解SolvingBIP

1/12/2023搜索到3个可行解，3个目标值中Z3最大，因此X3是最优解，转换到原问题的最优解为X＝（1，0，1，1），最优值Z＝14，计算结束。图3－23.30－1规划的求解SolvingBIP

1/12/2023【例3.9】用分枝－隐枚举法求解下列BIP问题解（1）令x2=1－x'2及x5=1－x'5，代入模型后整理得3.30－1规划的求解SolvingBIP

1/12/2023（2）目标函数系数按升序将对应的变量重新排列得到模型（3）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解X1＝（0，0，0，0，0），Z1＝－7，检验约束条件知X1不可行，进行分枝。（4）取x1=1和x1=0，分别其它变量等于“1”和

“0”分枝，判断可行性，计算过程