生產(chǎn)網(wǎng)絡(luò)最小費(fèi)用流問題的研究.pdf

1、網(wǎng)絡(luò)流問題是網(wǎng)絡(luò)最優(yōu)化的重要組成部分，其中最小費(fèi)用流是一類最為基本的網(wǎng)絡(luò)流模型，對于該模型已有豐富的研究成果。但是隨著人類活動和生產(chǎn)過程日益復(fù)雜，新的約束條件不斷出現(xiàn)，這對原有的網(wǎng)絡(luò)流問題構(gòu)成了挑戰(zhàn)。基于此，生產(chǎn)網(wǎng)絡(luò)模型應(yīng)運(yùn)而生，它引入六種頂點(diǎn)，以便表示不同類型的額外線性約束。將生產(chǎn)網(wǎng)絡(luò)模型與最小費(fèi)用流問題相結(jié)合則構(gòu)成了二類新的網(wǎng)絡(luò)流問題，其中頂點(diǎn)具有流量需求的最小費(fèi)用流問題和最小費(fèi)用分配流問題就是兩個(gè)典型的代表，并且在現(xiàn)實(shí)生活中具有廣

2、泛的應(yīng)用。
　　 本文的主要工作概括如下：
　　 首先，針對頂點(diǎn)具有流量需求的最小費(fèi)用流問題，提出了一種新的最小費(fèi)用流算法。新算法中引入了頂點(diǎn)分層的思想，克服了已有網(wǎng)絡(luò)不適用于大型網(wǎng)絡(luò)的缺點(diǎn)，使得網(wǎng)絡(luò)在龐大的情況下能夠有次序的將網(wǎng)絡(luò)規(guī)模減小，有利于計(jì)算機(jī)化。通過數(shù)值試驗(yàn)表明新算法的性能良好。
　　 其次，針對最小費(fèi)用分配流問題，在經(jīng)典最小費(fèi)用路算法的基礎(chǔ)上設(shè)計(jì)了一種新的最小費(fèi)用分配流算法。該算法通過對頂點(diǎn)進(jìn)行三次