運籌學課件 第三章運輸問題

第三章運輸問題2/7/20231例、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最?。拷猓寒a(chǎn)銷平衡問題：總產(chǎn)量=總銷量設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）一運輸問題及其數(shù)學模型2/7/20232一般運輸模型：產(chǎn)銷平衡A1、A2、…、Am表示某物資的m個產(chǎn)地；B1、B2、…、Bn表示某物質的n個銷地；si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：mnMinf=cijxiji=1j=1n

s.t.

xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)2/7/20233二、運輸問題的表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。運輸問題都存在最優(yōu)解。計算過程（假設產(chǎn)銷平衡）：1.找出初始基本可行解。對于有m個產(chǎn)地n個銷地的產(chǎn)銷平衡問題，則有m個關于產(chǎn)量的約束方程和n個關于銷量的約束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個獨立的約束方程，即運輸問題有m+n-1個基變量。在m×n的產(chǎn)銷平衡表上給出m+n-1個數(shù)字格，其相對應的調運量的值即為基變量的值。2.求各非基變量的檢驗數(shù)，即檢驗除了上述m+n-1個基變量以外的空格的檢驗數(shù)判別是否達到最優(yōu)解，如果已是最優(yōu)，停止計算，否則轉到下一步。3.確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調整。4.重復2、3直到得到最優(yōu)解。2/7/20234三、初始基本可行解的確定1、最低費用法最低費用法是就近供應，即對單位運價最小的變量分配運輸量。2/7/202352、運費差額法初看起來，最小元素法十分合理。但是，有時按某一最小單位運價優(yōu)先安排物品調運時，卻可能導致其他的地方多花幾倍的費用，從而使整個運輸費用增加。對每一個供應地或銷售地，均可由它到各銷售地或到各供應地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為該供應地或銷售地的罰數(shù)。若罰數(shù)的值不大，當不能按最小單位運價安排運輸時造成的運費損失不大，2/7/20236反之，如果罰數(shù)的值很大，則不按最小運價組織運輸就會造成很大損失。故應盡量按最小單位運價安排運輸。運費差額法就是基于這種考慮提出來的。運費差額法的計算方法和步驟：

2/7/20237例、2/7/20238四、最優(yōu)解的判別運用運費差額法，得到上例的初始基本可行解如下：

2/7/20239現(xiàn)用位勢法求這個解各非基變量的檢驗數(shù)。由于所有非基變量的檢驗數(shù)全非負，故這個解為最優(yōu)解。對這個解來說，因若以為換入變量可再得一解，它與上面最優(yōu)解的目標函數(shù)值相等，故它也是一個最優(yōu)解，即該運輸問題有無窮多最優(yōu)解。五、需要說明的幾個問題1、若運輸問題的某一基可行解有幾個非基變量的檢驗數(shù)均為負。在繼續(xù)進行迭代時，取它們中的任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取中最小者對應的變量為換入變量。2/7/2023102、當?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重（無窮多）最優(yōu)解。3、當運輸問題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運量時需同時劃去運輸表的一行和一列，這時就出現(xiàn)了退化。在運輸問題中，退化解是時常發(fā)生的。為了使表上作業(yè)法的迭代工作進行下去，退化時應在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格中的變量是取值為0的基變量，使迭代過程中基可行解的分量恰好為m+n-1個。2/7/202311例：某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由3個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均為噸）各工廠到各銷售點的單位運價（元/噸）示于下表中。要求研究產(chǎn)品如何調運才能使總運費最小。2/7/202312運用最小元素法，得到上例的初始基本可行解如下：2/7/202313

運用運費差額法，得到上例的初始基本可行解如下：2/7/202314例：某企業(yè)有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均為噸）各工廠到各銷售點的單位運價（元/噸）示于下表中。要求研究產(chǎn)品如何調運才能使總運費最小。2/7/202315運用最小元素法，得到上例的初始基本可行解如下：對初始基本可行解進行最優(yōu)判斷

2/7/202316五、解的改進對運輸問題的一個解來說，若最優(yōu)性檢驗時某非基變量的檢驗數(shù)為負，說明將這個非基變量變?yōu)榛兞繒r運費會更小。因而這個解不是最優(yōu)解，還可以進一步改進。改進的方法是在運輸表中找出這個空格對應的閉回路，在滿足所有約束條件的前提下，使盡量增大并相應調整此閉回路上其它頂點的運輸量，以得到另一個更好的基可行解。1、閉回路的確定方法2/7/202317首先選取某檢驗數(shù)為負數(shù)的空格為調入格，即以它對應的非基變量為入基變量。從調入格出發(fā)找一條閉回路，閉回路的確定方法為:以調入格為起點，用水平或垂直線向前劃，遇到適當數(shù)字格則轉90。后繼續(xù)前進，直到回到起始空格為止。2/7/2023182、解的改進解改進的具體步驟為：（1）以為換入變量，找出它在運輸表中的閉回路；

（2）以空格為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回路上的頂點依次編號；

（3）在閉回路上的所有偶數(shù)頂點中，找出運輸量最小的頂點（格子），以該格中的變量為換出變量；2/7/202319（4）以為調整量，將該閉回路上所有奇數(shù)頂點處的運輸量都增加這一數(shù)值，所有偶數(shù)頂點處的運輸量都減去這一數(shù)值，從而得出一新的運輸方案，該運輸方案的總運費比原運輸方案減少，改變量等于然后，再對得到的新解進行最優(yōu)性檢驗，如不是最優(yōu)解，就重復以上步驟繼續(xù)進行調整，一直到得出最優(yōu)解為止。2/7/202320對初始基本可行解迭代尋優(yōu)得到最優(yōu)解為：2/7/202321運用運費差額法，得到該問題的初始基本可行解如下：2/7/202322練習1、2/7/202323最小運輸費用為1502/7/2023242、2/7/202325無窮多最優(yōu)解,最小運輸成本為7225.2/7/202326六、產(chǎn)銷不平衡問題的討論

；增加銷地B其運價：c=0，i=1,2,…，m，銷量：

2/7/202327

；增加產(chǎn)地A其運價：c=0,j=1,2,…,n,產(chǎn)量：

2/7/202328例、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩