實用運籌學

－－運用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：目標是使與運輸量有關的總利潤最大而不是使總成本最小（Min－>

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：目標是與指派有關的總利潤最大而不是總成本最小；特征7：實際能夠完成的任務數小于總人數，也小于總任務數。3.6指派問題的變形例3-7指派工廠生產產品問題。題目見例3-3，即某公司需要安排三個工廠來生產四種產品，相關的數據見表3-7。在例3-3中，允許產品生產分解，但這將產生與產品生產分解相關的隱性成本（包括額外的設置、配送和管理成本等）。因此，管理人員決定在禁止產品生產分解發生