第6章運(yùn)輸問題

1、1,第六章 運(yùn) 輸 問 題,1運(yùn) 輸 模 型 2運(yùn)輸問題的計算機(jī)求解 3運(yùn)輸問題的應(yīng)用 4*運(yùn)輸問題的表上作業(yè)法,2,問題的提出: 一般的運(yùn)輸問題就是要解決把某種產(chǎn)品（或原料、資源等）從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地，在每個產(chǎn)地的供給量與每個銷地的需求量已知，并知道各地之間的運(yùn)輸單價的前提下，如何確定一個使得總的運(yùn)輸費(fèi)用最小的方案。,1運(yùn) 輸 模 型,3,例1、某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各個銷地每件物品的運(yùn)費(fèi)如下表所示， 問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？,1運(yùn) 輸 模 型,4,解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè)

2、xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：,1運(yùn) 輸 模 型,5,Min Z= 6x11+4x12+6x13+6x21+5x22+5x23,s.t. x11 + x12 + x13 = 200 x21 + x22 + x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0 (i=1、2；j=1、2、3）,1運(yùn) 輸 模 型,6,1運(yùn) 輸 模 型,一般運(yùn)輸模型： （1）A1、A2、Am 表示某物資的m個產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個銷地； （2）si 表示產(chǎn)地Ai的產(chǎn)量； dj 表示銷地Bj 的銷量

3、； （3）cij 表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價。 xij 表示從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量。 （4）Z 表示總的運(yùn)輸費(fèi)用 如果： s1 + s2 + + sm = d1 + d2 + + dn ， 則稱該運(yùn)輸問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷不平衡。 下面，首先討論產(chǎn)銷平衡問題。,7,運(yùn)輸問題數(shù)據(jù)表,1運(yùn) 輸 模 型,8,運(yùn)輸問題變量表,1運(yùn) 輸 模 型,9,1運(yùn) 輸 模 型,產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型： m n Min Z = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i =

4、 1 xij 0 (i = 1,2,m ; j = 1,2,n) 在實際問題建模時，經(jīng)常會出現(xiàn)如下一些變化（很值得關(guān)注）： 1）有時目標(biāo)函數(shù)求最大，如求利潤最大或營業(yè)額最大等； 2）產(chǎn)銷不平衡時，可增加一個假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時），從而使得總產(chǎn)量總銷量（因為計算機(jī)求解時需要保持是產(chǎn)銷平衡的狀態(tài)）。,10,2運(yùn)輸問題的計算機(jī)求解,例2、某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地物品的單位運(yùn)價如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?解：增加一個假想的銷地B*4，由任意產(chǎn)地到該銷地的單位運(yùn)價為0， B*4的銷

5、量為100（600-500100）。,11,2運(yùn)輸問題的計算機(jī)求解,例3、某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地物品的單位運(yùn)價如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?解：增加一個假想的產(chǎn)地A*3，由該產(chǎn)地到任意銷地的單位運(yùn)價為0， A*3的產(chǎn)量為150（650-500150）。,12,3運(yùn)輸問題的應(yīng)用,一、產(chǎn)銷不平衡的運(yùn)輸問題 案例1、汽車客運(yùn)公司有豪華、中檔和普通三種型號的客車5輛、10輛和15輛，每輛車上均載客40人，汽運(yùn)公司每天要送400人到B1城市，送600人到B2城市。每輛客車每天只能送一次，從客運(yùn)公司到B1

6、和B2城市的票價如下表所示： 試建立平衡的運(yùn)價表？,13,3運(yùn)輸問題的應(yīng)用,解：由于每輛車額定40人，所以到B1和B2兩個城市各需要10輛車和15輛車。把豪華、中檔和普通三種型號的客車看成是產(chǎn)地，把B1和B2兩個城市看成是銷地，總產(chǎn)量比總銷量多出5，所以要假設(shè)一銷地B*3。 通過軟件求解，甲每天發(fā)5輛車到B1城市，乙每天發(fā)5輛車到B1城市，5輛車到B2城市，丙每天發(fā)10車輛到B2城市，多余5輛，最大收入為Z=40（580+560+550+1040）=54000（元）,14,3運(yùn)輸問題的應(yīng)用,案例2、石家莊北方研究院有一、二、三共三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城

7、、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價為： 由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0-300噸，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。,15,3運(yùn)輸問題的應(yīng)用,解： 根據(jù)題意，可把一區(qū)分成一區(qū)（必須要滿足供應(yīng)）和一區(qū)（不需要一定滿足），把三區(qū)分成三區(qū)（必須要滿足供應(yīng)）和三區(qū)（不需要一定滿足），作出產(chǎn)銷平衡的單位運(yùn)價表： 這里 M 代表一個很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的 x31、 x33、 x34取值為0。在計算機(jī)求解時，可把M設(shè)定成106或以上的數(shù)。 根據(jù)計算結(jié)果知道，一區(qū)只能得到2700噸煤，二區(qū)得到10

8、00噸煤，三區(qū)只能得到1800噸。,16,3運(yùn)輸問題的應(yīng)用,案例3、設(shè)有A、B、C三個化肥廠供應(yīng)1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)肥料效果相同，由三個化肥廠到四個地區(qū)的單位運(yùn)價有關(guān)數(shù)據(jù)如下表： 試求總費(fèi)用為最低的化肥調(diào)撥方案。,17,3運(yùn)輸問題的應(yīng)用,解： 根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價表： 最低要求必須滿足，因此把假想產(chǎn)地到1、2和4的相應(yīng)單位運(yùn)價設(shè)定為M ；而最高要求與最低要求的差額按需要安排，因此把假想產(chǎn)地到1、3和4的相應(yīng)單位運(yùn)價設(shè)定為 0。 4的銷量50是考慮問題本身適當(dāng)取的數(shù)據(jù)，是根據(jù)產(chǎn)銷平衡要求（實際總產(chǎn)量減去最低需求量，即：160-11050），確定 4的銷量為 50。D的產(chǎn)

9、量50也是根據(jù)產(chǎn)銷平衡要求適當(dāng)取的數(shù)據(jù)，即最大總需求量減去實際總產(chǎn)量（210-16050）。,18,3運(yùn)輸問題的應(yīng)用,二、生產(chǎn)與儲存問題 案例4、某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如下表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。,19,3運(yùn)輸問題的應(yīng)用,解： 設(shè) xij為第 i 季度生產(chǎn)交付第 j 季度銷售的柴油機(jī)數(shù)目，那么應(yīng)滿足： 交 貨： 生 產(chǎn)： x11 = 10 x11 + x12 + x1

10、3 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個產(chǎn)地的產(chǎn)量； 把第 j 季度銷售的柴油機(jī)數(shù)目看作第 j 個銷地的銷量。 把單位成本加上單位儲存、維護(hù)等費(fèi)用看作單位運(yùn)價，可構(gòu)造下列產(chǎn)銷平衡的單位運(yùn)價表：,20,3運(yùn)輸問題的應(yīng)用,目標(biāo)函數(shù)：Min Z= 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +1

11、1.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 D看作是每個季度多余的產(chǎn)能，實際并不生產(chǎn)，所以單位運(yùn)價為0。,21,3運(yùn)輸問題的應(yīng)用,案例5、光明儀器廠生產(chǎn)電腦繡花機(jī)是以銷定產(chǎn)的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表： 已知上年末庫存103臺繡花機(jī)（需要在今年上半年全部售完），如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫房，每臺增加運(yùn)輸成本0.1萬元，每臺機(jī)器每月的平均倉儲費(fèi)、維護(hù)費(fèi)為0.2萬元。在7-8月份銷售淡季，全廠停產(chǎn)2個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機(jī)器每臺增加成本1萬元。問應(yīng)如何安排

12、1-6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉儲、維護(hù)）最少？,22,3運(yùn)輸問題的應(yīng)用,解： 這個生產(chǎn)存儲問題可化為運(yùn)輸問題來做。 考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地 1）1-6月份合計生產(chǎn)能力為743臺（包括上年末儲存量103臺） ，銷量為707臺（包括6月份預(yù)留的庫存80臺）。由于計算機(jī)計算時，需要是產(chǎn)銷平衡的單位運(yùn)價表，則假想一銷地，其銷量為36臺； 2）一臺繡花機(jī)的單位成本單位生產(chǎn)費(fèi)用單位運(yùn)輸費(fèi)單位倉儲費(fèi)*倉儲月數(shù)，把單位成本看成是單位運(yùn)價； 3） 1-6表示1-6月份正常生產(chǎn)情況， 1-6表示1-6月份加班生產(chǎn)情況； 4） 6月份的需求除70臺銷量外，還要80臺預(yù)留庫存，其需求

13、應(yīng)為70+80=150臺； 5）上年末庫存103臺（需要運(yùn)至分廠庫房），只有倉儲費(fèi)和運(yùn)輸費(fèi)，把它列為第0行，由于必須要售清，所以到虛擬地的單位運(yùn)價為M；,23,3運(yùn)輸問題的應(yīng)用,產(chǎn)銷平衡的單位運(yùn)價表：,24,3運(yùn)輸問題的應(yīng)用,用“管理運(yùn)籌學(xué)”軟件解得的結(jié)果是：16月最低生產(chǎn)費(fèi)用為8307.5萬元，每月的銷售安排如下表所示：,25,案例6、某航運(yùn)公司承擔(dān)六個港口城市A、B、C、D、E、F間四條航線的貨物運(yùn)輸任務(wù)。各航線的起點、終點、日航班數(shù)如下：,假定各航線使用的船只相同，各城市間的航程天數(shù)如下：,每條船每次裝卸貨時間各需1天，問該公司至少應(yīng)配備多少條船？,3運(yùn)輸問題的應(yīng)用,三、轉(zhuǎn)運(yùn)問題,26,

14、所需船只包括兩個部分：載貨船、調(diào)度船。 (1)載貨航行需要的船只數(shù)：3*19+2*5+9+15=91條,3運(yùn)輸問題的應(yīng)用,問題的核心是：如何使調(diào)度船的數(shù)量為最少？ 亦即如何按照最近原則調(diào)度船只。,27,(2)各港口調(diào)度需要的船只數(shù)（即每天為以后載貨準(zhǔn)備的空載船只數(shù)）： 各港口每天船只的余缺數(shù)為：,3運(yùn)輸問題的應(yīng)用,28,3運(yùn)輸問題的應(yīng)用,為使配備船只數(shù)盡可能少，建立如下運(yùn)輸模型： 設(shè)xij表示每天從港口i調(diào)往港口j的空船數(shù)，則cijxij就表示 ij航線上周轉(zhuǎn)的空船數(shù)，cijxij表示所有航線周轉(zhuǎn)的空船總數(shù)。,2 3 5 14 13 17 7 8 3,調(diào)度需要的船只數(shù)為：2+5+13+17+3

15、=40條,共計最少需要船只：91+40=131條,29,3運(yùn)輸問題的應(yīng)用,案例7、某公司有A1、 A2、 A3三個分廠生產(chǎn)某種物資，分別供應(yīng)B1、 B2、 B3、 B4四個地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表： 假設(shè)： 1.每個分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個產(chǎn)地集中一起運(yùn)； 2.運(yùn)往各銷地的物資可以先運(yùn)給其中幾個銷地，再轉(zhuǎn)運(yùn)給其他銷地； 3.除產(chǎn)銷地之外，還有幾個中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。,30,3運(yùn)輸問題的應(yīng)用,分廠、中轉(zhuǎn)站和銷售公司之間的單位運(yùn)價如下表所示： 試求總費(fèi)用為最低的調(diào)運(yùn)方案？,31,解：設(shè) xij 為從 i 到 j 的運(yùn)輸量

16、，可得到有下列特點的線性規(guī)劃模型： 目標(biāo)函數(shù)： Min Z = 所有可能的運(yùn)輸費(fèi)用（單價運(yùn)價與運(yùn)輸量乘積之和） 約束條件： 對產(chǎn)地（分廠）i ：輸出量 - 輸入量 = 產(chǎn)量 對轉(zhuǎn)運(yùn)點（中轉(zhuǎn)站）：輸入量 - 輸出量 = 0 對銷地（銷售公司）j ：輸入量 - 輸出量 = 銷量,3運(yùn)輸問題的應(yīng)用,32,3運(yùn)輸問題的應(yīng)用,把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問題： 1、把三個分廠、四個中轉(zhuǎn)站和四個銷售公司都同時看作是輸出地（相當(dāng)于運(yùn)價表中的產(chǎn)地）和輸入地（相當(dāng)于銷地）； 2、單位運(yùn)價表中不可能方案的單位運(yùn)價取作M，自身對自身的單位運(yùn)價為0； 3、Ai：輸出量為 20（最大可能的發(fā)出量）， 輸入量為13、16和

17、11（最大可能的接受量），其中20為各點可能變化的最大流量； Ti ：輸入量、輸出量均為 20 （最大可能的發(fā)出量和接受量）； Bj： 輸出量分別為17、14、15和14（最大可能的發(fā)出量，因為各個銷地要保留本身必要的銷量），輸入量為 20（最大可能的接受量），其中20為各點可能變化的最大流量。 4、對于最優(yōu)方案，其中 xi i 為自身對自身的運(yùn)量，實際上不進(jìn)行運(yùn)作。,33,3運(yùn)輸問題的應(yīng)用,擴(kuò)大后的運(yùn)輸問題產(chǎn)銷平衡的單位運(yùn)價表：,34,3運(yùn)輸問題的應(yīng)用,經(jīng)過計算機(jī)求解得：,35,3運(yùn)輸問題的應(yīng)用,各分廠到各銷售公司的最佳運(yùn)輸方案為： A1A2：2 A1B3：5 A2B1：6 A3B2：3 A3B4：6 B1B2：3 總的運(yùn)輸費(fèi)用為68 * 此題若沒有中轉(zhuǎn)站，則總的運(yùn)輸費(fèi)用將達(dá)到85 *,36,4*運(yùn)輸問題的表上作業(yè)