4.1整数规划.ppt

一、整数规划的模型 图 二、分枝定界法 （二）、例题 三、割平面法 四、0－1 整数规划 五、指派问题 例一： 例二、 0 1/4 1/4 1 0 3/2 x2 1 -1/4 -1/4 -1/6 x4 0 0 1 0 s1 0 -1/4 0 0 -3/2 －Z -1/4 0 0 -1/2 s1 0 1/6 0 1 1 x1 0 x3 x2 x1 b XB CB 0 1 0 Cj 现将生成的割平面条件加入松弛变量，然后加到表中： 1 0 0 1 0 1 x2 1 0 1 -1/3 x4 -1 -4 2/3 s1 0 0 0 -1 －Z 1 0 0 2 x3 0 0 0 1 2/3 x1 0 x3 x2 x1 b XB CB 此时，X1 ＝(2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为： 用上表的约束解出x4 和s1 ，将它们带入上式得到等价的割平面条件：x1 ≥ x2 ，见图： x1 x2 ⑴ ⑵ 3 3 第一个割平面 第二个割平面 将生成的割平面条件加入松弛变量，然后加到表中： 0 2/3 -1/3 0 0 1 2/3 x1 0 0 1 0 0 1 0 1 x2 1 0 -4 1 1 0 0 2 x3 0 -1 -2/3 s1 0 -2/3 x4 0 1 s2 0 0 0 -1 －Z 0 0 0 -2/3 s2 0 x3 x2 x1 b XB CB 1 0 -1 0 0 1 0 x1 0 3/2 0 -1 0 1 0 0 x2 1 -6 0 5 1 0 0 6 x3 0 0 1 s1 1 1 x4 -3/2 -3/2 s2 0 0 0 0 －Z 0 0 0 1 s1 0 x3 x2 x1 b XB CB -1/2 1 0 0 0 1 1 x1 0 0 1 0 0 1 0 1 x2 1 3/2 -5 0 1 0 0 1 x3 0 -1 1 s1 0 1 x4 0 -3/2 s2 0 0 0 -1 －Z 0 0 0 1 x4 0 x3 x2 x1 b XB CB 至此得到最优表，其最优解为 X＊= (1 , 1) , Z = 1, 这也是原问题的最优解。 有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 例一、求解下列0－1 规划问题 解：对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。 × 2 6 ( 1. 1. 1 ) × 3 ( 1. 1. 0 ) 8 ∨ 0 2 1 1 ( 1. 0. 1 ) × 1 5 ( 0. 1. 1 ) 3 ∨ 1 1 1 0 ( 1. 0. 0 ) －2 ∨ 2 4 1 4 ( 0. 1. 0 ) 5 ∨ －1 1 0 1 ( 0. 0. 1 ) 0 ∨ 0 0 0 0 ( 0. 0. 0 ) 是∨ 否× (1) (2) (3) (4) Z 值 满足条件 约束条件 x1 . x2. x3 由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。 × 4 ( 1. 1. 1 ) × 1 ( 1. 1. 0 ) 8 ∨ 8 0 2 1 1 ( 1. 0. 1 ) × 3 ( 1. 0. 0 ) × 3 ( 0. 1. 1 )