第5章 整数规划 (1).ppt

第五章 整数规划,内容： 分支定界法 割平面法 0-1型整数规划,学习目标,了解整数规划决策问题的特点； 熟悉分枝定界法和割平面法的原理及其应用； 掌握0－1规划及其求解方法——枚举法； 会用匈牙利法求解工作指派问题整数规划的概念,问题的提出：决策问题中变量经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？ 整数规划：决策变量要求取整数的线性规划例1：线性规划问题 Max Z=38x1+81x2 18x1+40x2≥237 8x1-8x2≤23 x1,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元，如何装运获利最多？ Max Z=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1.x2 ≥0且为整数 解此LP问题，得：x1=4.8，x2=0 显然不是可行解,整数规划图解法,,,x1,,,,,,,,1 2 3 4 5 6 7,2,3,1,,,,,,,,,,,,,B,A,Return,x2,图解法的启示,A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解 纯整数规划的可行解就是可行域中的整数点 非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化 IP问题的最优解不优于LP问题的最优解,,例3：背包问题 有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。

第i种物品每件重量为wi公斤，价值为vi元每种物品各取多少件装入背包，使其中物品的总价值最高设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为,,这个问题如果用线性规划求解，k个变量中将只有一个基变量大于0，其余k-1个非基变量都等于0，而且这个大于0的基变量一般情况下是非整数这样的解显然是没有意义的例如以下一个背包问题：,线性规划最优解为 x1=0，x2=50/42，x3=0 而整数规划的最优解是 x1=1，x2=0，x3=2整数规划的分类 纯整数规划：指全部决策变量均要求取整数的线性规划； 混合整数规划：指只有部分决策变量要求取整数的线性规划；,,整数规划的性质 可行解域为离散点集； 整数最优解的目标值：劣于同问题非整数最优解的目标值（即去掉决策变量取整数这一约束） 不能简单地将非整数最优解用四舍五入的办法凑成整数解，也不能取与非整数最优解靠得最近的整数解整数规划的求解 分枝定界法 割平面法 隐枚举法等分枝定界法,分枝定界法对原问题的可行域的非整数区域进行切割，且切割的区域与坐标轴相平行；切割方法是对取非整数的相邻整数作附加约束，且约束方程简单分枝定界法,思路：切割可行域，去掉非整数点。

一次分枝变成两个可行域，分别求最优解 例. maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1、x2 ≥0且为整数 解：先不考虑整数要求，解相应的LP问题，得：x1=4.8，x2=0，Z=9600不是可行解 Z=9600是IP问题的上界，记为：Z=9600,,,x2,,,x1,,,,,,,,1 2 3 4 5 6 7,2,3,1,,,,,,,,,,,,,B,A,分枝定界法（续）,x1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1 ≤4和x1 ≥5 原问题分解为两个,IP2： Max Z=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1 ≥5 x1，x2 ≥0且为整数,IP1： Max Z=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1 ≤4 x1，x2 ≥0且为整数,分枝定界法（续）,不考虑整数要求，解相应LP问题 解IP1得：x1=4 ,x2=1 z=9000 解IP2得：无可行解 此时可以断定IP问题的下界为9000，记为Z=9000 ٭由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。

由于Z=Z，此时已得IP问题的最优解，即x1=4, x2=1, Z=9000,,IP0: x1=4.8,x2=0 Z=9600,IP1: x1=4,x2=1, Z=9000,IP2: 无可行解,,,,,x1≤4,x1≥5,Z=0,Z=9600,,,Z=Z=9000=Z*,,,分枝定界法的求解步骤如下：,第一步：求相应线性规划问题的最优解： 如果所得的最优解满足原问题的取整条件，则计算结束否则，从不满足整数条件的基变量中任选一下xk进行分枝； 第二步：分枝： 构造两个新的约束条件： xk≤[xk]和xk≥[xk] +1 其中，表示不超过的最大整数将这两个约束条件分别加进原相应问题的约束条件中去，形成两个子问题，或两个分枝，解这两个子问题；,,第三步：定界 把满足整数条件的各分枝的最优目标函数值中的最优值作为上（下）界值，用它来判别分枝是保留还是剪枝； 第四步：剪枝： 把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止例：求解问题L0： Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0且为整数,,解：L0对应的线性规划问题为： L1: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0 用单纯形法，求得最优解为： x1=4.809, x2=1.817, Z1=355.9,,,2,4,6,8,10,2,6,4,8,10,,,7x1+20x2=70,9x1+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: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1≤4 x1,x2≥0,L3: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1≥ 5 x1,x2≥0,2,4,6,8,10,2,6,4,8,10,,,7x1+20x2=70,9x1+7x2=56,,,,,,,,,,,,,,,,,,分别求解问题L2和问题L3，得,问题：L2 x1=4,x2=2.1 Z2=349,问题：L3 x1=5,x2=1.571 Z3=341.39,显然没有得到全部变量是整数的解 由于Z2Z3，故将Z改为349，而Z仍为0,,,继续对问题L2和L3进行分解在问题L2中增加约束条件x2≤2，得问题L4： L4: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1≤4 x2≤2 x1,x2≥0,在问题L2中增加约束条件x2 ≥3，得问题L5： L5: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1≤4 x2 ≥3 x1,x2≥0,解问题L4，得 ： x1=4,x2=2 Z4=340,解问题L5，得 ： x1=1.428,x2=3 Z5=327.12,2,4,6,8,10,2,6,4,8,10,,,7x1+20x2=70,9x1+7x2=56,,,,,,,由于问题L4已经得到整数解，因此Z改为340。

问题L5的最优解Z5Z，所以必须继续分解，得以下两个分枝：,,,,继续对问题L2和L3进行分解在问题L3中增加约束条件x2≤1，得问题L6： L6: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1 ≥5 x2≤1 x1,x2≥0,在问题L2中增加约束条件x2 ≥2，得问题L7： L7: Max Z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1≤5 x2 ≥2 x1,x2≥0,解问题L6，得 x1=5.444, x2=1 Z6=307.76,解问题L7，无可行解,,由于Z6Z，所以也予以“剪枝” 到此，我们可以确定，原问题的最优整数解为： x1=4, x2=2, Z*=Z4=340,求解过程示意图,L1： x1=4.809 x2=1.817 Z1=355.9,L2： x1=4 x2=2.1 Z2=349,L3： x1=5 x2=1.517 Z3=341.39,L4： x1=4 x2=2 Z4=340,L5： x1=1.428 x2=3 Z5=327.12,L6： x1=5.444 x2=1 Z6=307.76,L7： 无可行解,,,,,,,,,,,,,Z=0,Z=355.9,Z=0,Z=349,Z=340,Z=341.39,Z=Z=340,,,,,,,,,x1≤4,x1≥5,x2≤2,x2≥3,x2≥2,x2≤1,得最优解：x1=4,x2=2,Z*=Z4=340,L0：,问：如果L2中的x2=2 or 3…，结果如何？,,如果用分枝定界法求解混合整数规划，则分枝的过程只针对有整数要求的变量进行，而不管连续变量的取值如何。

其整个求解过程与纯整数规划的求解过程基本相同割平面法,分枝定界法是对原问题可行解域进行切割，但子问题却由于分枝的增多而呈指数增长为了克服这个缺点，割平面法采用另一种切割可行解域的办法： 既要切割掉非整数解域，又不希望对问题进行分枝割平面法的计算步骤,第一步：先不考虑整数约束，变成一般的LP问题，用单纯形法求其最优解，记为X0*； 第二步：若求得的最优解X0*刚好就是整数解，则该整数解就是原整数规划的最优解，否则，转下步；,第三步：寻求附加约束，即割平面方程： (1) 从最优化表中抄下非整数解的约束方程： xi+Σaikxk=bi，其中bi是基变量xi的非整数解； (2) 将该约束方程所有系数和常数分解为整数N和正真分数f之和： xi+Σ(Nik+fik)xk= Nbi+fbi (3) 整系数项归写于方程左边，真分数项写于右边： xi+ΣNik xk - Nbi = fbi -Σfik xk (4) 考虑整数条件约束以上方程左边为整数，右边的Σfik xk 为非负数， fbi 为不大于1的正小数，又方程右边必是整数，故方程右边满足：fbi -Σfik xk０这就是所求的割平面方程第四步：将割平面方程标准规范化： -(Σfik xk)+xi,k+1=-fbi 加入原最优表中，用对偶单纯形法求新的最优解； 第五步：重复第三、四步直至获得原问题的最优整数解为止。

具体例子见DOC文档0-1规划与隐枚举法,0-1概念： 0-1规划：决策变量只取０，１两个数的整数规划１，０分别表示方案的取舍例：某公司对三个项目进行投资，根据预算，前两年每年可投资6万元，后两年每年可投资7万元三个项目每年需投资额和纯利润见下表，问对哪几个项目进行投资，可获得最大利润令xj=1或0，其分别表示对项目j进行投资或不投资(j=1,2,3)，则该问题的数学模型如下： Max Z=1。