Chapter 3 整数规划 运筹学 Integer Programming Operations Research

Presentation on theme: "Chapter 3 整数规划 运筹学 Integer Programming Operations Research"— Presentation transcript:

1 Chapter 3 整数规划 运筹学 Integer Programming Operations Research
3.1 整数规划数学模型 Mathematical Model of IP 3.2 纯整数规划的求解 Solving Pure Integer Programming 3.3 0－1规划的求解 Solving Binary Integer Programming

2 Mathematical Model of IP
3.1 整数规划数学模型 Mathematical Model of IP

3 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。 很多实际规划问题都属于整数规划问题 1. 变量是人数、机器设备台数或产品件数等都要求是整数 2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当x=1表示投资，x=0表示不投资； 3. 人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。

4 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 【例3-1 】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，所装物品的总价值最大？ 表3-1 物品 重量 （公斤/每件） 体积 （m3/每件） 价值 (元/每件) 甲 乙 1.2 0.8 0.002 0.0025 4 3 【解】设甲、乙两种物品各装x1、x2件，则数学模型为： (3-1)

5 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 如果不考虑x1、x2取整数的约束（称为（3-1）的松弛问题），线性规划的可行域如图3-1中的阴影部分所示。 图3-1

6 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 用图解法求得点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）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。 还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。

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

8 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 （1） 由于所装物品不变，式(3-1)约束左边不变，整数规划数学模型为 （2）       由于不同载体所装物品不一样，数学模型为

9 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 式中M为充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令： 同样可以讨论对于有m个条件互相排斥、有m（≤m、≥m）个条件起作用的情形。

10 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 （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）个起作用时，约束条件写成

11 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束条件 （1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20 （2）若x1≤5，则x2≥0，否则x2≤8 （3）x取值0，1，3，5，7 【解】 （1）3个约束只有1个起作用 或

12 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 （2）两组约束只有一组起作用 （3）右端常数是5个值中的1个

13 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表3－2所示，怎样安排产品的加工使总成本最小． 表3－2 固定成本（元） 变动成本 （元／件） 最大加工数 （件） 本企业加工 500 8 1500 外协加工Ⅰ 800 5 2000 外协加工Ⅱ 600 7 不限 【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为

14 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 式中kj是固定成本，cj是单位产品成本．设0－1变量yj，令 数学模型为 （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.

15 Mathematical Model of IP
3.1 整数规划的数学模型 Mathematical Model of IP 2019年4月30日星期二 1.线性整数规划模型的特征 2.什么是纯（混合）整数规划 3.0－1规划模型的应用 下一节：纯整数规划的求解

16 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming

17 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 3.2.1求解纯整数规划的分枝定界法 分枝定界法的步骤： 1. 求整数规划的松弛问题最优解； 2.  若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步； 3.任意选一个非整数解的变量xi，在松弛问题中加上约束xi≤[xi]及xi≥[xi]+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界； 4.  检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。

18 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 【例3-5 】用分枝定界法求解例5.1 【解】先求对应的松弛问题（记为LP0）： 用图解法得到最优解X＝（3.57,7.14）,Z0=35.7,如下图所示。

19 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 x2 A 10 松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7 B C o x1 8.33 10

20 x2 ① ② A LP1:X=(3,7.6),Z1=34.8 10 B LP2:X=(4,6.5),Z2=35.5 LP1 LP2 C o 10 x1 3 4

21 x2 ① LP1:X=(3,7.6),Z1=34.8 ② A 10 B 6 LP3:X=(4.33,6),Z3=35.33 LP1 LP3 C o 10 x1 3 4

22 x2 ① ② A 10 6 C o x1 10 3 4 LP1:X=(3,7.6),Z1=34.8 LP4:X=(4,6),Z4=34
5

23 尽管LP1的解中x1不为整数，但Z5>Z因此LP5的最优解就是原整数规划的最优解。
上述分枝过程可用下图表示 LP0:X=(3.57,7.14),Z0=35.7 x1≤3 x1≥4 LP1:X=(3,7.6) Z1=34.8 LP2:X=(4,6.5) Z2=35.5 x2≥7 x2≤6 LP3:X=(4.33,6) Z3=35.33 无可行解 x1≤4 x1≥5 LP4:X=(4,6) Z4=34 LP5:X=(5,5) Z5=35

24 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 3.2.2 求解IP的割平面法 设纯整数规划 松弛问题 的最优解 设xi不为整数，

25 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 将 分离成一个整数与一个非负真分数之和： 则有 等式两边都为整数并且有

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

27 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 例如， x1行： 移项： 令 加入松弛变量s1得 同理，对于x2行有：

28 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 【例3-6】 用割平面法求解下列IP问题 【解】 放宽变量约束，对应的松弛问题是

29 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。 表3-3 Cj 4 3 b CB XB x1 x2 x3 x4 1 1/4 －1/8 －1/2 3/4 5/2 15/4 λj －5/8 －1/4 最优解X(0)＝(5/2，15/4),不是IP的最优解。选择表3-3的第一行(也可以选第二行)为源行

30 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 分离系数后改写成 加入松弛变量x5得到高莫雷约束方程 将式(3-8)作为约束条件添加到表3－3中，用对偶单纯形法计算，如表3－4所示

31 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 表3－4 Cj 4 3 b CB XB x1 x2 x3 x4 x5 1 1/4 －1/8 －1 －1/2 3/4 [－2] 5/2 15/4 －2→ λj －5/8 －1/4↑ 1/2 －1/4 3/8 最优解X(1)＝(3，3)，最优值Z＝21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。 如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。

32 Solving Pure Integer Programming
3.2 纯整数规划的求解 Solving Pure Integer Programming 2019年4月30日星期二 1.理解分枝与定界的含义 2.选择合适的“ 枝”生“ 枝” 3.掌握何时停止生“ 枝” 4.领会割平面法的基本原理 5.分离源行，求出Gomory约束 6.在最优表中增加Gomory约束，用 对偶单纯形法迭代 下一节： 0－1规划的求解

33 3.3 0－1规划的求解 Solving BIP

34 3.3.1 求解0－1整数规划的隐枚举法 隐枚举法的步骤： 1.找出任意一可行解，目标函数值为Z0 2. 原问题求最大值时，则增加一个约束
3.3 0－1规划的求解 Solving BIP 2019年4月30日星期二 3.3.1 求解0－1整数规划的隐枚举法 隐枚举法的步骤： 1.找出任意一可行解，目标函数值为Z0 2.  原问题求最大值时，则增加一个约束 当求最小值时，上式改为小于等于约束 3. 列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值 4. 目标函数值最大（最小）的解就是最优解

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

36 3.3 0－1规划的求解 Solving BIP 2019年4月30日星期二 (2) 列出变量取值0和1的组合，共24＝16个，分别代入约束条件判断是否可行。首先判断式（3-9a）是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见表3－7所示。

37 (3) 由表3-5知，BIP问题的最优解：X＝（1，0，1，1），最优值Z＝14
3.3 0－1规划的求解 Solving BIP 2019年4月30日星期二 表3－5 j Xj 3-9a 3-9b 3-9c 3-9d Zj 1 (0,0,0,0) × 9 (1,0,0,0) 2 (0,0,0,1) 10 (1,0,0,1) √ 11 3 (0,0,1,0) (1,0,1,0) 4 (0,0,1,1) 12 (1,0,1,1) 14 5 (0,1,0,0) 13 (1,1,0,0) 6 (0,1,0,1) (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) 由表3-5知，BIP问题的最优解：X＝（1，0，1，1），最优值Z＝14

38 在表3－7的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。
3.3 0－1规划的求解 Solving BIP 2019年4月30日星期二 选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于1，如例3-8。当目标函数求最小值时，先考虑目标函数系数最大的变量等于0。 在表3－7的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。

39 1.用隐枚举法求0-1规划最优解 基本步骤 2.注意求最大值、最小值的区别 3.3 0－1规划的求解 Solving BIP
3.3 0－1规划的求解 Solving BIP 2019年4月30日星期二 1.用隐枚举法求0-1规划最优解 基本步骤 2.注意求最大值、最小值的区别