運輸問題_表上作業(yè)法

1、4.2 表上作業(yè)法,表上作業(yè)法表上作業(yè)法與單純形法的關(guān)系表上作業(yè)法的基本步驟確定初始基可行解最小元素法的基本步驟伏格爾法,三、 運輸問題的求解,運輸問題的求解采用表上作業(yè)法，即用列表的方法求解線性規(guī)劃問題中的運輸模型的計算方法，實質(zhì)上是單純形法。,,表上作業(yè)法是一種特定形式的單純形法，它與單純形法有著完全相同的解題步驟，所不同的只是完成各步采用的具體形式。,,1.表上作業(yè)法,,,2.表上作業(yè)法與單純形法的關(guān)系,表上作業(yè)法中

2、的最小元素法和伏格爾法實質(zhì)上是在求單純形表中的初始基可行解；表上作業(yè)法中的“位勢法”實質(zhì)上是在求單純形表中的檢驗數(shù)；調(diào)運方案表中數(shù)字格的數(shù)實質(zhì)上就是單純形法中基變量的值；調(diào)運方案表上的“閉回路法”實質(zhì)上是在做單純形表上的換基迭代。,,（1）找出初始基可行解： m+n-1個數(shù)字格（基變量）；（2）求各非基變量（空格）的檢驗數(shù)。,,那么,選取xij為入基變量；,（3）確定入基變量，若,,3.表上作業(yè)法的基本步驟,（4）確定出基變量，

3、找出入基變量的閉合回路；（5）在表上用閉合回路法調(diào)整運輸方案；（6）重復2、3、4、5步驟，直到得到最優(yōu)解。,,4、確定初始基可行解,與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運輸問題一定具有可行解（同時也一定存在最優(yōu)解）。最小元素法（the least cost rule）和伏格爾法（Vogel’s approximation method）。,,最小元素法的基本思想是就近供應，即從單位運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此類推

4、，一直到給出基本方案為止.,最小元素法,,找出最小運價，確定供求關(guān)系，最大量的供應 ；劃掉已滿足要求的行或 (和) 列，如果需要同時劃去行和列，必須要在該行或列的任意位置填個“0”；在剩余的運價表中重復1、2兩步，直到得到初始基可行解。,,5、最小元素法的基本步驟,最小元素法,最小元素法的基本思想是就近供應，即從單位運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方案為止。,,,,表4-1,最小元素法的應用（以引例4-1

5、為例）,第一步：從表4-1中找出最小運價“1”， 最小運價所確定的供應關(guān)系為（B，甲），在（B，甲）的交叉格處填上“3”，形成表4-2；將運價表的甲列運價劃去得表4-3.,,,表4-2,表4-3,3,,,第二步：在表4-3的未被劃掉的元素中再找出最小運價“2”，最小運價所確定的供應關(guān)系為（B，丙），即將B余下的1個單位產(chǎn)品供應給丙，表4-2轉(zhuǎn)換成表4-4。劃去B行的運價，劃去B行表明B所生產(chǎn)的產(chǎn)品已全部運出，表4-3轉(zhuǎn)換成表4-5。,,

6、,表4-3,,,表4-4,表4-5,3,,1,,,,表4-5,,,第三步：在表4-5中再找出最小運價“3”，這樣一步步地進行下去，直到單位運價表上的所有元素均被劃去為止。,,,表4-7,表4-6,,3,2,1,,3,4,,4,6,,5,3,,3,,,,最后在產(chǎn)銷平衡表上得到一個調(diào)運方案，見表4-6。這一方案的總運費為86個單位。,最小元素法各步在運價表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個數(shù)相應地劃掉一

7、行或一列，這樣最終將得到一個具有m+n-1個數(shù)字格（基變量）的初始基可行解。,,,在供需關(guān)系格（i，j ）處填入一數(shù)字，剛好使第 i個產(chǎn)地的產(chǎn)品調(diào)空，同時也使第j個銷地的需求得到滿足。填入一數(shù)字同時劃去了一行和一列，那么最終必然無法得到一個具有m+n-1個數(shù)字格（基變量）的初始基可行解。,,6.應注意的問題,為了使在產(chǎn)銷平衡表上有m+n-1個數(shù)字格，這時需要在第行或第列此前未被劃掉的任意一個空格上填一個“0”。填“0”格雖然所反映的運輸

8、量同空格沒有什么不同；但它所對應的變量卻是基變量，而空格所對應的變量是非基變量。,,,表4-7,表4-8,,,3,1,4,,7. 舉例 將例4-1的各工廠的產(chǎn)量做適當調(diào)整（調(diào)整結(jié)果見表4-7），就會出現(xiàn)上述特殊情況。,,,,,0,,6,,,6,,每次從當前運價表上，計算各行各列中兩個最小運價之差值（行差值hi，列差值kj），優(yōu)先取最大差值的行或列中最小的格來確定運輸關(guān)系，直到求出初始方案。,,8.伏格法爾法,伏格爾法的基本步驟：

9、,8.伏格爾法,1.計算每行、列兩個最小運價的差；2.找出最大差所在的行或列；3.找出該行或列的最小運價，確定供求關(guān)系，最大量的供應 ；4.劃掉已滿足要求的行或 (和) 列，如果需要同時劃去行和列，必須要在該行或列的任意位置填個“0”；5.在剩余的運價表中重復1~4步，直到得到初始基可行解。,,,,表4-1,表4-12,1,3,0,1,1,2,5,4,,,表4-13,表4-14,,6,2,1,3,0,1,2,5,,表4-15,6

10、,3,,表4-16,,,,2,1,2,0,1,1,,,表4-17,6,3,3,,,,,表4- 18,,,1,2,6,7,3,,,,,,,表4-19,,表4-20,,,6,3,3,5,2,8,1,,2,,,總運費為85由以上可見，伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟是完全相同的。伏格爾法給出的初始解比最小元素法給出的初始解一般來講會更接近于最優(yōu)解。,表4-23,6,3,3,5,1,2,4.2.2 基可行解的最優(yōu)

11、性檢驗,對初始基可行解的最優(yōu)性檢驗有閉合回路法和位勢法兩種基本方法。閉合回路法具體、直接，并為方案調(diào)整指明了方向；而位勢法具有批處理的功能，提高了計算效率。所謂閉合回路是在已給出的調(diào)運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉合回路。一個空格存在唯一的閉回路。,所謂

12、閉合回路法，就是對于代表非基變量的空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。,1.閉合回路,下面就以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論閉合回路法。,,,,,表4-

13、24,,,,（+3）,（-3）,（+2）,（-1）,從表4-6給定的初始方案的任一空格出發(fā)尋找閉合回路，如對于空格（A，甲）在初始方案的基礎(chǔ)上將A生產(chǎn)的產(chǎn)品調(diào)運一個單位給甲，為了保持新的平衡，就要依次在（A，丙）處減少一個單位、（B，丙）處增加一個單位、（B，甲）處減少一個單位；即要尋找一條除空格（A，甲）之外其余頂點均為有數(shù)字格（基變量）組成的閉合回路。表4-24中用虛線畫出了這條閉合回路。閉合回路頂點所在格括號內(nèi)的數(shù)字是相應的單位運

14、價，單位運價前的“+”、“-”號表示運量的調(diào)整方向。,,對應這樣的方案調(diào)整，運費會有什么變化呢？可以看出（A，甲）處增加一個單位，運費增加3個單位；在（A，丙）處減少一個單位，運費減少3個單位；在（B，丙）處增加一個單位，運費增加2個單位；在（B，甲）處減少一個單位，運費減少1個單位。增減相抵后，總的運費增加了1個單位。由檢驗數(shù)的經(jīng)濟含義可以知道，（A，甲）處單位運量調(diào)整所引起的運費增量就是（A，甲）的檢驗數(shù)，即σ11=1。,表4-24

15、,（+3）,（-3）,（+2）,（-1）,,,仿照此步驟可以計算初始方案中所有空格的檢驗數(shù)，表4-25～表4-30展示了各檢驗數(shù)的計算過程，表4-30給出了最終結(jié)果?？梢宰C明，對初始方案中的每一個空格來說“閉合回路存在且唯一”。,,,,,表4-25,,,,,,,,,,表4-26,,,,,,,,表4-27,,,,,,,表4-28,,,,,,,,,,表4-29,,,,,表4-30,,如果檢驗數(shù)表中所有數(shù)字均大于等于零，這表明對調(diào)運方案做出任

16、何改變都將導致運費的增加，即給定的方案是最優(yōu)方案。在表4-30中， ?24 = -1,說明方案需要進一步改進。,2.位勢法,對于特定的調(diào)運方案的每一行給出一個因子 ui（稱為行位勢），每一列給出一個因子vj（稱為列位勢），使對于目前解的每一個基變量xij 有cij= ui + vj，這里的ui 和 vj可正、可負也可以為零。那么任一非基變量 xij的檢驗數(shù)就是,這一表達式完全可以通過先前所述的閉合回路法得到。在某一的閉合回路上（如下表所

17、示），由于基變量的運價等于其所對應的行位勢與列位勢之和，即：,,,,,非基變量,,基變量,（-cik）基變量,（+clk）基變量,,于是,所以,,,對于一個具有m個產(chǎn)地、n個銷地的運輸問題，應具有m個行位勢、n個列位勢，即具有“m+n”個位勢。運輸問題基變量的個數(shù)只有“m+n-1”個，所以利用基變量所對應的“m+n-1”個方程，求出“m+n”個位勢，進而計算各非基變量的檢驗數(shù)是不現(xiàn)實的。,通?？梢酝ㄟ^在這些方程中對任意一個因子假定一個任

18、意的值（如u1=0等等），再求解其余的“m+n-1”個未知因子，這樣就可求得所有空格（非基變量）的檢驗數(shù)。仍以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論位勢法求解非基變量檢驗數(shù)的過程。,,第一步：把方案表中基變量格填入其相應的運價并令u1=0 ；讓每一個基變量xij都有cij= ui + vj ，可求得所有的位勢，如表4-32所示。,表4-32,,,,,,,,,第二步：利用,計算各非基變量xij,的檢驗數(shù)，結(jié)果

19、見表4-30。,10,3,-1,-5,9,2,0,4.2.3方案的優(yōu)化,在負檢驗數(shù)中找出最小的檢驗數(shù)，該檢驗數(shù)所對應的變量即為入基變量。在入基變量所處的閉合回路上，賦予入基變量最大的增量，即可完成方案的優(yōu)化。在入基變量有最大增量的同時，一定存在原來的某一基變量減少為“0”，該變量即為出基變量。切記出基變量的“0”運量要用“空格”來表示，而不能留有“0”。,在表4-30中，,,，故選擇,x24為入基變量。在入基變量x24所處的閉合回路上

20、（如表4-33所示），賦予最大的增量“1”，相應地有x23最大的增量“1”，相應地有x23出基, x13=5,x14=2.,利用閉合回路法或位勢法計算各空格（非基變量）的檢驗數(shù)，可得表4-34（同伏格爾法的初始解表4-23）。,表4-30,表4-33,,,,,表4-34,由于表4-33中的檢驗數(shù)均大于等于零，所以表4-33（同伏格爾法所給出的初始解表4-23）給出的方案是最優(yōu)方案，這個最優(yōu)方案的運費是85個單位。,?23 = 1,?

21、31 = 9,?22 = 2,?11 = 1,?12 = 2,?33 = 12,§4.3運輸問題的拓展,總產(chǎn)量大于總銷量的運輸問題即為產(chǎn)大于銷的運輸問題。在實際問題中，產(chǎn)大于銷意味著某些產(chǎn)品被積壓在倉庫中?？梢赃@樣設(shè)想，如果把倉庫也看成是一個假想的銷地，并令其銷量剛好等于總產(chǎn)量與總銷量的差；那么，產(chǎn)大于銷的運輸問題就轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題 假想一個銷地，相當于在原產(chǎn)銷關(guān)系表上增加一列。,4.3.1產(chǎn)大于銷的運輸問題,假想

22、列所對應的運價,由于假想的銷地代表的是倉庫，而我們優(yōu)化的運費是產(chǎn)地與銷地間的運輸費用，并不包括廠內(nèi)的運輸費用；所以假想列所對應的運價都應取為“0”。,至此，我們已經(jīng)將產(chǎn)大于銷的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題，進一步的求解可利用上節(jié)介紹的表上作業(yè)法來完成。,[例4-2] 將表4-35所示的產(chǎn)大于銷的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題,表4-35,解 此運輸問題的總產(chǎn)量為23、總銷量為20，所以假設(shè)一個銷地戊并令其銷量剛好等于總產(chǎn)量與總

23、銷量的差“3”。取假想的戊列所對應的運價都為“0”，可得表4-36所示的產(chǎn)銷平衡運輸問題。,表4-36,4.3.2銷大于產(chǎn)的運輸問題,總銷量大于總產(chǎn)量的運輸問題即為銷大于產(chǎn)的運輸問題?？梢赃@樣設(shè)想，假想一個產(chǎn)地，并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差；那么，銷大于產(chǎn)的運輸問題同樣可以轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題 假想的產(chǎn)地并不存在，于是各銷地從假想產(chǎn)地所得到的運量，實際上所表示的是其未滿足的需求。由于假想的產(chǎn)地與各銷地之間并不存在實際

24、的運輸，所以假想的產(chǎn)地行所有的運價都應該是“0”。至此，我們又將銷大于產(chǎn)的運輸問題轉(zhuǎn)換成了產(chǎn)銷平衡的運輸問題。,[例4-3] 將表4-37所示的銷大于產(chǎn)的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題,表4-37,解 此運輸問題的總產(chǎn)量為20、總銷量為28，所以假設(shè)一個產(chǎn)地D并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差“8”。令假想的D行所對應的運價都為“0”，可得表4-37所示的產(chǎn)銷平衡運輸問題。,表4-38,4.3.3運輸問題的應用舉例,[例4-4

25、] 設(shè)有三個化肥廠供應四個地區(qū)的化肥需求，假定等量化肥在這些地區(qū)的使用效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的單位運價如表4-39所示，試求出總的運費最節(jié)省的化肥調(diào)撥方案。,表4-39,根據(jù)現(xiàn)有產(chǎn)量，除滿足地區(qū)1、地區(qū)2和地區(qū)3的最低需求外，地區(qū)4每年最多能分配到60萬噸，這樣其不限的最高需求可等價認為是60萬噸。,,解 這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬

26、噸，最高需求為無限。,按最高需求分析，總需求為210萬噸，大于總產(chǎn)量160萬噸，將此問題定義為銷大于產(chǎn)的運輸問題。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，令其年產(chǎn)量為50萬噸。 各地區(qū)的需要量包含最低和最高兩部分：如地區(qū)1，其中30萬噸是最低需求，故這部分需求不能由假想的化肥廠D來供給，因此相應的運價定義為任意大正數(shù)M ；而另一部分20萬噸滿足與否都是可以的，因此可以由假想化肥廠D來供給，按前面講的，令相應運價為“0”。

27、,,凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)來看待，這樣可以將表4-39所示的運輸問題轉(zhuǎn)換為表4-40所示的運輸問題。,表4-40 （單位：萬噸）,用表上作業(yè)法計算，可以求得這個問題的最優(yōu)方案,如表4-41所示。,19,0,30,2,14,0,2,15,3,1,0,0,,,2,14,0,2,15,3,1,0,0,0,30,20,,,2,2,0,2

28、,2,3,1,0,0,0,30,20,,13,50,,,5,5,7,M,M,3,1,0,0,0,30,20,,13,50,,15,10,,,5,5,7,M,M,3,1,0,0,0,30,20,,13,50,,15,10,,15,30,,,5,5,7,M,M,3,0,0,0,0,30,20,,13,50,,15,10,,15,30,,13,20,,14,,5,5,7,M,M,3,1,0,0,0,30,20,,13,50,,15,10,,1

29、5,30,,13,20,,0,,30,,20,,[例4-6] 在A1、A2、A3、A4、A5和A6六個經(jīng)濟區(qū)之間有磚、砂子、爐灰、塊石、卵石、木材和鋼材七種物資需要運輸。具體的運輸需求如表4-43所示，各地點間的路程（公里）見表4-44，試確定一個最優(yōu)的汽車調(diào)度方案。,表4-43,表4-44,,汽車的最優(yōu)調(diào)度實質(zhì)上就是空車行駛的公里數(shù)最少。先構(gòu)造如表4-45所示的各地區(qū)汽車出入平衡表，表中“十”號表示該點產(chǎn)生空車，“—”號表示該點需要調(diào)

30、進空車。,表4-44,平衡結(jié)果A1、A5、A6除裝運自己的貨物外，可多出空車21車次；A2、A3、A4缺21車次。按最小空駛調(diào)度，可構(gòu)造表4-46所示的運輸問題數(shù)據(jù)表，進而可得表4-47所示的最優(yōu)調(diào)度方案。,表4-45,表4-46,作 業(yè),課本P62：6、7題課本P63：8題,2024/3/31,第62頁習題,6.已知某廠每月可生產(chǎn)甲產(chǎn)品270噸，先運至A1、A2、A3三個倉庫，然后在分別供應B1、B2、B3、B4、B5五個用戶。

31、已知倉庫容量分別為50、100、150噸，各用戶的需要量分別為25、105、60、30、70噸。已知從該廠經(jīng)各倉庫然后供應各用戶的運費如下表所示，試確定一個使總運費最少的調(diào)運方案。,倉庫總?cè)萘浚?0+100+150=300（t）各地區(qū)需求：25+105+60+30+70=290（t）由于該廠每月最多生產(chǎn)甲產(chǎn)品270t，則倉庫有30t不滿，各地區(qū)有20t不能滿足需求可假設(shè)存在倉庫A4，它的存儲量為20t，用戶B6 的需求量為30t。

32、這樣就轉(zhuǎn)化為產(chǎn)銷平衡問題。由于A4 與B6都是假設(shè)的，不需要運輸，故運價都為0，但是由A4運到B6的運輸無法發(fā)生，因兩者皆為假設(shè)的，運價為無窮大，設(shè)為M。,此題屬于產(chǎn)銷不平衡問題,2024/3/31,第62頁習題,?,用伏格爾法求解初始基可行解得：,數(shù)字格內(nèi)填入相應價格，用位勢法檢驗是否為最優(yōu)解，得：,,,用位勢法檢驗是否為最優(yōu)解，得：,,,因檢驗數(shù)存在負數(shù)，故需用閉合回路法調(diào)整,用閉合回路法調(diào)整得：,,,,,,,,,,,,,用位勢法檢

33、驗得：,,因檢驗數(shù)全為正，所以已得最優(yōu)方案。即A3差30t沒有得到滿足， B2缺5t，B4缺15t。,7、已知某運輸問題的單位運價及最優(yōu)調(diào)運方案如表所示（括號中的數(shù)據(jù)代表運輸數(shù)量），由于產(chǎn)地A2至銷地B2的道路關(guān)閉，故最優(yōu)調(diào)運方案將發(fā)生變化，試在原最優(yōu)調(diào)運方案的基礎(chǔ)上，尋找新的最優(yōu)調(diào)運方案。,表4-50,解：由于A2 到B2道路關(guān)閉，則其運價為M，應令其出基，以實現(xiàn)最優(yōu)調(diào)度。先將M反映進產(chǎn)銷平衡表，然后用位勢法作檢驗，有：,,要令A2

34、 B2出基，即令其運輸量為0，找出負檢驗數(shù)最小的來進行調(diào)整，得：,用位勢法作檢驗，有：,,,檢驗數(shù)已全為非負，故已得最優(yōu)調(diào)度方案。,8、已知某運輸問題的單位運價及最優(yōu)調(diào)運方案如表4所示，試回答下述問題：(1)A1到B2、A3到B5、和A4到B1的單位運價，分別在什么范圍內(nèi)變化時上表中給出的最優(yōu)方案不變；(2)若A1到B2的單位運價由1變?yōu)?，最優(yōu)方案將發(fā)生怎樣的變化；(3)若A3到B5的單位運價由4變?yōu)?，最優(yōu)方案將發(fā)生怎樣的變

35、化；,2024/3/31,表4-51,解：（1）設(shè)A1 到B2的單位運價為c12，因A1 到B2是基變量，它的運價變化會引起非基變量檢驗系數(shù)的變化，此時，只需對其再進行位勢法分析即可。,要令最優(yōu)方案不變，則非基變量的檢驗數(shù)非負；故有c12 ≥0；3- c12 ≥ 0；4- c12 ≥0；2- c12 ≥ 0；2+ c12≥0；1+ c12 ≥ 0解上述不等式得0≤ c12 ≤2。即A1 到B2的單位運價在[0，2]內(nèi)變化時，最有方案

36、不變。,,,(1),A3 到B5的單位運價屬于非基變量，它的變化不會引起其它檢驗數(shù)變化，故只需保證其檢驗數(shù)非負即可。,先用位勢法算出原方案的檢驗數(shù)：,,設(shè)A3 到B5的單位運價為c35，則其檢驗數(shù)滿足c35 -（1+2）≥ 0，即c35 ≥ 3。也就是說A3 到B5的單位運價大于等于3時，最有方案不變。,A4 到B1的單位運價屬于非基變量，它的變化不會引起其它檢驗數(shù)變化，故只需保證其檢驗數(shù)非負即可。,設(shè)A4到B1的單位運價為c41，

37、則其檢驗數(shù)滿足c41 -（0+2）≥ 0，即c35 ≥2。也就是說A4到B1的單位運價大于等于2時，即A4 到B1的單位運價變化范圍是[2，+∞)最有方案不變。,先用位勢法算出原方案的檢驗數(shù)：,把變化直接反映到表中可得下表：,,,(2)若A1到B2的單位運價由1變?yōu)?，最優(yōu)方案將發(fā)生怎樣的變化；,因存在檢驗數(shù)為負數(shù)，最優(yōu)方案發(fā)生改變，用閉合回路法調(diào)整得：,表4-51,,,,,,,重新計算檢驗數(shù)，得：,非基變量檢驗數(shù)均為非負，故為最優(yōu)方