运筹学-整数规划（课堂PPT）

运筹学,整数规划,IntegerProgramming,第四章,2,5/18/2020,第四章整数规划,本章主要内容：,整数问题规划及其数学模型整数规划问题的求解0-1型整数规划问题指派问题,3,5/18/2020,第四章整数规划,在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。,整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。,4,5/18/2020,第四章整数规划,线性规划模型：,实际问题要求xi为整数！,如机器的台数，人数等,5,5/18/2020,第四章整数规划,例:胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,6,5/18/2020,第四章整数规划,纯整数规划,7,5/18/2020,第四章整数规划,例（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有m件物品，第i件件物品的重量为bi，价值为ci，问题就变成：在携带的物品总重量不超过b公斤的条件下，携带哪些物品可使总价值最大?,8,5/18/2020,第四章整数规划,9,解：,Z表示所带物品的总价值,携带物品的总重量,数学模型：,0-1规划,5/18/2020,第四章整数规划,10,5/18/2020,第四章整数规划,解：,数学模型：,混合型整数规划,11,5/18/2020,第四章整数规划,例工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：,工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。,12,5/18/2020,第四章整数规划,解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：,再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：,13,5/18/2020,第四章整数规划,混合整数规划问题,14,5/18/2020,第四章整数规划,整数线性规划问题的种类：,纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。,15,5/18/2020,第四章整数规划,纯整数规划的数学模型：,0-1规划的数学模型：,16,5/18/2020,第四章整数规划,例,Z=130,，可行且Z=140,不可行,可行,17,5/18/2020,第四章整数规划,（IP）,（IP）问题的松弛问题,18,5/18/2020,第四章整数规划,松弛问题的最优值是原整数规划的目标函数值的上界,19,5/18/2020,第四章整数规划,例设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,20,5/18/2020,第四章整数规划,用图解法求出最优解为：x13/2,x2=10/3，且有Z=29/6,现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。,x1,x2,3,3,(3/2,10/3),按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。,21,5/18/2020,第四章整数规划-分支定界法,1）求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；2）分支与定界：任意选一个非整数解的变量xi，在松弛问题中加上约束：xixi和xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。,分支定界法的解题步骤：,22,5/18/2020,上界,x1x*01,x1x*01+1,23,5/18/2020,24,5/18/2020,一、分枝定界法的原理：,1、分枝,松弛问题的可行域,增加x13,增加x14,L1,L2,25,x13,x14,父问题,子问题,结论1：（IP）的最优解一定在某个子问题中,父问题的最优值,3：子问题中的整数解都是（IP）的可行解,子问题的最优解,2：子问题的可行域,父问题的可行域,26,2、定界,1、（LP）的最优值是(IP)的最优值的上界,27,IP,松弛问题L0,L1,L2,通过对（L0）分枝，使（IP）的最优值的上界不断下降，,L3,L4,L5,L6,下界不断上升，,上界=下界,得最优值,28,x13,x14,z=30 x1+20 x2,4x1+x2=16.5,2x1+3x2=14.5,x22,x23,x12,x13,29,混合型,x13,x14,L0的最优单纯型表：,x5,x5,100013,000,30,x13,x14,x12,x13,x22,x23,31,x5,x5,100013,000,x5,x5,001/10-3/101-1/2,000,x4,x5,32,x22,x2+x6=2,x6,0100012,x6,0000,33,x23,X2-x6=3,x6,0-10001-3,x6,0000,-X2+x6=-3,34,x12,x1+x7=2,00-1/200-3/21-3/4,35,如何选择分枝的节点及分枝变量？,1、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点，提高搜索效率。,方法：,（1）深探法：,（2）广探法：,最后打开的节点最先选择,选择有最大目标函数值的节点继续向下分枝,2、分枝变量选择的原则：,寻找那些对问题影响最大的变量首先分枝,（1）按目标函数系数选择：,选择目标函数系数绝对值最大的变量首先分枝,（2）按非整数变量选择：,选择与整数值相差最大的非整数变量进行分枝,（3）按人为给定的顺序选择,36,x13,x14,x22,x23,x12,x13,37,第四章整数规划-割平面法,割平面法的基本思想：,若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.,38,5/18/2020,割平面,39,南京邮电大学经济与管理学院,问题：如何寻找割平面？,增加的约束方程须满足什么条件才能使：,1、割掉松弛规划的最优解,2、保留所有的整数解,40,南京邮电大学经济与管理学院,二、割平面法,41,南京邮电大学经济与管理学院,L0的最优单纯形表：,源方程,42,南京邮电大学经济与管理学院,-对应于生成行i的割平面,43,南京邮电大学经济与管理学院,L0的最优单纯形表：,生成行,对应于生成行i的割平面,非基变量,44,南京邮电大学经济与管理学院,b,010.500-0.51,00-1.75103.255.5,00-10113,10-0.25000.751.5,00-0.500-1.5z-9,对应第2行的割平面：,对应第4行的割平面：,45,南京邮电大学经济与管理学院,非基变量,46,南京邮电大学经济与管理学院,如何求解？,47,南京邮电大学经济与管理学院,s,s,000-fim+1-fim+j-fin1fi0,0000,对偶单纯形法,48,南京邮电大学经济与管理学院,割平面计算步骤,第一步：,用单纯形法解整数问题IP的松弛问题L0,若L0没有最优解，则IP没有最优解。停止,若L0有最优解X0:,(1)X0是整数解，,则X0也是IP的最优解，停止,(2)X0不是整数解，,转第二步,第二步：,求割平面方程,49,南京邮电大学经济与管理学院,第三步：,将割平面加到L0得L1,第四步：,解L1,在L0的最优单纯形表中增加一行一列，得L1的单纯形表，,用对偶单纯形法求解，,若其解是整数解，则该解也是原整数规划的最优解,否则将该解记为X0，返回第二步,50,南京邮电大学经济与管理学院,例用割平面法求解IP,解：IP问题的松弛规划的标准型：,X5,000,X5,00-0.125-0.3751-0.75,100013,010.3330-0.6672,00-1.6670-4.667z-34,整数,最优值：Z=34,51,南京邮电大学经济与管理学院,例：用割平面法求解,解：IP的松弛规划的标准型,X5,00-7/22-1/221-1/2,X5,000,1001/7-1/732/7,010013,000-1-8Z-59,非整数,52,南京邮电大学经济与管理学院,1001/7-1/732/7,010013,000-1-8Z-59,X6000-1/7-6/71-4/7,X6,0000,整数,最优值：Z=55,53,南京邮电大学经济与管理学院,作业：,分别用分枝定界法和割平面法求解整数规划：,最优值为：,Z=4,54,南京邮电大学经济与管理学院,第四章整数规划-0-1整数规划,01型整数规划是整数规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为01变量，或称二进制变量。xi仅取值0或1这个条件可由下述约束条件：xi1xi0，整数所代替，和一般整数规划的约束条件形式一致的。,55,5/18/2020,第四章整数规划-0-1整数规划,投资场所的选择相互排斥的计划例：某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai（i=1，2，7）可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为Ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？,56,5/18/2020,第四章整数规划-0-1整数规划,令xi=1，2，7,57,5/18/2020,第四章整数规划-0-1整数规划,（1）两个约束中，只有一个起作用。例：a11x1+a12x2B1a21x1+a22x2B2,例含有相互排斥的约束条件的问题,解：引入0-1变量Y1,Y2和足够大的正数M，则,a11x1+a12x2B1+M1Y1a21x1+a22x2B2+M2Y2Y1+Y2=1,58,5/18/2020,第四章整数规划-0-1整数规划,（2）互相排斥的多个约束中，只有一个起作用,ai1x1+ai2x2+ainxnbi(i=1,m),互相排斥m个约束，只有一个起作用:,（3）若a个约束条件中只能有b个起作用。则令01变量之和为a-b。注意：可用统一M，但M的取值必须足够的大。,59,5/18/2020,第四章整数规划-0-1整数规划,1问题的提出:已知：两种货物装箱每种货物装箱利润体积限制重量限制决策变量:两种货物各多少箱MaxZ=利润最大？箱数不能为分数,相互排斥的约束条件,60,5/18/2020,第四章整数规划-0-1整数规划,互相排斥的约束条件（假设有车、船2种运输方式）用车运的体积约束用船运的体积约束,61,5/18/2020,第四章整数规划-0-1整数规划,固定费用的问题在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。,62,5/18/2020,第四章整数规划-0-1整数规划,例固定费用问题,解：设Xj是第j种产品的产量。Yj是01变量，表示是（Yj=1）否（Yj=0）生产第j种产品。,63,5/18/2020,第四章整数规划-0-1整数规划,64,5/18/2020,第四章整数规划-隐枚举法,在整数规划模型中，若变量取值为0或1两个特殊的数值，则称此类模型为01的使用及建立模型的方法。隐枚举法基本思想：隐枚举法是分枝定界法思想的延伸。通过放松主约束条件（而非变量符号限制条件）求得最优解，再检查是否满足约束条件，再经过分枝与剪枝等工作迭代出最优解。,65,5/18/2020,第四章整数规划-隐枚举法,在2n个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。对于可行解，其目标函数值也有优劣之分。若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合不必再去检验它的可行性。在以后的求解过程中，每当发现比原来更好的可行解，则替换原来的过滤条件。,66,5/18/2020,第四章整数规划-隐枚举法,0-1规划求解,MaxZ=3X12X25X3X1+2X2X3=2（1）X1+4X2+X3=4（2）X1+X2=3（*）称为过滤条件（FilteringConstraint）,67,5/18/2020,第四章整数规划-隐枚举法,于是最优解（X1,X2,X3）（1，0，1）MaxZ=8,3X12X25X3=3（*）称为过滤条件（FilteringConstraint）,68,5/18/2020,第四章整数规划-隐枚举法,MaxZ=2X23X15X3目标函数按系数递增（2，3，5）约束条件也按上面决定的顺序2X23X15X3=3（*）2X2X1X3=2（1）4X2+X1X3=4（2）X2X1=8（*）为过滤条件,这里已经更换了x1,x2的位置(x2,x1,x3),71,5/18/2020,MaxZ=2X23X15X3目标函数按系数递增（2，3，5）约束条件也按上面决定的顺序2X23X15X3=3（*）2X2X1X3=2（1）4X2+X1X3=4（2）X2X1=3（3）4X2+X3=6（4）X1,X2,X3=0或者1（5）,解：变量（X1,X2,X3）按下面顺序容易更早发现最优解：（1，0，1）,对应目标函数系数（3，-2，5）负系数的Xi取0，正系数的Xi取1这时目标函数达到最大值，但不一定满足约束条件；如果满足约束条件，则不必检验其他解，一步直达。,这里已经更换了x1,x2的位置,72,5/18/2020,第四章整数规划-隐枚举法,在解决0-1规划问题时，为了进一步减少运算量，常按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解有可能较早出现。对于最大化问题，可按目标函数中各变量系数由小到大的顺序排列。对于最小化问题，可按目标函数中各变量系数由大到小的顺序排列。,73,5/18/2020,第四章整数规划-隐枚举法,求解01整数规划maxf(x)=3x1-2x2+5x3s.t.x1+2x2-x32x1+4x2+x34x1+x234x2+x36x1,x2,x3=0或1,74,5/18/2020,第四章整数规划-隐枚举法,求解0-1整数规划minf(x)=3x1+7x2-x3+x4s.t.2x1-x2+x3-x41x1-x2+6x3+4x485x1+3x2+x45x1,x2,x3,x4=0或1,75,5/18/2020,设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。,费用,12jn,12in,指派问题模型：,i=1,2,n,j=1,2,n,第i个人做第j件事,Z表示总费用,i=1,2,n;j=1,2,n,第i个人不做第j件事,1、指派问题的数学模型,76,i=1,2,n,j=1,2,n,当n=4时，,有16变量，,8个约束方程,77,例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。,工作,人,费用,1234,1234,3545,6768,89810,1010911,1,0,第i人做第j件事,Z表示总费用,i=1,2,3,4;j=1,2,3,4,第i人不做第j件事,78,2、费用矩阵,设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。,费用,12jn,12in,cij表示第i个人做第j件事的费用,费用矩阵,79,例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。,工作,人,收费用,1234,1234,3545,6768,89810,1010911,费用矩阵,对应一个5个人5个工作的指派问题,第2个人做第4个工作的费用,5,第4个人做第2个工作的费用,0,80,定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。,n个人n个工作的指派问题1,-b,3、匈牙利法,n个人n个工作的指派问题2,81,i=1,2,n,j=1,2,n,i=1,2,n,j=1,2,n,-b,82,83,-b,i=1,2,n,j=1,2,n,i=1,2,n,j=1,2,n,84,任务：对C的行和列减去某个常数，将C化的尽可能简单，,简单到可一眼看出该问题的最优解,-b,85,南京邮电大学经济与管理学院,指派问题的最优解：若C中有n个位于不同行不同列的零元素，则令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解,i=1,2,3,4,j=1,2,3,4,可行解,最优解,86,匈牙利法的基本思路：,对费用矩阵C的行和列减去某个常数，将C化成有n个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，即得指派问题的最优解,87,例：有一份说明书要分别译成英、日、德、俄四种文字，现交给甲、乙丙、丁四个人去完成，每人完成一种。由于个人的专长不同，翻译成不同文字所需的时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？,工作,人,时间,英日德俄,甲乙丙丁,215134,1041415,9141613,78119,-2,-4,-9,-7,最优方案：,甲翻译俄文,，乙翻译日文,丙翻译英文,，丁翻译德文,总费用：28小时,-4,-2,88,-2,-4,-9,-7,-4,-2,最优解的取法：,从含0元素最少的行或列开始，圈出一个0元素，用表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推，若能得到n个，则得最优解X0,89,例：求费用矩阵为右表的指派问题的最优解,工作,人,费用,ABCDE,甲乙丙丁戊,127979,89666,717121412,15146610,4107106,-7,-6,-7,-6,-4,得4个，且不存在没打的0,修改方法！,90,对n阶费用矩阵C，若C有n个位于不同行不同列的零元素，即可得最优解X0。否则，对C进行调整。,-2,+2,-2,最优指派方案：甲做B工作,，乙做C工作,丙做A工作,，丁做D工作,戊做E工作,？,？,91,当C没有n个位于不同行不同列的零元素时，对C进行调整。,第一步：做能复盖所有0元素的最小直线集合：,1）对没有的行打号,2）对打号的行上所有0元素的列打号,3）再对打号的列上所有的行打号,4）重复以上步骤直到得不出新的打号为止,5）对没有打号的行画横线，所有打号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合,具体步骤：,92,第二步：在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素,第三步：对所得到的矩阵画，若能得到n个，则得最优解，否则重复以上步骤，直至得到n个。,+2,-2,-2,93,南京邮电大学经济与管理学院,例：求费用矩阵为下表的指派问题的最优解,工作,人,费用,ABCDE,甲乙丙丁戊,127979,89666,717121412,15146610,4107106,-7,-6,-7,-6,-4,+2,-2,-2,最优指派方案：甲做B工作,乙做C工作,丙做A工作,丁做D工作,戊做E工作,=32,94,匈牙利法的具体步骤：,第一步：变换指派问题的费用矩阵，使其在各行各列都出现0元素：,方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素,第二步：进行试指派（画）,方法：从含0元素最少的行或列开始，圈出一个0元素，用表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推。,若矩阵中的的个数等于n，则得最优解,若矩阵中的的个数n,工作,人,费用,12jn,12im,n+1n+2m,用匈牙利法求解,105,例：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只