声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 2098|回复: 1

[C/C++] 求助:0-1规划法

[复制链接]
发表于 2007-5-20 16:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

x
有序组合树具有下面的几个特点:

(1)树的节点号就是变量的下标号,第j号节点对应变量xj

(2)自树根到某一节点j的一条路表示一个解;路中节点(不含树根)对应的变量取值为1,其余变量1取值为0。树根也代表一个解,即所有变量均取值为0;
(3)同一条路上的相邻节点是父子关系,左边的父节点号小于右边的子节点号,由同一父节点衍生出的同一层节点之间是兄弟关系,上边的兄节点号小于下边的弟节点号。因此,靠上、靠左的路代表的解优于靠下、靠右的路所代表的解.这一特点是设计算法的基本依据。
将原问题转化为标准型之后,有序组合树法的运算步骤如下:

(1)以树根作为初始解,将目标函数值(以下简称
Fig.1
The ordinal combined tree with five variables “目标值”)“0”标记在节点旁;

(2)用约束条件检验树根是否可行解.若是,找到最优解,输出结果,算法结束;否则划“×”勾销,然后向右上衍生,到达其“长子”1号节点,得到新的解向量。

(3)计算新解的目标值,标记在节点旁;
(4)在已计算目标值而未划“X”勾销的解集中找出目标值最小的解;
(5)用约束条件检验该解是否可行解.若是,找到最优解,输出结果,算法结束;否则划“X”勾销,执行下一步;
(6)检查该节点有无“次弟”和“长子”.若有,向正下和右上各生长一步,到达两个新的节点,形成新向量,转到(3);若无,则执行下一步;
(7)检查有无已计算目标值而未划“X”勾销的解,若有,转(4);若无,算法结束,原问题无解。
从上述步骤可以看出,对于存在可行解的0-1规划问题,一般并不需要把组合树全部构造出来,然而隐含地搜索了整棵树,不会遗漏最优解,这点与隐枚举法在本质上是一致的。

如附件图中所示的简单例子。谢谢
sshot-1.png
回复
分享到:

使用道具 举报

发表于 2007-5-28 15:00 | 显示全部楼层
有什么问题吗?
您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-12-24 07:46 , Processed in 0.113853 second(s), 23 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表