1、第四章 運輸問題,一、運輸問題的數(shù)學(xué)模型,問題的提出,在許多大型連鎖超市的商品供應(yīng), 物流公司的物資供,應(yīng)都牽涉到眾多貨物的運輸問題. 這些問題最終都面臨,一個如何降低貨物運輸成本的問題. 該問題可用下面的,方式加以描述:,問題,設(shè)有某種物資, 該物資共有 個產(chǎn)地, 產(chǎn)地 的產(chǎn)量,的需求量為 且產(chǎn)量和需求量為相等.,分析 一個合適的運輸方案即是要確定從第 個產(chǎn)地,為 該物資另有 個銷售點, 銷售點,從產(chǎn)地 到銷售點 的單位運輸成本為 求一個運輸,方案, 使總運輸費用為最小.,到第 個需求點 的物資供應(yīng)量. 假設(shè)供應(yīng)量為 則,問題的約束條件為,而相應(yīng)的總運輸成本為,從而得到問題的數(shù)學(xué)模型,例1

2、試對下面的運輸問題建立相應(yīng)的數(shù)學(xué)模型.,解 由前面的討論容易得到相應(yīng)的數(shù)學(xué)模型:,注: 前面所討論的是產(chǎn)銷平衡的運輸問題. 若產(chǎn)銷不平,衡時, 相應(yīng)的模型將分為產(chǎn)大于銷或銷大于產(chǎn)的運輸問,題. 當(dāng)產(chǎn)大于銷時, 則問題的模型為:,而當(dāng)需求量大于供應(yīng)量時, 相應(yīng)的模型為,二、表上作業(yè)法,在上面的例中可以看到: 運輸問題的數(shù)學(xué)模型最終歸,結(jié)為一個線性規(guī)劃的模型, 并可用相應(yīng)的解法加以求解,但即使是一個簡單的運輸問題, 涉及到的變量也是比較,多的, 因而求解也較為困難. 這里將介紹一種新的解法:,表上作業(yè)法.,表上作業(yè)法的求解步驟:,求出一個初始可行解;,判定當(dāng)前解是否為最優(yōu)解;,解的調(diào)整.,求初始基

3、可行解,1.西北角法,用西北角法求運輸問題的初始解的要點是: 從西北角,開始按最大可能進行分配, 直到完成所有分配.,例2 用西北角法求下面運輸問題的初始解.,解 由西北角法, 首先分配 得,500,100,再對第二列及第三列進行分配, 即有下表,500,100,400,100,500,100,400,100,100,200,最后對第三行進行分配, 得下表,由此得初始解為,此時對應(yīng)的運輸成本為,注 1.用西北角法所得到問題的解與表中的單位運輸成,2.在表格中, 凡填入數(shù)據(jù)的單元 稱為基變量, 否則稱,3.基變量的個數(shù)應(yīng) 當(dāng)?shù)仁讲怀闪r, 則稱該,本無關(guān), 因而該解一般與最優(yōu)解的距離較“遠”;,

4、為非基變量.,解是退化的. 對退化問題, 需要虛擬基變量來補充基變量,的個數(shù), 其取值為0.,例3 用西北角法求下面問題的初始解,解 由西北角法, 容易得到問題的初始解,3,4,4,5,4,即: 問題的初始解為,并注意到該解是退化的. 此時可令,來增加基變,量的個數(shù).,2.最小元素法,最小元素法的基本想法是: 按最小成本進行分配.,例4 用最小元素法求下面運輸問題的初始解.,300,解 由最小元素法, 最小成本為 故,剩下的最小成本分別為,300,400,200,300,400,200,最后有,100,200,200,由此得到問題的初始解,此時對應(yīng)的運輸成本為,例5 用最小元素法求下面運輸問題

5、的初始解.,解 由最小元素法得:,3,1,4,8,3,1,即: 初始解為,最優(yōu)解的判定,為判斷當(dāng)前解是否為最優(yōu)解, 需要建立相應(yīng)的位勢.,若 為基變量, 則有,因基變量的個數(shù)為 故令 由此得到所有,為此定義位勢,的位勢.,例6 求下面運輸問題的初始解所對應(yīng)的位勢.,解 由位勢的定義, 及 是基變量,由此得到 同樣有,得 再由 及 得 同理,即有下表:,又,可得其它位勢:,例7 求下面運輸問題的初始解所對應(yīng)的位勢,解 由位勢的定義可分別得到,3,1,4,8,3,1,下面的例子說明對退化問題的處理方式,例8 求下面運輸問題的初始解所對應(yīng)的位勢,解 由位勢的定義可分別得到,此時, 因基變量的個數(shù),計

6、算下去. 為此, 虛擬基變量,勢:,故位勢無法再繼續(xù),再進一步計算位,3,4,4,5,4,由位勢, 再定義影響系數(shù) 其定義關(guān)系為: 若 為,非基變量, 則,例9 對下面問題求相應(yīng)的影響系數(shù).,解 因 為非基變量, 由影響系數(shù)的定義, 有,300,400,200,100,200,200,最優(yōu)解判定方法,當(dāng)前解是最優(yōu)解,解的調(diào)整,若當(dāng)前解不是最優(yōu)解, 則要進行適當(dāng)?shù)慕獾恼{(diào)整, 以,1.確定進基變量 :,2.對當(dāng)前進基變量 構(gòu)造一條閉回路:,降低運輸費用. 其具體步驟為,閉回路: 從當(dāng)前非基變量出發(fā), 以直線方式向前（后,注意到在閉回路上, 除出發(fā)頂點外, 其余頂點均為基,左, 右）前進, 遇到某一

7、個基變量變向, 直到回到起點.,變量頂點.,常見的幾種閉回路形式,3.在閉回路上確定最大調(diào)整量,首先在閉回路上給各頂點以編號: 出發(fā)頂點標(biāo)號為0,依次類推. 例如在下面的回路中, 各個頂點的編號為:,最大調(diào)整量 閉回路上編號為奇數(shù)頂點的最小運輸,例如在下面問題中, 則最大調(diào)整量,量.,4.求出新解,在閉回路上進行解的調(diào)整: 偶數(shù)頂點+ 奇數(shù)頂點,由此得到求解運輸問題的具體方法:,1.求出問題的初始解（一般用最小元素法）;,2.求出位勢及影響系數(shù), 從而判定是否為最優(yōu)解;,3.若不是最優(yōu)解, 則進行解的調(diào)整;,4.重新進行判定.,例10 求下面運輸問題的最小成本解,解 由西北角法得到問題的初始解

8、:,500,100,400,100,100,200,再求出相應(yīng)的位勢及影響系數(shù).,500,100,400,100,100,200,即有下表,500,100,400,100,100,200,由于 是最小的負數(shù), 故以 為進基變量, 構(gòu),即,造閉回路:,500,100,400,100,100,200,由此得最大調(diào)整量 從而得到新解. 注意到該解,是退化的, 因而需要虛擬基變量: 令并進一步計,算位勢和影響系數(shù):,500,100,400,100,100,200,500,100,400,200,200,0,500,100,400,200,200,0,最小影響系數(shù)為,閉回路為:,最大調(diào)整量 即有,500

9、,100,400,200,200,0,500,100,400,200,200,0,500,100,400,200,200,0,最小影響系數(shù)為,構(gòu)造閉回路:,500,100,400,200,200,0,最大調(diào)整量 由此得到新解:,500,100,400,200,200,0,再一次計算位勢和影響系數(shù), 得,300,300,200,200,200,200,由于 故當(dāng)前解為最優(yōu)解, 最優(yōu)解值,注 由于在上題的解題中的初始解是通過西北角法得到,的, 因而求解過程比較煩瑣. 下面我們用最小元素法求,解該問題.,例11 求下面問題的最小成本解,解 由最小元素法得問題的初始解,300,400,200,100,

10、200,200,進一步求出位勢及影響系數(shù):,300,400,200,100,200,200,最小影響系數(shù)為 閉回路為,最大調(diào)整量 由此得到新解:,300,400,200,100,200,200,300,300,200,200,200,200,注意到該解即為用西北角法求解過程中所得到的最優(yōu)解.,此例說明用最小元素法所得到的初始解一般情況下比,用西北角法得到的初始解更為優(yōu)越.,例12 求下面運輸問題的最小成本解.,解 由最小元素法得到問題的初始解:,11,1,7,8,10,3,對此初始解, 再求相應(yīng)的位勢和影響系數(shù):,最小影響系數(shù),即有下表:,閉回路為,最大調(diào)整量為 由此得到新解,計算相應(yīng)的位勢及

11、影響系數(shù):,最小影響系數(shù) 取 為進基變量, 則閉回,最大調(diào)整量為 由此得到新解:,路為,再計算位勢及影響系數(shù):,最小影響系數(shù) 取 為進基變量, 則閉回路為,最大調(diào)整量為,進一步計算位勢和影響系數(shù),最小影響系數(shù) 回路,最大調(diào)整量為 從而得到新解:,計算位勢和影響系數(shù), 得,因 故當(dāng)前解為最優(yōu)解, 且最小成本為,例13 求解下面的運輸問題:,解 由最小元素法得初始解:,4,5,3,5,1,2,計算位勢, 得,此時最小影響系數(shù) 回路為,最大調(diào)整量 由此得到新解,再計算位勢和影響系數(shù), 得,此時最小影響系數(shù) 回路為,最大調(diào)整量 由此得到新解,再計算位勢和影響系數(shù), 得,因 故當(dāng)前解為最優(yōu)解, 且最小成

12、本為,三、幾類特殊的運輸問題,在前面所討論的是產(chǎn)銷平衡的運輸問題, 實際工作中,遇到的更多的是產(chǎn)銷不平衡的運輸問題. 由于在處理中,是把產(chǎn)銷不平衡的運輸問題化為產(chǎn)銷平衡的運輸問題加,以解決, 故本段中我們將其歸為特殊的運輸問題來解決.,1.產(chǎn)銷不平衡的運輸問題,產(chǎn)大于銷的運輸問題,設(shè)運輸問題中, 產(chǎn)量總和大于需求量的總和, 即有,為此, 虛擬需求點 需求量為,運輸成本均為 從而將問題轉(zhuǎn)化為產(chǎn)銷平衡,的問題.,例14 求解運輸問題,解 虛擬第四個需求點, 由此得下表,由最小元素法, 容易得到問題的初始解:,計算位勢和影響系數(shù)得:,10,10,15,10,5,最小影響系數(shù) 回路,最大調(diào)整量 由此得

13、到新解,相應(yīng)的位勢和影響系數(shù)為,因 故當(dāng)前解為最優(yōu)解, 且最小成本為,銷大于產(chǎn)的運輸問題,為此, 虛擬產(chǎn)地 產(chǎn)量為,設(shè)運輸問題中, 需求量總和大于產(chǎn)量的總和, 即有,運輸成本均為,的問題.,從而將問題轉(zhuǎn)化為產(chǎn)銷平衡,例15 求下面運輸問題的最小費用解.,解 由前面討論, 虛擬產(chǎn)地 產(chǎn)量為,則有下表:,由最小元素法得問題的初始解, 并計算位勢和影響系數(shù),20,80,70,50,40,40,20,80,70,50,40,40,最小影響系數(shù) 回路,最大調(diào)整量 由此得到新解,最小影響系數(shù) 回路,最大調(diào)整量 由此得到新解:,因 故當(dāng)前解為最優(yōu)解, 且最小成本為,注: 在上題中, 若先分配,由此得到初始解

14、:,再計算相應(yīng)的位勢, 有,20,80,50,70,20,60,最小影響系數(shù)為,閉回路為,20,80,50,70,20,60,此時最大調(diào)整量為20, 繼續(xù)迭代, 所得到的解即為前面,解法中的初始解.,20,80,50,70,20,60,20,80,70,50,40,40,2.存在無通行路的運輸問題,所謂存在無通行路的運輸問題是指在一個運輸問題中,分析: 對所給條件, 為使 不能成為基變量, 可使相,產(chǎn)地 與需求點 之間不存在相應(yīng)的運輸線路. 在此種,情況下, 求運輸方案.,應(yīng)的運輸成本為最大的. 為此可設(shè) 再由前面所,提供的方法求出最優(yōu)解.,例16 求解下面的運輸問題:,解 由最小元素法得初始

15、解,50,10,30,40,20,注意到該解是退化的, 故需虛擬基變量. 但基變量需在,求位勢的過程中加以解決. 先求位勢:,此時, 位勢計算中斷, 問題在于初始解退化. 為此, 虛擬,基變量, 令 則有,此時最小影響系數(shù) 回路為,最大調(diào)整量 由此得到新解,計算位勢和影響系數(shù)后得:,因 故當(dāng)前解為最優(yōu)解, 且最小成本為,例17 有三個化肥廠供應(yīng)四個地區(qū)農(nóng)用化肥. 假設(shè)等量,的化肥在這些地區(qū)使用效果相同. 各化肥廠的年產(chǎn)量, 各,地區(qū)的需要量和各廠到各地的單位運價如下表所示, 求,總運費最省的調(diào)運方案.,解 此為產(chǎn)銷不平衡的運輸問題.,總產(chǎn)量為160, 四個地區(qū)的最低需求量為110, 最高需,求

16、量可以設(shè)為210. 因而是需求量大于產(chǎn)量的問題. 為此,虛設(shè)工廠. 再注意到各地區(qū)的需求量分為兩部分, 一部分,是必須滿足的, 另一部分是可以不滿足的. 由此產(chǎn)生表,格.,注意對表中第四行中單位成本的理解.,由最小元素法得到問題的初始解:,再計算相應(yīng)的影響系數(shù):,此時 為進基變量, 由此得新解,再一次計算位勢和影響系數(shù)有,再計算相應(yīng)的影響系數(shù),以 為進基變量, 則有新解,經(jīng)過數(shù)次換基后得到問題的最優(yōu)解:,4.具有中轉(zhuǎn)站的運輸問題,某類物資有 個產(chǎn)地, 產(chǎn)地 的產(chǎn)地為,對該類物,資有 個需求點, 第 個需求點的需求量為,從產(chǎn)地到達需求點都需經(jīng)過 個中轉(zhuǎn)站中的某個中轉(zhuǎn),站.,啟動第 個中轉(zhuǎn)站將發(fā)生

17、固定費用,相應(yīng)的單位,費用分別為,求運輸方案, 使總運費為最小.,中轉(zhuǎn)站的最大轉(zhuǎn)運量為,引入 變量,表示啟用第 個中轉(zhuǎn)站,表示經(jīng)過從 個產(chǎn)地到第 個中轉(zhuǎn)站及從第 個中轉(zhuǎn)站到,第 個需求點的運輸量, 則問題的目標(biāo)函數(shù)為,產(chǎn)量限制:,中轉(zhuǎn)站能力限制:,需求量限制：,供需平衡限制:,由此得到該問題的數(shù)學(xué)模型:,四、指派問題,1.指派問題的數(shù)學(xué)模型,問題 設(shè)有 項工作, 交給 個人去完成. 每個人只能,如此的問題即稱為指派問題.,完成其中的一項. 又每人完成其中任何一項工作的代價,為已知, 求這樣的任務(wù)分配方案, 使完成這些工作的總,代價為最小.,以 表示第 人完成第 項工作所需的代價, 由此得,如此

18、的矩陣稱為指派問題中的代價矩陣.,到矩陣:,引入決策變量 :,由此得到矩陣 注意到: 由于每項工作只能由,一人完成及每人只能完成一項工作, 故在矩陣中每行和,每列只能有一個1, 其余均為0.,如此的矩陣稱為指派問題中的指派矩陣.,例17 設(shè)指派問題中的代價矩陣為,則下列矩陣,均為指派矩陣, 其代價分別為 而矩陣,則不是指派矩陣.,所謂求解指派問題的最小值解, 即為求解這樣的矩陣,使對應(yīng)的代價為最小.,分析,條件: 矩陣中每行每列的元素只有一個是1, 其余均為,行:,列:,零的數(shù)學(xué)表達式為:,由此得到問題的模型為:,而相應(yīng)的代價為,2.指派問題的求解方法,設(shè)代價矩陣為 我們用下面的方法求其最,每

19、行減去該行的最小數(shù);,每列減去該列的最小數(shù);,判斷是否有 個獨立的零, 若有, 則在指派矩陣中,小值解:,相應(yīng)元素取1, 其余為0.,所謂有 個獨立的零, 即指這些零應(yīng)分布在不同的行,判斷方法: 用最少的橫線和豎線將所有的零劃去, 若最,列上.,少的線數(shù)為 則一定有 個獨立的零.,例18 求下面指派問題中的最小值解.,解,注意到在最后表中, 每行每列都有零的存在.,在下面矩陣中, 選獨立的零:,則問題的最優(yōu)解為 其余,即相應(yīng)的指派矩陣為,最小代價為,例19 求下面指派問題的最小值解:,解,注意到, 對表,可以用3條線將所有的零劃去, 因而沒有4個獨立的零.,對此我們有下面的迭代次序:,在所有未劃去的數(shù)中找最小數(shù);,未劃去的數(shù)減去該數(shù);,交叉點加上該數(shù), 其余不變;,繼續(xù)判定.,在上例中:,最小數(shù)為2, 由此得:,此時有4個獨立的零,因而最優(yōu)解為,其余 最小