(運(yùn)籌重修課件)第三章運(yùn)輸問題

1、第三章第三章 運(yùn)輸問題運(yùn)輸問題 n掌握表上作業(yè)法及其在產(chǎn)銷平衡問題求解中 的應(yīng)用 n掌握產(chǎn)銷不平衡運(yùn)輸問題的求解方法 （一）基本要求： （二）重點(diǎn)和難點(diǎn)： n表上作業(yè)法 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 1、問題的提出 一般的運(yùn)輸問題就是要解決把 某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個 銷地，在每個產(chǎn)地的供應(yīng)量與每個銷 地的需求量已知，并知道各地之間的 運(yùn)輸單價的前提下，如何確定一個使 得總的運(yùn)輸費(fèi)用最小的方案。 1 運(yùn)輸問題模型運(yùn)輸問題模型 例4.1:某公司從兩個產(chǎn)地A1、 A2將物品運(yùn)往三個銷地B1、B2、B3， 各產(chǎn)地的產(chǎn)量、各銷地的銷量和 各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn) 費(fèi)如下

2、表所示，問：應(yīng)如何調(diào)運(yùn) 可使總運(yùn)輸費(fèi)用最小？ B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 6 200 A2 6 5 5 300 銷銷量量 150 150 200 解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj 的運(yùn)輸量，得到下列運(yùn)輸量表： B1 B2 B3 產(chǎn)產(chǎn)量量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 銷銷量量 150 150 200 1 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 Min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 +

3、 x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0(i=1,2；j=1,2,3） 1 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系數(shù)矩陣 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 模型系數(shù)矩陣特征 1.共有m+n行，分別表示各 產(chǎn)地和銷地；mn列，分別表示 各變量； 2.每列只有兩個 1，其余 為 0，分別表示只有一個產(chǎn)地和 一個銷地被使用。 1運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題

4、模型及有關(guān)概念 一般運(yùn)輸問題的線性規(guī)劃模型及求解思路 一般運(yùn)輸問題的提法： A 1 , A 2 ,A m 表示某物資的m個產(chǎn)地； B1,B2,Bn 表示某物資的n個銷地； ai 表示產(chǎn)地 Ai 的產(chǎn)量； bj 表示銷地 Bj 的銷量； cij 表示把物資為從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的單位 運(yùn)價。 如果a1 + a2 + + am = b1 + b2 + + bn ， 則稱該運(yùn)輸問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷 不平衡。下面，首先討論產(chǎn)銷平衡問題。 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 表1 運(yùn)輸問題數(shù)據(jù)表 銷地 產(chǎn)地 B1 B2 Bn產(chǎn)量 A1 A2 Am c11 c12 c1

5、n c21 c22 c2n cm1 cm2 cmn a1 a2 am 銷量b1 b2 bn 設(shè) xij 為從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的運(yùn) 輸量，根據(jù)這個運(yùn)輸問題的要求，可以建立 運(yùn)輸變量表。 1運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 表2 運(yùn)輸問題變量表 銷地 產(chǎn)地 B1 B2 Bn產(chǎn)量 A1 A2 Am x11 x12 x1n x21 x22 x2n xm1 xm2 xmn a1 a2 am 銷量b1 b2 bn 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 m n Min f = cij xij （1） i=1 j=1 n s.t. xij ai i = 1,2,m （2）

6、j=1 m xij bj j = 1,2,n （3） i=1 xij0(i=1,2,m;j=1,2,n)（4） 于是得到下列一般運(yùn)輸問題的模型： 在模型（1）（4）中，式（2）為 m 個產(chǎn)地的 產(chǎn)量約束；式（3）為 n 個銷地的銷量約束。 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 m n Min f = cij xij i=1 j=1 n s.t. xij = ai i = 1,2,m (5) j=1 m xij = bj j = 1,2,n (6) i=1 xij0(i=1,2,m;j=1,2,n) 對于產(chǎn)銷平衡問題，可得到下列運(yùn)輸 問題的模型： 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模

7、型及有關(guān)概念 運(yùn)輸問題是一種特殊的線性規(guī)劃 問題，在求解時依然可以采用單純形法 的思路。由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊 性，如果直接使用線性規(guī)劃單純形法求 解計算，則無法利用這些有利條件。人 們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ) 上建立了針對運(yùn)輸問題的表上作業(yè)法。 1 運(yùn)輸問題模型及有關(guān)概念運(yùn)輸問題模型及有關(guān)概念 2 運(yùn)輸問題求解表上作業(yè)法 n表上作業(yè)法步驟: (1) 找出初始基可行解。即在(mn)產(chǎn)銷平衡表 上用西北角法或最小元素法，Vogel法給出 m+n-1個數(shù)字，稱為數(shù)字格。它們就是初始基 變量的取值。 。 (2) 求各非基變量的檢驗(yàn)數(shù)，即在表上計算空格 的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如已是

8、最優(yōu) 解，則停止計算，否則轉(zhuǎn)到下一步。 (3) 確定換入變量和換出變量，找出新的基可行 解。在表上用閉回路法調(diào)整。 (4)重復(fù)(2)，(3)直到得到最優(yōu)解為止。 2 運(yùn)輸問題求解表上作業(yè)法 1、初始基本可行解的確定 在產(chǎn)銷平衡表中任選一個單元填入運(yùn)輸量xij，使 盡量匹配產(chǎn)銷，使一個約束方程得以滿足， 填入相應(yīng)位置； 調(diào)整Ai的擁有量及Bj的需求量，分別減去xij ，得到調(diào)整 后的擁有量ai和需求量bj ； 若ai=0，則劃去對應(yīng)的行（擁有的量全部運(yùn)走），若 bj=0則劃去對應(yīng)的列（需求的量全部運(yùn)來），且每次只劃 去一行或一列（每次只去掉一個約束）； 若平衡表中所有的行或列均被劃去，則結(jié)束。

9、否則，在剩下的平衡表中選下一個變量填入運(yùn)輸量，轉(zhuǎn) 2運(yùn)輸問題求解表上作業(yè)法 b j= b j- x ij a i= a i- x ij 2 運(yùn)輸問題求解表上作業(yè)法 按照上述方法所產(chǎn)生的一組變量的取值將滿足下面 條件： a所得的變量均為非負(fù)，且變量總數(shù)恰好為m+n-1 個； b所有的約束條件均得到滿足； c所得的變量不構(gòu)成閉回路。 因此所得的解一定是運(yùn)輸問題的基本可行解。 在上面的方法中： xij的選取方法并沒有加以限定， 如果采取一定的規(guī)則來選取，則會產(chǎn)生不同的方法 （1）西北角法 運(yùn)輸問題 某地區(qū)有兩個煤礦A1 A2 ，所產(chǎn)的煤要運(yùn)往三 個城市B1 B2 B3，各產(chǎn)地的產(chǎn)量、銷地的銷 量以及

10、各產(chǎn)地到各銷地的單位運(yùn)費(fèi)見下表， 求使總運(yùn)費(fèi)最小的運(yùn)輸方案 若每次在調(diào)整后的供需表中選 取最左上角的元素，則稱為 西北角法（或稱左上角方法） （1）西北角法 （2）最小費(fèi)用法 缺點(diǎn)：為了節(jié)省一處的費(fèi)用，有時造成在其它處缺點(diǎn)：為了節(jié)省一處的費(fèi)用，有時造成在其它處 要多花幾倍的運(yùn)費(fèi)。要多花幾倍的運(yùn)費(fèi)。 若每次在調(diào)整后的供需表中選取 對應(yīng)單位運(yùn)費(fèi)最小的元素，則稱 為最小費(fèi)用法。 （3）伏格爾(Vogel)法 伏格爾法的思想：一產(chǎn)地的產(chǎn)品假如不能按 最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個 差額。差額越大的地方，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn) 時，運(yùn)費(fèi)增加就越多，因而對差額最大處，就應(yīng)當(dāng) 采用最小運(yùn)費(fèi)法

11、（3）伏格爾(Vogel)法 練習(xí)：求初始運(yùn)輸方案（分別用最小費(fèi)用法和伏格爾法） 產(chǎn)銷平衡表 單位運(yùn)價表 B1 B2 B3 B4 A1 2 9 10 7 A2 1 3 4 2 A3 3 4 2 5 B1 B2 B3 B4 ai A1 5 4 9 A2 3 2 5 A3 3 4 7 bj 3 8 4 6 B1 B2 B3 B4 ai A1 3 5 1 9 A2 5 5 A3 3 4 7 bj 3 8 4 6 Ai Bj xij 最小元素法 伏格爾法 最優(yōu)性檢驗(yàn)就是檢查所得到的方案是 不是最優(yōu)方案。 檢查的方法與單純形方法中的原理相 同，即計算檢驗(yàn)數(shù)。計算檢驗(yàn)數(shù)。 由于目標(biāo)要求極小極小，因此，當(dāng)所

12、有的 檢驗(yàn)數(shù)都大于或等于零時該調(diào)運(yùn)方案就是 最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào) 整。 計算檢驗(yàn)數(shù)一般有兩種方法：閉回路法 和位勢法 2、基本可行解的最優(yōu)性檢驗(yàn) 2 運(yùn)輸問題求解表上作業(yè)法 （1）閉回路法 n在給出調(diào)運(yùn)方案的計算表上，從每一空格出發(fā) 找一條閉回路。它是以某空格為起點(diǎn)，用水平 或垂直線向前劃，當(dāng)碰到一數(shù)字格時可以轉(zhuǎn) 90（也可以穿過數(shù)字格），繼續(xù)前進(jìn)，直到 回到起始空格為止。 n從每一空格出發(fā)一定存在和可以找到唯一的閉 回路。因(m+n-1)個數(shù)字格(基變量)對應(yīng)的系數(shù) 向量是一個基。任一空格(非基變量)對應(yīng)的系 數(shù)向量是這個基的線性組合。如對于某非基變 量的系數(shù)列向量Pij,i

13、,jN可表示為 ujuslslkik jmu smusmlkmlkmi jmuusmsmllkmkmi jmiij PPPPP ee eeeeeeee eeeeeeeeee eeP )( )()()()( 其中Pik,Plk,Pls,Pus,PujB。而這些向量構(gòu)成了閉 回路(見圖3-2)。 如下是某一運(yùn)輸問題的初始方案，則可得到每個 空格（非基變量）的閉回路。 1040 25 52035 1040 25 52035 1040 25 52035 1040 25 52035 1040 25 52035 1040 25 52035 1040 25 52035 n利用閉回路法計算檢驗(yàn)數(shù)，對于每一個

14、空格（非基變量）xlk （1）以xlk為起點(diǎn)尋找該變量的閉回路 （2）以xlk為起點(diǎn)，沿任意一個方向?qū)υ撻] 回路拐角上變量的單位運(yùn)價（包括xlk） 依次標(biāo)“+”和“-” （3）將閉回路上標(biāo)有正負(fù)號的單位運(yùn)價直 接求代數(shù)和即得到非基變量xlk的檢驗(yàn)數(shù)。 以非基變量 x22 為起始頂點(diǎn)的閉回路 銷地 產(chǎn)地 B1B2B3B4產(chǎn)量 3 11 3 10 7 1 9 2 8 4 7 4 10 5 9 銷量3656 20(產(chǎn)銷平衡) A1 A2 A3 銷地 產(chǎn)地 B1B2B3B4產(chǎn)量 3 11 3 4 10 3 7 1 3 9 2 1 8 4 7 4 6 10 5 3 9 銷量3656 20(產(chǎn)銷平衡) A

15、1 A2 A3 運(yùn)輸費(fèi)用發(fā)生的變化為 92+310+541 中為 ij 以非基變量 x22 為起始頂點(diǎn)的閉 回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 9 2 + 3 10 + 5 4 1 即總的運(yùn)費(fèi)增加 1 個單位，這就說明 這個調(diào)整不能改善目標(biāo)值。 2運(yùn)輸問題求解表上作業(yè)法 按上述作法，計算出表的所有非基變量 的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號內(nèi)， 如圖所示。 表4-11 初始基本可行解及檢驗(yàn)數(shù) 銷地 產(chǎn)地 B1B2B3B4產(chǎn)量 A13 1 11 2 3 4 10 3 7 A21 3 9 1 2 1 8 -1 4 A37 10 4 6 10 12 5 3 9 銷量3656 20(產(chǎn)銷平衡) 中為

16、 ij 顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù) 均大于或等于零時，現(xiàn)行的調(diào)運(yùn)方案就 是最優(yōu)方案，因?yàn)榇藭r對現(xiàn)行方案作任 何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。 閉回路法的主要缺點(diǎn)是： 當(dāng)變量個數(shù)較多時，尋找閉回路 以及計算兩方面都會產(chǎn)生困難。 2運(yùn)輸問題求解表上作業(yè)法 （2）位勢法 njmix njbx miax ts ij j m i ij i n j ij , 1, 10 , 2 , 1 , 2 , 1 . . 1 1 m i n j ijij xcZ 11 min m i n j jjii vbuaW 11 max 利用了運(yùn)輸問題的對偶變量。設(shè)ui（i=1，2，m） 和vj（ j=1，2，n）是對應(yīng)運(yùn)輸

17、問題m+n個約束 條件的對偶變量，則運(yùn)輸問題的對偶問題為： njmvu micvu ts ji ijji , 2 , 1, 2 , 1i, , 2 , 1 . . 無約束， 原問題： n從線性規(guī)劃的對偶理論知，CBB-1=（u1， u2，um，v1，v2，vn），則運(yùn)輸 問題任一變量的檢驗(yàn)數(shù)可表示為： )( )(,( 2121 1 jiij jminmij Bijij vuc eevvvuuuc BCc 0)( jiijij vuc 若xij為基變量，因基變量的檢驗(yàn)數(shù)等于0，必有 有m+n-1個基變量，則可得到m+n-1個ui+vj=cij， 要求出m+n個ui和vj，可令任一個ui或vj等于

18、零，從 而解出其他m+n-1個ui和vj n位勢法求解檢驗(yàn)數(shù)步驟如下： 步驟1：在運(yùn)輸表的右端增加一列，稱為行位勢， 記為ui（i=1，2，m）；在運(yùn)輸表的下 面增加一行，稱為列位勢，記為vj（j=1， 2，n）。 步驟2：令某一個ui或vj等于0，利用基變量的檢 驗(yàn)數(shù)等于0，由基變量的cij和與其對應(yīng)的某個 已知的行位勢（ui）或列位勢（vj），依次計 算出其他的列位勢（vj）或行位勢（ui） 步驟3：按來計算各非基 變量（空格）的檢驗(yàn)數(shù)，即每一個非基變量 的cij減去位勢表中對應(yīng)格的行位勢和列位勢， 得到每個非基變量的檢驗(yàn)數(shù)，形成檢驗(yàn)數(shù)表。 )( jiijij vuc 下例是利用最小元素法得到的初始基可行解， 利用位勢表法計算其檢驗(yàn)數(shù)如下： 初始運(yùn)輸方案及位勢表初始運(yùn)輸方案及位勢表 7 5 11 9 15 10 14 7 13 158 16 35205 25 4010 因?yàn)?，所以此方案不是最優(yōu)方案。01 24 0 -2 -6 715816 3、解的改進(jìn)閉回路調(diào)整法 n當(dāng)運(yùn)輸問題基可行解的某個非基變量檢驗(yàn)數(shù)小于0時， 該方案不是最優(yōu)解，需要改進(jìn)，改進(jìn)的步驟如下： 步驟1：確定進(jìn)基變量。一般情況下，當(dāng) 時，選擇xlk為進(jìn)基變量。 步驟2：確定出基變量 （1）以