第6章-整数规划-课件

管理运筹学

——模型与方法1ppt课件第6章

整数规划6.1

一般模型6.2

一般解法6.3

0-1规划6.4指派模型22ppt课件在整数规划（IP，整数线性规划）中:如果所有的变量都为整数，则称为纯整数规划问题；如果所有的变量都为0-1变量，则称之为0-1规划。如果只有一部分变量为整数，则称之为混合整数规划问题。求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。3

6.1

一般模型3ppt课件例6-1生产计划问题

4ppt课件例6-2设备购置问题5ppt课件例6-3（5-4）任务分配问题某学院安排3名教师为4门课程任教。学院希望完成这些授课任务所消耗的工作量达到最小，且三位老师的负荷尽量均衡，则应如何安排？ABCD课时系数甲√√√5乙√√√6丙√√8学分1.5223学时24323248门次45346ppt课件分支定界法（BBM）割平面法（CPA）

6.2

一般解法7ppt课件8性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。8ppt课件分枝定界法

分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。先求解整数规划的线性规划问题(伴随LP)。如果其最优解不符合整数条件，则求出整数规划的上下界。增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝）再求解这些子区域上的线性规划问题。不断缩小整数规划上下界的距离，最后得整数规划的最优解。9ppt课件10

用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：

第一步：求解问题B，可得以下情况之一：

1.B没有可行解，则A也没有可行解，求解过程停止。

2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。

3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。

第二步：确定A的最优目标函数值z*的上下界，其上界即为z1,=z1,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。

第三步：判断

是否等于z

。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。10ppt课件

第四步：在B的最优解中任选一个（或最远离整数要求的变量），不妨设此变量为xj，以[bj]表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。xj

≤[bj]和xj

≥[bj]+1

第五步：求解B1和B2

。修改A问题的最优目标函数值z*的上下界，

和z。

第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打Х表示），即以后不再考虑了。若大于

，则不符合整数条件，则重复第三步至第六步，直至

=z，求出最优解为止。

对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。11ppt课件例6-4（6-1）12ppt课件（1）13ppt课件14ppt课件莫高瑞割平面法割平面法，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整数解，这个条件就是Gomory约束条件。Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。15ppt课件设纯整数规划伴随LP的最优解若全为整数，则为IP的最优解。否则，若不全为整数，设第r行基变量非整。对应方程为16ppt课件将分离成一个整数与一个非负真分数之和：则有等式两边都为整数并且有17ppt课件加入松弛变量si得此式称为以r行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。

将Gomory约束加入到松弛问题(伴随LP)的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则18ppt课件cj1100基bx1x2x3x40x4205/21/211x11/217/2-1/3005/21/20例6.1例6-519ppt课件0-1规划的分支定界法引入0-1变量的实际问题①双态变量的归一化（变量）②不相容约束的归一化（约束条件）③分段线性函数的归一化（目标函数）

6.3

0-1规划20ppt课件①双态变量的归一化21ppt课件②不相容约束的归一化22ppt课件23ppt课件24ppt课件25（1）关于固定费用的问题例6.2高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。③分段线性函数的归一化（目标函数）25ppt课件26解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）。引入约束xi≤Myi

，i=1，2，3，M充分大，以保证当yi=0时，xi=0。

yi=0xi=0

这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100

xi≤Myi，i=1，2，3，M充分大

xj≥0yj

为0--1变量，i=1,2,326ppt课件（2）关于变动费用的问题27ppt课件28其它应用投资决策问题选址问题值班问题28ppt课件投资决策问题例6-91亿资金投资，6个项目选择，每个项目只能投资一次。其中，项目1、2互斥，项目3、4互斥；项目1或2是项目3、4的前提条件。该公司应如何投资？投资项目123456所需资金/百万元453146363424预期利润/百万元16112014121029ppt课件解：设xi为30ppt课件例6-10选择几个村建卫生站，使各村到卫生站的距离都不超过5km。各村之间距离见表选址问题村234567145689112435683667943465246331ppt课件例6-11某大型活动要举办6天，某接待站有3名正式工作人员，4名临时人员。每天：接待站对外开放时间为上午9点至下午5点。其间须2人同时值班，并且至少有1名正式人员。每人每次值班时间不少于2小时，每天值班的临时人员不超过2人。活动期间：临时人员不超过3次，正式人员不超过5次。其余见表值班时间表问题人员序号用人代价元/小时每人每天最多可安排值班的时间/小时第1天第2天第3天第4天第5天第6天临时人员184400262803463039403404410456040正式人员51288442261824486872048484432ppt课件指派问题也称为分配或配置问题，是资源合理配置或最优匹配问题。有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。

6.4

指派模型33ppt课件例6-12表中为所耗时间，若一种模具只交一人加工，应如何指派？

模具钳工ABCD甲46484047乙35444340丙34413943丁4745424434ppt课件如果从指派问题效率矩阵的每一行元素中分别减去（或加上）一个常数（称为该行的位势），从每一列分别减去（或加上）一个常数（称为该列的位势），得到一个新的效率矩阵，其中，则的最优解等价于的最优解，这里及均非负。定理6-1指派问题的匈牙利算法若矩阵A的元素可分成“0”与非“0”两部分，则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为独立元素）的最大个数。定理6-235ppt课件0690807434050209效率矩阵在效率矩阵中找出4个不同行不同列的数使得它们的总和最小。0001010000101000效率矩阵的变形找出4个不同行不同列的0元使得它们的和为最小0，令这些零元素对应的其余变量=0，得到最优解。一