1、運輸問題和指派問題The Transportationand Assignment Problems本章內容要點運輸問題的基本概念及其各種變形的建模與應用指派問題的基本概念及其各種變形的建模與應用本章節內容1 運輸問題基本概念2 運輸問題數學模型和電子表格模型3 各種變形的運輸問題建模4 運輸問題應用舉例5 指派問題6 各種變形的指派問題建模 產大于銷（總產量大于總銷量）運輸問題 數學模型和電子表格模型各種變形的建模應用舉例 指派問題 數學模型和電子表格模型本章主要內容框架圖 產銷平衡（總產量等于總銷量） 銷大于產（總產量小于總銷量）運輸問題和指派問題 平衡指派問題（總人數等于總任務數） 各種

2、變形的建模1 運輸問題運輸問題最初起源于人們在日常生活中把某些物品或人們自身從一些地方轉移到另一些地方，要求所采用的運輸路線或運輸方案是最經濟或成本最低的，這就成為了一個運籌學問題。隨著經濟的不斷發展，現代物流業蓬勃發展，如何充分利用時間、信息、倉儲、配送和聯運體系創造更多的價值，向運籌學提出了更高的挑戰。要求科學地組織貨源、運輸和配送使得運輸問題變得日益復雜，但是其基本思想仍然是實現現有資源的最優化配置。1 運輸問題基本概念一般的運輸問題就是解決如何把某種產品從若干個產地調運到若干個銷地，在每個產地的供應量和每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用

3、最小的方案。平衡運輸問題的條件：1. 明確出發地（產地）、目的地（銷地）、供應量（產量）、需求量（銷量）和單位成本。2. 需求假設：每一個出發地都有一個固定的供應量，所有的供應量都必須配送到目的地。與之類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發地滿足。即“總供應總需求”。3. 成本假設：從任何一個出發地到任何一個目的地的貨物配送成本與所配送的數量成線性比例關系，因此成本就等于配送的單位成本乘以所配送的數量（目標函數是線性的）。1 運輸問題基本概念例1 某公司有三個加工廠A1、A2、A3生產某產品，每日的產量分別為：7噸、4噸、9噸；該公司把這些產品分別運往四個銷售點B1、B

4、2、B3、B4，各銷售點每日銷量分別為：3噸、6噸、5噸、6噸；從各工廠到各銷售點的單位產品運價如表1所示。問該公司應如何調運這些產品，在滿足各銷售點的需要量的前提下，使總運費最少？表1 各工廠到各銷售點的單位產品運價（元/噸）B1B2B3B4產量（噸）749A1A2A3銷量（噸）3173119463210510856對于例1，其數學模型如下：首先，三個產地A1、A2、A3的總產量為74920；四個銷地B1、B2、B3、B4的總銷量為365620。由于總產量等于總銷量，故該問題是一個產銷平衡的運輸問題。(1)決策變量設xij為從產地Ai運往銷地Bj的運輸量(i1,2,3;j=1,2,3,4)（

5、2）目標函數本問題的目標是使得總運輸費最小Min z =3x11 + 11x12 + 3x13 + 10 x14+ x21 + 9 x22 + 2 x23 + 8 x24+ 7 x31 + 4 x32 + 10 x33 + 5 x34（3）約束條件滿足產地產量（3個產地的產品都要全部配送出去）滿足銷地銷量（4個銷地的產品都要全部得到滿足）非負2 運輸問題數學模型和電子表格模型運輸問題是一種特殊的線性規劃問題，一般采用“表上作業法”求解運輸問題，但Excel的“規劃求解”工具還是采用“單純形法”來求解。例1的電子表格模型2 運輸問題數學模型和電子表格模型（1）產銷平衡運輸問題的數學模型具有m個產

6、地Ai（i1,2,m）和n個銷地Bj（j1,2,n）的運輸問題的數學模型為2 運輸問題數學模型和電子表格模型需要注意的是：運輸問題有這樣一個性質（整數解性質），只要它的供應量和需求量都是整數，任何有可行解的運輸問題必然有所有決策變量都是整數的最優解。因此，沒有必要加上所有變量都是整數的約束條件。由于運輸量經常以卡車、集裝箱等為單位，如果卡車不能裝滿的話，就很不經濟了。整數解性質就避免了運輸量（運輸方案）為小數的麻煩。（以滿足小的產量為準） i j=（3）銷大于產（供不應求）運輸問題2 運輸問題數學模型和電子表格模型例2 某廠按合同規定須于當年每個季度末分別提供10，15，25，20臺同一規格的

7、柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如表所示。如果生產出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護等費用1500元。要求在完成合同的情況下，做出使該廠全年生產（包括儲存、維護）費用最小的決策。各季度的生產能力及生產每臺柴油機的成本季度生 產 能 力 （ 臺 ） 單位成本（萬元）12342535301010.811.111.011.32 運輸問題數學模型和電子表格模型解：這是一個生產與儲存（庫存）問題，可以轉化為運輸問題來做。由于每個季度生產出來的柴油機不一定當季交貨，所以設xij為第i季度生產的第j季度交貨的柴油機數。則第i季度生產的第j季度交貨的每臺柴油機的實際

8、成本cij為：cij=第i季度每臺的生產成本+0.15(j-i)（儲存、維護等費用）把第i季度生產的柴油機數看作第i個生產廠商的產量；把第j季度交貨的柴油機數看作第j個銷售點的銷量；生產成本加儲存、維護等費用看作運費。將生產與儲存問題轉化為運輸問題，相關數據見表。2 運輸問題數學模型和電子表格模型柴油機生產的相關數據由表可知，總產量（生產能力）為25+35+30+10=100，總銷量（需求量）為10+15+25+20=70，因此是產大于銷的運輸問題。1234生產能力10.810.9511.1012311.1011.2511.0011.2511.40113010需求量1

9、0152520該生產與儲存問題（轉化為產大于銷的運輸問題）的數學模型為2 運輸問題數學模型和電子表格模型Min z = 10.80 x11 + 10.95 x12 + 11.10 x13 + 11.25 x14+ 11.10 x22 + 11.25 x23 + 11.40 x24+ 11.00 x33 + 11.15 x34+ 11.30 x442 運輸問題數學模型和電子表格模型例2的電子表格模型2 運輸問題數學模型和電子表格模型例3 某公司從兩個產地A1、A2將物品運往三個銷地 B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如表所示。問應如何調運，可使得總運輸費

10、最小？例3 運輸費用表B1B2B3產量A1A2銷量1311531529361222657845（銷大于產）2 運輸問題數學模型和電子表格模型解：由表知，總產量為78+45=123，總銷量為53+36+65=154，銷大于產(供不應求)。數學模型如下：設xij為產地Ai運往銷地Bj的物品數量2 運輸問題數學模型和電子表格模型例3的電子表格模型3 各種變形的運輸問題建模現實生活中符合產銷平衡運輸問題每一個條件的情況很少。一個特征近似但其中的一個或者幾個特征卻并不符合產銷平衡運輸問題條件的運輸問題卻經常出現。下面是要討論的一些特征：（1）總供應大于總需求。每一個供應量（產量）代表了從其出發地中配送出

11、去的最大數量（而不是一個固定的數值,）。（2）總供應小于總需求。每一個需求量（銷量）代表了在其目的地中所接收到的最大數量（而不是一個固定的數值,）。（3）一個目的地同時存在著最小需求和最大需求，于是所有在這兩個數值之間的數量都是可以接收的（,）。（4）在配送中不能使用特定的出發地目的地組合（xij=0）。（5）目標是使與配送數量有關的總利潤最大而不是使總成本最小。（Min Max）3 各種變形的運輸問題建模例4 某公司決定使用三個有生產余力的工廠進行四種新產品的生產。每單位產品需要等量的工作，所以工廠的有效生產能力以每天生產的任意種產品的數量來衡量（見表的最右列）。而每種產品每天有一定的需求量

12、（見表的最后一行）。每家工廠都可以制造這些產品，除了工廠2不能生產產品3以外。然而，每種產品在不同工廠中的單位成本是有差異的（如表所示）。現在需要決定的是在哪個工廠生產哪種產品，可使總成本最小。表 產品生產的有關數據單位成本（元）生產能力產品1產品2產品3產品4757545工廠1工廠2工廠3需求量414037202729303028273024232140解：指定工廠生產產品可以看作運輸問題來求解。本題中，工廠2不能生產產品3，這樣可以增加約束條件 ；并且，總供應x230（75+75+45=195）總需求（20+30+30+40=120）。其數學模型如下：設xij為工廠i生產產品j的數量3 各

13、種變形的運輸問題建模3 各種變形的運輸問題建模例4的電子表格模型產品4分在2個工廠生產3 各種變形的運輸問題建模例5 某公司在3個工廠中專門生產一種產品。在未來的4個月中，有四個處于國內不同區域的潛在顧客（批發商）很可能大量訂購。顧客1是公司最好的顧客，所以他的全部訂購量都應該滿足；顧客2和顧客3也是公司很重要的顧客，所以營銷經理認為作為最低限度至少要滿足他們訂單的1/3；對于顧客4，銷售經理認為并不需要進行特殊考慮。由于運輸成本上的差異，銷售一個產品得到的凈利潤也不同，很大程度上取決于哪個工廠供應哪個顧客（見表）。問應向每一個顧客供應多少貨物，以使公司總利潤最大？表4-8 工廠供應顧客的相關

14、數據產量單位利潤（元）顧客1 顧客2顧客3顧客4800050007000工廠1工廠2工廠3最小采購量最大采購量553729700070004218593000900046325120006000534835080003 各種變形的運輸問題建模解：該問題要求滿足不同顧客的需求（采購量），解決辦法：實際供給量最小采購量實際供給量最大采購量目標是利潤最大，而不是成本最小。其數學模型如下：設xij為工廠i供應給顧客j的產品數量3 各種變形的運輸問題建模例5的電子表格模型4 運輸問題應用舉例例6 某廠生產設備是以銷定產的。已知16月份各月的生產能力、合同銷量和單臺設備平均生產費用，如表所示。已知上年末庫

15、存103臺。如果當月生產出來的設備當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元，每臺設備每月的平均倉儲費、維護費為0.2萬元。78月份為銷售淡季，全廠停產1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產設備每臺增加成本1萬元。問應如何安排16月份的生產，使總的生產（包括運輸、倉儲、維護）費用最少？月份1月2月3月4月5月6月正常生產能力（臺）60509010010080加班生產能力（臺）101020404040合同銷量（臺）1047511516010370單臺費用（萬元）151413.5131313.54 運輸問題應用舉例例7 華中金剛石鋸片廠有兩條生產線，分別生產

16、直徑900-1800mm大鋸片基體20000片，直徑350-800mm中小鋸片基體40000片。公司在全國有25個銷售網點，主要銷售區域集中在福建、廣東、廣西、四川、山東5個石材主產區。為完成總廠的要求，公司決定一方面拿出10%的產量穩定與前期各個客戶的聯系以保證將來的市場區域份額，另一方面，面臨如何將剩余的90%的產量合理分配給五個石材主產區和其他省區，以獲取最大的利潤。各個銷售區的最低需求、銷售固定費用、每片平均運費、每片從總廠庫房的購進價與當地的銷售價差貢獻等自然情況見表。問應如何分配給各個銷售區，才能使得總利潤為最大？4 運輸問題應用舉例5 指派問題在現實生活中，經常會遇到指派人員做某

17、項工作（任務）的情況。指派問題的許多應用是用來幫助管理人員解決如何為一項即將開展的工作指派人員的問題。其他的一些應用如為工作指派機器、設備或工廠等。指派問題也稱分配問題，主要研究人和工作（任務）間如何匹配，以使所有工作完成的效率實現最優化。形式上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員，所需要解決的問題就是要確定出指派哪個人去完成哪項工作。5 指派問題指派問題的假設：（1）人的數量和工作的數量相等；（2）每個人只能完成一項工作；（3）每項工作只能由一個人來完成；（4）每個人和每項工作的組合都會有一個相關的成本（單位成本）；（5）目標是要確定如何指派才能使總成本最小。設決策變

18、量xij為第i個人做第j項工作，而已知5 指派問題目標函數系數cij為第i個人完成第j項工作所需要的單位成本。平衡指派問題的數學模型為5 指派問題需要說明的是：指派問題實際上是一種特殊的運輸問題。其中出發地是人，目的地是工作。只不過，每一個出發地的供應量都為1（因為每個人都要完成一項工作），每一個目的地的需求量都為1（因為每項工作都要完成）。由于運輸問題有“整數解性質”，因此，沒有必要加上所有決策變量都是0-1變量的約束。指派問題是一種特殊的線性規劃問題，有一種快捷的求解方法：匈牙利方法（HungarianMethod），但Excel的“規劃求解”工具還是采用“單純形法”來求解。5 指派問題例

19、8 某公司的營銷經理將要主持召開一年一度的由營銷區域經理以及銷售人員參加的銷售協商會議。為了更好地安排這次會議，他安排小張、小王、小李、小劉等四個人，每個人負責完成下面的一項工作：A、B、C和D。由于每個人完成每項任務的時間和工資不同（如表所示）。問如何指派，可使總成本最小。人員每小時工資（元）每一項工作所需要的時間（小時）工作A 工作B 工作C 工作D小張小王小李小劉35473932414556512732362540514346141213155 指派問題解：該問題是一個典型的指派問題。單位成本為每個人做每項工作的總工資目標是要確定哪個人做哪一項工作，使總成本最小供應量為1代表每個人都只能

20、完成一項工作需求量為1代表每項工作也只能有一個人來完成總人數（4人）和總任務數（4項）相等5 指派問題數學模型：設xij為指派人員i去做工作j（i，j1,2,3,4)5 指派問題電子表格模型6 各種變形的指派問題建模經常會遇到指派問題的變形，之所以稱它們為變形，是因為它們都不滿足平衡指派問題所有假設之中的一個或者多個。一般考慮下面的一些特征：（1）有些人并不能進行某項工作（相應的xij0）;（2）雖然每個人完成一項任務，但是任務比人多(人少事多);（3）雖然每一項任務只由一個人完成，但是人比任務多（人多事少）；（4）某人可以同時被指派給多個任務（一人可做幾件事）；（5）某事可以由多人共同完成（一事可由多人完成） ；（6）目標是與指派有關的總利潤最大而不是使總成本最小；（7）實際需要完成任務數不超過總人數也不超過總任務數。6 各種變形的指派問題建模例9 題目見例4，即某公司需要安排三個工廠來生產四種新產品，相關的數據在例4表4中已經給出。在例4中，允許產品生產分解，但這將產生與產品生產分解相關的隱性成本（包括額外的設置、配送和管理成本等）。因此，管理人員決定在禁止產品生產分解發生的情況下對問題進行分析。新問題描述為：已知如表所示的數據，問如何把每一個工廠指派給