第7章運(yùn)輸問題表上作業(yè)法

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

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

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

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

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

6、最小的運(yùn)價(jià)開始確定產(chǎn)從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(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中再找出最小運(yùn)價(jià)中再找出最小運(yùn)價(jià)“3”3”，這樣一步步地進(jìn)行下去，直到單位運(yùn)價(jià)表上這樣一步步地進(jìn)行下去，直到單位運(yùn)價(jià)表上的所有元素均被劃去為止。的所有元素均被劃去為止。 表表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)銷平衡表上得到一個(gè)調(diào)運(yùn)方案，見最后在產(chǎn)銷平衡表上得到一個(gè)調(diào)運(yùn)方案，見表表4-64-6。這一方案的總運(yùn)費(fèi)為。這一方案的總運(yùn)費(fèi)為8686個(gè)單位。個(gè)單位。|最小元素法各步在運(yùn)價(jià)表中劃掉的行或列是需求得最小元素法各步在運(yùn)價(jià)表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個(gè)數(shù)相應(yīng)地劃掉一行或一列，這樣最終將得到入一個(gè)數(shù)相應(yīng)地劃掉一行或一列，這

9、樣最終將得到一個(gè)具有一個(gè)具有m+n-1m+n-1個(gè)數(shù)字格（基變量）的初始基可行解。個(gè)數(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），就會(huì)出現(xiàn)上述特殊情況。），就會(huì)出現(xiàn)上述特殊情況。 0 06 66 68.8.伏格法爾法伏格法爾法伏格爾法的基

10、本步驟：伏格爾法的基本步驟：8.8.伏格爾法伏格爾法1.1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；2.2.找出最大差所在的行或列；找出最大差所在的行或列；3.3.找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)的供應(yīng) ；4.4.劃掉已滿足要求的行或劃掉已滿足要求的行或 ( (和和) ) 列，如果需要同時(shí)劃列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)去行和列，必須要在該行或列的任意位置填個(gè)“0”“0”；5.5.在剩余的運(yùn)價(jià)表中重復(fù)在剩余的運(yùn)價(jià)表中重復(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|總運(yùn)費(fèi)為總運(yùn)費(fèi)為85|由以上可見，伏格爾法同最小元素法除在確由以上可見，伏格爾法

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

14、而位勢(shì)法直接，并為方案調(diào)整指明了方向；而位勢(shì)法具有批處理的功能，提高了計(jì)算效率。具有批處理的功能，提高了計(jì)算效率。|所謂所謂閉合回路閉合回路是是在已給出的調(diào)運(yùn)方案的運(yùn)輸在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水表上從一個(gè)代表非基變量的空格出發(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ā)的那個(gè)空格，由此形成的封閉直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉合回路。一

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

16、基變量的檢驗(yàn)數(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ā)尋找閉合回路，如對(duì)給定的初始方案的任一空格出發(fā)尋找閉合回路，如對(duì)于空格（于空格（A A，甲）

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

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

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

20、算過程，表檢驗(yàn)數(shù)的計(jì)算過程，表4-304-30給出了最終給出了最終結(jié)果?？梢宰C明，對(duì)初始方案中的每一結(jié)果?？梢宰C明，對(duì)初始方案中的每一個(gè)空格來說個(gè)空格來說“閉合回路存在且唯一閉合回路存在且唯一”。表表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|如果檢驗(yàn)數(shù)表中所有數(shù)字均大于等于零，如果檢驗(yàn)數(shù)表中所有數(shù)字均大于等于零，這表明對(duì)調(diào)運(yùn)方案做出任何改變都將導(dǎo)這表明對(duì)調(diào)運(yùn)方案做出任何改變都將導(dǎo)致運(yùn)費(fèi)的增加，即給定的方案是最優(yōu)方致運(yùn)費(fèi)的增加，即給定的方案是最優(yōu)方案。在表案。在表4-304-30中，中， 2424 = -1, = -1,說明方案說明方案需要進(jìn)一步改進(jìn)。需要進(jìn)一步改進(jìn)。 2.2.位勢(shì)法位勢(shì)法)(jiijijvucn這一表達(dá)式完全可以通過先前所述的閉合這一表達(dá)式完全可以通過先前所述的閉合回路法得到。在某一的閉合回路上（如下表回路法得到。在某一的閉合回路上（如下表所示），由

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

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

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

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

27、基變量的變量的“0”0”運(yùn)量要用運(yùn)量要用“空格空格”來表示，而來表示，而不能留有不能留有“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ì)法計(jì)算各空格（非基變量）的利用閉合回路法或位勢(shì)法計(jì)算各空格（非基變量）的檢驗(yàn)數(shù)，可得表檢驗(yàn)數(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中的檢驗(yàn)數(shù)均大于等于零，所以表中的檢驗(yàn)數(shù)均大于等于零，所以表4-33（

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

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

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

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

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

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

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

36、所示，試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。表表4-39地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4年產(chǎn)量年產(chǎn)量化肥廠化肥廠A1613221750化肥廠化肥廠B1413191560化肥廠化肥廠C192023M50年需要量年需要量/萬(wàn)萬(wàn)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萬(wàn)噸，萬(wàn)噸，這樣其不限的最高需求可等價(jià)認(rèn)為是這樣其不限的最高需求可等價(jià)認(rèn)為是6060萬(wàn)噸。萬(wàn)噸。 160

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

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

39、以將表4-394-39所示所示的運(yùn)輸問題轉(zhuǎn)換為表的運(yùn)輸問題轉(zhuǎn)換為表4-404-40所示的運(yùn)輸問題。所示的運(yùn)輸問題。 表表4-40 （單位：萬(wàn)噸）（單位：萬(wàn)噸）地區(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è)法計(jì)算，可以求得這個(gè)問題的最優(yōu)方案用表上作業(yè)法計(jì)算，可以求得這個(gè)問題的最優(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)量A

41、50B60C50D50年需要量年需要量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ū)

43、1地區(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

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

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

46、需要調(diào)進(jìn)號(hào)表示該點(diǎ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除裝運(yùn)自己的貨物外，可除裝運(yùn)自己的貨物外，可多出空車多出空車2121車次；車次；A A2 2、A A3 3、A A4 4缺缺2121車次。按最車次。按最小空駛調(diào)度，可構(gòu)造表小空駛調(diào)度，可構(gòu)造表4-464-46所示的運(yùn)輸問題所示的運(yùn)輸問題數(shù)據(jù)表，進(jìn)而可得表數(shù)據(jù)表，進(jìn)而可得表4-474-47所示的最優(yōu)調(diào)度方所示的最優(yōu)調(diào)度方案。案。 表表4-45A2A3A4aiA1

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

48、用戶的需要量分別為2525、105105、6060、3030、7070噸。已知從該廠經(jīng)各倉(cāng)庫(kù)然后供應(yīng)噸。已知從該廠經(jīng)各倉(cāng)庫(kù)然后供應(yīng)各用戶的運(yùn)費(fèi)如下表所示，試確定一個(gè)使總運(yùn)各用戶的運(yùn)費(fèi)如下表所示，試確定一個(gè)使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。費(fèi)最少的調(diào)運(yùn)方案。|倉(cāng)庫(kù)總?cè)萘浚簜}(cāng)庫(kù)總?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，則倉(cāng)庫(kù)有，則倉(cāng)庫(kù)有30t30t不滿，各地區(qū)有不滿，各地區(qū)有20t20t不能滿足

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

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

51、34=3025020A441= 1042=-1043=-1544=0046=M+25-5vj-5152055-20因檢驗(yàn)數(shù)存在負(fù)數(shù)，故需用閉合回路法調(diào)整因檢驗(yàn)數(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)量A15050A225 6015100A

52、3507030150A4515 20銷量銷量2510560307030用位勢(shì)法檢驗(yàn)得：用位勢(shì)法檢驗(yàn)得：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因檢驗(yàn)數(shù)全為正，所以已得最優(yōu)方案。因檢驗(yàn)數(shù)全為正，所以已得最優(yōu)方案。即即A A3 3差差30t30t沒有得到滿足，沒有得到滿足， B B2 2缺缺5t5t，B B4 4缺缺15t15t。7 7、已知某運(yùn)輸問題的單位運(yùn)價(jià)及最優(yōu)調(diào)運(yùn)方、已知某運(yùn)輸問題的單位運(yùn)價(jià)及最優(yōu)調(diào)運(yùn)

53、方案如表所示（括號(hào)中的數(shù)據(jù)代表運(yùn)輸數(shù)量），案如表所示（括號(hào)中的數(shù)據(jù)代表運(yùn)輸數(shù)量），由于產(chǎn)地由于產(chǎn)地A A2 2至銷地至銷地B B2 2的道路關(guān)閉，故最優(yōu)調(diào)運(yùn)的道路關(guān)閉，故最優(yōu)調(diào)運(yùn)方案將發(fā)生變化，試在原最優(yōu)調(diào)運(yùn)方案的基礎(chǔ)方案將發(fā)生變化，試在原最優(yōu)調(diào)運(yùn)方案的基礎(chǔ)上，尋找新的最優(yōu)調(diào)運(yùn)方案。上，尋找新的最優(yōu)調(diào)運(yùn)方案。表表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)閉，則其運(yùn)價(jià)為道路關(guān)閉，則其運(yùn)價(jià)為M M，應(yīng)，應(yīng)令其出基，以實(shí)現(xiàn)最優(yōu)調(diào)

54、度。先將令其出基，以實(shí)現(xiàn)最優(yōu)調(diào)度。先將M M反映進(jìn)產(chǎn)反映進(jìn)產(chǎn)銷平衡表，然后用位勢(shì)法作檢驗(yàn)，有：銷平衡表，然后用位勢(shì)法作檢驗(yà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出基，即令其運(yùn)輸量為出基，即令其運(yùn)輸量為0，找出負(fù)檢驗(yàn)數(shù)最小的來，找出負(fù)檢驗(yàn)數(shù)最小的來進(jìn)行調(diào)整，得：進(jìn)行調(diào)整，得：B1B2B3B4B5產(chǎn)量產(chǎn)量A1459A2314A35128銷量銷量35463iujv用位勢(shì)法作檢驗(yàn)，有：用位勢(shì)法作檢驗(yàn)，有：B1B2B3B4B5A1（11）（1）59(7)0

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

56、變?yōu)樽優(yōu)? 3，最優(yōu)方案，最優(yōu)方案將發(fā)生怎樣的變化；將發(fā)生怎樣的變化；(3)(3)若若A A3 3到到B B5 5的單位運(yùn)價(jià)由的單位運(yùn)價(jià)由4 4變?yōu)樽優(yōu)? 2，最優(yōu)方案，最優(yōu)方案將發(fā)生怎樣的變化；將發(fā)生怎樣的變化；表表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的單位運(yùn)價(jià)為的單位運(yùn)價(jià)為c c1212，因，因A A1 1 到到B B2 2是是基變量，它的運(yùn)價(jià)變化會(huì)引起非基

57、變量檢驗(yàn)系數(shù)的基變量，它的運(yùn)價(jià)變化會(huì)引起非基變量檢驗(yàn)系數(shù)的變化，此時(shí)，只需對(duì)其再進(jìn)行位勢(shì)法分析即可。變化，此時(shí)，只需對(duì)其再進(jìn)行位勢(shì)法分析即可。|要令最優(yōu)方案不變，則非基變量的檢驗(yàn)數(shù)非負(fù)；要令最優(yōu)方案不變，則非基變量的檢驗(yàn)數(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的單位的單位運(yùn)價(jià)在運(yùn)價(jià)在00，22內(nèi)變化時(shí)，最有方案不變。內(nèi)變化時(shí)，最有方案不變。iujvB1B2B3B4B5B6A12c12(3- c12

58、)(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的單位運(yùn)價(jià)屬于非基變量，它的變的單位運(yùn)價(jià)屬于非基變量，它的變化不會(huì)引起其它檢驗(yàn)數(shù)變化，故只需保證其化不會(huì)引起其它檢驗(yàn)數(shù)變化，故只需保證其檢驗(yàn)數(shù)非負(fù)即可。檢驗(yàn)數(shù)非負(fù)即可。 先用位勢(shì)法算出原方案的檢驗(yàn)數(shù)：先用位勢(shì)法算出原方案的檢驗(yàn)數(shù)：B1B2B3B4B5B6uiA121(2)(2)(1)(5)0A2（1）22（3）(1)(3)1A33（3） （2）2（1）11A4(2