运筹学整数规划

1、1,第四章 整数规划Integer Programming,特点-解法-应用,2,主要内容,整数规划的性质 整数规划的解法 分支定界法 割平面法 匈牙利法（指派问题）,3,4.1 整数规划的引出,例1、某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、 重量，可获利润以及托运所受限制如表所示。,问两种货物各装运多少箱，可使获得利润最大？,4,设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下： max z20 x1+10 x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1, x20 (4) x1, x2为整数 (5

2、),它和线性规划问题的区别在于条件(5)。,5,4.2 整数规划的特点与分类,（1）在很多实际问题中，全部或部分变量的取值必须是整数，如人或机器设备等不可分割。 （2）此外还有一些问题，如要不要在某地建设工厂或指派某人去做某事，可选用一个逻辑变量x，令x=1表示在该地建厂或指派某人做事，x=0表示不在该地建厂或不指派某人做事，逻辑变量也是只允许取整数值的一类变量。,6,整数规划的分类,（3）纯整数线性规划（IP）： 在一个线性规划中要求全部变量取整数值，或简称纯整数规划。 （4）混合整数(线性)规划（MIP）： 在一个线性规划中只要求一部分变量取整数值。,7,4.3 整数规划的解法“凑整法”？

3、,直觉认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整方法寻找最优解。 是否合适？ 是否可行？,8,例1、,求下述整数规划问题的最优解,9,2x1+3x2=14,x1+0.5x2=4.5,10,如果不考虑x1、x2取整数的约束，用图解法求得最优解为(3.25，2.5)。由于x1、x2必须取整数值，实际上问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但(4，3)、(4，2)、(3，3)都不是可行解，(3，2)虽属可行解，但代入目标函数得z=13，并非最优。实际上问题的最优解应该是(4，1)，z*=1

4、4。 注意：(4，1)不是可行域的顶点，因此直接用图解法或单纯形法都无法找出整数规划问题的最优解来。 这就要求研究解整数规划问题的特殊方法。,11,收 获,整数规划的可行域包含在其对应的一般线性规划可行域之内； 整数规划的最优解可能不是其对应的一般线性规划的顶点； 整数规划需要专门的求解方法。,12,4.4 整数规划与对应的线性规划解的关系,1、任何求max的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；（对应线性规划最优解为其上界） 2、任何求min的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数。（对应线性规划最优解为其下

5、界） 3、整数规划之相应线性规划的最优解经四舍五入不能得到其最优解,整数规划的最优解不会优于其对应的线性规划的最优解。 既然不能通过凑整来求解，可以逐步将对应线性规划可行域中的非整数部分舍去。,13,4.5 整数规划的解法,分支定界法 割平面法 匈牙利法,14,4.5.1 整数规划解法 分枝定界法,步骤： 1、寻找替代问题并求解 2、分枝与定界 3、剪枝,15,1、基本思路：整数规划的最优解不会优于相应的线性规划的最优解。对于极大值问题，相应线性规划的最大值成为整数规划目标函数的上界。,(B)为(A)的松弛问题。,（1）替代问题的确定,16,（2）替代问题的求解,采用相应的方法（如图解法）求解

6、出替代问题的最优解，观察其是否满足整数解的要求。如其最优解就为整数，则结束；如含有分数，则需要进行分支定界操作。,17,（3）分支与定界增加约束,如替代问题的解不符合整数条件，则需要对原问题进行分支。 分支方法：假设替代问题的解为i，i+1之间的一个数，则分成两支：一支增加约束xji，另一支增加约束xj i+1； 对上述两个问题进行求解：不考虑整数问题时，求解对应的线性规划问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到全部整数解为止。,18,max Z=40X1 + 90X2,例：,19,解：先解该整数规划对应的松弛问题,选X1分枝,将4,5之间的非整数部分舍去,20,选(2)

7、继续分枝,问题2,问题3,21,分支定界过程,22,4.5.2 整数规划解法2割平面法,割平面法的基本思想： 在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束，高莫雷约束或割平面)，使问题的可行域逐步缩小。但每次切割时，只割去问题的部分非整数解，而不切割任何整数的可行解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。,23,4.5.3 整数规划的解法匈牙利法应用于分配问题或指派问题,分配问题也称指派问题，是一种特殊的整数规划问题。 假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个

8、人去完成，应如何分配使总的效率为最高。,24,1、指派问题一般模型的引出,例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高（所需总时间最短）？,从人的角度看,从任务角度看,25,指派问题的一般模型,假设： aij表示指派问题的效率矩阵 xij表示决策变量，决策变量的取值：,26,指派问题的一般数学模型,指派问题的一般模型,27,2、指派问题的求解方法,单纯形法 表上作业法 匈牙利法,28,（1）指派问题的求解匈牙利法,核心思路：基于这样一个事实：如果效率矩阵的所有元素aij

9、0，而其中存在一组位于不同行、不同列的零元素，则只要令对应于这些零元素的xij=1（分配任务），其余的xij =0，则目标函数z必然会取得最小（0）。,只需令：x11=1，x23=1，x32=1，x44=1，即第一项各种分配给甲，二工作丙，三乙，四丁。总工作时间最少。,效率矩阵,29,问 题,要求：效率矩阵中存在零元素，同时存在不在同一行、同一列的零元素。 实际的效率矩阵中，是不可能存在0元素的，那么如何获得这种特殊的效率矩阵？ 如何让效率矩阵中产生零元素； 如何让产生的零元素位于不同行和不同列。,30,（2）零元素的产生方法：匈牙利法的基本定理1,如果从分配问题效率矩阵aij的每一行元素中分

10、别减去(或加上)一个常数ui (被称为该行的位势)，从每一列分别减去(或加上)一个常数vj (称为该列的位势)，得到一个新的效率矩阵bij，若其中 则bij的最优解等价于aij的最优解（说明，经过变换后，有零的新效率矩阵取得最优解时，原效率矩阵也同时取得最优解）,31,（3）独立零元素的判断方法：匈牙利法的基本定理2,若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行、不同列的“0”元素的最大个数。,32,若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行、不同列的“0”元素的最大个数。 将确定一个效率矩阵中最大独立零元素

11、的个数，转化为寻找覆盖所有零元素所需的最少直线数。,33,匈牙利法的计算步骤,基本步骤：在效率矩阵中产生零元素判断独立的零元素个数是否等于任务数或人数？如是，则对效率矩阵中独立零元素所处的位置进行指派（对应的决策变量为1），完成如否，则要继续产生足够的独立零元素。 通过实例来说明匈牙利法求解指派问题的过程。,34,例：,有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高？,35,效率矩阵,36,步骤一：零元素的产生。方法：找出效率矩阵每行的最小元素，并分别从每行中减去它。,min

12、,实际含义：从事情的角度来考虑，表示此事分配给此人效率最高。,37,步骤二：继续产生零元素方法：再找出矩阵每列的最小元素，再分别从各列中减去它。,min 0 0 5 0,实际含义：从人的角度来考虑，表示某人做此事效率最高。,38,步骤三：判断零元素是否位于不同行、不同列？,经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。 确定能否找出m个位于不同行不同列的零元素的集合(本例中m=4)， 直观法：m很小时，直接判断得到； 非直观法：m很大时，根据一定规则寻找。,39,直观法,只有3个0元素位于不同行、不同列,40,非直观法-步骤1（试指派过程）,(1) 从第一行开始，若该行只有一个零元素

13、，就对这个零元素打上( )号。 同时，对打( )号零元素所在列画一条直线，表示此列已经确定（人员确定），不能再从事其他行的工作（任务） 。 若该行没有零元素或有两个以上零元素(已划去的零元素不计在内)，则转下一行，按照上述方法依次进行到最后一行；,41,例：从行开始的独立零元素的寻找与判断,（ ）,（ ）,从行开始标定独立零元素时，只能找到两个独立的零元素。,42,非直观法-步骤2,(2) 在行寻找的基础上，从第一列开始，若该列只有一个零元素就对这个零元素打上( )号(同样不考虑已划去的零元素)， 对打( )号零元素所在行画一条直线（任务分配完毕，不能再分配给其他人）。 若该列没有零元素或有两

14、个以上零元素，则转下一列，依次进行到最后一列；,43,例：从列开始的独立零元素的寻找与判断,（ ）,在行标定后的基础上，从第一列开始标定独立零元素时，只能找到一独立的零元素。,44,问 题,只能对三个零元素进行标定（代表独立的零元素只有三个），后续如何操作？,45,非直观法-步骤3（第一种情形）,(3) 重复(1)、(2)两个步骤，可能出现三种情况： 效率矩阵每行都有一个打( )号的零元素，很显然，按上述步骤得到的打( )号的零元素都位于不同行不同列，只要令对应打( )号零元素对应的决策变量xij=1就找到了问题的最优解；,46,第一种情形,x11=1，x22=1，x33=1，x44=1。 任

15、务一甲；二乙；三丙；四丁,任务一 任务二 任务三 任务四,甲 乙 丙 丁,47,非直观法-4（第二种情形）, 打( )号的零元素个数小于m，但未被划去的零元素之间存在闭回路（全以0为拐点），这时可顺着闭回路的走向，对每个间隔的零元素打一( )号，然后对所有打( )号的零元素，或所在行，或所在列画一条直线（一般会出现多种方案）。如：,48,第二种情形,（ ）,（ ）,只能给两个零元素打括号，还有四个零元素不能打上括号。剩下的未被划去和未打括号的零元素存在闭回路。,（ ）,（ ）,49,x13=1，x22=1，x31=1，x44=1,结论1,50,结论2,（ ）,（ ）,x14=1，x22=1，x

16、31=1，x43=1,51,非直观法-5（第三种情形）, 矩阵中所有零元素或被划去，或打上( )号，但打( )号的零元素个数小于m，如：,打括号的零元素3m=4。证明0元素产生的还不够，还应继续产生。,52,步骤四：继续创造零元素。方法：为设法使每一行都有一个打( )号的零元素，需要继续按定理1对矩阵进行变换。,(1) 从矩阵未被直线覆盖的数字中找出一个最小的数k； (2) 对矩阵的每行，当该行有直线覆盖时，令ui= 0，无直线覆盖的，令ui=k； (3) 对矩阵每列，有直线覆盖的列，令vj= -k，对无直线覆盖的列，令vj=0； (4) 从原矩阵的每个元素aij中分别减去ui和vj，得到一个

17、新的矩阵（ aij - ui - vj ），保证新矩阵中，原打括号的0元素不变，同时产生新的零元素。,53,步骤五：回到第三步，反复进行，一直到矩阵的每一行都有一个打( )号的零元素为止，即找到了最优分配方案。,54,最优分配方案为： 甲将说明书译成俄文，乙译成日文，丙译成英文，丁译成德文， 全部所需时间为4+4+9+11=28小时。,55,回顾：指派问题的计算过程,效率矩阵,56,4,11,4,2,步骤一：产生每行的零元素。方法：从每行中找出最小的元素，与对应的每行元素相减,min,每行减去对应的最小元素,57,步骤二：产生位于每列的零元素方法：再找出矩阵每列的最小元素，再分别从各列中减去。

18、,min 0 0 5 0,每列减去对应的最小元素,保证每行、每列都至少有一个0元素。,58,步骤三：判断零元素是否位于不同行、不同列。方法：首先从行开始试指派，只有一个零元素时，对零元素打括号，并对所在列画直线。而有多个零元素，或零元素已被画去，则转下一行；行分析完毕后，然后从列开始试指派，对每列只有一个零元素时，打括号，并画去其所在的行。,（ ）,（ ）,行试指派过程,列试指派过程,（ ）,59,步骤四：继续创造零元素。方法：从未被画去的元素中，找到一个最小的元素k。（1）对行的操作：选择行位势ui，如果行被直线覆盖，则ui=0；如果未被覆盖，ui=k；（2）列的操作：列位势vj，如果列被直

19、线覆盖，vj=-k；如果未被覆盖，vj=0。（3）产生新的效率矩阵：bij= aij -ui-vj,1、最小元素k=2；2、ui依次为2、2、0和2；3、vj依次取为-2、-2、0和0.。,ui,2,2,0,2,vj,-2,-2,0,0,bij= aij -ui-vj,60,步骤五：继续判断零元素是否位于不同行、不同列。方法：首先从行开始试指派，只有一个零元素时，对零元素打括号，并对所在列画直线。而有多个零元素，或零元素已被画去，则转下一行；行分析完毕后，然后从列开始试指派，对每列只有一个零元素时，打括号，并画去其所在的行。,（ ）,（ ）,（ ）,（ ）,最终结果,61,步骤六：获得最后结果。方法：对于打括号的零元素处进行指派，即可获得最短时间。,x13=1（工作一丙） x22=1 （工作二乙） x34=1 （工作三丁） x41=1（工作四甲）,最短时间为：9+4+11+4=28 h。,指派结果,62,4.5.4 极大化的指派问题,对于目标为求极大的指派问题，先要对 效率矩阵进行处理：,（1）找出效率矩阵中的最大值，分别用它去减阵中每一元素，得到新矩阵；,（2）对新得到的矩阵用原匈牙利法求解。,63,64,例、有 4 种机械要分别安装在4个工地，它们 在4个工地的工作效率不同，问应如何指 派，可使