《運輸問題》課件

第三章運輸問題運輸問題的典例和數(shù)學模型表上作業(yè)法產銷不平衡的運輸問題應用舉例本章主要內容：4/7/20231精選PPT運輸問題的典例和數(shù)學模型

[例1]某食品公司從三個加工廠A1、A2、

A3將其生產的糖果運往四個門市部B1、B2、B3、B4銷售，各加工廠每天的生產量、各門市部每天的銷售量和各加工廠運往各門市部每噸糖果的運價如下表所示，問：該食品公司應如何調運可使總運輸費用最??？B1B2B3B4產量A13113107A219284A3741059銷量36564/7/20232精選PPT運輸問題的典例和數(shù)學模型解：產銷平衡問題：總產量=總銷量＝20設xij為從產地Ai運往銷地Bj的運輸量，得到下列運輸量表：MinZ=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24

+7x31+4x32+10x33+5x34

B1B2B3B4產量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,…,3；j=1,…,4）4/7/20233精選PPT運輸問題的典例和數(shù)學模型運輸問題的一般形式：產銷平衡A1、A2、…、Am表示某物資的m個產地；B1、B2、…、Bn表示某物資的n個銷地；ai表示產地Ai的產量；bj表示銷地Bj的銷量；cij表示把物資從產地Ai運往銷地Bj的單位運價。設xij為從產地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：4/7/20234精選PPT運輸問題的典例和數(shù)學模型變化：

1）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等；2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；3）產銷不平衡時，可加入假想的產地（銷大于產時）或銷地（產大于銷時）。定理:設有m個產地n個銷地且產銷平衡的運輸問題，則基變量數(shù)為m+n-1。4/7/20235精選PPT 學習要點： 1.掌握運輸問題模型結構；2.了解運輸問題模型特點。

運輸問題的典例和數(shù)學模型4/7/20236精選PPT表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。步驟描述方法第一步求初始基本可行解（初始調運方案）最小元素法、元素差額法、第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當非基變量的檢驗數(shù)σij全都非負時得到最優(yōu)解，若存在檢驗數(shù)σij<0，說明還沒有達到最優(yōu)，轉第三步。閉回路法和位勢法第三步調整運量，即換基，選一個變量出基，對原運量進行調整得到新的基可行解，轉入第二步4/7/20237精選PPT表上作業(yè)法例用表上作業(yè)法求解例1中的問題：單位銷地運價產地產量311310719284741059銷量3656問：應如何調運可使總運輸費用最小？4/7/20238精選PPT表上作業(yè)法解：第1步求初始方案方法1：最小元素法基本思想是就近供應，即從運價最小的地方開始供應（調運），然后次小，直到最后供完為止。B1B2B3B4產量A17A2

4A39銷量36563113101927410583416334/7/20239精選PPT表上作業(yè)法總的運輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差額法對最小元素法進行了改進，考慮到產地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調運，否則會增加總運費。例如下面兩種運輸方案。85102120151515510總運費是z=10×8+5×2+15×1=105最小元素法：4/7/202310精選PPT表上作業(yè)法85102120151551510總運費z=10×5+15×2+5×1=85后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調運x21，到后來就有可能x11≠0，這樣會使總運費增加較大，從而先調運x21，再是x22，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。4/7/202311精選PPT表上作業(yè)法方法2：Vogel法1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2B3B4產量行差額A177A2

41A391銷量3656列差額25133113101927410584/7/202312精選PPT表上作業(yè)法2）再從差值最大的行或列中找出最小運價確定供需關系和供需數(shù)量。當產地或銷地中有一方數(shù)量供應完畢或得到滿足時，劃去運價表中對應的行或列。重復1)和2)，直到找出初始解為至。B1B2B3B4產量行差額A170A2

41A3

91銷量3656列差額251331131019274105864/7/202313精選PPT表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額01135216××4/7/202314精選PPT表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額0213216××3××4/7/202315精選PPT表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額012216××3××3×4/7/202316精選PPT表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額71266××3××3×5×4/7/202317精選PPT表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額6××3××3×5×1×4/7/202318精選PPT表上作業(yè)法第2步最優(yōu)解的判別（檢驗數(shù)的求法）

求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為σij由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)求檢驗數(shù)的方法有兩種：閉回路法位勢法（▲）4/7/202319精選PPT表上作業(yè)法閉回路的概念為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表4/7/202320精選PPT表上作業(yè)法例下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉90度與另一頂點連接，表3－3中的變量x32及x33不是閉回路的頂點，只是連線的交點。4/7/202321精選PPT表上作業(yè)法閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組不能構成一條閉回路，但A中包含有閉回路

變量組變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；4/7/202322精選PPT表上作業(yè)法用位勢法對初始方案進行最優(yōu)性檢驗：1）由ij=Cij-（Ui+Vj）計算位勢Ui，Vj，因對基變量而言有ij=0，即Cij-（Ui+Vj）=0，令U1=02）再由ij=Cij-（Ui+Vj）計算非基變量的檢驗數(shù)ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029（1）（2）（1）（-1）（10）（12）當存在非基變量的檢驗數(shù)kl

≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。4/7/202323精選PPT表上作業(yè)法當存在非基變量的檢驗數(shù)kl<0且kl=min{ij}時，令Xkl進基。從表中知可選X24進基。第3步確定換入基的變量第4步確定換出基的變量以進基變量xik為起點的閉回路中，標有負號的最小運量作為調整量θ，θ對應的基變量為出基變量，并打上“×”以示換出作為非基變量。4/7/202324精選PPT表上作業(yè)法B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)調整步驟為：在進基變量的閉回路中標有正號的變量加上調整量θ，標有負號的變量減去調整量θ，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數(shù)重新檢驗。1254/7/202325精選PPT表上作業(yè)法當所有非基變量的檢驗數(shù)均非負時，則當前調運方案即為最優(yōu)方案，如表此時最小總運費：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039（0）（2）（2）（1）（12）（9）4/7/202326精選PPT表上作業(yè)法表上作業(yè)法的計算步驟：分析實際問題列出產銷平衡表及單位運價表確定初始調運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負檢驗數(shù)，用閉合回路調整，得到新的調運方案得到最優(yōu)方案，算出總運價4/7/202327精選PPT表上作業(yè)法表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取σij<0中最小者對應的變量為換入變量。（2）無窮多最優(yōu)解 產銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。4/7/202328精選PPT表上作業(yè)法（3）退化解：

※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進基變量的閉回路對解進行調整時，標有負號的最小運量（超過2個最小值）作為調整量θ，選擇任意一個最小運量對應的基變量作為出基變量，并打上“×”以示作為非基變量。4/7/202329精選PPT表上作業(yè)法銷地產地B1B2B3B4產量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經過調整，可得到另一個最優(yōu)解。4/7/202330精選PPT表上作業(yè)法銷地產地B1B2B3B4產量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解4/7/202331精選PPT表上作業(yè)法銷地產地B1B2B3B4產量A184124A2694725A3534326銷量10102015練習4/7/202332精選PPT 學習要點： 1.掌握表上作業(yè)法的基本原理；2.能熟練運用表上作業(yè)法求解；

3.理解表上作業(yè)法與單純形法的聯(lián)系。

作業(yè)：（P101）3.1表3-35表上作業(yè)法4/7/202333精選PPT產銷不平衡的運輸問題及其應用當總產量與總銷量不相等時，稱為不平衡運輸問題。這類運輸問題在實際中常常碰到，它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。當產大于銷時，即：數(shù)學模型為：4/7/202334精選PPT產銷不平衡的運輸問題及其應用由于總產量大于總銷量，必有部分產地的產量不能全部運送完，必須就地庫存，即每個產地設一個倉庫，假設該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設銷地Bn+1的銷量(即庫存量)。各產地Ai到Bn+1的運價為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可4/7/202335精選PPT產銷不平衡的運輸問題及其應用當銷大于產時，即：數(shù)學模型為：由于總銷量大于總產量，故一定有些需求地不完全滿足,這時虛設一個產地Am+1，產量為：4/7/202336精選PPT產銷不平衡的運輸問題及其應用銷大于產化為平衡問題的數(shù)學模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產量為am+1即可。4/7/202337精選PPT產銷不平衡的運輸問題及其應用例2求下列表中極小化運輸問題的最優(yōu)解。B1B2B3B4aiA1211347A2103595A378127bj23461915因為有：4/7/202338精選PPT產銷不平衡的運輸問題及其應用所以是一個產大于銷的運輸問題。虛設一個銷量為B5=19-15=4，Ci5=0，i=1,2,3，表的右邊增添一列，得到新的運價表。B