《运筹学-整数规划.ppt》由会员分享，可在线阅读，更多相关《运筹学-整数规划.ppt（54页珍藏版）》请在三一办公上搜索。
1、第四章整数规划,基本要求：了解整数规划决策问题的特点熟悉分枝定界法和割平面法的原理及其应用理解0-1规划及其求解方法隐枚举法掌握指派问题及其求解方法匈牙利法,第一节整数规划问题的提出,一、什么是整数规划问题决策变量要求取整数的线性规划叫做整数规划（Integer Programming），简称IP。,二、整数规划的分类纯整数规划：整数规划中如果所有的决策变量都限制为（非负）整数，称为纯整数规划或称为全整数规划。混合整数规划：整数规划中如果仅有一部分决策变量限制为（非负）整数，则称为混合整数规划。0-1规划：整数规划中如果决策变量取值仅限0或1，则称为0-1规划。,第一节整数规划问题的提出,例：
2、某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai(i=1,2,7)可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪个点可使年利润最大？,建模如下：,第一节整数规划问题的提出,第一节整数规划问题的提出,例.某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如右表所示。问两种货物各托运多少箱，可使获得利润为最大？,解：设甲、乙两种货物的托运箱数分别为x1,x2。建模如下：,第一
3、节整数规划问题的提出,整数规划的松弛问题,解得：最优解：X=（4.8,0）T最优值：Z=96,X(1)=(5,0)TX(2)=(4,0)T,(4,1),第一节整数规划问题的提出,整数规划与其松弛问题之间的关系,整数规划问题的可行域是它的松弛问题可行域的一个子集；整数规划问题的最优值（最优解对应的目标函数值）不会优于它的松弛问题的最优值；对松弛问题的最优解中不符合整数要求的分量简单地取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。,第二节分枝定界法,第二节分枝定界法,例：用分枝定界法求解下面问题,x14,x15,x22,x23,x21,x22,图解法,x2,x1
4、,0,4,5,2,3,1,4,3,2,1,6,5,6,7,8,7,8,9,10,第二节分枝定界法,第二节分枝定界法,第二节分枝定界法,第二节分枝定界法,用分枝定界法解下列问题：,x13,x14,x23,x22,x22,x23,第三节割平面法,一、什么是割平面法（基本思想）先不考虑变量的整数限制，求解其对应的线性规划问题。如果得到的解不是整数解，则不断增加适当的约束，割掉原可行域中不含整数解的一部分，最终得到一个具有若干整数顶点的可行域，而这些顶点中恰有一个顶点是原问题的最优整数解。步骤1：不考虑变量的整数限制，求解相应的线性规划问题，如果该问题无可行解或最优解已是整数解，则停止计算，否则转入一
5、下步；步骤2：对上述线性规划问题的可行域进行“切割”，去掉不含整数解的一部分可行域，即增加适当的约束条件（Gomory约束），然后转入步骤1。,第三节割平面法,二、Gomory约束的求解步骤：1、设xi是相应线性规划最优解中一个不是整数的基变量，将最终单纯形表中该基变量对应的行还原成约束方程。即其中iQ(Q指构成基变量下标的集合)kK(K指构成非基变量下标的集合),第三节割平面法,2、将bi和aik都分解成整数部分N与非负真分数f之和,即bi=Ni+fi，其中0fi1 aik=Nik+fik，其中0fik1代入（1）式得由于变量有整数的限制，所以上式左边必为整数。则右边也应该是整数，但由于0f
6、i1，所以不能为正，即,第三节割平面法,例：用割平面法求解下列问题,第三节割平面法,初始单纯形表,最终单纯形表,第三节割平面法,第三节割平面法,3/4(3/4x3+1/4x4)0,-3/4x3-1/4x4+x5=-3/4,O,x1,x2,1,2,3,4,1,2,3,4,A,B,第四节0-1整数规划,决策变量只能取0或1的整数规划，叫做0-1整数规划。决策变量称为0-1变量(二进制变量、逻辑变量)。0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。,一、什么是0-1整数规划,第四节0-1整数规划,1、投资场所的选定相互排斥的计划例：某公司拟在市东、西、南
7、三区建立门市部，拟议中有7个位置Ai(i=1,2,7)可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪个点可使年利润最大？,0-1规划的实际问题：,建模如下：,st.,第四节0-1整数规划,2、相互排斥的约束条件例：本章例1中，关于货运的体积限制为5x1+4x224(车)。今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为7x1+3x245(船)。（这两条件是互相排斥
8、的）,例1.某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如右表所示。问两种货物各托运多少箱，可使获得利润为最大？,解：设甲、乙两种货物的托运箱数分别为x1,x2。,设变量y表示运货的方式，当y为1时，用车运，y为0时，用船运。,+(1-y)M,+yM,第四节0-1整数规划,二、0-1整数规划的解法,隐枚举法：只检查变量取值的组合的一部分的方法。,(0,0,0),0,Z0,(0,0,1),5,Z5,(0,1,0),-2,(0,1,1),3,(1,0,0),3,Z8,(1,0,1),(1,1,0),8,1,(1,1,1),6,按目标函数中各变量系数的大小重新排列各变
9、量最大化问题：由小到大最小化问题：由大到小,第五节指派问题,一、什么是指派问题,某单位需完成任务n项任务，恰好有n个人可承担这些任务，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。这类问题称为指派问题(分派问题、分配问题),人,任务,cij表示第i个人完成第j项任务的效率。,第五节指派问题,二、指派问题的数学模型,=(Cij),人,任务,解：设,例：某单位现在、四项工作需完成，现在甲、乙、丙、丁四个人均可完成这四项任务。每人完成各项任务所用的时间如右表所示，问应指派何人去完成何项任务，使所需时间最少？,A,B,C,D,任务,人员
10、,满足所有约束条件的可行解xij也可写成表格或矩阵形式，称为解矩阵,(xij)=,就是上例的一个可行解矩阵,第五节指派问题,(cij)=,第五节指派问题,指派问题数学模型的性质：,若从指派问题的系数的系数矩阵（cij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。,独立的0元素：位于不同行不同列的0元素称为独立的0元素。,结论：若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。将其代入目标函数中得到zk=0，它一定是最小。这就是以
11、(bij)为系数矩阵的指派问题的最优解。也就得到了问题的最优解。,第五节指派问题,三、指派问题的解法（匈牙利法）,第一步:使指派问题的系数矩阵经变换，在各行各列都出现元素。,（）从系数矩阵的每行元素减去该行的最小元素；（）再从所得系数矩阵的每列元素中减去该列的最小元素。,min,min,经第一步变换后，系数矩阵中每行每列都已有了0元素；只需找出n个独立的0元素，若能找出，就以这些独立的0元素对应解矩阵中的元素为1，其作为0，这就得到最优解。找独立0元素的步骤如下：,第二步：进行试指派，以寻求最优解。,第五节指派问题,（3）反复(1),(2)两步，直到所有0元素都被圈出和划掉为止。,（4）若各行
12、各列均有多于2个的0元素未被圈出或划掉，中任选其中任意一个0元素加圈。,（5）若元素的数目m等于矩阵的阶数n，那么指派问题的最优解已得到，若mn，则转入下一步。,min,第五节指派问题,第五节指派问题,第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立0元素数。,（5）对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有0元素的最少直线。,（1）对没有的行打号；,（2）对已打号的行中所有含划0元素的列打号；,（3）再对打有号的列中含元素的行打号；,（4）重复(2)、(3)直到得不出新的打号的行、列为止；,第五节指派问题,第四步：对第三步所得矩阵进行变换，目的是增加0
13、元素。,在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去该最小元素，而在打列的各元素都加上该最小元素（以保证原来的0元素不变）。这样得到新系数矩阵。重复第二步。,独立0元素的个数等于效率矩阵的阶数得到了最优解,最优解矩阵为：,第五节指派问题,练习：有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：,工作,工人,解：用匈牙利法求解过程如下：,min,min,1,第五节指派问题,第五节指派问题,四、非标准形式的指派问题,1、最大化指派问题2、人数和事数不等的指派问题3、一个人可做几件事的指派问题4、某事一定不能由某人做的指派问题,第五节指派问题,1、求最大化的
14、指派问题,令bij=M-cij其中：M是足够大的常数（cij中最大元素）用匈牙利法求解（bij）即可。所得最小解就是原问题的最大解。,第五节指派问题,2、人数和任务数不等的指派问题,若人少任务多，则添上一些虚拟的“人”。这些虚拟的“人”完成各任务的费用系数可取0，理解为这些费用实际上不会发生。若人多任务少，则添上一些虚拟的“任务”，这些虚拟的“任务”由各人完成的费用系数同样也取0。,第五节指派问题,3、一个人可以完成几项任务的指派问题,若某个人可完成几项任务，则可将人化作相同的几个“人”，来接受指派，这几个“人”完成同一项任务的费用系数都一样。,4、某项任务一定不能由某人完成的指派问题,若某项
15、任务一定不能由某个人完成，则可将相应的费用系数取作足够大的数M。,例：分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。,第五节指派问题,第六节应用举例,1、m约束条件中只有k个起作用,设m个约束条件可表示为：,定义,又M为任意大的正数，得,第六节应用举例,定义,第六节应用举例,3、两组条件中满足其中一组,若x14，则x21；否则（即x14）,x23,又M为任意大正数，则问题可表达为：,第六节应用举例,4、用以表示固定费用的函数,生产费用函数：,引入变量yj,复
16、习题,一、判断下列说法是否正确,1、整数规划的目标函数值一般优于其相应的线性规划问题（松弛问题）的解的目标函数值。2、用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。3、用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较、剪枝。4、用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。,复习题,一、判断下列说法是否正确,5、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。6、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。7、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。8、求解0-1规划的隐枚举法是分枝定界法的特例。9、分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。,复习题,2、用匈牙利法求解最小化的指派问题，效率矩阵如下：,min,复习题,3、应用建模：教材128页4.16,
