运筹学整数规划

1第四章整数规划IntegerProgramming特点-解法-应用2主要内容整数规划的性质整数规划的解法分支定界法割平面法匈牙利法（指派问题）34.1整数规划的引出例1、某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如表所示。货物每件体积(立方米)每件重量(百斤)每件利润(百元)甲乙54252010托运限制24(立方米)14(百斤)问两种货物各装运多少箱，可使获得利润最大？4设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)x1,x2≥0(4)x1,x2为整数(5)它和线性规划问题的区别在于条件(5)。货物每件体积(立方米)每件重量(百斤)每件利润(百元)甲乙54252010托运限制24(立方米)14(百斤)54.2整数规划的特点与分类（1）在很多实际问题中，全部或部分变量的取值必须是整数，如人或机器设备等不可分割。（2）此外还有一些问题，如要不要在某地建设工厂或指派某人去做某事，可选用一个逻辑变量x，令x=1表示在该地建厂或指派某人做事，x=0表示不在该地建厂或不指派某人做事，逻辑变量也是只允许取整数值的一类变量。6整数规划的分类（3）纯整数线性规划（IP）：在一个线性规划中要求全部变量取整数值，或简称纯整数规划。（4）混合整数(线性)规划（MIP）：在一个线性规划中只要求一部分变量取整数值。74.3整数规划的解法—“凑整法”？直觉认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整方法寻找最优解。是否合适？是否可行？8例1、求下述整数规划问题的最优解2123maxxxz且均取整数值,0,5.45.01432212121xxxxxx9(3,3)(3,2)(4,3)(4,2)(4,1)，Z=14(3.25，2.5)2x1+3x2=14x1+0.5x2=4.53x1+2x2=0且均取整数值,0,5.45.01432212121xxxxxx2123maxxxz10如果不考虑x1、x2取整数的约束，用图解法求得最优解为(3.25，2.5)。由于x1、x2必须取整数值，实际上问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但(4，3)、(4，2)、(3，3)都不是可行解，(3，2)虽属可行解，但代入目标函数得z=13，并非最优。实际上问题的最优解应该是(4，1)，z*=14。注意：(4，1)不是可行域的顶点，因此直接用图解法或单纯形法都无法找出整数规划问题的最优解来。这就要求研究解整数规划问题的特殊方法。11收获整数规划的可行域包含在其对应的一般线性规划可行域之内；整数规划的最优解可能不是其对应的一般线性规划的顶点；整数规划需要专门的求解方法。124.4整数规划与对应的线性规划解的关系1、任何求max的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；（对应线性规划最优解为其上界）2、任何求min的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数。（对应线性规划最优解为其下界）3、整数规划之相应线性规划的最优解经四舍五入不能得到其最优解整数规划的最优解不会优于其对应的线性规划的最优解。既然不能通过凑整来求解，可以逐步将对应线性规划可行域中的非整数部分舍去。134.5整数规划的解法分支定界法割平面法匈牙利法144.5.1整数规划解法——分枝定界法步骤：1、寻找替代问题并求解2、分枝与定界3、剪枝151、基本思路：整数规划的最优解不会优于相应的线性规划的最优解。对于极大值问题，相应线性规划的最大值成为整数规划目标函数的上界。maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的松弛问题。（1）替代问题的确定16（2）替代问题的求解maxZ=CXAX=bX0(B)采用相应的方法（如图解法）求解出替代问题的最优解，观察其是否满足整数解的要求。如其最优解就为整数，则结束；如含有分数，则需要进行分支定界操作。17（3）分支与定界—增加约束•如替代问题的解不符合整数条件，则需要对原问题进行分支。•分支方法：假设替代问题的解为[i，i+1]之间的一个数，则分成两支：一支增加约束xj≤i，另一支增加约束xj≥i+1；•对上述两个问题进行求解：不考虑整数问题时，求解对应的线性规划问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到全部整数解为止。X*Xj*i+1i(C)(D)(B)Xji+1(B)Xji18maxZ=40X1+90X29X1+7X2567X1+20X270X1,X20X1,X2为整数例：19解：先解该整数规划对应的松弛问题X*=4.8091.817Z*=355.890，上界Z*选X1分枝问题(2)(1)X14问题(3)(1)X15将[4,5]之间的非整数部分舍去20选(2)继续分枝问题(4)(2)X22问题(5)(2)X23解为X1=4X2=2.1Z=349.0解为X1=5X2=1.571Z=341.39问题2问题321(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283340327.12(6)5.4441340307.76(7)无解X14X15X22X21X22X23分支定界过程224.5.2整数规划解法2——割平面法割平面法的基本思想：在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束，高莫雷约束或割平面)，使问题的可行域逐步缩小。但每次切割时，只割去问题的部分非整数解，而不切割任何整数的可行解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。234.5.3整数规划的解法——匈牙利法应用于分配问题或指派问题分配问题也称指派问题，是一种特殊的整数规划问题。假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。241、指派问题一般模型的引出例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高（所需总时间最短）？人工作甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文415139从人的角度看从任务角度看25指派问题的一般模型假设：[aij]表示指派问题的效率矩阵xij表示决策变量，决策变量的取值：1,0,(1,...,m;1,...,m)ijijxijij分配第个人去完成第项任务不分配第个人去完成第项任务26指派问题的一般数学模型mimjijijxaz11min111(1,...,m)1(1,...,m)01mijjmijiijxixjx或指派问题的一般模型272、指派问题的求解方法单纯形法表上作业法匈牙利法28（1）指派问题的求解—匈牙利法核心思路：基于这样一个事实：如果效率矩阵的所有元素aij≥0，而其中存在一组位于不同行、不同列的零元素，则只要令对应于这些零元素的xij=1（分配任务），其余的xij=0，则目标函数z必然会取得最小（0）。0149392002320038512140只需令：x11=1，x23=1，x32=1，x44=1，即第一项各种分配给甲，二工作→丙，三→乙，四→丁。总工作时间最少。效率矩阵29问题要求：效率矩阵中存在零元素，同时存在不在同一行、同一列的零元素。实际的效率矩阵中，是不可能存在0元素的，那么如何获得这种特殊的效率矩阵？如何让效率矩阵中产生零元素；如何让产生的零元素位于不同行和不同列。30（2）零元素的产生方法：匈牙利法的基本定理1如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵[bij]，若其中则[bij]的最优解等价于[aij]的最优解（说明，经过变换后，有零的新效率矩阵取得最优解时，原效率矩阵也同时取得最优解）jiijijvuab31（3）独立零元素的判断方法：匈牙利法的基本定理2若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行、不同列的“0”元素的最大个数。1200020312402030120002030240223132若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行、不同列的“0”元素的最大个数。将确定一个效率矩阵中最大独立零元素的个数，转化为寻找覆盖所有零元素所需的最少直线数。33匈牙利法的计算步骤基本步骤：在效率矩阵中产生零元素→判断独立的零元素个数是否等于任务数或人数？→如是，则对效率矩阵中独立零元素所处的位置进行指派（对应的决策变量为1），完成→如否，则要继续产生足够的独立零元素。通过实例来说明匈牙利法求解指派问题的过程。34例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高？人工作甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文41513935效率矩阵9131541116141381441579102A36步骤一：零元素的产生。方法：找出效率矩阵每行的最小元素，并分别从每行中减去它。min实际含义：从事情的角度来考虑，表示此事分配给此人效率最高。591100532410011578041142913154111614138144157910237步骤二：继续产生零元素方法：再找出矩阵每列的最小元素，再分别从各列中减去它。min0050实际含义：从人的角度来考虑，表示某人做此事效率最高。541100032450115280259110053410011578038步骤三：判断零元素是否位于不同行、不同列？经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。确定能否找出m个位于不同行不同列的零元素的集合(本例中m=4)，直观法：m很小时，直接判断得到；非直观法：m很大时，根据一定规则寻找。39直观法541100032450115280只有3个0元素位于不同行、不同列40非直观法-步骤1（试指派过程）(1)从任务的角度来挑选从第一行开始，若该行只有一个零元素，就对这个零元素打上()号。表示该0元素处在单独的一行同时，对打()号零元素所在列画一条直线，表示此列已经确定（人员确定），不能再从事其他行的工作（任务）。若该行没有零元素或有两个以上零元素(已划去的零元素不计在内)，则转下一行，按照上述方法依次进行到最后一行；41082511054230001145例：从行开始的独立零元素的寻找与判断（）（）(0)82511(0)54230001145从行开始标定独立零元素时，只能找到两个独立的零元素。42非直观法-步骤2(2)从人的角度在行寻找的基础上，从第一列开始，若该列只有一个零元素就对这个零元素打上()号(同样不考虑已划去的零元素)，对打()号零元素所在行画一条直线