整数线性规划_修改_

1、第六章 整数线性规划,6.1 常用整数线性规划模型,6.1.1下料问题,例题1：制造某种产品，需要A，B，C 三种轴 件，其规格与数量如下表所示。各类轴件都用 55m 长的同一种圆钢下料。若计划生产100 台机床，最少要用多少根圆钢？,依据问题，若直接以要用的圆钢数作为决策 变量,则建模变得很困难. 所以避免直接由题 意建模，先进行分析，实际问题抽象成线性 规划的数学模型经常要求进行转化。,首先考虑一根长5.5m 的圆钢截成 A，B,C 三种轴的毛坯有哪些具体下料方式。为此， 只需找出全部省料截法，如下表所示余料 的各种截法，其中1.2m 是各类轴件 长度中最短者。,一根圆钢所截各类轴件数,现

2、在问题归结为：采用上述五种截法用 多少根圆钢，才能配成100 套轴件，且 使 总下料根数最少？,设按第j 种截法下料 根。这样 就可以建立该问题的LP 模型为:,6.1.2工作人员调度的问题,例题2：某个百货商场对售货人员的需求 经过统计分析如表所示. 每个销售人员每 周连续工作5 天，然后休息2 天，每个 销售人员的周工资为100 元, 问应该如何 安排, 使聘用售货人员所需花费最少？,解 (一): 设 为星期一开始工作的人数， 为 星期二开始工作的人数， 为星期六开始 工作的人数， 为星期日开始工作的人数。 于是目标函数为：,按照每天所需售货员的人数写出约束条件，由 于除了周二和周三开始工

3、作的之外，其余都会 在周一工作，所以周一应有 个人工作, 相应的约束为,类似可得其它约束, 于是约束条件为:,从而数学模型为:,解 (二): 设 为星期一开始休息的人数， 为星期二开始休息的人数， 为星期六开 始休息的人数， 为星期日开始休息的人数。 于是目标函数为：,由于除了周日和周一开始休息的之外，其余 都会在周一工作，周一有 个人工作, 相应的约束为,类似可得其它约束, 于是约束条件为:,从而数学模型为:,6.1.3背包问题,例题 某公司正在考虑4个投资项目。投资 项目1将产生16，000元的净利润（NPV）， 项目2将产生22000元的净利润，项目3将产 生12000元的净利润， 项目

4、4将产生8000元 的净利润。每个投资项目现在都需要一定的 现金流出量：投资项目1需5000元；项目2需 7000元； 项目3需4000元；项目4需3000元。 目前可用于投资的现金为14000元。表述一 个IP， 它的解将告诉该公司如何最大化由投 资项目14获得的净利润。,解：如同LP表述那样，我们首先针对该公司必 须做出的每个决策定义一个变量。这时我们将 定义一个0-1型变量：,公司获得的总净利润(单位为千元)是:,因此公司的目标函数是:,由于最多只能投资14 000元，所以 必须满足,把目标函数和约束条件组合以后，将 得到下列0-1型IP：,像这样只有一个约束条件的IP称为背包 问题。假

5、设小王打算进行夜间徒步旅行， 小王考虑在旅途中携带 4样物品。下表 给出了每样物品的重量以及小王觉得能 够从每样物品得到的利益。,背包中物品的重量和利益,设小王的背包最多能携带14公斤的物品， 对 ，定义：,同样得到上面的模型。,例题4：修改上例的表述，把下列每个要求 考虑在内： （1）公司最多可以投资 2个投资项目。 （2)如果公司对投资项目2进行投资，那么 还必须对投资项目 1进行投资。 （3）如果公司对投资项目 2进行投资，那 么就不能对投资项目 4进行投资。,解：对（1），只需增加约束条件,（2）就 和 而言，这个要求规定， 如 ，那么 也必须等于1。 如果我们增加约束条件 那么我们考

6、虑到了第2个要求。,(3) 此时投资项目2和投资项目4只能 出现一个或者两个都不出现，因此只 需增加约束条件,6.1.4固定费用问题,例题5：固定费用IP G服装公司能够生产3种 服装：衬衣、短裤和长裤。每种服装的生产 都要求G公司具有适当类型的机器。 生产每 种服装所需要的机器将按照下列费用租用： 衬衣机器，每周200元；短裤机器，每周150 元；长裤机器，每周100元。 每种服装的生产 还需要表 2 所示数量的布料和劳动时间。每周 可以使用的劳动时间为150个小时，布料为160 平方米。 下表给出了每种服装的单位成本和 售价。表述一个可以使G公司每周利润最大的IP.,解: 如同LP表述那样

7、，我们将针对G公司 必须做出的每个决策定义一个决策变量。 显然，G公司必须决定每周应当生产多少 每种类型的服装， 因此我们定义,注意，租用机器的费用只取决于所生产服 装的类型，而与每种服装的产量无关。因 此我们就能够使用下列变量表示租用机器 的费用：,从而建立模型如下：,可依次取为：,6.1.5集合覆盖问题,(1),集合 的打包问题可表示为：,(2),集合 的划分问题可表示为：,实际问题中许多问题可表示上述三类问题。 下面看一个具体的集合覆盖问题。,例题6:设施位置集合覆盖问题 K市有6个城区（城区16）。这个市必须确 定在什么地方修建消防站。在保证至少有一 个消防站在每个城区的15分钟（行驶

8、时间） 路程内的情况下，这个市希望修建的消防站 最少。下表给出了在K市的城区之间行驶时需 要的时间（单位为分钟）。 表述一个IP，告 诉K市应当修建多少消防站以及它们所在的 位置。,解： 对城区16， 定义,于是目标函数是极小化：,下表给出了每个位置在15分钟内可到达的城区。,因此对每个位置，有约束条件：,从而整个模型为：,6.1.6二选一约束条件（either or）,下列情况通常出现在数学规划问题中。现在 提供了两个下列形式的约束条件,希望保证至少满足上述两个约束条件中的一 个约束条件，这经常称做二选一约束条件。 在表述中加人如下两个约束条件以后， 将保 证至少满足一个约束条件成立：,例题

9、7:二选一约束条件,D汽车公司正在考虑生产3种类型的汽车： 微型、中型和大型汽车。表6给出了生产 每种汽车需要的资源以及产生的利润。目 前有 6000吨钢材和 60000小时的劳动时 间。要生产一种在经济效益上可行的汽车， 这种类型的汽车至少必须生产1000辆。 表述一个可以使该公司利润最大的IP。,解: 由于D公司必须确定每种汽车应当生产 多少辆，所以我们定义 分别是微 型、中型和大型汽车的产量，因此利润 （单位为千元）就是 ， D公司的目标函数是,我们知道，如果要生产某种类型的汽车， 那么至少必须生产 1000辆。因此，对于 ，必须有 或 ， 于是可表示为：,由于钢材和劳动时间有限，因此必

10、须有：,（钢材约束条件）,（劳动时间约束条件）,注意到 为非负整数，这样便得到如下IP：,这个IP最优解是 ， ， 其它为0。因此，D公司应当生产 2000辆 中型汽车。如果不要求 D公司每种汽车至 少生产1000辆，那么最优解将是生产570 辆微型汽车和 1715辆中型汽车。,6.1.7 If-then约束条件,在许多应用中将出现下列情况：我们希望 保证，如果满足约束条件，,那么必须满足约束条件,如果没有满足,那么可以满足也可以不满足,简而言之，我们希望保证,意味着,为了确保这一点，我们将在表述中加人下 列约束条件：,6.2整数规划的基本性质,整数规划(Integer Programming

11、, 简称 IP) 的一般模型为：,其中 。 若 ，则称之为 纯整数规划问，否则称为混合整数规划问题。,上述问题也通常简记为：,其中,（1）,若去掉整数约束，上述问题就是一个连续 规划问题, 相应的数学模型为：,（2）,称之为对应IP 问题的松弛问题。 对问题(1)， 若目标与约束函数均为线性函数， 则称之为 整数线性规划。,求解一般整数规划问题 的主要方法有分枝 定界方法和割平面方法。这两个方法都基 于下面的观察： 如果在求解一个IP 的松弛 问题时得到了恰好是整数值的解, 那么这个 松弛问题的最优解也是这个IP 的最优解。 这是因为IP 的可行域是其LP 松弛问题可行 域的子集。因此，这个I

12、P 的最优值不会小于 (对min 问题) 或大于(对max 问题)松弛问题 的最优值。因此我们有如下定理：,定理 1. 1、若松弛问题(2)的解为IP问题(1)的可行解， 则该解也是原问题(1)的最优解。 2、松弛问题(2)的解对应的目标值是原问题(1) 目标值的一个下界（对max问题为一个上界）。,本章将在线性规划基础上考虑整数线性规划 问题。和线性规划一样可定义整数线性规划 的标准形式如下：,（3）,其中 表示所有n维非负整数向量构成的 集合，即：,则问题(3)也可写作 或：,整数线性规划通常要比线性规划困难得多， 将其相应的LP 松弛问题的最优 解“圆整” 来解原整数规划，虽是最容易想到

13、的， 但 常常得不到整数规划的最优解，甚至根本 不是可行解。,例题 1: 计算：,下面介绍一个代数学的基本定理，它 与整数线性规划密切相关。,证明： 必要性是显然的。下面证明 充分性， 不妨设矩阵 行满秩，,设,证明： 设无界多面体P的顶点集合为 ，极方向集合为 。 因为极方向的任何正数倍仍是极方向， 故不妨可设所有的 都是非负整数向 量。根据线性规划的 表示定理，可得：,以 记所有n维非负整数向量构成的集合，设,其中 表示不超过 的最大整数，且,由此就可推得,证毕,由于 的每一点均可写成集合 中若 干个点的凸组合，因此 的极点必属 于集合 。 而线性规划问题的最优解 必 可在极点（即基本可行

14、解）处达到，故问 题(3)的求解便可化为如下线性规划问题：,（6）,这是整数线性规划所要研究的一个 基本问题。后面的分枝定界方法和 割平面法都可看作是为解决这一基 本问题而提出的简单而有效的方法。,6.3整数规划的计算方法,整数规划(Integer Programming, 简称 IP) 的一般模型为：,通常简记为：,（7.1）,其中,为可行域,若去掉整数约束，上述问题就是一个连续 规划问题, 相应的数学模型为：,（7.2）,称之为对应IP 问题的松弛问题。 对问题 （7.1），若 ，则称之为纯 整数规划问题；否则称之为混合整数规划 问题。若目标与约束函数均为线性函数， 则称之为整数线性规划。

15、,整数规划通常要比线性规划困难得多，将其相应的LP 松弛问题的最优 解“化整” 来解原整数规划，虽是最容易想到的， 但常常得不到整数规划的最优解，甚至根本不是可行解，因此有必要对整数规划的解法进行专门研究。 求解一般整数规划问题 的主要方法是分枝定界方法， 此外还有割平面方法。,这两个方法都基于下面基本而重要的观察： 如果你在求解一个IP 的松弛问题时得到了恰好是整数值的解, 那么这个松弛问题的最优解也是这个IP 的最优解。因此，这个IP 的最优值不会小于(对min 问题) 或大于(对max 问题)松弛问题的最优值。因此我们有如下定理：,定理711： （1）若松弛问题的解为IP问题的可行解，则

16、 该解也是原问题的最优解。 （2）松弛问题的解对应的目标值是原问题 目标值的一个下界（对max问题为一个上界）。,6.3.1分枝定界方法,下面介绍求解一般整数规划问题(IP)的主要 方法分枝定界方法。 在求解整数规划时，如果可行域是有界的， 首先容易想到的方法就是穷举变量的所有 可行的整数组合，然后比较它们的目标函 数值以定出最优解：对于小型的问题, 这个方 法是可行的，也是有效的。对于大 型的问题，可行的整数 组合数是很大的， 如设某个问题有50 个0-1 整型变量, 则其可 能的解有,即使是用每秒1 亿次的计算机, 也要算上130.31 天; 若有100 个0-1 整型变量, 则要算上46

17、.52 年! 解这样的题，穷举法是不可取的。所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分枝定界解法（Branch and Bound Method）就是其中的一个。,显然 必是某个叶子节点的解，且是所有叶子节点的解中最小的。 因此分枝定界法实际上是一个穷举的过程，有可能会遇到“组合爆炸”的问题，但通过分枝、剪枝和定界过程的灵活组合，常常能在规定时间里获得满意的结果，因此分枝定界法是目前求解整数规划问题商业软件的首选方法。在求解过程中首先要解决如下两个问题：,1、在分枝的问题中先求解哪个问题？ 2、在多个 非整数的情形下，选择哪一 个变量作为分枝变量？,对第一个问

18、题，通常采用LIFO 规则，即 “后进先出(即Last In, First Out)” 的规则 依次求解子问题。另一种常用的方法是 跳跃式跟踪法。,对第二个问题，分枝经济重要性最大的 分数值变量通常是最佳策略。,例7-1：生产桌子和椅子，已知生产一个这 桌子9个单位的木材和1个单位的工时，其 利润为8元。生产一个椅子需要5个单位的 木材和1个单位的工时，其利润为5元。木 材总数为45，工时总数为6，如下表所示。,问应如何安排生产利润最大？,解：设生产餐桌和椅子的数量分别是 和 ，则数学模型为：,用作图法：,下面用“分枝定界”的方法：首先解由原问题 去掉整数约束后得到的松弛问题（称之为子 问题1

19、），得解：,即若误差不超过6%，则该解已可接受了。 由于已得到整数解，子问题2已不用分枝， 其最优解可作为候选的最优解。然后求解 子问题3，得解,这一过程如下图所示。,再解子问题5不可行，舍去，此时已穷尽所有 分枝，因此最优解就是 。 整个计算过程一共计算了七个线性规划子问题。,在使用单纯形法计算上述子问题时，可采用 前述灵敏度分析的方法。如对上述例题。 下面介绍求解背包问题的分枝定界方法。由 于背包问题只有一个约束，其松弛问题的解 可以直接得到，如对问题：,（7.5）,其中 是选择物品j的利益， 是可使用资源的量， 物品j占用的资源。其松弛问题为：,对问题7.6， 可以解释为物品j每使用 一

20、个单位资源可以获得的利益，设,(7.6),则问题(7.6)的解为,对相应的min问题，解为,此对背包问题(7.5)，对变量 ，应按 从 大到小的顺序对 从小到大编号，然后直接 按前述分枝定界方法（首先对编号最小的变 量进行分枝，并采用LIFO规则）计算即可。,实际问题中的大多数背包问题是0-1背包问题， 其模型为：,(7.7),即每种物品最多只能取一个。由于每个变量 只能取值0或1，因此对变量 进行分枝后 将直接得到两个分枝，此时分枝过程也简化 了。下面举例说明。,例：计算0-1背包问题：,解：此时变量 已按 从大到小的顺序 编好号，首先解由原问题去掉整数约束后 得到的松弛问题（称之为子问题1

21、），容易 看出其解为：,对应的目标值为,6.3.2 0-1规划的隐枚举法,一般0-1规划的数学模型为：,(7.8),对上述问题，由于变量只取0与1，因此 n个变量组合起来得到的所有可能解有 个，可用一个完全二叉树来表示，如三 个只取0与1的变量的所有可能组合可由 下面的完全二叉树来表示：,当n 很小时，可直接用枚举法解上述问题，当n很大时，可结合分枝定界方法，通过对问题的观察简化上述枚举过程，得到隐枚举法。隐枚举法经常用于求解0l型IP。 它利用每个变量都必须等于0或1，简化了分枝定界过程的分枝和定界。,在隐枚举法中使用的树中， 对于某个变量 ，树的每个分枝将规定 或1。在每个节点处，一些变量的值已经被确定，值已经被确定的那些变量称为固定变量， 在一个节点处值没有被定的所有变量都称为自由变量。对于一个节点来说，所有自由变量的取定的值称为该节点的完备值。下面描述3个在隐枚举法中使用的主要思想。,1、在一个节点处，对于固定变量在该节点的给 定值，是不是有一种容易的方法能够求出该 节点在原始0l型IP 中可行的良好完备值呢？ 要回答这个问题，我们需要完备这个节 点， 把每个自由变量设置为能够使目标函数最大或 最小的值（0或1）。如果