運籌學(xué)運輸問題

第四章運輸問題 運輸問題的表示 網(wǎng)絡(luò)圖、線性規(guī)劃模型、運輸表 初始根底可行解 西北角法、最小元素法 非基變量的檢驗數(shù) 閉回路法、對偶變量法 確定進(jìn)基變量，調(diào)整運量，確定離基 變量1整理ppt運輸問題的提出運輸問題的直接背景是單一品種的物質(zhì)的運輸調(diào)度問題，其典型情況是：設(shè)某物品有m個產(chǎn)地A1,A2,…,Am,各產(chǎn)地的產(chǎn)量分別為a1,a2,…,am;n個銷地B1,B2,…,Bn,各銷地的銷量分別為b1,b2,…,bn.假定從產(chǎn)地Ai(i=1,2,…,m)向銷地Bj(j=1,2,…,n)運輸單位物質(zhì)的運價為cij,問怎樣調(diào)運這些物品才能使得總運費最??？2整理ppt運輸問題的表示——網(wǎng)絡(luò)圖A1A2Am產(chǎn)地B1B2Bn銷地a1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若則稱該問題為平衡運輸問題，否則稱為非平衡運輸問題。3整理ppt運輸問題的表示—表格表示這個表常稱為運輸表4整理ppt運輸問題的數(shù)學(xué)模型平衡問題的數(shù)學(xué)模型為各產(chǎn)地運出的物資數(shù)量等于其產(chǎn)量各銷地接受的物資數(shù)量等于其銷量其中5整理ppt運輸問題數(shù)學(xué)模型的特點運輸問題一定存在最優(yōu)解實際上是平衡運輸問題的一個可行解。此外由于目標(biāo)函數(shù)有下界，因此平衡運輸問題存在最優(yōu)解。

6整理ppt運輸問題系數(shù)矩陣的特點mn7整理ppt上述矩陣的列向量具有形式第i個第(m+j)個因此運輸問題約束條件系數(shù)矩陣的元素只能是0或1，對應(yīng)變量xij列除了第i個與第(m+j)個分量為1外，其它分量均為零8整理ppt此外產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型還具有特點：所有約束條件都是等式前m個約束條件的和等于后n個約束條件的和〔可以證明盡管有m+n個約束條件，但獨立的約束條件只有m+n-1個〕9整理ppt運輸問題的例子—表格表示10整理ppt運輸問題的例子—線性規(guī)劃模型供給地約束需求地約束11整理ppt運輸問題的解運輸問題的解可以表示為X=(xij),它表示一個運輸方案，其中xij表示從產(chǎn)地Ai到銷地Bj運送的物質(zhì)數(shù)量在用運輸表表示運輸問題時，也常將xij取的值填入對應(yīng)的格子表示一個解。但是對基可行解，通常僅將基變量取的值填入相應(yīng)的格中，稱之為數(shù)字格，而對應(yīng)著非基變量的格子，那么不填數(shù)字，稱之為空格。注：在一個基可行解中，所有mn個變量〔格子〕中，只有m+n-1個基變量〔數(shù)字格〕12整理ppt求解運輸問題的表上作業(yè)法13整理ppt求初始基可行解〔初始調(diào)運方案〕西北角法最小元素法沃格爾法14整理ppt初始基可行解—西北角法886481415整理ppt初始基可行解—最小元素法8210148616整理ppt沃格爾〔Vogel〕法2（5）130111421（3）0128（2）1201812（7）6122417整理ppt檢驗數(shù)的計算兩種方法：閉回路法和對偶變量法閉回路法的原理：非基變量的檢驗數(shù)等于非基變量增加一個單位時，目標(biāo)函數(shù)的改變量18整理ppt檢驗數(shù)的計算—閉回路法〔1〕82101486119整理ppt檢驗數(shù)的計算—閉回路法〔2〕821014861220整理ppt檢驗數(shù)的計算—閉回路法〔3〕8210148612121整理ppt檢驗數(shù)的計算—閉回路法〔4〕82101486121-122整理ppt檢驗數(shù)的計算—閉回路法〔5〕82101486121-11023整理ppt檢驗數(shù)的計算—閉回路法〔6〕82101486121-1101224整理ppt檢驗數(shù)的計算—對偶變量法對偶變量法也稱為位勢法，它是利用運輸問題的對偶問題求檢驗數(shù)。設(shè)運輸問題的對偶變量矩陣為那么對偶問題為25整理ppt利用單純形法的矩陣表示可知，變量xij的檢驗數(shù)可以表示為另一方面，對于(m+n-1)個基變量而言，檢驗數(shù)等于零，故可以得到包含(m+n)個變量的(m+n-1)個方程由該方程組求出對偶變量后即可計算出所有的檢驗數(shù)。26整理ppt檢驗數(shù)的計算—對偶變量法82101486u1=0v3=4v4=11u2=-1u3=-5v1=3v2=10121-1101227整理ppt解的改進(jìn)82101486-128整理ppt解的改進(jìn)8121484229整理ppt解的改進(jìn)81214842u1=0v3=4v4=11u2=-2u3=-5v1=4v2=10022191230整理ppt最優(yōu)解〔最優(yōu)調(diào)運方案〕81214842最小運費：31整理ppt表上作業(yè)法的幾個問題換入變量確實定退化〔兩種情況〕無窮多個最優(yōu)解的判別32整理ppt產(chǎn)銷不平衡的運輸問題解決的根本思路：將其轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題求解33整理ppt產(chǎn)大于銷的運輸問題這時有，數(shù)學(xué)模型為34整理ppt處理的方法為增加一個假想的銷地Bn+1，其銷量為各個產(chǎn)地運送物質(zhì)到假想銷地的單位運價為零，即ci(n+1)=035整理ppt假想的銷地36整理ppt這時有，數(shù)學(xué)模型為銷大于產(chǎn)的運輸問題37整理ppt處理的方法為增加一個假想的產(chǎn)地Am+1，其產(chǎn)量為假想產(chǎn)地運送物質(zhì)到各個銷地的單位運價為零，即c(m+1),1=038整理ppt假想的產(chǎn)地39整理ppt表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負(fù)檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，算出總運價40整理ppt表上作業(yè)法計算中的問題：〔1〕假設(shè)運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σij<0中最小者對應(yīng)的變量為換入變量?！?〕無窮多最優(yōu)解 產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，那么該問題有無窮多最優(yōu)解。41整理ppt⑵退化解： ※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時那么需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。 ※利用進(jìn)基變量的閉回路對解進(jìn)行調(diào)整時，標(biāo)有負(fù)號的最小運量〔超過2個最小值〕作為調(diào)整量θ，選擇任意一個最小運量對應(yīng)的基變量作為出基變量，并打上“×〞以示作為非基變量。42整理ppt

銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。43整理ppt產(chǎn)銷不平衡的運輸問題運輸問題運輸問題的應(yīng)用

例：有三個供給地要將物資運往五個需求地區(qū)，各產(chǎn)地的產(chǎn)量和個地區(qū)的需求以及運費情況如下表。要求：其中B2地區(qū)的115個單位必須滿足。供\求B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需要量25115603070產(chǎn)銷不平問：應(yīng)如何運輸總運費最?。?4整理ppt運輸問題運輸問題的應(yīng)用

供\求B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需要量25115603070產(chǎn)銷不平解：由于產(chǎn)量小于需求，因此虛設(shè)以產(chǎn)地A4，其產(chǎn)量為供需的差額20。與此項有關(guān)的費用一般設(shè)為0。又因為B1地區(qū)的需求要保證，所以應(yīng)該迫使虛設(shè)產(chǎn)地運輸?shù)皆摰貐^(qū)的運費本錢極高，從而在優(yōu)化過程中實現(xiàn)0運量。因此取該項費用為一個充分大的數(shù)M。由此可以建立如下的產(chǎn)銷平衡運輸費用表：45整理ppt運輸問題運輸問題的應(yīng)用

供\求B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需要量25115603070產(chǎn)銷不平供\求B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130A40M00020需要量25115603070產(chǎn)銷平衡46整理ppt運輸問題思考題1：

某部有B1，B2，B3三個作戰(zhàn)單位。每年分別需要某軍用品3500噸、1100噸、2400噸，這些用品都要由A1,A2兩兵工廠負(fù)責(zé)供給，兩兵工廠生產(chǎn)的軍用品質(zhì)量均相同。假設(shè)A1,A2的供給能力分別為1500噸、4000噸，運價(元/噸)如下表所示。由于需求大于供給，經(jīng)院研究決定B1區(qū)供給量可減少0-900噸，B2區(qū)必須滿足需求量，B3區(qū)供給量不少于1600噸，試求總費用為最低的調(diào)運方案。B1B2B3供應(yīng)量A11751952081500A21601822154000需求量35001100240047整理ppt運輸問題思考題1〔解〕：解根據(jù)題意以及給定的數(shù)據(jù)可知，這是一個產(chǎn)銷不平衡的運輸問題，需求量大于生產(chǎn)量。由于B1區(qū)供給量可減少0-900噸，B2區(qū)必須滿足需求量，B3區(qū)供給量不少于1600噸?？梢园袯1區(qū)和B3區(qū)分別設(shè)為兩個區(qū):一個為必須滿足需求量的區(qū)域，另一個為可以調(diào)整供給量的區(qū)域。這樣，原問題化為五個需求區(qū)域B1，B1’，B2，B3，B3’的問題，同時增加一個虛設(shè)的產(chǎn)地A3。在運輸費方面，取M代表一個很大的正數(shù)，使必須滿足需求量區(qū)域的相應(yīng)變量x31,x33,x34運費的取值為M，可調(diào)整需求量區(qū)域的相應(yīng)變量x32,x35運費的取值為0，作出產(chǎn)銷平衡的運價表48整理pptB1B1’B2B3B3’SupplyA11751751952082081500A21601601822152154000A3M0MM01500Demand16009001100160080049整理ppt運輸問題思考題2：

某運輸問題的產(chǎn)銷需求及單位運價如下表所示B1B2B3SupplyA159315A213418A382617Demand181216求解運輸費用最少的方案和總運費50整理ppt運輸問題思考題2〔解〕：因產(chǎn)銷不平衡，補充一虛擬銷售地B4如下：B1B2B3B4SupplyA1593015A2134018A3826017Demand1812164采用最小元素法可以得到初始可行解如下：B1B2B3B4SupplyA1593(11)0(4)15A21(18)34018A38(0)2(12)6(5)017Demand181216451整理ppt運輸問題思考題2〔解〕：計算檢驗數(shù)〔位勢法〕B1B2B3B4SupplyA1593(11)0(4)15A21(18)34018A38(0)2(12)6(5)017Demand1812164uivj108-6-25-5[0][10][8][5][4][-3]Theta=4,換元B1B2B3B4SupplyA1593