第1节整数线性规划问题的提出 令容易求得相应的线性规划问题的最优解为 x1=4.8,x2=0,max=96 z=96 C 1234567 清华大学出版社
清华大学出版社 7 第1节 整数线性规划问题的提出 ❖ 容易求得相应的线性规划问题的最优解为 x1=4.8，x2=0，max z=96
第1节整数线性规划问题的提出 令现在来分析上述线性规划问题的最优解是否是整数规 划问题的最优解 因为x1表示的是托运甲种货物的箱数,目前得到的最优解不 是整数,所以不合条件⑤的要求 o是不是可以把所得的非整数最优解经过“化整”就可得到合 于条件⑤的整数最优解呢? 口如将x1-48,x2=0)凑整为(x1=5,x2=0),这样就破坏了条件② (关于体积的限制),因而它不是可行解 口如将(x1=48,x2=0)舍去尾数0.8,变为(x4,x2=0),这当然满 足各约束条件,因而是可行解,但不是最优解,因为当x=4, x2=0,时z80;而当x=4,x2=1(这也是可行解)时,z90 清华大学出版社
清华大学出版社 8 第1节 整数线性规划问题的提出 ❖ 现在来分析上述线性规划问题的最优解是否是整数规 划问题的最优解 因为x1表示的是托运甲种货物的箱数，目前得到的最优解不 是整数，所以不合条件⑤的要求。 是不是可以把所得的非整数最优解经过“化整”就可得到合 于条件⑤的整数最优解呢? 如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件② (关于体积的限制)，因而它不是可行解； 如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满 足各约束条件，因而是可行解，但不是最优解，因为当x1=4， x2=0, 时z=80；而当x1=4，x2=1(这也是可行解)时，z=90
第1节整数线性规划问题的提出 本例还可以用图解法来说明。见图5-1 01234567 图51 图中画(+)号的点表示可行的整数解。凑整得到的(5,0)点不在可行域内, 而C点又不合于条件⑤。为了满足题中要求,表示目标函数的z的等值线 必须向原点平行移动,直到第一次遇到带“+”号B点(x=4,x2=1)为止。 这样,z的等值线就由z96变到z90,它们的差值为△z=96-90=6,表示 利润的降低,这是由于变量的不可分性(装箱)所引起的。 清华大学出版社
清华大学出版社 9 第1节 整数线性规划问题的提出 本例还可以用图解法来说明。见图 5-1 图中画(+)号的点表示可行的整数解。凑整得到的(5，0)点不在可行域内， 而C点又不合于条件⑤。为了满足题中要求，表示目标函数的z的等值线 必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。 这样，z的等值线就由z=96变到z=90，它们的差值为Δz=96-90=6，表示 利润的降低，这是由于变量的不可分性(装箱)所引起的。 图5-1
第1节整数线性规划问题的提出 令由上例看出,将其相应的线性规划的最优解经过“化整” 来解原整数线性规划,虽是最容易想到的,但常常得不 到整数线性规划的最优解,甚至根本不是可行解。因此 有必要对整数线性规划的解法进行专门研究。 清华大学出版社
清华大学出版社 10 第1节 整数线性规划问题的提出 ❖ 由上例看出，将其相应的线性规划的最优解经过“化整” 来解原整数线性规划，虽是最容易想到的，但常常得不 到整数线性规划的最优解，甚至根本不是可行解。因此 有必要对整数线性规划的解法进行专门研究
第2节分支定界解法 令在求解整数线性规划时,如果可行域是有界的,首先容 易想到的方法就是穷举所有可行的整数解,即列出图5-1 中所有标有“+〃的整数点,然后比较它们的目标函数值, 从而确定最优解。 对于规模较小的问题,变量个数很少,可行解的组合数 也较小时,这个方法是可行的,也是有效的。 o如在例1中,变量只有x和x。由条件②,x所能取的整数值为0 为 个。因此所有可能的整数组合(不都是可行的)数是3×5=15个, 穷举法还是勉强可用的。 令对于大型问题,可行的整数组合数会很大 例如在指派问题中,将n项任务指派n个人去完成,不同的指派 方案共有n!种,当n=10时,可能的指派方案数超过300万;当 n=20,超过2×108。显然,穷举法是不可取的。 清华大学出版社
清华大学出版社 11 第2节 分支定界解法 ❖ 在求解整数线性规划时，如果可行域是有界的，首先容 易想到的方法就是穷举所有可行的整数解，即列出图5-1 中所有标有“+”的整数点，然后比较它们的目标函数值， 从而确定最优解。 ❖ 对于规模较小的问题，变量个数很少，可行解的组合数 也较小时，这个方法是可行的，也是有效的。 如在例1中，变量只有x1和x2。由条件②，x1所能取的整数值为0、 1、2、3、4共5个；由条件③，x2所能取的整数值为0、1、2共3 个。因此所有可能的整数组合(不都是可行的)数是3×5=15个， 穷举法还是勉强可用的。 ❖ 对于大型问题，可行的整数组合数会很大。 例如在指派问题中，将n项任务指派n个人去完成，不同的指派 方案共有n!种，当n=10时，可能的指派方案数超过300万；当 n=20，超过2×1018。显然，穷举法是不可取的