数规判 Integer programming(IP) 整数规划问题的求解方法 割平面法 cutting plane approach 构造切割方程的步骤: 1、令x1是相应松驰问题的最优解中为非整数值的一个基变量,由 单纯形表最终表得: X1+∑akxk=b;… (1式) 其中i∈Q(Q指非基变量下标集) k∈K(K指基变量下标集)
11 整数规划 Integer Programming（IP） 整数规划问题的求解方法 割平面法cutting plane approach 构造切割方程的步骤： 1、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由 单纯形表最终表得： xi + ∑aik xk = bi ……………………（1 式） 其中 i ∈Q （Q 指非基变量下标集） k ∈K （K 指基变量下标集）
数规判 Integer programming(IP) 整数规划问题的求解方法 割平面法 cutting plane approach 构造切割方程的步骤: 2、将b1和aik都分解成整数部分N(不超过b的最大整数)与非 负真分数部分f之和,即: b;=N+f1,其中0<f<1 (2式) ak=Nk+fk,其中0≤fk<1 例如:若b=235,则N=2,f=0.35; 若b=-145,则N=-2,f=0.55 12
12 整数规划 Integer Programming（IP） 整数规划问题的求解方法 割平面法cutting plane approach 构造切割方程的步骤： 2、将 bi 和 aik 都分解成整数部分 N （不超过 b 的最大整数）与非 负真分数部分 f 之和，即： bi = Ni + fi ， 其中 0 ＜ fi ＜ 1 ………（2 式） aik = Nik + fik ，其中 0 ≤ fik ＜ 1 例如：若 b = 2.35 ，则 N = 2 ，f = 0.35； 若 b = -1.45 ，则 N = -2 ，f = 0.55
数规判 Integer programming(IP) 整数规划问题的求解方法 割平面法 cutting plane approach 构造切割方程的步骤: 2、将(2式)代入(1式)得: X1+∑Nkxk-N=f1-∑ fik xk (3式) 3、提出变量为整(当然含非负)的条件: 由于(3式)中等式左边需整,而0<f<1,故有 f1-2 fik xk≤0 (4式) 此即为所需切割方程。 13
13 整数规划 Integer Programming（IP） 整数规划问题的求解方法 割平面法cutting plane approach 构造切割方程的步骤： 2、将（2 式）代入（1 式）得： xi + ∑ Nik xk - Ni = fi - ∑ fik xk ……………………（3 式） 3、提出变量为整（当然含非负）的条件： 由于（3 式）中等式左边需整，而 0 ＜ fi ＜ 1 ，故有 fi - ∑ fik xk ≤ 0 ……………………（4 式） 此即为所需切割方程
数规判 Integer programming(IP) 整数规划问题的求解方法 割平面法 cutting plane approach 构造切割方程的步骤: (1)切割方程f-∑fkxk≤0真正进行了切割,至少把非整数最优 解这一点切割掉了。 证明:(反证法)假设松驰问题的最优解X*未被切割掉,则由 f1-∑fkxk≤0,又因为x*k=0,(因x*k为非基变量) 有f≤0,这与f>0矛盾。 (2)不会切割掉任何整数解,因为切割方程是由变量为整的条件 提出的。 14
14 整数规划 Integer Programming（IP） 整数规划问题的求解方法 割平面法cutting plane approach 构造切割方程的步骤： （1）切割方程 fi - ∑ fik xk ≤ 0 真正进行了切割，至少把非整数最优 解这一点切割掉了。 证明：（反证法）假设松驰问题的最优解 X* 未被切割掉，则由 fi - ∑ fik x*k ≤ 0， 又因为 x*k = 0，（因 x*k 为非基变量） 有 fi ≤ 0 ，这与 fi ＞ 0 矛盾。 （2）不会切割掉任何整数解，因为切割方程是由变量为整的条件 提出的
数规判 Integer programming(IP) 整数规划问题的求解方法 割平面法 cutting plane approach 例——一求解 P Max Z=X1+Ⅹ2 X1+Ⅹ2≤1 3X1+Ⅹ2≤4 X1,X2≥0 X1,X2整数 LP Max Z=X+ x2 X1+Ⅹ2≤1 3X1+X2≤4 X1,Ⅹ2≥0 15
15 整数规划 Integer Programming（IP） 整数规划问题的求解方法 割平面法cutting plane approach 例——求解 IP Max Z = X1 + X2 - X1 + X2 ≤ 1 3X1 + X2 ≤ 4 X1 ，X2 ≥ 0 X1 ，X2 整数 LP Max Z = X1 + X2 - X1 + X2 ≤ 1 3X1 + X2 ≤ 4 X1 ，X2 ≥ 0