由上例看出,将其相应的线性规划的最 优解“化整”来解原整数线性规划,虽 是最容易想到的,但常常得不到整数线 性规划的最优解,甚至根本不是可行解。 因此有必要对整数线性规划的解法进行 专门研究
• 由上例看出，将其相应的线性规划的最 优解“化整”来解原整数线性规划，虽 是最容易想到的，但常常得不到整数线 性规划的最优解，甚至根本不是可行解。 因此有必要对整数线性规划的解法进行 专门研究
第2节分支定界解法 在求解整数线性规划时,如果可行域是有界 的,首先容易想到的方法就是穷举变量的所 有可行的整数组合,就像在图5-1中画出所有 “+〃"号的点那样,然后比较它们的目标函数 值以定出最优解。对于小型的问题,变量数 很少,可行的整数组合数也是很小时,这个 方法是可行的,也是有效的
第2节 分支定界解法 • 在求解整数线性规划时，如果可行域是有界 的，首先容易想到的方法就是穷举变量的所 有可行的整数组合，就像在图5-1中画出所有 “+”号的点那样，然后比较它们的目标函数 值以定出最优解。对于小型的问题，变量数 很少，可行的整数组合数也是很小时，这个 方法是可行的，也是有效的
在例1中,变量只有x;和x2 由条件②,x所能取的整数值为0、1、2、3、4共5 个;由条件③,x2所能取的整数值为0、1、2共3个, 它的组合(不都是可行的)数是3×5=15个,穷举法还 是勉强可用的。对于大型的问题,可行的整数组合 数是很大的。例如在本章第5节的指派问题(这也是 整数线性规划)中,将n项任务指派n个人去完成,不 同的指派方案共有n!种,当n=10,这个数就超过300 万;当n=20,这个数就超过2×1018,如果一一计算 就是用每秒百万次的计算机,也要几万年的功夫, 很明显,解这样的题,穷举法是不可取的。所以我 们的方法一般应是仅检查可行的整数组合的一部分, 就能定出最优的整数解。分支定界解法( branch and bound me thod就是其中的
在例1中，变量只有x1和x2 • 由条件②，x1所能取的整数值为0、1、2、3、4共5 个；由条件③，x2所能取的整数值为0、1、2共3个， 它的组合(不都是可行的)数是3×5=15个，穷举法还 是勉强可用的。对于大型的问题，可行的整数组合 数是很大的。例如在本章第5节的指派问题(这也是 整数线性规划)中，将n项任务指派n个人去完成，不 同的指派方案共有n!种，当n=10，这个数就超过300 万；当n=20，这个数就超过2×1018，如果一一计算， 就是用每秒百万次的计算机，也要几万年的功夫， 很明显，解这样的题，穷举法是不可取的。所以我 们的方法一般应是仅检查可行的整数组合的一部分， 就能定出最优的整数解。分支定界解法(branch and bound method)就是其中的一个
分支定界法可用于解纯整数或混合的整数线性规划问 题。在20世纪60年代初由 Land doi g和 Dakin等人提出 由于这方法灵活且便于用计算机求解,所以现在它已 是解整数线性规划的重要方法。设有最大化的整数线 性规划问题A,与它相应的线性规划为问题B,从解问 题B开始,若其最优解不符合A的整数条件,那么B的 最优目标函数必是A的最优目标函数z*的上界,记作 而A的任意可行解的目标函数值将是z*的一个下界。 分支定界法就是将B的可行域分成子区域(称为分支) 的方法,逐步减小和增大,最终求到z*。现用下例来 说明:
• 分支定界法可用于解纯整数或混合的整数线性规划问 题。在20世纪60年代初由Land Doig和Dakin等人提出。 由于这方法灵活且便于用计算机求解，所以现在它已 是解整数线性规划的重要方法。设有最大化的整数线 性规划问题A，与它相应的线性规划为问题B，从解问 题B开始，若其最优解不符合A的整数条件，那么B的 最优目标函数必是A的最优目标函数z *的上界，记作； 而A的任意可行解的目标函数值将是z *的一个下界。 分支定界法就是将B的可行域分成子区域(称为分支) 的方法，逐步减小和增大，最终求到z * 。现用下例来 说明：
例2 求解A maxz=40x1+90x2① 9x,+7X≤56 7x1+20x2≤70 ③(5.2) x1,xn≥0 x1,x,整数
例 2 • 求解A max z=40x1 +90x2 ① 9x1 +7x2≤56 ② 7x1 +20x2≤70 ③ (5.2) x1，x2≥0 ④ x1，x2整数 ⑤