这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。 分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由Land Doig和 Dakin等人提出的。由于这方法灵活且便于用计算机求解,所以现在它已是解 整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂 选址问题、背包问题及分配问题等。 设有最大化的整数规划问题A,与它相应的线性规划为问题B,从解问题B开始, 若其最优解不符合A的整数条件,那么B的最优目标函数必是A的最优目标函数x的 上界,记作;而A的任意可行解的目标函数值将是x的一个下界。分枝定界法就 是将B的可行域分成子区域的方法。逐步减小三和增大〓,最终求到z。现用下例来 例3求解下述整数规划 Max=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0且为整数 解(i)先不考虑整数限制,即解相应的线性规划B,得最优解为: x1=48092,x2=18168,=3558779 可见它不符合整数条件。这时z是问题A的最优目标函数值z的上界,记作三。而 x1=0,x2=0显然是问题A的一个整数可行解,这时二=0,是z的一个下界,记作三 即0≤x≤356。 (ⅱi)因为x,x2当前均为非整数,故不满足整数要求,任选一个进行分枝。设选x1 进行分枝,把可行集分成2个子集 x1≤[48092]=4,x1≥[4.8092]+1=5 因为4与5之间无整数,故这两个子集的整数解必与原可行集合整数解一致。这 一步称为分枝。这两个子集的规划及求解如下 问题B1:Max=40x+90x2 9x1+7x2≤56 7x1+20x,≤70 0≤x1≤4,x,≥0 x2 最优解为:x1=4.0,x2=2.1,=1=349。 问题B2:Max2=40x1+90x2 9x1+7x2≤56 7x1+20x,≤70 x1≥5,x2≥0 最优解为:x1=5.0,x2=1.57,=1=341.4 再定界:0≤x≤349。 (i)对问题B1再进行分枝得问题B1和B12,它们的最优解为-17- 这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。 分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解 整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂 选址问题、背包问题及分配问题等。 设有最大化的整数规划问题 A ，与它相应的线性规划为问题 B ，从解问题 B 开始， 若其最优解不符合 A 的整数条件，那么 B 的最优目标函数必是 A 的最优目标函数 * z 的 上界，记作 z ；而 A 的任意可行解的目标函数值将是 * z 的一个下界 z 。分枝定界法就 是将 B 的可行域分成子区域的方法。逐步减小 z 和增大 z ，最终求到 * z 。现用下例来 说明： 例 3 求解下述整数规划 1 2 Max z = 40x + 90x ⎪ ⎩ ⎪ ⎨ ⎧ ≥ + ≤ + ≤ , 0 且为整数 7 20 70 9 7 56 1 2 1 2 1 2 x x x x x x 解 （i）先不考虑整数限制，即解相应的线性规划 B ，得最优解为： 4.8092, 1.8168, 355.8779 x1 = x2 = z = 可见它不符合整数条件。这时 z 是问题 A 的最优目标函数值 * z 的上界，记作 z 。而 0, 0 x1 = x2 = 显然是问题 A 的一个整数可行解，这时 z = 0 ，是 * z 的一个下界，记作 z ， 即0 356 * ≤ z ≤ 。 （ii）因为 1 2 x , x 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 1 x 进行分枝，把可行集分成 2 个子集： [4.8092] 4 x1 ≤ = ， [4.8092] 1 5 x1 ≥ + = 因为 4 与 5 之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这 一步称为分枝。这两个子集的规划及求解如下： 问题 B1 ： 1 2 Max z = 40x + 90x ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ ≥ + ≤ + ≤ 0 4, 0 7 20 70 9 7 56 1 2 1 2 1 2 x x x x x x 最优解为： 4.0, 2.1, 349 x1 = x2 = z1 = 。 问题 B2 ： 1 2 Max z = 40x + 90x ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≥ + ≤ + ≤ 5, 0 7 20 70 9 7 56 1 2 1 2 1 2 x x x x x x 最优解为： 5.0, 1.57, 341.4 x1 = x2 = z1 = 。 再定界：0 349 * ≤ z ≤ 。 （iii）对问题 B1 再进行分枝得问题 B11和 B12 ，它们的最优解为