第四章運(yùn)輸問題4.1運(yùn)輸問題4.2運(yùn)輸問題的表上作業(yè)法4.3運(yùn)輸問題的進(jìn)一步討論精選ppt產(chǎn)銷平衡問題的數(shù)學(xué)模型精選ppt表上作業(yè)法是單純形法在求解運(yùn)輸問題的一種簡便方法。單純形法與表上作業(yè)法的關(guān)系：〔1〕找出初始基可行解〔2〕求各非基變量的檢驗數(shù)〔3〕判斷是否最優(yōu)解計算表中空格檢驗數(shù)表上給出m+n-1個數(shù)字格檢驗是否所有檢驗數(shù)非負(fù)精選ppt換基：〔4〕確定換入變量和換出變量找出新的基可行解。〔5〕重復(fù)〔2〕、〔3〕直至求出最優(yōu)解。表上調(diào)整（閉回路調(diào)整）（運(yùn)輸問題必有最優(yōu)解）停止最優(yōu)解？是否精選ppt舉例說明表上作業(yè)法例1、某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量、四個銷售點(diǎn)的銷量及單位運(yùn)價如下表：4122854396111110銷量產(chǎn)量銷地產(chǎn)地精選ppt第一步：確定初始基可行解

——最小元素法、伏格爾法最小元素法思路：從單價中最小運(yùn)價確定供給量，逐步次小，直至得到m+n-1個數(shù)字格。精選ppt最小元素法舉例4122854396111110銷量產(chǎn)量銷地產(chǎn)地822010100614868000060精選ppt例1用伏格爾法得到的初始基可行解4122854396111110銷量產(chǎn)量銷地產(chǎn)地48148122目標(biāo)函數(shù)值用最小元素法求出的目標(biāo)函數(shù)z=246一般說來，伏格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似解。精選ppt第三步：解的調(diào)整調(diào)整位置〔2，4〕非空，回路角上的格至少為空，且保證數(shù)字的非負(fù)性。4122854396111110銷量產(chǎn)量銷地產(chǎn)地82101468-1〔-2〕〔-2〕〔+2〕〔+2〕精選ppt調(diào)整后的解為：4122854396111110銷量產(chǎn)量銷地產(chǎn)地821214482209112此時的解為最優(yōu)解。有無窮多最優(yōu)解精選ppt幾點(diǎn)說明：當(dāng)檢驗數(shù)為的負(fù)的變量超過兩個，選擇最小者對應(yīng)的變量換入；在最優(yōu)解的表中，假設(shè)有檢驗數(shù)=0，那么該運(yùn)輸問題有無窮多最優(yōu)解；迭代過程中，假設(shè)某一格填數(shù)時需同時劃去一行和一列，此時出現(xiàn)退化。為保證m+n-1個非空格，需在上述的行或列中填入數(shù)字0。精選ppt產(chǎn)銷不平衡的運(yùn)輸問題實際問題中產(chǎn)銷往往是不平衡的，就需要把產(chǎn)銷不平衡的問題轉(zhuǎn)化成產(chǎn)銷平衡問題。產(chǎn)大于銷銷大于產(chǎn)精選ppt一、產(chǎn)銷不平衡的運(yùn)輸問題〔Ⅰ〕假設(shè)總產(chǎn)量大于總銷量，即令假象銷地的銷量為：精選ppt

這里，松弛變量xin+1

可以視為從產(chǎn)地Ai

運(yùn)往銷地Bn+1

的運(yùn)輸量，由于實際并不運(yùn)送，它們的運(yùn)費(fèi)為

cin+1=0i=1,2,…,m。于是，這個運(yùn)輸問題就轉(zhuǎn)化成了一個產(chǎn)銷平衡的問題。精選ppt原產(chǎn)大于銷平衡問題的數(shù)學(xué)模型精選ppt修改后產(chǎn)大于銷平衡問題的數(shù)學(xué)模型精選ppt決策變量表示由到的物品數(shù)量。銷地產(chǎn)地銷量產(chǎn)量注意：用最小元素法求初始調(diào)運(yùn)方案時，最后一列的零運(yùn)價最后考慮。精選ppt例:某公司從兩個產(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)用最??？精選ppt解：增加一個虛設(shè)的銷地運(yùn)輸費(fèi)用為0精選ppt〔Ⅱ〕假設(shè)總產(chǎn)量小于總銷量，即令假象產(chǎn)地的銷量為：一、產(chǎn)銷不平衡的運(yùn)輸問題仿照上述類似處理。精選ppt

這里，松弛變量xm+1,j

可以視為從產(chǎn)地Am+1

運(yùn)往銷地Bj

的運(yùn)輸量，由于實際并不運(yùn)送，它們的運(yùn)費(fèi)為

cm+1,j=0j=1,2,…,n。于是，這個運(yùn)輸問題就轉(zhuǎn)化成了一個產(chǎn)銷平衡的問題。精選ppt例:某公司從兩個產(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)用最?。烤xppt解：增加一個虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0精選ppt產(chǎn)銷不平衡運(yùn)輸問題舉例設(shè)有A、B、C三個化肥廠供給1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表

舉例1234產(chǎn)量A1613221750B1413191560C19202350最低需要量3070010最高需要量507030不限精選ppt根據(jù)題意，作出產(chǎn)銷平衡運(yùn)價表：

精選ppt最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取M，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對應(yīng)4〞的銷量50是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50。精選pptEx.2運(yùn)輸問題由表給出，試建立運(yùn)輸模型.

Bj

Ai

B1

B2

B3

ai

A14

25

10

A2638

15

bj

8

7

14解:

Bj

Ai

B1

B2

B3

ai

A14

25

10

A2638

15

A3000

4

bj

8

7

14此題產(chǎn)量為25，銷量為29，是銷大于產(chǎn)問題虛設(shè)一個產(chǎn)地A3，由于并沒有生產(chǎn)，所以運(yùn)價為零，得運(yùn)輸模型.如果各銷地不滿足時，單位缺貨費(fèi)為4，3，7，那么運(yùn)輸模型為437精選ppt運(yùn)輸問題討論精選ppt一、概念題〔判斷〕1、運(yùn)輸問題是一種LP問題，其求解結(jié)果有四種情況。2、在運(yùn)輸問題中，只要給出一組含〔m+n-1〕個非零的，且滿足

就可以作為一個初始基可行解。精選ppt3、按最小元素法〔或伏格爾法〕給出的初始基