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

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

2、是完成各步采用的具體形式。不同的只是完成各步采用的具體形式。1.1.表上作業(yè)法表上作業(yè)法2.2.表上作業(yè)法與單純形法的關(guān)系表上作業(yè)法與單純形法的關(guān)系|表上作業(yè)法中的最小元素法和伏格爾法實質(zhì)表上作業(yè)法中的最小元素法和伏格爾法實質(zhì)上是在求單純形表中的初始基可行解；上是在求單純形表中的初始基可行解；|表上作業(yè)法中的表上作業(yè)法中的“位勢法位勢法”實質(zhì)上是在求單實質(zhì)上是在求單純形表中的檢驗數(shù)；純形表中的檢驗數(shù)；|調(diào)運方案表中數(shù)字格的數(shù)實質(zhì)上就是單純形調(diào)運方案表中數(shù)字格的數(shù)實質(zhì)上就是單純形法中基變量的值；法中基變量的值；|調(diào)運方案表上的調(diào)運方案表上的“閉回路法閉回路法”實質(zhì)上是在做實質(zhì)上是在做單純形表上的

3、換基迭代。單純形表上的換基迭代。|（1 1）找出初始基可行解：）找出初始基可行解： m+n-1m+n-1個數(shù)字格（基變個數(shù)字格（基變量）；量）；|（2 2）求各非基變量（空格）的檢驗數(shù)。）求各非基變量（空格）的檢驗數(shù)。 ,那么那么選取選取xijij為入基變量；為入基變量； |（3 3）確定入基變量，若）確定入基變量，若 min|0ijijlk3.3.表上作業(yè)法的基本步驟表上作業(yè)法的基本步驟| （4 4）確定出基變量，找出入基變量的閉合回路；）確定出基變量，找出入基變量的閉合回路；| （5 5）在表上用閉合回路法調(diào)整運輸方案；）在表上用閉合回路法調(diào)整運輸方案；| （6 6）重復(fù)）重復(fù)2 2、3

4、3、4 4、5 5步驟，直到得到最優(yōu)解。步驟，直到得到最優(yōu)解。4 4、確定初始基可行解、確定初始基可行解 |與一般的線性規(guī)劃不同，與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運輸問產(chǎn)銷平衡的運輸問題一定具有可行解（同時也一定存在最優(yōu)題一定具有可行解（同時也一定存在最優(yōu)解）。解）。|最小元素法最小元素法（the least cost rule）和伏格爾法和伏格爾法（Vogels approximation method）。）。 z最小元素法的基本思想是最小元素法的基本思想是就近供應(yīng)就近供應(yīng)，即從單位，即從單位運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本

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

6、最小的運價開始確定產(chǎn)從單位運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方銷關(guān)系，依此類推，一直到給出基本方案為止。案為止。 表表4-1甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059銷量（銷量（bj）3656最小元素法的應(yīng)用（以引例最小元素法的應(yīng)用（以引例4-14-1為例）為例） 甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）3656甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059銷量（銷量（bj）3656表表4-2表表4-33 甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059

7、銷量（銷量（bj）3656表表4-3甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）3656甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059銷量（銷量（bj）3656表表4-4表表4-531甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059銷量（銷量（bj）3656表表4-5 第三步：在表第三步：在表4-54-5中再找出最小運價中再找出最小運價“3”3”，這樣一步步地進(jìn)行下去，直到單位運價表上這樣一步步地進(jìn)行下去，直到單位運價表上的所有元素均被劃去為止。的所有元素均被劃去為止。 表表4-7甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A

8、 A7B B4C C9銷量（銷量（b bj j）3 3656表表4-6甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A311107B1984C7109銷量（銷量（bj）3656321344653 33|最后在產(chǎn)銷平衡表上得到一個調(diào)運方案，見最后在產(chǎn)銷平衡表上得到一個調(diào)運方案，見表表4-64-6。這一方案的總運費為。這一方案的總運費為8686個單位。個單位。|最小元素法各步在運價表中劃掉的行或列是需求得最小元素法各步在運價表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個數(shù)相應(yīng)地劃掉一行或一列，這樣最終將得到入一個數(shù)相應(yīng)地劃掉一行或一列，這

9、樣最終將得到一個具有一個具有m+n-1m+n-1個數(shù)字格（基變量）的初始基可行解。個數(shù)字格（基變量）的初始基可行解。 6.6.應(yīng)注意的問題應(yīng)注意的問題 表表4-7甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113104B19284C7410512銷量（銷量（bj）3656表表4-8甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A4B4C12銷量（銷量（bj）365631 47. 7. 舉例舉例 將例將例4-14-1的各工廠的產(chǎn)量做適當(dāng)調(diào)整（調(diào)的各工廠的產(chǎn)量做適當(dāng)調(diào)整（調(diào)整結(jié)果見表整結(jié)果見表4-74-7），就會出現(xiàn)上述特殊情況。），就會出現(xiàn)上述特殊情況。 0 06 66 68.8.伏格法爾法伏格法爾法伏格爾法的基

10、本步驟：伏格爾法的基本步驟：8.8.伏格爾法伏格爾法1.1.計算每行、列兩個最小運價的差；計算每行、列兩個最小運價的差；2.2.找出最大差所在的行或列；找出最大差所在的行或列；3.3.找出該行或列的最小運價，確定供求關(guān)系，最大量找出該行或列的最小運價，確定供求關(guān)系，最大量的供應(yīng)的供應(yīng) ；4.4.劃掉已滿足要求的行或劃掉已滿足要求的行或 ( (和和) ) 列，如果需要同時劃列，如果需要同時劃去行和列，必須要在該行或列的任意位置填個去行和列，必須要在該行或列的任意位置填個“0”0”；5.5.在剩余的運價表中重復(fù)在剩余的運價表中重復(fù)1414步，直到得到初始基可步，直到得到初始基可行解。行解。表表4-

11、1甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059銷量（銷量（bj）3656表表4-12甲甲乙乙丙丙丁丁兩最小元素之差兩最小元素之差A(yù)311310B1928C7105兩最小元素之差兩最小元素之差13011254表表4-13甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）3656表表4-14甲甲乙乙丙丙丁丁兩最小元素之差兩最小元素之差A(yù)311310B1928C7410兩最小元素之差兩最小元素之差562130125表表4-15甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）365663表表4-16甲甲乙乙丙丙丁丁兩最小元素之差兩最小元素之

12、差A(yù)311310B928C74105兩最小元素之差兩最小元素之差212011表表4-17甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）3656633表表4- 18 甲甲乙乙丙丙丁丁兩最小元素之差兩最小元素之差A(yù)31110B1928C74105兩最小元素之差兩最小元素之差12673表表4-19甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）3656表表4-20甲甲乙乙丙丙丁丁兩最小元素之差兩最小元素之差A(yù)311310B192C74105兩最小元素之差兩最小元素之差63352812|總運費為總運費為85|由以上可見，伏格爾法同最小元素法除在確由以上可見，伏格爾法同

13、最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟是完定供求關(guān)系的原則上不同外，其余步驟是完全相同的。伏格爾法給出的初始解比最小元全相同的。伏格爾法給出的初始解比最小元素法給出的初始解一般來講會更接近于最優(yōu)素法給出的初始解一般來講會更接近于最優(yōu)解。解。 表表4-23甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A7B4C9銷量（銷量（bj）36566335124.2.2 4.2.2 基可行解的最優(yōu)性檢驗基可行解的最優(yōu)性檢驗n對初始基可行解的最優(yōu)性檢驗有對初始基可行解的最優(yōu)性檢驗有閉合回路法閉合回路法和和位勢法位勢法兩種基本方法。兩種基本方法。閉合回路法具體、閉合回路法具體、直接，并為方案調(diào)整指明了方向；而

14、位勢法直接，并為方案調(diào)整指明了方向；而位勢法具有批處理的功能，提高了計算效率。具有批處理的功能，提高了計算效率。|所謂所謂閉合回路閉合回路是是在已給出的調(diào)運方案的運輸在已給出的調(diào)運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)填入數(shù)字的格才能向左或右轉(zhuǎn)9090度（當(dāng)然也度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉合回路。一個

15、空格存在唯一的閉折線叫做閉合回路。一個空格存在唯一的閉回路。回路。|所謂閉合回路法，就是對于代表非基變量的所謂閉合回路法，就是對于代表非基變量的空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為為1 1，由于產(chǎn)銷平衡的要求，由于產(chǎn)銷平衡的要求, ,我們必須對這個我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少空格的閉回路的頂點的調(diào)運量加上或減少1 1。最后我們計算出由這些變化給整個運輸方案最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)變量的空格的檢驗數(shù)也即非基

16、變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。迭代找出最優(yōu)解。1.1.閉合回路閉合回路n下面就以表下面就以表4-64-6中給出的初始基可行解（最中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論閉合小元素法所給出的初始方案）為例，討論閉合回路法?；芈贩?。表表4-24甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 437B 3 14C639銷量（銷量（bj）3656（+3）（-3）（+2）（-1）|從表從表4-64-6給定的初始方案的任一空格出發(fā)尋找閉合回路，如對給定的初始方案的任一空格出發(fā)尋找閉合回路，如對于空格（于空格（A A，甲）在

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

18、。閉合回路頂點所在格括號內(nèi)的數(shù)字是相應(yīng)的單位運價，單位運價前的價，單位運價前的“+”+”、“-”-”號表示運量的調(diào)整方向。號表示運量的調(diào)整方向。|對應(yīng)這樣的方案調(diào)整，運費會有什么變化呢？可以對應(yīng)這樣的方案調(diào)整，運費會有什么變化呢？可以看出（看出（A A，甲）處增加一個單位，運費增加，甲）處增加一個單位，運費增加3 3個單位；個單位；在（在（A A，丙）處減少一個單位，運費減少，丙）處減少一個單位，運費減少3 3個單位；在個單位；在（B B，丙）處增加一個單位，運費增加，丙）處增加一個單位，運費增加2 2個單位；在個單位；在（B B，甲）處減少一個單位，運費減少，甲）處減少一個單位，運費減少1

19、1個單位。增減個單位。增減相抵后，總的運費增加了相抵后，總的運費增加了1 1個單位。由檢驗數(shù)的經(jīng)濟(jì)個單位。由檢驗數(shù)的經(jīng)濟(jì)含義可以知道，（含義可以知道，（A A，甲）處單位運量調(diào)整所引起的，甲）處單位運量調(diào)整所引起的運費增量就是（運費增量就是（A A，甲）的檢驗數(shù)，即，甲）的檢驗數(shù)，即1111=1=1。 表表4-24甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 437B 3 14C639銷量（銷量（bj）3656（+3）（-3）（+2）（-1）|仿照此步驟可以計算初始方案中所有空仿照此步驟可以計算初始方案中所有空格的檢驗數(shù)，表格的檢驗數(shù)，表4-254-25表表4-304-30展示了各展示了各檢驗數(shù)的計算

20、過程，表檢驗數(shù)的計算過程，表4-304-30給出了最終給出了最終結(jié)果?？梢宰C明，對初始方案中的每一結(jié)果?？梢宰C明，對初始方案中的每一個空格來說個空格來說“閉合回路存在且唯一閉合回路存在且唯一”。表表4-25甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1（+11）43（-10）7B314C6（-4）3（+5）9銷量（銷量（bj）3656表表4-26甲乙丙丁產(chǎn)量（ai）A 11 = 1 12 = 24（+3）3（-10）7B3（+9）1（-2）4C6（-4）3（+5）9銷量（bj）3656表表4-27甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1 12 = 24（+3）3（-10）7B3

21、22 = 11（-2）（+8）4C639銷量（銷量（bj）3656表表4-28甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1 12 = 24（-3）3（+10）7B3 22 = 11 24 = -14C6（+10）3（-5）9銷量（銷量（bj）3656表表4-29甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1 12 = 24（-3）3（+10）7B3（-1） 22 = 11（+2） 24 = -14C（+7）6 33 = 123（-5）9銷量（銷量（bj）3656表表4-30甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1 12 = 2437B3 22 = 11 24 = -14C

22、31 = 106 33 = 1239銷量（銷量（bj）3656|如果檢驗數(shù)表中所有數(shù)字均大于等于零，如果檢驗數(shù)表中所有數(shù)字均大于等于零，這表明對調(diào)運方案做出任何改變都將導(dǎo)這表明對調(diào)運方案做出任何改變都將導(dǎo)致運費的增加，即給定的方案是最優(yōu)方致運費的增加，即給定的方案是最優(yōu)方案。在表案。在表4-304-30中，中， 2424 = -1, = -1,說明方案說明方案需要進(jìn)一步改進(jìn)。需要進(jìn)一步改進(jìn)。 2.2.位勢法位勢法)(jiijijvucn這一表達(dá)式完全可以通過先前所述的閉合這一表達(dá)式完全可以通過先前所述的閉合回路法得到。在某一的閉合回路上（如下表回路法得到。在某一的閉合回路上（如下表所示），由于

23、基變量的運價等于其所對應(yīng)的所示），由于基變量的運價等于其所對應(yīng)的行位勢與列位勢之和，即：行位勢與列位勢之和，即： kiikvuckllkvucjlljvuclkxlukv非基變量非基變量基變量基變量ijxiuljxjv（-cik）基變量）基變量ikx（+clk）基變量）基變量 （+cij） （-clj）于是于是所以所以)()()(jlklkiijljlkikijijvuvuvuccccc)(jiijijvucn對于一個具有對于一個具有m m個產(chǎn)地、個產(chǎn)地、n n個銷地的運輸問題，應(yīng)具個銷地的運輸問題，應(yīng)具有有m m個行位勢、個行位勢、n n個列位勢，即具有個列位勢，即具有“m+nm+n”個位勢

24、。個位勢。運輸問題基變量的個數(shù)只有運輸問題基變量的個數(shù)只有“m+n-1”m+n-1”個，所以利個，所以利用基變量所對應(yīng)的用基變量所對應(yīng)的“m+n-1”m+n-1”個方程，求出個方程，求出“m+nm+n”個位勢，進(jìn)而計算各非基變量的檢驗數(shù)是不現(xiàn)實的。個位勢，進(jìn)而計算各非基變量的檢驗數(shù)是不現(xiàn)實的。n通?？梢酝ㄟ^在這些方程中對任意一個因子假定一通?？梢酝ㄟ^在這些方程中對任意一個因子假定一個任意的值（如個任意的值（如u1=0等等），再求解其余的等等），再求解其余的“m+n-1”個未知因子，這樣就可求得所有空格（非基變量）個未知因子，這樣就可求得所有空格（非基變量）的檢驗數(shù)。仍以表的檢驗數(shù)。仍以表4-6

25、中給出的初始基可行解（最小中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論位勢法求解元素法所給出的初始方案）為例，討論位勢法求解非基變量檢驗數(shù)的過程。非基變量檢驗數(shù)的過程。|第一步：把方案表中基變量格填入其相應(yīng)的第一步：把方案表中基變量格填入其相應(yīng)的運價并令運價并令u u1 1=0 =0 ；讓每一個基變量；讓每一個基變量xijij都有都有c cijij= = u ui i + + v vj j ，可求得所有的位勢，如表，可求得所有的位勢，如表4-324-32所所示。示。iujv表表4-32甲甲乙乙丙丙丁丁A310B12C45|第二步：利用第二步：利用 )(jiijijvuc計算各非

26、基變量計算各非基變量xij 的檢驗數(shù)，結(jié)果見表的檢驗數(shù)，結(jié)果見表4-30。 103-1-59204.2.34.2.3方案的優(yōu)化方案的優(yōu)化n在負(fù)檢驗數(shù)中找出最小的檢驗數(shù)，該檢驗數(shù)在負(fù)檢驗數(shù)中找出最小的檢驗數(shù)，該檢驗數(shù)所對應(yīng)的變量即為入基變量。在入基變量所所對應(yīng)的變量即為入基變量。在入基變量所處的閉合回路上，賦予入基變量最大的增量，處的閉合回路上，賦予入基變量最大的增量，即可完成方案的優(yōu)化。在入基變量有最大增即可完成方案的優(yōu)化。在入基變量有最大增量的同時，一定存在原來的某一基變量減少量的同時，一定存在原來的某一基變量減少為為“0”0”，該變量即為出基變量。切記出基，該變量即為出基變量。切記出基變量

27、的變量的“0”0”運量要用運量要用“空格空格”來表示，而來表示，而不能留有不能留有“0”0”。 在表在表4-304-30中，中， 24min|01ijij ，故選擇，故選擇x24為入基變量。在入基變量為入基變量。在入基變量x24所處的閉合回路上所處的閉合回路上（如表（如表4-33所示），賦予最大的增量所示），賦予最大的增量“1”，相應(yīng)地，相應(yīng)地有有x23最大的增量最大的增量“1”，相應(yīng)地有，相應(yīng)地有x23出基出基, x13=5,x14=2.利用閉合回路法或位勢法計算各空格（非基變量）的利用閉合回路法或位勢法計算各空格（非基變量）的檢驗數(shù)，可得表檢驗數(shù)，可得表4-34（同伏格爾法的初始解表（同伏

28、格爾法的初始解表4-23）。）。 表表4-30甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1 12 = 2437B3 22 = 11 24 = -14C 31 = 106 33 = 1239銷量（銷量（bj）3656表表4-33甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A 11 = 1 12 = 2437B3 22 = 11 24 = -14C 31 = 106 33 = 1239銷量（銷量（bj）3656表表4-34甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A527B314C639銷量（銷量（bj）3656 由于表由于表4-33中的檢驗數(shù)均大于等于零，所以表中的檢驗數(shù)均大于等于零，所以表4-33（同伏格

29、爾法（同伏格爾法所給出的初始解表所給出的初始解表4-23）給出的方案是最優(yōu)方案，這個最優(yōu)方案的）給出的方案是最優(yōu)方案，這個最優(yōu)方案的運費是運費是85個單位。個單位。 23 = 1 31 = 9 22 = 2 11 = 1 12 = 2 33 = 124.34.3運輸問題的拓展運輸問題的拓展 n總產(chǎn)量大于總銷量的運輸問題即為產(chǎn)大于總產(chǎn)量大于總銷量的運輸問題即為產(chǎn)大于銷的運輸問題。銷的運輸問題。n在實際問題中，產(chǎn)大于銷意味著某些產(chǎn)品在實際問題中，產(chǎn)大于銷意味著某些產(chǎn)品被積壓在倉庫中?？梢赃@樣設(shè)想，被積壓在倉庫中?？梢赃@樣設(shè)想，如果把如果把倉庫也看成是一個假想的銷地，并令其銷倉庫也看成是一個假想的銷

30、地，并令其銷量剛好等于總產(chǎn)量與總銷量的差量剛好等于總產(chǎn)量與總銷量的差；那么，；那么，產(chǎn)大于銷的運輸問題就轉(zhuǎn)換成產(chǎn)銷平衡的產(chǎn)大于銷的運輸問題就轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題運輸問題 n假想一個銷地，相當(dāng)于在原產(chǎn)銷關(guān)系表上假想一個銷地，相當(dāng)于在原產(chǎn)銷關(guān)系表上增加一列。增加一列。 4.3.1產(chǎn)大于銷的運輸問題產(chǎn)大于銷的運輸問題 n假想列所對應(yīng)的運價假想列所對應(yīng)的運價|由于假想的銷地代表的是倉庫，而我們由于假想的銷地代表的是倉庫，而我們優(yōu)化的運費是產(chǎn)地與銷地間的運輸費用，優(yōu)化的運費是產(chǎn)地與銷地間的運輸費用，并不包括廠內(nèi)的運輸費用；所以假想列并不包括廠內(nèi)的運輸費用；所以假想列所對應(yīng)的運價都應(yīng)取為所對應(yīng)的運價都

31、應(yīng)取為“0”0”。n至此，我們已經(jīng)將產(chǎn)大于銷的運輸問題至此，我們已經(jīng)將產(chǎn)大于銷的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題，進(jìn)一步的轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題，進(jìn)一步的求解可利用上節(jié)介紹的表上作業(yè)法來完求解可利用上節(jié)介紹的表上作業(yè)法來完成。成。 n 例例4-2 4-2 將表將表4-354-35所示的產(chǎn)大于銷所示的產(chǎn)大于銷的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題題表表4-35甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C7410512銷量（銷量（bj）3656|解解 此運輸問題的總產(chǎn)量為此運輸問題的總產(chǎn)量為2323、總銷量為、總銷量為2020，所以，所以假設(shè)一個銷

32、地戊并令其銷量剛好等于總產(chǎn)量與總銷假設(shè)一個銷地戊并令其銷量剛好等于總產(chǎn)量與總銷量的差量的差“3”3”。取假想的戊列所對應(yīng)的運價都為。取假想的戊列所對應(yīng)的運價都為“0”0”，可得表，可得表4-364-36所示的產(chǎn)銷平衡運輸問題。所示的產(chǎn)銷平衡運輸問題。表表4-36甲甲乙乙丙丙丁丁戊戊產(chǎn)量（產(chǎn)量（ai）A31131007B192804C74105012銷量（銷量（bj）365634.3.2銷大于產(chǎn)的運輸問題銷大于產(chǎn)的運輸問題 n總銷量大于總產(chǎn)量的運輸問題即為銷大于產(chǎn)的運總銷量大于總產(chǎn)量的運輸問題即為銷大于產(chǎn)的運輸問題。輸問題。n可以這樣設(shè)想，可以這樣設(shè)想，假想一個產(chǎn)地，并令其產(chǎn)量剛好假想一個產(chǎn)地，

33、并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差；等于總銷量與總產(chǎn)量的差；那么，銷大于產(chǎn)的運那么，銷大于產(chǎn)的運輸問題同樣可以轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題輸問題同樣可以轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題 n假想的產(chǎn)地并不存在，于是各銷地從假想產(chǎn)地所假想的產(chǎn)地并不存在，于是各銷地從假想產(chǎn)地所得到的運量，實際上所表示的是其未滿足的需求。得到的運量，實際上所表示的是其未滿足的需求。n由于假想的產(chǎn)地與各銷地之間并不存在實際的運由于假想的產(chǎn)地與各銷地之間并不存在實際的運輸，所以假想的產(chǎn)地行所有的運價都應(yīng)該是輸，所以假想的產(chǎn)地行所有的運價都應(yīng)該是“0”0”。n至此，我們又將銷大于產(chǎn)的運輸問題轉(zhuǎn)換成了產(chǎn)至此，我們又將銷大于產(chǎn)的運輸問題

34、轉(zhuǎn)換成了產(chǎn)銷平衡的運輸問題。銷平衡的運輸問題。 例例4-3 4-3 將表將表4-374-37所示的銷大于產(chǎn)所示的銷大于產(chǎn)的運輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸?shù)倪\輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運輸問題問題表表4-37甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059銷量（銷量（bj）11656|解解 此運輸問題的總產(chǎn)量為此運輸問題的總產(chǎn)量為2020、總銷量為、總銷量為2828，所以，所以假設(shè)一個產(chǎn)地假設(shè)一個產(chǎn)地D D并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差的差“8”8”。令假想的。令假想的D D行所對應(yīng)的運價都為行所對應(yīng)的運價都為“0”0”，可得表可得表4

35、-374-37所示的產(chǎn)銷平衡運輸問題所示的產(chǎn)銷平衡運輸問題。表表4-38甲甲乙乙丙丙丁丁產(chǎn)量（產(chǎn)量（ai）A3113107B19284C741059D00008銷量（銷量（bj）116564.3.3運輸問題的應(yīng)用舉例運輸問題的應(yīng)用舉例n 例例4-4 4-4 設(shè)有三個化肥廠供應(yīng)四個地區(qū)的設(shè)有三個化肥廠供應(yīng)四個地區(qū)的化肥需求，假定等量化肥在這些地區(qū)的使化肥需求，假定等量化肥在這些地區(qū)的使用效果相同。各化肥廠年產(chǎn)量、各地區(qū)年用效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化需要量及從各化肥廠到各地區(qū)運送單位化肥的單位運價如表肥的單位運價如表4-394-39所示，試求出總的所示，

36、試求出總的運費最節(jié)省的化肥調(diào)撥方案。運費最節(jié)省的化肥調(diào)撥方案。表表4-39地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量化肥廠化肥廠A1613221750化肥廠化肥廠B1413191560化肥廠化肥廠C192023M50年需要量年需要量/萬萬t最低需求最低需求3070010最高需求最高需求507030不限不限|根據(jù)現(xiàn)有產(chǎn)量，除滿足地區(qū)根據(jù)現(xiàn)有產(chǎn)量，除滿足地區(qū)1 1、地區(qū)、地區(qū)2 2和地區(qū)和地區(qū)3 3的的最低需求外，地區(qū)最低需求外，地區(qū)4 4每年最多能分配到每年最多能分配到6060萬噸，萬噸，這樣其不限的最高需求可等價認(rèn)為是這樣其不限的最高需求可等價認(rèn)為是6060萬噸。萬噸。 160307

37、0060|解解 這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量為為160160萬噸，四個地區(qū)的最低需求為萬噸，四個地區(qū)的最低需求為110110萬噸，最萬噸，最高需求為無限高需求為無限。|按最高需求分析，總需求為按最高需求分析，總需求為210210萬噸，大于總?cè)f噸，大于總產(chǎn)量產(chǎn)量160160萬噸，將此問題定義為銷大于產(chǎn)的運萬噸，將此問題定義為銷大于產(chǎn)的運輸問題。輸問題。|為了求得平衡，在產(chǎn)銷平衡表中增加一個假想為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠的化肥廠D D，令其年產(chǎn)量為，令其年產(chǎn)量為5050萬噸。萬噸。 |各地區(qū)的需要量包含最低和最高兩部分：如地各地區(qū)的

38、需要量包含最低和最高兩部分：如地區(qū)區(qū)1 1，其中，其中3030萬噸是最低需求，故這部分需求萬噸是最低需求，故這部分需求不能由假想的化肥廠不能由假想的化肥廠D D來供給，因此相應(yīng)的運來供給，因此相應(yīng)的運價定義為任意大正數(shù)價定義為任意大正數(shù)M M ；而另一部分；而另一部分2020萬噸滿萬噸滿足與否都是可以的，因此可以由假想化肥廠足與否都是可以的，因此可以由假想化肥廠D D來供給，按前面講的，令相應(yīng)運價為來供給，按前面講的，令相應(yīng)運價為“0”0”。 210 16050|凡是需求分兩種情況的地區(qū)，實際上可按凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)來看待，這樣可以將表照兩個地區(qū)來看待，這樣可以將表

39、4-394-39所示所示的運輸問題轉(zhuǎn)換為表的運輸問題轉(zhuǎn)換為表4-404-40所示的運輸問題。所示的運輸問題。 表表4-40 （單位：萬噸）（單位：萬噸）地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量化肥廠化肥廠A16161322171750化肥廠化肥廠B14141319151560化肥廠化肥廠C19192023MM50化肥廠化肥廠DM0M0M050年需要量年需要量302070301050用表上作業(yè)法計算，可以求得這個問題的最優(yōu)方案用表上作業(yè)法計算，可以求得這個問題的最優(yōu)方案如表如表4-41所示。所示。地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最

40、小元素差兩最小元素差A(yù)161613221717B141413191515C19192023MMDM0MM0兩最小元素差兩最小元素差地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50B60C50D50年需要量年需要量3020703010501903021402153100地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最小元素差兩最小元素差A(yù)161613221717B141413191515C19192023MMDM0M0M兩最小元素差兩最小元素差214021531000地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50

41、B60C50D50年需要量年需要量3020703010503020地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最小元素差兩最小元素差A(yù)1616221717B141413191515C19192023MMDM0M0M兩最小元素差兩最小元素差2202231000地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50B60C50D50年需要量年需要量30207030105030201350地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最小元素差兩最小元素差A(yù)1616221717B1414131915C19192023MMDM0M0M兩最

42、小元素差兩最小元素差557MM31000地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50B60C50D50年需要量年需要量302070301050302013501510地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最小元素差兩最小元素差A(yù)1616221717B14141319C19192023MMDM0M0M兩最小元素差兩最小元素差557MM31000地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50B60C50D50年需要量年需要量3020703010503020135015101530地區(qū)地區(qū)1 地區(qū)地區(qū)1地

43、區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最小元素差兩最小元素差A(yù)1616221717B1419C19192023MMDM0M0M兩最小元素差兩最小元素差557MM30000地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50B60C50D50年需要量年需要量3020703010503020135015101530132014地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)4兩最小元素差兩最小元素差A(yù)1616221717B141419C19192023MMDM0M0M兩最小元素差兩最小元素差557MM31000地區(qū)地區(qū)1 地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)

44、地區(qū)4地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量A50B60C50D50年需要量年需要量3020703010503020135015101530132003020 例例4-6 4-6 在在A1、A2、A3、A4、A5和和A6六個經(jīng)濟(jì)區(qū)六個經(jīng)濟(jì)區(qū)之間有磚、砂子、爐灰、塊石、卵石、木材和之間有磚、砂子、爐灰、塊石、卵石、木材和鋼材七種物資需要運輸。具體的運輸需求如表鋼材七種物資需要運輸。具體的運輸需求如表4-434-43所示，各地點間的路程（公里）見表所示，各地點間的路程（公里）見表4-444-44，試確定一個最優(yōu)的汽車調(diào)度方案。試確定一個最優(yōu)的汽車調(diào)度方案。表表4-43貨物貨物起點起點 終點終點車次車次起點起點終點

45、終點車次車次起點起點 終點終點車次車次磚磚A1A311A1A52A1A66砂子砂子A2A114A2A33A2A63爐灰爐灰A3A19A4A14塊石塊石A3A47A3A65卵石卵石A4A28A4A53木材木材A5A22鋼材鋼材A6A44表表4-44 到到從從A2A3A4A5A6A121191315A22101410A3459A4416A56|汽車的最優(yōu)調(diào)度實質(zhì)上就是空車行駛的汽車的最優(yōu)調(diào)度實質(zhì)上就是空車行駛的公里數(shù)最少。先構(gòu)造如表公里數(shù)最少。先構(gòu)造如表4-454-45所示的各地所示的各地區(qū)汽車出入平衡表，表中區(qū)汽車出入平衡表，表中“十十”號表示該號表示該點產(chǎn)生空車，點產(chǎn)生空車，“”號表示該點需要

46、調(diào)進(jìn)號表示該點需要調(diào)進(jìn)空車。空車。表表4-44A1A2A3A4A5A6出車數(shù)出車數(shù)1920211524來車數(shù)來車數(shù)27101411514平衡數(shù)平衡數(shù)+8-10-7-4+3+10|平衡結(jié)果平衡結(jié)果A A1 1、A A5 5、A A6 6除裝運自己的貨物外，可除裝運自己的貨物外，可多出空車多出空車2121車次；車次；A A2 2、A A3 3、A A4 4缺缺2121車次。按最車次。按最小空駛調(diào)度，可構(gòu)造表小空駛調(diào)度，可構(gòu)造表4-464-46所示的運輸問題所示的運輸問題數(shù)據(jù)表，進(jìn)而可得表數(shù)據(jù)表，進(jìn)而可得表4-474-47所示的最優(yōu)調(diào)度方所示的最優(yōu)調(diào)度方案。案。 表表4-45A2A3A4aiA121

47、198A514543A61091610bj1074表表4-46A2A3A4aiA188A533A627110bj1074作作 業(yè)業(yè)課本課本P P6262：6 6、7 7題題課本課本P P6363：8 8題題2022-5-12第第6262頁習(xí)題頁習(xí)題6.6.已知某廠每月可生產(chǎn)甲產(chǎn)品已知某廠每月可生產(chǎn)甲產(chǎn)品270270噸，先運至噸，先運至A A1 1、A A2 2、A A3 3三個倉庫，然后在分別供應(yīng)三個倉庫，然后在分別供應(yīng)B B1 1、B B2 2、B B3 3、B B4 4、B B5 5五個用戶。已知倉庫容量分別為五個用戶。已知倉庫容量分別為5050、100100、150150噸，各用戶的需要

48、量分別為噸，各用戶的需要量分別為2525、105105、6060、3030、7070噸。已知從該廠經(jīng)各倉庫然后供應(yīng)噸。已知從該廠經(jīng)各倉庫然后供應(yīng)各用戶的運費如下表所示，試確定一個使總運各用戶的運費如下表所示，試確定一個使總運費最少的調(diào)運方案。費最少的調(diào)運方案。|倉庫總?cè)萘浚簜}庫總?cè)萘浚?0+100+150=30050+100+150=300（t t）|各地區(qū)需求：各地區(qū)需求：25+105+60+30+70=29025+105+60+30+70=290（t t）|由于該廠每月最多生產(chǎn)甲產(chǎn)品由于該廠每月最多生產(chǎn)甲產(chǎn)品270t270t，則倉庫有，則倉庫有30t30t不滿，各地區(qū)有不滿，各地區(qū)有20t

49、20t不能滿足需求不能滿足需求|可假設(shè)存在倉庫可假設(shè)存在倉庫A A4 4，它的存儲量為，它的存儲量為20t20t，用戶，用戶B B6 6 的的需求量為需求量為30t30t。這樣就轉(zhuǎn)化為產(chǎn)銷平衡問題。由于。這樣就轉(zhuǎn)化為產(chǎn)銷平衡問題。由于A A4 4 與與B B6 6都是假設(shè)的，不需要運輸，故運價都為都是假設(shè)的，不需要運輸，故運價都為0 0，但是由但是由A A4 4運到運到B B6 6的運輸無法發(fā)生，因兩者皆為假設(shè)的運輸無法發(fā)生，因兩者皆為假設(shè)的，運價為無窮大，設(shè)為的，運價為無窮大，設(shè)為M M。此題屬于產(chǎn)銷不平衡問題此題屬于產(chǎn)銷不平衡問題 2022-5-12第第6262頁習(xí)題頁習(xí)題用伏格爾法求解初

50、始基可行解得：用伏格爾法求解初始基可行解得：B1B2B3B4B5B6產(chǎn)量產(chǎn)量A15050A2254530100A310605030150A42020銷量銷量2510560307030iujv數(shù)字格內(nèi)填入相應(yīng)價格，用位勢法檢驗是否為最優(yōu)解，得：數(shù)字格內(nèi)填入相應(yīng)價格，用位勢法檢驗是否為最優(yōu)解，得：B1B2B3B4B5B6uiA1150A220403025A3354025020A40-5vj-5152055-20用位勢法檢驗是否為最優(yōu)解，得：用位勢法檢驗是否為最優(yōu)解，得：B1B2B3B4B5B6uiA111=151513= 014= 1515=3516=200A2204023=-303025=026

51、=-525A331=15354034=3025020A441= 1042=-1043=-1544=0046=M+25-5vj-5152055-20因檢驗數(shù)存在負(fù)數(shù)，故需用閉合回路法調(diào)整因檢驗數(shù)存在負(fù)數(shù)，故需用閉合回路法調(diào)整 B1B2B3B4B5B6產(chǎn)量產(chǎn)量A111=155013= 014= 1515=3516=2050A2254523=-303025=026=-5100A331=15106034=305030150A441= 1042=-1043=-1544=02046=M+2520銷量銷量2510560307030用閉合回路法調(diào)整得：用閉合回路法調(diào)整得：B1B2B3B4B5B6產(chǎn)量產(chǎn)量A15

52、050A225 6015100A3507030150A4515 20銷量銷量2510560307030用位勢法檢驗得：用位勢法檢驗得：B1B2B3B4B5B6uiA1（5）15(20)(5)(35)(20)0A220（10）1530(10)(5)15A3(5)35（20）(20)25020A4(10)0(15)0 (10)(M+35)-15vj5150155-20因檢驗數(shù)全為正，所以已得最優(yōu)方案。因檢驗數(shù)全為正，所以已得最優(yōu)方案。即即A A3 3差差30t30t沒有得到滿足，沒有得到滿足， B B2 2缺缺5t5t，B B4 4缺缺15t15t。7 7、已知某運輸問題的單位運價及最優(yōu)調(diào)運方、已

53、知某運輸問題的單位運價及最優(yōu)調(diào)運方案如表所示（括號中的數(shù)據(jù)代表運輸數(shù)量），案如表所示（括號中的數(shù)據(jù)代表運輸數(shù)量），由于產(chǎn)地由于產(chǎn)地A A2 2至銷地至銷地B B2 2的道路關(guān)閉，故最優(yōu)調(diào)運的道路關(guān)閉，故最優(yōu)調(diào)運方案將發(fā)生變化，試在原最優(yōu)調(diào)運方案的基礎(chǔ)方案將發(fā)生變化，試在原最優(yōu)調(diào)運方案的基礎(chǔ)上，尋找新的最優(yōu)調(diào)運方案。上，尋找新的最優(yōu)調(diào)運方案。表表4-504-50B1B2B3B4B5aiA110205（4） 9（5）109A2210（4）103064A31（3） 20（1）710（1）4（3）8bj35463解：由于解：由于A A2 2 到到B B2 2道路關(guān)閉，則其運價為道路關(guān)閉，則其運價為M

54、M，應(yīng)，應(yīng)令其出基，以實現(xiàn)最優(yōu)調(diào)度。先將令其出基，以實現(xiàn)最優(yōu)調(diào)度。先將M M反映進(jìn)產(chǎn)反映進(jìn)產(chǎn)銷平衡表，然后用位勢法作檢驗，有：銷平衡表，然后用位勢法作檢驗，有：iujvB1B2B3B4B5A1（10）（1）59(7)0A2（21-M）M (24-M) （40-M） (22-M)M-19 A3120（1）1041019593要令要令A(yù)2 B2出基，即令其運輸量為出基，即令其運輸量為0，找出負(fù)檢驗數(shù)最小的來，找出負(fù)檢驗數(shù)最小的來進(jìn)行調(diào)整，得：進(jìn)行調(diào)整，得：B1B2B3B4B5產(chǎn)量產(chǎn)量A1459A2314A35128銷量銷量35463iujv用位勢法作檢驗，有：用位勢法作檢驗，有：B1B2B3B4B

55、5A1（11）（1）59(7)0A22（M-22） (2)（18）63 A3（1）20（1）1041-119593檢驗數(shù)已全為非負(fù)，故已得最優(yōu)調(diào)度方案。檢驗數(shù)已全為非負(fù)，故已得最優(yōu)調(diào)度方案。8 8、已知某運輸問題的單位運價及最優(yōu)調(diào)運方已知某運輸問題的單位運價及最優(yōu)調(diào)運方案如表案如表4 4所示，試回答下述問題：所示，試回答下述問題：(1)(1)A A1 1到到B B2 2、A A3 3到到B B5 5、和、和A A4 4到到B B1 1的單位運價，的單位運價，分別在什么范圍內(nèi)變化時上表中給出的最分別在什么范圍內(nèi)變化時上表中給出的最優(yōu)方案不變；優(yōu)方案不變；(2)(2)若若A A1 1到到B B2

56、2的單位運價由的單位運價由1 1變?yōu)樽優(yōu)? 3，最優(yōu)方案，最優(yōu)方案將發(fā)生怎樣的變化；將發(fā)生怎樣的變化；(3)(3)若若A A3 3到到B B5 5的單位運價由的單位運價由4 4變?yōu)樽優(yōu)? 2，最優(yōu)方案，最優(yōu)方案將發(fā)生怎樣的變化；將發(fā)生怎樣的變化；2022-5-12表表4-51B1B2B3B4B5B6aiA12（20）1（30）333550A242（20）2（20）44440A33（10）542（39）41（11） 60A44221（1）2（30）231bj305020403011解：（解：（1 1）設(shè)）設(shè)A A1 1 到到B B2 2的單位運價為的單位運價為c c1212，因，因A A1 1

57、到到B B2 2是是基變量，它的運價變化會引起非基變量檢驗系數(shù)的基變量，它的運價變化會引起非基變量檢驗系數(shù)的變化，此時，只需對其再進(jìn)行位勢法分析即可。變化，此時，只需對其再進(jìn)行位勢法分析即可。|要令最優(yōu)方案不變，則非基變量的檢驗數(shù)非負(fù)；要令最優(yōu)方案不變，則非基變量的檢驗數(shù)非負(fù)；故有故有c12 00；3- 3- c12 0 0；4- 4- c12 00；2- 2- c12 0 0；2+ 2+ c1200；1+ 1+ c12 0 0解上述不等式得解上述不等式得0 0 c12 22。即。即A A1 到到B B2的單位的單位運價在運價在00，22內(nèi)變化時，最有方案不變。內(nèi)變化時，最有方案不變。iujv

58、B1B2B3B4B5B6A12c12(3- c12)(2)(1)(5)0A2（ c12 ）22（20）(1+ c12)(2+ c12)2- c12A33（4- c12 ） （3- c12 ）2（1）11A4(c12)(2- c12)(1)1 2(2)02 c12c12120(1)| A A3 3 到到B B5 5的單位運價屬于非基變量，它的變的單位運價屬于非基變量，它的變化不會引起其它檢驗數(shù)變化，故只需保證其化不會引起其它檢驗數(shù)變化，故只需保證其檢驗數(shù)非負(fù)即可。檢驗數(shù)非負(fù)即可。 先用位勢法算出原方案的檢驗數(shù)：先用位勢法算出原方案的檢驗數(shù)：B1B2B3B4B5B6uiA121(2)(2)(1)(5)0A2（1）22（3）(1)(3)1A33（3） （2）2（1）