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

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

2、否所有檢驗(yàn)數(shù)非負(fù)檢驗(yàn)是否所有檢驗(yàn)數(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ùn)輸問題必有最優(yōu)解）（運(yùn)輸問題必有最優(yōu)解）停頓最優(yōu)解？是否舉例說明表上作業(yè)法例1、某部門三個(gè)工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量、 四個(gè)銷售點(diǎn)的銷量及單位運(yùn)價(jià)如下表：41228543961111104814121482210163214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地第一步：確定初始基可行解 最小元素法、伏格爾法n最小元素法思路：n 從單價(jià)中最小運(yùn)價(jià)確定供應(yīng)量，

3、逐步次小，直至得到m+n-1個(gè)數(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此時(shí)的解為最優(yōu)解。有無窮多最優(yōu)解幾點(diǎn)說明：n當(dāng)檢驗(yàn)數(shù)為的負(fù)的變量超過兩個(gè)，選擇最小者對(duì)應(yīng)的變量換入；n在最優(yōu)解的表中，若有檢驗(yàn)數(shù)=0，則該運(yùn)輸問題有無窮多最優(yōu)解；n迭代過程中，若某一格填數(shù)時(shí)需同時(shí)劃去一行和一列，此時(shí)出現(xiàn)退化。為保證m+n-1個(gè)非空格，需在上述的行或列中填入數(shù)字0。產(chǎn)銷不平衡的

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

6、一個(gè)于是，這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(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)運(yùn)方案時(shí)，最后一列的零運(yùn)價(jià)最后考慮。 例:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。緽1B2B3產(chǎn)產(chǎn)量量A1646300A2655300銷銷量量150150200 解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為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)銷不平衡的運(yùn)輸問題仿照上述類似處理。這里，松弛變量這里，松弛變量xm+1,j可以視為可以視為從產(chǎn)地從產(chǎn)地Am+1運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸?shù)倪\(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為費(fèi)為cm+1,j=0j=1,2,n。于是，這。于是，這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問題。衡的問題。 例例: :某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1A1、A2A2將物品將物品運(yùn)往三個(gè)銷地運(yùn)往三個(gè)銷地B1B1、B2B2、B3B3，各產(chǎn)地的產(chǎn)，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地量、各銷

9、地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?B1 B2 B3 產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 銷量 250 200 200 解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為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)銷不平衡運(yùn)輸問題舉例產(chǎn)銷不平衡運(yùn)輸問題舉例 設(shè)有設(shè)有A、B、C三個(gè)化肥廠供應(yīng)三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地四個(gè)地區(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)銷平衡運(yùn)價(jià)表：根據(jù)題意，作出產(chǎn)銷平衡運(yùn)價(jià)表： 最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取地運(yùn)費(fèi)取M ，而最高要求與最低要求的差，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為運(yùn)費(fèi)取為 0 。對(duì)應(yīng)。對(duì)應(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 已知運(yùn)輸問題由表給出，試建立運(yùn)輸模型已知運(yùn)輸問題由表給出，試建立運(yùn)輸模型 . 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è)一個(gè)產(chǎn)地虛設(shè)一個(gè)產(chǎn)地 A3 A3，由于并沒有生產(chǎn)，所以，由于并沒有生產(chǎn)，所以運(yùn)價(jià)為零，得運(yùn)輸模型運(yùn)價(jià)為零，得運(yùn)輸模型. . 如果各銷地不滿足時(shí)，單位缺貨費(fèi)為如果各銷地不滿足時(shí)，單位缺貨費(fèi)為 4 4，3 3，7 7，則運(yùn)輸模型為則運(yùn)輸模型為437運(yùn)輸問題討論一、概念題判斷）1、運(yùn)輸問題是一種LP問題，其求解結(jié)果有四種情況。2、在運(yùn)輸問題中，只要給出一組含m+n-1個(gè)非零的 ，且滿足 就可以作為