1、運(yùn)運(yùn) 籌籌 學(xué)學(xué)( Operations Research )運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型表上作業(yè)法表上作業(yè)法運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用 Page 3例例3.1 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地將物品運(yùn)往三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。啃。緽1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200Page 4解：產(chǎn)銷平衡問題：總

2、產(chǎn)量解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量總銷量500 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量的運(yùn)輸量，得到下列運(yùn)輸量表：表：B1B2B3產(chǎn)量產(chǎn)量A1x11x12x13200A2x21x22x23300銷量銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）Pag

3、e 5運(yùn)輸問題的一般形式：產(chǎn)銷平衡運(yùn)輸問題的一般形式：產(chǎn)銷平衡A1、 A2、 Am 表示某物資的表示某物資的m個(gè)產(chǎn)地；個(gè)產(chǎn)地； B1、B2、Bn 表示表示某物質(zhì)的某物質(zhì)的n個(gè)銷地；個(gè)銷地；ai 表示產(chǎn)地表示產(chǎn)地Ai的產(chǎn)量；的產(chǎn)量； bj 表示銷地表示銷地Bj 的銷量；的銷量； cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)的單位運(yùn)價(jià)。設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型： minjijijxcz11min njmixnjbxmiaxtsijjmiijnjiij, 1;,

4、 1, 0, 1, 1.11Page 6（1）系數(shù)矩陣）系數(shù)矩陣 約束條件系數(shù)矩陣的元素等于約束條件系數(shù)矩陣的元素等于0或者或者1. 約束條件矩陣的每一列有兩個(gè)非約束條件矩陣的每一列有兩個(gè)非0元素，這對應(yīng)于每一元素，這對應(yīng)于每一個(gè)變量在前個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約束方程中也個(gè)約束方程中也出現(xiàn)一次。出現(xiàn)一次。 所有結(jié)構(gòu)約束條件都是等式約束所有結(jié)構(gòu)約束條件都是等式約束 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和Page 7（2）產(chǎn)地）產(chǎn)地m3，銷售地，銷售地n4, 決策變量決策變量mn12個(gè)，個(gè)，約束方程約束方程m+n7個(gè)，秩個(gè)，秩

5、m+n-1=6，有一個(gè)多余約束條件。，有一個(gè)多余約束條件。產(chǎn)銷平衡（總產(chǎn)量總銷量）：產(chǎn)銷平衡（總產(chǎn)量總銷量）：任一約束都可由其它約束的線性組合描述，如：任一約束都可由其它約束的線性組合描述，如： 說明有一個(gè)多余約束方程，解中非零變量說明有一個(gè)多余約束方程，解中非零變量xij的個(gè)數(shù)不大于的個(gè)數(shù)不大于m+n-1（這也只有產(chǎn)銷平衡問題才有）（這也只有產(chǎn)銷平衡問題才有）Page 8變化：變化： 1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等；）有時(shí)目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束

6、條件（等式或不等式約束約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。地（產(chǎn)大于銷時(shí)）。定理定理: 設(shè)有設(shè)有m個(gè)產(chǎn)地個(gè)產(chǎn)地n個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變量數(shù)為量數(shù)為m+n-1。Page 9表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單純實(shí)質(zhì)是單純形法。形法。步驟步驟描述描述方法方法第一步第一步求初始基行可行解（初始調(diào)運(yùn)方案）求初始基行可行解（初始調(diào)運(yùn)方案）西北角法、西北角法、最小元素法、最小元素法、元素差額

7、法元素差額法 第二步第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)數(shù)檢驗(yàn)數(shù) ij ij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)數(shù) ij ij 00，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位閉回路法和位勢法勢法第三步第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對原運(yùn)調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步閉回路法閉回路法Page 10 方法一：西北角法方法一：西北角法 優(yōu)先滿足左上角。優(yōu)先滿足左上角。例：例：結(jié)束標(biāo)志：所有

8、行、列均被劃去；找到結(jié)束標(biāo)志：所有行、列均被劃去；找到m+n-1個(gè)非零變量（即基變量的值）個(gè)非零變量（即基變量的值）Z372B1B2B3B4產(chǎn)量 aiA18 48 12 4 1116 8 0A2 2 6 10 4 3 910 4 0A3 8 5 8 1114 622 14 0銷量 bj8 014 6 012 8 014 0總計(jì)48Page 11方法二：最小元素法方法二：最小元素法 優(yōu)先滿足單位運(yùn)價(jià)最小或運(yùn)距最短的業(yè)務(wù)需求。優(yōu)先滿足單位運(yùn)價(jià)最小或運(yùn)距最短的業(yè)務(wù)需求。例：例：結(jié)束標(biāo)志：所有行、列均被劃去；找到結(jié)束標(biāo)志：所有行、列均被劃去；找到m+n-1個(gè)非零變量（即基變量的值）個(gè)非零變量（即基變量

9、的值）Z246B1B2B3B4產(chǎn)量 aiA1 4 1210 46 1116 6 0A28 2 102 3 910 2 0A3 8 14 5 118 622 8 0銷量 bj8 014 012 10 014 6 0總計(jì)48Page 12 方法三：沃格爾法（伏格爾法）方法三：沃格爾法（伏格爾法） 找出每行、每列的最小運(yùn)價(jià)和次小運(yùn)價(jià)，二者的差值稱為該行（列）的罰數(shù)。若該找出每行、每列的最小運(yùn)價(jià)和次小運(yùn)價(jià)，二者的差值稱為該行（列）的罰數(shù)。若該行（列）的罰數(shù)很大時(shí)，應(yīng)盡可能按最小運(yùn)價(jià)的路線安排運(yùn)輸，否則運(yùn)費(fèi)損失會(huì)很大。行（列）的罰數(shù)很大時(shí)，應(yīng)盡可能按最小運(yùn)價(jià)的路線安排運(yùn)輸，否則運(yùn)費(fèi)損失會(huì)很大。結(jié)束標(biāo)志：

10、所有行、列均被劃去；找到結(jié)束標(biāo)志：所有行、列均被劃去；找到m+n-1個(gè)非零變量（即基變量的值）個(gè)非零變量（即基變量的值）Z244B1B2B3B4產(chǎn)量 ai行罰數(shù)A1 4 1212 44 1116 4 000070A28 2 10 32 910 2 011160A3 8 14 5 118 622 8 012銷量bj8 014 012 014 6 4 0總計(jì)48列罰數(shù) 2 5 1 3 2 1 3 2 1 2 1 2 2Page 13用元素差額法求得的基本可行解更接近最優(yōu)解，所用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。以也稱為近似方案。Page 14求出一組基可行解后，判斷是否為

11、最優(yōu)解，仍然是用檢求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來判斷，記驗(yàn)數(shù)來判斷，記xij的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為ij由第一章知，求最小值的運(yùn)由第一章知，求最小值的運(yùn)輸問題的最優(yōu)判別準(zhǔn)則是：輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)求檢驗(yàn)數(shù)的方法有兩種：求檢驗(yàn)數(shù)的方法有兩種： 閉回路法閉回路法 位勢法（位勢法（）Page 15閉回路的概念閉回路的概念閉回路：從某空格某空格出發(fā)，水平或垂直劃線，遇到數(shù)字格（不遇到數(shù)字格（不是必須）拐是必須）拐90彎彎, 指向下一個(gè)數(shù)字格指向下一個(gè)數(shù)字格，直至回到起點(diǎn)空格回到起點(diǎn)空格。對于每個(gè)

12、空格，無論起始是水平劃線還是垂直劃線，這樣的閉回路都是唯一唯一的。解釋：解釋：空格（非基變量）的系數(shù)列向量可由m+n-1個(gè)基變量的系數(shù)列向量（線性無關(guān)）的線性組合唯一表示。 例：空格x11（非基變量），數(shù)字格x13、x23、x21（基變量）Page 16 非基變量（空格）對應(yīng)的檢驗(yàn)數(shù)：閉回路上從空格開始各頂點(diǎn)的運(yùn)價(jià)交替加減。若有檢驗(yàn)數(shù)0,則非最優(yōu)。 經(jīng)濟(jì)解釋：若將若將X11的運(yùn)輸量由的運(yùn)輸量由0調(diào)整為調(diào)整為1,為了產(chǎn)銷平衡，閉回路上的為了產(chǎn)銷平衡，閉回路上的X13 的運(yùn)輸量的運(yùn)輸量應(yīng)該減少應(yīng)該減少1, X23增加增加1 ，X21減少減少1。這樣的調(diào)整使得運(yùn)費(fèi)發(fā)生了改變：。這樣的調(diào)整使得運(yùn)費(fèi)發(fā)生

13、了改變：C11-C13+C23-C21=4-4+3-2=1。因此非基變量。因此非基變量X11的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)10，說明這樣的調(diào)整會(huì)使得運(yùn)費(fèi)增，說明這樣的調(diào)整會(huì)使得運(yùn)費(fèi)增加，加， X110是更明智的選擇。相反的，若運(yùn)費(fèi)減少（即檢驗(yàn)數(shù)是更明智的選擇。相反的，若運(yùn)費(fèi)減少（即檢驗(yàn)數(shù)0，例如，例如24 ），），說明目前的方案是不經(jīng)濟(jì)的，未達(dá)最優(yōu)。說明目前的方案是不經(jīng)濟(jì)的，未達(dá)最優(yōu)。 B1B2B3B4產(chǎn)量 aiA1 411=1 1212=210 46 1116A28 2 1022=12 324=1 910A3 831=10 14 5 1133=128 622銷量 bj8141214總計(jì)48 若所有空格的檢

14、驗(yàn)數(shù)若所有空格的檢驗(yàn)數(shù)ij ij 0 0，現(xiàn)在的方案已，現(xiàn)在的方案已是最優(yōu)方案。是最優(yōu)方案。Page 17用位勢法對初始方案進(jìn)行最優(yōu)性檢驗(yàn)：用位勢法對初始方案進(jìn)行最優(yōu)性檢驗(yàn)：1）由）由 ij=Cij-（Ui+Vj）計(jì)算位勢）計(jì)算位勢Ui ， Vj ，因?qū)兞慷杂?，因?qū)兞慷杂?ij=0，即，即Cij-（Ui+Vj） = 0，令，令U1=02）再由）再由 ij=Cij-（Ui+Vj）計(jì)算非基變量的檢驗(yàn)數(shù)）計(jì)算非基變量的檢驗(yàn)數(shù) ij當(dāng)存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) kl 0，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。還可以進(jìn)一步

15、減小。Page 18計(jì)算對偶變量ui 、vj 基變量的檢驗(yàn)數(shù)基變量的檢驗(yàn)數(shù)0 4（ u1 v3 ）=0 7個(gè)未知數(shù)，個(gè)未知數(shù)，6個(gè)方程，解不唯一。個(gè)方程，解不唯一。 11（ u1 v4 ）=0 任意賦值使任意賦值使u11， 2（ u2 v1 ）=0 算出算出 u20 u3 4 3（ u2 v3 ）=0 v12 v2 9 v3 3 v410 5（ u3 v2 ）=0 6（ u3 v4 ）=0計(jì)算非基變量的檢驗(yàn)數(shù)ij cij（ ui vj ）例：例：11 c11（ u1 v1 ）4-1-2=1B1B2B3B4產(chǎn)量 aiA1 411=1 1212=210 46 1116u1A28 222=1 102

16、 324=1 910u2A331=10 8 14 533=12 118 622u3銷量 bj8141214總計(jì)48v1v2v3v4Page 19當(dāng)存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) kl 0 且且 kl =min ij時(shí)，令時(shí)，令Xkl 進(jìn)進(jìn)基。從表中知可選基。從表中知可選X24進(jìn)基。進(jìn)基。第第3步步 確定換入基的變量確定換入基的變量第第4步步 確定換出基的變量確定換出基的變量以進(jìn)基變量以進(jìn)基變量xik為起點(diǎn)的閉回路中，從起點(diǎn)（空格、非基變量）為起點(diǎn)的閉回路中，從起點(diǎn)（空格、非基變量）開始，奇點(diǎn)增加運(yùn)量，偶點(diǎn)減少運(yùn)量，在保證產(chǎn)銷平衡的條開始，奇點(diǎn)增加運(yùn)量，偶點(diǎn)減少運(yùn)量，在保證產(chǎn)銷平衡的

17、條件下盡可能的增大起點(diǎn)運(yùn)量。件下盡可能的增大起點(diǎn)運(yùn)量。Page 20表上作業(yè)法的計(jì)算步驟：表上作業(yè)法的計(jì)算步驟：分析實(shí)際問題列出產(chǎn)銷平分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小確定初始調(diào)運(yùn)方案（最小元素法或元素法或Vogel法）法）求檢驗(yàn)數(shù)（位勢法）求檢驗(yàn)數(shù)（位勢法）所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0找出絕對值最大的負(fù)檢驗(yàn)數(shù)，用閉合找出絕對值最大的負(fù)檢驗(yàn)數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案回路調(diào)整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運(yùn)價(jià)算出總運(yùn)價(jià)Page 21（1）若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)）若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)

18、數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對應(yīng)的變量為中最小者對應(yīng)的變量為換入變量。換入變量。（2）無窮多最優(yōu)解）無窮多最優(yōu)解產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。，則該問題有無窮多最優(yōu)解。Page 22 退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)時(shí)則需要同時(shí)劃去一行

19、和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證，以保證有有(m+n-1)個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個(gè)任意空格處加一個(gè)0即可。即可。 Page 232.目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。 minjijijxCZ11max njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 24求解方法：求解方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價(jià)將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價(jià)表為表為C ，用一個(gè)較大的數(shù)，用一

20、個(gè)較大的數(shù)M（Mmaxcij）去減每一個(gè)）去減每一個(gè)cij得得到矩陣到矩陣C，其中，其中C=（Mcij）0,將將C作為極小化問題的運(yùn)作為極小化問題的運(yùn)價(jià)表，用表上用業(yè)法求出最優(yōu)解。價(jià)表，用表上用業(yè)法求出最優(yōu)解。Page 25例例3.3 下列矩陣下列矩陣C是是Ai（I=1，2，3）到）到Bj的噸公里利潤的噸公里利潤,運(yùn)輸運(yùn)輸部門如何安排運(yùn)輸方案使總利潤最大部門如何安排運(yùn)輸方案使總利潤最大. 銷地銷地產(chǎn)地產(chǎn)地B1B2B3產(chǎn)量產(chǎn)量A1A2A3銷量銷量ijijijccccM 10,10max/22取取Page 263.當(dāng)總產(chǎn)量與總銷量不相等時(shí)當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問題稱為不平衡運(yùn)輸問

21、題.這類這類運(yùn)輸問題在實(shí)際中常常碰到運(yùn)輸問題在實(shí)際中常常碰到,它的求解方法是將不平衡問題它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解?；癁槠胶鈫栴}再按平衡問題求解。 當(dāng)產(chǎn)大于銷時(shí)，即：當(dāng)產(chǎn)大于銷時(shí)，即： minjjiba11數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 27由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉庫，假設(shè)該倉庫為一個(gè)虛擬必須就地

22、庫存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉庫，假設(shè)該倉庫為一個(gè)虛擬銷地銷地Bn+1， bn+1作為一個(gè)虛設(shè)銷地作為一個(gè)虛設(shè)銷地Bn+1的銷量的銷量(即庫存量即庫存量)。各產(chǎn)地。各產(chǎn)地Ai到到Bn+1的運(yùn)價(jià)為零，即的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，m）。則平衡問題的）。則平衡問題的數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min , 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具體求解時(shí)具體求解時(shí), ,只在只在運(yùn)價(jià)表右端增加運(yùn)價(jià)表右端增加一列一列B Bn n+1+1，運(yùn)價(jià)，運(yùn)價(jià)為零為零, ,銷量為銷量為b bn n+1+1即

23、可即可Page 28 當(dāng)銷大于產(chǎn)時(shí)，即：當(dāng)銷大于產(chǎn)時(shí)，即： minjjiba11 minjijijxCZ11min , 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 111jmixnjbxmiaxijmijijnjiij數(shù)學(xué)模型為：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)由于總銷量大于總產(chǎn)量量,故一定有些需求地故一定有些需求地不完全滿足不完全滿足,這時(shí)虛設(shè)這時(shí)虛設(shè)一個(gè)產(chǎn)地一個(gè)產(chǎn)地Am+1，產(chǎn)量，產(chǎn)量為：為： miinjjab11Page 29銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為 ： minjijijxcZ11min njmixnjbxmiaxijmijijnjij

24、i, 2 , 11, 2 , 1, 0, 2 , 11, 2 , 1111；具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)，運(yùn)價(jià)為零。產(chǎn)量為量為am+1即可。即可。 Page 30例例3.4 求下列表中極小化運(yùn)輸問題的最優(yōu)解。求下列表中極小化運(yùn)輸問題的最優(yōu)解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160 4141160180ijjiba因?yàn)橛校阂驗(yàn)橛校篜age 31所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表中所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表中A2不可達(dá)不可達(dá)B1，用一個(gè)，用一個(gè)很大的

25、正數(shù)很大的正數(shù)M表示運(yùn)價(jià)表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷量為。虛設(shè)一個(gè)銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，表的右邊增添一列 ，得到新的運(yùn)價(jià)表。，得到新的運(yùn)價(jià)表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180Page 32下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地A4還有還有20個(gè)單位沒有運(yùn)出。個(gè)單位沒有運(yùn)出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180Page 33例例 設(shè)有三個(gè)化肥

26、廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。各化肥廠年產(chǎn)量，各設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各地區(qū)運(yùn)送化肥的單位運(yùn)價(jià)如下表：地區(qū)年需要量及從各地區(qū)運(yùn)送化肥的單位運(yùn)價(jià)如下表：試求出總運(yùn)費(fèi)最省的花費(fèi)調(diào)運(yùn)方案。試求出總運(yùn)費(fèi)最省的花費(fèi)調(diào)運(yùn)方案。B1B2B3B4產(chǎn)量產(chǎn)量A11613221750A21413191560A319202350最低需求最低需求3070010最高需求最高需求507030不限不限Page 34B1B1B2B3B4B4產(chǎn)量產(chǎn)量 aiA150A260A350A4(虛擬虛擬)M0M0M050銷量銷量302070301050210最多分配到最多分配到60B1B2B3

27、B4產(chǎn)量產(chǎn)量A150A260A350最低需最低需求求3070010總產(chǎn)量總產(chǎn)量160最低總需求量最低總需求量110實(shí)際最高總需求量實(shí)際最高總需求量210最高需最高需求求507030不限不限最低需求是必須滿足的，不最低需求是必須滿足的，不可由虛擬產(chǎn)地提供可由虛擬產(chǎn)地提供Page 35B1B1B2B3B4B4產(chǎn)量產(chǎn)量 aiA15050A220103060A33020050A4(虛擬虛擬) 30 2050銷量銷量302070301050210Page 36B1B2B3產(chǎn)量產(chǎn)量A12436a1 11A2156a2=7A3324a34使用量使用量1046Page 37 1 各產(chǎn)地的產(chǎn)品可以運(yùn)到某產(chǎn)地再集

28、中運(yùn)到某銷售地；各產(chǎn)地的產(chǎn)品可以運(yùn)到某產(chǎn)地再集中運(yùn)到某銷售地； 2 某產(chǎn)地產(chǎn)品可以先運(yùn)到某銷售地再分運(yùn)到其他銷售地；某產(chǎn)地產(chǎn)品可以先運(yùn)到某銷售地再分運(yùn)到其他銷售地； 3 中轉(zhuǎn)站可實(shí)現(xiàn)產(chǎn)品在產(chǎn)地間、銷售地間、產(chǎn)銷間的轉(zhuǎn)運(yùn)。中轉(zhuǎn)站可實(shí)現(xiàn)產(chǎn)品在產(chǎn)地間、銷售地間、產(chǎn)銷間的轉(zhuǎn)運(yùn)。擴(kuò)大的運(yùn)輸問題：每個(gè)產(chǎn)地、中轉(zhuǎn)站、銷售地都擴(kuò)大的運(yùn)輸問題：每個(gè)產(chǎn)地、中轉(zhuǎn)站、銷售地都可能有產(chǎn)品運(yùn)進(jìn)，也都可能有產(chǎn)品運(yùn)出，因此都可可能有產(chǎn)品運(yùn)進(jìn)，也都可能有產(chǎn)品運(yùn)出，因此都可以看作產(chǎn)地，也都可以看作銷售地。以看作產(chǎn)地，也都可以看作銷售地。Page 38產(chǎn)地中轉(zhuǎn)站銷售地產(chǎn)量A1A2A3T1T2T3T4B1B2B3B4產(chǎn)地A1A2A3

29、中轉(zhuǎn)站T1T2T3T4M銷售地B1B2B3B4銷售量虛擬產(chǎn)地、中轉(zhuǎn)站、銷售地虛擬產(chǎn)地、中轉(zhuǎn)站、銷售地運(yùn)價(jià)運(yùn)價(jià)cij0（當(dāng)（當(dāng)ij）對于不存在的路線（即不可能的運(yùn)對于不存在的路線（即不可能的運(yùn)輸方案），運(yùn)價(jià)輸方案），運(yùn)價(jià)cijM各產(chǎn)地產(chǎn)量原各產(chǎn)地產(chǎn)量原產(chǎn)量轉(zhuǎn)運(yùn)總量產(chǎn)量轉(zhuǎn)運(yùn)總量各中轉(zhuǎn)站產(chǎn)量各中轉(zhuǎn)站產(chǎn)量轉(zhuǎn)運(yùn)總量轉(zhuǎn)運(yùn)總量各銷售地產(chǎn)量各銷售地產(chǎn)量轉(zhuǎn)運(yùn)總量轉(zhuǎn)運(yùn)總量各產(chǎn)地銷售量各產(chǎn)地銷售量轉(zhuǎn)運(yùn)總量轉(zhuǎn)運(yùn)總量各中轉(zhuǎn)站銷售量各中轉(zhuǎn)站銷售量轉(zhuǎn)運(yùn)總量所有產(chǎn)轉(zhuǎn)運(yùn)總量所有產(chǎn)地總產(chǎn)量地總產(chǎn)量各銷售地銷售量原各銷售地銷售量原銷售量轉(zhuǎn)運(yùn)總量銷售量轉(zhuǎn)運(yùn)總量Page 394. 生產(chǎn)與儲(chǔ)存問題生產(chǎn)與儲(chǔ)存問題例例 某廠按合同規(guī)定須于當(dāng)

30、年每個(gè)季度末分別提供某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。季度季度生產(chǎn)能力生產(chǎn)能力/臺(tái)臺(tái)單位成本單位成本/萬元萬元2510.83511.130111

31、011.3Page 40解：解： 設(shè)設(shè) xij為第為第 i 季度生產(chǎn)的第季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：么應(yīng)滿足：交貨：交貨： x11 = 10 生產(chǎn)：生產(chǎn)：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10把第把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠的產(chǎn)量；把第個(gè)生產(chǎn)廠的產(chǎn)量；把第 j 季季度交貨的柴油機(jī)數(shù)目看作第度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷售點(diǎn)的銷量；設(shè)個(gè)銷售點(diǎn)的銷量；設(shè)cij是第是第i季度生季度生產(chǎn)的第產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本，應(yīng)該等于該季度單位季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本，應(yīng)該等于該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用?？蓸?gòu)造下列產(chǎn)銷平衡問題：成本加上儲(chǔ)存、維護(hù)等費(fèi)用?？蓸?gòu)造下列產(chǎn)銷平衡問題：Page 41 ji產(chǎn)量產(chǎn)量10.810.95