最短路問題的靈敏度分析與最短路調(diào)整.pdf

1、在一些實際網(wǎng)絡(luò)規(guī)劃模型中，有時因條件的變化需要對網(wǎng)絡(luò)進行調(diào)整，如：交通運輸網(wǎng)中的路線或站點的調(diào)整問題；油品輸送網(wǎng)中的調(diào)線問題，等等。這些改變是否影響原網(wǎng)絡(luò)的最優(yōu)方案，如果影響，改變后的最優(yōu)方案又是什么，這就是網(wǎng)絡(luò)問題的靈敏度分析。對網(wǎng)絡(luò)做靈敏度分析，可以采用對新網(wǎng)絡(luò)重新計算的方式，這對于大型網(wǎng)絡(luò)問題往往會造成巨大的資源浪費，如果采用在原最優(yōu)方案基礎(chǔ)上進行調(diào)整的方式，將會大大節(jié)省各種資源。這是本文做靈敏度分析的出發(fā)點。 本文研究的

2、是網(wǎng)絡(luò)規(guī)劃中的最短路問題的靈敏度分析，具體針對以下六種情況：1.弧上權(quán)值的改變(變大或變小)；2.去掉網(wǎng)絡(luò)中的一條?。?.在網(wǎng)絡(luò)中轉(zhuǎn)移一條??；4.在網(wǎng)絡(luò)中添加一條弧；5.去掉網(wǎng)絡(luò)中的一個節(jié)點及與該節(jié)點關(guān)聯(lián)的弧；6.在網(wǎng)絡(luò)中添加一個節(jié)點及與該節(jié)點關(guān)聯(lián)的弧。給出了相應(yīng)的理論分析，并通過例子對理論進行了驗證。自定義方向矩陣、標(biāo)志矩陣，給出了最短路問題的靈敏度分析算法。與徐冬梅最短路問題的Gauss-Seidel矩陣算法結(jié)合，構(gòu)成了求最短路并能