对偶理论在整数规划中有哪些具体的应用?可以解决哪类典型整数规划问题?简要叙述思想即可. 数学
网友回答
【答案】 首先,对偶理论和方法是最优化的基本工具,也是整数规划中内容最丰富、应用最广泛的松弛方法之一.在简单的实际问题中,可以利用拉格朗日松弛和对偶产生线性整数规划的界,从而用分支定界法求解规划问题的最优解.
其次,对偶理论中应用最为广泛的就是拉格朗日对偶,它的基本思想就是把难处理的约束通过乘子移到目标函数上去,只在优化问题中保留容易处理的约束,从而得到原问题的一个松弛问题,而最优的松弛问题可通过以乘子为变量的对偶问题来求得.只要熟悉基本的对偶思想应该能够明白这段话的含义.
最后,举几个常见的例子.
1.选址问题UFL
n个可选地址建立服务站,以服务m个客户.每个位置建站的成本不同,对不同客户的利润也不同.问题就是如何选择建站位置,使得总收入最大.
2.广义指派问题GAP
m台机器,n个工作,成本和效率各不相同,如何安排生产计划,使得总费用最小.
这两个问题的模型都可以用拉格朗日对偶,得到一个容易求解的松弛问题,比原问题的规模和复杂程度都小很多.