《運籌學(xué)（第3版）》 課件 第3章 運輸問題和指派問題；第4章 網(wǎng)絡(luò)最優(yōu)化問題

實用運籌學(xué)

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

3.2.1產(chǎn)銷平衡的運輸問題例3-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)地）到四個銷售點（銷地）的單位產(chǎn)品運價如表3-2所示。問該公司應(yīng)如何調(diào)運產(chǎn)品，才能在滿足四個銷售點的銷量的前提下，使總運費最?。夸N售點B1銷售點B2銷售點B3銷售點B4加工廠A1311310加工廠A21928加工廠A3741053.2.1產(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為從加工廠Ai（i＝1,2,3）運往銷售點Bj（j=1,2,3,4）的運輸量。（2）目標(biāo)函數(shù)

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

加工廠

運輸量

銷售點

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

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

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

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

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

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

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

某公司決定使用三個有生產(chǎn)余力的工廠進(jìn)行四種產(chǎn)品的生產(chǎn)。生產(chǎn)每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來衡量（見表3-7的最右列）。而每種產(chǎn)品每天有一定的需求量（見表3-7的最后一行）。除了工廠2不能生產(chǎn)產(chǎn)品3以外，每個工廠都可以生產(chǎn)這些產(chǎn)品。然而，每種產(chǎn)品在不同工廠中的單位成本（元）是有差異的（如表3-7所示）。現(xiàn)在需要決定的是在哪個工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。單位成本生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠24029一2375工廠33730272145需求量203030403.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ù)學(xué)模型：設(shè)xij為工廠i生產(chǎn)產(chǎn)品j

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

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

最少供應(yīng)量實際供應(yīng)量

要求訂購量

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

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

132143311310A21

一35一21928A33一

1一2374105中間轉(zhuǎn)運站T1231

1322846T215一1

114527T34一231

21824T4323212

1一26銷售點（銷地）B13172411

142B21194858一1

21B33210422242

3B410856746213

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

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

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

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

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

設(shè)xij為指派工廠i（i=1,2,3）生產(chǎn)產(chǎn)品j（j=1,2,3,4)3.6指派問題的變形例3-7的電子表格模型、最優(yōu)指派生產(chǎn)方案網(wǎng)絡(luò)圖2312314工廠

指派生產(chǎn)

產(chǎn)品

本章上機實驗1．實驗?zāi)康?/p>

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

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

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

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

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

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

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

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

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

⑦最小費用流問題的目標(biāo)是在滿足給定需求的條件下，使得通過配送網(wǎng)絡(luò)的總成本最?。ɑ蚩偫麧欁畲螅?.2最小費用流問題（3）最小費用流問題的解的特征①具有可行解的特征：在以上假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點所提供的供應(yīng)量總和等于需求點所需要的需求量總和時（即平衡條件），最小費用流問題有可行解。②具有整數(shù)解的特征：只要所有的供應(yīng)量、需求量和弧的容量都是整數(shù)，任何最小費用流問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解（與運輸問題和指派問題有整數(shù)解一樣）。因此，沒有必要加上所有決策變量都是整數(shù)的約束條件。4.2最小費用流問題最小費用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fi

j為?。ü?jié)點i->節(jié)點j）的流量。（2）目標(biāo)是使通過配送網(wǎng)絡(luò)的總成本最小。（3）約束條件

①所有供應(yīng)點的凈流量（總流出－總流入）為正； ②所有轉(zhuǎn)運點的凈流量為零； ③所有需求點的凈流量為負(fù)； ④所有弧的流量fi

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

j非負(fù)。4.2最小費用流問題例4-1最小費用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fi

j為?。ü?jié)點i->節(jié)點j）的流量。（2）目標(biāo)函數(shù)本問題的目標(biāo)是使通過配送網(wǎng)絡(luò)的總運輸成本最小4.2最小費用流問題①供應(yīng)點F1

供應(yīng)點F2

②轉(zhuǎn)運點DC ③需求點W1

需求點W2

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

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

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

某公司要從起點VS（供應(yīng)點）運送貨物到目的地VT（需求點），其網(wǎng)絡(luò)圖如圖4-4所示。圖中每條?。ü?jié)點i->節(jié)點j）旁的權(quán)ci

j表示這條運輸線路的最大運輸能力（容量）。要求制訂一個運輸方案，使得從VS到VT的貨運量達(dá)到最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。708060403050407050VSV1V2V3V5V4VT4.3最大流問題例4-2最大流問題的線性規(guī)劃數(shù)學(xué)模型：（1）決策變量設(shè)fi

j為?。ü?jié)點i->節(jié)點j）的流量。（2）目標(biāo)函數(shù)

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

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

40

6100（剩20）204040

7120

4080

8120

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

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

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

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

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

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

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

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

①最小邊；②不構(gòu)成圈。（3）重復(fù)第（2）步，直到選取的邊數(shù)為節(jié)點數(shù)-1

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