運(yùn)輸問題的內(nèi)涵運(yùn)輸問題不僅僅是把某種商品從若干個(gè)產(chǎn).ppt

2019/7/9,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)輸問題的擴(kuò)展及應(yīng)用,第三章 運(yùn)輸問題,2019/7/9,運(yùn)輸問題的數(shù)學(xué)模型,2019/7/9,第88頁例3.1,2019/7/9,例3.1的數(shù)學(xué)模型,2019/7/9,運(yùn)輸問題的求解,1.求解方法：表上作業(yè)法 2.表上作業(yè)法的基本步驟 (1)找出初始基可行解； (2)求檢驗(yàn)數(shù)并判斷最優(yōu)性； (3)確定入基變量和出基變量； (4)調(diào)整運(yùn)輸方案； (5)重復(fù)24，直至最優(yōu)。 ,2019/7/9,找出初始基可行解,1.最小元素法 (1)基本思想：就近供應(yīng) (2)基本步驟 (3)例3.1 2.伏格爾法 (1)基本思想：機(jī)會(huì)成本 (2)基本步驟 (3)例3.1 ,2019/7/9,最小元素法的基本步驟,1.找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng) ； 2.劃掉已滿足要求的行或 (和) 列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”； 3.在剩余的運(yùn)價(jià)表中重復(fù)1、2兩步，直到得到初始基可行解。 ,2019/7/9,例3.1的最小元素法,2019/7/9,例3.1的最小元素法,2019/7/9,例3.1的最小元素法,2019/7/9,例3.1的最小元素法,2019/7/9,例3.1的最小元素法,2019/7/9,例3.1的最小元素法,2019/7/9,伏格爾法的基本步驟,1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差； 2.找出最大差所在的行或列； 3.找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng) ； 4.劃掉已滿足要求的行或 (和) 列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”； 5.在剩余的運(yùn)價(jià)表中重復(fù)14步，直到得到初始基可行解。 ,2019/7/9,例3.1的伏格爾法,2019/7/9,例3.1的伏格爾法,2019/7/9,例3.1的伏格爾法,2019/7/9,例3.1的伏格爾法,2019/7/9,例3.1的伏格爾法,2019/7/9,例3.1的伏格爾法,2019/7/9,求檢驗(yàn)數(shù)并判斷最優(yōu)性,1.閉合回路法 ：從任意一個(gè)空格（非基變量）出發(fā)，沿著行或列尋找的一條除此空格之外其余頂點(diǎn)均為有數(shù)字格（基變量）的回路?？崭竦拈]合回路有且唯一，有數(shù)字格不存在閉合回路。 2.位勢(shì)法：行因子i，列因子j，使每一個(gè)基變量有cij = i + j。 3.判斷最優(yōu)性：若所有的檢驗(yàn)數(shù)均大于等于零，已得最優(yōu)方案；否則，進(jìn)行方案調(diào)整。 ,2019/7/9,閉合回路法的基本步驟,1.找出某一空格的閉合回路； 2.從該空格開始在閉合回路上給各個(gè)頂點(diǎn)進(jìn)行 ”+“ 、”-“ 間隔標(biāo)號(hào)； 3.計(jì)算空格的檢驗(yàn)數(shù) 空格檢驗(yàn)數(shù)=cij(+) - cij(-) 4.重復(fù)13，直至求得全部的檢驗(yàn)數(shù)。 ,2019/7/9,例3.1(最小元素法),2019/7/9,閉合回路法求檢驗(yàn)數(shù),2019/7/9,閉合回路法求檢驗(yàn)數(shù),2019/7/9,閉合回路法求檢驗(yàn)數(shù),2019/7/9,例3.1(伏格爾法),2019/7/9,閉合回路法求檢驗(yàn)數(shù),2019/7/9,位勢(shì)法的基本步驟,1.把基變量對(duì)應(yīng)的運(yùn)價(jià)拿來； 2.任意取一個(gè)位勢(shì)因子并賦予一個(gè)任意值； 3.余下的所有因子可根據(jù)基變量的運(yùn)價(jià)cij = i + j 來唯一確定； 4.計(jì)算空格檢驗(yàn)數(shù)ij=cij - ( i + j) 。 ,2019/7/9,例3.1(最小元素法),2019/7/9,位勢(shì)法求檢驗(yàn)數(shù),2019/7/9,位勢(shì)法求檢驗(yàn)數(shù),2019/7/9,例3.1(伏格爾法),2019/7/9,位勢(shì)法求檢驗(yàn)數(shù),2019/7/9,位勢(shì)法求檢驗(yàn)數(shù),2019/7/9,確定入基變量和出基變量,1.確定入基變量：具有最大絕對(duì)值的負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的變量即為入基變量。 2.確定出基變量：在入基變量所處的閉合回路上，讓入基變量增加，由于供求平衡關(guān)系，帶 “+” 標(biāo)號(hào)的基變量將隨之增加；而帶 “-” 標(biāo)號(hào)的基變量將隨之減少，最先減少為零的基變量即為出基變量。 ,2019/7/9,確定入基變量,2019/7/9,確定出基變量,2019/7/9,調(diào)整運(yùn)輸方案,1.在入基變量所在的閉合回路上，帶 “+” 標(biāo)號(hào)的格增加 x出 ，帶 “-” 標(biāo)號(hào)的格減少x出 。注意：出基變量減少后的 “0” 不要保留在表格中，如果同時(shí)有多個(gè)而帶 “-” 標(biāo)號(hào)的格減少為零，可人為確定之一為出基變量，在表格中保留其它“0” 。 2. 對(duì)調(diào)整后的方案求檢驗(yàn)數(shù)并判斷其最優(yōu)性。 3. 重復(fù)12兩步，直至得到最優(yōu)方案。 ,2019/7/9,運(yùn)輸方案,2019/7/9,調(diào)整后的運(yùn)輸方案,2019/7/9,最優(yōu)運(yùn)輸方案,2019/7/9,運(yùn)輸問題的擴(kuò)展及應(yīng)用,1.產(chǎn)銷不平衡的運(yùn)輸問題 (1)產(chǎn)大于銷 (2)銷大于產(chǎn) 2.運(yùn)輸問題的應(yīng)用 (1)第94頁例3.3 (2)第95頁例3.4 (3)第99頁習(xí)題3.3 (4)第96頁例3.5 ,2019/7/9,產(chǎn)大于銷的運(yùn)輸問題,2019/7/9,產(chǎn)大于銷的運(yùn)輸問題,2019/7/9,銷大于產(chǎn)的運(yùn)輸問題,2019/7/9,銷大于產(chǎn)的運(yùn)輸問題,2019/7/9,第94頁例3.3,2019/7/9,第94頁例3.3,2019/7/9,第94頁例3.3,2019/7/9,第95頁例3.4,2019/7/9,第95頁例3.4,2019/7/9,第99頁習(xí)題3.3,已知某廠每月可生產(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)如下表所示，試確