本文選題：瓶頸容量擴(kuò)張 + 最小生成樹(shù)�。� 參考：《中國(guó)管理科學(xué)》2014年09期

【摘要】：在一些物理網(wǎng)絡(luò)中,當(dāng)設(shè)施(邊的容量等)建立后,由于需求增加,需要調(diào)整網(wǎng)絡(luò)的容量來(lái)提高服務(wù)水平。調(diào)整優(yōu)化的過(guò)程中既要考慮擴(kuò)張成本,同時(shí)也要考慮需要調(diào)整的總邊數(shù),以盡可能小的影響人們的正常生活。本文研究對(duì)于一個(gè)給定的網(wǎng)絡(luò)G,已知邊ei的初始容量和單位容量擴(kuò)張成本,在預(yù)算成本和擴(kuò)張總邊數(shù)的約束下,如何有效地?cái)U(kuò)張邊的容量至xi,使得系統(tǒng)的容量最大,即max{mine i∈Txi,T是網(wǎng)絡(luò)G中的生成樹(shù)}。首先求解兩個(gè)與之相關(guān)的模型,然后通過(guò)分析兩個(gè)相關(guān)模型與原問(wèn)題之間的聯(lián)系與區(qū)別,提出了原問(wèn)題的多項(xiàng)式時(shí)間算法。最后,通過(guò)算例說(shuō)明算法的步驟,并分析了不同參數(shù)值對(duì)系統(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 鈭，

本文編號(hào)：2025611