本文選題：瓶頸容量擴張 + 最小生成樹��； 參考：《中國管理科學》2014年09期

【摘要】：在一些物理網(wǎng)絡(luò)中,當設(shè)施(邊的容量等)建立后,由于需求增加,需要調(diào)整網(wǎng)絡(luò)的容量來提高服務(wù)水平。調(diào)整優(yōu)化的過程中既要考慮擴張成本,同時也要考慮需要調(diào)整的總邊數(shù),以盡可能小的影響人們的正常生活。本文研究對于一個給定的網(wǎng)絡(luò)G,已知邊ei的初始容量和單位容量擴張成本,在預(yù)算成本和擴張總邊數(shù)的約束下,如何有效地擴張邊的容量至xi,使得系統(tǒng)的容量最大,即max{mine i∈Txi,T是網(wǎng)絡(luò)G中的生成樹}。首先求解兩個與之相關(guān)的模型,然后通過分析兩個相關(guān)模型與原問題之間的聯(lián)系與區(qū)別,提出了原問題的多項式時間算法。最后,通過算例說明算法的步驟,并分析了不同參數(shù)值對系統(tǒng)容量的影響。
[Abstract]:In some physical networks, when facilities (side capacity, etc.) are set up, the capacity of the network needs to be adjusted to improve the level of service due to the increased demand. In the process of adjustment and optimization, both the cost of expansion and the total number of edges that need to be adjusted should be considered in order to influence people's normal life as little as possible. In this paper, we study how to effectively expand the capacity of a given network to the maximum capacity of the system under the constraints of budget cost and the total number of expanded edges under the constraints of the initial capacity and the unit capacity expansion cost of a given network. That is, max {mine I 鈭，

本文編號：2025611