運(yùn)輸模型解析課件

第5章運(yùn)輸模型5.1運(yùn)輸問題及其數(shù)學(xué)模型5.2表上作業(yè)法5.2.1初始方案的確定5.2.2最優(yōu)性檢驗(yàn)5.2.3非最優(yōu)方案的調(diào)整5.2.4產(chǎn)銷不平衡問題的解法5.3運(yùn)輸模型的應(yīng)用第5章運(yùn)輸模型5.1運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸模型是線性規(guī)劃諸多模型中較早引起人們關(guān)注的一類模型，由美國學(xué)者希奇柯克（Hitchcock，1941）和庫普曼（Koopmans，1947）提出。中國——“圖上作業(yè)法”（1958年）1975年康托洛維奇和庫普曼因資源配置理論研究獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)（丹茨格）（24、12、4）（日內(nèi)瓦國際應(yīng)用系統(tǒng)分析研究所）運(yùn)輸模型是線性規(guī)劃諸多模型中較早引起人們關(guān)注的一類模型，由美運(yùn)輸模型是線性規(guī)劃諸多模型中的特例，其約束方程組對(duì)應(yīng)的系數(shù)矩陣具有特殊的結(jié)構(gòu)，使得有可能找到比單純形法更為簡(jiǎn)便的求解方式。運(yùn)輸問題的專門求解方法不僅適用于運(yùn)輸問題本身，還適用于其他相當(dāng)多的應(yīng)用問題（如指派問題），更使其得到人們的高度重視和深入的系統(tǒng)研究。運(yùn)輸模型是線性規(guī)劃諸多模型中的特例，其約束方程組對(duì)應(yīng)的系數(shù)矩

在經(jīng)濟(jì)建設(shè)中經(jīng)常會(huì)碰到大宗物資的調(diào)運(yùn)問題。如煤、鐵、木材、糧食等大宗物資，在全國有若干生產(chǎn)基地，根據(jù)現(xiàn)已有的交通網(wǎng)絡(luò)，應(yīng)該如何制定調(diào)運(yùn)方案，將這些物資運(yùn)往各消費(fèi)地點(diǎn)。1）“產(chǎn)地”——貨物發(fā)出的地點(diǎn)2）“銷地”——貨物接收的地點(diǎn)3）“產(chǎn)量”——各產(chǎn)地的可供貨量4）“銷量”——各銷地的需求數(shù)量在經(jīng)濟(jì)建設(shè)中經(jīng)常會(huì)碰到大宗物資的調(diào)運(yùn)問題。如【運(yùn)輸問題的描述】運(yùn)輸問題就是研究如何組織調(diào)運(yùn)，在滿足各銷地需求的前提下，追求總的運(yùn)費(fèi)（或里程、時(shí)間等）達(dá)到最少？運(yùn)輸問題所建立的模型就稱為運(yùn)輸模型。【運(yùn)輸問題的描述】5.1運(yùn)輸問題及其數(shù)學(xué)模型【例1】某飲料集團(tuán)在國內(nèi)有3個(gè)生產(chǎn)工廠，分布在城市

A1，A2，A3；其一級(jí)分銷商有4個(gè)，分布在城市B1，B2，B3，

B4?，F(xiàn)已知每月各生產(chǎn)工廠的產(chǎn)量、各分銷商的需求量；以及從Ai到Bj的每噸飲料的運(yùn)費(fèi)cij（見下表）。5.1運(yùn)輸問題及其數(shù)學(xué)模型

銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量2314為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司需要統(tǒng)一籌劃運(yùn)銷問題，求使運(yùn)費(fèi)最小的調(diào)運(yùn)方案。銷地B1B2B3B4產(chǎn)量A163255A275842解：建立該運(yùn)輸問題的LP模型如下解：建立該運(yùn)輸問題的LP模型如下運(yùn)輸模型解析課件運(yùn)輸問題的一般提法：

設(shè)某種物資有m個(gè)產(chǎn)地，其產(chǎn)量分別為；有n個(gè)銷地，其銷量分別為；從到的單位運(yùn)價(jià)為。問應(yīng)該如何組織調(diào)運(yùn)才能使總的運(yùn)費(fèi)最少？運(yùn)輸問題的一般提法：設(shè)

為把這種物資從Ai運(yùn)到Bj的數(shù)量，簡(jiǎn)稱為Ai至Bj的運(yùn)量；設(shè)z為總運(yùn)費(fèi)，則一般運(yùn)輸問題及其數(shù)學(xué)模型可以簡(jiǎn)潔地表示為下表這種形式，稱為表格形式的一般運(yùn)輸模型，簡(jiǎn)稱表式運(yùn)輸模型。p136設(shè)為把這種物資從Ai運(yùn)到Bj的數(shù)量，簡(jiǎn)稱p136表式運(yùn)輸模型

銷地產(chǎn)地A1A2…Am產(chǎn)量a1a2…amB1B2…Bn銷量b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn表式運(yùn)輸模型銷地A1A2…Am產(chǎn)量a1a2…amB產(chǎn)銷平衡產(chǎn)銷平衡產(chǎn)大于銷產(chǎn)大于銷產(chǎn)小于銷產(chǎn)小于銷【運(yùn)輸模型系數(shù)矩陣】m行n行【運(yùn)輸模型系數(shù)矩陣】mn【討論】運(yùn)輸模型系數(shù)矩陣的特征？[表面]任意一個(gè)運(yùn)輸模型系數(shù)矩陣同一個(gè)與之規(guī)模相當(dāng)?shù)钠胀↙P模型的系數(shù)矩陣相比都大為簡(jiǎn)潔，且其中只含有0和1這兩個(gè)元素，且0的個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于1的個(gè)數(shù)，一般我們把這樣的矩陣稱為稀疏陣。[深層次]對(duì)任意產(chǎn)銷平衡的運(yùn)輸模型來說，其系數(shù)陣的前m行之和等于后n行之和。意味著？【討論】運(yùn)輸模型系數(shù)矩陣的特征？意味著？可以證明：平衡模型的系數(shù)陣和增廣陣的秩均為m+n-1，這也意味著平衡模型的基本可行解所含基變量的個(gè)數(shù)必為m+n-1個(gè)?！窘Y(jié)論】m+n-1可以證明：平衡模型的系數(shù)陣和增廣陣的秩均為m+n-1，這也意【討論】上述運(yùn)輸問題所建立的LP模型如果用傳統(tǒng)的單純形法進(jìn)行求解會(huì)出現(xiàn)什么情況？【友情提示】1）表上作業(yè)法僅僅適用于產(chǎn)銷平衡的運(yùn)輸問題

2）表上作業(yè)法基于一種作業(yè)表——“產(chǎn)銷平衡及運(yùn)價(jià)表”特征？5.2表上作業(yè)法【討論】上述運(yùn)輸問題所建立的LP模型如果用傳統(tǒng)的特征？5.2用單純形法求解LP式運(yùn)輸模型，必須刪掉一個(gè)函數(shù)約束，而且計(jì)算量很大，但表上作業(yè)法不必如此費(fèi)力，而是另辟蹊徑。表上作業(yè)法是一種專門求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)仍是單純形法，只是具體計(jì)算和術(shù)語有所區(qū)別。與一般的LP問題不同的是，平衡運(yùn)輸問題總是存在最優(yōu)解。用單純形法求解LP式運(yùn)輸模型，必須刪掉一個(gè)函數(shù)約束，而且計(jì)算

銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410銷地B1B2B3B4產(chǎn)量A163255A275842■表上作業(yè)法的基本思想及基本步驟【基本思想】類似于單純形法，只是叫法不同而已，如基本

可行解稱為“方案”；迭代稱為“調(diào)整改進(jìn)”等?！净静襟E】1）確定初始方案；

2）對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)；

3）調(diào)整、改進(jìn)非最優(yōu)方案；

4）直至得到最優(yōu)方案（惟一方案或多重方案）■表上作業(yè)法的基本思想及基本步驟【基本思想】類似于單純形法運(yùn)輸問題求解思路確定初始方案（初始基本可行解）

輸出最優(yōu)方案改進(jìn)調(diào)整（換基迭代）判斷是否最優(yōu)結(jié)果是否確定初始方案輸出最優(yōu)方案改進(jìn)調(diào)整判斷是否最優(yōu)結(jié)果是否5.2.1初始方案的確定

確定初始方案的方法有很多，原理各不相同——左上角法（西北角法、階梯法）最小元素法最大差額法Russell概算法5.2.1初始方案的確定確定初始方案的方法有很多，原理各銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410②左上角法銷地B1B2B3B4產(chǎn)量A163255A275842A332最小元素指？最小元素法的基本思想？？最小元素法“最小運(yùn)價(jià)”“就近運(yùn)給”最小元素指？最小元素法的基本思想？？最小元素法“最小運(yùn)價(jià)”“先給作業(yè)表中最小運(yùn)價(jià)那格安排運(yùn)量，然后劃去該運(yùn)價(jià)所在的行或列；繼續(xù)這樣做，每次總在表中剩余運(yùn)價(jià)的最小元素那格確定運(yùn)量，直至求出初始方案為止。先給作業(yè)表中最小運(yùn)價(jià)那格安排運(yùn)量，然后劃去該運(yùn)價(jià)所在的行或列銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410①③(0)②②②初始方案：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=38銷地B1B2B3B4產(chǎn)量A163255A275842A332【結(jié)論】最小元素法確定初始方案的4條原則運(yùn)量選擇時(shí)必須遵循產(chǎn)、銷量比較取其小的原則確定某格的運(yùn)量后，其所在行或列其余格運(yùn)量為0，并劃去滿足約束的行或列，同時(shí)滿足只能劃去其中之一中間遇到0運(yùn)量也必須畫上最后一個(gè)格產(chǎn)地、銷地同時(shí)滿足，同時(shí)劃去【結(jié)論】最小元素法確定初始方案的4條原則運(yùn)量選擇時(shí)必須遵循產(chǎn)最小元素法確定的有效的初始方案滿足——初始作業(yè)表中有m+n-1

個(gè)畫圈數(shù)字（運(yùn)量）畫圈數(shù)字（運(yùn)量）恰好符合產(chǎn)銷平衡運(yùn)輸問題的約束條件作業(yè)表中不存在以畫圈數(shù)字為頂點(diǎn)的閉回路【閉回路】從表中任一畫圈數(shù)字所在格出發(fā)，沿水平或垂直方向前進(jìn)，當(dāng)碰到另一個(gè)畫圈數(shù)字后，可沿原方向繼續(xù)前進(jìn)，也可以轉(zhuǎn)90°繼續(xù)前進(jìn)，如此進(jìn)行下去最終回到出發(fā)點(diǎn)。注意：用最小元素法得到的初始方案肯定不會(huì)形成閉回路！??！最小元素法確定的有效的初始方案滿足——初始作業(yè)表中有m+銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410①②①①③②銷地B1B2B3B4產(chǎn)量A163255A275842A332B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43B1B2B3B4B5A1X11X12A2X23X25A3X3最大差額法“差額”——行差和列差“最大差額”——兩最小元素之差（正值）不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)差額越大，說明當(dāng)不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加的越多最大差額法5.2.2最優(yōu)性檢驗(yàn)確定初始方案后，就要對(duì)它進(jìn)行最優(yōu)性檢驗(yàn)，即檢驗(yàn)初始基本可行解對(duì)應(yīng)的目標(biāo)函數(shù)值是否達(dá)到最優(yōu)。運(yùn)輸問題要求目標(biāo)函數(shù)求最小值，故當(dāng)檢驗(yàn)數(shù)時(shí)，表示該方案為最優(yōu)。計(jì)算檢驗(yàn)數(shù)的方法有——A位勢(shì)法B閉回路法5.2.2最優(yōu)性檢驗(yàn)1、位勢(shì)法A兩個(gè)位勢(shì)量：產(chǎn)地的位勢(shì)量；銷地的位勢(shì)量B兩個(gè)基本公式：1）該公式僅僅適用于基變量所在格（基格）2）決策變量的檢驗(yàn)數(shù)計(jì)算公式：1、位勢(shì)法銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA162

321

52

50A2758422-1A330

23

973-3銷量2314vj6525-2217105非基變量x12的檢驗(yàn)數(shù)12=c12–u1–v2=-2，即讓非基變量x12從0增到1，可使總運(yùn)費(fèi)減少2百元。銷地B1B2B3B4產(chǎn)量uiA1632550A275842-2、閉回路法這里的閉回路是指以非基變量的格子為始點(diǎn)和終點(diǎn)，而其余頂點(diǎn)均為畫圈數(shù)字（基變量）的一條封閉回路，用水平或者垂直線向前畫，每碰到一數(shù)字格轉(zhuǎn)90度后繼續(xù)前進(jìn)，直到回到始點(diǎn)。偶點(diǎn)（+）奇點(diǎn)（-）結(jié)論1：閉回路都是唯一的。結(jié)論2：任一非基變量的檢驗(yàn)數(shù)都等于它的閉回路上所有偶點(diǎn)運(yùn)價(jià)的總和與所有奇點(diǎn)的運(yùn)價(jià)總和之差。2、閉回路法5.2.3非最優(yōu)方案的調(diào)整當(dāng)作業(yè)表中出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明此方案仍不是最優(yōu)方案，需要進(jìn)行調(diào)整，調(diào)整時(shí)仍用閉回路法。5.2.3非最優(yōu)方案的調(diào)整（1）進(jìn)基變量的確定若同時(shí)有多個(gè)負(fù)檢驗(yàn)數(shù)一樣最小，則選其中最小運(yùn)價(jià)所對(duì)應(yīng)的那個(gè)進(jìn)基。（2）離基變量的確定在進(jìn)基變量的閉回路上，按確定離基變量，同時(shí)也確定了調(diào)整量t。若有多個(gè)奇點(diǎn)的運(yùn)量值一樣，則選其中最大運(yùn)價(jià)所對(duì)應(yīng)的那個(gè)離基。（3）非最優(yōu)方案的調(diào)整所有偶點(diǎn)的運(yùn)量+t所有奇點(diǎn)的運(yùn)量-t（1）進(jìn)基變量的確定x12進(jìn)基最小調(diào)整量為2，即t=2，x11離基銷地產(chǎn)地B1B2B3B4產(chǎn)量A1623x1221525A2758422A33023973銷量2314+-+-x12進(jìn)基銷地B1B2B3B4產(chǎn)量A163255A27銷地產(chǎn)地B1B2B3B4產(chǎn)量A16

321525A2758422A33

2

973銷量2314

調(diào)整后新方案：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=34

221銷地B1B2B3B4產(chǎn)量A163255A275842A3定理1(惟一最優(yōu)解的判定定理)

如果在表上作業(yè)法得到的最終表中,非基變量的檢驗(yàn)數(shù)全都大于零,則該運(yùn)輸問題存在惟一最優(yōu)解。

定理2(多重最優(yōu)解的判定定理)對(duì)于一個(gè)運(yùn)輸問題,在得到的第一個(gè)最優(yōu)解的最終表中,若至少存在一個(gè)檢驗(yàn)數(shù)為零的非基變量,并且在以這個(gè)非基變量為出發(fā)點(diǎn)的閉回路上,在需要減少運(yùn)輸量的頂點(diǎn)中,最小運(yùn)量不等于零,那么該運(yùn)輸問題存在多重最優(yōu)解。

運(yùn)輸問題的多重解定理1(惟一最優(yōu)解的判定定理)

如果在表上作業(yè)法得到的最終表運(yùn)輸問題多重解B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656

運(yùn)輸問題多重解B1B2B3B4產(chǎn)量A13113107A2195.2.4產(chǎn)銷不平衡問題的解法A產(chǎn)大于銷

虛設(shè)銷地（經(jīng)濟(jì)意義：貯存）B產(chǎn)小于銷

虛設(shè)產(chǎn)地（經(jīng)濟(jì)意義：脫銷）5.2.4產(chǎn)銷不平衡問題的解法虛設(shè)的產(chǎn)地的產(chǎn)量或銷地的銷量等于產(chǎn)銷量之差的絕對(duì)值，且其運(yùn)價(jià)全部為0。用最小元素法確定初始方案時(shí)，盡管虛設(shè)產(chǎn)地或銷地對(duì)應(yīng)的運(yùn)價(jià)為0，均為最小，但我們先不考慮它，先給有實(shí)際運(yùn)輸任務(wù)的其他產(chǎn)銷地之間安排運(yùn)量，這樣處理往往能獲得較好的初始方案，減少調(diào)整的次數(shù)（為什么？）。虛設(shè)的產(chǎn)地的產(chǎn)量或銷地的銷量等于產(chǎn)銷量之差的絕對(duì)值，且其運(yùn)價(jià)5.3運(yùn)輸模型的應(yīng)用短缺資源的分配問題轉(zhuǎn)運(yùn)問題生產(chǎn)調(diào)度問題（***）5.3運(yùn)輸模型的應(yīng)用這里所說的生產(chǎn)調(diào)度問題是指對(duì)某產(chǎn)品在一個(gè)總的計(jì)劃周期內(nèi)的某項(xiàng)既定總生產(chǎn)指標(biāo)（總產(chǎn)量），應(yīng)怎樣分解到各個(gè)生產(chǎn)周期，才能既保證在總計(jì)劃期內(nèi)完成該項(xiàng)總生產(chǎn)指標(biāo)，又能使總生產(chǎn)費(fèi)用最少。這里所說的生產(chǎn)調(diào)度問題是指對(duì)某產(chǎn)品在一個(gè)總的計(jì)劃周期內(nèi)的某項(xiàng)[案例]拖拉機(jī)生產(chǎn)調(diào)度問題前進(jìn)拖拉機(jī)廠與農(nóng)機(jī)供銷站簽訂了一項(xiàng)生產(chǎn)100臺(tái)某種小型拖拉機(jī)的合同。按合同規(guī)定，該廠要在今后4個(gè)月的每月內(nèi)各交付一定臺(tái)數(shù)的拖拉機(jī)。為此，該廠生產(chǎn)計(jì)劃科根據(jù)本廠實(shí)際情況列出了一個(gè)生產(chǎn)調(diào)度數(shù)據(jù)表。根據(jù)此表第二欄（生產(chǎn)能力）的數(shù)據(jù)，該廠能夠提前完成合同總數(shù)，但生產(chǎn)出來的拖拉機(jī)若當(dāng)月不交貨，每臺(tái)存儲(chǔ)一個(gè)月，由于維修保養(yǎng)和積壓資金等緣故，另需費(fèi)用100元，問該廠應(yīng)如何擬訂最經(jīng)濟(jì)的生產(chǎn)進(jìn)度？[案例]拖拉機(jī)生產(chǎn)調(diào)度問題月份合同規(guī)定交付臺(tái)數(shù)/臺(tái)生產(chǎn)能力/臺(tái)單臺(tái)成本/元115305000225355200335455100425205300合計(jì)100130月份合同規(guī)定生產(chǎn)能力/臺(tái)單臺(tái)成本/元11530500022512345/虛產(chǎn)量1505152530302M5253540353MM51520454MMM53020銷量152535253012345/虛產(chǎn)量1505152530302M5253540第5章運(yùn)輸模型5.1運(yùn)輸問題及其數(shù)學(xué)模型5.2表上作業(yè)法5.2.1初始方案的確定5.2.2最優(yōu)性檢驗(yàn)5.2.3非最優(yōu)方案的調(diào)整5.2.4產(chǎn)銷不平衡問題的解法5.3運(yùn)輸模型的應(yīng)用第5章運(yùn)輸模型5.1運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸模型是線性規(guī)劃諸多模型中較早引起人們關(guān)注的一類模型，由美國學(xué)者希奇柯克（Hitchcock，1941）和庫普曼（Koopmans，1947）提出。中國——“圖上作業(yè)法”（1958年）1975年康托洛維奇和庫普曼因資源配置理論研究獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)（丹茨格）（24、12、4）（日內(nèi)瓦國際應(yīng)用系統(tǒng)分析研究所）運(yùn)輸模型是線性規(guī)劃諸多模型中較早引起人們關(guān)注的一類模型，由美運(yùn)輸模型是線性規(guī)劃諸多模型中的特例，其約束方程組對(duì)應(yīng)的系數(shù)矩陣具有特殊的結(jié)構(gòu)，使得有可能找到比單純形法更為簡(jiǎn)便的求解方式。運(yùn)輸問題的專門求解方法不僅適用于運(yùn)輸問題本身，還適用于其他相當(dāng)多的應(yīng)用問題（如指派問題），更使其得到人們的高度重視和深入的系統(tǒng)研究。運(yùn)輸模型是線性規(guī)劃諸多模型中的特例，其約束方程組對(duì)應(yīng)的系數(shù)矩

在經(jīng)濟(jì)建設(shè)中經(jīng)常會(huì)碰到大宗物資的調(diào)運(yùn)問題。如煤、鐵、木材、糧食等大宗物資，在全國有若干生產(chǎn)基地，根據(jù)現(xiàn)已有的交通網(wǎng)絡(luò)，應(yīng)該如何制定調(diào)運(yùn)方案，將這些物資運(yùn)往各消費(fèi)地點(diǎn)。1）“產(chǎn)地”——貨物發(fā)出的地點(diǎn)2）“銷地”——貨物接收的地點(diǎn)3）“產(chǎn)量”——各產(chǎn)地的可供貨量4）“銷量”——各銷地的需求數(shù)量在經(jīng)濟(jì)建設(shè)中經(jīng)常會(huì)碰到大宗物資的調(diào)運(yùn)問題。如【運(yùn)輸問題的描述】運(yùn)輸問題就是研究如何組織調(diào)運(yùn)，在滿足各銷地需求的前提下，追求總的運(yùn)費(fèi)（或里程、時(shí)間等）達(dá)到最少？運(yùn)輸問題所建立的模型就稱為運(yùn)輸模型?！具\(yùn)輸問題的描述】5.1運(yùn)輸問題及其數(shù)學(xué)模型【例1】某飲料集團(tuán)在國內(nèi)有3個(gè)生產(chǎn)工廠，分布在城市

A1，A2，A3；其一級(jí)分銷商有4個(gè)，分布在城市B1，B2，B3，

B4?，F(xiàn)已知每月各生產(chǎn)工廠的產(chǎn)量、各分銷商的需求量；以及從Ai到Bj的每噸飲料的運(yùn)費(fèi)cij（見下表）。5.1運(yùn)輸問題及其數(shù)學(xué)模型

銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量2314為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司需要統(tǒng)一籌劃運(yùn)銷問題，求使運(yùn)費(fèi)最小的調(diào)運(yùn)方案。銷地B1B2B3B4產(chǎn)量A163255A275842解：建立該運(yùn)輸問題的LP模型如下解：建立該運(yùn)輸問題的LP模型如下運(yùn)輸模型解析課件運(yùn)輸問題的一般提法：

設(shè)某種物資有m個(gè)產(chǎn)地，其產(chǎn)量分別為；有n個(gè)銷地，其銷量分別為；從到的單位運(yùn)價(jià)為。問應(yīng)該如何組織調(diào)運(yùn)才能使總的運(yùn)費(fèi)最少？運(yùn)輸問題的一般提法：設(shè)

為把這種物資從Ai運(yùn)到Bj的數(shù)量，簡(jiǎn)稱為Ai至Bj的運(yùn)量；設(shè)z為總運(yùn)費(fèi)，則一般運(yùn)輸問題及其數(shù)學(xué)模型可以簡(jiǎn)潔地表示為下表這種形式，稱為表格形式的一般運(yùn)輸模型，簡(jiǎn)稱表式運(yùn)輸模型。p136設(shè)為把這種物資從Ai運(yùn)到Bj的數(shù)量，簡(jiǎn)稱p136表式運(yùn)輸模型

銷地產(chǎn)地A1A2…Am產(chǎn)量a1a2…amB1B2…Bn銷量b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn表式運(yùn)輸模型銷地A1A2…Am產(chǎn)量a1a2…amB產(chǎn)銷平衡產(chǎn)銷平衡產(chǎn)大于銷產(chǎn)大于銷產(chǎn)小于銷產(chǎn)小于銷【運(yùn)輸模型系數(shù)矩陣】m行n行【運(yùn)輸模型系數(shù)矩陣】mn【討論】運(yùn)輸模型系數(shù)矩陣的特征？[表面]任意一個(gè)運(yùn)輸模型系數(shù)矩陣同一個(gè)與之規(guī)模相當(dāng)?shù)钠胀↙P模型的系數(shù)矩陣相比都大為簡(jiǎn)潔，且其中只含有0和1這兩個(gè)元素，且0的個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于1的個(gè)數(shù)，一般我們把這樣的矩陣稱為稀疏陣。[深層次]對(duì)任意產(chǎn)銷平衡的運(yùn)輸模型來說，其系數(shù)陣的前m行之和等于后n行之和。意味著？【討論】運(yùn)輸模型系數(shù)矩陣的特征？意味著？可以證明：平衡模型的系數(shù)陣和增廣陣的秩均為m+n-1，這也意味著平衡模型的基本可行解所含基變量的個(gè)數(shù)必為m+n-1個(gè)。【結(jié)論】m+n-1可以證明：平衡模型的系數(shù)陣和增廣陣的秩均為m+n-1，這也意【討論】上述運(yùn)輸問題所建立的LP模型如果用傳統(tǒng)的單純形法進(jìn)行求解會(huì)出現(xiàn)什么情況？【友情提示】1）表上作業(yè)法僅僅適用于產(chǎn)銷平衡的運(yùn)輸問題

2）表上作業(yè)法基于一種作業(yè)表——“產(chǎn)銷平衡及運(yùn)價(jià)表”特征？5.2表上作業(yè)法【討論】上述運(yùn)輸問題所建立的LP模型如果用傳統(tǒng)的特征？5.2用單純形法求解LP式運(yùn)輸模型，必須刪掉一個(gè)函數(shù)約束，而且計(jì)算量很大，但表上作業(yè)法不必如此費(fèi)力，而是另辟蹊徑。表上作業(yè)法是一種專門求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)仍是單純形法，只是具體計(jì)算和術(shù)語有所區(qū)別。與一般的LP問題不同的是，平衡運(yùn)輸問題總是存在最優(yōu)解。用單純形法求解LP式運(yùn)輸模型，必須刪掉一個(gè)函數(shù)約束，而且計(jì)算

銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410銷地B1B2B3B4產(chǎn)量A163255A275842■表上作業(yè)法的基本思想及基本步驟【基本思想】類似于單純形法，只是叫法不同而已，如基本

可行解稱為“方案”；迭代稱為“調(diào)整改進(jìn)”等?！净静襟E】1）確定初始方案；

2）對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)；

3）調(diào)整、改進(jìn)非最優(yōu)方案；

4）直至得到最優(yōu)方案（惟一方案或多重方案）■表上作業(yè)法的基本思想及基本步驟【基本思想】類似于單純形法運(yùn)輸問題求解思路確定初始方案（初始基本可行解）

輸出最優(yōu)方案改進(jìn)調(diào)整（換基迭代）判斷是否最優(yōu)結(jié)果是否確定初始方案輸出最優(yōu)方案改進(jìn)調(diào)整判斷是否最優(yōu)結(jié)果是否5.2.1初始方案的確定

確定初始方案的方法有很多，原理各不相同——左上角法（西北角法、階梯法）最小元素法最大差額法Russell概算法5.2.1初始方案的確定確定初始方案的方法有很多，原理各銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410②左上角法銷地B1B2B3B4產(chǎn)量A163255A275842A332最小元素指？最小元素法的基本思想？？最小元素法“最小運(yùn)價(jià)”“就近運(yùn)給”最小元素指？最小元素法的基本思想？？最小元素法“最小運(yùn)價(jià)”“先給作業(yè)表中最小運(yùn)價(jià)那格安排運(yùn)量，然后劃去該運(yùn)價(jià)所在的行或列；繼續(xù)這樣做，每次總在表中剩余運(yùn)價(jià)的最小元素那格確定運(yùn)量，直至求出初始方案為止。先給作業(yè)表中最小運(yùn)價(jià)那格安排運(yùn)量，然后劃去該運(yùn)價(jià)所在的行或列銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410①③(0)②②②初始方案：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=38銷地B1B2B3B4產(chǎn)量A163255A275842A332【結(jié)論】最小元素法確定初始方案的4條原則運(yùn)量選擇時(shí)必須遵循產(chǎn)、銷量比較取其小的原則確定某格的運(yùn)量后，其所在行或列其余格運(yùn)量為0，并劃去滿足約束的行或列，同時(shí)滿足只能劃去其中之一中間遇到0運(yùn)量也必須畫上最后一個(gè)格產(chǎn)地、銷地同時(shí)滿足，同時(shí)劃去【結(jié)論】最小元素法確定初始方案的4條原則運(yùn)量選擇時(shí)必須遵循產(chǎn)最小元素法確定的有效的初始方案滿足——初始作業(yè)表中有m+n-1

個(gè)畫圈數(shù)字（運(yùn)量）畫圈數(shù)字（運(yùn)量）恰好符合產(chǎn)銷平衡運(yùn)輸問題的約束條件作業(yè)表中不存在以畫圈數(shù)字為頂點(diǎn)的閉回路【閉回路】從表中任一畫圈數(shù)字所在格出發(fā)，沿水平或垂直方向前進(jìn)，當(dāng)碰到另一個(gè)畫圈數(shù)字后，可沿原方向繼續(xù)前進(jìn)，也可以轉(zhuǎn)90°繼續(xù)前進(jìn)，如此進(jìn)行下去最終回到出發(fā)點(diǎn)。注意：用最小元素法得到的初始方案肯定不會(huì)形成閉回路?。?！最小元素法確定的有效的初始方案滿足——初始作業(yè)表中有m+銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量231410①②①①③②銷地B1B2B3B4產(chǎn)量A163255A275842A332B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43B1B2B3B4B5A1X11X12A2X23X25A3X3最大差額法“差額”——行差和列差“最大差額”——兩最小元素之差（正值）不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)差額越大，說明當(dāng)不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加的越多最大差額法5.2.2最優(yōu)性檢驗(yàn)確定初始方案后，就要對(duì)它進(jìn)行最優(yōu)性檢驗(yàn)，即檢驗(yàn)初始基本可行解對(duì)應(yīng)的目標(biāo)函數(shù)值是否達(dá)到最優(yōu)。運(yùn)輸問題要求目標(biāo)函數(shù)求最小值，故當(dāng)檢驗(yàn)數(shù)時(shí)，表示該方案為最優(yōu)。計(jì)算檢驗(yàn)數(shù)的方法有——A位勢(shì)法B閉回路法5.2.2最優(yōu)性檢驗(yàn)1、位勢(shì)法A兩個(gè)位勢(shì)量：產(chǎn)地的位勢(shì)量；銷地的位勢(shì)量B兩個(gè)基本公式：1）該公式僅僅適用于基變量所在格（基格）2）決策變量的檢驗(yàn)數(shù)計(jì)算公式：1、位勢(shì)法銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA162

321

52

50A2758422-1A330

23

973-3銷量2314vj6525-2217105非基變量x12的檢驗(yàn)數(shù)12=c12–u1–v2=-2，即讓非基變量x12從0增到1，可使總運(yùn)費(fèi)減少2百元。銷地B1B2B3B4產(chǎn)量uiA1632550A275842-2、閉回路法這里的閉回路是指以非基變量的格子為始點(diǎn)和終點(diǎn)，而其余頂點(diǎn)均為畫圈數(shù)字（基變量）的一條封閉回路，用水平或者垂直線向前畫，每碰到一數(shù)字格轉(zhuǎn)90度后繼續(xù)前進(jìn)，直到回到始點(diǎn)。偶點(diǎn)（+）奇點(diǎn)（-）結(jié)論1：閉回路都是唯一的。結(jié)論2：任一非基變量的檢驗(yàn)數(shù)都等于它的閉回路上所有偶點(diǎn)運(yùn)價(jià)的總和與所有奇點(diǎn)的運(yùn)價(jià)總和之差。2、閉回路法5.2.3非最優(yōu)方案的調(diào)整當(dāng)作業(yè)表中出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明此方案仍不是最優(yōu)方案，需要進(jìn)行調(diào)整，調(diào)整時(shí)仍用閉回路法。5.2.3非最優(yōu)方案的調(diào)整（1）進(jìn)基變量的確定若同時(shí)有多個(gè)負(fù)檢驗(yàn)數(shù)一樣最小，則選其中最小運(yùn)價(jià)所對(duì)應(yīng)的那個(gè)進(jìn)基。（2）離基變量的確定在進(jìn)基變量的閉回路上，按確定離基變量，同時(shí)也確定了調(diào)整量t。若有多個(gè)奇點(diǎn)的運(yùn)量值一樣，則選其中最大運(yùn)價(jià)所對(duì)應(yīng)的那個(gè)離基。（3）非最優(yōu)方案的調(diào)整所有偶點(diǎn)的運(yùn)量+t所有奇點(diǎn)的運(yùn)量-t（1）進(jìn)基變量的確定x12進(jìn)基最小調(diào)整量為2，即t=2，x11離基銷地產(chǎn)地B1B2B3B4產(chǎn)量A1623x1221525A2758422A33023973銷量2314+-+-x12進(jìn)基銷地B1B2B3B4產(chǎn)量A163255A27銷地產(chǎn)地B1B2B3B4產(chǎn)量A16

321525A2758422A33

2

973銷量2314

調(diào)整后新方案：x12=2,x13=1,x14