數(shù)據(jù)、模型與決策課件：分配與網(wǎng)絡(luò)模型與決策

分配與網(wǎng)絡(luò)模型與決策本章主要內(nèi)容框架圖4.1運輸問題基本概念運輸問題最初起源于人們在日常生活中把某些物品或人們自身從一些地方轉(zhuǎn)移到另一些地方，要求所采用的運輸路線或運輸方案是最經(jīng)濟或成本最低的，這就成為了一個運籌學問題。隨著經(jīng)濟的不斷發(fā)展，現(xiàn)代物流業(yè)蓬勃發(fā)展，如何充分利用時間、信息、倉儲、配送和聯(lián)運體系創(chuàng)造更多的價值，向運籌學提出了更高的挑戰(zhàn)。要求科學地組織貨源、運輸和配送使得運輸問題變得日益復(fù)雜，但是其基本思想仍然是實現(xiàn)現(xiàn)有資源的最優(yōu)化配置。4.1運輸問題基本概念一般的運輸問題就是解決如何把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應(yīng)量和每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。平衡運輸問題的條件：1. 明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需求量（銷量）和單位成本。2. 需求假設(shè)：每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足。即“總供應(yīng)＝總需求”。3. 成本假設(shè)：從任何一個出發(fā)地到任何一個目的地的貨物配送成本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單位成本乘以所配送的數(shù)量（目標函數(shù)是線性的）。4.1運輸問題基本概念例4.1某公司有三個加工廠A1、A2、A3生產(chǎn)某產(chǎn)品，每日的產(chǎn)量分別為：7噸、4噸、9噸；該公司把這些產(chǎn)品分別運往四個銷售點B1、B2、B3、B4，各銷售點每日銷量分別為：3噸、6噸、5噸、6噸；從各工廠到各銷售點的單位產(chǎn)品運價如表4-1所示。問該公司應(yīng)如何調(diào)運這些產(chǎn)品，在滿足各銷售點的需要量的前提下，使總運費最少？

表4-1各工廠到各銷售點的單位產(chǎn)品運價（元/噸）B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）36564.2運輸問題數(shù)學模型和電子表格模型（1）產(chǎn)銷平衡運輸問題的數(shù)學模型具有m個產(chǎn)地Ai（i＝1,2,,m）和n個銷地

Bj（j＝1,2,,n）的運輸問題的數(shù)學模型為4.2運輸問題數(shù)學模型和電子表格模型對于例4.1，其數(shù)學模型如下：首先，三個產(chǎn)地A1、A2、A3的總產(chǎn)量為7＋4＋9＝20；四個銷地B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20。由于總產(chǎn)量等于總銷量，故該問題是一個產(chǎn)銷平衡的運輸問題。(1)決策變量設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量(i＝1,2,3;j=1,2,3,4)

（2）目標函數(shù)本問題的目標是使得總運輸費最小4.2運輸問題數(shù)學模型和電子表格模型（3）約束條件①滿足產(chǎn)地產(chǎn)量（3個產(chǎn)地的產(chǎn)品都要全部配送出去）②滿足銷地銷量（4個銷地的產(chǎn)品都要全部得到滿足）③非負4.2運輸問題數(shù)學模型和電子表格模型運輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解運輸問題，但Excel的“規(guī)劃求解”工具還是采用“單純形法”來求解。例4.1的電子表格模型4.2運輸問題數(shù)學模型和電子表格模型需要注意的是：運輸問題有這樣一個性質(zhì)（整數(shù)解性質(zhì)），只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。由于運輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿的話，就很不經(jīng)濟了。整數(shù)解性質(zhì)就避免了運輸量（運輸方案）為小數(shù)的麻煩。4.2運輸問題數(shù)學模型和電子表格模型（2）產(chǎn)大于銷（供過于求）運輸問題的數(shù)學模型（以滿足小的銷量為準）4.2運輸問題數(shù)學模型和電子表格模型（3）銷大于產(chǎn)（供不應(yīng)求）運輸問題的數(shù)學模型（以滿足小的產(chǎn)量為準）例4.2海華設(shè)備廠均衡運輸問題臺海華設(shè)備廠下設(shè)三個位于不同地點的分廠A、B、C，該三個分廠生產(chǎn)同一種設(shè)備，設(shè)每月的生產(chǎn)能力分別為20、30臺和40臺。海華設(shè)備廠有四個固定用戶，該四個用戶下月的設(shè)備需求量分別為20臺、15臺、23臺和32臺。設(shè)各分廠的生產(chǎn)成本相同，從各分廠至各用戶的單位設(shè)備運輸成本如表1所示。而且各分廠本月末的設(shè)備庫存量為零。問該廠應(yīng)如何安排下月的生產(chǎn)與運輸，才能在滿足四個用戶需求的前提下，使總運輸成本最低。表1海華設(shè)備廠運輸成本表分廠名稱運輸成本（元/臺）月生產(chǎn)能力（臺）用戶1用戶2用戶3用戶4分廠A7040806020分廠B701001105030分廠C80701304040下月設(shè)備需求量（臺）2015233290解：可用一個網(wǎng)絡(luò)圖來描述ABC432170408060701001105080701304020304020152332總供應(yīng)量=20+30+40=90（臺），總需求量=20+15+23+32=90（臺），供應(yīng)量之和等于需求量之和，供需均衡。決策變量是下月各分廠為各用戶生產(chǎn)與運輸?shù)脑O(shè)備數(shù)量。可設(shè)：分廠A下月為四個用戶生產(chǎn)和運輸?shù)脑O(shè)備數(shù)量分別為A1，A2

，A3

，A4

（臺）；分廠B下月為四個用戶生產(chǎn)和運輸?shù)脑O(shè)備數(shù)量分別為B1，B2

，B3

，B4

（臺）；分廠C下月為四個用戶生產(chǎn)和運輸?shù)脑O(shè)備數(shù)量分別為C1，C2

，C3

，C4

（臺）。目標函數(shù)是總運輸成本最小化，總運輸成本=70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2

+130C3+40C4約束條件有兩部分，第一部分是需求約束，各用戶從各分廠收到的設(shè)備總數(shù)不得少于它們的需求量，線性規(guī)劃模型為：

Min70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2+130C3+40C4

s.t.A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32A1+A2+A3+A4=20B1+B2+B3+B4=30C1+C2+C3+C4=40A1，A2

，A3

，A4

，B1，B2

，B3

，B4

，C1，C2

，C3，C4

≥0分廠名稱運輸量（臺）用戶1用戶2用戶3用戶4工廠A07130工廠B200100工廠C08032

運行結(jié)果4.2運輸問題數(shù)學模型和電子表格模型例4.3某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示。問應(yīng)如何調(diào)運，可使得總運輸費最小？運輸費用表

B1B2B3產(chǎn)量A113151278A211292245銷量533665（銷大于產(chǎn)）5.2運輸問題數(shù)學模型和電子表格模型解：由表知，總產(chǎn)量為78+45=123，總銷量為53+36+65=154，銷大于產(chǎn)(供不應(yīng)求)。數(shù)學模型如下：設(shè)xij為產(chǎn)地Ai運往銷地Bj的物品數(shù)量4.2運輸問題數(shù)學模型和電子表格模型

電子表格模型5.3各種變形的運輸問題建?，F(xiàn)實生活中符合產(chǎn)銷平衡運輸問題每一個條件的情況很少。一個特征近似但其中的一個或者幾個特征卻并不符合產(chǎn)銷平衡運輸問題條件的運輸問題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：（1）總供應(yīng)大于總需求。每一個供應(yīng)量（產(chǎn)量）代表了從其出發(fā)地中配送出去的最大數(shù)量（而不是一個固定的數(shù)值,≤）。（2）總供應(yīng)小于總需求。每一個需求量（銷量）代表了在其目的地中所接收到的最大數(shù)量（而不是一個固定的數(shù)值,≤）。（3）一個目的地同時存在著最小需求和最大需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接收的（≥,≤）。（4）在配送中不能使用特定的出發(fā)地—目的地組合（xij=0）。（5）目標是使與配送數(shù)量有關(guān)的總利潤最大而不是使總成本最小。（Min－>Max）5.3各種變形的運輸問題建模例4.4某公司決定使用三個有生產(chǎn)余力的工廠進行四種新產(chǎn)品的生產(chǎn)。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來衡量（見表4-7的最右列）。而每種產(chǎn)品每天有一定的需求量（見表的最后一行）。每家工廠都可以制造這些產(chǎn)品，除了工廠2不能生產(chǎn)產(chǎn)品3以外。然而，每種產(chǎn)品在不同工廠中的單位成本是有差異的（如表）?，F(xiàn)在需要決定的是在哪個工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。產(chǎn)品生產(chǎn)的有關(guān)數(shù)據(jù)單位成本（元）生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠24029－2375工廠33730272145需求量203030404.3各種變形的運輸問題建模解：指定工廠生產(chǎn)產(chǎn)品可以看作運輸問題來求解。本題中，工廠2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件x23＝0；并且，總供應(yīng)（75+75+45=195）>總需求（20+30+30+40=120）。其數(shù)學模型如下：設(shè)xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量5.3各種變形的運輸問題建模例4.4的電子表格模型產(chǎn)品4分在2個工廠生產(chǎn)轉(zhuǎn)運問題運輸問題的擴展，其中中間節(jié)點代表轉(zhuǎn)運節(jié)點，加入這個節(jié)點的目的是指代地點位置，例如倉庫。案例——瑞恩電子公司的轉(zhuǎn)運問題例4.5瑞恩電子是一家電子公司，其生產(chǎn)線分別位于丹佛和亞特蘭大，在每條生產(chǎn)線上生產(chǎn)出來的商品都可以被運送到公司在堪薩斯城或者是路易斯維爾地區(qū)的倉庫中，公司把這些地區(qū)的倉庫中的商品發(fā)給底特律、邁阿密、達拉斯和新奧爾良的零售商。600400200300350150612438765工廠開始節(jié)點倉庫轉(zhuǎn)載節(jié)點零售商丹佛600亞特蘭大400底特律200邁阿密150達拉斯350新奧爾良300堪薩斯城路易斯維爾23312635644網(wǎng)絡(luò)圖

線性規(guī)劃模型決策變量：令xij代表從節(jié)點i到節(jié)點j運輸?shù)募?shù)。目標函數(shù)：運輸線路的總運輸成本最小起點節(jié)點約束：輸出的總量減去輸入的總量必須小于或等于該節(jié)點的商品供給量終點節(jié)點約束：輸入的總量減去輸出的總量必須等于該節(jié)點的需求。轉(zhuǎn)運節(jié)點約束：輸出的總量必須等于輸入的總量。瑞恩電子問題的線性規(guī)劃模型求解結(jié)果：

見Excel文件瑞恩電子轉(zhuǎn)運問題的最優(yōu)解更一般的轉(zhuǎn)運問題假設(shè)可以直接從亞特蘭大運輸商品到新奧爾良，單位運輸費用為4美元，且從達拉斯運到新奧爾良的單位運費為1美元。12438765工廠開始節(jié)點倉庫轉(zhuǎn)載節(jié)點丹佛600亞特蘭大400底特律200邁阿密150達拉斯350新奧爾良300堪薩斯城路易斯維爾23312636564441線性規(guī)劃模型問題的變化總供給不等于總需求最大化目標函數(shù)路線容量或者路線最小量（有容量限制的轉(zhuǎn)運問題）不可接受的路線轉(zhuǎn)運問題的一般線性規(guī)劃模型這里，xij表示從節(jié)點i到節(jié)點j的運量；cij表示從節(jié)點i到節(jié)點j的單位運價；si表示起點節(jié)點i的供給量；dj表示終點節(jié)點j的需求量。實踐——寶潔公司在產(chǎn)品供應(yīng)上的啟發(fā)式探索幾年前，寶潔公司開始了一個重大戰(zhàn)略計劃，稱為北美產(chǎn)品供應(yīng)研究。寶潔公司想綜合運用它的資源供應(yīng)，最優(yōu)化其北美的產(chǎn)品配送系統(tǒng)。一個決策支持系統(tǒng)用于輔助這個被稱為產(chǎn)品供應(yīng)啟發(fā)式探索的項目（PSH），這個系統(tǒng)是基于和本章我們描述的轉(zhuǎn)運模型非常相似的轉(zhuǎn)運模型。以前，很多寶潔公司的產(chǎn)品聚集成幾個組，這些組是共享相同的技術(shù)且可以在同一個工廠生產(chǎn)的。應(yīng)用了轉(zhuǎn)運模型的PSH項目被用于設(shè)計這些產(chǎn)品組的采購選擇時的產(chǎn)品策略團隊的對策中。生產(chǎn)產(chǎn)品組的工廠為資源節(jié)點，公司區(qū)域配送中心為轉(zhuǎn)運節(jié)點，顧客需求區(qū)域為終點節(jié)點，直接運輸?shù)筋櫩蛥^(qū)域或者通過配送中心運送都是可行的。產(chǎn)品策略小組用相互影響的啟發(fā)式算法解決了各種產(chǎn)品供應(yīng)和配送相關(guān)的問題。例如，小組想知道如果關(guān)掉5個工廠中的2個，把產(chǎn)品集中在剩下的3個工廠中生產(chǎn)，那么會產(chǎn)生什么影響？PSH將會刪除兩個相應(yīng)的供應(yīng)節(jié)點，還要對剩下3個工廠的生產(chǎn)能力進行必要的修改，然后求解這個轉(zhuǎn)運問題。產(chǎn)品策略小組然后可以檢查新的最優(yōu)解，接著再對模型做進一步修改，再求解，再檢查結(jié)果，如此循環(huán)。PSH被所有使用者看成是一個非常有價值的決策支持系統(tǒng)。當寶潔公司按照研究得出的結(jié)果進行實施時，它實現(xiàn)了每年2億美元的節(jié)約。寶潔應(yīng)用PSH在北美市場獲得了極大的成功。實踐——寶潔公司在產(chǎn)品供應(yīng)上的啟發(fā)式探索4指派問題在現(xiàn)實生活中，經(jīng)常會遇到指派人員做某項工作（任務(wù)）的情況。指派問題的許多應(yīng)用是用來幫助管理人員解決如何為一項即將開展的工作指派人員的問題。其他的一些應(yīng)用如為工作指派機器、設(shè)備或工廠等。指派問題也稱分配問題，主要研究人和工作（任務(wù)）間如何匹配，以使所有工作完成的效率實現(xiàn)最優(yōu)化。形式上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員，所需要解決的問題就是要確定出指派哪個人去完成哪項工作。指派問題指派問題的假設(shè)：（1）人的數(shù)量和工作的數(shù)量相等；（2）每個人只能完成一項工作；（3）每項工作只能由一個人來完成；（4）每個人和每項工作的組合都會有一個相關(guān)的成本（單位成本）；（5）目標是要確定如何指派才能使總成本最小。指派問題設(shè)決策變量xij為第i個人做第j項工作，而已知目標函數(shù)系數(shù)cij為第i個人完成第j項工作所需要的單位成本。平衡指派問題的數(shù)學模型為指派問題需要說明的是：指派問題實際上是一種特殊的運輸問題。其中出發(fā)地是人，目的地是工作。只不過，每一個出發(fā)地的供應(yīng)量都為1（因為每個人都要完成一項工作），每一個目的地的需求量都為1（因為每項工作都要完成）。由于運輸問題有“整數(shù)解性質(zhì)”，因此，沒有必要加上所有決策變量都是0-1變量的約束。指派問題是一種特殊的線性規(guī)劃問題，有一種快捷的求解方法：匈牙利方法（HungarianMethod），但Excel的“規(guī)劃求解”工具還是采用“單純形法”來求解。指派問題例4.6某公司的營銷經(jīng)理將要主持召開一年一度的由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議。為了更好地安排這次會議，他安排小張、小王、小李、小劉等四個人，每個人負責完成下面的一項工作：A、B、C和D。由于每個人完成每項任務(wù)的時間和工資不同（如表4-14所示）。問如何指派，可使總成本最小。人員每一項工作所需要的時間（小時）每小時工資（元）工作A工作B工作C工作D小張3541274014小王4745325112小李3956364313小劉3251254615指派問題解：該問題是一個典型的指派問題。單位成本為每個人做每項工作的總工資目標是要確定哪個人做哪一項工作，使總成本最小供應(yīng)量為1代表每個人都只能完成一項工作需求量為1代表每項工作也只能有一個人來完成總?cè)藬?shù)（4人）和總?cè)蝿?wù)數(shù)（4項）相等

指派問題數(shù)學模型：設(shè)xij為指派人員i去做工作j（i，j＝1,2,3,4)指派問題電子表格模型

各種變形的指派問題建模經(jīng)常會遇到指派問題的變形，之所以稱它們?yōu)樽冃?，是因為它們都不滿足平衡指派問題所有假設(shè)之中的一個或者多個。一般考慮下面的一些特征：（1）有些人并不能進行某項工作（相應(yīng)的xij＝0）;（2）雖然每個人完成一項任務(wù)，但是任務(wù)比人多(人少事多);（3）雖然每一項任務(wù)只由一個人完成，但是人比任務(wù)多（人多事少）；（4）某人可以同時被指派給多個任務(wù)（一人可做幾件事）；（5）某事可以由多人共同完成（一事可由多人完成）；（6）目標是與指派有關(guān)的總利潤最大而不是使總成本最小；（7）實際需要完成任務(wù)數(shù)不超過總?cè)藬?shù)也不超過總?cè)蝿?wù)數(shù)。網(wǎng)絡(luò)最優(yōu)化問題網(wǎng)絡(luò)最優(yōu)化問題的基本概念網(wǎng)絡(luò)最優(yōu)化問題的四種主要類型：最小費用流、最大流、最短路、最小支撐樹各種網(wǎng)絡(luò)最優(yōu)化問題的建模與應(yīng)用網(wǎng)絡(luò)最優(yōu)化問題基本概念網(wǎng)絡(luò)在各種實際背景問題中以各種各樣的形式存在。交通、電子和通訊網(wǎng)絡(luò)遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡(luò)規(guī)劃也廣泛用于解決不同領(lǐng)域中的各種問題，如生產(chǎn)、分配、項目計劃、廠址選擇、資源管理和財務(wù)策劃等等。網(wǎng)絡(luò)規(guī)劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效的直觀和概念上的幫助，廣泛應(yīng)用于科學、社會和經(jīng)濟活動的各個領(lǐng)域中。近些年來，運籌學（管理科學）中一個振奮人心的發(fā)展是它的網(wǎng)絡(luò)最優(yōu)化問題的方法論和應(yīng)用方面都取得了不同尋常的飛速發(fā)展。許多研究的對象往往可以用一個圖表示，研究的目的歸結(jié)為圖的極值問題。運籌學中研究的圖具有下列特征：

(1)用點表示研究對象，用連線（不帶箭頭的邊或帶箭頭的弧）表示對象之間某種關(guān)系；

(2)強調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀；

(3)每條邊上都賦有一個權(quán)，其圖稱為賦權(quán)圖。實際中權(quán)可以代表兩點之間的距離、費用、利潤、時間、容量等不同的含義；

(4)建立一個網(wǎng)絡(luò)模型，求最大值或最小值。對于該網(wǎng)絡(luò)圖，可以提出許多極值問題網(wǎng)絡(luò)最優(yōu)化問題基本概念（1）將某個點vi的物資或信息送到另一個點vj，使得運送總成本最小。這屬于最小費用流問題。（2）將某個點vi的物資或信息送到另一個點vj，使得總流量最大。這屬于最大流問題。（3）從某個點vi出發(fā)到達另一個點vj，怎樣安排路線使得總距離最短或總費用最小。這屬于最短路問題。（4）點vi表示自來水廠及用戶，vi與vj之間的邊表示兩點間可以鋪設(shè)管道，權(quán)為vi與vj間鋪設(shè)管道的距離或費用，極值問題是如何鋪設(shè)管道，將自來水送到其他5個用戶并且使總的費用最小。這屬于最小支撐樹問題。

(5)售貨員從某個點vi出發(fā)走過其他所有點后回到原點vi，如何安排路線使總路程最短。這屬于貨郎擔問題或旅行售貨員問題。（6）郵遞員從郵局vi出發(fā)要經(jīng)過每一條邊將郵件送到用戶手中，最后回到郵局vi，如何安排路線使總路程最短。這屬于中國郵遞員問題。網(wǎng)絡(luò)最優(yōu)化問題類型主要包括：（1）最小費用流問題；（2）最大流問題；（3）最短路問題；（4）最小支撐樹問題；（5）貨郎擔問題和中國郵路問題，等等5最小費用流問題最小費用流問題的模型在網(wǎng)絡(luò)最優(yōu)化中扮演著重要的角色，因為它的適用性很廣，并且求解方法容易。通常最小費用流問題用于最優(yōu)化貨物從供應(yīng)點到需求點的網(wǎng)絡(luò)。目標是在通過網(wǎng)絡(luò)配送貨物時，以最小的成本滿足需求，一種典型的應(yīng)用就是使得配送網(wǎng)絡(luò)的運營最優(yōu)。最小費用流問題的特殊類型包括運輸問題和指派問題，以及在下面將要提到的兩種重要類型：最大流問題和最短路問題。最小費用流問題例4.7某公司有兩個工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運送到兩個倉庫中。其配送網(wǎng)絡(luò)圖如圖所示。目標是確定一個運輸方案（即每條路線運送多少單位的產(chǎn)品），使通過配送網(wǎng)絡(luò)的總運輸成本最小。最小費用流問題最小費用流問題的三個基本概念：1、最小費用流問題的構(gòu)成（網(wǎng)絡(luò)表示）（1）節(jié)點：包括供應(yīng)點、需求點和轉(zhuǎn)運點；（2）?。嚎尚械倪\輸線路（節(jié)點i->節(jié)點j），經(jīng)常有最大流量（容量）的限制。2、最小費用流問題的假設(shè)（1）至少一個供應(yīng)點；（2）至少一個需求點；（3）剩下都是轉(zhuǎn)運點；（4）通過弧的流只允許沿著箭頭方向流動，通過弧的最大流量取決于該弧的容量；（5）網(wǎng)絡(luò)中有足夠的弧提供足夠容量，使得所有在供應(yīng)點中產(chǎn)生的流都能夠到達需求點；（有解）（6）在流的單位成本已知前提下，通過每一條弧的流的成本和流量成正比；（目標是線性的）（7）最小費用流問題的目標在滿足給定需求條件下，使得通過網(wǎng)絡(luò)供應(yīng)的總成本最?。ɑ蚩偫麧欁畲螅?。最小費用流問題的數(shù)學模型為：（1）決策變量：設(shè)fij為通過?。ü?jié)點i->節(jié)點j）的流量。（2）目標是通過網(wǎng)絡(luò)供應(yīng)的總成本最小。（3）約束條件

①所有供應(yīng)點：凈流量（總流出－總流入）為正； ②所有轉(zhuǎn)運點：凈流量為零； ③所有需求點：凈流量為負； ④所有弧的流量fij受到弧的容量限制； ⑤所有弧的流量fij非負。例4.7最小費用流問題的數(shù)學模型為：（1）決策變量：設(shè)fij為通過弧(節(jié)點i->節(jié)點j)的流量。（2）目標函數(shù)本問題的目標是總運輸成本最?。?）約束條件(節(jié)點凈流量、弧的容量限制、非負）①供應(yīng)點F1:

供應(yīng)點F2: ②轉(zhuǎn)運點DC: ③需求點W1:

需求點W2: ④弧的容量限制：⑤非負：例4.7的電子表格模型：列出了網(wǎng)絡(luò)中的弧和各弧所對應(yīng)的容量、單位成本。決策變量為通過弧的流量。目標是計算流量的總成本。每個節(jié)點的凈流量為約束條件。供應(yīng)點的凈流量為正，需求點的凈流量為負，而轉(zhuǎn)運點的凈流量為0。這里用了一個竅門：用兩個SUMIF函數(shù)的差來計算每個節(jié)點的凈流量，這樣快捷且不容易犯錯。

最小費用流問題最小費用流問題有五種重要的特殊類型：（1）運輸問題：有出發(fā)地(供應(yīng)點-供應(yīng)量)和目的地(需求點-需求量)，沒有轉(zhuǎn)運點和弧的容量限制，目標是總運輸成本最?。ɑ蚩偫麧欁畲螅?。（2）指派類型：出發(fā)地(供應(yīng)點-供應(yīng)量為1)是人，目的地(需求點-需求量為1)是任務(wù)，沒有轉(zhuǎn)運點和弧的容量限制，目標是總指派成本最小（或總利潤最大）。（3）轉(zhuǎn)運問題：有出發(fā)地(供應(yīng)點-供應(yīng)量)和目的地(需求點-需求量)，有轉(zhuǎn)運點，但沒有弧的容量限制(或有容量限制)，目標是總流量費用最?。ɑ蚩偫麧欁畲螅?/p>

最小費用流問題最小費用流問題有五種重要的特殊類型(續(xù))：（4）最大流問題：有供應(yīng)點、需求點、轉(zhuǎn)運點、弧的容量限制，但沒有供應(yīng)量和需求量的限制，目標是通過網(wǎng)絡(luò)到目的地的總流量最大。（5）最短路問題：有供應(yīng)點(供應(yīng)量為1)、需求點(需求量為1)、轉(zhuǎn)運點、沒有弧的容量限制，目標是通過網(wǎng)絡(luò)到目的地的總距離最短。最大流問題在許多實際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等。而網(wǎng)絡(luò)系統(tǒng)最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)中的實際問題起著十分重要的作用。最大流問題也與網(wǎng)絡(luò)中的流有關(guān)，但目標不是使得流的總成本最小，而是尋找一個流的方案，使得通過網(wǎng)絡(luò)的總流量最大。除了目標（流最大化和成本最小化）不一樣外，最大流問題的特征和最小費用流問題的特征非常相似。例4.8某公司要從起始點vs（發(fā)點）運送貨物到目的地vt（收點），其網(wǎng)絡(luò)圖如下圖（下一張幻燈片)所示。圖中每條弧（節(jié)點i->節(jié)點j）旁邊的權(quán)cij表示這段運輸線路的最大通過能力（容量）。要求制定一個運輸方案，使得從vs到vt的運貨量達到最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。

最大流問題例4.8最大流問題的線性規(guī)劃數(shù)學模型：（1）決策變量設(shè)fij為通過?。ü?jié)點i->節(jié)點j）的流量。（2）目標函數(shù)本問題的目標是從vs流出的總流量最大。（3）約束條件(轉(zhuǎn)運點的凈流量為0、弧的容量限制、非負）

最大流問題例4.8最大流問題電子表格模型最大流問題最大流問題的變形主要在于：有多個發(fā)點（供應(yīng)點）和多個收點（需求點）。例4.9

在例4.8的基礎(chǔ)上，增加了一個發(fā)點ps、一個收點pt、兩個轉(zhuǎn)運點p1和p2、以及與之相連的7條弧，如下圖（下一張幻燈片）所示。目標是從vs和ps兩個發(fā)點運出的總流量最大。這是一個有2個發(fā)點（供應(yīng)點）和2個收點（需求點）的最大流問題。最大流問題

最大流問題例4.9的數(shù)學模型例4.3的電子表格模型最大流問題最大流問題的一些實際應(yīng)用：（1）通過配送網(wǎng)絡(luò)的流量最大，如例4.8和例4.9；（2）通過管道運輸系統(tǒng)的油的流量最大；（3）通過輸水系統(tǒng)的水的流量最大；（4）通過交通網(wǎng)絡(luò)的車輛的流量最大；等等。最大流問題例4.10計劃編制問題。某市政工程公司在未來5～8月份內(nèi)需完成4項工程：修建一條地下通道、修建一座人行天橋、新建一條道路及道路維修。工期和所需勞動力見表。該公司共有勞動力120人，任一工程在一個月內(nèi)的勞動力投入不能超過80人，問公司應(yīng)如何分配勞動力完成所有工程，是否能按期完成？工程工期需要勞動力（人）A.地下通道5～7月100B.人行天橋6～7月80C.新建道路5～8月200D.道路維修8月80

最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來求解（可設(shè)xij為工程i在j月投入的勞動力）外，還可以用最大流的方法來求解。將工程計劃用網(wǎng)絡(luò)圖（下一張幻燈片）表示。圖中的節(jié)點5、6、7、8分別表示5～8月份，Ai、Bi、Ci、Di表示工程在第i個月內(nèi)完成的部分。用弧表示某月完成某項工程的狀態(tài)，弧的流量為所投入的勞動力，受到勞動力限制（弧旁邊的數(shù)字表示弧的容量，從S開始的弧，其容量為該公司共有勞動力120人；從節(jié)點5、6、7、8開始的弧以及到節(jié)點A、B、C、D的弧，其容量為任一工程在一個月內(nèi)的勞動力投入不能超過80人；到收點T的弧，其容量為每個工程所需勞動力）。合理安排每個月各工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求圖5-8從發(fā)點到收點的最大流問題。

最大流問題注意：增加一個起點S和一個終點T，其容量是供應(yīng)量和需求量

最大流問題例4.10市政工程公司勞動力分配電子表格模型，求解結(jié)果（每個月的勞動力分配）如表所示。5月份有剩余勞動力20人，4項工程恰好按期完成。月份投入勞動力項目A項目B項目C項目D51002080612080407120408081204080合計4601008020080

最小費用最大流問題

在實際的網(wǎng)絡(luò)應(yīng)用當中，當涉及到流的問題時，有時考慮的不只是流量，還要考慮費用多少的問題。比如一個鐵路運輸系統(tǒng)的網(wǎng)絡(luò)流，不但要考慮網(wǎng)絡(luò)系統(tǒng)的貨運量最大，還要考慮總費用最小。最小費用最大流就是要解決這一類的問題。所謂最小費用最大流問題就是：給定一個帶收點和發(fā)點的網(wǎng)絡(luò)，對每一條弧（節(jié)點i->節(jié)點j）,除了給出容量cij外，還給出了這條弧的單位流量的費用bij

，要求一個最大流F，并使得總運費用最小。最小費用最大流問題也是一個線性規(guī)劃問題。例4.10某公司有一個管道網(wǎng)絡(luò)（如圖5-10所示，下一張幻燈片），使用這個網(wǎng)絡(luò)可以把石油從采地v1運送到銷地v7。由于輸油管道長短不一，每段管道除了有不同的流量cij限制外，還有不同的單位流量的費用bij。每段管道旁邊括號內(nèi)的數(shù)值意義為（cij，bij）。如果使用這個網(wǎng)絡(luò)系統(tǒng)，從采地v1向銷地v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最小？

最小費用最大流問題

(3,2)(6,3)(2,8)(1,3)(4,4)(2,3)(5,7)(2,4)（2,5）(3,4)(6,6)v1v7v6v5v4v3v2最小費用最大流問題

最小費用最大流問題

解：用線性規(guī)劃來求解此題，分為兩步走。第一步：先求出此網(wǎng)絡(luò)系統(tǒng)的最大流量F。數(shù)學模型P164電子表格模型P165求得的最大流量F=10第二步：在最大流量F的所有解中，找出一個最小費用的解。數(shù)學模型P166電子表格模型P166求得的最小費用為145

最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等最短路問題的最普遍的應(yīng)用是在兩個點之間尋找最短路，是最小費用流問題的一種特殊類型：源的供應(yīng)量為1、目的地（需求點）的需求量為1、轉(zhuǎn)運點的凈流量為0、沒有弧的容量限制，目標：通過網(wǎng)絡(luò)到目的地的總距離最短。

最短路問題例4.11某人每天從住處v1開車到工作地v7上班，圖中各弧旁的數(shù)字表示道路的長度（公里），試問該人應(yīng)選擇哪條路線，從家出發(fā)到工作地，路上行駛的總距離最短。v1v2v3v4v5v6v729683.51452.53

最短路問題解：這是一個最短路問題。其數(shù)學模型為：（1）決策變量：設(shè)xij為弧(節(jié)點i->節(jié)點j)是否走（1表示走，0表示不走）。（2）目標函數(shù)本問題的目標是總距離最短（3）約束條件(節(jié)點凈流量、非負）P169

最短路問題例4.11的最短路問題的電子表格模型最短路問題的應(yīng)用很廣，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局、選址等。下面舉兩個例子：（1）設(shè)備更新問題；（2）新產(chǎn)品開發(fā)時間問題。

最短路問題例4.12設(shè)備更新問題。某工廠的某臺機器可連續(xù)工作4年，決策者每年年初都要決定機器是否需要更新。若購置新機器，就要支付購置費用；若繼續(xù)使用，則需要支付維修與運行費用，而且隨著機器使用年限的增加費用逐年增多。已知計劃期（4年）中每年的購置價格及維修與運行費用。試制定今后4年的機器更新計劃，使總的支付費用最少。年限1234購置費（萬元）2.52.62.83.1維修與運行費（萬元）11.524

最短