论文部分内容阅读
现如今,资源配置问题不管是在实体经济领域,还是虚拟经济领域都有广泛的应用,大到国家电网的电力分配,小的一家作坊的机械分配,都有资源配置问题的提现。最优节点配置问题作为资源配置问题的一种变型,也得到了广泛的研究。而现在大规模高精度的问题对单一设备的要求也越来越大,因此很多复杂的问题都需要分配给若干设备协同解决,这就要求这些设备之间可以相互通信,即构成一个网络化系统,从而进行协同工作。上述两方面的需求,共同促成了本文的研究。 本文,主要研究保持网络连通性的最优节点配置问题的建模和相应的求解算法。本文考虑将一组节点最优地放置到有限数量的位置的问题,以便形成连通的网络并且使总成本最小化。本文提出了四种不同的混合整数规划模型来求解保持网络连通性的最优节点配置问题,这些模型都具有多项式的变量和约束数量。基于混合整数规划模型,本文分别给出了对应分支界定算法和动态规划算法。针对动态规划算法,本文考虑了无差异和有差异两种情况,并验证了算法的有效性和时间复杂度。最后,这个优化模型可以灵活的通过一些扩展和变化,应用到数个实际工程问题,包括无线传感器网络的传感器开关决策,多跳网络的构建,和电动车充电站规划。