运筹学整数规划

第5章整数规划主讲人：晋琳琳学习内容整数规划的数学模型及解分枝定界法割平面法0－1型整数规划指派问题整数规划的例子例5.1（p94）货物体积重量利润甲19542乙273403托运限制1365140设：x1，x2分别为甲、乙两种货物托运的件数，建立模型如右：整数规划的例子例5.2（p73）时段12345678服务员最少数目10x18x29x311x413x5853整数规划的数学模型及解的特点要求一部分或全部决策变量必须取整数值的规划问题称为整数规划在整数规划中去掉取整数的约束，剩下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题若整数规划的松弛问题是线性规划，则称该整数规划为整数线性规划整数线性规划的数学模型松弛问题整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。

0－1整数规划：所有决策变量只能取0或1两个整数。整数线性规划问题解的特点整数规划的可行解集合是它的松弛问题可行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束，则它也是整数规划的可行解整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到松弛问题最优解整数规划最优解不能通过舍入取整地方法，由松弛问题的解得到整数规划的最优解按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集。

因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（4，2）点为最大值，Z=12。

目前，常用的求解整数规划的方法有：

分支定界法和割平面法对于特别的0－1规划问题采用隐枚举法和匈牙利法。0-1型整数规划0-1变量：只能取值0或1的变量。0-1变量也称为逻辑变量。它常用来表示两个选项中非此即彼的选择。如P是一个方案，则类似，设A1，A2，A3是三个方案，则可以用(x1,x2,x3)=(0,1,1)表示采用方案A2,A3但不用方案A1，(x1,x2,x3)=(1,0,1)表示采用方案A1,A3但不用方案A2再比如x1+x2+x3=1表示方案A1,A2,A3中恰好采用一个x1+x2+x3≤2表示方案A1,A2,A3中最多采用两个x1+x2+x3≥2表示方案A1,A2,A3中至少采用两个x1≥x3表示如果采用方案A3,则必采用方案A1••••••含有相互排斥的约束条件的问题设工序B的每周工时约束为假设工序B还有一种新的加工方式，相应的每周工时约束为如果工序B只能从两种加工方式中选择其中一种，那么上面两式就是互为排斥的两个约束条件。为了表示在这两个约束条件之间进行的选择，可以引入如下的0-1变量：y1=0，若工序B采用了原加工方式1，若工序B不采用了原加工方式y2=0，若工序B采用了新加工方式1，若工序B不采用了新加工方式和于是两个互斥的约束条件可以下述三个约束条件统一起来：其中M1与M2都是形式上的大正数。一般地，要从p个约束条件中恰好选择q个条件，则可以引入0-1变量：yi=0，若选择了第i个约束条件1，若不选择了第i个约束条件(i=1,…,p)于是采用下列约束条件组就可以达到目的：工件排序问题（p138）产品1产品2产品3a11机床1a13机床3a14机床4a21机床1a22机床2a24机床4a32机床2a33机床31同一件产品在不同机床上的加工顺序同一件产品在下一台机床上加工的开始时间不得早于在上一台机床上加工的结束时间xij表示第i种产品在第j台机床上加工的开始时间。产品1：x11+a11x13

及x13+a13x14产品2：x21+a21x22

及x22+a22x24产品3：x32+a32x332每台机床对不同产品的加工顺序约束一台机床在工作中，若已开始的加工还未结束，则不能开始加工另一产品。注意到每台机床可以加工两种产品。因此可以用0-1变量yi表示第i台机床加工产品的顺序。具体表示y1y2y3y40先加工产品11先加工产品20先加工产品21先加工产品30先加工产品11先加工产品30先加工产品11先加工产品2机床1x11+a11x21+My1及x21+a21x11+M(1-y1)机床2x22+a22x32+My2及x32+a32x22+M(1-y2)机床3x13+a13x33+My3及x33+a33x13+M(1-y3)机床4x14+a14x24+My4及x24+a24x14+M(1-y4)3产品2的加工总时间约束产品2加工开始的时间是x21，结束加工的时间是x24+a24，于是x24+a24–x21d4目标函数的建立设全部产品加工结束时间为W。由于三件产品的加工结束时间分别为x14+a14,x24+a24,x33+a33故W=max(x14+a14,x24+a24,x33+a33)根据问题的要求，目标函数为minz=W满足Wx14+a14Wx24+a24Wx33+a33从而最后得到p140的混合整数线性规划模型0-1型整数规划问题的解法枚举法：列出变量取值为0或1的可能的组合（若有n个变量则有2n个组合），再逐一验证它们是否满足约束条件，然后对满足约束条件的可行解计算目标函数值，其中目标函数值最优的就是最优解方法的改进：通过设置过滤条件有效地减少验证组合为可行解的次数。(x1,x2,x3)zABCD过滤条件(0,0,0)(0,0,1)05YYYYYYYY(0,1,0)-2YYYY(0,1,1)3YNYY(1,0,0)3YYYY(1,0,1)8YYYY(1,1,0)1YNYY(1,1,1)6YNYYz≥0z≥5z≥8(x1,x2,x3)zABCD过滤条件(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)05-233816YYYYYYYYYYYYz≥0z≥5z≥8指派问题指派问题的标准形式有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一指派方案，使完成这n件事的总费用最小。标准形式的特点：每个人必须承担也仅承担一项任务，每项任务必须有人承担承担任务的人数与任务数相同目标函数最小化对何人做何事没有限制指派问题数学模型若引入如下的0-1型变量则数学模型为每个人必须承担也只能承担一项工作每项工作必须指派给一人也只能指派给一人明显地不同的n阶指派问题，有相同的可行解。但最优解可能不同。区别在于它们目标函数的系数不同。称指派问题的目标函数系数构成的矩阵为系数矩阵。指派问题的解可以用矩阵表示：若矩阵X是指派问题的一个可行解，则它的每一行恰好有一个元素等于1其余元素为零，每一列也恰好有一个元素等于1其余元素为零。因此指派问题有n!个可行解。例（p143）B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106

系数矩阵：系数矩阵的性质系数矩阵C=(cij)的某行（列）各元素分别减去一个常数k，得到一个新的矩阵C'=(c'ij)，则以C'和C为系数矩阵的两个指派问题有相同的最优解匈牙利解法（1）变换系数矩阵：使变换后的矩阵各行各列出现零元素4766601300减去每行最小者减去每列最小者匈牙利解法（2）确定独立的零元素若独立零元素的个数小于矩阵的阶数，转下一步，否则按独立零元素进行指派对有唯一零元素的行（列），将零元素圈起来，再划去其所在列（行）的其他零元素匈牙利解法（3）用最少的直线覆盖所有的零元素对没有独立零元素的行打“√”在已打“√”行中，选择划去零元素的列打“√”在已打“√”列中，选择圈住了的零元素的行打“√”用线条覆盖没打“√”的行和已打“√”的列匈牙利解法（4）继续变换矩阵，使其中出现新的零元素选择没有被覆盖的元素中最小的元素；没有被覆盖的元素减去这一最小的元素，位于直线交叉处的元素加上这个最小的元素匈牙利解法（5）重新确定独立零元素最优指派方案：A1→B3,A2→B2,A3→B1,A4→B4,A5→B5。按照此方案指派费用最少，为7+9+6+6+6=34注：匈牙利解法是一反复迭代的过程非标准形式的指派问题非标准形式的指派问题可以化为标准形式的指派问题求解非标准形式的指派问题（1）最大化指派问题：设最大化指派问题的系数矩阵为C=(cij)，其中最大元素为m，构造矩阵B=(bij)=(m-cij)，则以B为系数矩阵的最小化指派问题与以C为系数矩阵的原最大化指派问题有相同的最优解非标准形式的指派问题（2）人数和事数不等的指派问题：若人少事多，则添上一些虚拟的“人”，使得人数与事数相等，而虚拟的“人”承担各事的费用为零若人多事少，则添加一些虚拟的事，使人数与事数相等，各人做虚拟的“事”的费用为零非标准形式的指派问题（3）一个人可做几件事的指派若某人可做几件事，则可将此人看作相同的几个“人”，这几个“人”做同一件事的费用相同非标准形式的指派问题（4）某事一定不能由某人承担若某事一定不能由某人来做，则可取此人承担该件事的费用为M例如：人多事少的情形，若某人必须承担工作任务，则此人承担虚拟的“事”的费用为M；类似地，在人少事多的情形，若某项工作必须完成，则虚拟的“人”做该工作的费用为M非标准形式的指派问题—例（p147例13）B1B2B3B4B54871512A179171410A2691287A34871512A1’79171410A2’691287A3’B600000048715120487151207917141007917141006912870691287000075