常見運(yùn)籌學(xué)概念和操作

1、管理科學(xué)（運(yùn)籌學(xué)）是對于定量因素有關(guān)的管理問題通過應(yīng)用科學(xué)的方法進(jìn)行輔助管理決策 制定的一門學(xué)科。起初用于第二次世界大戰(zhàn)，而推動(dòng)其發(fā)展的重大因素之一是計(jì)算機(jī)革命的爆發(fā)。解決問題的一般步驟：1，定義問題和收集數(shù)據(jù)（考慮的問題和達(dá)成的目標(biāo)）構(gòu)建模型（數(shù)學(xué)模型）從模型中形成一個(gè)對問題進(jìn)行求解的基于計(jì)算機(jī)的程序測試模型并在必要時(shí)進(jìn)行修正應(yīng)用模型分析問題以及提出管理意見幫助實(shí)施被管理者采納的小組意見建立模型的重要因素：1，約束條件：數(shù)學(xué)模型中對決策變量可能取值進(jìn)行限制的不等式或等式。2，參數(shù)：數(shù)學(xué)模型中的變量。3，目標(biāo)函數(shù)：是數(shù)學(xué)模型中根據(jù)決策變量作出的績效度量的數(shù)學(xué)表達(dá)式。關(guān)于敏感性分析：數(shù)學(xué)模型只是

2、問題的一個(gè)近似求解，因而敏感性分析是由于估計(jì)值發(fā)生偏差時(shí)，帶來的 模型變化。數(shù)學(xué)模型編入電子表格，這種數(shù)學(xué)模型通常成為電子表格模型。線性規(guī)劃【用線性數(shù)學(xué)模型表示的活動(dòng)計(jì)劃】的基本概念1，顯示數(shù)據(jù)的單元格稱為數(shù)據(jù)單元格。2，可變單元格包含要做的決策。3，輸出單元格顯示依賴于可變單元格的輸出結(jié)果。4，目標(biāo)單元格是一種特殊的可變單元格，其包含了對所有可變單元格所作出決策的評(píng)估 用電子表格為問題建立數(shù)學(xué)模型（線性規(guī)劃模型）過程中要解決的三個(gè)問題：1，要做出的決策是什么？（表現(xiàn)的是什么）2，在作出這些決策上有哪些約束條件？（約束是什么）3，這些決策的全部績效測度是什么？（達(dá)到的目的是什么）電子表格上的線

3、性規(guī)劃模型的特征：1，需要作出許多活動(dòng)水平的決策，因此可變單元格被用來顯示這些水平。2，這些活動(dòng)的水平能夠取滿足許多約束條件的任何值（包括小數(shù)值）3，每個(gè)約束條件對活動(dòng)水平的決策可行值進(jìn)行了限制，約束條件的左邊往往是一個(gè)輸出 單元格，中間是一個(gè)數(shù)學(xué)符號(hào)（=,=等），右邊是數(shù)據(jù)單元格。4，活動(dòng)水平的決策是以進(jìn)入目標(biāo)單元格的一個(gè)完全績效測度為基礎(chǔ)的，目標(biāo)是最大化目 標(biāo)單元格或是最小化目標(biāo)單元格，這由績效測度的性質(zhì)決定。5，每個(gè)輸出單元格（包括目標(biāo)單元格）的excel等式可以表達(dá)一個(gè)SUMPRODUCT函數(shù)， 這里加和的每一項(xiàng)是一個(gè)數(shù)據(jù)單元格與一個(gè)可變單元格的乘積。特征2與5是區(qū)分線性規(guī)劃模型和其他

4、可變電子表格上建模的數(shù)學(xué)模型的關(guān)鍵。約束邊界線：即形成一個(gè)約束條件所允許的邊界的直線，它通常是由它的方程式確定的，切 對于一含有不等號(hào)的約束條件，它的約束邊界方程將不等號(hào)換成等號(hào)即可。約束邊界線的位 置由它與兩軸相交的交點(diǎn)確定。如3*x+4*y=10。只改變約束條件的右邊會(huì)得到平行的約束 邊界線，檢驗(yàn)（0，0）是否滿足約束條件可以表明位于約束邊界線的哪一邊滿足約束條件。斜截式，斜率?？尚杏颍嚎尚杏騼?nèi)的點(diǎn)是那些符合所有約束條件的解。目標(biāo)函數(shù)線：是它上面點(diǎn)的都有相同目標(biāo)函數(shù)值的一條直線。如何有效的建立一個(gè)電子表格模型：首先輸入數(shù)據(jù)，先輸入和仔細(xì)編排所有數(shù)據(jù)，然后盡量使模型的結(jié)構(gòu)符合數(shù)據(jù)的編排。 可

5、以先建立一個(gè)小型表格。組織和清楚的標(biāo)識(shí)數(shù)據(jù)，行列都有表示。每個(gè)數(shù)據(jù)輸入唯一的一個(gè)單元格，為了方便更改數(shù)據(jù)。公式與數(shù)據(jù)分離。避免在公式中直接使用數(shù)字，這樣可以是表格易于說明，切模型易 于修改。保持簡單化。使用區(qū)域名稱。但也不能濫用。（命名方法，注意事項(xiàng)：不允許使用空格，但可以用 下劃線）使用相對與絕對坐標(biāo)（它的使用方法$）使用邊框，陰影和顏色來區(qū)分單元格類型在電子表格中顯示整個(gè)模型。即要包含整個(gè)內(nèi)容，而不要依賴so lver對話框去包含某 些要素。關(guān)于四類線性規(guī)劃問題：資源分配問題：資源分配問題是將有限的資源分配到各種活動(dòng)中去的線性規(guī)劃問題。 這一類問題的共性是在線性規(guī)劃模型中每一個(gè)函數(shù)限制為資

6、源限制，并且，每一種資 源都可以表現(xiàn)為如下形式，使用的資源數(shù)量=可用的資源數(shù)量。廣義上的資源角度來說：使用的數(shù)量=可獲得的數(shù)量解決資源分配問題的第一步是明確活動(dòng)和資源，對每一個(gè)活動(dòng)，需要作出活動(dòng)數(shù)量的 決策，也就是要確定活動(dòng)水平。一下三類數(shù)據(jù)是必須的：每種資源的可供量；每一種 活動(dòng)所需要的各種資源的數(shù)量，對于每一種資源與活動(dòng)的組合，單位活動(dòng)所消耗的資 源量必須首先估計(jì)出來；每一種活動(dòng)對總的績效測度的單位貢獻(xiàn)。它包含了生產(chǎn)分配和財(cái)務(wù)問題。它的一般建模步驟：首先確認(rèn)問題的活動(dòng)類型，問題的決策也就是決定各種活動(dòng)的水平明確合適的績效測度以求解問題估計(jì)每一種活動(dòng)對于總績效測度的單位貢獻(xiàn)明確分配給各種活動(dòng)

7、的有限資源對于每一種資源，明確可獲得的數(shù)量以及各種活動(dòng)的單位使用量將數(shù)據(jù)輸入電子表格，可以在活動(dòng)欄與可獲得的資源欄之間要保留兩個(gè)空欄的參數(shù)表 指定可變單元格來顯示活動(dòng)水平的決策量在第六步中產(chǎn)生的兩個(gè)空欄，左邊一欄做為輸出單元格的總數(shù)欄，右邊一欄為所有的 資源輸入=符號(hào)，使用SUMPRODUCT函數(shù)指派目標(biāo)單元格以顯示總的績效測度，也使用SUMPRODUCT函數(shù)成本收益平衡問題：成本收益平衡問題是一類線性規(guī)劃問題，在這類問題中，通過選 擇各種活動(dòng)水平的組合，從而以最小的成本來實(shí)現(xiàn)最低可接受的各種收益水平。這類 問題的共性是，所有的函數(shù)約束條件均為收益約束，并具有如下的形式，完成的水平= 可接受的

8、最低水平它也需要三種數(shù)據(jù)：每種收益的最低可接受水平；每一種活動(dòng)對一種收益的貢獻(xiàn)；每 種活動(dòng)的單位成本。解決任何成本收益平衡問題的第一步是明確活動(dòng)和收益。線性規(guī)劃建模的類型并不是由應(yīng)用決定，而是由作出決策的各種限制條件決定的。其他的建模步驟跟資源問題大致相同。網(wǎng)絡(luò)配送問題：它出現(xiàn)了一種新的限制條件一一確定需求的約束，確定的需求限制在 網(wǎng)絡(luò)配送中占有重要的地位，且必須確定需求以及相應(yīng)的確定需求的約束條件。首先必須明確這一網(wǎng)絡(luò)配送問題的活動(dòng)與需求，線性規(guī)劃中確定需求的限制是以“=” 表示的等式，每種這樣的限制都可以解釋為一定數(shù)量的確定的需求：提供的數(shù)量=需 求的數(shù)量，純網(wǎng)絡(luò)配送問題的特點(diǎn)之一就是其建

9、模的主要函數(shù)約束是確定需求的約 束。但是，其他類型的線性規(guī)劃問題也可能包含這一類的約束條件。4.混合型問題類型形式解釋主要用于資源問題LHS=RHS對于特定的資源使用的數(shù)量 =RHS對于特定的收獲達(dá)到的水平 =最低可接受水平成本收益平衡問題混合問題確定要求約束LHS=RHS對于一些數(shù)量提供的數(shù)量=需求的數(shù)量網(wǎng)絡(luò)配送問題混合問題LHS=左式（一個(gè) SUMPRODUCT 函數(shù)）RHS=右式（常數(shù)）混合線性規(guī)劃問題建模過程的總結(jié)：【首先明確問題的各種活動(dòng)，活動(dòng)的水平即為要做出的決策】從管理的角度，為問題的解確定一個(gè)總績效測度；對于每一種活動(dòng)，估計(jì)活動(dòng)對總技校測度的單位貢獻(xiàn)；確定分配給各種活動(dòng)的有限資

10、源，明確每一種資源可獲得的數(shù)量以及活動(dòng)的單位使用量； 確定各種活動(dòng)的可獲得的收益，并明確各種收益管理層所制定的最低可接受水平以及每種活 動(dòng)的單位收益貢獻(xiàn)；判別確定的需要，對于一些類型的數(shù)量，提供的數(shù)量必須等于需求的數(shù)量，明確每一種要求 的數(shù)量，以及每一活動(dòng)對該要丟的數(shù)量的單位貢獻(xiàn)；將36步所收集的數(shù)據(jù)輸入到電子表格的數(shù)據(jù)單元格中；指明可變單元格一顯示活動(dòng)水平的各項(xiàng)決策；使用輸出單元格來說明資源，收益以及確定需求的約束；指定目標(biāo)單元格來顯示總的績效測度。檢驗(yàn)?zāi)Ｐ偷腻e(cuò)誤與遺漏的過程就是模型的確認(rèn)。模型的擴(kuò)展就叫模型的變異。如何會(huì)出現(xiàn)WHAT-IF問題：如果模型的參數(shù)的估計(jì)有誤怎么辦；如果作出不同的

11、似是而非的假設(shè)，問題的結(jié)果將會(huì)如何變化；如果管理方面所要求的某一選項(xiàng)沒有被考慮在內(nèi)，會(huì)產(chǎn)生怎么樣的結(jié)果。線性規(guī)劃的目的：對未來進(jìn)行各種各樣的假想，在這些假設(shè)下，測試各種管理方法可能產(chǎn)生 的結(jié)果，而通過對各種各樣結(jié)果的深入分析來知道管理者作出最終的決定。WHAT-IF的基本作用：線性規(guī)劃模型的許多參數(shù)在建模時(shí)是難精確的，只能是對一些數(shù)據(jù)的估計(jì)，通過 WHAT-IF分析可以表明，系數(shù)估計(jì)值必須精確到怎么樣的程度，才能避免得出 錯(cuò)誤的最優(yōu)解，而且，可以找出哪些系數(shù)是需要重新精確定義的靈敏度參數(shù)。如果在研究結(jié)果之后，問題的條件發(fā)生了變化，通過WHAT-IF分析，即使不求 解，也可以表明模型參數(shù)的變化是

12、否會(huì)改變最優(yōu)解。（通常稱靈敏度分析；如果 模型的主要參數(shù)是管理層的政策決策而不是管理層所無法控制的外部數(shù)據(jù)，就可 以用這種前攝性分析方法）當(dāng)模型特定的參數(shù)反映管理政策決策時(shí)，WHAT-IF分析可以表明改變這些決策 對結(jié)果的影響，從而有效指導(dǎo)管理者作出最終的決定。SOLVER TABLE可以解決一系列數(shù)據(jù)單元格的數(shù)值改變的問題；當(dāng)在SOLVER TABLE的 第一欄里填入相關(guān)數(shù)據(jù)單元格的試驗(yàn)值時(shí)，請將第一行置空，以便在其他欄第一行的單元格 內(nèi)填入可變單元格和（或）相應(yīng)輸出單元格的公式。【具體練習(xí)】能使最優(yōu)解保持在相同的范圍稱為保持最優(yōu)解的允許變化范圍，簡稱最優(yōu)域。目標(biāo)函數(shù)中系數(shù)的允許變化范圍是指

13、系數(shù)在次范圍內(nèi)變化最優(yōu)解保持不變。EXCELSOLVER得出的靈敏度報(bào)告顯示了目標(biāo)函數(shù)允許的變化范圍。如果參數(shù)的微小變動(dòng)能引起最優(yōu)解的變化，就認(rèn)為它是敏感參數(shù)。二維SOLVER TABLE的使用，雖然他只能顯示一組試算值的變化給單元格帶來的影響， 但是使用符號(hào)“&”可以在表格中的一個(gè)單元格內(nèi)可以顯示多個(gè)單元格。任何需要在公式中顯示的文本必須在兩側(cè)加以引號(hào)（比如“（” &A22& ，” &B12& “）”） &符號(hào)這此表示連接。多系數(shù)變化可以用一下三種方法來做，在電子表格上作相應(yīng)的變動(dòng)；使用二維SOLVER表 格；應(yīng)用百分百法則。目標(biāo)函數(shù)系數(shù)同時(shí)變化的百分之百法則：如果目標(biāo)函數(shù)的系數(shù)同時(shí)變動(dòng)，計(jì)

14、算出每一系數(shù) 變動(dòng)量占該系數(shù)允許變化范圍允許變動(dòng)量的百分比，而后，將各個(gè)系數(shù)的變動(dòng)百分比相加， 如果所得的和不超過100%，最優(yōu)解不會(huì)改變，如果超過100%，則不能確定最優(yōu)解是否改 變。注：1.百分百法則可以用于確定在保持最優(yōu)解不變的條件下，目標(biāo)函數(shù)系數(shù)的變動(dòng)范圍當(dāng)模型中有大量的決策變量時(shí)，用電子表格系統(tǒng)的測試目標(biāo)函數(shù)一部分或全部系數(shù)的 同步變動(dòng)是相當(dāng)不實(shí)際的，因?yàn)榧词褂写硇缘淖儎?dòng)組合數(shù)也是大量的。SOLVER表格只能 用來檢驗(yàn)一次最多兩個(gè)系數(shù)的變化。但是，百分百法則通過將允許的增加或減少值在各個(gè)系 數(shù)之間分?jǐn)?，從而可以直接顯示出每個(gè)系數(shù)的允許變動(dòng)量。在線性規(guī)劃的研究結(jié)束后，也可以節(jié)省修正模

15、型的時(shí)間。影子價(jià)格：在給定線性規(guī)劃模型的最優(yōu)解和目標(biāo)函數(shù)相應(yīng)值的條件下，影子價(jià)格就是約束常 數(shù)增加微小的量1，使得目標(biāo)函數(shù)值增加的量，一般約束條件的影子價(jià)格顯示了約束條件右 端值的改變給目標(biāo)單元格帶來的增長率。它在右端值在允許變化范圍內(nèi)保持正確。函數(shù)約束的右端值允許變化范圍就是保持約束條件的影子價(jià)格有效時(shí)右端值變化的范圍?？紤]約束條件變化帶來的影響時(shí)，常用三種方法：運(yùn)用靈敏度報(bào)告只能用來分析左端值的 變化，而用電子表格和SOLVER表格分析左端系數(shù)和右端值的變化時(shí)過程是一樣的。而著 重分析右端值。通過在一個(gè)單元格內(nèi)輸入有關(guān)另一個(gè)單元格的公式，一維SOLVER表格可以解決相關(guān)的 單元格的試算值。

16、雖然一維SOLVER表格只能用來研究一個(gè)數(shù)據(jù)格的試算值變化的情況， 但是可以通過上述方法來解決二維問題。約束右端值同時(shí)變化的百分百法則：同時(shí)改變幾個(gè)或所有函數(shù)約束的約束右端值，如果這 些變化的幅度不大，那么可以用影子價(jià)格預(yù)測變動(dòng)產(chǎn)生的影響。為了判別這些變動(dòng)的幅度是 否允許，計(jì)算每一變動(dòng)占可行域所允許的增加值或減少值的百分比，如果所有的百分比之和 不超過100%，那么，影子價(jià)格還是有效的，如果所有的百分比之和超過100%，那就無法 確定影子價(jià)格是否有效了。運(yùn)輸問題和指派問題都屬于網(wǎng)絡(luò)配送問題。運(yùn)輸問題的基本概念：運(yùn)輸問題最關(guān)心的是以最低的總配送成本把出發(fā)地的任何產(chǎn)品運(yùn)送到每一個(gè)目的地；需求假設(shè)：

17、每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地， 與之類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須有出發(fā)地滿足。可行特征解：當(dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和時(shí)，運(yùn)輸問題才有可行解。成本假設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成本和所配送的數(shù)量成線性 比例關(guān)系，因此這個(gè)成本就等于配送的單位乘以所配送的數(shù)量。模型：如果問題可以完全描述成以參數(shù)形式，明確出發(fā)地，目的地，供應(yīng)量，需求量和 單位成本，符合需求假設(shè)和成本假設(shè)，那么這個(gè)問題（不管涉不涉及運(yùn)輸）都適用于運(yùn)輸問 題模型，最終目的都是要使配送的總成本最小。注：供應(yīng)量，需求量和單位成本提供了運(yùn)輸問題所需要的

18、一切數(shù)據(jù)。運(yùn)輸問題的電子表格模型用兩張分開的表格顯示單位成本數(shù)據(jù)和可變單元格，在兩張表中使 用相同的行號(hào)和列號(hào)。在可變單元格旁邊表明了的約束條件。整數(shù)解的性質(zhì)：只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然有所有 決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。我們在execl中用到的SOLVER來解決運(yùn)輸問題的另一種方法是單純形法，其中有運(yùn)輸單純 形法和網(wǎng)絡(luò)單純形法，它們的運(yùn)行速度很快，而網(wǎng)絡(luò)的越來越有競爭力。運(yùn)輸問題變體類型：供應(yīng)總量超過了需求總量。于是每一個(gè)供應(yīng)量代表了從這個(gè)出發(fā)地中配送出去的 最大數(shù)量（而不是一個(gè)固定的值）需求總量超過了供應(yīng)總量。于是

19、每一個(gè)需求量代表了在這個(gè)目的地中接收到的最 大數(shù)量（而不是一個(gè)固定的值）一個(gè)目的地同時(shí)存在著最小需求和最大需求，于是所有在這兩個(gè)數(shù)值之間的數(shù)量 都是可以接受的在配送中不能使用特定的出發(fā)地一一目的地組合目標(biāo)是使與配送數(shù)量有關(guān)的總利潤最大而不是最小此上問題均有一般的解法，以后討論。指派問題一般模型的假設(shè)：被指派者的數(shù)量和任務(wù)的數(shù)量是相同的每一個(gè)被指派者只完成一項(xiàng)任務(wù)每一項(xiàng)任務(wù)只能由一個(gè)被指派者完成每一個(gè)被指派者和每一項(xiàng)任務(wù)的組合都會(huì)有一個(gè)相關(guān)的成本問題的目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本達(dá)到最小 網(wǎng)絡(luò)表示法提供了另一種表示指派問題的方法 指派問題的變形：有一些被指派者并不能進(jìn)行某一項(xiàng)任務(wù)雖然每

20、一個(gè)被指派者完成一項(xiàng)任務(wù)，但是任務(wù)比被指派者多。所以其中某些任務(wù)并 沒有得到執(zhí)行雖然每一項(xiàng)任務(wù)只由一個(gè)被指派者完成，但是這里被指派者比要完成的任務(wù)數(shù)量多。 所以，其中有一些被指派者沒有指派到任務(wù)每一個(gè)被指派者可以同時(shí)被指派給多個(gè)任務(wù)每一項(xiàng)任務(wù)都可以由多個(gè)被指派者完成解決指派問題時(shí)有時(shí)會(huì)用到一種更為快捷的方法：匈牙利方法。網(wǎng)絡(luò)最優(yōu)化問題的求解，許多網(wǎng)絡(luò)最優(yōu)化問題實(shí)質(zhì)上是線性規(guī)劃問題的特殊類型，主要是構(gòu) 建出一個(gè)模型，即有弧的模型。（最重要的即為畫出網(wǎng)絡(luò)模型）最小費(fèi)用流問題是線性規(guī)劃問題的特殊類型，也叫做網(wǎng)絡(luò)配送問題。它的目標(biāo)是通過配送網(wǎng) 絡(luò)的運(yùn)輸成本最小?？梢杂镁W(wǎng)絡(luò)圖完整的表示最小成本問題?；?/p>

21、術(shù)語：所有最小費(fèi)用流問題都是用帶有通過其中的流的網(wǎng)絡(luò)表示的網(wǎng)絡(luò)中的圓圈被稱為節(jié)點(diǎn)如果節(jié)點(diǎn)產(chǎn)生的凈流量（流出減去流入）是一個(gè)確定的正數(shù)的話，這個(gè)節(jié)點(diǎn)就是供 應(yīng)點(diǎn)如果節(jié)點(diǎn)產(chǎn)生的凈流量是一個(gè)確定的負(fù)數(shù)的話，那么這個(gè)節(jié)點(diǎn)就是需求點(diǎn)如果節(jié)點(diǎn)產(chǎn)生的凈流量恒為零，那么這個(gè)節(jié)點(diǎn)就稱為轉(zhuǎn)運(yùn)點(diǎn)，我們把流出節(jié)點(diǎn)的量 等于流入節(jié)點(diǎn)的量稱為流量守恒網(wǎng)絡(luò)中的箭頭稱為弧允許通過某一條弧的最大流量稱為該弧的容量最小費(fèi)用流問題的假設(shè)：至少一個(gè)節(jié)點(diǎn)是供應(yīng)點(diǎn)至少一個(gè)節(jié)點(diǎn)是需求點(diǎn)所有剩下的節(jié)點(diǎn)都是轉(zhuǎn)運(yùn)點(diǎn)通過弧的流只允許沿著箭頭的方向流動(dòng)，通過弧的最大流量取決于該弧的容量（如 果流是雙向的話，則需要用一對箭頭指向相反方向的弧來表示）網(wǎng)

22、絡(luò)中有足夠的弧提供足夠的容量，使得所有在供應(yīng)點(diǎn)中產(chǎn)生的流都能夠到達(dá)需求 點(diǎn)在流的單位成本已知的前提下，通過每一條弧的流的成本和流量成正比最小費(fèi)用流問題的目標(biāo)是在滿足給定需求的條件下，使得通過網(wǎng)絡(luò)供應(yīng)的總成本最 下這類問題的解需要確定通過每一條弧的流有多大。具有可行解的特征：在以上的假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點(diǎn)所提供的流量總和等于需求點(diǎn)所需要 的流量總和時(shí)，最小費(fèi)用流問題有可行解。具有整數(shù)解的特征：只要其所有的供應(yīng)，需求和弧的容量都是整數(shù)值，那么任何最小費(fèi)用流 問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解。容量限制在任何有流量限制的弧的最小費(fèi)用流問題中都存在。最小費(fèi)用流問題的任一個(gè)節(jié)點(diǎn)都需要凈流量限制

23、Sumif的使用方法這里不加介紹。在這里也有網(wǎng)絡(luò)單純形法，它可以用來解決那些對于單純形法來說太大而無法解決的大型問 題。最小費(fèi)用流問題最重要的應(yīng)用可能是在配送網(wǎng)絡(luò)的運(yùn)營上。幾類典型的最小費(fèi)用流問題的應(yīng)用：應(yīng)用的類型供應(yīng)點(diǎn)轉(zhuǎn)運(yùn)點(diǎn)需求點(diǎn)配送網(wǎng)絡(luò)的運(yùn)作貨源中間存儲(chǔ)設(shè)備客戶固體廢棄物管理固體廢棄物源處理設(shè)備固體廢棄物掩埋地供應(yīng)網(wǎng)絡(luò)的運(yùn)作供應(yīng)商中間倉庫加工設(shè)備工廠協(xié)調(diào)產(chǎn)品組合工廠某一特定產(chǎn)品的生產(chǎn)某一特定產(chǎn)品的市場現(xiàn)金流管理某一特定時(shí)間的現(xiàn)金 來源短期投資期權(quán)在特定時(shí)間對現(xiàn)金的 需求最小費(fèi)用流問題的特殊類型：運(yùn)輸問題，沒有轉(zhuǎn)運(yùn)點(diǎn)和弧的容量限制指派問題，供應(yīng)量為一的供應(yīng)點(diǎn)，每項(xiàng)任務(wù)都是需求量為一的需求點(diǎn)轉(zhuǎn)

24、運(yùn)問題，在出發(fā)點(diǎn)與目的地之間會(huì)有轉(zhuǎn)運(yùn)點(diǎn)，除此斗魚運(yùn)輸問題一樣最大流問題最短路問題對于此些做法，可以用網(wǎng)絡(luò)單純形法，它可以跟快捷的進(jìn)行計(jì)算求解。對于最大流問題，它的目標(biāo)是使目標(biāo)單元格最大流量最大化。最大流問題的假設(shè)：網(wǎng)絡(luò)中所有流起源于一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)叫做源，所有的流終止于另一個(gè)節(jié)點(diǎn)，這個(gè) 節(jié)點(diǎn)叫做收點(diǎn)其余所有的節(jié)點(diǎn)叫做轉(zhuǎn)運(yùn)點(diǎn)通過每一個(gè)弧的流只允許沿著弧的箭頭所指方向流動(dòng)。由源出發(fā)的所有的弧背向源， 而所有終于收點(diǎn)的弧都指向收點(diǎn)。最大流問題的目標(biāo)是使得從源到收點(diǎn)的總流量最大。這個(gè)流量的大小可以用兩種等價(jià) 的方法來衡量，分別叫做從源點(diǎn)出發(fā)的流量和進(jìn)入收點(diǎn)的流量最大流問題與最小費(fèi)用流問題的區(qū)別：供應(yīng)點(diǎn)的供應(yīng)量和需求點(diǎn)的需求量都是固定的，而源和收點(diǎn)則不同最小費(fèi)用流問題中，不管是供應(yīng)點(diǎn)的數(shù)量還是需求點(diǎn)的數(shù)量都可能多于一個(gè)，而在最 大流問題中只能有一個(gè)源和收點(diǎn)（若有多個(gè)，可用其變形）注：當(dāng)網(wǎng)絡(luò)中實(shí)際行進(jìn)在多個(gè)節(jié)點(diǎn)結(jié)束時(shí)，我們在每一個(gè)這樣的節(jié)點(diǎn)和虛擬目標(biāo)地之間插入 一個(gè)長度為0的弧，從而使得網(wǎng)絡(luò)中仍然只有一個(gè)目標(biāo)地 最大流的一些實(shí)際應(yīng)用：通過配送網(wǎng)絡(luò)的流量最大通