最小費用網(wǎng)絡流的若干新問題研究.pdf

1、近幾十年來，組合優(yōu)化經(jīng)歷了飛速的發(fā)展。網(wǎng)絡流在生產(chǎn)和社會實踐中有著廣泛的應用，是組合優(yōu)化中被廣泛研究的問題之一。網(wǎng)絡流上的優(yōu)化問題涉及多個學科領(lǐng)域，包括應用數(shù)學、計算機科學、管理學以及運籌學等。最小費用流是最為基本的網(wǎng)絡流模型，對于該模型已有豐富的研究成果。隨著人類活動和生產(chǎn)過程的日益復雜，新問題不斷出現(xiàn)，這對原有的網(wǎng)絡模型構(gòu)成了挑戰(zhàn)，也為網(wǎng)絡流的進一步發(fā)展提供了新的源泉。本文主要就近年來出現(xiàn)的來自生產(chǎn)實踐的若干最小費用流問題進行研究，

2、提出了進一步的模型，并給出了求解新模型的網(wǎng)絡單純形算法。 全文共分七章。第一章主要介紹了本文要研究的主要問題，并對文獻中相關(guān)問題的研究成果作了簡要的回顧。 第二章介紹了有關(guān)網(wǎng)絡流的若干基本概念和知識，為后面各章的展開做好準備。 第三章我們對近年來新提出的一類網(wǎng)絡流問題一最小費用分配流，做了進一步的研究，給出了用單純形法求解該問題時尋找初始基本可行解的方法，并把經(jīng)典網(wǎng)絡流中的一些概念和方法推廣到了最小費用分配流模型

3、上。 第四章給出了上述最小費用分配流問題的一種推廣，并對推廣的模型進行了研究，探討了該問題的基本可行解的網(wǎng)絡結(jié)構(gòu)和性質(zhì)，設計出了求解該問題的網(wǎng)絡單純形法。 第五章提出了廣義網(wǎng)絡上的最小費用分配流問題，稱為廣義最小費用分配流問題，第三章和第四章中研究的問題都是這種問題的特殊情形。本文研究了此類問題的基本可行解的網(wǎng)絡結(jié)構(gòu)和性質(zhì)，并給出了求解該問題的網(wǎng)絡單純形法，并對如何有效的執(zhí)行算法進行了探討。 第六章主要研究了廣義