管理運籌學04運輸問題課件

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

3.運輸問題的求解

4.運輸問題的拓展及應用第四章運輸問題2023/7/232.

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

=

i

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

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

2023/7/23例4-1(最小元素法)

2023/7/23閉合回路法求檢驗數(shù)

2023/7/23閉合回路法求檢驗數(shù)

2023/7/23閉合回路法求檢驗數(shù)

2023/7/23例4-1(伏格爾法)

2023/7/23閉合回路法求檢驗數(shù)2023/7/23位勢法的基本步驟1.把基變量對應的運價拿來；2.任意取一個位勢因子并賦予一個任意值；3.余下的所有因子可根據(jù)基變量的運價cij

=

i

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

i

+j)。

2023/7/23例4-1(最小元素法)

2023/7/23位勢法求檢驗數(shù)

2023/7/23位勢法求檢驗數(shù)

2023/7/23例1(伏格爾法)

2023/7/23位勢法求檢驗數(shù)

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

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

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