《《运筹学（第2版）孔造杰or1-ch6-整数规划》由会员分享，可在线阅读，更多相关《《运筹学（第2版）孔造杰or1-ch6-整数规划（72页珍藏版）》请在金锄头文库上搜索。
1、第六章 整数规划 Integer Programming,6-1 整数规划模型 6-2 分枝定界法 6-3 割平面法 6-4 0-1规划 6-5 指派问题 6-6 整数规划的计算机解法 6-7 IP的应用及案例分析,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 2 of 72,6-1 整数规划模型（Model of Integer Programming）,在线性规划与非线性规划模型中，变量的取值是在实数范围或在正实数范围。 但是，在很多管理与经济活动中，要求所探讨的问题变量只能取整数值或取整数值中的一部分。如人数、机器台数、投资项目个数等，这时的非整数解就没有
2、意义。 如果一个规划模型中的变量有整数要求，则该规划模型就是整数规划模型。 整数规划模型包括：整数规划、0-1规划、混合规划 三种类型。,例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数,2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x， 当x=1表示投资，x=0表示不投资；,3. 人员的合理安排问题，当变量xij=1表示安排第i人去做j工作， xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数 值的一类变量。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 3 of 72,6-1 整数规划模型（Model of Inter
3、Programming）,纯整数规划模型及其解的分析 求解整数解的线性规划问题，通常人们首先想到的是先不管整数条件的限制，直接使用单纯形法求解，然后将所得到的非整数解经四舍五入化为整数。但是这种办法往往是行不通的，这是因为由舍入化整所得的整数解不一定是可行解，即便是可行解，也不一定是最优解。 【例6-1 】整数规划问题,图6-1,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 4 of 72,6-1 整数规划模型（Model of Integer Programming）,如果先不考虑决策变量 的整数限制，无论是用图解法还是用单纯形法都可很容易地求得最优解为： ，
4、 。这里也很容易验证：,（1）如果按四舍五入将非整数解 化为整数，应取 ， 而 不是可行解；,（2）如果把 的小数部分0.8舍去，取 ，它虽是可行解，但不是最优解，这是因为 ，而 ，且（0，2）也是可行解。,由此可见，用凑整数法解整数规划是不可取的。目前，解整数规划问题通常采用的方法是分支定界法和割平面法。不过割平面法通常用于手工解法，适应于一些小型的问题，对于较大的整数规划问题一般采用分支定界法用计算机来求解，特别是对于那些只要求部分决策变量是整数的规划问题，分支定界法尤为方便。,纯整数规划模型及其解的分析(续）,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page
5、5 of 72,6-1 整数规划模型（Model of Integer Programming）,【例6-2 】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表61所示。问两种物品各装多少件，所装物品的总价值最大？,表61,【解】设甲、乙两种物品各装x1、x2件，则数学模型为：,(6.1),纯整数规划模型及其解的分析,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 6 of 72,6-1 整数规划模型（Model of Integer Programming）,如果不考虑x1、x2取整数的约束，线性规划
6、的可行域如图6-2中的阴影部分所示。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 7 of 72,6-1 整数规划模型（Model of Integer Programming）,用图解法求得点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元。 由图6-2知，点（5
7、，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。 还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 8 of 72,6-1 整数规划模型（Model of Integer Programming）,0-1规划问题 当进一步限定线性规划问题中的决策变量只取0、1两个值时，就构成了一类特殊的整数规划0-1整数规划。这时的决策变量称为0-1变量。在实际问题中，有些问题往往只需回答“是”或“否”，问题就算解决
8、了。描述这类问题的变量只需要取两个值就可以了。如果问题的变量不是仅取0和1，而是可取其它某个范围的非负整数，则也可以利用二进制的记数法将它用若干个0-1变量来代替，从而将其化为0-1整数规划。 引入0-1变量的实际问题 投资场所的选定：有n个投资场所，对每一投资场所的投资有一定限额与一定的收益，而根据一些限制的条件，只能对其中某些投资场所投资，问如何从n个投资场所中选择出m个场所（在一定约束条件下），使投资收益最大,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 9 of 72,6-1 整数规划模型（Model of Integer Programming）,相互
9、排斥的约束条件 为了使m个互相排斥的约束条件：,中只有一个起作用，可以引入m个0-1变量yi（i=1m）和一个充分大的正数M，用下面这一组m+1个方程来表示这m个相互排斥的约束条件。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 10 of 72,6-1 整数规划模型（Model of Integer Programming）,【例6-3 】在例6-2中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。 所装物品不变； 如果选择旅行箱，载重量和体积的约束为,解：此问题可
10、以建立两个整数规划模型，但用一个模型描述更简单。,引入01变量（或称逻辑变量）yi，令,i=1,2分别是采用背包及旅行箱装载。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 11 of 72,6-1 整数规划模型（Model of Integer Programming）,由于所装物品不变，式(6.1)约束左边不变，整数规划数学模型为：,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 12 of 72,6-1 整数规划模型（Model of Integer Programming）,【例6-4 】企业计划生产2000件某种产品，该种
11、产品可利用、设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 13 of 72,6-1 整数规划模型（Model of Integer Programming）,【解】设xj表示在第j（j=1,2,3）种设备上加工的产品数量， 其生 产费用为：,式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设01变量yj，令,目标函数为：,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,
12、Page 14 of 72,6-1 整数规划模型（Model of Integer Programming）,用QSB软件求解得到：X（0，800，1200），Y（0，1，1），Z=8100.,如果问题的所有变量取0或1，此问题称为01整数规划问题，简称01规划。,式中 是一个特殊的约束条件，显然当xj0时，yj=1, 当xj0时，为使Z极小化，只有yj=0才有意义。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 15 of 72,6-2 分枝定界法,由于整数规划是在原线性规划模型的基础上加上整数条件，因此，整数规划的可行域必在原线性规划问题的可行域之中，因而整
13、数规划问题的最优解不会超过对应的线性规划问题的最优解。所以，任何有界整数规划问题仅有有限个整数可行解。,分枝定界法的步骤：,1. 求整数规划的松弛问题（对应LP模型）最优解；,3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；,4. 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，
14、再检查，直到得到最优解。,2. 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 16 of 72,6-2 分枝定界法,解：先不考虑整数条件，用图解法或单纯形法可求得相应的线性规划的最优解为：,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 17 of 72,6-2 分枝定界法,随着原整数规划被分为两枝（）和（），原整数规划的可行域R也被分为两个可行域R1和R2（见下图）,由于最优解的两个变量都是非整数，因此可任对其中一个进行分枝，例如对变量将原整数规划分解为如下两个
15、整数规划：,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 18 of 72,6-2 分枝定界法,同样，先不考虑整数条件，分别解出与（）和（）相应的线性规划，得到最优解如下表,由于这两个解都不是整数解，所以还必须将（）和（）继续进行分枝、求解。先将（）对变量x2分为两枝如下，其可行域如图所示。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 19 of 72,6-2 分枝定界法,先不考虑整数条件，分别求得（1）和（2）的最优解如表 问题（1）已是整数解，问题（2）虽非整数解，但其整数解不会超过其当前最优解44，更不会超过（1）的当前目
16、标函数值45，所以就没有必要再对（2）进行分枝求解了。 由于（）的目标函数值Z=48大于（1）的目标函数值45，所以（）的整数解目标函数值仍可能大于45，所以，还必须对（）继续分枝求解。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 20 of 72,6-2 分枝定界法,在不考虑整数条件下，不难求得结果如表 由此结果看出，线性规划（1）的最优解虽不是整数解，但它的最优整数解的目标函数值不会超过（1）的整数解目标函数值Z=45，而线性规划（2）无解。因此，整数规划（1）的最优解就是原整数规划的最优解，其目标函数值为Z=45。,2019年9月23日3时39分,河北工业大学管理学院 孔造杰 制作,Page 21 of 72,【例6-6 】用分枝定界法求解例6.2,【解
