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

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

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