管理運(yùn)籌學(xué)04運(yùn)輸問題課件

1.運(yùn)輸問題的內(nèi)涵：運(yùn)輸問題不僅僅是把某種商品從若干個(gè)產(chǎn)地運(yùn)至若干個(gè)銷地而使總運(yùn)費(fèi)最小的問題；從更廣義上講，運(yùn)輸問題是具有一定模型特征的線性規(guī)劃問題。2.運(yùn)輸問題的數(shù)學(xué)模型

3.運(yùn)輸問題的求解

4.運(yùn)輸問題的拓展及應(yīng)用第四章運(yùn)輸問題2023/2/62.

運(yùn)輸問題的數(shù)學(xué)模型2023/2/6第46頁例4-12023/2/63.運(yùn)輸問題的求解1.求解方法：表上作業(yè)法2.表上作業(yè)法的基本步驟:(1)找出初始基可行解；(2)求檢驗(yàn)數(shù)并判斷最優(yōu)性；(3)確定入基變量和出基變量；(4)調(diào)整運(yùn)輸方案；(5)重復(fù)2~4，直至最優(yōu)。2023/2/6找出初始基可行解1.最小元素法(1)基本思想：就近供應(yīng)(2)基本步驟(3)例4-12.伏格爾法(1)基本思想：機(jī)會(huì)成本(2)基本步驟(3)例4-12023/2/6最小元素法的基本步驟1.找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)；2.劃掉已滿足要求的行或(和)列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”；3.在剩余的運(yùn)價(jià)表中重復(fù)1、2兩步，直到得到初始基可行解。2023/2/6例4-1的最小元素法2023/2/6例4-1的最小元素法2023/2/6例4-1的最小元素法2023/2/6例4-1的最小元素法2023/2/6伏格爾法的基本步驟1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；2.找出最大差所在的行或列；3.找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)；4.劃掉已滿足要求的行或(和)列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”；5.在剩余的運(yùn)價(jià)表中重復(fù)1~4步，直到得到初始基可行解。2023/2/6例4-1的伏格爾法2023/2/6例4-1的伏格爾法2023/2/6例4-1的伏格爾法2023/2/6例4-1的伏格爾法2023/2/6求檢驗(yàn)數(shù)并判斷最優(yōu)性1.閉合回路法：從任意一個(gè)空格（非基變量）出發(fā)，沿著行或列尋找的一條除此空格之外其余頂點(diǎn)均為有數(shù)字格（基變量）的回路?？崭竦拈]合回路有且唯一，有數(shù)字格不存在閉合回路。2.位勢法：行因子i，列因子j，使每一個(gè)基變量有cij

=

i

+j。3.判斷最優(yōu)性：若所有的檢驗(yàn)數(shù)均大于等于零，已得最優(yōu)方案；否則，進(jìn)行方案調(diào)整。2023/2/6閉合回路法的基本步驟1.找出某一空格的閉合回路；2.從該空格開始在閉合回路上給各個(gè)頂點(diǎn)進(jìn)行”+“、”-“間隔標(biāo)號(hào)；3.計(jì)算空格的檢驗(yàn)數(shù)空格檢驗(yàn)數(shù)=cij(+)-cij(-)

4.重復(fù)1~3，直至求得全部的檢驗(yàn)數(shù)。

2023/2/6例4-1(最小元素法)

2023/2/6閉合回路法求檢驗(yàn)數(shù)

2023/2/6閉合回路法求檢驗(yàn)數(shù)

2023/2/6位勢法的基本步驟1.把基變量對應(yīng)的運(yùn)價(jià)拿來；2.任意取一個(gè)位勢因子并賦予一個(gè)任意值；3.余下的所有因子可根據(jù)基變量的運(yùn)價(jià)cij

=

i

+j來唯一確定；4.計(jì)算空格檢驗(yàn)數(shù)ij=cij-(

i

+j)。

2023/2/6例4-1(最小元素法)

2023/2/6位勢法求檢驗(yàn)數(shù)

2023/2/6位勢法求檢驗(yàn)數(shù)

2023/2/6例1(伏格爾法)

2023/2/6位勢法求檢驗(yàn)數(shù)

2023/2/6位勢法求檢驗(yàn)數(shù)2023/2/6確定入基變量和出基變量1.確定入基變量：具有最大絕對值的負(fù)檢驗(yàn)數(shù)所對應(yīng)的變量即為入基變量。2.確定出基變量：在入基變量所處的閉合回路上，讓入基變量增加，由于供求平衡關(guān)系，帶“+”標(biāo)號(hào)的基變量將隨之增加；而帶“-”標(biāo)號(hào)的基變量將隨之減少，最先減少為零的基變量即為出基變量。2023/2/6確定入基變量2023/2/6確定出基變量2023/2/6調(diào)整運(yùn)輸方案1.在入基變量所在的閉合回路上，帶“+”標(biāo)號(hào)的格增加x出，帶“-”標(biāo)號(hào)的格減少x出。注意：出基變量減少后的“0”不要保留在表格中，如果同時(shí)有多個(gè)而帶“-”標(biāo)號(hào)的格減少為零，可人為確定之一為出基變量，在表格中保留其它“0”。2.對調(diào)整后的方案求檢驗(yàn)數(shù)并判斷其最優(yōu)性。3.重復(fù)1~2兩步，直至得到最優(yōu)方案。2023/2/6運(yùn)輸方案2023/2/6調(diào)整后的運(yùn)輸方案2023/2/6最優(yōu)運(yùn)輸方案2023/2/64.運(yùn)輸問題的拓展及應(yīng)用1.產(chǎn)銷不平衡的運(yùn)輸問題(1)產(chǎn)大于銷

(2)銷大于產(chǎn)2.運(yùn)輸問題的應(yīng)用(1)第59頁例4-4(2)第60頁例4-5(3)第62頁習(xí)題6

(4)第60頁例4-62023/2/6產(chǎn)大于銷的運(yùn)輸問題2023/2/6產(chǎn)大于銷的運(yùn)輸問題2023/2/6銷大于產(chǎn)的運(yùn)輸問題2023/2/6銷大于產(chǎn)的運(yùn)輸問題2023/2/6第59頁例4-42023/2/6第59頁例4-42023/2/6第59頁例4-42023/2/6第60頁例4-52023/2/6第60頁例4-52023/2/6第62頁習(xí)題6已知某廠每月可生產(chǎn)甲產(chǎn)品270噸，先運(yùn)至A1、A2、A3三個(gè)倉庫，然后在分別供應(yīng)B1、B2、B3、B4、B5五個(gè)用戶。已知倉庫容量分別為50、100、150噸，各用戶的需要量分別為25、105、60、30、70噸。已知從該廠經(jīng)各倉庫然后供應(yīng)各用戶的運(yùn)費(fèi)如下表所示，試確定一個(gè)使總運(yùn)費(fèi)最少的