第6章運輸問題

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

2、xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：,1運 輸 模 型,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運 輸 模 型,6,1運 輸 模 型,一般運輸模型： （1）A1、A2、Am 表示某物資的m個產(chǎn)地； B1、B2、Bn 表示某物質的n個銷地； （2）si 表示產(chǎn)地Ai的產(chǎn)量； dj 表示銷地Bj 的銷量

3、； （3）cij 表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。 xij 表示從產(chǎn)地Ai運往銷地Bj的運輸量。 （4）Z 表示總的運輸費用 如果： s1 + s2 + + sm = d1 + d2 + + dn ， 則稱該運輸問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷不平衡。 下面，首先討論產(chǎn)銷平衡問題。,7,運輸問題數(shù)據(jù)表,1運 輸 模 型,8,運輸問題變量表,1運 輸 模 型,9,1運 輸 模 型,產(chǎn)銷平衡運輸問題的數(shù)學模型： 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)如下一些變化（很值得關注）： 1）有時目標函數(shù)求最大，如求利潤最大或營業(yè)額最大等； 2）產(chǎn)銷不平衡時，可增加一個假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時），從而使得總產(chǎn)量總銷量（因為計算機求解時需要保持是產(chǎn)銷平衡的狀態(tài)）。,10,2運輸問題的計算機求解,例2、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地物品的單位運價如下表所示，問：應如何調運可使總運輸費用最??？ 解：增加一個假想的銷地B*4，由任意產(chǎn)地到該銷地的單位運價為0， B*4的銷

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

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

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

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

9、量50也是根據(jù)產(chǎn)銷平衡要求適當取的數(shù)據(jù)，即最大總需求量減去實際總產(chǎn)量（210-16050）。,18,3運輸問題的應用,二、生產(chǎn)與儲存問題 案例4、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如下表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。,19,3運輸問題的應用,解： 設 xij為第 i 季度生產(chǎn)交付第 j 季度銷售的柴油機數(shù)目，那么應滿足： 交 貨： 生 產(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)的柴油機數(shù)目看作第 i 個產(chǎn)地的產(chǎn)量； 把第 j 季度銷售的柴油機數(shù)目看作第 j 個銷地的銷量。 把單位成本加上單位儲存、維護等費用看作單位運價，可構造下列產(chǎn)銷平衡的單位運價表：,20,3運輸問題的應用,目標函數(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)，所以單位運價為0。,21,3運輸問題的應用,案例5、光明儀器廠生產(chǎn)電腦繡花機是以銷定產(chǎn)的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機平均生產(chǎn)費用見下表： 已知上年末庫存103臺繡花機（需要在今年上半年全部售完），如果當月生產(chǎn)出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元，每臺機器每月的平均倉儲費、維護費為0.2萬元。在7-8月份銷售淡季，全廠停產(chǎn)2個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機器每臺增加成本1萬元。問應如何安排

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

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

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

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

16、，可得到有下列特點的線性規(guī)劃模型： 目標函數(shù)： Min Z = 所有可能的運輸費用（單價運價與運輸量乘積之和） 約束條件： 對產(chǎn)地（分廠）i ：輸出量 - 輸入量 = 產(chǎn)量 對轉運點（中轉站）：輸入量 - 輸出量 = 0 對銷地（銷售公司）j ：輸入量 - 輸出量 = 銷量,3運輸問題的應用,32,3運輸問題的應用,把此轉運問題轉化為一般運輸問題： 1、把三個分廠、四個中轉站和四個銷售公司都同時看作是輸出地（相當于運價表中的產(chǎn)地）和輸入地（相當于銷地）； 2、單位運價表中不可能方案的單位運價取作M，自身對自身的單位運價為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 為自身對自身的運量，實際上不進行運作。,33,3運輸問題的應用,擴大后的運輸問題產(chǎn)銷平衡的單位運價表：,34,3運輸問題的應用,經(jīng)過計算機求解得：,35,3運輸問題的應用,各分廠到各銷售公司的最佳運輸方案為： A1A2：2 A1B3：5 A2B1：6 A3B2：3 A3B4：6 B1B2：3 總的運輸費用為68 * 此題若沒有中轉站，則總的運輸費用將達到85 *,36,4*運輸問題的表上作業(yè)