下载掌阅APP，畅读海量书库
立即打开
逆优化的概念从提出至今已有近30年的发展历程。在此期间，在研究人员的共同努力下，该思想广泛应用于交通运输、生产作业、人工智能、网络规划等领域，取得了不错的研究成果。
1.逆优化问题的描述及分类
Mori和Kaya在1979年首次对逆优化领域进行了研究。他们引用逆优化的思想方法求得一个线性目标函数，并且在一个给定范围内优化相关参数。但是，由于该论文以日文形式发表，所以当时并没有在国际上受到关注。直到1992年，Burton和Toint第一次将逆最短路问题用于预测地震并正式发表，引起学术界的广泛关注。几十年来，随着研究者对逆优化问题研究的逐渐深入，新的理论和方法不断被相关学者提出。这些研究成果对系统管理科学和计算机科学的发展有着十分重要的意义。关于此类问题的研究已取得不少进展，可以大体概括为如下几类。
（1）最大费用流逆问题：Yang等人使用对偶特性，将最大流和最小割问题进行变形，转变为最小费用流问题。Liu和Zhang则进一步研究了加权哈明距离下的最大流逆问题。
（2）最小最大生成树逆问题：Liu和Yao研究了 L 1 和 L ∞ 距离下的最小最大生成树逆问题和最小最大容量逆问题，论文中，他们给出了用多项式时间算法求解不同的问题模型。Liu和Wang进一步研究了加权哈明距离下的最小最大生成树逆问题。
（3）最小割逆问题：Zhang等人于1997年首先研究了一种受约束情况下的 L 1 距离下最小割逆问题，并将其变形为最大流问题。Auja和Orlin在2001年和2002年分别采用两类方法对上述问题进行讨论，主要包括线性规划方法和组合方法。另外，针对受约束的情况，Zhang、Cai和Auja、Orlin将问题转化为最小费用流问题进行求解。在2002年，Auja和Orlin采用组合的方式，探讨了赋权 L ∞ 距离下受约束的问题，设计了一种基于二分法的算法求解。Radzik提出有的方法可以将以上方法转换为强多项式时间算法。Yang证明了受约束最小割逆问题是一类NP-hard问题。
（4）最小费用流逆问题：1996年，Zhang、Liu和Ma最初研究了 L 1 距离下无约束的最小费用流逆问题。关于无穷距离下的最小费用流逆问题，Zhang和Liu进一步探讨了假设无加权情况下的最小费用流逆问题。Auja和Orlin分别研究了无加权情况和加权情况下的两类问题。Dial用线性规划的方法对该问题进行深入探讨。Skkalingam则分别研究了无穷距离下的无加权情况和加权情况，还对 L 2 距离下的无加权情况进行了分析与研究。另外Jiang、Liu和Wu研究了加权哈明距离最小费用的逆问题。
（5）最短路逆问题：Burton等人应用Goldfib and Idnani算法进行求解最短路逆问题，在此过程中，首先将该问题转变为二次规划问题，然后对其求解。Zhang等人对 L 1 距离下无加权的情况进行了研究，采用列生成法求解。随后，Cai等人利用线性规划法求解了 L 1 距离下的逆问题。Zhang等人对无权的最短路逆问题进行研究，证明了该问题就是同一个图中的另一个最短路问题。
在逆优化领域，除上述提到的逆问题之外，还有很多其他类型，如指派问题的逆问题、最小支撑树逆问题、线性规划逆问题等。
2.逆优化问题的特性
与一般资源优化配置“选择最优解”相比，逆优化问题侧重于“培养”最优解，即通过改变模型相关系数，如目标函数的价值系数、约束条件的资源消耗系数或资源总量限制等，将给定的可行解培养为最优解。
3.求解逆优化问题的几类方法
求解逆优化问题的方法包括基于线性规划的方法，一般范数下逆问题的对偶性方法， l 1 范数、 l 2 范数下的多项式算法，以及牛顿型方法。
自从1987年Tarantola给出逆问题的描述，逆优化问题受到国内外学者的广泛关注。Yang等人使用对偶特性，将最大费用流问题的最大流和最小割问题进行变形，转变为最小费用流问题。对于同一问题，Liu和Zhang则进一步研究了加权哈明距离下的最大流逆问题。Liu和Yao研究了 L 1 和 L ∞ 距离下的最小最大生成树逆问题和最小最大容量逆问题，论文中，他们都用多项式时间算法求解了不同的问题模型。Zhang等人于1997年首先研究了一种受约束情况下的 L 1 距离下最小割逆问题，并将其变形为最大流问题。Zhang和Liu等人于2002年提出在 l ∞ 范数下求解逆组合问题的牛顿型方法。
4.逆优化问题的现状总结
“逆优化”思想自1992年被提出以来，随着计算机技术的飞速发展，逐渐应用于社会生活的各个领域，受到众多学者的关注。到目前为止，逆优化已取得许多研究成果，对国民经济的各个领域产生了重要影响和积极作用，在优化生产过程、提高生产效益、节约资源等方面发挥了重要作用。其通过调整相关参数，对方案进行最小的改变满足优化目标，是一种具有高柔性和高容错能力的优化方法。
由于逆优化问题能够在方案改动最小的基础上完成，所以对方案的优化特性具有重要的理论研究价值和实际工程意义，并且已经成为一个研究热点，取得了大量研究成果。在未来的研究中，如何将该思想与实际问题结合并应用仍然值得进一步探讨。