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

第三章運(yùn)輸問(wèn)題2/7/20231例、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。拷猓寒a(chǎn)銷平衡問(wè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)輸問(wèn)題及其數(shù)學(xué)模型2/7/20232一般運(yùn)輸模型：產(chǎn)銷平衡A1、A2、…、Am表示某物資的m個(gè)產(chǎn)地；B1、B2、…、Bn表示某物質(zhì)的n個(gè)銷地；si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問(wè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)輸問(wèn)題的表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其實(shí)質(zhì)是單純形法。運(yùn)輸問(wèn)題都存在最優(yōu)解。計(jì)算過(guò)程（假設(shè)產(chǎn)銷平衡）：1.找出初始基本可行解。對(duì)于有m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡問(wèn)題，則有m個(gè)關(guān)于產(chǎn)量的約束方程和n個(gè)關(guān)于銷量的約束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個(gè)獨(dú)立的約束方程，即運(yùn)輸問(wèn)題有m+n-1個(gè)基變量。在m×n的產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格，其相對(duì)應(yīng)的調(diào)運(yùn)量的值即為基變量的值。2.求各非基變量的檢驗(yàn)數(shù)，即檢驗(yàn)除了上述m+n-1個(gè)基變量以外的空格的檢驗(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)，即對(duì)單位運(yùn)價(jià)最小的變量分配運(yùn)輸量。2/7/202352、運(yùn)費(fèi)差額法初看起來(lái)，最小元素法十分合理。但是，有時(shí)按某一最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)時(shí)，卻可能導(dǎo)致其他的地方多花幾倍的費(fèi)用，從而使整個(gè)運(yùn)輸費(fèi)用增加。對(duì)每一個(gè)供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)價(jià)中找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià)，并稱這兩個(gè)單位運(yùn)價(jià)之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小單位運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大，2/7/20236反之，如果罰數(shù)的值很大，則不按最小運(yùn)價(jià)組織運(yùn)輸就會(huì)造成很大損失。故應(yīng)盡量按最小單位運(yùn)價(jià)安排運(yùn)輸。運(yùn)費(fèi)差額法就是基于這種考慮提出來(lá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)用位勢(shì)法求這個(gè)解各非基變量的檢驗(yàn)數(shù)。由于所有非基變量的檢驗(yàn)數(shù)全非負(fù)，故這個(gè)解為最優(yōu)解。對(duì)這個(gè)解來(lái)說(shuō)，因若以為換入變量可再得一解，它與上面最優(yōu)解的目標(biāo)函數(shù)值相等，故它也是一個(gè)最優(yōu)解，即該運(yùn)輸問(wèn)題有無(wú)窮多最優(yōu)解。五、需要說(shuō)明的幾個(gè)問(wèn)題1、若運(yùn)輸問(wèn)題的某一基可行解有幾個(gè)非基變量的檢驗(yàn)數(shù)均為負(fù)。在繼續(xù)進(jìn)行迭代時(shí)，取它們中的任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取中最小者對(duì)應(yīng)的變量為換入變量。2/7/2023102、當(dāng)?shù)竭\(yùn)輸問(wèn)題的最優(yōu)解時(shí)，如果有某非基變量的檢驗(yàn)數(shù)等于零，則說(shuō)明該運(yùn)輸問(wèn)題有多重（無(wú)窮多）最優(yōu)解。3、當(dāng)運(yùn)輸問(wèn)題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時(shí)，在迭代過(guò)程中有可能在某個(gè)格填入一個(gè)運(yùn)量時(shí)需同時(shí)劃去運(yùn)輸表的一行和一列，這時(shí)就出現(xiàn)了退化。在運(yùn)輸問(wèn)題中，退化解是時(shí)常發(fā)生的。為了使表上作業(yè)法的迭代工作進(jìn)行下去，退化時(shí)應(yīng)在同時(shí)劃去的一行或一列中的某個(gè)格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0的基變量，使迭代過(guò)程中基可行解的分量恰好為m+n-1個(gè)。2/7/202311例：某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由3個(gè)銷售點(diǎn)（銷地）出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位均為噸）各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)（元/噸）示于下表中。要求研究產(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個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)（銷地）出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位均為噸）各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)（元/噸）示于下表中。要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小。2/7/202315運(yùn)用最小元素法，得到上例的初始基本可行解如下：對(duì)初始基本可行解進(jìn)行最優(yōu)判斷

2/7/202316五、解的改進(jìn)對(duì)運(yùn)輸問(wèn)題的一個(gè)解來(lái)說(shuō)，若最優(yōu)性檢驗(yàn)時(shí)某非基變量的檢驗(yàn)數(shù)為負(fù)，說(shuō)明將這個(gè)非基變量變?yōu)榛兞繒r(shí)運(yùn)費(fèi)會(huì)更小。因而這個(gè)解不是最優(yōu)解，還可以進(jìn)一步改進(jìn)。改進(jìn)的方法是在運(yùn)輸表中找出這個(gè)空格對(duì)應(yīng)的閉回路，在滿足所有約束條件的前提下，使盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點(diǎn)的運(yùn)輸量，以得到另一個(gè)更好的基可行解。1、閉回路的確定方法2/7/202317首先選取某檢驗(yàn)數(shù)為負(fù)數(shù)的空格為調(diào)入格，即以它對(duì)應(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）以空格為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針?lè)较蚯斑M(jìn)，對(duì)閉回路上的頂點(diǎn)依次編號(hào)；

（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)輸方案減少，改變量等于然后，再對(duì)得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，如不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。2/7/202320對(duì)初始基本可行解迭代尋優(yōu)得到最優(yōu)解為：2/7/202321運(yùn)用運(yùn)費(fèi)差額法，得到該問(wèn)題的初始基本可行解如下：2/7/202322練習(xí)1、2/7/202323最小運(yùn)輸費(fèi)用為1502/7/2023242、2/7/202325無(wú)窮多最優(yōu)解,最小運(yùn)輸成本為7225.2/7/202326六、產(chǎn)銷不平衡問(wèn)題的討論

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

2/7/202327

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

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