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

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

2、xij 為從產(chǎn)地Ai運(yùn)往銷(xiāo)地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個(gè)產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個(gè)銷(xiāo)地； （2）si 表示產(chǎn)地Ai的產(chǎn)量； dj 表示銷(xiāo)地Bj 的銷(xiāo)量

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

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

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

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

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

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

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

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

14、所需船只包括兩個(gè)部分：載貨船、調(diào)度船。 (1)載貨航行需要的船只數(shù)：3*19+2*5+9+15=91條,3運(yùn)輸問(wèn)題的應(yīng)用,問(wèn)題的核心是：如何使調(diào)度船的數(shù)量為最少？ 亦即如何按照最近原則調(diào)度船只。,27,(2)各港口調(diào)度需要的船只數(shù)（即每天為以后載貨準(zhǔn)備的空載船只數(shù)）： 各港口每天船只的余缺數(shù)為：,3運(yùn)輸問(wèn)題的應(yīng)用,28,3運(yùn)輸問(wè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條,共計(jì)最少需要船只：91+40=131條,29,3運(yùn)輸問(wèn)題的應(yīng)用,案例7、某公司有A1、 A2、 A3三個(gè)分廠生產(chǎn)某種物資，分別供應(yīng)B1、 B2、 B3、 B4四個(gè)地區(qū)的銷(xiāo)售公司銷(xiāo)售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表： 假設(shè)： 1.每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷(xiāo)地，可以從其中幾個(gè)產(chǎn)地集中一起運(yùn)； 2.運(yùn)往各銷(xiāo)地的物資可以先運(yùn)給其中幾個(gè)銷(xiāo)地，再轉(zhuǎn)運(yùn)給其他銷(xiāo)地； 3.除產(chǎn)銷(xiāo)地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷(xiāo)地之間或在產(chǎn)地與銷(xiāo)地之間轉(zhuǎn)運(yùn)。,30,3運(yùn)輸問(wèn)題的應(yīng)用,分廠、中轉(zhuǎn)站和銷(xiāo)售公司之間的單位運(yùn)價(jià)如下表所示： 試求總費(fèi)用為最低的調(diào)運(yùn)方案？,31,解：設(shè) xij 為從 i 到 j 的運(yùn)輸量

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

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