1、第四講 運輸、指派問題與網絡最優化數據，模型與決策Data, Model and Decisions數據、模型與決策數據、模型與決策第四講第四講運輸、指派問題與網絡最優化運輸、指派問題與網絡最優化第四講 運輸、指派問題與網絡最優化數據，模型與決策主要內容主要內容 P&T公司配送問題公司配送問題 運輸問題運輸問題 運輸問題的特征運輸問題的特征 運輸問題的一個獲獎應用運輸問題的一個獲獎應用 各種運輸問題變體各種運輸問題變體 特賽格公司的選地址問題特賽格公司的選地址問題第四講 運輸、指派問題與網絡最優化數據，模型與決策 指派問題指派問題 指派問題模型指派問題模型 指派問題的變形指派問題的變形

2、 指派問題的應用指派問題的應用主要內容主要內容第四講 運輸、指派問題與網絡最優化數據，模型與決策主要內容主要內容 飛利浦石油公司運輸工具替換計劃飛利浦石油公司運輸工具替換計劃 網絡最優化模型的應用網絡最優化模型的應用 網絡最優化問題類型網絡最優化問題類型 最小費用流問題最小費用流問題 最短路問題最短路問題 最小支撐樹問題最小支撐樹問題第四講 運輸、指派問題與網絡最優化數據，模型與決策配送問題配送問題P&T公司是一家由家族經營的小公司。它收購生菜并在食品罐頭廠中把它們家工成罐頭，然后在把這些罐頭食品分銷到各地。公司的一個主要產品是豌豆罐頭，在三個食品罐頭廠生產（靠近華盛頓的貝林翰；俄勒岡

3、州的尤基尼；明尼蘇達州的艾爾貝李）然后用卡車把它們運送到美國西部的四個分銷倉庫（加利福尼亞州的薩克拉門托；猶他州的鹽湖城；南達科他州的賴皮特城；新墨西哥州的澳爾巴古）。實際問題實際問題第四講 運輸、指派問題與網絡最優化數據，模型與決策配送問題配送問題實際問題實際問題第四講 運輸、指派問題與網絡最優化數據，模型與決策配送問題配送問題當前的當前的運輸策略：1因為在貝林翰的罐頭廠距離倉庫最遠，所以把它的產品運送到最近的一個倉庫。也就是薩克拉門托的那個倉庫。如果還有剩余的話，就把它們運送到鹽湖城的倉庫中去。 2因為在澳爾巴古的倉庫距離食品罐頭廠最遠，所以就要從最近的一個罐頭廠（艾爾貝李的罐頭廠）中運送

4、產品到澳爾巴古。如果還有剩余的話，就要運送到賴皮特城的倉庫中。 3用尤基尼的罐頭廠滿足其他倉庫的剩余需求。實際問題實際問題第四講 運輸、指派問題與網絡最優化數據，模型與決策配送問題配送問題現在所要做的是要檢查當前的運輸計劃，看看是否能夠制定出一個新的運輸計劃，使總運輸成本下降到一個絕對最小值。實際問題實際問題第四講 運輸、指派問題與網絡最優化數據，模型與決策運輸問題是物流中的一個普遍問題，如何以盡可能小的成本把貨物從一系列起始地（sources）（如工廠、倉庫）運輸到一系列終點地（destinations）（如倉庫、顧客）運輸問題運輸問題運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，

5、模型與決策運輸問題運輸問題 SourcesDestinations運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，模型與決策P&T公司運輸問題公司運輸問題運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，模型與決策P&T公司運輸問題公司運輸問題運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，模型與決策P&T公司運輸問題公司運輸問題運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，模型與決策P&T公司運輸問題公司運輸問題運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，模型與決策P&T公司運輸問題公司運輸問題Excel建模

6、建模 運輸問題運輸問題第四講 運輸、指派問題與網絡最優化數據，模型與決策每一個出發地都有一定的供應量（供應量（supply）配送到目的地，每一個目的地都有需要從一定的需求需求量（量（demand），接收從出發地發出的產品需求假設需求假設（The Requirements Assumption） 可行解特性可行解特性（The Feasible Solutions Property） 成本假設成本假設（The Cost Assumption）整數解性質整數解性質（Integer Solutions Property）運輸問題的特征運輸問題的特征 運輸問題特征運輸問題特征第四講 運輸、指派問題與網絡

7、最優化數據，模型與決策需求假設需求假設（The Requirements Assumption）：每一個出發地都有一個固定的供應量，所有的供應量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發地滿足 需求假設需求假設運輸問題特征運輸問題特征第四講 運輸、指派問題與網絡最優化數據，模型與決策可行解特性（可行解特性（The Feasible Solutions Property）：）：當且僅當供應量的總和等于需求量的總和時，運輸問題才有可行解 可行解特性可行解特性運輸問題特征運輸問題特征第四講 運輸、指派問題與網絡最優化數據，模型與決策成本假設（成本假設（T

8、he Cost Assumption）：）：從任何一個出發地到任何一個目的地的貨物配送成本和所配送的數量成線性比例關系，因此這個成本就等于配送的單位成本乘以所配送的數量 成本假設成本假設運輸問題特征運輸問題特征第四講 運輸、指派問題與網絡最優化數據，模型與決策整數解性質（整數解性質（Integer Solutions Property）：）：只要它的供應量和需求量都是整數，任何有可行解的運輸問題必然有所有決策變量都是整數的最優解。因此，沒有必要加上所有變量都是整數的約束條件 整數解性質整數解性質運輸問題特征運輸問題特征第四講 運輸、指派問題與網絡最優化數據，模型與決策P&G重新設計制造

9、和配送體系重新設計制造和配送體系 ：90S 成百上千個供應商成百上千個供應商 50多個產品類別多個產品類別 超過超過60個的工廠個的工廠 15個配送中心個配送中心 超過超過1000個的顧客群體個的顧客群體 運輸問題的一個獲獎應用運輸問題的一個獲獎應用 獲獎應用獲獎應用第四講 運輸、指派問題與網絡最優化數據，模型與決策為每個單獨的產品種類設計并求解運輸問題對于針對還在運行的工廠的每一個選擇，為每 一個產品種類解決相應的運輸問題體現了從這 些工廠運送產品到配送中心或顧客區所需要的 配送成本是多少。在找出最好的新生產和配送系統的過程之中解 決了許多這樣的運輸問題 北美工廠數減少了20%，并且公司每年

10、節省了2 億美元的稅前費用 運輸問題的一個獲獎應用運輸問題的一個獲獎應用 獲獎應用獲獎應用第四講 運輸、指派問題與網絡最優化數據，模型與決策供應總量超出了需求總量供應總量超出了需求總量 供應總量小于需求總量供應總量小于需求總量 一個目的地同時存在著最小需求和最大需求一個目的地同時存在著最小需求和最大需求在配送中不能使用特定的出發地在配送中不能使用特定的出發地目的地組合目的地組合 目標是與配送量有關的總利潤最大不是成本最小目標是與配送量有關的總利潤最大不是成本最小 各種運輸問題變形各種運輸問題變形 運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策求佳產品公司決定使用三個

11、有生產余力的工廠進行四種新求佳產品公司決定使用三個有生產余力的工廠進行四種新產品的生產制造。每單位產品需要等量的工作，所以工廠產品的生產制造。每單位產品需要等量的工作，所以工廠的有效生產能力以每天生產的任意種產品的數量來衡量。的有效生產能力以每天生產的任意種產品的數量來衡量。 求佳公司指定工廠生產產品求佳公司指定工廠生產產品運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策求佳公司指定工廠生產產品求佳公司指定工廠生產產品運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策耐芙迪公司選擇顧客耐芙迪公司選擇顧客耐芙迪公司在三個工廠中專門生產一種產品。這

12、種產品有著優良的品質，所以現在公司接到了許多的訂單，產品供不應求。公司也正在努力擴大生產，甚至計劃要建立一個新的工廠，但是這個新的工廠要到明年才能投人運營。 在未來的四個月中，有四個處于國內不同區域的潛在顧客（批發商）很有可能大量訂購。顧客1是公司最好的顧客，所以它的全部訂購量都應該滿足；顧客2和3也是公司很重要的顧客，所以營銷經理認為作為最低限度至少要滿足他們訂單的1/3；對于顧客4，她認為并不需要進行特殊考慮，所以不想向這位顧客供應貨物。這樣就有足夠的貨物滿足最少數量。運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策耐芙迪公司選擇顧客耐芙迪公司選擇顧客運輸問題變形

13、運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策德羅水管站分配自然資源德羅水管站分配自然資源米德羅水管站是一個主管著廣闊地域的水資源分配的機構。由于這個地域十分干燥，所以這個機構需要從外地引水。這些引人的水來自于科倫坡、塞克隆以及卡路里河這三條河流。引人這些水之后，這個機構把水轉賣給這個地區的用戶。它的主要客戶是布都、勞斯戴維斯、圣哥以及豪利格拉斯等城市的供水部門。 運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策德羅水管站分配自然資源德羅水管站分配自然資源運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策德羅水管站分配自然資源德

14、羅水管站分配自然資源Excel運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策北方飛機制造公司生產進度安排北方飛機制造公司生產進度安排北方飛機制造公司為全世界的航空公司生產各種商務飛機。制造過程的最后的一步是生產噴氣發動機并把它們安裝到已經完成的飛機框架之中去（非常快的一個操作）按照公司的一些訂單合同，不久公司要交付使用相當多數量的飛機。所以有必要現在為未來四個月這些飛機噴氣發動機的生產制定計劃。運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策北方飛機制造公司生產進度安排北方飛機制造公司生產進度安排運輸問題變形運輸問題變形Excel第四講 運

15、輸、指派問題與網絡最優化數據，模型與決策排米德爾城學區劃分學生入學區域排米德爾城學區劃分學生入學區域米德爾城學區開辦了第三所中學，需要為每一所學校重新劃定這個城市內的服務區域。 在初步的計劃中，這個城市被分成了擁有大致相同數量人口的九個區域（在進一步細化的計劃之中，就把城市分成了超過100個更小的區域）表5-12 給出了每一所學校與每一個區域之間的近似距離。最右一列給出了明年每一個區域的高中學生數量（這些數字在未來幾年之內估計會有緩慢的增長）。最下面的兩行表示了每一所學校所能夠安排的最少和最多的學生數量。 運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策排米德爾城學區

16、劃分學生入學區域排米德爾城學區劃分學生入學區域運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策源豐公司源豐公司滿足能源需求滿足能源需求源豐公司需要為新的建筑物建立起能源系統。建筑物的能源需求主要來自于下面三個方面：1）電，2）熱水，3）建筑物內取暖。每天這三類用途的能源需求（以相同的單位衡量）分別是20個單位、10個單位和30個單位。 滿足這些需求的三個可能的能源來源是：電、天然氣和安裝在屋頂上的太陽能加熱裝置。房屋屋頂的大小決定了太陽能加熱裝置每天所能夠提供的能源量30單位。但是對于電和天然氣來說沒有這種限制。運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優

17、化數據，模型與決策源豐公司源豐公司滿足能源需求滿足能源需求運輸問題變形運輸問題變形第四講 運輸、指派問題與網絡最優化數據，模型與決策特塞格公司的選址問題特塞格公司的選址問題特塞格公司特塞格公司第四講 運輸、指派問題與網絡最優化數據，模型與決策特塞格公司的選址問題特塞格公司的選址問題特塞格公司特塞格公司第四講 運輸、指派問題與網絡最優化數據，模型與決策特塞格公司的選址問題特塞格公司的選址問題特塞格公司特塞格公司第四講 運輸、指派問題與網絡最優化數據，模型與決策特塞格煉油廠每一個備選廠址所帶來的年變動成本特塞格煉油廠每一個備選廠址所帶來的年變動成本地點地點運輸原油的總成運輸原油的總成本（百萬美元）

18、本（百萬美元）運輸石油制品運輸石油制品的總成本的總成本（十億美元）（十億美元）新煉油廠新煉油廠的運營成本的運營成本(百萬美元百萬美元)總變動成本總變動成本(十億美元十億美元)洛杉機洛杉機8201.266202.7加爾維斯敦加爾維斯敦8601.245702.67圣路易斯圣路易斯10401.085302.65特塞格公司的選址問題特塞格公司的選址問題特塞格公司特塞格公司第四講 運輸、指派問題與網絡最優化數據，模型與決策一種特殊的線性規劃問題，我們也經常遇到指派人員做某項工作的情況。指派問題的許多應用都用來幫助管理人員解決如何為一項將要開展進行的工作指派人員的問題。其他的一些應用如為一項任務指派機器、

19、設備或者是工廠 。指派問題指派問題第四講 運輸、指派問題與網絡最優化數據，模型與決策指派問題的形式表述指派問題的形式表述:給定了一系列所要完成的任務（tasks）以及一系列完成任務的被指派者（assignees），所需要解決的問題就是要確定出哪一個人被指派進行哪一項任務。指派問題模型指派問題模型 第四講 運輸、指派問題與網絡最優化數據，模型與決策指派問題的假設指派問題的假設:被指派者的數量和任務的數量是相同的 每一個被指派者只完成一項任務 每一項任務只能由一個被指派者來完成 每個被指派者和每項任務的組合有一個相關成本 目標是要確定怎樣進行指派才能使得總成本最小 指派問題模型指派問題模型 第四講

20、 運輸、指派問題與網絡最優化數據，模型與決策塞爾默公司的營銷經理將要主持召開一年一度的由營銷區域塞爾默公司的營銷經理將要主持召開一年一度的由營銷區域經理以及銷售人員參加的銷售協商會議。為了更好地安排這經理以及銷售人員參加的銷售協商會議。為了更好地安排這次會議，他雇用了四個臨時工（安、伊安、瓊、肖恩）每一次會議，他雇用了四個臨時工（安、伊安、瓊、肖恩）每一個人負責完成下面的一項任務：個人負責完成下面的一項任務： 1書面陳述的文字處理。書面陳述的文字處理。 2制作口頭和書面陳述的電腦圖。制作口頭和書面陳述的電腦圖。 3會議材料的準備，包括書面材料的抄寫和組織。會議材料的準備，包括書面材料的抄寫和組

21、織。 4處理與會者的提前和當場注冊報名。處理與會者的提前和當場注冊報名。 塞爾默公司塞爾默公司第四講 運輸、指派問題與網絡最優化數據，模型與決策塞爾默公司塞爾默公司第四講 運輸、指派問題與網絡最優化數據，模型與決策塞爾默公司塞爾默公司第四講 運輸、指派問題與網絡最優化數據，模型與決策指派問題的變形指派問題的變形 指派問題的變形指派問題的變形:有一些被指派者并不能進行某一些的任務 任務比被指派者多 被指派者比要完成的任務多每個被指派者可以同時被指派給多于一個的任務 每一項任務都可以由多個被指派者共同完成 第四講 運輸、指派問題與網絡最優化數據，模型與決策指派問題的應用指派問題的應用 在各個地點分

22、派設備在各個地點分派設備 指派工廠生產產品指派工廠生產產品 設計學生入學區域設計學生入學區域 指派問題應用指派問題應用第四講 運輸、指派問題與網絡最優化數據，模型與決策各個地點分派設備各個地點分派設備指派問題應用指派問題應用第四講 運輸、指派問題與網絡最優化數據，模型與決策求佳產品公司指派工廠生產產品求佳產品公司指派工廠生產產品指派問題應用指派問題應用第四講 運輸、指派問題與網絡最優化數據，模型與決策米德爾城學區設計學生入學區域米德爾城學區設計學生入學區域指派問題應用指派問題應用第四講 運輸、指派問題與網絡最優化數據，模型與決策飛利浦石油（飛利浦石油（Phillips Petroleum）應用

23、最短路問題模型對各種高速公路運輸車、卡車和貨車運輸路線的優化來降低成本提高競爭力飛利浦石油的運輸工具替換計劃飛利浦石油的運輸工具替換計劃Waddell (1983) Jul-Aug Interfaces article, “A Model for Equipment Replacement Decisions and Policies” 飛利浦石油飛利浦石油第四講 運輸、指派問題與網絡最優化數據，模型與決策有1500輛卡車和3800輛貨車用最短路模型建立替換戰略(20年時間跨度)每次為每一類運輸工具求解模型考慮成本有維護和運營成本、租賃成本、購買成本、 政府授權費用路稅和其他稅收（投資稅、折舊

24、）開始做lease-or-buy決策，然后做替換戰略，目前擴展到了其他的設備（非運輸工具）飛利浦石油的運輸工具替換計劃飛利浦石油的運輸工具替換計劃飛利浦石油飛利浦石油第四講 運輸、指派問題與網絡最優化數據，模型與決策網絡最優化模型的應用網絡最優化模型的應用網絡在交通、電子和通訊網絡遍及我們日常生活的各個方面，網絡規劃也廣泛用于解決不同領域中的各種問題，如生產、分配、項目計劃、廠址選擇、資源管理和財務策劃等等。網絡規劃為描述系統各組成部分之間的關系提供了非常有效直觀和概念上的幫助，廣泛應用于科學、社會和經濟活動的每個領域中。第四講 運輸、指派問題與網絡最優化數據，模型與決策網絡表述網絡表述 F1

25、DCF2W2W180 unitsproduced70 units produced60 unitsneeded90 units needed第四講 運輸、指派問題與網絡最優化數據，模型與決策網絡最優化問題類型網絡最優化問題類型最小費用流問題最小費用流問題 最大流問題最大流問題最短路問題最短路問題 最小支撐樹問題最小支撐樹問題 第四講 運輸、指派問題與網絡最優化數據，模型與決策基本術語基本術語節點、供應點節點、供應點 、需求點需求點 、轉運點轉運點流量、流量守恒、弧、容量流量、流量守恒、弧、容量 第四講 運輸、指派問題與網絡最優化數據，模型與決策最小費用流問題最小費用流問題最小費用流問題的構成：

26、最小費用流問題的構成：節點節點(nodes)（供應點供應點 、需求點需求點 、轉運點）轉運點）弧（弧（arcs） 目標目標: 通過網絡滿足需求提供供應，通過網絡滿足需求提供供應， 最小化流的總成本最小化流的總成本最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策最小費用流問題的假設最小費用流問題的假設1至少有一個節點是供應點。2至少有一個節點是需求點。3所有剩下的節點都是轉運點。4通過弧的流只允許沿著箭頭的方向流動，通過弧的最大流量取決于該弧的容量。（如果流是雙向的話，則需要用一對箭頭指向相反的弧來表示。）最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決

27、策最小費用流問題的假設最小費用流問題的假設5網絡中有足夠的弧提供足夠的容量，使得所有在供應點中產生的流都能夠到這需求點。6在流的單位成本已知的前提下，通過每一條弧的流的成本和流量成正比。7最小費用流問題的目標是在滿足給定需求的條件下，使得通過網絡供應的總成本最小。（換一種說法是通過這樣做使得總利潤最大化。） 最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策解的特征解的特征具有可行解可行解的特征：在以上的假設下，當且僅當供應點所提供的流量總和等于需求點所需要的流量總和時，最小費用流問題有可行解 具有整數解整數解的特征：只要其所有的供應、需求和弧的容量都是整數值，那么任何最小

28、費用流問題的可行解就一定有所有流量都是整數的最優解 最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策無限配送公司無限配送公司無限配送公司的最小成本流問題的無限配送公司的最小成本流問題的電子表格模型電子表格模型 最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策網絡單純形法網絡單純形法實際運用中解決比較大型問題時需要用不同的方法實際運用中解決比較大型問題時需要用不同的方法網絡單純形法可以用來解決那些對于單純形法來說網絡單純形法可以用來解決那些對于單純形法來說 太大而無法解決的大型問題太大而無法解決的大型問題 Excel Solver軟件中沒有網絡單純形法

29、，但是其他的軟件中沒有網絡單純形法，但是其他的 線性規劃的商業軟件包通常都有這種方法線性規劃的商業軟件包通常都有這種方法 最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策一些實際應用一些實際應用 國際紙業公司（國際紙業公司（International Paper Company）配送網絡（Interfaces 1988年3/4）世界上最大的紙漿、紙和紙類產品的制造商以及木材和夾板的主要生產者。擁有兩千萬英畝的林區或其權益。分布在不同地方的林區是它配送網絡的供應點,供應流必須經過一系列很長的轉運點 ： 林區林區木材堆積場木材堆積場鋸木廠鋸木廠造紙廠造紙廠 紙制品加工廠紙制品

30、加工廠倉庫倉庫客戶客戶 最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策一些實際應用一些實際應用 馬爾薩斯公司（馬爾薩斯公司（Marshalls, Inc.） 配送網絡（Interfaces 1987年7/8）一家折扣連鎖零售店，現在和以前是如何使用微型計算機去處理一個最小費用流問題。應用中公司力圖使得從供應商到加工中心，再從加工中心到零售店的商流最優。其中的一些網絡有超過20,000條弧。 最小費用流最小費用流第四講 運輸、指派問題與網絡最優化數據，模型與決策最大流問題最大流問題 最大流問題也與網絡中的流有關，但目標不是使得最大流問題也與網絡中的流有關，但目標不是使得流

31、的成本最小化，而是尋找一個流的方案，使得通流的成本最小化，而是尋找一個流的方案，使得通過網絡的流量最大。過網絡的流量最大。 最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策最大流問題的假設最大流問題的假設 1網絡中所有流起源于一個節點，這個節點叫做源，所有網絡中所有流起源于一個節點，這個節點叫做源，所有的流終止于另一個節點，這個節點叫做收點。（在的流終止于另一個節點，這個節點叫做收點。（在BMZ問題問題中源和收點分別代表工廠和配送中心）中源和收點分別代表工廠和配送中心） 2其余所有的節點叫做轉運點。（在其余所有的節點叫做轉運點。（在BMZ問題中，節點問題中，節點RO、BO

32、、LI、NY和和NO都是轉運點）都是轉運點） 3通過每一個弧的流只允許沿著弧的箭頭所指方向流動。通過每一個弧的流只允許沿著弧的箭頭所指方向流動。由源發出的所有的弧背向源，而所有終結于收點的弧都指向由源發出的所有的弧背向源，而所有終結于收點的弧都指向收點。收點。 4最大流問題的目標是使得從源到收點的總流量最大。這最大流問題的目標是使得從源到收點的總流量最大。這個流量的大小可以用兩種等價的方法來衡量，分別叫做從源個流量的大小可以用兩種等價的方法來衡量，分別叫做從源點出發的流量和進入收點的流量。點出發的流量和進入收點的流量。最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策最大流

33、問題最大流問題 最小費用流問題的這些節點和最大流問題中與其對應的節點最小費用流問題的這些節點和最大流問題中與其對應的節點有兩點區別：有兩點區別： 第一個區別是，供應點的供應量和需求點的需求量都是固第一個區別是，供應點的供應量和需求點的需求量都是固定的，而源和收點則不同。這是因為后者的目標是使得從源定的，而源和收點則不同。這是因為后者的目標是使得從源點出發的或進人收點的流量最大，它們的數量不是固定的。點出發的或進人收點的流量最大，它們的數量不是固定的。 第二個區別是，在最小費用流問題中，不管是供應點的數第二個區別是，在最小費用流問題中，不管是供應點的數量還是需求點的數量都可能多于一個。而在最大流

34、問題中只量還是需求點的數量都可能多于一個。而在最大流問題中只能有一個源和一個收點。但是，有多個源和收點的最大流問能有一個源和一個收點。但是，有多個源和收點的最大流問題的變形也能用題的變形也能用 Excel Solver軟件解決。軟件解決。 最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策BMZ案例研究案例研究BMZ公司是歐洲一家生產豪華汽車的制造商。雖然它生產的汽車在所有發達國家的銷量都不錯，但是對于這家公司來說，出口到美國顯得尤其重要。BMZ公司因為提供優質的服務而獲得很好的聲譽，保持這個聲譽一個很重要的秘訣是它有著充裕的汽車配件供應，從而能夠隨時供貨給公司眾多的經銷商

35、和授權維修店。這些供應件主要存放在公司的配送中心里，這樣一有需求就可以立即送貨。因為總廠生產的配件量遠遠要大于能夠運送到配送中心的量，所以，可以運送多少配件的限制條件就是該公司配送網絡的容量。最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策BMZ案例研究案例研究BMZ從德國斯圖加特工廠到洛杉磯配送中心的配送網絡從德國斯圖加特工廠到洛杉磯配送中心的配送網絡 最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策BMZ案例研究案例研究BMZ案例的網絡描述案例的網絡描述 STLIBORONONYLA708070604050305040最大流問題最大流問題第四講

36、運輸、指派問題與網絡最優化數據，模型與決策BMZ案例研究案例研究Excel求解求解最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策擴展后的擴展后的BMZ問題問題Excel求解求解最大流問題最大流問題第四講 運輸、指派問題與網絡最優化數據，模型與決策最短路問題最短路問題最短路問題的最普遍的應用在兩個點之間最短路問題的最普遍的應用在兩個點之間尋找最短路尋找最短路 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策里特城消防站里特城消防站 Fire StationHGFEDCBA3642175468643467523Farming Community里特城的

37、消防站和某一農場社區間的道路系統里特城的消防站和某一農場社區間的道路系統 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策里特城消防站里特城消防站里特城的消防站道路系統里特城的消防站道路系統 的網絡表述的網絡表述 THGFEDBCAO(Destination)(Origin)3612643478654234675最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策里特城消防站里特城消防站最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策最短路問題的假設最短路問題的假設 網絡中選擇一條路網絡中選擇一條路,始于某源點終于目標地始于某源點終

38、于目標地 連接兩個節點的連線叫做邊（允許任一個方向行連接兩個節點的連線叫做邊（允許任一個方向行 進），弧（只允許沿著一個方向行進）進），弧（只允許沿著一個方向行進） 和每條邊相關的一個非負數，叫做該邊的長度和每條邊相關的一個非負數，叫做該邊的長度 目標是為了尋找從源到目標地的最短路目標是為了尋找從源到目標地的最短路 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策最短路問題三種類型最短路問題三種類型 1行進的總距離最小（上一例）行進的總距離最小（上一例）2一序列活動的總成本最小一序列活動的總成本最小3一序列活動的總時間最小一序列活動的總時間最小最短路問題最短路問題第四講

39、運輸、指派問題與網絡最優化數據，模型與決策使總成本最小的例子使總成本最小的例子 莎拉剛剛高中畢業。在畢業典禮上，她的父母給了她莎拉剛剛高中畢業。在畢業典禮上，她的父母給了她21000美元的汽車基金幫助她購買并保養一輛使用了三美元的汽車基金幫助她購買并保養一輛使用了三年的二手車，以供她上大學。由于開車費用和維修費年的二手車，以供她上大學。由于開車費用和維修費用隨著汽車的老化而飛速上漲，所以莎拉的父母告訴用隨著汽車的老化而飛速上漲，所以莎拉的父母告訴她在接下來的三個夏天里，她也可以一次或幾次折價她在接下來的三個夏天里，她也可以一次或幾次折價將她的汽車置換為其他使用了三年的二手車。如果她將她的汽車置

40、換為其他使用了三年的二手車。如果她覺得這樣做可以使她的總凈成本最小的話，他們會同覺得這樣做可以使她的總凈成本最小的話，他們會同意她這樣做的。他們也告訴莎拉，在四年后，他們會意她這樣做的。他們也告訴莎拉，在四年后，他們會送給她一輛新車作為大學畢業的禮物。所以，莎拉到送給她一輛新車作為大學畢業的禮物。所以，莎拉到那時肯定要計劃把舊車折價賣出。那時肯定要計劃把舊車折價賣出。 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策使總成本最小的例子使總成本最小的例子 在接下來的三個夏天里，什么時候莎拉應該折價賣掉她的汽車僅果有必要的話）可以使得她在大學四年里買車、開車、保養汽車的總費用

41、最小？ 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策使總成本最小的例子使總成本最小的例子 當把莎拉什么時候應該折價購車看成是一個最短路問題時問題的描述。節點的標號代表從現在開始計算的年份，每一條弧代表了購車然后又折價賣出。Excel求解最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策使總時間最小的例子使總時間最小的例子 奎克公司獲悉它的一個競爭對手計劃將把一種很有銷售潛力的新產品投放市場。奎克公司也一直在研制一種類似的產品，并計劃在20個月后投放市場。但是，研究臨近結束，奎克公司的管理者希望迅速推出產品去參與競爭。 現在還有四個沒有時間重疊的階段

42、沒有完成，包括正以正常速度進行剩下的研究工作。然而，每個階段的實施水平可以從正常水平提高為優先水平或應急水平，使之能夠加速完成；而且最后三個階段中都可以考慮提高實施水平。 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策使總時間最小的例子使總時間最小的例子 最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策使總時間最小的例子使總時間最小的例子 當網絡中實際行進在多于一個節點結束時，在每個這樣的節點和虛擬目標地之間插入一條長度為0的弧，從而使得網絡中仍然只有一個目標地。最短路問題最短路問題第四講 運輸、指派問題與網絡最優化數據，模型與決策最小支撐樹問題最小支撐樹問題最小支撐樹問題的假設最小支