毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 论文 >> 正文

分支定界法求解整数规划问题的设计与实现 第4页

更新时间:2012-2-23:  来源:毕业论文
增加松弛变量 和 ,变为如下式子(1-2):
max Z=   (1-2)
得到(LP)的初始单纯形表(表 1-1)[8]和最优单纯形表(表 1-2)[8]:
表 1-1 初始单纯形表
0 1 0 0
CB XB b x1 x2 x3 x4
0 x3 6 3 2 1 0
0 x4 0 -3 2 0 1
-Z 0 0 1 0 0

表 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.751com.cn/  
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] 下一页

分支定界法求解整数规划问题的设计与实现 第4页下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©751com.cn 辣文论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。