论文部分内容阅读
作为近二十年来发展起来的处理不确定问题的一种新方法，鲁棒优化从理论研究和实际应用两个方面都取得了很大的发展。应用鲁棒优化方法建模求解实际问题时因考虑到不确定因素的影响，所得最优方案通常具有很好的鲁棒性。但该方法的保守性一直是一个备受关注的核心问题。 首先，研究了鲁棒优化模型的保守性问题。2004年Bertsimas和Sim提出了一种可以控制保守性的鲁棒优化模型。该模型通过引入参数Γ来控制变化的参数的最大数目。但是当Γ远小于n的时候，该模型就可能达到极端保守情况。文通过理论分析解释了发生这种情况会的原因;并指出:当Γ小于k时，该模型不会达到极端保守情况，其中k是极端保守情况的最优解中的非0分量的数目。为了对该模型的保守性有一个整体认识，本文还给出了k的概率分布和期望。 其次，建立了鲁棒虚拟网络设计问题中的流量矩阵的支配关系。证明了，如果D1支配D2，那么D3支配D3+λ(D2-D1)对任何λ≥0;令u(D)为被流量矩阵D支配的所有流量矩阵的集合，那么u(D1)和u(D2)是同构的。在多商品流问题上推广了此结果。设U1和U2为任意两个容量矩阵，D为任一流量矩阵。如果U1支撑D，那么U2支撑U2+λ(D-U1)对任何λ≥0。令(D)(U)为被容量矩阵U支撑的流量矩阵的集合。那么D（U1）和D（U2）是同构的。 最后，设计了一个鲁棒虚拟网络设计问题的启发式算法。并以中国教育网骨干网为拓扑，利用数值模拟结果对比了无边失效无点失效情形、有边失效无点失效情形、无边失效有点失效情形等三种情形的费用。以某公司的实际网络拓扑结构，利用数值模拟结果分析了流量的不确定性程度与费用的关系。数值结果表明，流量的不确定程度越高，费用越高。