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

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

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

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

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

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

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

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

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

9、,8.伏格爾法,1.計算每行、列兩個最小運(yùn)價的差；2.找出最大差所在的行或列；3.找出該行或列的最小運(yùn)價，確定供求關(guān)系，最大量的供應(yīng) ；4.劃掉已滿足要求的行或 (和) 列，如果需要同時劃去行和列，必須要在該行或列的任意位置填個“0”；5.在剩余的運(yùn)價表中重復(fù)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,,,總運(yùn)費(fèi)為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)運(yùn)方案的運(yùn)輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉合回路。一個空格存在唯一的閉回路。,所謂

12、閉合回路法，就是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后我們計算出由這些變化給整個運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。如果所有代表非基變量的空格的檢驗數(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)運(yùn)一個單位給甲，為了保持新的平衡，就要依次在（A，丙）處減少一個單位、（B，丙）處增加一個單位、（B，甲）處減少一個單位；即要尋找一條除空格（A，甲）之外其余頂點(diǎn)均為有數(shù)字格（基變量）組成的閉合回路。表4-24中用虛線畫出了這條閉合回路。閉合回路頂點(diǎn)所在格括號內(nèi)的數(shù)字是相應(yīng)的單位運(yùn)

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

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

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

18、意的值（如u1=0等等），再求解其余的“m+n-1”個未知因子，這樣就可求得所有空格（非基變量）的檢驗數(shù)。仍以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論位勢法求解非基變量檢驗數(shù)的過程。,,第一步：把方案表中基變量格填入其相應(yīng)的運(yùn)價并令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)化,在負(fù)檢驗數(shù)中找出最小的檢驗數(shù)，該檢驗數(shù)所對應(yīng)的變量即為入基變量。在入基變量所處的閉合回路上，賦予入基變量最大的增量，即可完成方案的優(yōu)化。在入基變量有最大增量的同時，一定存在原來的某一基變量減少為“0”，該變量即為出基變量。切記出基變量的“0”運(yùn)量要用“空格”來表示，而不能留有“0”。,在表4-30中，,,，故選擇,x24為入基變量。在入基變量x24所處的閉合回路上

20、（如表4-33所示），賦予最大的增量“1”，相應(yīng)地有x23最大的增量“1”，相應(yīng)地有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)方案的運(yùn)費(fèi)是85個單位。,?23 = 1,?

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

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

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

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

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

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

27、,,凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)來看待，這樣可以將表4-39所示的運(yùn)輸問題轉(zhuǎn)換為表4-40所示的運(yùn)輸問題。,表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)濟(jì)區(qū)之間有磚、砂子、爐灰、塊石、卵石、木材和鋼材七種物資需要運(yùn)輸。具體的運(yùn)輸需求如表4-43所示，各地點(diǎn)間的路程（公里）見表4-44，試確定一個最優(yōu)的汽車調(diào)度方案。,表4-43,表4-44,,汽車的最優(yōu)調(diào)度實質(zhì)上就是空車行駛的公里數(shù)最少。先構(gòu)造如表4-45所示的各地區(qū)汽車出入平衡表，表中“十”號表示該點(diǎn)產(chǎn)生空車，“—”號表示該點(diǎn)需要調(diào)

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

31、已知倉庫容量分別為50、100、150噸，各用戶的需要量分別為25、105、60、30、70噸。已知從該廠經(jīng)各倉庫然后供應(yīng)各用戶的運(yùn)費(fèi)如下表所示，試確定一個使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。,倉庫總?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è)的，不需要運(yùn)輸，故運(yùn)價都為0，但是由A4運(yùn)到B6的運(yùn)輸無法發(fā)生，因兩者皆為假設(shè)的，運(yùn)價為無窮大，設(shè)為M。,此題屬于產(chǎn)銷不平衡問題,2024/3/31,第62頁習(xí)題,?,用伏格爾法求解初始基可行解得：,數(shù)字格內(nèi)填入相應(yīng)價格，用位勢法檢驗是否為最優(yōu)解，得：,,,用位勢法檢驗是否為最優(yōu)解，得：,,,因檢驗數(shù)存在負(fù)數(shù)，故需用閉合回路法調(diào)整,用閉合回路法調(diào)整得：,,,,,,,,,,,,,用位勢法檢

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

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

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

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

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