運(yùn)籌學(xué)運(yùn)輸問題分析課件

Chapter3運(yùn)輸規(guī)劃

(TransportationProblem)運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型表上作業(yè)法運(yùn)輸問題的應(yīng)用本章主要內(nèi)容：Chapter3運(yùn)輸規(guī)劃

(Transportation運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型例3.1某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最小？B1B2B3產(chǎn)量A1646200A2655300銷量150150200運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型例3.1某公司從兩個(gè)產(chǎn)地A1、A2運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=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)輸規(guī)劃問題的數(shù)學(xué)模型解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸問題的一般形式：產(chǎn)銷平衡A1、A2、…、Am表示某物資的m個(gè)產(chǎn)地；B1、B2、…、Bn表示某物質(zhì)的n個(gè)銷地；ai表示產(chǎn)地Ai的產(chǎn)量；bj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸問題的一般形式：產(chǎn)銷平衡A1、A運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型已知資料如下：

銷產(chǎn)地地產(chǎn)量產(chǎn)銷平衡銷量運(yùn)價(jià)運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型已知資料如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型當(dāng)產(chǎn)銷平衡時(shí)，其模型如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型當(dāng)產(chǎn)銷平衡時(shí)，其模型如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型當(dāng)產(chǎn)大于銷時(shí)，其模型如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型當(dāng)產(chǎn)大于銷時(shí)，其模型如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型當(dāng)產(chǎn)小于銷時(shí)，其模型如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型當(dāng)產(chǎn)小于銷時(shí)，其模型如下：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型特征：

1、平衡運(yùn)輸問題必有可行解，也必有最優(yōu)解；2、運(yùn)輸問題的基本可行解中應(yīng)包括m+n－1個(gè)基變量。運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型特征：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸問題約束條件的系數(shù)矩陣mn運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸問題約束條件的系數(shù)矩陣mn運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型基本可行解是否最優(yōu)解結(jié)束換基是否

運(yùn)輸問題的求解思路運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型基本可行解是否最優(yōu)解結(jié)束換基是否運(yùn)輸問題的求解思路運(yùn)輸規(guī)劃

計(jì)算步驟：(1)找出初始調(diào)運(yùn)方案。即在(m×n)產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格。(最小元素法、西北角法或伏格爾法）(2)求檢驗(yàn)數(shù)。（閉回路法或位勢法）判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。(3)對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（表上閉回路法調(diào)整）確定m+n-1個(gè)基變量(4)重復(fù)（2）、（3），直到求得最優(yōu)調(diào)運(yùn)方案?？崭穸⒈砩献鳂I(yè)法計(jì)算步驟：(1)找出初始調(diào)運(yùn)方案。即在(m×n)產(chǎn)銷平表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運(yùn)方案）最小元素法、西北角法、伏格爾法第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)數(shù)σij全都非負(fù)(求min)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)σij<0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位勢法第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單表上作業(yè)法例3.2某運(yùn)輸資料如下表所示：單位銷地運(yùn)價(jià)產(chǎn)地產(chǎn)量311310719284741059銷量3656問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？1、求初始方案：最小元素法、西北角法、伏格爾法表上作業(yè)法例3.2某運(yùn)輸資料如下表所示：單位表上作業(yè)法基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058總的運(yùn)輸費(fèi)＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元方法1：最小元素法341633表上作業(yè)法基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供表上作業(yè)法練習(xí)銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314A2842727A35910619銷量221312131213131912表上作業(yè)法練習(xí)銷地B1B2B3B4產(chǎn)量A1675表上作業(yè)法（2）西北角法（或左上角法）此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實(shí)際背景，但它易操作，特別適合在計(jì)算機(jī)上編程計(jì)算，因而受歡迎。方法如下：365674934490656404902562029005620090036360000000340002200036表上作業(yè)法（2）西北角法（或左上角法）此法是純粹的人為的規(guī)表上作業(yè)法在滿足約束條件下盡可能的給最左上角的變量最大值.銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量8141214488864814所以，初始基可行解為：(8,8,4,8,14)目標(biāo)函數(shù)值Z＝372例3.3某運(yùn)輸資料如下表所示：表上作業(yè)法在滿足約束條件下盡可能的給最左上角的變量最大值.表上作業(yè)法練習(xí)銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314A2842727A35910619銷量22131213813131466表上作業(yè)法練習(xí)銷地B1B2B3B4產(chǎn)量A1675表上作業(yè)法

最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其他處要多花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。例如下面兩種運(yùn)輸方案。

最小元素法：15152012105815510總運(yùn)費(fèi)是z=10×8+5×2+15×1=10515152012105851510另一種方法：總運(yùn)費(fèi)z=10×5+15×2+5×1=85表上作業(yè)法最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時(shí)表上作業(yè)法方法2：Vogel法1）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量行差額A177A2

41A391銷量3656列差額251331131019274105810-3=72-1=15-4=13-1=29-4=53-2=18-5=3表上作業(yè)法方法2：Vogel法1）從運(yùn)價(jià)表中分別計(jì)算出各行和表上作業(yè)法2）再從差值最大的行或列中找出最小運(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。重復(fù)1)和2)，直到找出初始解為至。B1B2B3B4產(chǎn)量行差額A177A2

41A3

91銷量3656列差額25133113101927410585表上作業(yè)法2）再從差值最大的行或列中找出最小運(yùn)價(jià)確定供需關(guān)系表上作業(yè)法單位銷地運(yùn)價(jià)產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額7135275×××3×表上作業(yè)法單位銷地產(chǎn)量行差額311310719表上作業(yè)法單位銷地運(yùn)價(jià)產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額113515×××3×631××2該方案的總運(yùn)費(fèi):(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元表上作業(yè)法單位銷地產(chǎn)量行差額311310719銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A385116221銷量814121448列差額251314所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝244表上作業(yè)法例3.4某運(yùn)輸資料如下表所示：銷地B1B2B3B4產(chǎn)量行差額A14124111銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A385116221銷量814121448列差額21314所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝2448表上作業(yè)法例3.4某運(yùn)輸資料如下表所示：銷地B1B2B3B4產(chǎn)量行差額A14124111銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A385116221銷量814121448列差額21314所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝24488表上作業(yè)法例3.4某運(yùn)輸資料如下表所示：銷地B1B2B3B4產(chǎn)量行差額A14124111銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A38511622銷量814121448列差額1314所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝24488表上作業(yè)法例3.4某運(yùn)輸資料如下表所示：12銷地B1B2B3B4產(chǎn)量行差額A14124111銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A38511622銷量814121448列差額314所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝24488表上作業(yè)法例3.4某運(yùn)輸資料如下表所示：1224銷地B1B2B3B4產(chǎn)量行差額A14124111表上作業(yè)法練習(xí)銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314A2842727A35910619銷量221312131213121319表上作業(yè)法練習(xí)銷地B1B2B3B4產(chǎn)量A1675表上作業(yè)法2、最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）求檢驗(yàn)數(shù)的方法有兩種：閉回路法對(duì)偶變量法（位勢法）（1）閉合回路法：σij≥0（因?yàn)槟繕?biāo)函數(shù)要求最小化）表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量?；兞康臋z驗(yàn)數(shù)σij＝0，非基變量的檢驗(yàn)數(shù)σij≥0。σij<0表示運(yùn)費(fèi)減少，σij>0表示運(yùn)費(fèi)增加。表上作業(yè)法2、最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）求檢驗(yàn)數(shù)的方法有閉回路：從空格出發(fā)順時(shí)針(或逆時(shí)針)畫水平(或垂直)直線，遇到填有運(yùn)量的方格可轉(zhuǎn)90°，然后繼續(xù)前進(jìn)，直到到達(dá)出發(fā)的空格所形成的閉合回路。調(diào)運(yùn)方案的任意空格存在唯一閉回路。表上作業(yè)法注：1.每一空格有且僅有一條閉回路；2.如果某數(shù)字格有閉回路，則此解不是可行解。若令則—運(yùn)費(fèi)的增量分析：閉回路：從空格出發(fā)順時(shí)針(或逆時(shí)針)畫水平(或垂直)表上作業(yè)法以最小元素法的初始解為例。假設(shè)產(chǎn)地A1供應(yīng)1個(gè)單位的物品給銷地B1。則解的變化和目標(biāo)函數(shù)的變化如何。銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量814121448表上作業(yè)法以最小元素法的初始解為例。假設(shè)產(chǎn)地A1供應(yīng)1個(gè)單位表上作業(yè)法要保證產(chǎn)銷平衡，則稱為閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量8141214481表上作業(yè)法要保證產(chǎn)銷平衡，則表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量81412144812表上作業(yè)法銷地B1B2B3B4產(chǎn)量A1表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量814121448121表上作業(yè)法銷地B1B2B3B4產(chǎn)量A1表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量81412144810211表上作業(yè)法銷地B1B2B3B4產(chǎn)量A1表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量8141214481211210表上作業(yè)法銷地B1B2B3B4產(chǎn)量A1表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量814121448121-11210檢驗(yàn)數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。表上作業(yè)法銷地B1B2B3B4產(chǎn)量A1表上作業(yè)法練習(xí)銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531414A28427278136A35910619613銷量221312135579-3-11表上作業(yè)法練習(xí)銷地B1B2B3B4產(chǎn)量A1675

uivjm個(gè)n個(gè)（2）對(duì)偶變量法（位勢法）表上作業(yè)法設(shè)其對(duì)偶變量為：uivjm個(gè)n個(gè)（2）對(duì)偶變量法（位勢法）表上作業(yè)法

ui?vj無約束（i=1,2,…,m;j=1,2,…,n)標(biāo)準(zhǔn)型運(yùn)輸問題的對(duì)偶問題模型為：表上作業(yè)法則運(yùn)輸問題變量xij的檢驗(yàn)數(shù)為：ui?vj表上作業(yè)法用位勢法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)的方法：1）在給定初始解的表上增加一行和一列，在列中填入ui，在行中填入vj。2）令u1＝0，再按cij-(ui+vj)=0（基變量的cij求出其余的ui與vj。3）由

ij=Cij-（ui+vj），求出非基變量的檢驗(yàn)數(shù)。表上作業(yè)法用位勢法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)的方法：1）在給定表上作業(yè)法B1B2B3B4uiA1A2A3vj311310192741058u1u2u3v3v4v1v2注意：基變量的檢驗(yàn)數(shù)

i

j=Ci

j-（ui+vj）=0436313表上作業(yè)法B1B2B3B4uiA1A2A3vj3113101表上作業(yè)法B1B2B3B4uiA1A2A3vj3113101927410580-1-531029令u1=0u1+v3=3u1+v4=10u2+v3=2u2+v1=1u3+v2=4u3+v4=5436313表上作業(yè)法B1B2B3B4uiA1A2A3vj3113101表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B1436313（1）（2）（1）（-1）（10）（12）當(dāng)存在非基變量的檢驗(yàn)數(shù)

ij≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。注意：非基變量的檢驗(yàn)數(shù)

i

j=cij-（ui+vj）

11=c11-（u1+v1）=3-(0+2)=1

31=c31-（u3+v1）=7-(2-5)=10

24=c24-（u2+v4）=8-(10-1)=-1

22=c22-（u2+v2）=9-(9-1)=1

12=c12-（u1+v2）=11-(0+9)=2

33=c33-（u3+v3）=10-(3-5)=12311310192741058表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B表上作業(yè)法3、解的改進(jìn)

——閉合回路調(diào)整法（原理同單純形法一樣）當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得最優(yōu)解。若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選用其中最小的負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格為調(diào)入格，即以它對(duì)應(yīng)的非基變量為換入變量。做一閉合回路。(1)確定換入基的變量：當(dāng)存在非基變量的檢驗(yàn)數(shù)

kl<0且kl=min{ij}時(shí)，以Xkl為換入變量，找出它在運(yùn)輸表中的閉合回路。接上例：pqijj,i)(minσ

σ=<0Xpq=X24為換入變量解的改進(jìn)的具體步驟：表上作業(yè)法3、解的改進(jìn)當(dāng)在表中空格處出現(xiàn)負(fù)表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058（1）（2）（1）（-1）（10）（12）(2)頂點(diǎn)編號(hào)：以空格(Ak,Bl)(或進(jìn)基變量xik）為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針方向前進(jìn)，對(duì)閉回路上的頂點(diǎn)依次編號(hào)。1324表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058（1）（2）（1）（-1）（10）（12）(2)頂點(diǎn)編號(hào)：以空格(Ak,Bl)(或進(jìn)基變量xik）為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針方向前進(jìn)，對(duì)閉回路上的頂點(diǎn)依次編號(hào)。1324換出變量X23表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B表上作業(yè)法(3)確定換出基的變量：在該閉回路上，從所有偶數(shù)號(hào)格點(diǎn)的調(diào)運(yùn)量中選出最小值的頂點(diǎn)（格子），以該格子中的變量為換出變量。(4)確定新的運(yùn)輸方案：以換出變量的運(yùn)輸量為調(diào)整量θ

，將該閉回路上所有奇數(shù)號(hào)格的調(diào)運(yùn)量加上調(diào)整量θ

，所有偶數(shù)號(hào)格的調(diào)運(yùn)量減去θ

，其余的不變，這樣就得到一個(gè)新的調(diào)運(yùn)方案。該運(yùn)輸方案的總運(yùn)費(fèi)比原運(yùn)輸方案減少，改變量等于換出變量的檢驗(yàn)數(shù)。(5)然后，再對(duì)得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，加不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。表上作業(yè)法(3)確定換出基的變量：在該閉回路上，從所有表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B13631(＋1)(＋1)(－1)(－1)31131019274105843表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B表上作業(yè)法31039vj-5A3-2A20A1uiB4B3B2B1536312311310192741058重新求所有非基變量的檢驗(yàn)數(shù)：表上作業(yè)法31039vj-5A3-2A20A1uiB4B3B表上作業(yè)法31039vj-5A3-2A20A1uiB4B3B2B1536312（2）（2）（1）（12）（9）（0）當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元311310192741058表上作業(yè)法31039vj-5A3-2A20A1uiB4B3B表上作業(yè)法表上作業(yè)法的計(jì)算步驟：分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小元素法或Vogel法）求檢驗(yàn)數(shù)（位勢法）所有檢驗(yàn)數(shù)≥0找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，算出總運(yùn)價(jià)表上作業(yè)法表上作業(yè)法的計(jì)算步驟：分析實(shí)際問題列出產(chǎn)銷平衡表及表上作業(yè)法表上作業(yè)法計(jì)算中的問題：（1）若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σij<0中最小者對(duì)應(yīng)的變量為換入變量。（2）無窮多最優(yōu)解 產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。如上例：σ11的檢驗(yàn)數(shù)是0，經(jīng)過調(diào)整，可得到另一個(gè)最優(yōu)解。表上作業(yè)法表上作業(yè)法計(jì)算中的問題：（1）若運(yùn)輸問題的某一基可表上作業(yè)法⑵退化解：

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

※利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量（超過2個(gè)最小值）作為調(diào)整量θ，選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為出基變量，并打上“×”以示作為非基變量。表上作業(yè)法⑵退化解：表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗(yàn)數(shù)是0，經(jīng)過調(diào)整，可得到另一個(gè)最優(yōu)解。表上作業(yè)法銷地B1B2B3B4產(chǎn)量A116A表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選x34例：用最小元素法求初始可行解表上作業(yè)法銷地B1B2B3B4產(chǎn)量A17A2一、產(chǎn)銷不平衡的運(yùn)輸問題 當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問題.這類運(yùn)輸問題在實(shí)際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。當(dāng)產(chǎn)大于銷時(shí)，即：數(shù)學(xué)模型為：運(yùn)輸問題的進(jìn)一步討論一、產(chǎn)銷不平衡的運(yùn)輸問題當(dāng)產(chǎn)大于銷時(shí)，即：數(shù)學(xué)模型為：運(yùn)輸由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉庫，假設(shè)該倉庫為一個(gè)虛擬銷地Bn+1，bn+1作為一個(gè)虛設(shè)銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時(shí),只在運(yùn)價(jià)表右端增加一列Bn+1，運(yùn)價(jià)為零,銷量為bn+1即可運(yùn)輸問題的進(jìn)一步討論由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須當(dāng)銷大于產(chǎn)時(shí)，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時(shí)虛設(shè)一個(gè)產(chǎn)地Am+1，產(chǎn)量為：運(yùn)輸問題的進(jìn)一步討論當(dāng)銷大于產(chǎn)時(shí)，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為：具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。運(yùn)輸問題的進(jìn)一步討論銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為：具體計(jì)算時(shí)，在運(yùn)價(jià)表的下例3.4求下列表中極小化運(yùn)輸問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因?yàn)橛校哼\(yùn)輸問題的進(jìn)一步討論例3.4求下列表中極小化運(yùn)輸問題的最優(yōu)解。B1B2B3所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表中A2不可達(dá)B1，用一個(gè)很大的正數(shù)M表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運(yùn)價(jià)表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180運(yùn)輸問題的進(jìn)一步討論所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表中A2不可達(dá)B1，用一個(gè)很大下表為計(jì)算結(jié)果。可看出：產(chǎn)地A4還有20個(gè)單位沒有運(yùn)出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180用前面的方法求運(yùn)輸方案：運(yùn)輸問題的進(jìn)一步討論下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個(gè)單位沒有運(yùn)出。B1運(yùn)輸問題的進(jìn)一步討論例3.5某市有三個(gè)造紙廠A1，A2，A3，其紙的產(chǎn)量分別為8，5和9個(gè)單位，有4個(gè)集中用戶B1，B2，B3，B4，其需用量分別為4，3，5和6個(gè)單位。由各造紙廠到各用戶的單位運(yùn)價(jià)如表3—14所示，請確定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1312348A2112595A367159銷量4356運(yùn)輸問題的進(jìn)一步討論例3.5某市有三個(gè)造紙廠A1，A2，運(yùn)輸問題的進(jìn)一步討論解：由于總產(chǎn)量22大于總銷量18，故本問題是個(gè)產(chǎn)銷不平衡運(yùn)輸問題。增加一假想銷地B5，用表上作業(yè)法求解。銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A13123408A21125905A3671509銷量43564運(yùn)輸問題的進(jìn)一步討論解：由于總產(chǎn)量22大于總銷量18，故本問運(yùn)輸問題的進(jìn)一步討論銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A13123408418634A211259050302-8A3671509-2954-4銷量43564運(yùn)輸問題的進(jìn)一步討論銷地B1B2B3B應(yīng)用問題舉例例3.5由n個(gè)地區(qū)需要某種物資，需要量分別不少于bj（j=1,…,n）。這些物資均由某公司分設(shè)在m個(gè)地區(qū)的工廠供應(yīng)，各工廠的產(chǎn)量分別不大于ai（i=1,…,m）,已知從第i個(gè)地區(qū)至第j個(gè)需求地區(qū)單位物資的運(yùn)價(jià)為cij，又，試寫出其對(duì)偶問題，并解釋對(duì)偶變量的經(jīng)濟(jì)意義。由于在變量相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡單得多。所以在解決實(shí)際問題時(shí)，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型。應(yīng)用問題舉例例3.5由n個(gè)地區(qū)需要某種物資，需應(yīng)用問題舉例

解：由題給出的條件，數(shù)學(xué)模型可寫為:對(duì)偶問題可寫為：應(yīng)用問題舉例解：由題給出的條件，數(shù)學(xué)模型可寫為:對(duì)偶問題可應(yīng)用問題舉例對(duì)偶變量ui的經(jīng)濟(jì)意義為在i產(chǎn)地單位物資的價(jià)格，vj的經(jīng)濟(jì)意義為在第j銷地單位物資的價(jià)格。對(duì)偶問題的經(jīng)濟(jì)意義為：如該公司欲自己將該種物資運(yùn)至各地銷售，其差價(jià)不能超過兩地之間的運(yùn)價(jià)（否則買主將在i地購買自己運(yùn)至j地），在此條件下，希望獲利為最大。應(yīng)用問題舉例對(duì)偶變量ui的經(jīng)濟(jì)意義為在i產(chǎn)地單位物資應(yīng)用問題舉例已知資料如下表所示，問如何供電能使總的輸電費(fèi)用為最??？發(fā)電廠發(fā)電量城市需電量A1700B1500A2200B2250A3100B3100B4150電力供需表B1B2B3B4A110523A24312A35634單位輸電費(fèi)用練習(xí)：應(yīng)用問題舉例已知資料如下表所示，問如何供電能使總B1B2B3B4A140025050A2100100A3400初始方案單位輸電費(fèi)用電力供需表應(yīng)用問題舉例發(fā)電廠發(fā)電量城市需電量A1700B1500A2200B2250