首页 > 编程知识 正文

运筹学指派问题,隐枚举法求解过程

时间:2023-05-03 07:26:43 阅读:148731 作者:3880

1、看了很多书的介绍,有点头晕。 如果你把看到的东西放在一起:

2、理论上枚举不需要列举所有的解进行判断计算。 此时,需要将模型标准化变形,通过分支和上下边界的对比进行修剪的技术。 这样就不需要枚举和计算所有解。

3、其他教科书中提到的隐性列举法是对完全列举法的改进,是一种减少计算的方法。 还是需要列举所有的解,通过设置“过滤条件”这个目标函数值的上(下)边界,只是减少了限制条件的判断计算。 如果不满足过滤限制的话,就没有必要进行限制的判断计算,可以省略很多计算

4、当然,改进的方法有很多,我们也可以直接根据目标函数的系数来改进计算次数。 求最大值时,可以将目标函数的系数按从大到小的顺序排列(系数需要变形,都是正数),从全1的解开始按降序计算。 例如111; 110; 101; 100这个计算,从大到小计算,哪个解是可行解就是最佳值。

5、分析:

第一种方式很难学习,理论上不列举所有的解就可以得到最佳解,计算步骤也很少

第二种方式需要列举所有的解,但计算步骤减少,部分劣解可以直接排除,无需判断是否为可行解,制约判断的计算次数减少。 但是,在这种方式中,首先需要得到可行解,这需要增加一定的计算次数;

第三种方式没有必要列举所有的解,但是每个解都需要判断制约的计算。

6、隐性列举法教材混乱,应统一。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。