对偶理论在整数规划中有哪些具体应用？什么样的典型整数规划问题可以求解？

首先，对偶理论和方法是最优化的基本工具，也是整数规划中最丰富、应用最广泛的松弛方法之一。在简单的实际问题中，可以利用拉格朗日松弛和对偶来生成线性整数规划的界，从而可以利用分枝定界法来求解规划问题的最优解。

其次，拉格朗日对偶是对偶理论中应用最广泛的。其基本思想是通过乘子将困难的约束移到目标函数中，在优化问题中只保留容易的约束，从而得到原问题的一个松弛问题，最优松弛问题可以通过以乘子为变量的对偶问题得到。只要熟悉基本的对偶思想，就应该能理解这段话的意思。

最后，举几个常见的例子。

1.选址问题UFL

n个可选地址用于建立服务站，为M个客户提供服务。每个地点建站的成本不一样，给不同客户的利润也不一样。问题是如何选择车站的位置，使总收益最大化。

2.广义指派问题缺口

m台机器，n个工作，不同的成本和效率，如何安排生产计划使总成本最小。

这两个问题的模型可以利用拉格朗日对偶，得到一个容易求解的松弛问题，其规模和复杂度都比原问题小得多。