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

管理運(yùn)籌學(xué)04運(yùn)輸問題課件1管理運(yùn)籌學(xué)04運(yùn)輸問題課件2第46頁例4-12022/10/30第46頁例4-12022/10/233例4-1的數(shù)學(xué)模型2022/10/30例4-1的數(shù)學(xué)模型2022/10/2343.運(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)。2022/10/303.運(yùn)輸問題的求解1.求解方法：表上作業(yè)法2022/10/5找出初始基可行解1.最小元素法(1)基本思想：就近供應(yīng)(2)基本步驟(3)例4-12.伏格爾法(1)基本思想：機(jī)會成本(2)基本步驟(3)例4-12022/10/30找出初始基可行解1.最小元素法2022/10/236最小元素法的基本步驟1.找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)；2.劃掉已滿足要求的行或(和)列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”；3.在剩余的運(yùn)價(jià)表中重復(fù)1、2兩步，直到得到初始基可行解。2022/10/30最小元素法的基本步驟1.找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的7例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/238例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/239例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2310例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2311例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2312例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2313伏格爾法的基本步驟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步，直到得到初始基可行解。2022/10/30伏格爾法的基本步驟1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；202214例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2315例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2316例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2317例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2318例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2319例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2320求檢驗(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)整。2022/10/30求檢驗(yàn)數(shù)并判斷最優(yōu)性1.閉合回路法：從任意一個(gè)空格（非基變21閉合回路法的基本步驟1.找出某一空格的閉合回路；2.從該空格開始在閉合回路上給各個(gè)頂點(diǎn)進(jìn)行”+“、”-“間隔標(biāo)號；3.計(jì)算空格的檢驗(yàn)數(shù)空格檢驗(yàn)數(shù)=cij(+)-cij(-)

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

2022/10/30閉合回路法的基本步驟1.找出某一空格的閉合回路；202222例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2323閉合回路法求檢驗(yàn)數(shù)

2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2324閉合回路法求檢驗(yàn)數(shù)

2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2325閉合回路法求檢驗(yàn)數(shù)

2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2326例4-1(伏格爾法)

2022/10/30例4-1(伏格爾法)2022/10/2327閉合回路法求檢驗(yàn)數(shù)2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2328位勢法的基本步驟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)。

2022/10/30位勢法的基本步驟1.把基變量對應(yīng)的運(yùn)價(jià)拿來；2022/129例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2330位勢法求檢驗(yàn)數(shù)

2022/10/30位勢法求檢驗(yàn)數(shù)2022/10/2331位勢法求檢驗(yàn)數(shù)

2022/10/30位勢法求檢驗(yàn)數(shù)2022/10/2332例1(伏格爾法)

2022/10/30例1(伏格爾法)2022/10/2333位勢法求檢驗(yàn)數(shù)

2022/10/30位勢法求檢驗(yàn)數(shù)2022/10/2334位勢法求檢驗(yàn)數(shù)2022/10/30位勢法求檢驗(yàn)數(shù)2022/10/2335確定入基變量和出基變量1.確定入基變量：具有最大絕對值的負(fù)檢驗(yàn)數(shù)所對應(yīng)的變量即為入基變量。2.確定出基變量：在入基變量所處的閉合回路上，讓入基變量增加，由于供求平衡關(guān)系，帶“+”標(biāo)號的基變量將隨之增加；而帶“-”標(biāo)號的基變量將隨之減少，最先減少為零的基變量即為出基變量。2022/10/30確定入基變量和出基變量1.確定入基變量：具有最大絕對值的負(fù)檢36確定入基變量2022/10/30確定入基變量2022/10/2337確定出基變量2022/10/30確定出基變量2022/10/2338調(diào)整運(yùn)輸方案1.在入基變量所在的閉合回路上，帶“+”標(biāo)號的格增加x出，帶“-”標(biāo)號的格減少x出。注意：出基變量減少后的“0”不要保留在表格中，如果同時(shí)有多個(gè)而帶“-”標(biāo)號的格減少為零，可人為確定之一為出基變量，在表格中保留其它“0”。2.對調(diào)整后的方案求檢驗(yàn)數(shù)并判斷其最優(yōu)性。3.重復(fù)1~2兩步，直至得到最優(yōu)方案。2022/10/30調(diào)整運(yùn)輸方案1.在入基變量所在的閉合回路上，帶“+”標(biāo)號39運(yùn)輸方案2022/10/30運(yùn)輸方案2022/10/2340調(diào)整后的運(yùn)輸方案2022/10/30調(diào)整后的運(yùn)輸方案2022/10/2341最優(yōu)運(yùn)輸方案2022/10/30最優(yōu)運(yùn)輸方案2022/10/23424.運(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-62022/10/304.運(yùn)輸問題的拓展及應(yīng)用1.產(chǎn)銷不平衡的運(yùn)輸問題2022/43產(chǎn)大于銷的運(yùn)輸問題2022/10/30產(chǎn)大于銷的運(yùn)輸問題2022/10/2344產(chǎn)大于銷的運(yùn)輸問題2022/10/30產(chǎn)大于銷的運(yùn)輸問題2022/10/2345銷大于產(chǎn)的運(yùn)輸問題2022/10/30銷大于產(chǎn)的運(yùn)輸問題2022/10/2346銷大于產(chǎn)的運(yùn)輸問題2022/10/30銷大于產(chǎn)的運(yùn)輸問題2022/10/2347第59頁例4-42022/10/30第59頁例4-42022/10/2348第59頁例4-42022/10/30第59頁例4-42022/10/2349第59頁例4-42022/10/30第59頁例4-42022/10/2350第60頁例4-52022/10/30第60頁例4-52022/10/2351第60頁例4-52022/10/30第60頁例4-52022/10/2352第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)最少的調(diào)運(yùn)方案。2022/10/30第62頁習(xí)題6已知某廠每月可生產(chǎn)甲產(chǎn)品270噸，先運(yùn)至A1、53第62頁習(xí)題62022/10/30第62頁習(xí)題62022/10/2354第62頁習(xí)題62022/10/30第62頁習(xí)題62022/10/2355第60頁例4-62022/10/30第60頁例4-62022/10/2356第60頁例4-62022/10/30第60頁例4-62022/10/2357第60頁例4-62022/10/30第60頁例4-62022/10/2358第60頁例4-62022/10/30第60頁例4-62022/10/2359文檔名THEEND!THANKYOU!文檔名THEEND!THANKYOU!60管理運(yùn)籌學(xué)04運(yùn)輸問題課件61管理運(yùn)籌學(xué)04運(yùn)輸問題課件62第46頁例4-12022/10/30第46頁例4-12022/10/2363例4-1的數(shù)學(xué)模型2022/10/30例4-1的數(shù)學(xué)模型2022/10/23643.運(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)。2022/10/303.運(yùn)輸問題的求解1.求解方法：表上作業(yè)法2022/10/65找出初始基可行解1.最小元素法(1)基本思想：就近供應(yīng)(2)基本步驟(3)例4-12.伏格爾法(1)基本思想：機(jī)會成本(2)基本步驟(3)例4-12022/10/30找出初始基可行解1.最小元素法2022/10/2366最小元素法的基本步驟1.找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)；2.劃掉已滿足要求的行或(和)列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”；3.在剩余的運(yùn)價(jià)表中重復(fù)1、2兩步，直到得到初始基可行解。2022/10/30最小元素法的基本步驟1.找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的67例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2368例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2369例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2370例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2371例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2372例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2373伏格爾法的基本步驟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步，直到得到初始基可行解。2022/10/30伏格爾法的基本步驟1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；202274例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2375例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2376例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2377例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2378例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2379例4-1的伏格爾法2022/10/30例4-1的伏格爾法2022/10/2380求檢驗(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)整。2022/10/30求檢驗(yàn)數(shù)并判斷最優(yōu)性1.閉合回路法：從任意一個(gè)空格（非基變81閉合回路法的基本步驟1.找出某一空格的閉合回路；2.從該空格開始在閉合回路上給各個(gè)頂點(diǎn)進(jìn)行”+“、”-“間隔標(biāo)號；3.計(jì)算空格的檢驗(yàn)數(shù)空格檢驗(yàn)數(shù)=cij(+)-cij(-)

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

2022/10/30閉合回路法的基本步驟1.找出某一空格的閉合回路；202282例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2383閉合回路法求檢驗(yàn)數(shù)

2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2384閉合回路法求檢驗(yàn)數(shù)

2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2385閉合回路法求檢驗(yàn)數(shù)

2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2386例4-1(伏格爾法)

2022/10/30例4-1(伏格爾法)2022/10/2387閉合回路法求檢驗(yàn)數(shù)2022/10/30閉合回路法求檢驗(yàn)數(shù)2022/10/2388位勢法的基本步驟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)。

2022/10/30位勢法的基本步驟1.把基變量對應(yīng)的運(yùn)價(jià)拿來；2022/189例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2390位勢法求檢驗(yàn)數(shù)

2022/10/30位勢法求檢驗(yàn)數(shù)2022/10/2391位勢法求檢驗(yàn)數(shù)

2022/10/30位勢法求檢驗(yàn)數(shù)2022/10/2392例1(伏格爾法)

2022/10/30例1(伏格爾法)2022/10/2393位勢法求檢驗(yàn)數(shù)

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