實用運籌學

－－運用Excel建模和求解（第3版）第3章運輸問題和指派問題TheTransportationandAssignmentProblems本章內容要點運輸問題的基本概念運輸問題的數學模型運輸問題的變形轉運問題指派問題的基本概念指派問題的變形本章主要內容框架圖3.1運輸問題的基本概念運輸問題源于在日常生活中人們把某些物品或人們自身從一些地方轉移到另一些地方，要求所采用的運輸路線或運輸方案是最經濟或成本最小的，這就成為一個運籌學問題。隨著經濟水平的不斷提升，現代物流業蓬勃發展，如何充分利用時間、信息、倉儲、配送和聯運體系創造更多的價值，向運籌學提出了更高的挑戰。這要求科學地組織貨源、運輸和配送，使運輸問題變得日益復雜，但其基本思想仍然是實現現有資源的最優化配置。3.1運輸問題的基本概念一般的運輸問題就是解決如何把某種產品從若干個產地調運到若干個銷地的問題，在每個產地的供應量和每個銷地的需求量以及各地之間的運輸單價已知的前提下，確定一個使得總運輸成本最小的方案。平衡運輸問題的條件如下：（1）明確出發地（產地）、目的地（銷地）、供應量（產量）、需求量（銷量）和單位運輸成本。（2）需求假設：每一個出發地（產地）都有一個固定的供應量，所有的供應量都必須配送到目的地（銷地）。與之類似，每一個目的地（銷地）都有一個固定的需求量，所有的需求量都必須由出發地（產地）滿足。即“總供應量＝總需求量”。（3）成本假設：從任何一個出發地（產地）到任何一個目的地（銷地）的貨物運輸成本與所運送的貨物數量呈線性關系，因此，貨物運輸成本就等于單位運輸成本乘以所運送的貨物數量（目標函數是線性的）。3.2運輸問題的數學模型產銷平衡運輸問題的數學模型設從產地Ai運往銷地Bj的物資數量為xij（i=1,2,?,m;j=1,2,?,n)

3.2.1產銷平衡的運輸問題例3-1

某公司有三個加工廠（A1、A2和A3）生產某種產品，每日的產量分別為7噸、4噸、9噸。該公司把這些產品分別運往四個銷售點（B1、B2、B3和B4），四個銷售點每日的銷量分別為3噸、6噸、5噸、6噸。從三個加工廠（產地）到四個銷售點（銷地）的單位產品運價如表3-2所示。問該公司應如何調運產品，才能在滿足四個銷售點的銷量的前提下，使總運費最??？銷售點B1銷售點B2銷售點B3銷售點B4加工廠A1311310加工廠A21928加工廠A3741053.2.1產銷平衡的運輸問題【解】首先，三個加工廠A1、A2、A3的總產量為7＋4＋9＝20（噸）；四個銷售點B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20（噸）。也就是說，總產量等于總銷量，故該運輸問題是一個產銷平衡的運輸問題。（1）決策變量

設xij為從加工廠Ai（i＝1,2,3）運往銷售點Bj（j=1,2,3,4）的運輸量。（2）目標函數

本問題的目標是使公司的總運費最小。3.2.1產銷平衡的運輸問題（3）約束條件①三個加工廠的產品全部都要運送出去（產量約束）②四個銷售點的產品全部都要得到滿足（銷量約束）③非負3.2.1產銷平衡的運輸問題運輸問題是一種特殊的線性規劃問題，一般采用“表上作業法”求解，但Excel的“規劃求解”功能還是采用“單純形法”來求解。例3-1的電子表格模型（1）設置條件格式的操作請參見本章附錄。（2）將單元格的字體和背景顏色設置為相同顏色以實現“渾然一體”的效果，可以起到隱藏單元格內容的作用。當單元格被選中時，編輯欄中仍然會顯示單元格的真實數據。（3）本章所有例題的最優解（運輸方案或指派方案）有一個共同特點，即“0”值較多，所以都使用了Excel的“條件格式”功能。3.2.1產銷平衡的運輸問題例3-1的最優調運方案網絡圖A2A3A1B2B3B1B47365649231635產量

加工廠

運輸量

銷售點

銷量運輸問題的整數解性質需要注意的是：運輸問題有這樣一個性質（整數解性質），即只要它的產量（供應量）和銷量（需求量）都是整數，任何存在可行解的運輸問題就必然存在所有決策變量都是整數的最優解。因此，沒有必要加上所有決策變量都是整數的約束條件。由于運輸量經常以卡車、集裝箱等為單位，如果卡車不能裝滿，就很不經濟了。整數解性質避免了運輸量（運輸方案）為小數的麻煩。3.2.2產銷不平衡的運輸問題實際問題中，產銷往往是不平衡的。（1）銷大于產（供不應求）運輸問題的數學模型（以滿足小的產量為準）3.2.2產銷不平衡的運輸問題（2）產大于銷（供過于求）運輸問題的數學模型（以滿足小的銷量為準）3.2.2產銷不平衡的運輸問題例3-2自來水輸送問題。某市有甲、乙、丙、丁四個居民區，自來水由A、B、C三個水庫供應。四個居民區每天的基本生活用水量分別為3萬噸、7萬噸、1萬噸、1萬噸，但由于水源緊張，三個水庫每天最多只能分別供應5萬噸、6萬噸、5萬噸自來水。由于地理位置的差別，自來水公司從各水庫向各居民區供水所需支付的引水管理費不同（見表3?4，其中水庫C與丁區之間沒有輸水管道），其他管理費用都是4500元／萬噸。根據公司規定，各居民區用戶按照統一標準9000元／萬噸收費。此外，四個居民區都向公司申請了額外用水量，分別為每天5萬噸、7萬噸、2萬噸、4萬噸。問：（1）該公司應如何分配供水量，才能獲利最大？（2）為了增加供水量，自來水公司正在考慮進行水庫改造，使三個水庫每天的最大供水量都增加一倍，那時供水方案應如何改變？公司利潤可增加到多少？3.2.2產銷不平衡的運輸問題【解】可以把“自來水輸送問題”看作“運輸問題”，也就是用“運輸問題”的方法求解“自來水輸送問題”。設xij為水庫i向居民區j的日供水量（11個變量）

3.2.2產銷不平衡的運輸問題例3-2問題（1）的線性規劃模型目標：從獲利最大轉化為引水管理費最小由于A、B、C三個水庫的總供水量5＋6＋5＝16，超過四個居民區的基本生活用水量之和3＋7＋1＋1＝12（供過于求），但又少于四個居民區的基本生活用水量與額外用水量之和（3＋7＋1＋1）＋（5＋7＋2＋4）＝30（供不應求），所以本問題既是“供過于求”又是“供不應求”的不平衡運輸問題。

3.2.2產銷不平衡的運輸問題例3-2問題（1）的電子表格模型電子表格模型中有12個變量（供水量，C9:F11區域），通過增加約束條件“$F$11＝0”，實現“水庫C與居民區丁之間沒有輸水管道”。3.2.2產銷不平衡的運輸問題例3-2問題（1）的最優供水方案網絡圖BCA乙丙甲丁5814356551541水庫供水量居民區最大供水量最大用水量3.2.2產銷不平衡的運輸問題例3-2問題（2）方法1的線性規劃模型目標：將獲利最大轉化為引水管理費最小由于A、B、C三個水庫每天的最大供水量都提高一倍，則公司總供水能力增加到16×2＝32萬噸，大于總需求量30萬噸，為“供過于求”的不平衡運輸問題。

3.2.2產銷不平衡的運輸問題例3-2問題（2）方法1

的電子表格模型電子表格模型中有12個變量（供水量，C9:F11區域），通過增加約束條件“$F$11＝0”，實現“水庫C與居民區丁之間沒有輸水管道”。3.2.2產銷不平衡的運輸問題例3-2問題（2）的最優供水方案網絡圖BCA乙丙甲丁10814351210105353水庫供水量居民區最大供水量最大用水量43.2.2產銷不平衡的運輸問題例3-2問題（2）方法2：目標為獲利最大電子表格模型中有12個變量（供水量，C9:F11區域），通過增加約束條件“$F$11＝0”，實現“水庫C與居民區丁之間沒有輸水管道”。

3.3運輸問題的變形現實生活中符合產銷平衡運輸問題的每個條件的情況很少。一個特征近似但其他一個或者幾個特征不符合產銷平衡運輸問題條件的運輸問題卻經常出現。下面是要討論的一些特征：特征1：總供應量大于總需求量。每個供應量（產量）代表了從其出發地（產地）運送出去的最大數量（而不是一個固定的數值，≤）特征2：總供應量小于總需求量。每個需求量（銷量）代表了在其目的地（銷地）接收到的最大數量（而不是一個固定的數值，≤）特征3：一個目的地（銷地）同時存在最小需求量和最大需求量，于是所有在這兩個數值之間的數量都是可以接收的（需求量可在一定范圍內變化，≥、≤）特征4：在運輸中不能利用特定的出發地（產地）--目的地（銷地）組合（xij=0）特征5：目標是使與運輸量有關的總利潤最大而不是使總成本最?。∕in－>

Max）3.3運輸問題的變形例3-3

某公司決定使用三個有生產余力的工廠進行四種產品的生產。生產每單位產品需要等量的工作，所以工廠的有效生產能力以每天生產的任意種產品的數量來衡量（見表3-7的最右列）。而每種產品每天有一定的需求量（見表3-7的最后一行）。除了工廠2不能生產產品3以外，每個工廠都可以生產這些產品。然而，每種產品在不同工廠中的單位成本（元）是有差異的（如表3-7所示）。現在需要決定的是在哪個工廠生產哪種產品，可使總成本最小。單位成本生產能力產品1產品2產品3產品4工廠24029一2375工廠33730272145需求量203030403.3運輸問題的變形【解】把“指定工廠生產產品問題”看作“運輸問題”。本問題中，工廠2不能生產產品3，這樣可以增加約束條件x23＝0

；并且總供應量（75+75+45=195）>總需求量（20+30+30+40=120），是供大于求的運輸問題。其數學模型：設xij為工廠i生產產品j

的數量3.3運輸問題的變形例3-3的電子表格模型產品4分在2個工廠（工廠2和工廠3）生產3.3運輸問題的變形例3-4

需求量存在最小需求量和最大需求量（需求量可在一定范圍內變化）的問題。某公司在三個工廠中專門生產一種產品。在未來的四個月中，四個處于國內不同區域的潛在顧客（批發商）很可能有大量訂購該產品。顧客1是公司最重要的顧客，所以他的訂單要全部滿足；顧客2和顧客3也是公司很重要的顧客，所以營銷經理認為至少要滿足他們訂單的1/3；對于顧客4，營銷經理認為并不需要特殊考慮。由于運輸成本的差異，單位利潤也不同，利潤很大程度上取決于哪個工廠供應哪個顧客（見表3-8）。問應向每個顧客供應多少產品，才能使公司的總利潤最大？單位利潤（元）產量（件）顧客1顧客2顧客3顧客4工廠1554246538000工廠2371832485000工廠3295951357000最少供應量（件）7000300020000要求訂購量（件）70009000600080003.3運輸問題的變形【解】該問題要求滿足不同顧客的需求（訂購量），解決辦法：實際供應量

最少供應量實際供應量

要求訂購量

目標是總利潤最大，而不是總成本最小。其數學模型：設xij為工廠i供應顧客j的產品數量3.3運輸問題的變形例3-4的電子表格模型3.4轉運問題在實際工作中，有一類問題是需要先將物品由產地運到某個中間轉運地，這個轉運地可以是產地、銷地或中間轉運倉庫，然后再運到銷售目的地，這類問題稱為轉運問題，可以通過建模轉化為運輸問題模型。例3-5

例3-1是一個普通的產銷平衡運輸問題，如果假定：（1）每個加工廠（產地）的產品不一定直接運到銷售點（銷地），可以將其中幾個加工廠的產品集中一起運；（2）運往各銷售點的產品可以先運給其中幾個銷售點，再轉運給其他銷售點；（3）除產地、銷地之外，中間還可以有幾個轉運站，在產地之間、銷地之間或產地與銷地之間轉運。3.4轉運問題例3-5轉運問題（續）已知各產地、銷地、中間轉運站及相互之間的單位產品運價如表3-9所示，問在考慮產銷地之間非直接運輸的情況下，如何將三個加工廠生產的產品運往銷售點，才能使總運費最小？單位運價加工廠（產地）中間轉運站銷售點（銷地）A1A2A3T1T2T3T4B1B2B3B4加工廠（產地）A1

132143311310A21

一35一21928A33一

1一2374105中間轉運站T1231

1322846T215一1

114527T34一231

21824T4323212

1一26銷售點（銷地）B13172411

142B21194858一1

21B33210422242

3B410856746213

3.4轉運問題【解】現在把該轉運問題轉化成一般運輸問題，要做如下處理：（1）由于問題中的所有加工廠、中間轉運站、銷售點都可以看作產地，也可以看作銷地，因此把整個問題當作有11個產地和11個銷地的擴大的運輸問題。（2）對擴大的運輸問題建立單位運價表。方法是將不可能的運輸方案的運價用任意大的正數（相對極大值）M代替，其余運價cij不變。（3）所有中間轉運站的產量等于銷量，即流入量等于流出量。（4）擴大的運輸問題中原來的產地（加工廠）與銷地（銷售點），因為也有中間轉運站的作用，所以同樣在原來的產量與銷量上加t＝20噸。即三個加工廠的每日產量分別改為27噸、24噸和29噸，銷量均為20噸；四個銷售點的每日銷量分別改為23噸、26噸、25噸和26噸，產量均為20噸。同時引進xii為輔助變量（虛擬運量）。3.4轉運問題【解】表3-10為擴大的運輸問題產銷平衡表與單位運價表。單位運價A1A2A3T1T2T3T4B1B2B3B4產量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23102182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020銷量20202020202020232625262403.4轉運問題例3-5的電子表格模型例3-5（轉運問題）有多組最優解。（1）最優調運方案1：無需中間轉運站，如表3-11和圖3-12所示；（2）最優調運方案2：需中間轉運站T1，如表3-12和圖3-13所示；（3）最優調運方案3：需中間轉運站T3，如表3-13和圖3-14所示。3.5指派問題的基本概念在生活中經常會遇到這樣的問題：某單位需完成n項任務，恰好有n個人可以承擔這些任務。由于每個人的專長不同，各人完成的任務不同，所需的時間（或效率）也不同。于是產生應指派哪個人去完成哪項任務，使完成n項任務所需的總時間最短（或總效率最高）。這類問題稱為指派問題或分派問題。平衡指派問題的假設如下：（1）人的數量和任務的數量相等；（2）每個人只能完成一項任務；（3）每項任務只能由一個人完成；（4）每個人和每項任務的組合都會有一個相關的成本（單位成本）；（5）目標是要確定如何指派才能使總成本最小。3.5指派問題的基本概念設xij為是否指派第i個人去完成第j項任務，目標函數系數cij為第i個人完成第j項任務所需要的單位成本。平衡指派問題的線性規劃模型如下：3.5指派問題的基本概念需要說明的是：指派問題實際上是一種特殊的運輸問題。其中出發地是“人”，目的地是“任務”。只不過，每個出發地的供應量都為1（因為每個人都要完成一項任務），每個目的地的需求量也都為1（因為每項任務都要完成）。由于運輸問題有整數解性質，因此，指派問題沒有必要加上所有決策變量都是0-1變量的約束條件。指派問題是一種特殊的線性規劃問題，有一種簡便的求解方法：匈牙利方法（HungarianMethod），但Excel的“規劃求解”功能還是采用單純形法來求解。3.5指派問題的基本概念例3-6

某公司的營銷經理將要主持召開一年一度的由營銷區域經理以及營銷人員參加的銷售協商會議。為了更好地召開這次會議，他安排小張、小王、小李、小劉四個人，每個人負責完成一項任務：A、B、C和D。由于每個人完成每項任務的時間和工資不同。問公司應指派哪個人去完成哪項任務，才能使總成本最小？完成每項任務的時間（小時）每小時工資（元）任務A任務B任務C任務D小張3541274014小王4745325112小李3956364313小劉32512546153.5指派問題的基本概念【解】

該問題是一個典型的平衡指派問題。單位成本為每個人完成每項任務的總工資；目標是要確定哪個人去完成哪項任務，才能使總成本最小；供應量為1表示每個人都只能完成一項任務；需求量為1表示每項任務也只能由一個人完成；總人數（4人）和總任務數（4項）相等。3.5指派問題的基本概念例3-6的線性規劃模型設xij為是否指派人員i去完成任務j

3.5指派問題的基本概念例3-6的電子表格模型3.5指派問題的基本概念例3-6的最優指派方案網絡圖小李小劉小張BCAD人指派任務小王3.6指派問題的變形經常會遇到指派問題的變形，之所以稱它們為變形，是因為它們都不滿足平衡指派問題所有假設中的一個或者多個。一般考慮下面的一些特征：特征1：某人不能完成某項任務（相應的xij＝0）；特征2：每個人只能完成一項任務，但是任務數比人數多(人少事多)；特征3：每項任務只由一個人完成，但是人數比任務數多（人多事少）；特征4：某人可以同時被指派多項任務（一人可做多事）；特征5：某事需要由多人共同完成（一事需多人做）；特征6：目標是與指派有關的總利潤最大而不是總成本最?。惶卣?：實際能夠完成的任務數小于總人數，也小于總任務數。3.6指派問題的變形例3-7指派工廠生產產品問題。題目見例3-3，即某公司需要安排三個工廠來生產四種產品，相關的數據見表3-7。在例3-3中，允許產品生產分解，但這將產生與產品生產分解相關的隱性成本（包括額外的設置、配送和管理成本等）。因此，管理人員決定在禁止產品生產分解發生的情況下對問題進行分析。新問題描述為：已知如表3-7所示的數據，問如何把每個工廠指派給至少一種產品（每種產品只能在一個工廠生產），才能使總成本最小？3.6指派問題的變形【解】該問題可視為指派工廠生產產品問題，工廠可以看作指派問題中的人，產品則可以看作需要完成的任務。

由于有三個工廠和四種產品，所以就需要有一個工廠生產兩種新產品，只有工廠1和工廠2有生產兩種產品的能力，這是因為工廠1和工廠2的生產能力都是75，而工廠3的生產能力是45。這里涉及如何把運輸問題轉化為指派問題，關鍵之處在于數據轉化。3.6指派問題的變形如何把運輸問題轉化為指派問題，關鍵之處在于數據轉化：（1）單位指派成本:原來的單位成本轉化成整批成本（整批成本＝單位成本×需求量），即單位指派成本為每個工廠生產每種產品的成本。（2）供應量和需求量：三個工廠生產四種產品，但一種產品只能在一個工廠生產。根據生產能力，工廠3只能生產一種產品（供應量為1），而工廠1和工廠2可以生產兩種產品（供應量為2），而四種產品的需求量都為1。還有“總供應量”（2+2+1=5）>“總需求量”（1+1+1+1=4）,即“人多事少”的指派問題。3.6指派問題的變形例3-7的線性規劃模型

設xij為指派工廠i（i=1,2,3）生產產品j（j=1,2,3,4)3.6指派問題的變形例3-7的電子表格模型、最優指派生產方案網絡圖2312314工廠

指派生產

產品

本章上機實驗1．實驗目的

掌握利用Excel求解運輸問題和指派問題的操作方法。2．內容和要求

利用Excel求解運輸問題、轉運問題、指派問題等，題目自選。3．操作步驟（1）在Excel中建立運輸問題（或指派問題）的電子表格模型；（2）利用Excel中的“規劃求解”功能求解運輸問題或指派問題；（3）結果分析；（4）在Word文檔（或PowerPoint演示文稿）中撰寫實驗報告，包括線性規劃模型、電子表格模型和結果分析等。實用運籌學

－－運用Excel建模和求解（第3版）第4章網絡最優化問題NetworkOptimizationProblems本章內容要點網絡最優化問題的基本概念最小費用流問題最大流問題最小費用最大流問題最短路問題最小支撐樹問題貨郎擔問題和中國郵路問題本章主要內容框架圖4.1網絡最優化問題的基本概念網絡在各種實際背景問題中以各種各樣的形式存在。交通、電子和通信網絡遍及人們日常生活的各個方面，網絡規劃也廣泛應用于不同領域來解決各種問題，如生產、分派（指派）、項目計劃、廠址選擇、資源管理和財務策劃等。網絡規劃為描述系統各組成部分之間的關系提供了非常有效的直觀和概念上的幫助，廣泛應用于科學、社會和經濟活動的各個領域。近些年來，運籌學（管理科學）中一個振奮人心的、不同尋常的發展體現在解決網絡最優化問題的方法論及其應用方面。4.1網絡最優化問題的基本概念許多研究對象往往可以用一個圖來表示，研究的目的歸結為圖的極值問題。運籌學中研究的圖具有下列特征：

(1)用點（圓圈）表示研究對象，用連線（不帶箭頭的邊或帶箭頭的?。┍硎緦ο笾g的某種關系。

(2)強調點與點之間的關聯關系，不講究圖的比例大小與形狀。

(3)每條邊（或?。┒假x有一個權，其圖稱為賦權圖。實際應用中，權可以表示兩點之間的距離、費用、利潤、時間、容量等不同的含義；

(4)建立一個網絡模型，求最大值或最小值。4.1網絡最優化問題的基本概念V1V3V5V2V4V68736548521對于該網絡圖，可以提出許多極值問題。4.1網絡最優化問題的基本概念（1）將某個點Vi的物資或信息送到另一個點Vj，使得運送總費用最小。這屬于最小費用流問題。（2）將某個點Vi的物資或信息送到另一個點Vj，使得總流量最大。這屬于最大流問題。（3）從某個點Vi出發，到達另一個點Vj，如何安排路線，使得總距離最短或總費用最小。這屬于最短路問題。4.1網絡最優化問題的基本概念（4）點Vi表示自來水廠及用戶，Vi與Vj間的邊表示兩點間可以鋪設管道，權為Vi與Vj間鋪設管道的距離或費用，如何鋪設管道，使得將自來水送到其他5個用戶家中的總費用最小。這屬于最小支撐樹問題。（5）售貨員從某個點Vi出發，經過其他所有點，最后回到原點Vi，如何安排路線，使他行走的總路程最短。這屬于貨郎擔問題（旅行售貨員問題）。（6）郵遞員從郵局Vi出發，經過每一條邊（街道），將郵件送到客戶手中，最后回到郵局Vi，如何安排路線，使他行走的總路程最短。這屬于中國郵路問題。4.1網絡最優化問題的基本概念網絡最優化問題的類型主要包括：（1）最小費用流問題；（2）最大流問題；（3）最短路問題；（4）最小支撐樹問題；（5）貨郎擔問題；（6）中國郵路問題。4.2最小費用流問題最小費用流問題在網絡最優化問題中扮演著重要的角色，原因是它的適用性很廣，并且求解方法簡單。通常最小費用流問題用于最優化貨物從供應點到需求點的網絡。目標是在通過網絡配送貨物時，以最小的成本滿足需求。一種典型的應用就是使配送網絡的運營最優。4.2最小費用流問題例4-1

某公司有兩個工廠生產產品，這些產品需要運送到兩個倉庫中。其配送網絡圖如圖4-2所示。目標是確定一個運輸方案（即在每條線路上運送多少單位產品），使得通過配送網絡的總運輸成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（無限制，700）（無限制，900）4.2最小費用流問題最小費用流問題的三個基本概念如下：（1）最小費用流問題的構成（網絡表示）①節點：包括供應點、需求點和轉運點。②?。嚎尚械倪\輸線路（節點i->節點j），經常有最大運輸能力（容量）的限制。4.2最小費用流問題（2）最小費用流問題的假設

①至少有一個供應點。②至少有一個需求點。③可以有轉運點。④通過弧的流，只允許沿著箭頭方向流動，通過弧的最大流量取決于該弧的容量。⑤網絡中有足夠的弧提供足夠的容量，使得所有在供應點中產生的流都能夠到達需求點（有可行解）。⑥在流的單位成本已知的前提下，通過每條弧的流的成本與流量成正比（目標函數是線性的）。

⑦最小費用流問題的目標是在滿足給定需求的條件下，使得通過配送網絡的總成本最小（或總利潤最大）。4.2最小費用流問題（3）最小費用流問題的解的特征①具有可行解的特征：在以上假設下，當且僅當供應點所提供的供應量總和等于需求點所需要的需求量總和時（即平衡條件），最小費用流問題有可行解。②具有整數解的特征：只要所有的供應量、需求量和弧的容量都是整數，任何最小費用流問題的可行解就一定有所有流量都是整數的最優解（與運輸問題和指派問題有整數解一樣）。因此，沒有必要加上所有決策變量都是整數的約束條件。4.2最小費用流問題最小費用流問題的數學模型為：（1）決策變量：設fi

j為?。ü濣ci->節點j）的流量。（2）目標是使通過配送網絡的總成本最小。（3）約束條件

①所有供應點的凈流量（總流出－總流入）為正； ②所有轉運點的凈流量為零； ③所有需求點的凈流量為負； ④所有弧的流量fi

j受到弧的容量限制； ⑤所有弧的流量fi

j非負。4.2最小費用流問題例4-1最小費用流問題的數學模型為：（1）決策變量：設fi

j為弧（節點i->節點j）的流量。（2）目標函數本問題的目標是使通過配送網絡的總運輸成本最小4.2最小費用流問題①供應點F1

供應點F2

②轉運點DC ③需求點W1

需求點W2

④弧的容量限制⑤非負（3）約束條件(節點凈流量、弧的容量限制、非負）4.2最小費用流問題

例4-1的電子表格模型：列出了配送網絡中的弧和各弧所對應的容量、單位成本。決策變量為通過各弧的流量。目標是計算流量的總（運輸）成本。每個節點的凈流量為約束條件。供應點的凈流量為正，需求點的凈流量為負，而轉運點的凈流量為0。 這里使用了一個竅門：用兩個SUMIF函數的差來計算每個節點的凈流量，這樣快捷方便且不容易犯錯。4.2最小費用流問題大規模的最小費用流問題的求解一般采用網絡單純法?，F在，許多公司都使用網絡單純法來求解最小費用流問題。有些問題有數萬個節點和弧，是非常龐大的。有時弧的數量甚至可能還會多得多，達到幾百萬條。大家在Excel中使用的這個簡化版本的規劃求解中沒有網絡單純法，但其他的線性規劃商業軟件包中通常都有這種方法。4.2最小費用流問題最小費用流問題有五種重要的特殊類型：（1）運輸問題：有出發地（供應點：供應量）和目的地（需求點：需求量），沒有轉運點和弧的容量限制，目標是總運輸成本最?。ɑ蚩偫麧欁畲螅＃?）指派問題：出發地（供應點：供應量為1）是人，目的地（需求點：需求量為1）是任務，沒有轉運點和弧的容量限制，目標是總指派成本最?。ɑ蚩偫麧欁畲螅＃?）轉運問題：有出發地（供應點：供應量）和目的地（需求點：需求量），有轉運點，但沒有弧的容量限制（或有容量限制），目標是流量的總費用最?。ɑ蚩偫麧欁畲螅?.2最小費用流問題最小費用流問題有五種重要的特殊類型（續）（4）最大流問題：有出發點（供應點）、目的地（需求點）、轉運點、弧的容量限制，但沒有供應量和需求量的限制，目標是使通過配送網絡到達目的地的總流量最大。（5）最短路問題：有出發點（供應點：供應量為1）

、目的地（需求點：需求量為1）、轉運點、沒有弧的容量限制，目標是使通過配送網絡到達目的地的總距離最短。4.3最大流問題研究網絡能通過的最大流量是生產和管理工作中常遇到的現實問題。例如：交通網絡中車輛的最大通行能力；生產流水線上產品的最大加工能力；供水網絡中水的最大流量；信息網絡中的信息傳送能力等。這類網絡的組成弧一般具有確定的最大通行能力（容量），而實際通過弧的流量則因網絡各弧容量的配置關系，有些常常達不到額定容量值，因此，研究實際能通過的最大流量問題，可以充分發揮網絡中設備的能力，并且能明確為使最大流量增大應如何改造網絡。最大流問題也與網絡中的流量有關，但目標不是使得流量的總費用最小，而是尋找一個流量方案，使得通過網絡的總流量最大。除了目標（流量最大化和費用最小化）不一樣外，最大流問題的特征與最小費用流問題的特征非常相似。4.3最大流問題例4-2

某公司要從起點VS（供應點）運送貨物到目的地VT（需求點），其網絡圖如圖4-4所示。圖中每條?。ü濣ci->節點j）旁的權ci

j表示這條運輸線路的最大運輸能力（容量）。要求制訂一個運輸方案，使得從VS到VT的貨運量達到最大，這個問題就是尋求網絡系統的最大流問題。708060403050407050VSV1V2V3V5V4VT4.3最大流問題例4-2最大流問題的線性規劃數學模型：（1）決策變量設fi

j為?。ü濣ci->節點j）的流量。（2）目標函數

從供應點VS流出的總流量最大。（3）約束條件(轉運點的凈流量為0、弧的容量限制、非負）4.3最大流問題例4-2最大流問題的電子表格模型4.3.4最大流問題的變形最大流問題的變形主要在于：有多個供應點和（或）多個需求點。例4-3

在例4-2的基礎上，增加了一個供應點PS、一個需求點PT、兩個轉運點P1和P2，以及與之相連的7條弧，如圖4-6所示。目標是從2個供應點VS和PS運出的貨物量最大。本問題是一個有2個供應點和2個需求點的最大流問題。70804010203050406030404070502060V1V2V3V5V4VTP1PSPTP2VS4.3.4最大流問題的變形例4-3的線性規劃模型4.3.4最大流問題的變形例4-3的電子表格模型4.3.5最大流問題的應用舉例最大流問題的一些實際應用：（1）通過配送網絡的流量最大，如例4-2和例4-3。（2）通過管道運輸系統的油的流量最大。（3）通過輸水系統的水的流量最大。（4）通過交通網絡的車輛的流量最大。4.3.5最大流問題的應用舉例例4-4工程計劃問題。某市政工程公司在未來5－8月份需完成4項工程：修建一條地下通道、修建一座人行天橋、新建一條道路和道路維修。工期和所需勞動力見表4-1。該公司共有勞動力120人，任一工程在一個月內的勞動力投入不能超過80人。問公司應如何分派勞動力才能完成所有工程？是否能按期完成？工程工期需要的勞動力（人）A.地下通道5－7月100B.人行天橋6－7月80C.新建道路5－8月200D.道路維修8月804.3.5最大流問題的應用舉例【解】本問題可以用最大流問題的方法來求解。將工程計劃問題用圖4-8（下一張幻燈片）表示。圖中的節點5、6、7、8分別表示5－8月份，節點A、B、C、D表示4項工程。為了求解問題方便，增加了一個虛擬供應點S和一個虛擬需求點T。用弧表示某月完成某項工程的狀態，弧的流量為所投入的勞動力，受到勞動力的限制（弧旁的數字表示弧的容量，從虛擬供應點S開始的弧，其容量為該公司共有的勞動力120人；從節點5、6、7、8開始到節點A、B、C、D的弧，其容量為任一工程在一個月內的勞動力投入，不能超過80人；到虛擬需求點T的弧，其容量為每項工程所需的勞動力）。合理安排每個月各工程的勞動力，在不超過現有人力的條件下，盡可能保證工程按期完成，就是求圖4-8中從虛擬供應點S到虛擬需求點T的最大流問題。4.3.5最大流問題的應用舉例S6758BCADT120801008020080例4-4工程計劃問題的網絡圖4.3.5最大流問題的應用舉例例4-4市政工程公司勞動力分派的電子表格模型4.3.5最大流問題的應用舉例例4-4求解結果（每個月各工程的勞動力分派方案）如表4-2所示。6月份有剩余勞動力20人，4項工程恰好能按期完成。月份投入勞動力工程A工程B工程C工程D512080

40

6100（剩20）204040

7120

4080

8120

4080合計46010080200804.3.5最大流問題的應用舉例例4-5招聘問題。某單位招聘懂俄、英、日、德、法文的翻譯各1人，現有5人應聘，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，問：這5個人是否都能得到聘書？最多幾個人可以得到招聘？招聘后每個人從事哪一方面的翻譯工作？【解】本問題看似指派問題，但沒有指派成本，目標也不是總指派成本最小，而是“最多幾個人可以得到聘書”，因此本問題可以用最大流問題的方法來求解。方法1：與例4-4類似，將招聘問題用圖4-10表示。為了求解問題方便，增加了一個虛擬供應點S和一個虛擬需求點T（而方法2就沒有增加這兩個虛擬節點）。方法2：把該招聘問題看作變形的指派問題，因為目標是“最多幾個人可以得到聘書”，所以用最大流問題的方法來求解。變形的指派問題也可用網絡圖表示，如圖4-13所示。4.3.5最大流問題的應用舉例例4-5

招聘問題（方法1）的網絡圖（圖4-10，有虛擬節點S和T）S乙丙甲丁英日俄德T111戊法4.3.5最大流問題的應用舉例例4-5

招聘問題（方法1）的電子表格模型和求解結果乙丙甲丁英日俄德戊法4.3.5最大流問題的應用舉例例4-5

招聘問題（方法2）的網絡圖（圖4-13，變形的指派問題）乙丙甲丁英日俄德戊法4.3.5最大流問題的應用舉例例4-5

招聘問題（方法2）的電子表格模型和求解結果乙丙甲丁英日俄德戊法4.4最小費用最大流問題在實際的網絡應用中，當涉及流的問題時，有時不僅要考慮流量，還要考慮費用問題，尤其是需兼顧流量和費用問題，于是就出現了最小費用最大流問題。所謂的“最小費用最大流問題”，就是保證在最大流的情況下，如果網絡有多個最大流量運輸方案，則尋求其中費用最小的方案。最小費用最大流問題是最小費用流問題的特殊情況。因此，仍舊是單一目標的線性規劃問題。如果問題明確提出求最小費用最大流問題，則問題可以分成兩步求解（建立兩個模型）：第一步按照前面介紹的方法，求出不考慮成本時的最大流量；第二步是將前一步確定的最大流量作為新的約束條件，添加到求最小費用的模型中。4.4最小費用最大流問題例4-6

某公司有一個管道網絡（圖4-16），使用這個網絡可以把石油從采地V1輸送到銷地V7。由于輸油管道長短不一，每段管道除了有不同的容量cij限制外，還有不同的單位流量的費用bij。每段管道旁括號內的數字為（cij，bij）。如果使用這個管道網絡，從采地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(容量cij,費用bij)4.4最小費用最大流問題【解】用線性規劃來求解此問題，分為兩步：第一步：先求出此管道網絡的最大流量F（最大流問題）。第二步：在最大流量F的所有解中，找出一個最小費用的解（最小費用流問題）。4.4最小費用最大流問題第一步：先求出此管道網絡的最大流量F（最大流問題）。設通過?。╒i,Vj）的流量為fij，則例4-6最大流問題的線性規劃模型為：4.4最小費用最大流問題第一步：先求出此管道網絡的最大流量F（最大流問題）石油網絡最大流問題的電子表格模型求得的最大流量F＝104.4最小費用最大流問題第二步：在最大流量F=10的所有解中，找出一個最小費用的解（最小費用流問題）設通過?。╒i,Vj）的流量為fij，則例4-6最小費用最大流問題的線性規劃模型為：4.4最小費用最大流問題第二步：在最大流量F=10的所有解中，找出一個最小費用的解（最小費用流問題）石油網絡最小費用最大流問題的電子表格模型求得的最小費用為1454.5最短路問題最短路問題是網絡理論中應用最廣泛的問題之一。許多優化問題可以使用這個模型，如管道鋪設、路線安排、廠區布局等。全球定位系統（GPS）是人們熟知的，現在智能手機也配置了導航軟件。它可以為我們計算出滿足各種不同要求的、從出發地到目的地的最優路徑，可能花費時間最短，也可能過路費最少。GPS尋找最優路徑就是最短路問題的典型應用。最短路問題最普遍的應用是在兩個點之間尋找最短路線，是最小費用流問題的一種特殊類型：出發地（供應點）的供應量為1、目的地（需求點）的需求量為1、轉運點的凈流量為0、沒有弧的容量限制，目標是使通過網絡到目的地的總距離最短。4.5最短路問題例4-7

某人每天從住處V1開車到工作地點V7上班，圖中各弧旁的數字表示道路的長度（千米），試問他從家出發到工作地點，應選擇哪條路線，才能使路上行駛的總距離最短。V1V2V3V4V5V6V729683.51452.534.5最短路問題【解】這是一個最短路問題。其數學模型為：（1）決策變量：設xij為弧(節點Vi->節點Vj)是否走

（1表示走，0表示不走）。（2）目標函數本問題的目標是總距離最短（3）約束條件(節點凈流量、非負）4.5最短路問題例4-7最短路問題的電子表格模型4.5最短路問題例4-7最短路問題的求解結果：某人從家V1出發到工作地點V7，他開車應行駛的路線為：V1－>V2－>V3－>V5－>V7此時路上行駛的總距離最短，為13.5千米。V1V2V3V4V5V6V7262.534.6最小支撐樹問題許多網絡問題可以歸結為最小支撐樹問題。例如，設計長度最短的公路網，把若干城市（鄉村）連接起來；設計用料最省的電話線網（光纖），把有關單位聯系起來；等等。這種問題的目標是設計網絡。雖然節點已經給出，但必須決定在網絡中要加入哪些邊。特別要指出的是，向網絡中插入的每一條可能的邊都有成本。為了使每兩個節點之間有連接，需要插入足夠的邊。目標就是以某種方法完成網絡設計，使得邊的總成本最小。這種問題稱為最小支撐樹問題。4.6最小支撐樹問題例4-8某公司鋪設光導纖維網絡問題。某公司的管理層已經決定鋪設最先進的光導纖維網絡，為公司的主要中心之間提供高速通信（數據、聲音和圖像等）。圖4-22（下一張幻燈片）中的節點顯示了該公司主要中心（包括公司的總部、巨型計算機、研究區、生產和配送中心等）的分布圖。虛線是鋪設纖維光纜的可能位置。每條虛線旁的數字表示選擇在這個位置鋪設光纜的成本（千元）。為了充分利用光纖技術在中心之間高速通信上的優勢，不需要在每兩個中心之間都用一條光纜把它們直接連接起來?，F在的問題就是要確定需要鋪設哪些光纜，使得提供給每兩個中心之間的高速通信的總成本最小。4.6最小支撐樹問題圖4-22公司主要中心的分布圖425414371572ABDCEFG4.6最小支撐樹問題【解】實際上，這就是一個最小支撐樹問題。通過“貪婪算法”來求解。求解最小支撐樹問題的貪婪算法有很多種。比如，Kruskal算法（或稱避圈法），其步驟如下：（1）選擇第一條邊：選擇成本最小的備選邊。（2）選擇下一條邊：從剩下的邊中選取一條邊滿足：

①最小邊；②不構成圈。（3）重復第（2）步，直到選取的邊數為節點數-1

（邊數＝節點數-1）。此時就得到了最優解（最小支撐樹）處理成本相同的邊：當有幾條邊同時是成本最小的邊時，則從中任意選擇一條邊（不會影響最后的最優目標值）。利用Kruskal算法求解例4-8的最小支撐樹的步驟：P131－1324.6最小支撐樹問題圖4-23公司的最小支撐樹總成本為1＋1＋2＋2＋3＋5＝14千元4.7.1貨郎擔問題貨郎擔問題在運籌學中是一個著名的命題。有一個走村串戶的賣貨郎，他從某個村莊出發，穿過若干個村莊一次且僅一次，最后仍回到出發的村莊。問他應如何選擇行走路線，可使總行程最短？現在把問題一般化。設有n個城市，一位商人從n個城市中的某個城市出發，到其他n-1個城市去推銷商品，每個城市去一次且僅一次，最后回到出發城市（稱能到每個城市一次且僅一次的路線為一個巡回）。問他如何選擇行走的路線，可使總的距離最短（或總的費用最少）？4.7.1貨郎擔問題對于貨郎擔問題，也是將一條邊看作長度相等、方向相反的兩條弧，其線性規劃模型P133。用Excel求解貨郎擔問題的想法源