運(yùn)籌學(xué)-第3章運(yùn)輸問(wèn)題完整版

1、 2 從從m個(gè)發(fā)點(diǎn)個(gè)發(fā)點(diǎn) 向向n個(gè)收點(diǎn)個(gè)收點(diǎn) 發(fā)送某種貨物發(fā)送某種貨物. 發(fā)點(diǎn)的發(fā)發(fā)點(diǎn)的發(fā) 量為量為 ， 收點(diǎn)的收量為收點(diǎn)的收量為 。由。由 運(yùn)運(yùn) 往往 單位貨物的運(yùn)費(fèi)為單位貨物的運(yùn)費(fèi)為 ，問(wèn)如何調(diào)配，問(wèn)如何調(diào)配， 才能使運(yùn)費(fèi)最省？才能使運(yùn)費(fèi)最?。?問(wèn)題的提出問(wèn)題的提出 m AAA, 21 n BBB, 21 j B i A i aj b i A j B ji c .題否則稱(chēng)為非平衡運(yùn)輸問(wèn) 運(yùn)輸問(wèn)題，稱(chēng)此運(yùn)輸問(wèn)題為平衡若 ji ba 3 表表1 產(chǎn)銷(xiāo)平衡表產(chǎn)銷(xiāo)平衡表 銷(xiāo)銷(xiāo)地地 產(chǎn)產(chǎn)地地 1 2 n 產(chǎn)產(chǎn)量量 1 a1 2 a2 m am 銷(xiāo)銷(xiāo)量量 b1 b2 bn 上述數(shù)據(jù)可以匯總上述數(shù)據(jù)可以

2、匯總 于表格中于表格中, ,如下如下: : 表表2 單位運(yùn)價(jià)表單位運(yùn)價(jià)表 銷(xiāo)地銷(xiāo)地 產(chǎn)地產(chǎn)地 1 2 n 1 c11 c12 c1n 2 c21 c22 c2n m cm1 cm2 cmn 4 運(yùn)輸問(wèn)題的數(shù)學(xué)模型 設(shè)設(shè)xij代表為從第代表為從第i個(gè)產(chǎn)地調(diào)運(yùn)給第個(gè)產(chǎn)地調(diào)運(yùn)給第j個(gè)銷(xiāo)地的物資個(gè)銷(xiāo)地的物資 的數(shù)量的數(shù)量.在產(chǎn)銷(xiāo)平衡的條件下，即在產(chǎn)銷(xiāo)平衡的條件下，即 使總的運(yùn)費(fèi)支出最小，可以表為以下數(shù)學(xué)形式：使總的運(yùn)費(fèi)支出最小，可以表為以下數(shù)學(xué)形式： n j j m i i ba 11 0 , 1 , 1 . . min 1 1 11 ij j m i ij i n j ij m i n j ijij

3、 x njbx miax ts xcz 5 運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣及特征運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣及特征 111212122212 11.1 11.1 . 11.1 111 11. . .1 111 nnmmmn xxxxxxxxx A 矩陣矩陣A是一個(gè)是一個(gè)m+n行行mn列的矩陣，它的秩為列的矩陣，它的秩為m+n-1。 運(yùn)輸問(wèn)題應(yīng)該有運(yùn)輸問(wèn)題應(yīng)該有m+n-1個(gè)基變量。個(gè)基變量。 3. xij的系數(shù)列向量為：的系數(shù)列向量為： m行 n行 (0.1.0.1.0)T ijimj Pee 6 表上作業(yè)法表上作業(yè)法 7 表上作業(yè)法的基本思路：表上作業(yè)法的基本思路： 確定初始調(diào)運(yùn)方案確定初始調(diào)運(yùn)

4、方案 最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) 改進(jìn)方案改進(jìn)方案 8 1 確定初始基可行解確定初始基可行解 運(yùn)輸問(wèn)題確定初始基可行解，就是求出運(yùn)輸問(wèn)運(yùn)輸問(wèn)題確定初始基可行解，就是求出運(yùn)輸問(wèn) 題的初始調(diào)運(yùn)方案題的初始調(diào)運(yùn)方案. 確定初始基可行解的方法有確定初始基可行解的方法有 最小元素法最小元素法 伏格爾法伏格爾法 9 【例例2-12-1】 某公司經(jīng)銷(xiāo)甲產(chǎn)品某公司經(jīng)銷(xiāo)甲產(chǎn)品, ,下設(shè)下設(shè)3 3個(gè)加工廠個(gè)加工廠A A1 1、 A A2 2、A A3 3，產(chǎn)品分別運(yùn)往銷(xiāo)售點(diǎn)，產(chǎn)品分別運(yùn)往銷(xiāo)售點(diǎn)B1、B2、B3、B4，各工廠，各工廠 的日產(chǎn)量和各銷(xiāo)售點(diǎn)的日需求量及各工廠到各銷(xiāo)售點(diǎn)的日產(chǎn)量和各銷(xiāo)售點(diǎn)的日需求量及各工廠到各銷(xiāo)

5、售點(diǎn) 的運(yùn)價(jià)如下表所示的運(yùn)價(jià)如下表所示：（：（運(yùn)輸問(wèn)題供需平衡表和運(yùn)價(jià)表運(yùn)輸問(wèn)題供需平衡表和運(yùn)價(jià)表 如下），求總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。如下），求總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。 銷(xiāo)地 產(chǎn)地 B1B2B3B4 發(fā)量 （T） A13113107 A219284 A3741059 收量（T） 3656 表3-3 10 思路：思路：為了減少運(yùn)費(fèi)，應(yīng)優(yōu)先考慮單位運(yùn)價(jià)最小(或 運(yùn)距最短)的供銷(xiāo)業(yè)務(wù)，最大限度地滿(mǎn)足其供銷(xiāo)量。在可 供物品已用完的產(chǎn)地或需求已全部滿(mǎn)足的銷(xiāo)地，以后將不 再考慮。然后，在余下的供、銷(xiāo)點(diǎn)的供銷(xiāo)關(guān)系中，繼續(xù)按 上述方法安排調(diào)運(yùn)，直至安排完所有供銷(xiāo)任務(wù)，得到一個(gè) 完整的調(diào)運(yùn)方案(完整的解)為止。這樣

6、就得到了運(yùn)輸問(wèn)題 的一個(gè)初始基可行解(初始調(diào)運(yùn)方案)。 由于該方法基于優(yōu)先滿(mǎn)足單位運(yùn)價(jià)(或運(yùn)距)最小的供 銷(xiāo)業(yè)務(wù)，故稱(chēng)為最小元素法。 1、最小元素法、最小元素法 11 1. 最小元素法最小元素法 銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1 B2 B3 B4 產(chǎn)產(chǎn)量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 銷(xiāo)銷(xiāo)量量 3 6 5 6 3 1 4 6 3 3 Z=4Z=43+33+310+310+31+11+12+62+64+34+35=865=86 該方案總運(yùn)費(fèi)：該方案總運(yùn)費(fèi)： （思想：就近供應(yīng)）（思想：就近供應(yīng)） 不不 能能 同同 時(shí)時(shí) 劃劃 去去 行行 和和 列列 保證填保

7、證填 有運(yùn)量有運(yùn)量 的格子的格子 為為m+n- 1 表3-4 12 最小元素法，有時(shí)按某一最小單位運(yùn)價(jià)優(yōu)先安排 物品調(diào)運(yùn)時(shí)，卻可能在其他供銷(xiāo)點(diǎn)多花幾倍的運(yùn)費(fèi)， 從而使整個(gè)運(yùn)輸費(fèi)用增加。 55 5 5 2. 沃格爾法沃格爾法 沃格爾法考慮到： 一個(gè)產(chǎn)地的產(chǎn)品假如不能按照最小 運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有個(gè)差額。 如果差 額不大，當(dāng)不能按最小單位運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損 失不大；反之，如果差額很大，不按最小運(yùn)價(jià)組織運(yùn)輸就 會(huì)造成很大損失，故應(yīng)盡量按最小單位運(yùn)價(jià)安排運(yùn)輸。沃 格爾法就是基于這種考慮提出來(lái)的。 13 沃格爾法計(jì)算步驟：沃格爾法計(jì)算步驟： 1) 分別算出各行、各列的最小運(yùn)費(fèi)與次

8、小運(yùn)費(fèi)的差額。 2) 從行、列中選出差額最大者，選擇它所在行、列中的 最小元素，進(jìn)行運(yùn)量調(diào)整。 3) 對(duì)剩余行、列再分別計(jì)算各行、列的差額。返回1)、 2)。 14 2.伏格爾法伏格爾法 2 5 1 3 0 1 1 表表3-6 6 2 1 3 0 1 2 3 2 1 2 0 1 3 1 2 7 6 52 1 表3-5 Z=85 15 v1 若有兩個(gè)以上相同的最大差值，可任取其 一。 v2 剩下一行或者一列有空格，填數(shù)字，不能 劃掉。 v3 計(jì)算行差，列差時(shí)，已經(jīng)劃去的列或者行 不再考慮。 16 銷(xiāo) 產(chǎn) B1B2B3產(chǎn)量 A151 812 A224114 A33 674 銷(xiāo)量 91011 例例

9、用用伏格爾法伏格爾法求初始調(diào)運(yùn)方案求初始調(diào)運(yùn)方案 17 銷(xiāo) 產(chǎn) B1B2B3產(chǎn)量 A1210 12 A231114 A34 4 銷(xiāo)量 91011 初始調(diào)運(yùn)方案 18 2.2 最優(yōu)解的判別最優(yōu)解的判別 判別辦法是計(jì)算判別辦法是計(jì)算空格空格(非基變量非基變量)的檢驗(yàn)數(shù)的檢驗(yàn)數(shù),因?yàn)檫\(yùn)因?yàn)檫\(yùn) 輸問(wèn)題的目標(biāo)函數(shù)是實(shí)現(xiàn)最小化輸問(wèn)題的目標(biāo)函數(shù)是實(shí)現(xiàn)最小化,所以當(dāng)所有空格處所以當(dāng)所有空格處 的的檢驗(yàn)數(shù)大于等于零檢驗(yàn)數(shù)大于等于零時(shí)時(shí),為最優(yōu)解為最優(yōu)解. 下面分別介紹兩種計(jì)算檢驗(yàn)數(shù)的方法下面分別介紹兩種計(jì)算檢驗(yàn)數(shù)的方法: 閉回路法閉回路法 (2) 位勢(shì)法位勢(shì)法 19 閉回路法閉回路法 閉回路：從閉回路：從空格空

10、格出發(fā)畫(huà)出發(fā)畫(huà)水平水平(或垂直或垂直)直線，遇到直線，遇到 填有運(yùn)量填有運(yùn)量的方格（數(shù)字格）的方格（數(shù)字格）可轉(zhuǎn)可轉(zhuǎn)90，然后繼續(xù)前進(jìn)，然后繼續(xù)前進(jìn) ，直到到達(dá)出發(fā)的空格所形成的閉合回路。，直到到達(dá)出發(fā)的空格所形成的閉合回路。 調(diào)運(yùn)方案的任意空格一定存在唯一閉回路。調(diào)運(yùn)方案的任意空格一定存在唯一閉回路。 銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1B2B3B4供量供量 A1 5 27 A23 14 A3 6 39 銷(xiāo)量銷(xiāo)量 3656 表3-7 20 5 10 4 7A3 8 2 9 1A2 10 3 11 3A1 B4B3B2B1 銷(xiāo)地 產(chǎn)地 6 3 3 4 3 1 計(jì)算最小元素法得到的初始基可行解的檢驗(yàn)數(shù)計(jì)算最小元素法

11、得到的初始基可行解的檢驗(yàn)數(shù) (+1) (-1) (+1) (-1) (+1)(+1)3+(-1)3+(-1)3+(+1)3+(+1)2+(-1)2+(-1)1=11=1 調(diào)整后總運(yùn)費(fèi)增加：調(diào)整后總運(yùn)費(fèi)增加： 空格處 檢驗(yàn)數(shù) 為1 表3-8 21 5 10 4 7A3 8 2 9 1A2 10 3 11 3A1 B4B3B2B1 銷(xiāo)地 產(chǎn)地 6 3 3 4 3 1 (+1) (-1) (+1) (-1) 7-5+10-3+2-1=107-5+10-3+2-1=10 調(diào)整后總運(yùn)費(fèi)增加：調(diào)整后總運(yùn)費(fèi)增加： 空格處 檢驗(yàn)數(shù) 為10 (-1) (+1) 表3-9 22 檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表 1 10 12

12、1-1 2 因?yàn)榇嬖谛∮诹愕臋z驗(yàn)數(shù)因?yàn)榇嬖谛∮诹愕臋z驗(yàn)數(shù),所以最小元素法給出的所以最小元素法給出的 方案不是最優(yōu)方案方案不是最優(yōu)方案. 表3-10 23 2. 位勢(shì)法 位勢(shì)位勢(shì)：運(yùn)輸問(wèn)題的對(duì)偶變量稱(chēng)為位勢(shì)。：運(yùn)輸問(wèn)題的對(duì)偶變量稱(chēng)為位勢(shì)。 因?yàn)橐驗(yàn)閙個(gè)供應(yīng)點(diǎn)個(gè)供應(yīng)點(diǎn)n個(gè)需求點(diǎn)的運(yùn)輸問(wèn)題有個(gè)需求點(diǎn)的運(yùn)輸問(wèn)題有m+n個(gè)約束，個(gè)約束， 因此運(yùn)輸問(wèn)題就有因此運(yùn)輸問(wèn)題就有m+n個(gè)位勢(shì)。個(gè)位勢(shì)。 行位勢(shì)行位勢(shì):關(guān)于供應(yīng)點(diǎn)關(guān)于供應(yīng)點(diǎn)Ai的約束對(duì)應(yīng)的對(duì)偶變量，記為的約束對(duì)應(yīng)的對(duì)偶變量，記為 ui, i=1,2,m。 列位勢(shì)列位勢(shì):關(guān)于需求點(diǎn)關(guān)于需求點(diǎn)Bj的約束對(duì)應(yīng)的對(duì)偶變量，記為的約束對(duì)應(yīng)的對(duì)偶變量，記為vj,

13、 j = 1,2,n。 24 定理定理：運(yùn)輸問(wèn)題變量運(yùn)輸問(wèn)題變量xij的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) ijijij cuv 1 11 0 1 (,.,.) 1 0 ijijBijijmnijij cC B Pcuuvvcuv 證明：證明： 25 位勢(shì)法位勢(shì)法 求檢驗(yàn)數(shù)的步驟求檢驗(yàn)數(shù)的步驟: 1.1.在表中下面和右面增加一行和一列在表中下面和右面增加一行和一列, ,列中添入列中添入ui, , 行中添入行中添入vj , ,令令u1=0, 按照按照 , 根據(jù)表中已有根據(jù)表中已有 的數(shù)字確定所有的的數(shù)字確定所有的ui及及vj ; jiij vuC 2.2.計(jì)算所有空格處的檢驗(yàn)數(shù)計(jì)算所有空格處的檢驗(yàn)數(shù). . )vu(

14、C jiijij 26 B 1 B 2 B 3 B 4 u i 311310 A 1 1928 A 2 74105 A 3 vj 2 -1 3 0 10 -5 9 檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表 1 2 1 -1 1012 24=-10，當(dāng)前方案，當(dāng)前方案 不是最優(yōu)方案。不是最優(yōu)方案。 最最 優(yōu)優(yōu) 方方 案案 判判 別別 準(zhǔn)準(zhǔn) 則則 表3-12 27 2.3 2.3 閉回路調(diào)整法改進(jìn)方案閉回路調(diào)整法改進(jìn)方案 xpq為換入變量為換入變量 =min1，3=1 從從( (p,qp,q) )空格開(kāi)始畫(huà)閉回路，其它轉(zhuǎn)角點(diǎn)都是空格開(kāi)始畫(huà)閉回路，其它轉(zhuǎn)角點(diǎn)都是 填有運(yùn)量的方格，并從填有運(yùn)量的方格，并從( (p,qp,q)

15、 )空格開(kāi)始給閉回路上空格開(kāi)始給閉回路上 的點(diǎn)按的點(diǎn)按+1+1，-1-1，+1+1，-1-1編號(hào)，編號(hào)，-1-1格的最小運(yùn)量格的最小運(yùn)量為為 調(diào)整量。調(diào)整量。 pqij 0min 表3-13 28 找到最小調(diào)整量以后找到最小調(diào)整量以后, ,按照閉回路上的正、負(fù)按照閉回路上的正、負(fù) 號(hào)，分別加上和減去此值，得到新的運(yùn)輸方案。號(hào)，分別加上和減去此值，得到新的運(yùn)輸方案。 銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1B2B3B4供量供量 A1 5 27 A23 14 A3 6 39 銷(xiāo)量銷(xiāo)量 3656 再用閉回路法或者位勢(shì)法求檢驗(yàn)數(shù)，得到下再用閉回路法或者位勢(shì)法求檢驗(yàn)數(shù)，得到下 表表: : 表表3-14 29 銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1B

16、2B3B4供量供量 A102 7 A22 14 A39 129 銷(xiāo)量銷(xiāo)量 3656 這時(shí)所有的檢驗(yàn)數(shù)都非負(fù)，表中的解就是最優(yōu)解這時(shí)所有的檢驗(yàn)數(shù)都非負(fù)，表中的解就是最優(yōu)解. . 表3-15 30 銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1B2B3B4供量供量 A137 6 45 A224 3 22 A34 38 53 銷(xiāo)量銷(xiāo)量 3322 例 求該運(yùn)輸問(wèn)題的最優(yōu)解 31 v表上作業(yè)法的計(jì)算步驟： 分析實(shí)際問(wèn)題列出產(chǎn)銷(xiāo)平分析實(shí)際問(wèn)題列出產(chǎn)銷(xiāo)平 衡表及單位運(yùn)價(jià)表衡表及單位運(yùn)價(jià)表 確定初始調(diào)運(yùn)方案（最小確定初始調(diào)運(yùn)方案（最小 元素法或伏格爾法）元素法或伏格爾法） 求檢驗(yàn)數(shù)閉回路或位勢(shì)法求檢驗(yàn)數(shù)閉回路或位勢(shì)法 所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)

17、0 找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合找出絕對(duì)值最大的負(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à) 32 （1）若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，）若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)， 在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù) 值得到改善，但通常取值得到改善，但通常取ij0中最小者對(duì)應(yīng)的變量為換入變量。中最小者對(duì)應(yīng)的變量為換入變量。 （2）無(wú)窮多最優(yōu)解）無(wú)窮多最優(yōu)解 產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的產(chǎn)銷(xiāo)平

18、衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的ij0， 則該問(wèn)題有無(wú)窮多最優(yōu)解。則該問(wèn)題有無(wú)窮多最優(yōu)解。 33 退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量 時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證，以保證 有有(m+n-1)個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的 任意空格處加一個(gè)任意空格處加一個(gè)0即可。即可。 利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的 最小運(yùn)量（超過(guò)最小運(yùn)量（超過(guò)2

19、個(gè)最小值）作為調(diào)整量個(gè)最小值）作為調(diào)整量，選擇任意一個(gè)最，選擇任意一個(gè)最 小運(yùn)量對(duì)應(yīng)的基變量作為換出變量，而經(jīng)調(diào)整后，得到退化小運(yùn)量對(duì)應(yīng)的基變量作為換出變量，而經(jīng)調(diào)整后，得到退化 解。這時(shí)另一個(gè)數(shù)字格必須填入一個(gè)解。這時(shí)另一個(gè)數(shù)字格必須填入一個(gè)“0”以示它為基變量。以示它為基變量。 34 銷(xiāo)地 產(chǎn)地 B1B2B3B4產(chǎn)量 A116 A210 A322 銷(xiāo)量 8141214 124114 8 31029 5116 (0)(2) (9) (2)(1) (12) 如下例中如下例中11檢驗(yàn)數(shù)是檢驗(yàn)數(shù)是 0，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。 其中綠色是非基變量檢驗(yàn)數(shù)，紅色為

20、分配量。其中綠色是非基變量檢驗(yàn)數(shù)，紅色為分配量。 35 銷(xiāo)地 產(chǎn)地 B1B2B3B4產(chǎn)量 A17 A24 A39 銷(xiāo)量 365620 11443 1 3778 2106 0 在在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選中任選一個(gè)變量作為基變量，例如選x34 例：用最小元素法求初始可行解例：用最小元素法求初始可行解 36 第三節(jié)第三節(jié) 產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其求解方法產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其求解方法 表上作業(yè)法是以產(chǎn)銷(xiāo)平衡為前提的：表上作業(yè)法是以產(chǎn)銷(xiāo)平衡為前提的： 11 mn ij ij ab 實(shí)際中，往往遇到產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題實(shí)際中，往往遇到產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題 1.1

21、.產(chǎn)大于銷(xiāo)（供過(guò)于求）產(chǎn)大于銷(xiāo)（供過(guò)于求） 11 mn ij ij ab 2.2.銷(xiāo)大于產(chǎn)（供不應(yīng)求）銷(xiāo)大于產(chǎn)（供不應(yīng)求） 11 mn ij ij ab 37 產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題向產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題向產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化 產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題：產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題： 11 mn ij ij ab 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 數(shù)學(xué)模型數(shù)學(xué)模型 38 設(shè)設(shè)xi n+1 是產(chǎn)地是產(chǎn)地Ai 的儲(chǔ)存量，化成標(biāo)準(zhǔn)形的

22、儲(chǔ)存量，化成標(biāo)準(zhǔn)形 1 11 1 1 1 min (1,2,.) . .(1,2,. ,1) 0,1,2,.,1,2,.1 mn ijij ij n iji j m ijj i ij zc x xaim s txbjn n xim jn 其中其中 ,1 1 11 0,1,. i n mn nij ij cim bab 引入虛擬的銷(xiāo)地引入虛擬的銷(xiāo)地( (儲(chǔ)存地儲(chǔ)存地) )（需求量為（需求量為 ），并令），并令 各個(gè)產(chǎn)地到虛擬銷(xiāo)地的單位運(yùn)費(fèi)為各個(gè)產(chǎn)地到虛擬銷(xiāo)地的單位運(yùn)費(fèi)為0 0。 11 mn ij ij ab 39 產(chǎn)小于銷(xiāo)的運(yùn)輸問(wèn)題：產(chǎn)小于銷(xiāo)的運(yùn)輸問(wèn)題： 11 mn ij ij ab 引入一個(gè)虛

23、擬的產(chǎn)地（產(chǎn)量等于引入一個(gè)虛擬的產(chǎn)地（產(chǎn)量等于 ），）， 并令該虛擬產(chǎn)地到各銷(xiāo)地的單位運(yùn)費(fèi)為并令該虛擬產(chǎn)地到各銷(xiāo)地的單位運(yùn)費(fèi)為0 0。 11 nm ji ji ba 40 總供應(yīng)量為總供應(yīng)量為1919千噸，而總需求量為千噸，而總需求量為1515千噸千噸 例例2： A1、A2、A3三個(gè)蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)三個(gè)蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)B1、 B2、B3、B4四個(gè)城市。已知三個(gè)產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計(jì)分四個(gè)城市。已知三個(gè)產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計(jì)分 別為別為7千噸、千噸、5千噸和千噸和7千噸；四個(gè)城市今年的蔬菜需求量分別千噸；四個(gè)城市今年的蔬菜需求量分別 為為2千噸、千噸、3千噸、千噸、4千噸

24、和千噸和6千噸；從每個(gè)蔬菜產(chǎn)地平均運(yùn)輸千噸；從每個(gè)蔬菜產(chǎn)地平均運(yùn)輸1 千噸蔬菜到各個(gè)城市的單位費(fèi)用千噸蔬菜到各個(gè)城市的單位費(fèi)用(萬(wàn)元萬(wàn)元)見(jiàn)下表，你能否替他見(jiàn)下表，你能否替他 們編制一個(gè)總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案？們編制一個(gè)總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案？ 單位運(yùn)費(fèi)單位運(yùn)費(fèi) B1B2B3B4 供應(yīng)量供應(yīng)量 A1211347 A2103595 A378127 需求量需求量 2346 41 需求地需求地 生產(chǎn)地生產(chǎn)地 B1B2B3B4B5供應(yīng)量供應(yīng)量 A12113407 A21035905 A3781207 需求量需求量23464 0 0 -2 2043 0 8 25 7 2 3 3 4 3 2 2 2

25、3 8 7 最優(yōu)解中最優(yōu)解中x15=2, x25=2，表示兩個(gè)產(chǎn)地沒(méi)有運(yùn)出去的蔬菜量。表示兩個(gè)產(chǎn)地沒(méi)有運(yùn)出去的蔬菜量。 42 假如例假如例2 2中各產(chǎn)地的蔬菜總產(chǎn)量不是中各產(chǎn)地的蔬菜總產(chǎn)量不是1919千噸，而是千噸，而是 1212千噸，就成了一個(gè)供不應(yīng)求的運(yùn)輸問(wèn)題。千噸，就成了一個(gè)供不應(yīng)求的運(yùn)輸問(wèn)題。 單位運(yùn)費(fèi)單位運(yùn)費(fèi) B1B2B3B4 供應(yīng)量供應(yīng)量 A1211343 A2103594 A378125 需求量需求量 2346 單位運(yùn)費(fèi)單位運(yùn)費(fèi) B1B2B3B4 供應(yīng)量供應(yīng)量 A1211344 A2103593 A378125 A400003 需求量需求量 2 346 引入一個(gè)虛擬產(chǎn)地引入一個(gè)虛

26、擬產(chǎn)地 43 例例3 3 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等量的設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等量的 化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地 區(qū)年需要量及從各個(gè)化肥廠到各地區(qū)單位化肥的運(yùn)價(jià)如下表區(qū)年需要量及從各個(gè)化肥廠到各地區(qū)單位化肥的運(yùn)價(jià)如下表 所示，試決定使總運(yùn)費(fèi)最省的化肥調(diào)撥方案。所示，試決定使總運(yùn)費(fèi)最省的化肥調(diào)撥方案。 需求地區(qū)需求地區(qū) 化肥廠化肥廠 IIIIIIIV 產(chǎn)量產(chǎn)量 （萬(wàn)噸）（萬(wàn)噸） A 1613221750 B 1413191560 C 192023-50 最低需求最低需求 （萬(wàn)噸）（萬(wàn)噸） 3070 0