求助：0-1规划法
有序组合树具有下面的几个特点：(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规划问题，一般并不需要把组合树全部构造出来，然而隐含地搜索了整棵树，不会遗漏最优解，这点与隐枚举法在本质上是一致的。
如附件图中所示的简单例子。谢谢 有什么问题吗？
页:
[1]