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

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

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

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