权重不确定情形下中心选址的鲁棒优化方法

一、问题的描述 中心选址问题是网络优化理论中非常重要的一类问题。对于权重确定情形下的中心选址问题，相关的理论成果非常丰富。不确定情形下的中心选址问题的有关结论相对较少。参数具有不确定性，一般采取两种方法进行解决。一种是随机的方法，对参数的各种取值，利用统计数据，得到参数取值的概率分布，然后计算参数取值的数学期望，从而得到随机方法的最优解；另一种是采用鲁棒优化的方法，这是在仅仅知道参数取值的范围，但参数取值的概率分布未知的情形下所采取的一种优化方法。鲁棒优化包括绝对鲁棒优化、相对鲁棒优化、偏差鲁棒优化等，相应采取的求解方法以及得到的最优解也有所不同。其中相对鲁棒优化就是采用最小最大后悔值标准，针对每一个可行解，在参数的各种取值下计算与最优解的偏差，得到的最大值就作为该可行解的最大后悔值，选择具有最小后悔值的可行解就是相对鲁棒最优解。这样得到的解，是在参数各种可能取值的情形下都可以接受的解。本文将考虑在参数具有不确定性的条件下，采用相对鲁棒优化解决1-center选址问题。