第5章 整数规划 (1)

第五章整数规划内容：分支定界法割平面法0-1型整数规划学习目标•了解整数规划决策问题的特点；•熟悉分枝定界法和割平面法的原理及其应用；•掌握0－1规划及其求解方法——枚举法；•会用匈牙利法求解工作指派问题。整数规划的概念•问题的提出：决策问题中变量经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？•整数规划：决策变量要求取整数的线性规划。•例1：线性规划问题MaxZ=38x1+81x218x1+40x2≥2378x1-8x2≤23x1,x2≥0,且为整数•不考虑整数约束条件，利用单纯形法，可求得最优解为：•x1=6.069,x2=3.194,Z=489.336•如果化整，得整数解：–取x1=6,x2=3，则不满足第二个约束条件；–取x1=6,x2=4，则不满足第一个约束条件；–取x1=5,x2=3是可行解，但目标函数值为433，与可行解x1=2,x2=5的目标值481相差很大大。•例2：某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？•MaxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数•解此LP问题，得：x1=4.8，x2=0显然不是可行解整数规划图解法x11234567231BAReturnx2图解法的启示•A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解•纯整数规划的可行解就是可行域中的整数点•非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化•IP问题的最优解不优于LP问题的最优解•例3：背包问题•有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。•设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为maxz=v1x1+v2x2+…+vkxks.t.w1x1+w2x2+…+wkxk≤Wx1,x2,…xk≥0x1,x2,…xk为整数•这个问题如果用线性规划求解，k个变量中将只有一个基变量大于0，其余k-1个非基变量都等于0，而且这个大于0的基变量一般情况下是非整数。这样的解显然是没有意义的。例如以下一个背包问题：maxz=17x1+72x2+35x310x1+42x2+20x3≤50s.t.x1,x2,x3≥0x1,x2,x3为整数线性规划最优解为x1=0，x2=50/42，x3=0而整数规划的最优解是x1=1，x2=0，x3=2。•整数规划的分类–纯整数规划：指全部决策变量均要求取整数的线性规划；–混合整数规划：指只有部分决策变量要求取整数的线性规划；•整数规划的性质–可行解域为离散点集；–整数最优解的目标值：劣于同问题非整数最优解的目标值（即去掉决策变量取整数这一约束）–不能简单地将非整数最优解用四舍五入的办法凑成整数解，也不能取与非整数最优解靠得最近的整数解。•整数规划的求解–分枝定界法–割平面法–隐枚举法等。分枝定界法•分枝定界法对原问题的可行域的非整数区域进行切割，且切割的区域与坐标轴相平行；切割方法是对取非整数的相邻整数作附加约束，且约束方程简单。分枝定界法•思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解•例.maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1、x2≥0且为整数解：先不考虑整数要求，解相应的LP问题，得：x1=4.8，x2=0，Z=9600不是可行解Z=9600是IP问题的上界，记为：Z=9600x2x11234567231BA分枝定界法（续）•x1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1≤4和x1≥5•原问题分解为两个IP2：MaxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1≥5x1，x2≥0且为整数IP1：MaxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1≤4x1，x2≥0且为整数分枝定界法（续）•不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=9000解IP2得：无可行解此时可以断定IP问题的下界为9000，记为Z=9000٭由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=9000IP0:x1=4.8,x2=0Z=9600IP1:x1=4,x2=1,Z=9000IP2:无可行解x1≤4x1≥5Z=0,Z=9600Z=Z=9000=Z*分枝定界法的求解步骤如下：•第一步：求相应线性规划问题的最优解：–如果所得的最优解满足原问题的取整条件，则计算结束。否则，从不满足整数条件的基变量中任选一下xk进行分枝；•第二步：分枝：–构造两个新的约束条件：xk≤[xk]和xk≥[xk]+1–其中，表示不超过的最大整数。将这两个约束条件分别加进原相应问题的约束条件中去，形成两个子问题，或两个分枝，解这两个子问题；•第三步：定界–把满足整数条件的各分枝的最优目标函数值中的最优值作为上（下）界值，用它来判别分枝是保留还是剪枝；•第四步：剪枝：–把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。•例：求解问题L0：•MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0且为整数•解：L0对应的线性规划问题为：•L1:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0•用单纯形法，求得最优解为：•x1=4.809,x2=1.817,Z1=355.92468102648107x1+20x2=709x1+7x2=56•由于原问题的目标函数最大值Z*绝对不会比Z1更大，所以原问题的上界为：Z=Z1=355.9•又我们可以看出，原问题有整数解x1=x2=0所以原问题的下界为：Z＝0•从而有：0=Z≤Z*≤Z=355.9•现从L1的最优解中，任选一个不符合整数条件的变量，例如，选x1=4.809。因为x1的最优整数解只可能是x1≤4或x1≥5，而绝不会在4～5之间。在问题L1上增加约束条件x1≤4，构成一个分枝——问题L2；在问题L1上增加约束条件x1≥5，构成另一个分枝——问题L3，即有：L2:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≤4x1,x2≥0L3:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≥5x1,x2≥02468102648107x1+20x2=709x1+7x2=56•分别求解问题L2和问题L3，得问题：L2x1=4,x2=2.1Z2=349问题：L3x1=5,x2=1.571Z3=341.39•显然没有得到全部变量是整数的解。•由于Z2Z3，故将Z改为349，而Z仍为0•继续对问题L2和L3进行分解。在问题L2中增加约束条件x2≤2，得问题L4：L4:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≤4x2≤2x1,x2≥0在问题L2中增加约束条件x2≥3，得问题L5：L5:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≤4x2≥3x1,x2≥0解问题L4，得：x1=4,x2=2Z4=340解问题L5，得：x1=1.428,x2=3Z5=327.122468102648107x1+20x2=709x1+7x2=56•由于问题L4已经得到整数解，因此Z改为340。问题L5的最优解Z5Z，所以没有必要再分解L5，即剪枝。•对于问题L3来说，因为Z3Z，所以必须继续分解，得以下两个分枝：•继续对问题L2和L3进行分解。在问题L3中增加约束条件x2≤1，得问题L6：L6:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≥5x2≤1x1,x2≥0在问题L2中增加约束条件x2≥2，得问题L7：L7:MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≤5x2≥2x1,x2≥0解问题L6，得x1=5.444,x2=1Z6=307.76解问题L7，无可行解•由于Z6Z，所以也予以“剪枝”•到此，我们可以确定，原问题的最优整数解为：x1=4,x2=2,Z*=Z4=340求解过程示意图L1：x1=4.809x2=1.817Z1=355.9L2：x1=4x2=2.1Z2=349L3：x1=5x2=1.517Z3=341.39L4：x1=4x2=2Z4=340L5：x1=1.428x2=3Z5=327.12L6：x1=5.444x2=1Z6=307.76L7：无可行解Z=0,Z=355.9Z=0,Z=349Z=340,Z=341.39Z=Z=340x1≤4x1≥5x2≤2x2≥3x2≥2x2≤1得最优解：x1=4,x2=2,Z*=Z4=340L0：问：如果L2中的x2=2or3…，结果如何？•如果用分枝定界法求解混合整数规划，则分枝的过程只针对有整数要求的变量进行，而不管连续变量的取值如何。其整个求解过程与纯整数规划的求解过程基本相同。割平面法•分枝定界法是对原问题可行解域进行切割，但子问题却由于分枝的增多而呈指数增长。为了克服这个缺点，割平面法采用另一种切割可行解域的办法：–既要切割掉非整数解域，又不希望对问题进行分枝。割平面法的计算步骤•第一步：先不考虑整数约束，变成一般的LP问题，用单纯形法求其最优解，记为X0*；•第二步：若求得的最优解X0*刚好就是整数解，则该整数解就是原整数规划的最优解，否则，转下步；•第三步：寻求附加约束，即割平面方程：–(1)从最优化表中抄下非整数解的约束方程：xi+Σaikxk=bi，其中bi是基变量xi的非整数解；–(2)将该约束方程所有系数和常数分解为整数N和正真分数f之和：xi+Σ(Nik+fik)xk=Nbi+fbi–(3)整系数项归写于方程左边，真分数项写于右边：xi+ΣNikxk-Nbi=fbi-Σfikxk–(4)考虑整数条件约束。以上方程左边为整数，右边的Σfikxk为非负数，fbi为不大于1的正小数，又方程右边必是整数，故方程右边满足：fbi-Σfikxk０。这就是所求的割平面方程。•第四步：将割平面方程标准规范化：-(Σfikxk)+xi,k+1=-fbi–加入原最优表中，用对偶单纯形法求新的最优解；•第五步：重复第三、四步直至获得原问题的最优整数解为止。•具体例子见DOC文档。0-1规划与隐枚举法•0-1概念：–0-1规划：决策变量只取０，１两个数的整数规划。１，０分别表示方案的取舍。•例：某公司对三个项目进行投资，根据预算，前两年每年可投资6万元，后两年每年可投资7万元。三个项目每年需投资额和纯利润见下表，问对哪几个项目进行投资，可获得最大利润。投资年度每项投资额总投资额IIIIII1234054541-2222336677纯利润171016•令xj=1或0，其分别表示对项目j进行投资或不投资(j=1,2,3)，则该问题的数学模型如下：MaxZ=17x1+10x2+16x3S.t.0x1+4x2+2x3≤65x1+x2+2x3≤64x1-2x2+3x3≤75x1+2x2+3x3≤7xj=0or1(j=1,2,3)Return•显枚举法–列出所有组合，求出满足约束条件，且使目标函数值最优的组合，即为最优解。•例：求解下列0-1规划问题：MaxZ=3x1-2x2+5x3x1+2x2-x32x1+4x2+x34S.t.x1+x234x2+x36x1,x2,x3=0or1可知，最优解为：X*=(1,0,1)，MaxZ=8(x1,x2,x3)约束条件满足条件？Z值(1)(2)(3)(4)(0,0,0)00000(0,0,1)-