運(yùn)籌學(xué)CH2運(yùn)輸規(guī)劃

1、運(yùn)輸規(guī)劃問(wèn)題運(yùn)輸規(guī)劃問(wèn)題運(yùn)輸規(guī)劃的數(shù)學(xué)模型運(yùn)輸規(guī)劃的數(shù)學(xué)模型表上作業(yè)法表上作業(yè)法運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用 運(yùn)輸規(guī)劃模型的運(yùn)輸規(guī)劃模型的Excel解法解法 Page 2教學(xué)要求：教學(xué)要求：了解運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特點(diǎn)；了解運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特點(diǎn)；掌握表上作業(yè)法；掌握表上作業(yè)法；了解了解Microsoft Excel求解運(yùn)輸問(wèn)題的方法。求解運(yùn)輸問(wèn)題的方法。重難點(diǎn)：重難點(diǎn)：表上作業(yè)法表上作業(yè)法 Page 3 人們?cè)趶氖律a(chǎn)活動(dòng)中，不可避免地要進(jìn)行物資調(diào)運(yùn)工人們?cè)趶氖律a(chǎn)活動(dòng)中，不可避免地要進(jìn)行物資調(diào)運(yùn)工作。如某時(shí)期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，作。如某時(shí)期內(nèi)將生產(chǎn)基地的煤、鋼鐵、

2、糧食等各類物資，分別運(yùn)到需要這些物資的地區(qū)，根據(jù)各地的分別運(yùn)到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量生產(chǎn)量和和銷售量銷售量及各地之間的及各地之間的運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用，如何制定一個(gè)運(yùn)輸方案，使，如何制定一個(gè)運(yùn)輸方案，使總的運(yùn)總的運(yùn)輸費(fèi)用最小輸費(fèi)用最小。這樣的問(wèn)題稱為。這樣的問(wèn)題稱為運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題。Page 4 物資調(diào)運(yùn)是一個(gè)典型的線性規(guī)劃問(wèn)題。物資調(diào)運(yùn)是一個(gè)典型的線性規(guī)劃問(wèn)題。1939年前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出這一問(wèn)題；年前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出這一問(wèn)題；1941年美國(guó)數(shù)學(xué)家年美國(guó)數(shù)學(xué)家F.L.Hitchcock提出運(yùn)輸問(wèn)題數(shù)提出運(yùn)輸問(wèn)題數(shù)學(xué)模型；學(xué)模型；1951年年Dantzig將此類問(wèn)

3、題的解法系統(tǒng)化將此類問(wèn)題的解法系統(tǒng)化,完善化完善化,改改為用表上作業(yè)法求解為用表上作業(yè)法求解.Page 5無(wú)轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題無(wú)轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題: 產(chǎn)銷平衡問(wèn)題產(chǎn)銷平衡問(wèn)題: 總產(chǎn)量總產(chǎn)量 =總銷量總銷量 產(chǎn)銷不平衡問(wèn)題產(chǎn)銷不平衡問(wèn)題: 總產(chǎn)量總產(chǎn)量 總銷量，則為產(chǎn)大于銷情況總銷量，則為產(chǎn)大于銷情況 總產(chǎn)量總產(chǎn)量 總銷量，則為銷大于產(chǎn)情況總銷量，則為銷大于產(chǎn)情況 對(duì)于產(chǎn)銷不平衡運(yùn)輸問(wèn)題，可轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問(wèn)題處對(duì)于產(chǎn)銷不平衡運(yùn)輸問(wèn)題，可轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問(wèn)題處理，而有轉(zhuǎn)運(yùn)問(wèn)題可化為無(wú)轉(zhuǎn)運(yùn)問(wèn)題處理。理，而有轉(zhuǎn)運(yùn)問(wèn)題可化為無(wú)轉(zhuǎn)運(yùn)問(wèn)題處理。Page 6A1A2Am產(chǎn)地B1B2Bn銷地a1a2amb1b2

4、bnc11c12c1nc21c22c2ncm1cm2cmn若 則稱該問(wèn)題為平衡運(yùn)輸問(wèn)題，否則稱為非平衡運(yùn)輸問(wèn)題。njjmiiba11Page 7產(chǎn)銷平衡問(wèn)題產(chǎn)銷平衡問(wèn)題Page 8 幾個(gè)術(shù)語(yǔ)：幾個(gè)術(shù)語(yǔ)： 生產(chǎn)地生產(chǎn)地（供應(yīng)地，出發(fā)地）：產(chǎn)量（供應(yīng)量）（供應(yīng)地，出發(fā)地）：產(chǎn)量（供應(yīng)量） 銷售地銷售地（需求地，目的地）：銷量（需求量）（需求地，目的地）：銷量（需求量） 運(yùn)價(jià)運(yùn)價(jià)（單價(jià)）：?jiǎn)挝划a(chǎn)品運(yùn)輸費(fèi)用（單價(jià)）：?jiǎn)挝划a(chǎn)品運(yùn)輸費(fèi)用 運(yùn)費(fèi)運(yùn)費(fèi)：?jiǎn)蝺r(jià)：?jiǎn)蝺r(jià)運(yùn)量運(yùn)量Page 9例例2.1 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地將物品運(yùn)往三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷

5、地的銷量和各產(chǎn)地運(yùn)往各銷地每件，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的物品的運(yùn)價(jià)運(yùn)價(jià)如下如下表表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？小？B1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200Page 10解：解：產(chǎn)銷平衡問(wèn)題：產(chǎn)銷平衡問(wè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銷量銷量150150200B1B2B3產(chǎn)量產(chǎn)量A16462

6、00A2655300銷量銷量150150200Page 11)3 ,2, 1;2, 1(0200150150300200.556646min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxzij數(shù)學(xué)模型為：數(shù)學(xué)模型為：Page 12產(chǎn)銷平衡問(wèn)題數(shù)學(xué)模型的一般形式：產(chǎn)銷平衡問(wèn)題數(shù)學(xué)模型的一般形式： 設(shè)某物品有設(shè)某物品有m個(gè)產(chǎn)地個(gè)產(chǎn)地A1, A2 , Am；各產(chǎn)地的產(chǎn)量分別；各產(chǎn)地的產(chǎn)量分別是是a1,a2,am；有；有n個(gè)銷地個(gè)銷地B1, B2, Bn。各銷地的銷量分別。各銷地的銷量分別是是b1,b2,bn ；假如從產(chǎn)地；假如從

7、產(chǎn)地Ai(i=1,2,m)向銷地向銷地Bj( j= 1,2,n)運(yùn)輸單位物品的運(yùn)價(jià)是運(yùn)輸單位物品的運(yùn)價(jià)是cij；問(wèn)怎樣調(diào)運(yùn)這些物品才問(wèn)怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最?。磕苁箍傔\(yùn)費(fèi)最??？Page 13這是一個(gè)線性規(guī)劃問(wèn)題，可以用單純形法求解。這是一個(gè)線性規(guī)劃問(wèn)題，可以用單純形法求解。但是，由于它所含變量多，求解極不方便。即使求解一個(gè)但是，由于它所含變量多，求解極不方便。即使求解一個(gè)m3，n4的簡(jiǎn)單運(yùn)輸問(wèn)題，變量數(shù)目也將達(dá)到的簡(jiǎn)單運(yùn)輸問(wèn)題，變量數(shù)目也將達(dá)到19個(gè)之多。個(gè)之多。因此，必須尋找更簡(jiǎn)便的求解方法。因此，必須尋找更簡(jiǎn)便的求解方法。njmixnjbxmiaxxczijjmiijnjiijmi

8、njijij,.,2 , 1;,.,2 , 1;0,.,2 , 1;,.,2 , 1;min1111產(chǎn)量約束銷量約束非負(fù)約束總運(yùn)輸費(fèi)用極小化極小化由某一產(chǎn)地運(yùn)往各由某一產(chǎn)地運(yùn)往各個(gè)銷地的物品數(shù)量個(gè)銷地的物品數(shù)量之和等于該產(chǎn)地的之和等于該產(chǎn)地的產(chǎn)量產(chǎn)量由各個(gè)產(chǎn)地運(yùn)往某由各個(gè)產(chǎn)地運(yùn)往某一銷地的物品數(shù)量一銷地的物品數(shù)量之和等一該銷地的之和等一該銷地的銷量銷量非負(fù)條件非負(fù)條件Page 141.運(yùn)輸問(wèn)題有最優(yōu)解運(yùn)輸問(wèn)題有最優(yōu)解2.運(yùn)輸問(wèn)題約束條件的系數(shù)矩陣運(yùn)輸問(wèn)題約束條件的系數(shù)矩陣111111111111111111212222111211mnmmnnxxxxxxxxxm 行n 行TijA0 , 0 ,

9、 1 , 0 , 0 , 1 , 0 , 0第 i 個(gè)第(m+j)個(gè)系數(shù)列向量的結(jié)構(gòu)：即除第i個(gè)和第( m + j )個(gè)分量為1外，其它分量全等于0。Page 15n約束條件系數(shù)矩陣的元素等于約束條件系數(shù)矩陣的元素等于0或或1；n約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，對(duì)應(yīng)于每一約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，對(duì)應(yīng)于每一個(gè)變量在前個(gè)變量在前 m 個(gè)約束方程中出現(xiàn)一次個(gè)約束方程中出現(xiàn)一次,在后在后 n 個(gè)約束方程中個(gè)約束方程中也出現(xiàn)一次；也出現(xiàn)一次；n所有結(jié)構(gòu)約束條件都是等式約束；所有結(jié)構(gòu)約束條件都是等式約束；n各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。Page

10、 16 1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；最大等； 2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束直接加入約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時(shí)產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。時(shí)）或銷地（產(chǎn)大于銷時(shí)）。P89P90Page 17 表上作業(yè)法是求解運(yùn)輸問(wèn)題的一種簡(jiǎn)便而有效的方法表上作業(yè)法是求解運(yùn)輸問(wèn)題的一種簡(jiǎn)便而有效的方法,其其求解過(guò)程在運(yùn)輸表上進(jìn)行求解過(guò)程在運(yùn)輸表上進(jìn)行,它是一種迭代法它是一

11、種迭代法,其其實(shí)質(zhì)是單純形實(shí)質(zhì)是單純形法。法。步驟為：步驟為： 1. 先按某種方法找出一個(gè)初始解先按某種方法找出一個(gè)初始解(初始調(diào)運(yùn)方案）；初始調(diào)運(yùn)方案）； 2. 對(duì)現(xiàn)行解作最優(yōu)性判別；對(duì)現(xiàn)行解作最優(yōu)性判別； 3. 若不是最優(yōu)解若不是最優(yōu)解,就在表上對(duì)它進(jìn)行調(diào)整改進(jìn)就在表上對(duì)它進(jìn)行調(diào)整改進(jìn),得出一個(gè)新得出一個(gè)新解；解； 4. 再判別再判別,再改進(jìn)再改進(jìn),直到得到運(yùn)輸問(wèn)題的最優(yōu)解為止；直到得到運(yùn)輸問(wèn)題的最優(yōu)解為止；在迭代過(guò)程中在迭代過(guò)程中,得出的所有解都要求是運(yùn)輸問(wèn)題的基可行得出的所有解都要求是運(yùn)輸問(wèn)題的基可行解。解。Page 18步驟步驟描述描述方法方法第一步第一步求初始基行可行解求初始基行可

12、行解（初始調(diào)運(yùn)方案）（初始調(diào)運(yùn)方案）最小元素法、最小元素法、元素差額法、元素差額法、第二步第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解。求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解。當(dāng)檢驗(yàn)數(shù)當(dāng)檢驗(yàn)數(shù) ij ij全都非負(fù)全都非負(fù)時(shí)得到最優(yōu)解；時(shí)得到最優(yōu)解；若存在檢驗(yàn)數(shù)若存在檢驗(yàn)數(shù) ij ij 00，則為唯一最優(yōu)運(yùn)輸方案（唯一最優(yōu)解）；，則為唯一最優(yōu)運(yùn)輸方案（唯一最優(yōu)解）；n存在檢驗(yàn)數(shù)為存在檢驗(yàn)數(shù)為0，其他檢驗(yàn)數(shù)，其他檢驗(yàn)數(shù)0，則為無(wú)窮多最優(yōu)運(yùn)輸方案，則為無(wú)窮多最優(yōu)運(yùn)輸方案（無(wú)窮多最優(yōu)解）。（無(wú)窮多最優(yōu)解）。求檢驗(yàn)數(shù)的方法：求檢驗(yàn)數(shù)的方法： 閉回路法閉回路法Page 34閉回路的概念閉回路的概念,132222111jsis

13、jsijijijijixxxxxx稱稱集集合合),(2121互互不不相相同同；其其中中ssjjjiii為一個(gè)閉回路為一個(gè)閉回路 ，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。如下表量的連線為閉回路的邊。如下表Page 35B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 從從x11出發(fā)，用水平或垂直線段向前劃，碰到數(shù)字格必須轉(zhuǎn)出發(fā)，用水平或垂直線段向前劃，碰到數(shù)字格必須轉(zhuǎn)90度，再繼續(xù)向前，直到回到起點(diǎn)止。度，再繼續(xù)向前，直到回到起點(diǎn)止。 閉回路的變量集合是閉回路的變量集合是x11,x12,x42,x4

14、3,x23,x25,x35, x31 。 Page 36閉回路法求空格檢驗(yàn)數(shù)閉回路法求空格檢驗(yàn)數(shù)空格閉回路概念：空格閉回路概念： 從一空格出發(fā)，向數(shù)字格作直線，每遇數(shù)字格則轉(zhuǎn)從一空格出發(fā)，向數(shù)字格作直線，每遇數(shù)字格則轉(zhuǎn)90度，度，直回到開(kāi)始的空格。這種以一個(gè)空格為頂點(diǎn)，其余頂點(diǎn)全為直回到開(kāi)始的空格。這種以一個(gè)空格為頂點(diǎn)，其余頂點(diǎn)全為數(shù)字格的閉合折線，被稱為該空格的閉合回路。數(shù)字格的閉合折線，被稱為該空格的閉合回路。 可以證明：可以證明： 按前面方法確定的調(diào)運(yùn)方案，每一個(gè)空格都有惟一的閉按前面方法確定的調(diào)運(yùn)方案，每一個(gè)空格都有惟一的閉合回路。合回路。Page 37空格檢驗(yàn)數(shù)概念：空格檢驗(yàn)數(shù)概念：

15、 作出空格的閉合回路，令空格增加一個(gè)單位調(diào)運(yùn)量作出空格的閉合回路，令空格增加一個(gè)單位調(diào)運(yùn)量(+1)，沿閉合回路進(jìn)行減一沿閉合回路進(jìn)行減一(-1)增一增一(+1)方法進(jìn)行平衡調(diào)整調(diào)運(yùn)量方法進(jìn)行平衡調(diào)整調(diào)運(yùn)量得到新的調(diào)運(yùn)方案，新方案總運(yùn)費(fèi)與前一方案總運(yùn)費(fèi)相比，得到新的調(diào)運(yùn)方案，新方案總運(yùn)費(fèi)與前一方案總運(yùn)費(fèi)相比，總運(yùn)費(fèi)的改變量，就是該空格的檢驗(yàn)數(shù)?？傔\(yùn)費(fèi)的改變量，就是該空格的檢驗(yàn)數(shù)。最優(yōu)性檢驗(yàn)：所有空格檢驗(yàn)數(shù)最優(yōu)性檢驗(yàn)：所有空格檢驗(yàn)數(shù)非負(fù)非負(fù)，則為最優(yōu)解。，則為最優(yōu)解。 下面以例子說(shuō)明空格檢驗(yàn)數(shù)的求法：下面以例子說(shuō)明空格檢驗(yàn)數(shù)的求法：Page 38該空格檢驗(yàn)數(shù)：該空格檢驗(yàn)數(shù)：11=(+1) 3+(-

16、1) 1+ (+1) 2+ (-1) 3=1B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量311310192741058341633+1-1+1-11Page 39該空格檢驗(yàn)數(shù)：該空格檢驗(yàn)數(shù)：12=(+1) 11+(-1) 4 + (+1) 5+ (-1) 10=2B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量311310192741058341633+1-1+1-121Page 40該空格檢驗(yàn)數(shù)：該空格檢驗(yàn)數(shù)：22=(+1) 9+(-1) 4 + (+1) 5+ (-1) 10 + (+1) 3+ (-1) 2=1B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量3113101927410583

17、41633+1-1+1-121+1-11Page 41該空格檢驗(yàn)數(shù)：該空格檢驗(yàn)數(shù)：22=(+1) 8+(-1) 10 + (+1) 3+ (-1) 2=-1 故不是最優(yōu)解。故不是最優(yōu)解。B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量311310192741058341633+1-121+1-11-1Page 42閉回路調(diào)整法閉回路調(diào)整法步驟步驟:1、找出空格檢驗(yàn)數(shù)最小的空格、找出空格檢驗(yàn)數(shù)最小的空格 ；2、作此空格的惟一閉合回路；、作此空格的惟一閉合回路；3、確定、確定值：值： 閉回路中具有閉回路中具有(-1) 的數(shù)字格中運(yùn)量最小的運(yùn)量的數(shù)字格中運(yùn)量最小的運(yùn)量作為作為 ；4、按閉合回路上的正、

18、負(fù)號(hào)，將該單元格的運(yùn)量加減此、按閉合回路上的正、負(fù)號(hào)，將該單元格的運(yùn)量加減此值，值，調(diào)整運(yùn)量得新調(diào)運(yùn)方案；調(diào)整運(yùn)量得新調(diào)運(yùn)方案；5、再對(duì)此方案用閉回路法進(jìn)行最優(yōu)性檢驗(yàn)。、再對(duì)此方案用閉回路法進(jìn)行最優(yōu)性檢驗(yàn)。Page 431、空格、空格(2,4)檢驗(yàn)數(shù)最??；檢驗(yàn)數(shù)最?。?、作此空格的惟一閉合回路；、作此空格的惟一閉合回路；3、確定、確定值為值為1；B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量311310192741058341633211-11012+1-1+1-1Page 444、按閉合回路上的正、負(fù)號(hào)，將該單元格的運(yùn)量加減此、按閉合回路上的正、負(fù)號(hào)，將該單元格的運(yùn)量加減此=1值，調(diào)整運(yùn)量得

19、新調(diào)運(yùn)方案（值，調(diào)整運(yùn)量得新調(diào)運(yùn)方案（新的運(yùn)輸表新的運(yùn)輸表）；）；B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量311310192741058341633+1-1+1-11250總的運(yùn)輸費(fèi)總的運(yùn)輸費(fèi)(31)+(64) +(53) +(210)+(18)+(35)=85元元Page 45對(duì)新的運(yùn)輸表進(jìn)行最優(yōu)解的判定，所有檢驗(yàn)數(shù)都非負(fù)，故為對(duì)新的運(yùn)輸表進(jìn)行最優(yōu)解的判定，所有檢驗(yàn)數(shù)都非負(fù)，故為最優(yōu)解，且總的運(yùn)輸費(fèi)最優(yōu)解，且總的運(yùn)輸費(fèi)(31)+(64) +(53) +(210)+(18)+(35)=85元。元。B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量31131019274105835163220

20、21912Page 46同時(shí)，發(fā)現(xiàn)單元格（同時(shí)，發(fā)現(xiàn)單元格（1,1）的檢驗(yàn)數(shù)為）的檢驗(yàn)數(shù)為0，此問(wèn)題（模型）有，此問(wèn)題（模型）有無(wú)窮多解。無(wú)窮多解。B1B2B3B4產(chǎn)量產(chǎn)量A1A2 A3銷量銷量3113101927410583516322021912Page 47退化解：退化解： 表格中一般要有表格中一般要有(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即可。

21、即可。 利用閉回路調(diào)整法對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小利用閉回路調(diào)整法對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量運(yùn)量作為調(diào)整量，若最小運(yùn)量超過(guò)，若最小運(yùn)量超過(guò)2個(gè)相同，則選擇任意一個(gè)相同，則選擇任意一個(gè)最小運(yùn)量標(biāo)記為個(gè)最小運(yùn)量標(biāo)記為“0”。 （換句話說(shuō)，調(diào)整后有換句話說(shuō)，調(diào)整后有2個(gè)或個(gè)或2個(gè)以上運(yùn)量為個(gè)以上運(yùn)量為0的單元格時(shí)，的單元格時(shí)，只取只取1個(gè)單元格為空格，其他單元格運(yùn)量填個(gè)單元格為空格，其他單元格運(yùn)量填0。）Page 48表上作業(yè)法的計(jì)算步驟：表上作業(yè)法的計(jì)算步驟：分析實(shí)際問(wèn)題列出產(chǎn)銷平分析實(shí)際問(wèn)題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小確定初始調(diào)運(yùn)方案（最

22、小元素法或元素法或Vogel法）法）求檢驗(yàn)數(shù)（閉回路法）求檢驗(yàn)數(shù)（閉回路法）所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0找出最小檢驗(yàn)數(shù)，用閉回路調(diào)整法調(diào)找出最小檢驗(yàn)數(shù)，用閉回路調(diào)整法調(diào)整，得到新的調(diào)運(yùn)方案整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運(yùn)價(jià)算出總運(yùn)價(jià)Page 49Page 50Page 51例題：某公司承擔(dān)例題：某公司承擔(dān)4 4條航線的運(yùn)輸任務(wù)，已知：（條航線的運(yùn)輸任務(wù)，已知：（1 1）各條航）各條航線的起點(diǎn)城市和終點(diǎn)城市及每天的航班數(shù)見(jiàn)表線的起點(diǎn)城市和終點(diǎn)城市及每天的航班數(shù)見(jiàn)表1 1；（；（2 2）各城）各城市間的航行時(shí)間見(jiàn)表市間的航行時(shí)間見(jiàn)表2 2；（；（3 3）所有航線都使用同一種船只，

23、）所有航線都使用同一種船只，每次裝船和卸船時(shí)間均為每次裝船和卸船時(shí)間均為1 1天。問(wèn)該公司至少應(yīng)配備多少條船天。問(wèn)該公司至少應(yīng)配備多少條船才能滿足所有航線運(yùn)輸?shù)男枰?？才能滿足所有航線運(yùn)輸?shù)男枰縋age 52表表1 1航線航線起點(diǎn)城市起點(diǎn)城市終點(diǎn)城市終點(diǎn)城市每天航班數(shù)每天航班數(shù)1 1E ED D3 32 2B BC C2 23 3A AF F1 14 4D DB B1 1Page 53 至從ABCDEFA0121477B1031388C23015557851703F7852030Page 54解：所需船只可分為兩部分：解：所需船只可分為兩部分：（1 1）各航線航行、裝船、卸