運(yùn)籌學(xué)課件 第三章運(yùn)輸問題

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

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

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

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

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

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

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

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

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

2/7/202327

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

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