(数学模型 第三节 整数规划模型的解
第三节 整数规划模型的解
数学模型 例整数规划模型 2 s.t9x1+7x,≤56 7x1+20x,≤70 1,x2≥0 且为整数 345 由①④解得: ,x2=1.817,maxz=355.890 (1)若取整:x1=4,x2=1,=250, 是可行解,但非最优解,因有可行解: x1=4,x2=2,3Z=340>250 (2)按四舍五入得:x1=5,x2=2,不是可行解 因②左边为:5956 用穷举法也是不可取的
例 整数规划模型 max 40x1 90x2 z = + s.t 9x1 + 7x2 56 7x1 + 20x2 70 x1 , x2 0 且为整数 1 2 3 4 5 由 1 — 4 解得: x1 = 4.809, x2 = 1.817, max z = 355.890 （1）若取整： 4, 1, 250, x1 = x2 = z = 是可行解，但非最优解， x1 = 4, x2 = 2, z = 340 250 （2）按四舍五入得： 5, 2, x1 = x2 = 不是可行解 因 2 左边为：59 56 用穷举法也是不可取的。 因有可行解：
分枝定界法 (数学模型 设整数规划模型: inz=∑ (P) st ∑ i5 x1≥0且为整数,j=1,2,…,n 记最优解为X”,最优目标值为z 松弛问题: mnz三 ∑ st ≥0,j=1, 记可行域为S0,最优解为X0,最优目标值为z
一、分枝定界法 设整数规划模型： （P） = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1 = = = xj 0 且为整数， j = 1,2, ,n = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1 = = = 0, xj j = 1,2, ,n 记最优解为 ，最优目标值为 。 X z 松弛问题： （P0） 记可行域为S0 , 最优解为X0 ,最优目标值为z0 。 1 2 3
(数学模型 3 ≤[b2 →X 1,1 若X1整,则剪枝当前上界 0 3 并换上界:z≤x<+0 →Xn,z 0 若X整,则X 3x211+ 若xn=b非整 今X 2942 则分枝 若X2非整,则 且z≤z<+ 若z2>,则剪枝 自然上界 若z2 19 则分枝
0 0 X ,z : P0 1 — 3 • 若 X0 整，则 X = X0 • 若 非整， 则分枝 0 0 xi = bi + z z 且 0 自然上界 S0 0 bi S1 S2 1 1 X ,z P1 : 1 — 3 [ ] 0 0 xi bi 2 2 X ,z P2 : 1 — 3 [ ] 1 0 0 xi bi + 若 X1 整，则剪枝 并换上界： + z 1 z 若 X2 非整，则 • 若 z2 z1 ，则剪枝 • 若 z2 z1 ，则分枝 当前上界
(数学模型 3x≥|bn+1, X 393 若X3整,则剪枝 2 若3<列,则换界z≤3<孔<+ 1若3≥,则不换界 x 3xn2|bn+1, 4七4 若X4非整,则 若4>当前上界,则剪枝 若x4≤当前上界,则分枝 剪完所有枝得:x≤k<…<孔<+ 最小上界对 应的最优解 则 2=z X=X 为所求。 kg k
3 3 X ,z 1 — 3 : P3 xi0 [bi0 ]+ 1, 4 4 X ,z P4 : 1 — 3 xi0 [bi0 ]+ 1, 若 X3 整，则剪枝 • 若 z3 z1 ，则换界 + 1 z z3 z • 若 z3 z1 ，则不换界 若 X4 非整，则 • 若 z4 当前上界，则剪枝 • 若 z4 当前上界，则分枝 剪完所有枝得： + 1 z z z k 则 k X Xk z = z = , 最小上界对 应的最优解 为所求。 P2