運(yùn)輸問(wèn)題表上作業(yè)法.ppt

4.2 表上作業(yè)法,表上作業(yè)法 表上作業(yè)法與單純形法的關(guān)系 表上作業(yè)法的基本步驟 確定初始基可行解 最小元素法的基本步驟 伏格爾法,三、 運(yùn)輸問(wèn)題的求解,運(yùn)輸問(wèn)題的求解采用表上作業(yè)法，即用列表的方法求解線性規(guī)劃問(wèn)題中的運(yùn)輸模型的計(jì)算方法，實(shí)質(zhì)上是單純形法。,表上作業(yè)法是一種特定形式的單純形法，它與單純形法有著完全相同的解題步驟，所不同的只是完成各步采用的具體形式。,1.表上作業(yè)法,2.表上作業(yè)法與單純形法的關(guān)系,表上作業(yè)法中的最小元素法和伏格爾法實(shí)質(zhì)上是在求單純形表中的初始基可行解； 表上作業(yè)法中的“位勢(shì)法”實(shí)質(zhì)上是在求單純形表中的檢驗(yàn)數(shù)； 調(diào)運(yùn)方案表中數(shù)字格的數(shù)實(shí)質(zhì)上就是單純形法中基變量的值； 調(diào)運(yùn)方案表上的“閉回路法”實(shí)質(zhì)上是在做單純形表上的換基迭代。,（1）找出初始基可行解： m+n-1個(gè)數(shù)字格（基變量）； （2）求各非基變量（空格）的檢驗(yàn)數(shù)。,那么,選取xij為入基變量；,（3）確定入基變量，若,3.表上作業(yè)法的基本步驟,（4）確定出基變量，找出入基變量的閉合回路； （5）在表上用閉合回路法調(diào)整運(yùn)輸方案； （6）重復(fù)2、3、4、5步驟，直到得到最優(yōu)解。,4、確定初始基可行解,與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運(yùn)輸問(wèn)題一定具有可行解（同時(shí)也一定存在最優(yōu)解）。 最小元素法（the least cost rule）和伏格爾法（Vogels approximation method）。,最小元素法的基本思想是就近供應(yīng)，即從單位 運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系，依此 類推，一直到給出基本方案為止.,最小元素法,找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng) ； 劃掉已滿足要求的行或 (和) 列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”； 在剩余的運(yùn)價(jià)表中重復(fù)1、2兩步，直到得到初始基可行解。,5、最小元素法的基本步驟,最小元素法,最小元素法的基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方案為止。,表4-1,最小元素法的應(yīng)用（以引例4-1為例）,第一步：從表4-1中找出最小運(yùn)價(jià)“1”， 最小運(yùn)價(jià)所確定的供應(yīng)關(guān)系為（B，甲），在（B，甲）的交叉格處填上“3”，形成表4-2；將運(yùn)價(jià)表的甲列運(yùn)價(jià)劃去得表4-3.,表4-2,表4-3,3,第二步：在表4-3的未被劃掉的元素中再找出最小運(yùn)價(jià)“2”，最小運(yùn)價(jià)所確定的供應(yīng)關(guān)系為（B，丙），即將B余下的1個(gè)單位產(chǎn)品供應(yīng)給丙，表4-2轉(zhuǎn)換成表4-4。劃去B行的運(yùn)價(jià)，劃去B行表明B所生產(chǎn)的產(chǎn)品已全部運(yùn)出，表4-3轉(zhuǎn)換成表4-5。,表4-3,表4-4,表4-5,3,1,表4-5,第三步：在表4-5中再找出最小運(yùn)價(jià)“3”，這樣一步步地進(jìn)行下去，直到單位運(yùn)價(jià)表上的所有元素均被劃去為止。,表4-7,表4-6,3,2,1,3,4,4,6,5,3,3,最后在產(chǎn)銷平衡表上得到一個(gè)調(diào)運(yùn)方案，見(jiàn)表4-6。這一方案的總運(yùn)費(fèi)為86個(gè)單位。,最小元素法各步在運(yùn)價(jià)表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個(gè)數(shù)相應(yīng)地劃掉一行或一列，這樣最終將得到一個(gè)具有m+n-1個(gè)數(shù)字格（基變量）的初始基可行解。,在供需關(guān)系格（i，j ）處填入一數(shù)字，剛好使第 i個(gè)產(chǎn)地的產(chǎn)品調(diào)空，同時(shí)也使第j個(gè)銷地的需求得到滿足。填入一數(shù)字同時(shí)劃去了一行和一列，那么最終必然無(wú)法得到一個(gè)具有m+n-1個(gè)數(shù)字格（基變量）的初始基可行解。,6.應(yīng)注意的問(wèn)題,為了使在產(chǎn)銷平衡表上有m+n-1個(gè)數(shù)字格，這時(shí)需要在第行或第列此前未被劃掉的任意一個(gè)空格上填一個(gè)“0”。填“0”格雖然所反映的運(yùn)輸量同空格沒(méi)有什么不同；但它所對(duì)應(yīng)的變量卻是基變量，而空格所對(duì)應(yīng)的變量是非基變量。,表4-7,表4-8,3,1,4,7. 舉例 將例4-1的各工廠的產(chǎn)量做適當(dāng)調(diào)整（調(diào)整結(jié)果見(jiàn)表4-7），就會(huì)出現(xiàn)上述特殊情況。,0,6,6,每次從當(dāng)前運(yùn)價(jià)表上，計(jì)算各行各列中兩個(gè)最小運(yùn)價(jià)之差值（行差值hi，列差值kj），優(yōu)先取最大差值的行或列中最小的格來(lái)確定運(yùn)輸關(guān)系，直到求出初始方案。,8.伏格法爾法,伏格爾法的基本步驟：,8.伏格爾法,1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差； 2.找出最大差所在的行或列； 3.找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng) ； 4.劃掉已滿足要求的行或 (和) 列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”； 5.在剩余的運(yùn)價(jià)表中重復(fù)14步，直到得到初始基可行解。,表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,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 由以上可見(jiàn)，伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟是完全相同的。伏格爾法給出的初始解比最小元素法給出的初始解一般來(lái)講會(huì)更接近于最優(yōu)解。,表4-23,6,3,3,5,1,2,4.2.2 基可行解的最優(yōu)性檢驗(yàn),對(duì)初始基可行解的最優(yōu)性檢驗(yàn)有閉合回路法和位勢(shì)法兩種基本方法。閉合回路法具體、直接，并為方案調(diào)整指明了方向；而位勢(shì)法具有批處理的功能，提高了計(jì)算效率。 所謂閉合回路是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉合回路。一個(gè)空格存在唯一的閉回路。,所謂閉合回路法，就是對(duì)于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對(duì)這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后我們計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來(lái)的變化。如果所有代表非基變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。,1.閉合回路,下面就以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論閉合回路法。,表4-24,（+3）,（-3）,（+2）,（-1）,從表4-6給定的初始方案的任一空格出發(fā)尋找閉合回路，如對(duì)于空格（A，甲）在初始方案的基礎(chǔ)上將A生產(chǎn)的產(chǎn)品調(diào)運(yùn)一個(gè)單位給甲，為了保持新的平衡，就要依次在（A，丙）處減少一個(gè)單位、（B，丙）處增加一個(gè)單位、（B，甲）處減少一個(gè)單位；即要尋找一條除空格（A，甲）之外其余頂點(diǎn)均為有數(shù)字格（基變量）組成的閉合回路。表4-24中用虛線畫出了這條閉合回路。閉合回路頂點(diǎn)所在格括號(hào)內(nèi)的數(shù)字是相應(yīng)的單位運(yùn)價(jià)，單位運(yùn)價(jià)前的“+”、“-”號(hào)表示運(yùn)量的調(diào)整方向。,對(duì)應(yīng)這樣的方案調(diào)整，運(yùn)費(fèi)會(huì)有什么變化呢？可以看出（A，甲）處增加一個(gè)單位，運(yùn)費(fèi)增加3個(gè)單位；在（A，丙）處減少一個(gè)單位，運(yùn)費(fèi)減少3個(gè)單位；在（B，丙）處增加一個(gè)單位，運(yùn)費(fèi)增加2個(gè)單位；在（B，甲）處減少一個(gè)單位，運(yùn)費(fèi)減少1個(gè)單位。增減相抵后，總的運(yùn)費(fèi)增加了1個(gè)單位。由檢驗(yàn)數(shù)的經(jīng)濟(jì)含義可以知道，（A，甲）處單位運(yùn)量調(diào)整所引起的運(yùn)費(fèi)增量就是（A，甲）的檢驗(yàn)數(shù)，即11=1。,表4-24,（+3）,（-3）,（+2）,（-1）,仿照此步驟可以計(jì)算初始方案中所有空格的檢驗(yàn)數(shù)，表4-25表4-30展示了各檢驗(yàn)數(shù)的計(jì)算過(guò)程，表4-30給出了最終結(jié)果?？梢宰C明，對(duì)初始方案中的每一個(gè)空格來(lái)說(shuō)“閉合回路存在且唯一”。,表4-25,表4-26,表4-27,表4-28,表4-29,表4-30,如果檢驗(yàn)數(shù)表中所有數(shù)字均大于等于零，這表明對(duì)調(diào)運(yùn)方案做出任何改變都將導(dǎo)致運(yùn)費(fèi)的增加，即給定的方案是最優(yōu)方案。在表4-30中， 24 = -1,說(shuō)明方案需要進(jìn)一步改進(jìn)。,2.位勢(shì)法,對(duì)于特定的調(diào)運(yùn)方案的每一行給出一個(gè)因子 ui（稱為行位勢(shì)），每一列給出一個(gè)因子vj（稱為列位勢(shì)），使對(duì)于目前解的每一個(gè)基變量xij 有cij= ui + vj，這里的ui 和 vj可正、可負(fù)也可以為零。那么任一非基變量 xij的檢驗(yàn)數(shù)就是,這一表達(dá)式完全可以通過(guò)先前所述的閉合回路法得到。在某一的閉合回路上（如下表所示），由于基變量的運(yùn)價(jià)等于其所對(duì)應(yīng)的行位勢(shì)與列位勢(shì)之和，即：,非基變量,基變量,（-cik）基變量,（+clk）基變量,于是,所以,對(duì)于一個(gè)具有m個(gè)產(chǎn)地、n個(gè)銷地的運(yùn)輸問(wèn)題，應(yīng)具有m個(gè)行位勢(shì)、n個(gè)列位勢(shì)，即具有“m+n”個(gè)位勢(shì)。運(yùn)輸問(wèn)題基變量的個(gè)數(shù)只有“m+n-1”個(gè)，所以利用基變量所對(duì)應(yīng)的“m+n-1”個(gè)方程，求出“m+n”個(gè)位勢(shì)，進(jìn)而計(jì)算各非基變量的檢驗(yàn)數(shù)是不現(xiàn)實(shí)的。,通常可以通過(guò)在這些方程中對(duì)任意一個(gè)因子假定一個(gè)任意的值（如u1=0等等），再求解其余的“m+n-1”個(gè)未知因子，這樣就可求得所有空格（非基變量）的檢驗(yàn)數(shù)。仍以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論位勢(shì)法求解非基變量檢驗(yàn)數(shù)的過(guò)程。,第一步：把方案表中基變量格填入其相應(yīng)的運(yùn)價(jià)并令u1=0 ；讓每一個(gè)基變量xij都有cij= ui + vj ，可求得所有的位勢(shì)，如表4-32所示。,表4-32,第二步：利用,計(jì)算各非基變量xij,的檢驗(yàn)數(shù)，結(jié)果見(jiàn)表4-30。,10,3,-1,-5,9,2,0,4.2.3方案的優(yōu)化,在負(fù)檢驗(yàn)數(shù)中找出最小的檢驗(yàn)數(shù)，該檢驗(yàn)數(shù)所對(duì)應(yīng)的變量即為入基變量。在入基變量所處的閉合回路上，賦予入基變量最大的增量，即可完成方案的優(yōu)化。在入基變量有最大增量的同時(shí)，一定存在原來(lái)的某一基變量減少為“0”，該變量即為出基變量。切記出基變量的“0”運(yùn)量要用“空格”來(lái)表示，而不能留有“0”。,在表4-30中，,，故選擇,x24為入基變量。在入基變量x24所處的閉合回路上 （如表4-33所示），賦予最大的增量“1”，相應(yīng)地有 x23最大的增量“1”，相應(yīng)地有x23出基, x13=5,x14=2.,利用閉合回路法或位勢(shì)法計(jì)算各空格（非基變量）的 檢驗(yàn)數(shù)，可得表4-34（同伏格爾法的初始解表4-23）。,表4-30,表4-33,表4-34,由于表4-33中的檢驗(yàn)數(shù)均大于等于零，所以表4-33（同伏格爾法所給出的初始解表4-23）給出的方案是最優(yōu)方案，這個(gè)最優(yōu)方案的運(yùn)費(fèi)是85個(gè)單位。,23 = 1,31 = 9,22 = 2,11 = 1,12 = 2,33 = 12,4.3運(yùn)輸問(wèn)題的拓展,總產(chǎn)量大于總銷量的運(yùn)輸問(wèn)題即為產(chǎn)大于銷的運(yùn)輸問(wèn)題。 在實(shí)際問(wèn)題中，產(chǎn)大于銷意味著某些產(chǎn)品被積壓在倉(cāng)庫(kù)中?？梢赃@樣設(shè)想，如果把倉(cāng)庫(kù)也看成是一個(gè)假想的銷地，并令其銷量剛好等于總產(chǎn)量與總銷量的差；那么，產(chǎn)大于銷的運(yùn)輸問(wèn)題就轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問(wèn)題 假想一個(gè)銷地，相當(dāng)于在原產(chǎn)銷關(guān)系表上增加一列。,4.3.1產(chǎn)大于銷的運(yùn)輸問(wèn)題,假想列所對(duì)應(yīng)的運(yùn)價(jià),由于假想的銷地代表的是倉(cāng)庫(kù)，而我們優(yōu)化的運(yùn)費(fèi)是產(chǎn)地與銷地間的運(yùn)輸費(fèi)用，并不包括廠內(nèi)的運(yùn)輸費(fèi)用；所以假想列所對(duì)應(yīng)的運(yùn)價(jià)都應(yīng)取為“0”。,至此，我們已經(jīng)將產(chǎn)大于銷的運(yùn)輸問(wèn)題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問(wèn)題，進(jìn)一步的求解可利用上節(jié)介紹的表上作業(yè)法來(lái)完成。,例4-2 將表4-35所示的產(chǎn)大于銷的運(yùn)輸問(wèn)題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問(wèn)題,表4-35,解 此運(yùn)輸問(wèn)題的總產(chǎn)量為23、總銷量為20，所以假設(shè)一個(gè)銷地戊并令其銷量剛好等于總產(chǎn)量與總銷量的差“3”。取假想的戊列所對(duì)應(yīng)的運(yùn)價(jià)都為“0”，可得表4-36所示的產(chǎn)銷平衡運(yùn)輸問(wèn)題。,表4-36,4.3.2銷大于產(chǎn)的運(yùn)輸問(wèn)題,總銷量大于總產(chǎn)量的運(yùn)輸問(wèn)題即為銷大于產(chǎn)的運(yùn)輸問(wèn)題。 可以這樣設(shè)想，假想一個(gè)產(chǎn)地，并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差；那么，銷大于產(chǎn)的運(yùn)輸問(wèn)題同樣可以轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問(wèn)題 假想的產(chǎn)地并不存在，于是各銷地從假想產(chǎn)地所得到的運(yùn)量，實(shí)際上所表示的是其未滿足的需求。 由于假想的產(chǎn)地與各銷地之間并不存在實(shí)際的運(yùn)輸，所以假想的產(chǎn)地行所有的運(yùn)價(jià)都應(yīng)該是“0”。 至此，我們又將銷大于產(chǎn)的運(yùn)輸問(wèn)題轉(zhuǎn)換成了產(chǎn)銷平衡的運(yùn)輸問(wèn)題。,例4-3 將表4-37所示的銷大于產(chǎn)的運(yùn)輸問(wèn)題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問(wèn)題,表4-37,解 此運(yùn)輸問(wèn)題的總產(chǎn)量為20、總銷量為28，所以假設(shè)一個(gè)產(chǎn)地D并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差“8”。令假想的D行所對(duì)應(yīng)的運(yùn)價(jià)都為“0”，可得表4-37所示的產(chǎn)銷平衡運(yùn)輸問(wèn)題。,表4-38,4.3.3運(yùn)輸問(wèn)題的應(yīng)用舉例,例4-4 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥需求，假定等量化肥在這些地區(qū)的使用效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的單位運(yùn)價(jià)如表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萬(wàn)噸，這樣其不限的最高需求可等價(jià)認(rèn)為是60萬(wàn)噸。,解 這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題，總產(chǎn)量為160萬(wàn)噸，四個(gè)地區(qū)的最低需求為110萬(wàn)噸，最高需求為無(wú)限。,按最高需求分析，總需求為210萬(wàn)噸，大于總產(chǎn)量160萬(wàn)噸，將此問(wèn)題定義為銷大于產(chǎn)的運(yùn)輸問(wèn)題。 為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠D，令其年產(chǎn)量為50萬(wàn)噸。 各地區(qū)的需要量包含最低和最高兩部分：如地區(qū)1，其中30萬(wàn)噸是最低需求，故這部分需求不能由假想的化肥廠D來(lái)供給，因此相應(yīng)的運(yùn)價(jià)定義為任意大正數(shù)M ；而另一部分20萬(wàn)噸滿足與否都是可以的，因此可以由假想化肥廠D來(lái)供給，按前面講的，令相應(yīng)運(yùn)價(jià)為“0”。,凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個(gè)地區(qū)來(lái)看待，這樣可以將表4-39所示的運(yùn)輸問(wèn)題轉(zhuǎn)換為表4-40所示的運(yùn)輸問(wèn)題。,表4-40 （單位：萬(wàn)噸）,用表上作業(yè)法計(jì)算，可以求得這個(gè)問(wèn)題的最優(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,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,15,30,13,20,0,30,20,例4-6 在A1、A2、A3、A4、A5和A6六個(gè)經(jīng)濟(jì)區(qū)之間有磚、砂子、爐灰、塊石、卵石、木材和鋼材七種物資需要運(yùn)輸。具體的運(yùn)輸需求如表4-43所示，各地點(diǎn)間的路程（公里）見(jiàn)表4-44，試確定一個(gè)最優(yōu)的汽車調(diào)度方案。,表4-43,表4-44,汽車的最優(yōu)調(diào)度實(shí)質(zhì)上就是空車行駛的公里數(shù)最少。先構(gòu)造如表4-45所示的各地區(qū)汽車出入平衡表，表中“十”號(hào)表示該點(diǎn)產(chǎn)生空車，“”號(hào)表示該點(diǎn)需要調(diào)進(jìn)空車。,表4-44,平衡結(jié)果A1、A5、A6除裝運(yùn)自己的貨物外，可多出空車21車次；A2、A3、A4缺21車次。按最小空駛調(diào)度，可構(gòu)造表4-46所示的運(yùn)輸問(wèn)題數(shù)據(jù)表，進(jìn)而可得表4-47所示的最優(yōu)調(diào)度方案。,表4-45,表4-46,作 業(yè),課本P62：6、7題 課本P63：8題,2019/7/8,第62頁(yè)習(xí)題,6.已知某廠每月可生產(chǎn)甲產(chǎn)品270噸，先運(yùn)至A1、A2、A3三個(gè)倉(cāng)庫(kù)，然后在分別供應(yīng)B1、B2、B3、B4、B5五個(gè)用戶。已知倉(cāng)庫(kù)容量分別為50、100、150噸，各用戶的需要量分別為25、105、60、30、70噸。已知從該廠經(jīng)各倉(cāng)庫(kù)然后供應(yīng)各用戶的運(yùn)費(fèi)如下表所示，試確定一個(gè)使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。,倉(cāng)庫(kù)總?cè)萘浚?0+100+150=300（t） 各地區(qū)需求：25+105+60+30+70=290（t） 由于該廠每月最多生產(chǎn)甲產(chǎn)品270t，則倉(cāng)庫(kù)有30t不滿，各地區(qū)有20t不能滿足需求 可假設(shè)存在倉(cāng)庫(kù)A4，它的存儲(chǔ)量為20t，用戶B6 的需求量為30t。這樣就轉(zhuǎn)化為產(chǎn)銷平衡問(wèn)題。由于A4 與B6都是假設(shè)的，不需要運(yùn)輸，故運(yùn)價(jià)都為0，但是由A4運(yùn)到B6的運(yùn)輸無(wú)法發(fā)生，因兩者皆為假設(shè)的，運(yùn)價(jià)為無(wú)窮大，設(shè)為M。,此題屬于產(chǎn)銷不平衡問(wèn)題,2019/7/8,第62頁(yè)習(xí)題,用伏格爾法求解初始基可行解得：,數(shù)字格內(nèi)填入相應(yīng)價(jià)格，用位勢(shì)法檢驗(yàn)是否為最優(yōu)解，得：,用位勢(shì)法檢驗(yàn)是否為最優(yōu)解，得：,因檢驗(yàn)數(shù)存在負(fù)數(shù)，故需用閉合回路法調(diào)整,用閉合回路法調(diào)整得：,用位勢(shì)法檢驗(yàn)得：,因檢驗(yàn)數(shù)全為正，所以已得最優(yōu)方案。 即A3差30t沒(méi)有得到滿足， B2缺5t，B4缺15t。,7、已知某運(yùn)輸問(wèn)題的單位運(yùn)價(jià)及最優(yōu)調(diào)運(yùn)方案如表所示（括號(hào)中的數(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)價(jià)為M，應(yīng)令其出基，以實(shí)現(xiàn)最優(yōu)調(diào)度。先將M反映進(jìn)產(chǎn)銷平衡表，然后用位勢(shì)法作檢驗(yàn)，有：,要令A(yù)2 B2出基，即令其運(yùn)輸量為0，找出負(fù)檢驗(yàn)數(shù)最小的來(lái) 進(jìn)行調(diào)整，得：,用位勢(shì)法作檢驗(yàn)，有：,檢驗(yàn)數(shù)已全為非負(fù)，故已得最優(yōu)調(diào)度方案。,8、已知某運(yùn)輸問(wèn)題的單位運(yùn)價(jià)及最優(yōu)調(diào)運(yùn)方案如表4所示，試回答下述問(wèn)題： (1)A1到B2、A3到B5、和A4到B1的單位運(yùn)價(jià)，分別在什么范圍內(nèi)變化時(shí)上表中給出的最優(yōu)方案不變； (2)若A1到B2的單位運(yùn)價(jià)由1變?yōu)?，最優(yōu)方案將發(fā)生怎樣的變化； (3)若