產(chǎn)銷不平衡的運輸問題--運籌學(xué)

1、運籌學(xué)-產(chǎn)銷不平衡運輸問題1 運輸問題2 運輸問題的表上作業(yè)法3 運輸問題的進一步討論運輸問題的進一步討論運輸問題 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)系：（1）找出初始基可行解）找出初始基可行解 （2）求各非基變量的檢驗數(shù)）求各非基變量的檢驗數(shù)（3）判斷是否最優(yōu)解）判斷是否最優(yōu)解計算表中空格檢驗數(shù)計算表中空格檢驗數(shù)表上給出

2、表上給出m+n-1個數(shù)字格個數(shù)字格檢驗是否所有檢驗數(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)地運輸問題第一步：確定

3、初始基可行解 最小元素法、伏格爾法n最小元素法思路： 從單價中最小運價確定供應(yīng)量，逐步次小，直至得到m+n-1個數(shù)字格。運輸問題最小元素法舉例41228543961111104814121482210163214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地822010100614868000060運輸問題n例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

4、）非空，回路角上的格至少為空，且保證數(shù)字的非負(fù)性。41228543961111104814121482210163214321AAABBBB銷量產(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迭代

5、過程中，若某一格填數(shù)時需同時劃去一行和一列，此時出現(xiàn)退化。為保證m+n-1個非空格，需在上述的行或列中填入數(shù)字0。運輸問題產(chǎn)銷不平衡的運輸問題產(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)銷不平衡的運輸問題n（）若總產(chǎn)量大于總銷量，即）若總產(chǎn)量大于總銷量，即njjmiiba11minjjinbab111令假象銷地的銷量為：令假象銷地的銷量為：運輸問題這里，松弛變量這里，松弛變量xi n+1可以視為從可以視為從產(chǎn)地產(chǎn)地A i運往銷

6、地運往銷地Bn+1的運輸量，由的運輸量，由于實際并不運送，它們的運費為于實際并不運送，它們的運費為 ci n+1=0i=1,2,m。于是，這個運輸問題就轉(zhuǎn)化成了一個于是，這個運輸問題就轉(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運輸問題決策變量 表示由 到 的

7、物品數(shù)量。iAiBijx1211211222221211112111121nnmnmnmmmnnnnnnbbbbxxxxAxxxxAxxxxABBBB銷地產(chǎn)地銷量產(chǎn)量maaa2112c11cnc121c22cnc21mc2mcmnc000注意：用最小元素法求初始調(diào)運方案時，最后一列的零運價最后考慮。運輸問題 例:某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？B1B2B3產(chǎn)產(chǎn)量量A1646300A2655300銷銷量量150150200 運輸問題 解：增加一個虛設(shè)的銷地運輸費用

8、為解：增加一個虛設(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 運輸問題n（）若總產(chǎn)量小于總銷量，即njjmiiba11miinjjmaba111令假象產(chǎn)地的銷量為：一、產(chǎn)銷不平衡的運輸問題仿照上述類似處理。運輸問題這里，松弛變量這里，松弛變量x m+1,j可以視為從可以視為從產(chǎn)地產(chǎn)地A m+1運往銷地運往銷地Bj的運輸量，的運輸量，由于實際并不運送，它們的運費為由于實際并不運送，它們的運費為c m+1,j=0j=1,2,n。于是，這個運于是，這個運輸問題就轉(zhuǎn)化成了一個產(chǎn)銷平衡的輸問題就轉(zhuǎn)

9、化成了一個產(chǎn)銷平衡的問題。問題。運輸問題 例例: :某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A A1 1、A A2 2將物品將物品運往三個銷地運往三個銷地B B1 1、B B2 2、B B3 3，各產(chǎn)地的產(chǎn)各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地量、各銷地的銷量和各產(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 B

10、3 產(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è)效果相同，有關(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)

11、的虛設(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)銷平衡要求確本身適當(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)量為25，銷量為，銷量為29，是銷大于產(chǎn)問題，是銷大于產(chǎn)問題 虛設(shè)一個產(chǎn)地虛設(shè)一個產(chǎn)地 A3，由于并沒有生產(chǎn)，所以，由于并沒有生產(chǎn)，所以運價為零，得運輸模型運價為零，得運輸模型. . 如果各銷地不滿足時，單位缺貨費為如果各銷地不滿足時，單位缺貨費為 4，3，7，則運輸模型為則運輸模型為437運輸問題討論運輸問題一、概念題（判斷）1、運輸問題是一種LP問題，其求解結(jié)果有四種情況。2、在運輸問題中，只要給出一組含（m+n-1）個非零的 ，且滿足 就可以作為一