產(chǎn)銷不平衡的運輸問題ppt課件

1、第四章 運輸問題4.1 運輸問題4.2 運輸問題的表上作業(yè)法4.3 運輸問題的進(jìn)一步討論 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111產(chǎn)銷平衡問題的數(shù)學(xué)模型n表上作業(yè)法是單純形法在求解運輸問題表上作業(yè)法是單純形法在求解運輸問題的一種簡便方法。的一種簡便方法。n單純形法與表上作業(yè)法的關(guān)系：單純形法與表上作業(yè)法的關(guān)系：n（1找出初始基可行解找出初始基可行解 n（2求各非基變量的檢驗數(shù)求各非基變量的檢驗數(shù)n（3判斷是否最優(yōu)解判斷是否最優(yōu)解計算表中空格檢驗數(shù)計算表中空格檢驗數(shù)表上給出表上給出m+n-1個數(shù)字格個數(shù)字格檢驗是

2、否所有檢驗數(shù)非負(fù)檢驗是否所有檢驗數(shù)非負(fù)換基：（4 4確定換入變量和換出變量找出新確定換入變量和換出變量找出新的基可行解。的基可行解。（5 5反復(fù)反復(fù)2 2）、（）、（3 3直至求出最優(yōu)直至求出最優(yōu)解。解。表上調(diào)整閉回路調(diào)整）表上調(diào)整閉回路調(diào)整）（運輸問題必有最優(yōu)解）（運輸問題必有最優(yōu)解）停頓最優(yōu)解？是否舉例說明表上作業(yè)法例1、某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量、 四個銷售點的銷量及單位運價如下表：41228543961111104814121482210163214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地第一步：確定初始基可行解 最小元素法、伏格爾法n最小元素法思路：n 從單價中最小運價確定供應(yīng)量，

3、逐步次小，直至得到m+n-1個數(shù)字格。最小元素法舉例41228543961111104814121482210163214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地822010100614868000060n例1用伏格爾法得到的初始基可行解4814121482210163214321AAABBBB4122854396111110銷量產(chǎn)量銷地銷地產(chǎn)地產(chǎn)地48148122244685149228114412 z目標(biāo)函數(shù)值目標(biāo)函數(shù)值用最小元素法求出的目標(biāo)函數(shù)z=246第三步：解的調(diào)整 調(diào)整位置2，4非空，回路角上的格至少為空，且保證數(shù)字的非負(fù)性。412285439611111048141214822101

4、63214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地82101468-1（-2）（-2）（+2）（+2）n調(diào)整后的解為：41228543961111104814121482210163214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地8212144822091122246244689211441251428, 0zij此時的解為最優(yōu)解。有無窮多最優(yōu)解幾點說明：n當(dāng)檢驗數(shù)為的負(fù)的變量超過兩個，選擇最小者對應(yīng)的變量換入；n在最優(yōu)解的表中，若有檢驗數(shù)=0，則該運輸問題有無窮多最優(yōu)解；n迭代過程中，若某一格填數(shù)時需同時劃去一行和一列，此時出現(xiàn)退化。為保證m+n-1個非空格，需在上述的行或列中填入數(shù)字0。產(chǎn)銷不平衡的

5、運輸問題產(chǎn)銷不平衡的運輸問題實際問題中產(chǎn)銷往往是不平衡的，實際問題中產(chǎn)銷往往是不平衡的，就需要把產(chǎn)銷不平衡的問題轉(zhuǎn)化就需要把產(chǎn)銷不平衡的問題轉(zhuǎn)化成產(chǎn)銷平衡問題。成產(chǎn)銷平衡問題。產(chǎn)大于銷產(chǎn)大于銷銷大于產(chǎn)銷大于產(chǎn)一、產(chǎn)銷不平衡的運輸問題（）若總產(chǎn)量大于總銷量，即）若總產(chǎn)量大于總銷量，即njjmiiba11minjjinbab111令假象銷地的銷量為：令假象銷地的銷量為：這里，松弛變量這里，松弛變量xin+1可以視為從可以視為從產(chǎn)地產(chǎn)地Ai運往銷地運往銷地Bn+1的運輸量，的運輸量，由于實際并不運送，它們的運費為由于實際并不運送，它們的運費為cin+1=0i=1,2,m。于是，這個運輸問題就轉(zhuǎn)化成了

6、一個于是，這個運輸問題就轉(zhuǎn)化成了一個產(chǎn)銷平衡的問題。產(chǎn)銷平衡的問題。 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111原產(chǎn)大于銷平衡問題的數(shù)學(xué)模型修改后產(chǎn)大于銷平衡問題的數(shù)學(xué)模型 1,2,1,2,1,01,2,1,2,1,min111111nnjmixnnjbxmiaxxczijjmiijinjijminjijij決策變量 表示由 到 的物品數(shù)量。iAiBijx1211211222221211112111121nnmnmnmmmnnnnnnbbbbxxxxAxxxxAxxxxABBBB銷地產(chǎn)地銷量產(chǎn)量maaa2112c

7、11cnc121c22cnc21mc2mcmnc000注意：用最小元素法求初始調(diào)運方案時，最后一列的零運價最后考慮。 例:某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最?。緽1B2B3產(chǎn)產(chǎn)量量A1646300A2655300銷銷量量150150200 解：增加一個虛設(shè)的銷地運輸費用為解：增加一個虛設(shè)的銷地運輸費用為0 0 B1 B2 B3 B4 產(chǎn)量 A1 6 4 6 0 300 A2 6 5 5 0 300 銷量 150 150 200 100 （）若總產(chǎn)量小于總銷量，即njj

8、miiba11miinjjmaba111令假象產(chǎn)地的銷量為：一、產(chǎn)銷不平衡的運輸問題仿照上述類似處理。這里，松弛變量這里，松弛變量xm+1,j可以視為可以視為從產(chǎn)地從產(chǎn)地Am+1運往銷地運往銷地Bj的運輸?shù)倪\輸量，由于實際并不運送，它們的運量，由于實際并不運送，它們的運費為費為cm+1,j=0j=1,2,n。于是，這。于是，這個運輸問題就轉(zhuǎn)化成了一個產(chǎn)銷平個運輸問題就轉(zhuǎn)化成了一個產(chǎn)銷平衡的問題。衡的問題。 例例: :某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A1A1、A2A2將物品將物品運往三個銷地運往三個銷地B1B1、B2B2、B3B3，各產(chǎn)地的產(chǎn)，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地量、各銷

9、地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最?。亢握{(diào)運可使總運輸費用最??？ B1 B2 B3 產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 銷量 250 200 200 解：增加一個虛設(shè)的產(chǎn)地運輸費用為解：增加一個虛設(shè)的產(chǎn)地運輸費用為0 0 B1 B2 B3 產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 銷量 250 200 200 產(chǎn)銷不平衡運輸問題舉例產(chǎn)銷不平衡運輸問題舉例 設(shè)有設(shè)有A、B、C三個化肥廠供應(yīng)三個化肥廠供應(yīng)1、2、3、4四個地四個地區(qū)的農(nóng)用化肥。假設(shè)效果相

10、同，有關(guān)數(shù)據(jù)如下表區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表 舉例舉例1234產(chǎn)量產(chǎn)量A1613221750B1413191560C19202350最低需要最低需要量量3070010最高需要最高需要量量507030不限不限 根據(jù)題意，作出產(chǎn)銷平衡運價表：根據(jù)題意，作出產(chǎn)銷平衡運價表： 最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運費取地運費取M ，而最高要求與最低要求的差，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為運費取為 0 。對應(yīng)。對應(yīng) 4的銷量的銷量50 是考慮問是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)

11、銷平衡要求題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定確定 D的產(chǎn)量為的產(chǎn)量為 50。Ex. 2 已知運輸問題由表給出，試建立運輸模型已知運輸問題由表給出，試建立運輸模型 . Bj Ai B1 B2 B3 ai A142510 A263815 bj8714解解: Bj Ai B1 B2 B3 ai A142510 A263815 A3000 4 bj8714本題產(chǎn)量為本題產(chǎn)量為2525，銷量為，銷量為2929，是銷大于產(chǎn)問題，是銷大于產(chǎn)問題 虛設(shè)一個產(chǎn)地虛設(shè)一個產(chǎn)地 A3 A3，由于并沒有生產(chǎn)，所以，由于并沒有生產(chǎn)，所以運價為零，得運輸模型運價為零，得運輸模型. . 如果各銷地不滿足時，單位缺貨費為如果各銷地不滿足時，單位缺貨費為 4 4，3 3，7 7，則運輸模型為則運輸模型為437運輸問題討論一、概念題判斷）1、運輸問題是一種LP問題，其求解結(jié)果有四種情況。2、在運輸問題中，只要給出一組含m+n-1個非零的 ，且滿足 就可以作為