早教吧作业答案频道 -->数学-->
线性规划整数解有简便方法吗?线性规划整数解除了用画图法还有什么别的方法?有只用代数的方法吗?
题目详情
线性规划整数解有简便方法吗?
线性规划整数解除了用画图法还有什么别的方法?有只用代数的方法吗?
线性规划整数解除了用画图法还有什么别的方法?有只用代数的方法吗?
▼优质解答
答案和解析
整数线性规划的解法总结
0-1整数线性规划是整数线性规划的特殊情况,在实际中有着广泛的应用.虽然变量的取值只有两个,但此类问题的求解却意外的困难,下面把有关的一些解法总结一下.
1.穷举法 把所有可能的解一一代入,然后比较满足约束的解,使目标函数最达到最优的解是最优解.这不失为一种方法,但不是一种好方法.如果问题规模大,则无法在可接受的时间内求得最优解.这也是求解整数规划的困难所在.
2.隐枚举法I 是穷举法的改进,其思路是先给出一个可行解,然后代入目标函数算出函数值得到一个上界(如果求最小值)或下界(如果是求最大值).然后一一检验其它的解,如果该解大于上界或小于下界,则不用检验可行性,因为它不可能是最优解,否则的话就要检验可行性,如果是可行解,则修改上界或下界,继续检验其它的解,否则不用修改上界或下界,直接检验其它的解.这种方法通过上界或下界来控制是否需要进行可行性检验,提高了效率.但是,要找可行解也得花一定的时间,当约束和变量较多时,工作量异常的大,退一步来说,即使可行解比较容易找到,但其产生的上界太大,或是下界太小,则其过滤的效果也不明显.这是这种方法的缺陷.
3.隐枚举法II 这种方法先把问题转化成标准型,然后按照分枝定界法的思想,尽量少的检验可行解来寻找最优解.这种方法比较麻烦,我在这里也描述不清楚,过几天理解透了再来写这一部分.
4.隐枚举法III 这是在程冬时,张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的,大致的思路是:把所有可能的解都代入目标函数算出值,然后把这些目标函数值进行排序,如果是求最大值,则降序排列,如果是求最小值则升序排列.然后按这个顺序一个一个的检验对应的解的可行性,当碰到第一个可行解时即得到最优解,因为其它的解不会优于此解了.这种方法的缺陷也是明显的,如果变量为N个,则需求2的N次个目标函数值,然后还要进行排序,这又是项工作量很大的工作,再一个就是,如果排序结果是把可行解排在最后一个,那还是得进行2的N次方次检验.
4.启发式算法 遗传算法,蚁群算法等都可归于此类.这都是随机算法,说白了就是听天由命,即使算出了最优解你也不知道是不是最优解,因为此类算法的收敛性都只是依概率收敛的,真正在算的过程中是否已得到最优只有上帝知道.启发式算法是万不得已的情况下才使用的,我们用这种方法只能保证得到的解比其它方法得到的好,但不一定就说得到了最优了.
0-1规划的求解方法还在研究之中,也许你会发现一个有效的算法.
0-1整数线性规划是整数线性规划的特殊情况,在实际中有着广泛的应用.虽然变量的取值只有两个,但此类问题的求解却意外的困难,下面把有关的一些解法总结一下.
1.穷举法 把所有可能的解一一代入,然后比较满足约束的解,使目标函数最达到最优的解是最优解.这不失为一种方法,但不是一种好方法.如果问题规模大,则无法在可接受的时间内求得最优解.这也是求解整数规划的困难所在.
2.隐枚举法I 是穷举法的改进,其思路是先给出一个可行解,然后代入目标函数算出函数值得到一个上界(如果求最小值)或下界(如果是求最大值).然后一一检验其它的解,如果该解大于上界或小于下界,则不用检验可行性,因为它不可能是最优解,否则的话就要检验可行性,如果是可行解,则修改上界或下界,继续检验其它的解,否则不用修改上界或下界,直接检验其它的解.这种方法通过上界或下界来控制是否需要进行可行性检验,提高了效率.但是,要找可行解也得花一定的时间,当约束和变量较多时,工作量异常的大,退一步来说,即使可行解比较容易找到,但其产生的上界太大,或是下界太小,则其过滤的效果也不明显.这是这种方法的缺陷.
3.隐枚举法II 这种方法先把问题转化成标准型,然后按照分枝定界法的思想,尽量少的检验可行解来寻找最优解.这种方法比较麻烦,我在这里也描述不清楚,过几天理解透了再来写这一部分.
4.隐枚举法III 这是在程冬时,张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的,大致的思路是:把所有可能的解都代入目标函数算出值,然后把这些目标函数值进行排序,如果是求最大值,则降序排列,如果是求最小值则升序排列.然后按这个顺序一个一个的检验对应的解的可行性,当碰到第一个可行解时即得到最优解,因为其它的解不会优于此解了.这种方法的缺陷也是明显的,如果变量为N个,则需求2的N次个目标函数值,然后还要进行排序,这又是项工作量很大的工作,再一个就是,如果排序结果是把可行解排在最后一个,那还是得进行2的N次方次检验.
4.启发式算法 遗传算法,蚁群算法等都可归于此类.这都是随机算法,说白了就是听天由命,即使算出了最优解你也不知道是不是最优解,因为此类算法的收敛性都只是依概率收敛的,真正在算的过程中是否已得到最优只有上帝知道.启发式算法是万不得已的情况下才使用的,我们用这种方法只能保证得到的解比其它方法得到的好,但不一定就说得到了最优了.
0-1规划的求解方法还在研究之中,也许你会发现一个有效的算法.
看了线性规划整数解有简便方法吗?线...的网友还看了以下:
数学苏教版6年级分数乘除法解决实际问题中,平均要用除法,求一个数的几分之几是乘法,还有那些题要用的 2020-05-16 …
我国国家审计的总目标除真实性和合法性外还包括: A.效益性 B.一贯性 C.客观性 D.公允性 2020-05-21 …
除了重结晶法还有哪几个常见的除杂方法?貌似还有气体法什么的?求各种方法适用范围~ 2020-05-22 …
法的评价作用中所使用的标准,除具有规范性外,还具有()。A.统一性B.普遍性C.强制性D.综合性 2020-06-04 …
整除和被整除到底是谁除谁啊谁谁能被3整除.和3能被谁整除到底是什么呀?我这人很死脑筋,且大声给个简 2020-06-08 …
作题怎样才能看出用乘法或除法,我总是分不清,烦都要烦死了.做题经常看不出用乘法还是除法,分不清,经 2020-07-12 …
表示还原性化合价升高还是降低同物质一般是高的氧化性强,还原性反之氧化性,还原性强弱的判断方法(一) 2020-07-28 …
线性规划整数解有简便方法吗?线性规划整数解除了用画图法还有什么别的方法?有只用代数的方法吗? 2020-12-01 …
小学数学正方体的对面是什么用到排除方法,还有哪方面的知识用到了排除方法? 2020-12-10 …
(2013•龙江县二模)用伏安法测电阻时,由于电压表、电流表内阻的影响,不论使用电流表内接法还是电流 2021-01-22 …