整数剡 本章内容重点 √分支定界法 √0-1规划 √指派问题
本章内容重点 ü分支定界法 ü0-1规划 ü指派问题
问题的提出 在许多线性规划问题中,要求最优解必须取整教。例如 所求的解是机器的台数、人数车辆船只数等,如果所得的 解中决簟变量为分数或小数则不符合实际问题的要求。 对于一个规划问题,如果要求全部决篥变量都取整数 称为纯(或全)整教规划( Pure Integer Linear programming); 如果仅要求部分决变量取整数,称为混合整数规划问题 ( Mixed Integer Linear Programming)有的问题要求决策 变量仅取0或l两个值,称为0-规划问题
在许多线性规划问题中,要求最优解必须取整数。例如 所求的解是机器的台数、人数车辆船只数等，如果所得的 解中决策变量为分数或小数则不符合实际问题的要求。 对于一个规划问题，如果要求全部决策变量都取整数 称为纯(或全)整数规划(Pure Integer Linear Programming); 如果仅要求部分决策变量取整数，称为混合整数规划问题 (Mixed Integer Linear Programming)。有的问题要求决策 变量仅取0或l两个值，称为0-l规划问题
问题的提出 倒4-1:某公司承建一项工程,需要使用某种大型设备,有 A、B两种型号可供选择,若选择用A型1台,需配备司机 和助手各1人,工作一小肘可获利20元;若选择用B型1台, 需配备司机1人,助手3人,工作一小时可获利30元公司 可操作这类火型设备的司机最多可抽调5人,合适的助手 只有6人,如何选用设备可使获利录大? Maxf(x)=20x +30x, M +x≤5 +3x,≤6 x1,x2≥0 B(4.5,0.5) x,x2为整数
例4-1:某公司承建一项工程，需要使用某种大型设备，有 A、B两种型号可供选择，若选择用A型1台，需配备司机 和助手各1人，工作一小时可获利20元；若选择用B型1台， 需配备司机1人，助手3人，工作一小时可获利30元.公司 可操作这类大型设备的司机最多可抽调5人，合适的助手 只有6人，如何选用设备可使获利最大？ ï î ï í ì ³ + £ + £ = + 1 2为整数 1 2 1 2 1 2 1 2 , , 0 3 6 5 ( ) 20 30 x x x x x x x x st Maxf x x x B (4.5,0.5) · · · · · x1 x2 1 2 3 4 5 1 2 3 4 5 6 · · · · · · ·
分支定界法 在20世纪60年代初 Land doig和 Dakin等人提出了分 枚定界渎。由于该方法灵活且便于用计算机求解,所以目 前巳成为解整教规划的重要方法之一。分枚定界法既可用 来解纯整教规划,也可用来解涡合整教规划。 分枝定界法的主要思路是首先求解整数规划的伴随规 划,如果求得的最优解不符合整教条件,则增加新约柬- 縮小可行蜮;将原整数规划问题分枚——分为两个子规 划,再解子规划的伴随规划…,通过求解一糸列子规划的 伴随规划及不断地定界,最后得到原整数规划问题的整教 最优解
在20世纪60年代初 Land Doig 和 Dakin 等人提出了分 枝定界法。由于该方法灵活且便于用计算机求解，所以目 前已成为解整数规划的重要方法之一。分枝定界法既可用 来解纯整数规划，也可用来解混合整数规划。 分枝定界法的主要思路是首先求解整数规划的伴随规 划，如果求得的最优解不符合整数条件，则增加新约束— —缩小可行域；将原整数规划问题分枝——分为两个子规 划，再解子规划的伴随规划……通过求解一系列子规划的 伴随规划及不断地定界，最后得到原整数规划问题的整数 最优解
分支定界法 倒4-2:求解整数规划问题 整数规划问题A 松弛问题B maz=40x1+90x2 maxz=40x+90x 9x1+7x2≤56 9x1+7x,≤56 7x1+20x2≤70 7x+20x,≤70 x,x2≥0且为整数 x,x2≥0 设问题A的最优目标函数值为Z,则问题B的 录优目标函教值必定是问题A的上界,记为Z
例4-2:求解整数规划问题 整数规划问题A 松弛问题B ï î 且为整数 ï í ì ³ + £ + £ = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x ï î ï í ì ³ + £ + £ = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x 设问题A的最优目标函数值为Z* ,则问题B的 最优目标函数值必定是问题A的上界，记为Z
分支定界法 max 2=40x,+90x 不是问题A解 9x1+7x2≤56 7x1+20x2≤70 6 x2≥0 4.81 B 1:x1≤4 3 X 1.82 B 356 B 2:x1≥5 0 2345678910 z=0 2=356
、 、 、 、 、 、 、 、 、 、 、 0 1 2 3 4 5 6 7 8 9 10 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - B 356 1 .82 4 .81 021 === zxx 不是问题A解 z但 £ z * : 4 B1 x 1 £ : 5 B 2 x 1 ³ z = 0 , z = 356 ïîïíì ³ + £ + £ = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x
分支定界法 4.81 x1<4x 1.82 B,:x,=4.00 zo=356 2=2.10 349 x,≥5 B2:x1=5.00 1.57 341 0 349 01234567
0 1 2 3 4 5 6 7 4 3 2 1 B1 349 2 . 10 : 4 . 00 1 2 1 1 = = = z x B x 341 1 .57 : 5 .00 2 2 2 1 = = = z x B x z = 0 z = 349 B 2 356 1 .82 4 .81 0 2 1 = = = z x x 5 x 1 ³ 4 x 1 £
分 不是问题A解 2 4.00 剪枝 x,=2.10 B4:x1=1.42 z,=349 x,=3.00x x2≥3 zA=327 B,:x,=4.00 z=340 2.00 z=341 z3=340 是问题A解 但< 01234567
4 3 2 1 340 2 .00 : 4 .00 3 2 3 1 = = = z x B x 327 3 .00 : 1 .42 4 2 4 1 = = = z x B x 0 1 2 3 4 5 6 7 是问题A解 z 但 z 3 349 2 . 10 : 4 . 00 1 2 1 1 = = = z x B x x2 £ 2 x2 ³ 3 B 4 B 3 不是问题A解 而 剪枝 z £ z 4
分支定界法 B X 5.00 x,=1.57 z=340 341 z,=341 x2≤1 B =5.44B x2=1.00无可行解 308 0 234567
0 1 2 3 4 5 6 7 4321 308 1 .00 : 5 .44 52 5 1 === zx B x 无可行解 : B 6 341 1 .57 : 5 .00 22 2 1 === zx B x x 2 £ 1 x2 ³ 2 B 5
分支定界法 B 4.81 82 2=0,z=356 <4 z0=356 x,≥5 B,1:x,=4.00 B2:x=5.00三=0 x2=2.10 x2=1.572=349 349 z=340 =341 x2<2 ≥3 341 < x,≥2 B3:x1=400B:x1=142B5:x1=5.44B行解 x2=2.00 3.00 x2=1.00无可行 3=340 4=327 308 z=z=340
356 1 . 82 : 4 . 81 0 2 1 = = = z x B x 349 2.10 : 4.00 1 2 1 1 = = = z x B x 341 1.57 : 5.00 2 2 2 1 = = = z x B x 340 2.00 : 4.00 3 2 3 1 = = = z x B x 327 3.00 : 1.42 4 2 4 1 = = = z x B x z = 0 , z = 356 349 0 = = z z 341 340 = = z z x1 £ 4 5 x1 ³ 2 x 2 £ 3 x 2 ³ 308 1 .00 : 5 .44 5 2 5 1 = = = z x B x 无可行解 : B 6 x2 £ 1 x 2 ³ 2 340 * z = z =