運(yùn)輸問題資料

1、運(yùn)輸問題運(yùn)輸問題及其數(shù)學(xué)模型表上作業(yè)法產(chǎn)銷不平衡的運(yùn)輸問題應(yīng)用舉例運(yùn)輸問題及其數(shù)學(xué)模型一、運(yùn)輸問題的數(shù)學(xué)模型單一品種運(yùn)輸問題的典型情況：設(shè)某種物品有m個(gè)產(chǎn)地 Ai,A2,Am,各產(chǎn)地的產(chǎn)量分別是ai,a2,am；有N個(gè)銷地 Bi,B2,Bn,各銷地地銷量分別為bi,b2,bn。假定從產(chǎn)地 Ai(i = 1,2,m)向銷地Bj(j = 1,2,n)運(yùn)輸單位物品的運(yùn)價(jià)是5，問 怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最??？數(shù)據(jù)如下標(biāo)所示。表1產(chǎn)銷平衡表表2單位運(yùn)價(jià)表有時(shí)可把兩表合一如果運(yùn)輸問題的總產(chǎn)量等于其總銷量，即有Wfli = 1f - I則稱該運(yùn)輸問題為產(chǎn)銷平衡運(yùn)輸問題；反之，稱為產(chǎn)銷不平衡運(yùn) 輸問題。

2、運(yùn)輸問題的數(shù)學(xué)模型如下：min z =產(chǎn)行i =1 f « imX H" = 5" J = 1，,，制i-l用 =: = 1 j 2 >1$ = iM廳0這就是運(yùn)輸問題的數(shù)學(xué)模型，它包含MX n個(gè)變量，(M十M)個(gè)約 束方程.其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊.二、運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)1、運(yùn)輸問題有有限最優(yōu)解，即必有最優(yōu)基本可行解2、運(yùn)輸問題約束條件的系數(shù)矩陣A的秩為(m+n-1)以1Ml 麗'年用-2* * *匯川 1 11下1 1 * ' 4 1 |. 行1 1 1 j1 1 1 :1 1 1 _， 行« « - 1

3、1 1該系數(shù)矩陳中對(duì)應(yīng)于變量xij的系數(shù)向量pij ,其分量中除第i個(gè)和第m十j個(gè)為1以外，其余的都為零.即Pij = (0-1-1-0) =ei+em+j對(duì)產(chǎn)銷平衡的運(yùn)輸問題，由于有以下關(guān)系式存在：特點(diǎn)：(1)約束條件系數(shù)矩陣的元素等于0或1約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約束方程中也出現(xiàn)一次。.R(A)Wm+n-1此外，對(duì)于產(chǎn)銷平衡問題，還有以下特點(diǎn)所有結(jié)構(gòu)約束條件都是等式約束(4)各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和表上作業(yè)法、解題步驟 第1步：用西北角法或最小元素法確定初始基本可行解。第2步：位勢(shì)法求非基變量的檢驗(yàn)數(shù)（解的最優(yōu)性檢

4、驗(yàn)），若最優(yōu) 準(zhǔn)則（TijA0,則當(dāng)前解最優(yōu)，計(jì)算停止，否則轉(zhuǎn)第3步。第3步：取一個(gè)檢驗(yàn)數(shù)最小的非基變量做進(jìn)基變量。第4步：用閉回路法調(diào)整當(dāng)前基本可行解，轉(zhuǎn)第2步1 .確定初始基本可行解（初始調(diào)運(yùn)方案）以實(shí)例介紹：例 某公司生產(chǎn)糖果，它有三個(gè)加工廠A1,A2,A3,每月產(chǎn)量分別 為7t,6t,5t,6t。已知從第i個(gè)加工廠到第j個(gè)銷售店的每噸糖果的運(yùn) 價(jià)Cij見表，試設(shè)計(jì)在滿足各銷售店需求量的前提下，各加工廠 到各銷售店的每月調(diào)運(yùn)方案，使總的運(yùn)費(fèi)最小。運(yùn)價(jià)表表3-3單位：丸噸加工廠% 出跖3nr-.-3JO41g2B74；ID5A西北角法B最小元素法2 .解的最優(yōu)性判別（位勢(shì)法，也稱對(duì)偶變量法

5、）3 .用閉回路法調(diào)整當(dāng)前基可行解二、表上作業(yè)法計(jì)算中的幾個(gè)問題1、某個(gè)基本可行解有幾個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)若運(yùn)輸問題的某個(gè)基可行解有幾個(gè)非基變量的檢驗(yàn)數(shù)均為 負(fù)，在繼續(xù)進(jìn)行迭代時(shí)，取它們中的任一變量均可使目標(biāo)函數(shù)值 得到改善，但通常取。產(chǎn)0中最小者對(duì)應(yīng)的變量為換入變量。 2、無(wú)窮多個(gè)最優(yōu)解當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時(shí)，如果有某非基變量的檢驗(yàn)數(shù) =0,則說明該運(yùn)輸問題有無(wú)窮多最優(yōu)解。（如上例，為得到另一 個(gè)最優(yōu)解，只需讓 = 0的非基變量進(jìn)基）3、退化問題當(dāng)運(yùn)輸問題某部分產(chǎn)地的產(chǎn)量和與另一部分銷地的銷量和 相等時(shí)，在迭代過程中有可能在某個(gè)格填入一個(gè)運(yùn)量時(shí)需同時(shí)劃 去運(yùn)輸表的一行和一列，這時(shí)就出現(xiàn)

6、了退化。在運(yùn)輸問題中，退化解是時(shí)常發(fā)生的，為了使表上作業(yè)法的 迭代工作進(jìn)行下去，退化解應(yīng)在同時(shí)劃去的一行或一列中的某個(gè) 空格中填入數(shù)字0,表示這個(gè)格中的變量是取值為 0的基變量， 使迭代過程中基可行解的分量恰好為 m+n-1個(gè)。b.在用閉回路法調(diào)整當(dāng)前基本可行解時(shí)， 調(diào)整量0的取值應(yīng) 為0=minXj/（ i,j ）為閉回路上所有偶數(shù)號(hào)格點(diǎn)。這時(shí)可能出現(xiàn) 有兩個(gè)（或以上）偶數(shù)號(hào)格點(diǎn)的xij都相等且都為極小值，只能 取其中一個(gè)為離基格，其余的仍作為基格，而在作運(yùn)輸量調(diào)整時(shí)， 運(yùn)輸量與0相等的那些偶數(shù)號(hào)格點(diǎn)的Xij都將調(diào)整為0,因此得到 的也是一個(gè)退化了的基可行解。4、循環(huán)問題練習(xí)產(chǎn)銷不平衡的運(yùn)輸

7、問題一、總產(chǎn)量大于總銷量即mn' ai' bji =1j =1此時(shí)運(yùn)輸問題的數(shù)學(xué)模型為m nmin z "" cj xj1 =1 j =1n'、Xij - aii = 1,2,., mjmXj = bj j = 1,2,., ni=1xj - 0m n 1min z 、c q 為1j，n+1£ %& i = 1,2,.,mjmv Xj =bjj =1,2,.,n 1一Xij - 0、總銷量大于總產(chǎn)量m 1 nmin z = " " CijXiji & j工/ n£ 為=aji =1,2,.,m+

8、1j苴m，乙 Xij bj j 1,2,., ni 二Xj之0例1 某市有三個(gè)造紙廠A1,A2,A3,其紙產(chǎn)量分別為8, 5, 9個(gè) 單位，有4個(gè)集中用戶B1,B2,B3,B4,其需用量為4, 3, 5, 6個(gè)單 位，由各廠到各用戶的單位運(yùn)價(jià)如表所示，試確定總運(yùn)費(fèi)最小的 調(diào)運(yùn)方案。例2較為復(fù)雜的產(chǎn)銷不平衡問題設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥，假設(shè)每個(gè)地區(qū)使用各 廠的化肥效果相同，各化肥廠的年產(chǎn)量，各地區(qū)的需求量以及它 們之間的單位運(yùn)價(jià)如表，求總運(yùn)費(fèi)最少的化肥調(diào)運(yùn)方案。需求地區(qū)北肥廠III11IV產(chǎn)盤（萬(wàn)噸）A132117葡BH131915C2023一50酷陸需求（萬(wàn)噸）5070010最高需

9、求L萬(wàn)噸）5Q70叫不限衰 3 如運(yùn)漸t萬(wàn)元/萬(wàn)噸分析：（1）這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬(wàn)噸，四個(gè)地區(qū)的最低需求為110萬(wàn)噸，最高需求為無(wú)限.根據(jù)現(xiàn)有產(chǎn)量及I, n,m地區(qū)的最低需求，第 Iv個(gè)地區(qū) 每年最多能分配到（50+60+50）-（30+70+0）=60萬(wàn)噸，這樣四個(gè)地 區(qū)的最高需求為50+ 70+30+ 60= 210萬(wàn)噸，大于總產(chǎn)量.（2）為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠 D,其年產(chǎn)量為210-160=50萬(wàn)噸.（3）由于各地區(qū)的需要量包含兩部分， 最低需求和額外需求。 如地區(qū)I,其中30萬(wàn)噸是最低需求，故不能由假想化肥廠 D供 給，令相應(yīng)運(yùn)價(jià)為M

10、（任意大正數(shù)）.而另一部分20萬(wàn)噸滿足或 不滿足均可以，因此可以由假想化肥廠 D供給，按前面講的， 令相應(yīng)運(yùn)價(jià)為0。這樣，凡是需求分兩種情況的地區(qū)，實(shí)際上可 按照兩個(gè)地區(qū)看待.這樣可以寫出這個(gè)問題的產(chǎn)銷平衡表（表3 26）和單位運(yùn)價(jià)表（表327）.產(chǎn)銷平衡表、地嚴(yán)嫌r嚴(yán)IIin1VFwA B C Dso raso蜩*3Q307030ID5D表3T8產(chǎn)-平皿單位運(yùn)價(jià)表我377單位運(yùn)批集產(chǎn)地VItinIVIV"AuB121?17B141413n15L5rc191920打MMDM0M00兩個(gè)表也可以合在一起寫。根據(jù)表上作業(yè)法計(jì)算，可以求得這個(gè)問題的最優(yōu)方案如下:銷鼬產(chǎn)地r”111111Vr

11、JVJH產(chǎn)更A5050B201030的C30200soD30如50銷ftJO20703010加應(yīng)用舉例由于在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純 形法簡(jiǎn)單得多.所以在解決實(shí)際問題時(shí)，人們常常盡可能把某些 線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型. 下面介紹幾個(gè)典型的 例子.例1某廠按合同規(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)（包括儲(chǔ)存、維護(hù)）費(fèi) 用最小的決策.季 度生產(chǎn)

12、能力（臺(tái)）單位成本（萬(wàn)元）2510 .S113311.1U3011.0IV10113解：由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(jī)不一定當(dāng)季交貨， 所以設(shè)xij 為第i季度生產(chǎn)的用于第j季度交貨的柴油機(jī)數(shù).根據(jù)合同要求，必須滿足：一I。卜n+而一15#必+物，十工勢(shì)一25Xh +%.+癡 + " -20又每季度生產(chǎn)的用于當(dāng)季和以后各季交貨的柴油機(jī)數(shù)不可 能超過該季度的生產(chǎn)能力，故又有：工 十符？十聚k子。G 25知+知+和 35+毒藥+ *“ V 3。.、W 10第i季度生產(chǎn)的用于j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本 Cij 應(yīng)該是該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用. Cij的具體數(shù)值 見表X111“

13、1IV1曾810*95Il At)U)|HU011.1511.40IIIJ kuo11.1;IVLI JO巧，彼（萬(wàn)元）設(shè)用ai表示該廠第i季度的生產(chǎn)能力，bj表示第j季度的合 同供應(yīng)量，則問題可寫成：min考2 2%戶HW %, 一 包11。因?yàn)楫?dāng)j<i時(shí),xij=0 所以當(dāng)j<i時(shí)，取Cij=M,M為一個(gè)充分大的正數(shù)。此外，由于是產(chǎn)量大于銷量的不平衡問題，加上一個(gè)假想的需 求D,就可以把問題變成產(chǎn)銷平衡的運(yùn)輸模型， 并寫出產(chǎn)銷平衡 表和單位運(yùn)價(jià)表（合在一起，如下）銷地盧足5KHIIV口產(chǎn)敢1io. aUk”.If)11*25Q25111.】。IH2511譚口Qlit-MIf11

14、-001 U5D3C-IVMM口.打0mtt ftIQ15以20就經(jīng)用表上作業(yè)法求解，可得多個(gè)最優(yōu)方案，表332中列出最優(yōu) 方案之一.即第1季度生產(chǎn)25臺(tái)，10臺(tái)當(dāng)季交貨，15臺(tái)II季度 交貨；II季度生產(chǎn)5臺(tái).用于田季度交貨；田季度生產(chǎn) 30臺(tái)， 其中20臺(tái)于當(dāng)季交貨，10臺(tái)于IV季度交貨IV季度生產(chǎn)10臺(tái)， 于當(dāng)季交貨.按此方案生產(chǎn)，該廠總的生產(chǎn)（包括儲(chǔ)存、維護(hù)）的 費(fèi)用為773萬(wàn)元.餐 3-32銷囪季度生產(chǎn)季曳J- j1uinV口產(chǎn)量I LI 111 IVLOft5機(jī)卜103025351010銷 ftI'OL52510如例2某航運(yùn)公司承擔(dān)六個(gè)港口城市 A、B、C、D、E、F的四

15、條固定航線的物資運(yùn)輸任務(wù).已知（1）各條航線的起點(diǎn)、終點(diǎn)城 市及每天航班數(shù).（2）假定各條航線使用相同型號(hào)的船只，又已 知各城市間的航程天數(shù).（3）又知每條船只每次裝卸貨的時(shí)間各 需1天。問該航運(yùn)公司至少應(yīng)配備多少條船，才能滿足所有航線的運(yùn)輸需求？ 每天航班數(shù)表航 線起點(diǎn)城市終春城市每天航班船1EDS2C23AF1AD1各城市之間的航程天數(shù)IACPEF4(J121477R0135eC,S01555D1501720E7B517 'G7&52030解：該公司所需配備船只分兩部分：(1)載貨航程需要的周轉(zhuǎn)船只數(shù)。例如航線1,在港口 E裝貨1天，ED航程l 7天，在 D卸貨1天，總計(jì)19天.每天3航班，故該航線周轉(zhuǎn)船只需57 條.各條航線周轉(zhuǎn)所需船只數(shù)見表.以上累計(jì)共需周轉(zhuǎn)船只數(shù)91條.航域轉(zhuǎn)值天數(shù)航程天教卸貨天野小計(jì)航琥歌帚周轉(zhuǎn)船只放11171jy357213152加317191413115115(2)各港口間調(diào)度所需船只數(shù).有些港口每天到達(dá)船數(shù)多于需要 船數(shù).例如港口 D,每天到達(dá)3條，需求1條；而有些港口到達(dá) 數(shù)少于需求數(shù)，例如港口 B.各港口每天余缺船只數(shù)的計(jì)算見表.港口城市督天到達(dá)每天需京i余域數(shù)A01B121C2Q2D31彳E03一 3F1A1為使配備船只數(shù)最少，應(yīng)做到周轉(zhuǎn)的空船數(shù)為最少.因此建 立以下運(yùn)輸問題