整数归划.pptVIP

1 1 整数规划 整数规划的模型 整数规划的模型 整数规划的模型 整数规划的模型 整数规划的数学模型 整数规划的数学模型 整数规划与线性规划的关系 整数规划与线性规划的关系 整数规划与线性规划的关系 整数规划与线性规划的关系 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 分枝定界法 割平面法 割平面法 割平面法 割平面法 割平面法 割平面法 割平面法 割平面法 割平面法 0－1 整数规划 0－1 整数规划 0－1 整数规划 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 指派问题 此时，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.