《不确定条件下优化问题的高效精确与近似算法》MIT最新130页

某些最重要且最具挑战性的决策必须在信息不完整的条件下制定。这种信息缺失可能涉及已发生事件或条件的未知状态，也可能关乎尚未发生的事件。信息不足既涉及可用决策选项的认知局限，也包含这些决策后果的不确定性。不确定条件下的优化方法在众多领域具有应用价值，包括人才选拔（候选人素质如何？是否会出现更优人选？）、灾害救援（受灾人员位置何在？救援队伍在多长时间内需采取行动以避免情况恶化？）以及制造业（实际产能如何确定？应承接哪些订单？）。这些问题可通过转化为确定性问题进行简单求解，但此类转化将显著扩大问题规模，导致计算成本急剧上升。本研究旨在开发高效算法求解不确定条件下的优化问题，并构建适用于大规模实例的近似算法以快速逼近最优解。

第二章探讨具有广义决策的秘书问题。核心目标是对按不确定顺序抵达的项目进行实时“评级”。每个项目到达后必须在下个项目出现前完成等级评定，且后续新项目到达时已评定结果不可更改。通过精确动态规划方法挖掘问题结构特征，构建了可计算精确解的算法体系。同时开发了适用于大规模问题的启发式近似解法。第三章研究搜救无人机路径规划问题。该问题要求构建最大化自然灾害中待救援人员数量的巡逻路线。在建立非线性混合整数规划模型后，设计了可实时求解并随信息更新动态调整的简化策略。第四章讨论两阶段随机背包问题。在制造业场景中，订单受理决策需在资源供给量未知前提下完成。将该问题形式化为两阶段随机背包模型，基于可行解构造下界，通过问题松弛最优解建立上界，进而利用这些边界条件构建优于传统求解器的优化方案，最终开发出在大规模实例中能保持近似解优良性能的算法体系。