数学建模_整数规划

1、第三讲第三讲整数规划整数规划3.1 引言引言 在工程设计和企业管理中，常会遇到要求决策变量取离散非负整数值的线性规划问题。 例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。 这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划整数线性规划问题，也经常简称为整数规划整数规划问题。 整数规划是近四十年来发展起来的、规划论的一个重要的理论分支。根据对决策变量的要求不同，分为四种类型： 纯整数规划纯整数规划：所有决策变量均要求为离散的非负 整数。 混合整数规划混合整数规划：部分决策变量要求为离散的非负 整数

2、。 纯纯 0 1 整数规划整数规划：所有决策变量均要求为 0 或 1。 混合混合 0 1 整数规划整数规划：部分决策变量要求为 0 或 1。 3.2 引例：生产组织计划问题与选址问题引例：生产组织计划问题与选址问题 引例 3.2.1(生产组织计划问题生产组织计划问题)某工厂在一个计划期内拟生产甲、乙两种大型设备。除了 A、B 两种部件需要外部供应且供应受到严格限制之外，该厂有充分的能力来加工制造这两种设备所需的其余零件，并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表 3.2.1 给出。问该厂在本计划期内如何安排甲、乙设备的生产数量，才能获取最大利润？

3、部件设备AB利润(百万)甲6115乙4320部件的最大供应量2510表 3.2.1 设 x1, x2 分别为该计划期内甲、乙设备的生产数量，Z 为生产这两种设备可获得的总利润。依题意，给出问题的数学模型为： max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 这是一个纯整数规划问题。 引例 3.2.2 (选址问题选址问题)某商业连锁集团拟在 n 个连锁店所在城市中建立 m 个配货中心，每个城市最多建立一个配货中心。若在第 i 个城市建立配货中心，其配货能力为 Di，单位时间的固定成本为 ai，i = 1, , n，第 j 个连锁店的

4、需求量为 bj，j = 1, , n。从第 i 个配货中心到第 j 个连锁店的单位运输成本为 cij。应如何选择配货中心位置和安排运输计划，才能得到经济上花费最少的方案。 问题可分为两部分： 选择哪些城市作为配货中心 如何安排运输计划 首先考虑后一个问题：已经选定了 m 个配货中心，如何安排运输计划。 假设从配货中心 i 运往连锁店 j 的物资数量为 xij，Z 为单位时间内的总费用。则上述问题可归结为如下的数学模型： njmixnjbxmiDxxcZijjmiijinjijminjijij, 1 , 1 , 0, 1 , 1 ,s.t.min1111 这是一个线性规划问题(广义的运输问题)。

5、 其次，同时考虑选择配货中心和安排运输计划。 假设在单位时间内，从配货中心 i 运往连锁店 j 的物资数量为 xij，Z 为单位时间内的总费用。 引入布尔变量 则上述问题可归结为如下的数学模型： 个城市建立配货中心不在第个城市建立配货中心在第 , 0 , 1iiyinjiyxnjbxniyDxmyyaxcZiijjniijiinjijniiniiininjijij, 1 , ,1 , 0 , 0, 1 , 1 ,s.t.min111111 这是一个混合 01 规划问题。3.3 整数规划算法整数规划算法 3.3.1 分枝定界法分枝定界法 分枝定界法是求解整数规划问题的一种有效算法，在二十世纪六十

6、年代初由 Land 和Doig 提出并经 Dakin 修正而完善。它不仅适用于求解纯整数规划问题，同时也适用于求解混合整数规划问题。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。 分枝定界法对可行域恰当地进行系统搜索，基本上是一种“分而治之”的策略。 通常，它把可行域反复地划分为越来越小的一系列子域，称之为分枝；子域的一个边界为整数，在子域上解线性规划，对于最大值问题，线性规划解的目标函数值是整数规划的上界，整数规划任意可行点的目标函数值是其下界，这称为定界。在子域分解的过程中，上界非增，下界非减，经有限多次分解即可得到整数规划的最优解。 整数规划问题的数学模型的一般形

7、式一般形式为： , 1 , 0 , 0 ),(s.t. (min) max )P(TixXborAXXCZ 定义定义 凡是放弃问题 (P) 中的某些约束条件后得到的问题 ( )，称为 (P) 的松弛问题。 P 定理定理 若用 R 表示问题 (P) 的可行域，用 x* 和 z* 表示问题 (P) 的最优解与最优值；用 表示问题 ( ) 的可行域，用 和 表示问题 ( ) 的最优解与最优值。则对于任何松弛问题 ( )，有： (1) R ； (2) ( ) 无可行解 (P) 无可行解； (3) z* (对于求最小值的问题 (P)， 则有 z* )； (4) R 也是 (P) 的最优解。 RP*x*z

8、PPRP*z*z*x 根据上述定理，可以给出分枝定界法的基本步骤(参见教材)。 实现上述步骤的程序框图，如图 3.3.1。 为了更好地说明用分枝定界法求整数规划最优解的过程，我们选择只有两个变量的引例3.2.1 进行求解。 例 3.3.1 用分枝定界法求解整数规划问题 (P)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 解解：整数规划问题 (P) 的可行域为： 1. 求解如下的松弛问题 (P0)： (P0)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0，i = 1, 2得

9、最优解 x1 = 2.5，x2 = 2.5，最优值 z = 87.5。松弛问题的最优解(2.5, 2.5) 由于原问题 (P) 目标函数的系数为整数，xi 0, 1, 2, ，故 z* 87，也就是说最优值的上界 = 87。令最优值的下界 z = 0，则有 z = 0 z* 87 = 。 我们将这些结果记录在树形图中。 zz 2. 因为此时两个变量都不是整数，我们从中选择一个变量进行分枝。假定选择 x1，在 (P0) 的约束之外，增加两个互相排斥的约束条件：x1 2 与 x1 3，形成两个子模型 (P1) 和 (P2)： (P1)：max Z = 15x1 20 x2 (P2)：max Z =

10、 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1 4x2 25 x1 3x2 10 x1 3x2 10 x1 2 x1 3 xi 0，i = 1, 2 xi 0，i = 1, 2 相应地，模型 (P0) 的可行域被分成两个相应的子域 R1 和 R2。 显然，被抛去的非阴影区域内(2 x1 z = 75，所以，在 (P2) 的约束之外，增加两个互相排斥的约束条件：x2 1 与 x2 2，形成两个子模型 (P5) 和 (P6)： (P5)：max Z = 15x1 20 x2 (P6)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1

11、4x2 25 x1 3x2 10 x1 3x2 10 x1 3 x1 3 x2 1 x2 2 xi 0，i = 1, 2 xi 0，i = 1, 2 7. 对子模型 (P5) 进行求解，得最优解为 x1 = 3.5，x2 = 1，最优值 z = 72.5。子模型 (P5) 的最优解 (3.5, 1) 由于最优值 z = 72.5 75 = z，故不再分枝。因为分枝后，新模型的最优值不可能超过当前新的下界。 8. 对子模型 (P6) 进行求解，因为无可行解，故不再分枝。子模型 (P6)无可行解 至此，已将所有分枝的子模型求解完毕，当前新的下界值相应的解，是现行最好的整数可行解，也就是原整数规划问

12、题的最优解为：x1* = 1，x2* = 3。最优目标函数值为 z = 75。 z zz z整数解 (1, 3)最优值为 75整数解 (2, 2)最优值为 70 注：图 3.3.3 中的子模型 (P3)、(P4)、(P5) 不再分枝，并不是说它们分枝后不可以找到新的整数可行解，而是表明：即使找出新的整数可行解也不会优于目前最好的整数可行解，其目标函数值不会大于目前的下界值，这些可行解已被全部隐含枚举了。实质上实质上，分枝定界法是一种隐枚举法分枝定界法是一种隐枚举法(Implicit Enumeration)。 提示提示：用分枝定界法求解整数规划问题，其计算量一般比较大，所以此法只能求解规模不太

13、大的整数规划问题。对于规模较大的整数规划问题，可以采取启发式算法，例如遗传算法来求解。 3.3.2 求解求解 0 1 规划模型的隐枚举法规划模型的隐枚举法 01 规划是整数规划的特殊情况，可用前面介绍的方法求解。但由其变量取值的特性，它另有一种特殊的分枝定界法隐枚举法，该方法也是通过求解线性松弛模型来获得原整数规划模型的最优解：不过这里恰好与一般分枝定界法相反，是由放弃所有线性约束，只保留变量 01 约束而得到的。 隐枚举法要求 01 规划为下述标准形式其中 cj 0，约束条件必须为“”。 njxmibxaxcZjinjjijnjjj, 1 ,1 , 0, 1 ,s.t.min11 当某一 c

14、j0 0时，令 = 1 xj0，则再令 = cj0，原目标函数变为从而使目标函数中各变量的系数变为非负数。 0jx)1 (0000001jjjjjjjjjjjjnjjjxcxcxcxcxcZ0jc0000jjjjjjjxccxc 隐枚举法的解法思路与分枝定界法有相似之处，即利用变量只能取 0 或 1 进行分枝。首先令全部变量取 0 值(当求最大值时，令全部变量取 1 值)，检验解是否满足约束条件。若均满足，已得最优解；若不全满足。则令一个变量取值为 0 或 1(此变量称为固定变量固定变量)，将模型分成两个子棋型，其余未被指定取值的变量称为自由变量自由变量。由于 cj 0，因此自由变量为 0 与

15、固定变量组成的子模型的解使目标值最小。经过几次检验后，或者停止分枝，或者将另一个自由变量转为固定变量，令其值为 0 或 1，继续分枝。如此继续进行，直至没有自由变量或全部子模型停止分枝为止，就求出最优解。 下面通过一个例子来说明“隐枚举法”的解题步骤。 例 3.3.2 求解下列 01 规划的最优解 min Z = 8x1 2x2 + 4x3 + 7x4 + 5x5 s.t. 3x1 3x2 + x3 + 2x4 + 3x5 2 5x1 3x2 2x3 x4 + x5 4 xi0, 1，i = 1, 2, 3, 4, 5 解解：将原模型记为 P0，所有自由变量全部取 0 值，目标值 z0 = 0

16、，显然不是可行解。 不妨取 x1 作为固定变量，在 P0 中增加约束 x1 = 0 记为 P1，增加约束 x1 = 1 记为 P2。 模型 P2 中 x1 = 1，其他为自由变量，均取 0 值，此时X = (1, 0, 0, 0, 0)T为可行解，停止分枝。目标值 z2 = 8，因此，原模型的最优值的上界为 8。 模型 P1 不满足算法中停止的条件，需继续分枝。将 x2 变为固定变量，于是模型 P1 分为两个分枝 P3 和 P4，继续考虑 P3 和 P4。 为了清晰地表达求解过程，类似于分枝定界法，我们作出树形图(图 3.3.4)，图中黑体数字表示该变量为固定变量。 最优解为X* = (0,

17、1, 1, 0, 0)T最优值为 z* = z6 = 6。 3.3.4 舍入误差舍入误差 对于整数规划问题，可以先去掉整数限制来求解相应的松弛问题，找出松弛问题的最优解，然后将这个松弛问题的最优解舍入成整数(与它相邻的 2n 个整数点)，或者求最靠近它的那个可行整数解，对它们进行枚举。但是，这些都不能保证得到整数规划问题的最优解，甚至不是可行解。 另外，用穷举法对与它相邻的 2n 个整数点进行考察，当 n 较大时也是不可行的。 例 3.3.3 求解整数规划问题 (P) (P)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） xi 0,

18、 1, 2, 解解：将整数规划问题 (P) 去掉整数限制后得到如下的松弛问题 (P0)： (P0)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） 求解线性规划问题 (P0)，得最优解 x1 = 2.25，x2 = 3.75，最优值 z = 41.25。(P0) 的可行域如图 3.3.5 中阴影部分，最优解在 P 点取到，图中圆点为整数点，阴影中的圆点为 (P) 的可行解。 将 x1 = 2.25 和 x2 = 3.75 舍入成整数(与 P 相邻的 2n = 4 个整数点)，或者找最靠近它的那个可行整数解，有 (P0) 的最优解 (2

19、.25, 3.75)，z = 41.25(P0) 的舍入解(2, 3)z = 34(可行解)(3, 3)z = 39(可行解)(2, 4)z = 42(不可行解)(3, 4)z = 47(不可行解)最靠近 (P0) 的那个可行整数解 (2, 3)，z = 34最靠近 (2.25, 3.75) 的整数解为 (2, 4)，但不可行(P) 的最优解 (0, 5)，z = 40 提示提示：从理论上来讲，舍入凑整法是不能用来求解整数规划问题的，上述的例 3.3.3 也说明了这一点。 然而，在实践中，不必把整数规划与普通的线性规划界限划得太清。因为在许多实际问题中，模型的建立本身就包含了一些不确定因素，同

20、时常常也允许近似的或粗略的结果。因此，舍入凑整法在实践中经常是有用的。 但要注意，需要大致验证是否可行解。3.4 求解整数规划的蒙特卡洛方法求解整数规划的蒙特卡洛方法 在3.4 中介绍的分枝定界方法，算法的每一个计算步骤都是固定的，而且可以保证求得最优解。 但是，当整数线性规划的决策变量数目很大时，分枝定界法的代价可能是巨大的；特别是当整数规划本身是非线性的时候，尚未有一种成熟而有效的求解方法，因为非线性规划本身的通用有效解法尚未找到。 然而，由于整数规划解的数目是有限的，于是为枚举法提供了方便。当然，当决策变量数目很大、取值范围很宽情况下，企图用完全搜索(即穷举法)计算出最优值是不现实的，但

21、是应用蒙特卡洛算法，在一定的计算量下，完全可以得出一个满意解。 例 3.4.1 已知非线性整数规划为：max s.t.Z = x12 x22 3x32 4x42 2x52 8x1 2x2 3x3 x4 2x5x1 x2 x3 x4 x5 400 x1 2x2 2x3 x4 6x5 800 2x1 x2 6x3 200 x3 x4 5x5 2005x1 9x2 45 0 xi 99，i = 1, 2, 3, 4, 5 对该问题，目前尚无有效方法求出准确的最优解。如果用穷举法(完全搜索)试探，共需计算1005 = 1010 个点，计算量非常大。 然而概率理论能够保证，应用蒙特卡洛方法随机计算106

22、个点，便可找到问题的满意解，而且时间代价非常小(运行 Matlab 程序不到 30 秒)。 解解：用蒙特卡洛方法求解这个问题必须借助计算机来实现。 首先编写 M 文件 mente.m 定义目标函数 f 和约束向量函数 g，程序如下： 其次，编写主程序求问题的解。 由于是随机搜索，故运行程序 10 次，可得如下表所示的结果：106运行程序最优解最优值时间第一次运行 x = (1, 3, 30, 97, 10)T 4032526.5s第二次运行 x = (1, 2, 23, 99, 6)T4067626.3s第三次运行 x = (7, 0, 21, 98, 9)T3971526.6s第四次运行 x

23、 = (6, 1, 24, 99, 3)T4076026.5s第五次运行 x = (1, 4, 23, 97, 4)T3908226.6s第六次运行 x = (2, 2, 18, 99, 4)T4003526.6s第七次运行 x = (3, 3, 27, 99, 12)T4146326.4s第八次运行 x = (2, 0, 4, 98, 19)T3902626.3s第九次运行 x = (5, 1, 30, 99, 3)T4171126.5s第十次运行 x = (4, 2, 27, 99, 9)T4133926.7s 注注：蒙特卡洛(Monte Carlo)算法是一种随机搜索算法，它允许算法在执

24、行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时，因此蒙特卡洛算法可在很大程度上降低算法的复杂度。但另一方面，同一实例用蒙特卡洛算法求解两次可能得到完全不同的结果，也就是说，用蒙特卡洛算法能够求得问题的一个解，但无法判断这个解是否正确，求得正确解的概率依赖于算法所用的时间，算法所用的时间越多，得到正确解的概率就越高。 3.5 范例范例招聘计划招聘计划 招聘计划招聘计划：一家保姆服务公司专门向顾主提供保姆服务。根据估计，下一年的需求是：春季 6000 人日，夏季 7500 人日，秋季 5500 人日，冬季 9000 人日。公司新招聘的保姆

25、必须经过 5 天的培训才能上岗，每个保姆每季度工作(新保姆包括培训)65 天。保姆从该公司而不是从顾主那里得到报酬，每人每月工资 3000 元。春季开始时公司拥有 120 名保姆，在每个季度结束后，将有 15% 的保姆自动离职。 (1) 如果公司不允许解雇保姆，请你为公司制定下一年的招聘计划；哪些季度需求的增加不影响招聘计划？可以增加多少？ (2) 如果公司在每个季度结束后允许解雇保姆，请为公司制定下一年的招聘计划。 解解：问题(1)的求解 设 4 个季度开始时公司新招聘的保姆数分别为 x1, x2, x3, x4 人，4 个季度开始时保姆总数量分别为 S1, S2, S3, S4 人。 以本

26、年度付出的总报酬最少(即 4 个季度开始时保姆总数量之和最小)为目标，则问题的数学模型为 min Z = S1 + S2 + S3 + S4 s.t. 65S1 6000 + 5x1 65S2 7500 + 5x2 65S3 5500 + 5x3 65S4 9000 + 5x4 S1 = 120 + x1 S2 = 0.85S1 + x2 S3 = 0.85S2 + x3 S4 = 0.85S3 + x4 x1, x2, x3, x4, S1, S2, S3, S4Z + 各季度的服务需求 各季度初的储备量 虽然模型要求 x1, x2, x3, x4, S1, S2, S3, S4 为正整数，

27、但因为保姆数量较大，加之非整数因子 0.85 的影响，因此可以近似看作实数来处理。 其次，下一年各季度保姆服务的需求只是估计值，什么样的数学解都无法作为实际问题的精确解。 因此，采用舍入凑整的方法来求解。 将上述整数规划模型松弛成线性规划模型，用 Matlab 求解得： 对上述结果取整，4 个季度开始时公司新招聘的保姆数量分别为 0, 15, 0, 59 人，每个季度开始时保姆总数量分别为 120, 117, 99, 143 人。 x1 = 0.0000S1 = 120.0000 x2 = 14.5000S2 = 116.5000 x3 = 0.0000S3 = 99.0250 x4 = 58

28、.8145S4 = 142.9857 将上述取整得到的整数解带入各季度服务需求的约束条件65S1 6000 + 5x1, 65S2 7500 + 5x265S3 5500 + 5x3, 65S4 9000 + 5x4有65S1 5x1 = 7800 600065S2 5x2 = 7530 750065S3 5x3 = 6435 550065S4 5x4 = 9000 9000满足服务需求 再带入各季度初储备要求的约束条件 S1 = 120 + x1, S2 = 0.85S1 + x2 S3 = 0.85S2 + x3, S4 = 0.85S3 + x4有 S1 x1 = 120 S2 0.85

29、S1 x2 = 0 S3 0.85S2 x3 = 0.45 S4 0.85S3 x4 = 0.15虽不满足储备需求，但基本不影响制定招聘计划。 于是，这个招聘问题的解为： x1 = 0, x2 = 15, x3 = 0, x4 = 59 S1 = 120, S2 = 117, S3 = 99, S4 = 143相应的最优值为：Z = S1 + S2 + S3 + S4 = 479 因此，公司可以拟定如下的招聘计划： 第二季度开始时公司新招聘 15 人，第四季度开始时公司新招聘 59 人。 接下来讨论哪些季度需求的增加不会影响招聘计划。 由于春季开始时公司拥有 S1 = 120 名保姆，且春季开

30、始时公司招聘的保姆数量为 x1 = 0，因此，根据约束条件 65S1 6000 + 5x1 知，春季需求的增加不影响招聘计划，且可以增加65S1 6000 = 1800(人日) 类似地，夏季和秋季需求的增加也不影响招聘计划，且可以增加 30 和 935(人日)。 问题(2)的求解 设 4 个季度开始时公司新招聘的保姆数分别为 x1, x2, x3, x4 人，4 个季度结束时公司解雇的保姆数分别为 y1, y2, y3, y4 人，4 个季度开始时保姆总数量分别为 S1, S2, S3, S4 人。 以本年度付出的总报酬最少(即 4 个季度开始时保姆总数量之和最小)为目标，则问题的数学模型为

31、min Z = S1 + S2 + S3 + S4 s.t. 65S1 6000 + 5x1 65S2 7500 + 5x2 65S3 5500 + 5x3 65S4 9000 + 5x4 S1 = 120 + x1 S2 = 0.85S1 + x2 y1 S3 = 0.85S2 + x3 y2 S4 = 0.85S3 + x4 y3 xi, yi, SiZ +, i = 1, 2, 3, 4 将上述整数规划模型松弛成线性规划模型，用 Matlab 求解得： 对上述结果取整有：x1 = 0.0000S1 = 120.0000y1 = 0.0000 x2 = 14.5000S2 = 116.50

32、00y2 = 14.4096x3 = 0.0000S3 = 84.6154y3 = 0.0000 x4 = 72.0833S4 = 144.0064x1 = 0 x2 = 15x3 = 0 x4 = 72S1 = 120S2 = 117S3 = 85S4 = 144y1 = 0y2 = 15y3 = 0 将上述取整得到的整数解带入服务需求的约束条件65S1 6000 + 5x1, 65S2 7500 + 5x265S3 5500 + 5x3, 65S4 9000 + 5x4有65S1 5x1 = 7800 600065S2 5x2 = 7530 750065S3 5x3 = 5525 5500

33、65S4 5x4 = 9000 9000满足服务需求 再带入各季度初储备要求的约束条件 S1 = 120 + x1, S2 = 0.85S1 + x2 y1 S3 = 0.85S2 + x3 y2, S4 = 0.85S3 + x4 y3有 S1 x1 = 120 S2 0.85S1 x2 + y1 = 0 S3 0.85S2 x3 + y2 = 0.45 S4 0.85S3 x4 + y3 = 0.25虽不满足储备需求，但基本不影响制定招聘计划。 于是，这个招聘问题的解为： x1 = 0, x2 = 15, x3 = 0, x4 = 72 S1 = 120, S2 = 117, S3 = 8

34、5, S4 = 144 y1 = 0, y2 = 15, y3 = 0相应的最优值为：Z = S1 + S2 + S3 + S4 = 466 因此，公司可以拟定如下的招聘计划： 第二季度开始时公司新招聘 15 人，第二季度结束时解雇 15 人；第四季度开始时公司新招聘 72 人。 此时，目标函数值为 466，比不允许解雇时的目标函数值(479)略有减少。 整数规划补充范例整数规划补充范例合理下料问题合理下料问题 钢管零售商所进的原料钢管长度都是 19m。销售时零售商需要按照客户的要求进行切割。 现有一客户需要 50 根长 4m、20 根长 6m 和 15 根长 8m 的钢管。应如何下料最节省？

35、 问题分析问题分析 对于下料问题，首先要确定采用哪些可行的切割模式。所谓切割模式切割模式，是指按照顾客要求的长度在原料钢管上安排切割的一种组合。 例如，我们可以将 19m 的钢管切割成 3 根长4m 的钢管，余料为 7m；或者可以将长 19m 的钢管切割成长 4m、6m 和 8m 的钢管各 1 根，余料为 1m； 显然，可行的切割模式是很多的。 其次，应当明确哪些切割模式是合理的。合理的切割模式应该要求余料小于客户需要钢管的最小尺寸 4m。 例如，可以将长 19m 的钢管切割成 3 根 4m 的钢管是可行的，但余料为 7m，可进一步将 7m 的余料切割成 4m 钢管(余料为 3m)，或者将 7

36、m 的余料切割成 6m 钢管(余料为 1m) 经过简单的计算可知，问题(1)的合理切割模式一共有 7 种，如表 1 所示： 表 1 问题(1)的合理切割模式模式4m 钢管根数6m 钢管根数8m 钢管根数余料/m14003231013201341203511116030170023 于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式，每种模式切割多少根原料钢管最为节省。 而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。 下面将对这两个目标分别讨论。 建立模型及求解建立模型及求解 用 xi 表示按照表 1 第 i 种模式(i = 1, 2, , 7)

37、切割的原料钢管的根数，若以切割后剩余的总余料量最小为目标，则按照表 1 最后一列可得 min Z1 = 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 若以切割原料钢管的总根数最少为目标，则有min Z2 = x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件为客户的需求，按照表 1 应有 4x1 + 3x2 + 2x3 + x4 + x5 50 x2 + 2x4 + x5 + 3x6 20 x3 + x5 + 2x7 15 最后，切割的原料钢管的根数 xi 显然应当是非负整数(用 Z 表示整数集合，Z+ 表示非负整数集合)xiZ+, i =

38、1, 2, , 7 于是，问题(1)的数学模型为： 模型 1： 模型 2：7 , , 2 , 1 ,152203250234s.t. 3333min75365425432176543211ixxxxxxxxxxxxxxxxxxxxZiZ7 , , 2 , 1 ,152203250234s.t. min75365425432176543212ixxxxxxxxxxxxxxxxxxxxZiZ 这两个模型均是整数规划模型。首先将原问题松弛为线性规划问题，求解后再取整。 应用 Matlab 求解模型 1，得最优整数解为： x1 = 0, x2 = 12, x3 = 0, x4 = 0 x5 = 15,

39、 x6 = 0, x7 = 0最优值为：Z = 27。 将上述整数解带入约束条件验证，满足约束条件的要求。 应用 Matlab 求解模型 2，得最优整数解为： x1 = 2, x2 = 9, x3 = 1, x4 = 0 x5 = 11, x6 = 0, x7 = 1得最优值为：Z = 24。 将上述整数解带入约束条件验证，不满足约束条件的要求： 4x1 + 3x2 + 2x3 + x4 + x5 = 48 50 x2 + 2x4 + x5 + 3x6 = 20 20 x3 + x5 + 2x7 = 14 15需要调整需要调整 由于缺少 2 根 4m 和 1 根 8m 的钢管，它们的总长为 16m，故再增加一个模式 3(即2, 0, 1)给出的切割