Min Z=x,+3x2 x2≥3.13 x1,x2为非负整数 z0=17.51 解:x1=9 解: D =3.21 z1=1839 z2=1762 四￥解: D1:x2≥4|x2=4 D2:x2≤3 无 D21:x2≥ z21=18.77 D2x3解 解: D21:x≥7 D2:x≤6 4.5 z21=19 Z,2=195 如果在分枝求解的过程中,求得的整数解之目标函数值成为所有分枝稍头上诸解的最小 值,过程即可停止,此即最优解。否则,对于比整数解之目标函数小的,还需继续分枝搜索。 可见,最先得到的整数解未必是最优的。如此例中,第六步已得整数解,但它不是最优的, 而于第八步得到的才是最优解,即 X1=7x2=4minz=z21=19 需要指出的是,分枝定界法每步迭代,由于是增加一个上限或者下限约束,故一般都要 用对偶单纯形法或第五章的方法求解LP问题,且不能保证用最少的迭代次数达到最优解 在不顺利的情况下,甚至需要对全部区域进行搜索。但根据经验,它还是比较有效的,目前 应用也最广泛。 §2割平面法 解整数LP问题(1)的割平面法是R·E· Gomory于1959年首先提出来的。从此以后整 数规划逐渐形成一个独立的运筹学分支,割平面法被认为是整数规划的核心部分,其基本思 想是仍以LP问题为松弛问题。若求得的最优解不是整数,就设法把这个最优的极点连同它 的一个域,从可行解集中“切除”,但保留其中的全部整数点,从而不影响(1)的求解 如此进行,直到找到整数解为止,而“切除”将通过一个附加的约束条件(称为割平面)来 实现,故称为割平面法。具体说明如下: 设与(1)相应的LP问题 min CX AX= b (2) X≥0 之最优单纯形表为 135135 1 2 2 1 2 1 2 3 3.13 22 34 285 , Min Z x x x x x x x = +  +  为非负整数 1 2 0 8.12 3.13 17.51 x x Z = = = 解： 1 1 D x: 9  2 1 D x: 8  1 2 2 8 3.21 17.62 x x Z = = = 1 解： 2 1 9 3.13 18.39 x x Z = = = 解： 11 2 D x: 4  1 2 11 9 4 21 x x Z = = = 解： 21 2 D x: 4  1 2 21 6.77 4 18.77 x x Z = = = 解： 22 2 D x: 3  无 解 212 1 D x: 6  1 2 212 6 4.5 19.5 x x Z = = = 解： 211 1 D x: 7  1 2 211 7 4 19 x x Z = = = 解： 12 2 D x: 3  无 解 （ 一 ） （ 八 ） （ 九 ） （ 六 ） （ 七 ） （ 四 ） （ 五 ） （ 二 ） （ 三 ） 如果在分枝求解的过程中，求得的整数解之目标函数值成为所有分枝稍头上诸解的最小 值，过程即可停止，此即最优解。否则，对于比整数解之目标函数小的，还需继续分枝搜索。 可见，最先得到的整数解未必是最优的。如此例中，第六步已得整数解，但它不是最优的， 而于第八步得到的才是最优解，即 x1=7 x2=4 min z=z211=19 需要指出的是，分枝定界法每步迭代，由于是增加一个上限或者下限约束,故一般都要 用对偶单纯形法或第五章的方法求解 LP 问题，且不能保证用最少的迭代次数达到最优解， 在不顺利的情况下，甚至需要对全部区域进行搜索。但根据经验，它还是比较有效的，目前 应用也最广泛。 §2 割平面法 解整数 LP 问题（1）的割平面法是 R·E·Gomory 于 1959 年首先提出来的。从此以后整 数规划逐渐形成一个独立的运筹学分支，割平面法被认为是整数规划的核心部分，其基本思 想是仍以 LP 问题为松弛问题。若求得的最优解不是整数，就设法把这个最优的极点连同它 的一个邻域，从可行解集中“切除”，但保留其中的全部整数点，从而不影响（1）的求解。 如此进行，直到找到整数解为止，而“切除”将通过一个附加的约束条件（称为割平面）来 实现，故称为割平面法。具体说明如下： 设与（1）相应的 LP 问题： 0 min CX AX b X    =    （2） 之最优单纯形表为 1 2 m x x x m n 1 x x +