运筹学 第2版 课件 第三章 整数规划

JournalonComputing第三章整数规划01整数规划的导出03整数规划问题应用整数规划问题解法02CONTENTSPART01整数规划的导出整数规划的导出整数规划问题（前述线性规划问题的约束条件中对所有或部分决策变量有整数的要求，比如运输问题，网络流问题等）0-1整数规划问题整数规划的导出

在之前所学的线性规划问题中，最优解可能是整数，也可能是小数。但是在实际问题中，通常会要求求解结果必须为整数。例如，求解工件的件数、工人的个数、机器的台数，选址的个数等。

为满足此类问题整数解的要求，本章引入了整数线性规划，下面通过一些现实中的实际问题加以说明。整数规划的导出某汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量，试制定月生产计划，使工厂的利润最大。某钢管零售商从钢管厂进货，将钢管按照顾客的需求切割后售出，从钢管厂进货时，得到每根19米长度的钢管原料，现有乙客户需要50根4米，20根6米，15根8米，如何下料最省（所使用的原料根数最小）。一般整数规划整数规划的导出某背包的容积一定，现有多种物品待装，各物品的价值、体积已知，应该装入哪些物品使得在不超过背包的容量的前提下装入物品的价值最大？某物流企业在全国有多个仓储中心，拟新建n个仓储对所有分仓进行供货，现有数个地点作为被选点。应该在何处建设仓储中心使得其到所有分仓的总距离最小。0-1整数规划某投资人手头上有一定的资金，有数个可以考虑的投资项目。每个项目需要的资金，期望利润和风险已知。那么他应该如何选择投资项目才能尽可能获得更多的投资收益。

整数规划的导出0-1整数规划以上问题的特点是：变量为整数生产计划问题：汽车生产计划数量为整数；钢管下料问题：所消耗的钢管根数为整数；背包问题：对每一件物品进行取舍，装或者不装；选址问题：对每一个被选点有两种选择，在这里建或者不在这里建；投资组合问题：对每一个考虑的项目，投资或者不投资。指派问题：对每一个工人i，是否安排其做事情j。这类问题无法直接采用线性规划模型，因为线性规划的解可能包含小数部分整数规划的概念整数规划的导出

整数规划的概念整数规划的导出以上实例的整数规划模型都可以表示为以下一般形式：回顾线性规划模型的一般形式：

整数规划的概念整数规划（IP）和线性规划（LP）问题的区别：整数规划的约束条件中多一个部分或所有变量取值为整数的附加条件（在现实中当求解的问题是机器的台数，完成工作的人数时变量的取值必须整数）。整数规划问题的可行解集是所对应线性规划问题可行解集的子集。整数规划中如果所有的变数都限制为（非负）整数，就称为纯整数规划或全整数规划；如果仅一部分变数限制为整数，则成为混合整数规划。整数规划的特殊情形是0-1规划（变数取值0或1）。整数规划的导出PART02整数规划的求解整数规划的求解我们将删去变量的整数要求得到的一般线性规划问题称为整数规划的线性松弛问题，如下所示：且为整数松弛问题B整数规划问题A线性松弛问题下面给出该结论成立的一个充分条件：那当整数规划满足什么条件时，可以保证线性松弛问题的最优解就是整数解呢？整数问题的特殊情形整数规划的求解

整数规划的求解首先判断该矩阵的一阶子矩阵的行列式，即该矩阵中的每个元素是否为0，1或-1，通过观察可知所有一阶子矩阵满足以上条件。对于二阶子矩阵，可以分别求得所有结果均为1或-1；对于三阶子矩阵，该矩阵的行列式结果如下：请判断以下矩阵是否为全单模矩阵：

因此该矩阵不是全单模矩阵。整数规划的求解例1：某模具加工厂主要生产甲、乙两种产品，生产每件产品所需的劳动力工时、原材料质量、可获利润以及资源限制如下表所示。问两种产品各生产多少件，可使获得利润为最大?整数规划的求解

整数规划的求解

那么应该如何求解整数规划问题呢？可以想到的解法？整数规划的求解

所以能否找到这样的方法，仅需检查可行的整数组合的一部分，就能确定最优的整数解？分支定界解法（branchandboundmethod）就是其中的一个。整数规划的求解分支定界法(branchandbound)分枝定界法是求解整数规划的一种常用的有效方法，它既能解决纯整数规划问题，又能解决混合整数规划问题。大多数求解整数规划的商用软件都是基于分枝定界法。关键在于：分枝与定界分支定界法整数规划的求解

分支定界法分支定界法基本步骤整数规划的求解4.构造分枝：添加两个约束条件分别并入原松弛问题的约束条件中

分支定界法整数规划的求解

分支定界法整数规划的求解1.得到整数规划的松弛问题，求出整数规划松弛问题的最优解，判断得到的解是否满足整数要求，显然此时原问题有最优解，但非整数，进入下一步。分支定界法

现用分支定界法求解例1中的整数规划问题：整数规划的求解2.确定原问题的上下界分支定界法

3.分支

整数规划的求解4.定界分支定界法

整数规划的求解5.剪支分支定界法

分支定界法的计算步骤问题A

最优解

整数规划的求解分支定界法可以看成是一种改进（高效）的枚举法；主要思路：利用其松弛问题的最优解（最优值）来分支和定界；不断降低原整数规划最优值的上界，同时提高其下界，当上界等于下界时，得到最优解；当所有的子问题均被关闭或剪枝后，使目标函数值最大的整数解即为所求的最优解。分支定界法整数规划的求解

割平面法整数规划的求解割平面法以下只讨论纯整数规划的情形，现举例说明。某工厂可用A、B两种资源生产彩电和冰箱两种产品，已知生产一台彩电获利3千元，需消耗A资源2个单位，B资源2个单位；生产一台冰箱获利2千元，需消耗A资源3个单位，B资源1个单位；A资源拥有12个单位，B资源拥有9个单位，问如何根据资源情况安排生产且使工厂获利最大？

整数规划的求解割平面法如不考虑条件（5），容易求得相应的线性规划的最优解：

不符合整数条件用图解法来表示如下：12345678954321整数规划的求解割平面法现设想，如能找到像左图CD那样的直线去切割域R，去掉三角形域ACD，那么具有整数坐标的C点(4,1)就是域R′的一个极点，如在域R′上求解①~④，而得到的最优解又恰巧在C点就得到原问题的整数解。所以解法的关键就是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。如何找到这样一条直线来对原线性规划的可行域进行有效切割呢？12345654321整数规划的求解割平面法

不考虑条件⑤，用单纯形表解题，见下表。

3200

初始计算表012231009210103200最终计算表315/410-1/43/423/2011/2-1/2-57/400-1/4-5/2整数规划的求解割平面法从最终计算表中，得到非整数的最优解:

该最优解不能满足整数最优解的要求。考虑其中的非整数变量，可以从最终计算表中得到相应的关系式。

整数规划的求解割平面法将系数和常数项都分解成整数和非负真分数之和

将整数部分与分数部分分开，分别移到等式的左端与右端，化简后得

其中[A]表示小于等于A的最大整数。整数规划的求解割平面法

即

整数规划的求解割平面法将这新的约束方程加到原最终计算表，如下。

32000315/410-1/43/4023/2011/2-1/200-100-1-11-57/400-1/4-5/20整数规划的求解割平面法将这新的约束方程加到原最终计算表，如下。

32000315/410-1/43/4023/2011/2-1/20010011-1-57/200-1/4-5/20整数规划的求解割平面法

11000341001-1/421010-11/2010011-1-14000-1-1/4由上表可得到以下最优解：

整数规划的求解割平面法求一个切割方程归纳为以下几个步骤:

（2）根据Gomory方法对上式进行变换得到以下关系式：

其中[A]表示小于等于A的最大整数。整数规划的求解割平面法将整数项与分数项分别移至等式的两端，得到以下关系式：

这就是一个原问题可行域的一个切割方程。整数规划的求解割平面法由以上分析可知：（1）以下切割方程真正进行了切割，至少把非整数最优解这一点割掉了。（2）没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足以上切割方程的缘故。Gomory切割法自1958年被提出后，即引起人们广泛的注意。但至今完全用它解题的仍是少数，原因就是经常遇到收敛很慢的情形。但若和其他方法（如分枝定界法）配合使用，也是有效的。

整数规划的求解割平面法以下只讨论纯整数规划的情形，现举例说明。

如不考虑条件（5），容易求得相应的线性规划的最优解：

不符合整数条件整数规划的求解割平面法用图解法来表示如下：1234567896543219整数规划的求解割平面法现设想，如能找到像左图CD那样的直线去切割域R，去掉三角形域ACD，那么具有整数坐标的C点(1,1)就是域R′的一个极点，如在域R′上求解①~④，而得到的最优解又恰巧在C点就得到原问题的整数解。所以解法的关键就是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。9如何找到这样一条直线来对原线性规划的可行域进行有效切割呢？整数规划的求解割平面法

不考虑条件⑤，用单纯形表解题，见下表。

1100

初始计算表01-111004310101100最终计算表13/410-1/41/417/4013/41/4-5/200-1/2-1/2整数规划的求解割平面法从最终计算表中，得到非整数的最优解:

该最优解不能满足整数最优解的要求。考虑其中的非整数变量，可以从最终计算表中得到相应的关系式。

整数规划的求解割平面法将系数和常数项都分解成整数和非负真分数之和

将整数部分与分数部分分开，分别移到等式的左端与右端，化简后得

其中[A]表示小于等于A的最大整数。整数规划的求解割平面法

即

整数规划的求解割平面法将这新的约束方程加到原最终计算表，如下。

1100013/410-1/41/4017/4013/41/400-300-3-11-5/200-1/2-1/20整数规划的求解割平面法

11000111001/3-1/121101001/4010011/3-1/3-2000-1/3-1/6由上表可得到以下最优解：

PART03整数规划问题的应用0-1型整数规划

整数规划问题的应用1.指派问题在实际工作中，管理部门经常遇到这样一些问题，需要把n项任务指派给n个员工完成。由于员工熟练度和特长不同，各员工完成各项任务的时间也有所差异。如何把n项任务分配给n个员工（每项任务交给一个对象完成，每个对象也只能完成一种任务），使得完成n项任务的总效率最高（或者总消耗最少），这类问题被称为指派问题或分派问题。

由此可以建立指派问题的数学模型如下：

整数规划问题的应用指派问题的特征任何指派问题都可以下面的形式表述：给定一系列所要完成的任务以及一系列完成任务的被指派者，所需解决的问题就是要确定出哪一个人被指派进行哪一项任务。指派问题模型的假设：1、被指派者的数量与任务的数量相同；2、每一个被指派者只完成一项任务；3、每一项任务只能由一个被指派者来完成；4、每一个被指派者和每一项任务的组合都会有一个相关的成本；5、问题的目标是确定怎样进行指派才能使总成本最小。整数规划问题的应用1.指派问题例2：某地产公司计划在城中心老城改造区域建设4个住宅小区，分别是甲、乙、丙、丁，由4家与该公司长期合作的建筑公司A、B、C、D进行投标，为了保证建设质量，要求每家建设公司必须完成且只完成一个小区的建设任务，它们完成每项任务的建设工期（月）如下表所示，问该地产公司应如何分配任务，可以使完成所有建设任务的总工时耗费最少？整数规划问题的应用

ABCD甲7598乙912711丙8546丁73791.指派问题整数规划问题的应用

整数规划问题的应用指派问题的变形指它们不满足模型假设中一个或多个条件：1、目标函数最大化的指派问题2、任务比指派者多，所以某些任务并未得到执行；3、指派者比要完成的任务多，其中某些被指派者没有任务；4、每个被指派者可以同时被指派不止一项任务；5、每一项任务都可由多个被指派者共同完成。6、有一些被指派者并不能完成有一些任务；1.指派问题1.指派问题例3：某科技公司每年都会接收一批实习生，以培养未来的技术人才。今年，公司决定接收5名计算机科学专业的实习生。公司有4个不同的技术部门：软件开发部、数据分析部、人工智能部和网络安全部，软件开发部需要2名实习生，数据分析部需要1名，人工智能部需要1名，网络安全部需要1名。由于每个实习生的技能特长有所不同，所以他们在不同的部门能够发挥的价值也不尽相同，每个部门对实习生的数量需求不同。公司希望实习生能够充分利用他们的专业技能创造最大价值，同时满足各部门的需求，请问应该如何进行分配？整数规划问题的应用实习生软件开发部数据分析部人工智能部网络安全部18356247293658347642593711.指派问题整数规划问题的应用

根据指派问题的数学模型，可将该问题表示为以下形式：

1.指派问题若这一批的实习生中的实习生1和实习生2只能从事软件开发和数据分析的工作，而其他实习生则是“多面手”，可以从事所有部门的工作内容，此时又应该如何分配？整数规划问题的应用

该问题表示为以下形式：

1.指派问题若由于公司预算限制，最后只挑选了3名实习生1,2,3，且此时各个部门最多只需要1名实习生，此时又应该如何分配？整数规划问题的应用

该问题表示为以下形式：

1.指派问题整数规划问题的应用那么应该如何求解指派问题呢？

指派问题是整数规划的特例，也是0-1型整数规划的特例；当然可以用分支定界法，割平面法等一般解法进行手动求解，但这是不合算的，结合指派问题的特点可以用匈牙利法求解，这种方法相对于上述解法往往更加简便快捷，感兴趣的同学可以自行了解。

整数规划问题的应用2.背包问题

具有以上形式的整数规划问题称为背包问题，其中第1个约束条件称为背包约束，第2个约束条件定义了0-1变量，这是一个最简单的背包问题，因为该问题中仅有背包总重量的限制，我们也称这种只有一个限制条件的背包问题称为一维背包问题。例4：一位旅行者即将开始一次为期一周的旅行，他需要从一系列物品中选择一些放入他的背包。每个物品都有其重量和价值，而背包的总重量限制为10公斤。旅行者希望在不超过重量限制的情况下，最大化他所携带物品的总价值，请问应该如何选择所携带的物品？整数规划问题的应用2.背包问题物品重量价值13452230346041155580整数规划问题的应用2.背包问题

则该问题的数学模型可以表示为：

整数规划问题的应用2.背包问题

例5：一位旅行者即将开始一次为期一周的旅行，他需要从一系列物品中选择一些放入他的背包。每个物品都有其重量，体积和价值，而背包的总重量限制为10公斤，体积限制为15立方分米。旅行者希望在不超过重量和体积限制的情况下，最大化他所携带物品的总价值，请问应该如何选择所携带的物品？整数规划问题的应用2.背包问题物品重量（公斤）价值1324522530341604121555380整数规划问题的应用2.背包问题

则该问题的数学模型可以表示为：重量限制体积限制

整数规划问题的应用3.选址问题

整数规划问题的应用3.选址问题

结合销售中心选择的约束条件与利润最大化的目标，原问题的数学模型可表示为：

项目的投资总额不超过𝐵万元各个地区城市选择的要求区域划分问题通常表示为如何划定若干个服务点各自的服务区域，使得在满足特定的要求和约束条件的前提下，总成本最小。其中可以用0-1整数决策变量来表示每个服务区域是否属于某个服务点，约束条件可以包括所有服务区域只能划分至一个服务点，服务点的服务能力限制、对服务区域相邻性要求等。整数规划问题的应用4.区域划分与覆盖问题例7：某市高新区准备新设立三所中学，同时需要为每所学校重新划定服务区域，初步规划中，该高新区被分成了人口大致相同的6个区域。下表给出了每所学校与每一个区域之间的近似距离、明年每一个区域的高中生数量以及每所学校所能够安排的最少和最多的学生数量。另外为了使学生在学校间分布相对均衡，管理者要求每个学校都只能接收2个区域的学生。那么高新区管理者应该如何划分每所学校的服务区域，可以使得在满足学校招生人数约束的前提下，每个区域到学校的总距离最短。

学校123学生数量区域

13.53.04.060022.22.12.7120030.82.91.890044.31.12.4100052.91.91.380062.42.71.1900最小招生人数150020001500

最大招生人数200024001800

整数规划问题的应用4.区域划分与覆盖问题整数规划问题的应用

4.区域划分与覆盖问题整数规划问题的应用每个区域只能被划分至一所学校每所学校只能为两个区域提供教学服务分配到每所学校的人数不能低于该学校的最小招生人数，也不能高于最大招生人数。4.区域划分与覆盖问题例8：某快递公司为了提高当地快递配送服务水平，准备修建若干个快递服务站，通过考察筛选出了五个不同的备建地址。表1是每个备建服务站能够覆盖的社区以及建设费用，表2是每个社区的居民人数。现有预算500万元，为了覆盖社区中尽可能多的人，请给出最合适的建设方案。整数规划问题的应用4.区域划分与覆盖问题1107628341953245整数规划问题的应用

结合题中覆盖居民人数最高这一目标，以及每个快递服务站所划分社区情况与建设总费用的约束条件，可建立该问题的约束条件如下：

4.区域划分与覆盖问题整数规划问题的应用该约束表示若地点4和5中至少选择1处，则可以为社区1提供服务；否则，社区1则无法得到快递服务建设资金预算限制覆盖居民人数最大的目标4.区域划分与覆盖问题判断其他社区能否得到快递服务的约束条件例9：某学校规定，管理学专业的学生毕业时必须至少学习过2门数学课、3门经济学课和2门计算机课。这些课程的编号、名称、学分、所属类别、先修课要求如表所示。问毕业时学生最少可以学习这些课程中的哪些课程？整数规划问题的应用5.选课问题编号课程名称学分所属类别先修课要求1经济数学5数学2数理统计4数学、经济学3微观经济学4数学、经济学经济数学、数理统计4数据结构3数学、计算机计算机程序设计5计量经济学4数学、经济学经济数学、数理统计6电子商务3计算机、经济学计算机程序设计7计算机程序设计2计算机8宏观经济学2经济学微观经济学9经济模型建立3经济学、计算机经济数学、数理统计整数规划问题的应用

结合选修课程数最少这一目标，以及选修各类型课程数量要求与先修课程要求的约束，该问题可表示为：5.选课问题整数规划问题的应用

选修各类型课程数量要求

5.选课问题

整数规划问题的应用6.投资问题例10：某部门准备利用现有的资金10万元在今后五年内进行投资，目前主要有以下的4种投资项目方案：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利110%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末回收本利125%，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末回收本利130%，但规定其投资额只能为2万元、4万元、6万元三种金额的其中一种；项目D：五年内每年初可购买公债，于当年末归还，并加利息5%，此项投资金额不限。问应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大？整数规划问题的应用6.投资问题整数规划问题的应用

6.投资问题整数规划问题的应用为了获得更大的投资收益，该公司应该在每年年初将所持有的所有资金（初始本金或上一年末的本息和）都投入到各个项目当中，且所投总金额不能超过所持总金额，另外对于每个项目的投资金额需要在规定的区间之内，结合第五年末的持有本利总额最大化的目标，可建立该问题的数学模型如下:每一年对每个投资项目的决策变量设置如下表：

第一年第二年第三年第四年第五年A

B

C

D6.投资问题整数规划问题的应用

若选择投资，第1年初对项目A的投资金额不低于4万元，不高于10万元6.投资问题第1年年初将初始资金全部投到项目A或D第2年年初将上一年投资D的本息和全部投到项目A，C或D第3年年初将以前投资A和D本息和全部投到项目A，B或D第5年年初将以前投资A和D本息和全部投到项目D若选择投资，第3年对项目B的投资金额不低于3万元，不高于5万元若选择投资，第2年对项目C的投资金额投资额只能为2万元、4万元、6万元

整数规划问题的应用7.选址及运输问题

年生产能力（吨）29345006358800436280045361200年需求量（吨）1000500800700整数规划问题的应用7.选址及运输问题

整数规划问题的应用

7.选址及运输问题年需求量要求已有工厂生产能力限制新设工厂生产能力限制

整数规划问题的应用7.选址及运输问题整数规划问题的应用

结合总成本（固定成本与供应成本之和）最低这一目标，以及仓库的供应能力限制与各商店的供应需求，于是问题可表示为：

7.选址及运输问题总成本（固定成本与供应成本之和）最低的目标表示任意商店必须被供应表示仓库供应能力不能超过其最大供应能力表示如果商店i被仓库j供应，则仓库j必定被建立。

整数规划问题的应用8.生产计划问题例13：某制造公司的主营业务是为重型建筑设备组装柴油发动机，根据销售部门与市场部门的预测，在接下来的4个季度中公司分别需要组装并运输40，20，60和15台发动机，但在现有的生产条件下，每个季度最多能组装50台发动机且每次生产线启动时都需要12000元的固定成本，已知每台发动机的装配成本为1200元，发动机可以存放在工厂的仓库中，每台的库存成本为600元每季度。请问该公司应该如何制定4个季度的生产和组装计划才能使得总成本最小，假设开始和结束时都