表 1-2 最优单纯形表
本文来自优.文~论^文·网原文请找腾讯324,9114
0 1 0 0
CB XB b x1 x2 x3 x4
0 x1 1 1 0 1/6 -1/6
1 x2 3/2 0 1 1/4 1/4
-Z 3/2 0 0 -1/4 -1/4
此题的最优解为：X*=(1,3/2),Z=3/2 ,但x2不满足整数条件，不是整数最优解，因此需引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，由公式(1-1)生成割平面的条件为: (1-3)
将 x3=6-3x1-2x2,x4=3x1-2x2,带入式(1-3)得到等价的割平面条件：
x2≤1,见图 1-1[8]：
图 1-1 第一次割平面后所得图形
同理现将生成的割平面条件加入松弛变量，然后加到表中：
(1-4)
此时，X1＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：
(1-5)
用上表的约束解出x4和s1 ，将它们带入上式，得到等价的割平面条件：论文网http://www.youerw.com/
x1 ≥ x2 ，见图 1-2[8]：
图 1-2 第二次割平面所得图形
同理将生成的割平面条件加入松弛变量，然后加到表中：
(1-6)
此时，其最优解为 X＊=(1,1),Z = 1, 这也是原问题的最优解。
表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。
2.1.2. 优缺点
优点：切割后剩下的仍为一个子域，后继计算为一个较小的子域上的整数规划,缩小问题求解的规模；可选出切割条件较强的一个割平面方程或同时取几个割平面方程的方法[9]，减少切割次数和计算量；
缺点：对不符合(IP)的整数条件的分量，需将最优单纯形表中该行的系数分解为整数部分和小数部分之和；不同类的整数规划有不同的切割方程,对问题的结构以及求解结果都有较高的要求；对于每次割平面时，难于用计算机实现，并且切割后要改变计算方法。2.2. 隐枚举法求解0—1规划
上一页 [1] [2] [3] [4] [5] [6] [7] [8] 下一页