整数剡 本章内容重点 √分支定界法 √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