運(yùn)籌學(xué)：運(yùn)輸問題.docx

運(yùn)輸問題運(yùn)輸問題（transportation problem）一般是研究把某種商品從若干個(gè)產(chǎn)地運(yùn)至若干個(gè)銷地而使總運(yùn)費(fèi)最小的一 類問題。然而從更廣義上講，運(yùn)輸問題是具有一定模型特征的線性規(guī)劃問題。它不僅可以用來求解商品的調(diào)運(yùn)問題，還可以解決諸多非商品調(diào)運(yùn)問題。運(yùn)輸問題是一種特殊的線性規(guī)劃問題，由于其技術(shù)系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就有可能找到比一般單純形法更簡便高效的求解方法，這正是單獨(dú)研究運(yùn)輸問題的目的所在。1運(yùn)輸問題的數(shù)學(xué)模型例4-1 某公司經(jīng)營某種產(chǎn)品，該公司下設(shè)A、B、C三個(gè)生產(chǎn)廠，甲、乙、丙、丁四個(gè)銷售點(diǎn)。公司每天把三個(gè)工廠生產(chǎn)的產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)，由于各工廠到各銷售點(diǎn)的路程不同，所以單位產(chǎn)品的運(yùn)費(fèi)也就不同案。各工廠每日的產(chǎn)量、各銷售點(diǎn)每日的銷量，以及從各工廠到各銷售點(diǎn)單位產(chǎn)品的運(yùn)價(jià)如表4-1所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)需要的前提下，使總運(yùn)費(fèi)最小。表4-1甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059銷量（bj）3656設(shè)代表從第個(gè)產(chǎn)地到第個(gè)銷地的運(yùn)輸量（；），用代表從第個(gè)產(chǎn)地到第個(gè)銷地的運(yùn)價(jià)，于是可構(gòu)造如下數(shù)學(xué)模型： （；運(yùn)出的商品總量等于其產(chǎn)量） （；運(yùn)來的商品總量等于其銷量）通過該引例的數(shù)學(xué)模型，我們可以得出運(yùn)輸問題是一種特殊的線性規(guī)劃問題的結(jié)論，其特殊性就在于技術(shù)系數(shù)矩陣是由“1”和“0”兩個(gè)元素構(gòu)成的。將該引例的數(shù)學(xué)模型做一般性推廣，即可得到有個(gè)產(chǎn)地、個(gè)銷地的運(yùn)輸問題的一般模型。注意：在此僅限于探討總產(chǎn)量等于總銷量的產(chǎn)銷平衡運(yùn)輸問題，而產(chǎn)銷不平衡運(yùn)輸問題將在本章的后續(xù)內(nèi)容中探討。（；運(yùn)出的商品總量等于其產(chǎn)量）（；運(yùn)來的商品總量等于其銷量）供應(yīng)約束確保從任何一個(gè)產(chǎn)地運(yùn)出的商品等于其產(chǎn)量，需求約束保證運(yùn)至任何一個(gè)銷地的商品等于其需求。除非負(fù)約束外，運(yùn)輸問題約束條件的個(gè)數(shù)是產(chǎn)地與銷地的數(shù)量和，即；而決策變量個(gè)數(shù)是二者的積，即。由于在這個(gè)約束條件中，隱含著一個(gè)總產(chǎn)量等于總銷量的關(guān)系式，所以相互獨(dú)立的約束條件的個(gè)數(shù)是個(gè)。2運(yùn)輸問題的求解運(yùn)輸問題的求解采用表上作業(yè)法，該方法是單純形法求解運(yùn)輸問題的一種特定形式，其實(shí)質(zhì)是單純形法。既然表上作業(yè)法是一種特定形式的單純形法，它自然與單純形法有著完全相同的解題步驟，所不同的只是完成各步采用的具體形式。表上作業(yè)法的基本步驟可參照單純形法歸納如下：1 找出初始基可行解：即要在階產(chǎn)銷平衡表上給出“”個(gè)數(shù)字格（基變量）；2 求各非基變量（空格）的檢驗(yàn)數(shù)，判斷當(dāng)前的基可行解是否是最優(yōu)解，如已得到最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步；3 確定入基變量，若，那么選取為入基變量；4 確定出基變量，找出入基變量的閉合回路，在閉合回路上最大限度地增加入基變量的值，那么閉合回路上首先減少為“0”的基變量即為出基變量；5 在表上用閉合回路法調(diào)整運(yùn)輸方案；6 重復(fù)2、3、4、5步驟，直到得到最優(yōu)解。2.1確定初始基可行解與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運(yùn)輸問題一定具有可行解（同時(shí)也一定存在最優(yōu)解），這一點(diǎn)是顯然的。確定初始基可行解的方法有很多，在此介紹比較簡單但能給出較好初始方案的最小元素法（the least cost rule）和伏格爾法（Vogels approximation method）。1 最小元素法最小元素法的基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方案為止。下面就用例4-1說明最小元素法的應(yīng)用。第一步：從表4-1中找出最小運(yùn)價(jià)“1”，這表示先將B生產(chǎn)的產(chǎn)品供應(yīng)給甲。由于B每天生產(chǎn)4個(gè)單位產(chǎn)品，甲每天需求3個(gè)單位產(chǎn)品，即B每天生產(chǎn)的產(chǎn)品除滿足甲的全部需求外，還可多余1個(gè)單位產(chǎn)品。在（B，甲）的交叉格處填上“3”，形成表4-2；將運(yùn)價(jià)表的甲列運(yùn)價(jià)劃去得表4-3，劃去甲列表明甲的需求已經(jīng)得到滿足。表4-2甲乙丙丁產(chǎn)量（ai）A7B34C9銷量（bj）3656表4-3甲乙丙丁A311310B1928C74105第二步：在表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-4甲乙丙丁產(chǎn)量（ai）A7B314C9銷量（bj）3656第三步：在表4-5中再找出最小運(yùn)價(jià)“3”，這樣一步步地進(jìn)行下去，直到單位運(yùn)價(jià)表上的所有元素均被劃去為止。最后在產(chǎn)銷平衡表上得到一個(gè)調(diào)運(yùn)方案，見表4-6。這一方案的總運(yùn)費(fèi)為86個(gè)單位。表4-5甲乙丙丁A311310B1928C74105表4-6甲乙丙丁產(chǎn)量（ai）A437B314C639銷量（bj）3656最小元素法各步在運(yùn)價(jià)表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個(gè)數(shù)相應(yīng)地劃掉一行或一列，這樣最終將得到一個(gè)具有“”個(gè)數(shù)字格（基變量）的初始基可行解。然而，問題并非總是如此，有時(shí)也會出現(xiàn)這樣的情況：在供需關(guān)系格（）處填入一數(shù)字，剛好使第個(gè)產(chǎn)地的產(chǎn)品調(diào)空，同時(shí)也使第個(gè)銷地的需求得到滿足。按照前述的處理方法，此時(shí)需要在運(yùn)價(jià)表上相應(yīng)地劃去第行和第列。填入一數(shù)字同時(shí)劃去了一行和一列，如果不加入任何補(bǔ)救措施的話，那么最終必然無法得到一個(gè)具有“”個(gè)數(shù)字格（基變量）的初始基可行解。為了使在產(chǎn)銷平衡表上有“”個(gè)數(shù)字格，這時(shí)需要在第行或第列此前未被劃掉的任意一個(gè)空格上填一個(gè)“0”。填“0”格雖然所反映的運(yùn)輸量同空格沒有什么不同；但它所對應(yīng)的變量卻是基變量，而空格所對應(yīng)的變量是非基變量。表4-7甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656將例4-1的各工廠的產(chǎn)量做適當(dāng)調(diào)整（調(diào)整結(jié)果見表4-7），就會出現(xiàn)此類特殊情況。第一步在（B，甲）處填入“3”，劃去甲列運(yùn)價(jià)；第二步在（B，丙）處填入“1”，劃去B行運(yùn)價(jià)，此二步的結(jié)果見表4-8和表4-9。表4-8甲乙丙丁產(chǎn)量（ai）A4B314C12銷量（bj）3656表4-9甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656表4-10甲乙丙丁產(chǎn)量（ai）A044B314C12銷量（bj）3656表4-11甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656表4-9中剩下的最小元素為“3”，其對應(yīng)產(chǎn)地A的產(chǎn)量是4，銷地丙的剩余需要量也是4，在格（A，丙）中填入“4”，需同時(shí)劃去A行和丙列。在填入“4”之前A行和丙列中除了（A，丙）之外，還有（A，乙）、（A，?。┖停–，丙）三個(gè)空格未被劃去；因此，可以在（A，乙）、（A，?。┖停–，丙）任選一格填加一個(gè)“0”，不妨選擇（A，乙），結(jié)果可見表4-10和表4-11。注意這個(gè)“0”是不能填入（A，甲）或（B，丙）的，因?yàn)樵谔钊搿?”之前它們已經(jīng)被劃去了（見表4-9）。2 伏格爾法最小元素法的缺點(diǎn)是只考慮了就近的問題卻沒有考慮就近所付出的機(jī)會成本。伏格爾法通過計(jì)算每一行、每一列在沒有選擇最小元素（選擇次小元素）時(shí)的費(fèi)用增加，可給出最優(yōu)或近似最優(yōu)的方案，因此它是一種十分有效的方法。伏格爾法把費(fèi)用增量定義為給定行或列次小元素與最小元素的差（如果存在兩個(gè)或兩個(gè)以上的最小元素費(fèi)用增量定義為零）。最大差對應(yīng)的行或列中的最小元素確定了產(chǎn)品的供應(yīng)關(guān)系，即優(yōu)先避免最大的費(fèi)用增量發(fā)生。當(dāng)產(chǎn)地或銷地中的一方在數(shù)量上供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對應(yīng)的行或列，再重復(fù)上述步驟，即可得到一個(gè)初始的基可行解。仍以例4-1來說明伏格爾法。第一步：在表4-1中找出每行、每列兩個(gè)最小元素的差額，并填入該表的最右列和最下行，見表4-12。表4-12甲乙丙丁兩最小元素之差A(yù)3113100B19281C741051兩最小元素之差2513第二步：從行和列的差額中選出最大者，選擇它所在的行或列中的最小元素的位置確定供應(yīng)關(guān)系。在表4-12中乙列是最大差額“5”所在的列，乙列中的最小元素是“4”，從而確定了C與乙間的供應(yīng)關(guān)系，表4-13即反應(yīng)了這一供應(yīng)關(guān)系。同最小元素法一樣，由于乙的需求已得到了滿足，將運(yùn)價(jià)表中的乙列劃去。第三步：對運(yùn)價(jià)表中未劃去的元素再分別計(jì)算出各行、各列兩個(gè)最小運(yùn)費(fèi)的差，并填入該表的最右列和最下行，見表4-14。重復(fù)第一、第二兩步，直到給出一個(gè)初始基可行解，處理過程見表4-15表4-23。表4-13甲乙丙丁產(chǎn)量（ai）A7B4C69銷量（bj）3656表4-14甲乙丙丁兩最小元素之差A(yù)3113100B19281C741052兩最小元素之差213表4-15甲乙丙丁產(chǎn)量（ai）A7B4C639銷量（bj）3656在表4-16中兩個(gè)最小元素的最大差是“2”，但最大差“2”并不唯一，在此應(yīng)按最大差所對應(yīng)的最小元素最小的原則確定供應(yīng)關(guān)系，即選擇B生產(chǎn)的產(chǎn)品運(yùn)輸給甲。表4-16甲乙丙丁兩最小元素之差A(yù)3113100B19281C74105兩最小元素之差212表4-17甲乙丙丁產(chǎn)量（ai）A7B34C639銷量（bj）36564-18甲乙丙丁兩最小元素之差A(yù)3113107B19286C74105兩最小元素之差12表4-19甲乙丙丁產(chǎn)量（ai）A57B34C639銷量（bj）36564-20甲乙丙丁兩最小元素之差A(yù)311310B1928C74105兩最小元素之差2表4-21甲乙丙丁產(chǎn)量（ai）A57B314C639銷量（bj）3656表4-22甲乙丙丁兩最小元素之差A(yù)311310B1928C74105兩最小元素之差表4-23甲乙丙丁產(chǎn)量（ai）A527B314C639銷量（bj）3656由以上可見，伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟是完全相同的。伏格爾法給出的初始解比最小元素法給出的初始解一般來講會更接近于最優(yōu)解。2.2基可行解的最優(yōu)性檢驗(yàn)對初始基可行解的最優(yōu)性檢驗(yàn)有閉合回路法和位勢法兩種基本方法。閉合回路法具體、直接，并為方案調(diào)整指明了方向；而位勢法具有批處理的功能，提高了計(jì)算效率。1 閉合回路法判斷基可行解的最優(yōu)性，需計(jì)算空格（非基變量）的檢驗(yàn)數(shù)。閉合回路法即通過閉合回路求空格檢驗(yàn)數(shù)的方法。下面就以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論閉合回路法。表4-24甲乙丙丁產(chǎn)量（ai）A（+3）4（-3）37B3（-1）1（+2）4C639銷量（bj）3656從表4-6給定的初始方案的任一空格出發(fā)尋找閉合回路，如對于空格（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)所在格括號內(nèi)的數(shù)字是相應(yīng)的單位運(yùn)價(jià)，單位運(yùn)價(jià)前的“+”、“-”號表示運(yùn)量的調(diào)整方向。對應(yīng)這樣的方案調(diào)整，運(yùn)費(fèi)會有什么變化呢？可以看出（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ù)，即。仿照此步驟可以計(jì)算初始方案中所有空格的檢驗(yàn)數(shù)，表4-25表4-30展示了各檢驗(yàn)數(shù)的計(jì)算過程，表4-30給出了最終結(jié)果?？梢宰C明，對初始方案中的每一個(gè)空格來說“閉合回路存在且唯一”。表4-25甲乙丙丁產(chǎn)量（ai）As11 = 1（+11）43（-10）7B314C6（-4）3（+5）9銷量（bj）3656表4-26甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 24（+3）3（-10）7B3（+9）1（-2）4C6（-4）3（+5）9銷量（bj）3656表4-27甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 24（+3）3（-10）7B3s22 = 11（-2）（+8）4C639銷量（bj）3656表4-28甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 24（-3）3（+10）7B3s22 = 11s24 = -14C6（+10）3（-5）9銷量（bj）3656表4-29甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 24（-3）3（+10）7B3（-1）s22 = 11（+2）s24 = -14C（+7）6s33 = 123（-5）9銷量（bj）3656表4-30甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 2437B3s22 = 11s24 = -14Cs31 = 106s33 = 1239銷量（bj）3656如果檢驗(yàn)數(shù)表中所有數(shù)字均大于等于零，這表明對調(diào)運(yùn)方案做出任何改變都將導(dǎo)致運(yùn)費(fèi)的增加，即給定的方案是最優(yōu)方案。在表4-30中，說明方案需要進(jìn)一步改進(jìn)。2 位勢法對于特定的調(diào)運(yùn)方案的每一行給出一個(gè)因子（稱為行位勢），每一列給出一個(gè)因子（稱為列位勢），使對于目前解的每一個(gè)基變量有，這里的和可正、可負(fù)也可以為零。那么任一非基變量的檢驗(yàn)數(shù)就是這一表達(dá)式完全可以通過先前所述的閉合回路法得到。在某一的閉合回路上（如下表所示），由于基變量的運(yùn)價(jià)等于其所對應(yīng)的行位勢與列位勢之和，即：， ， 非基變量（+cij）（-cik）基變量基變量（-clj）（+clk）基變量于是所以對于一個(gè)具有個(gè)產(chǎn)地、個(gè)銷地的運(yùn)輸問題，應(yīng)具有個(gè)行位勢、個(gè)列位勢，即具有“”個(gè)位勢。運(yùn)輸問題基變量的個(gè)數(shù)只有“”個(gè)，所以利用基變量所對應(yīng)的“”個(gè)方程，求出“”個(gè)位勢，進(jìn)而計(jì)算各非基變量的檢驗(yàn)數(shù)是不現(xiàn)實(shí)的。通?？梢酝ㄟ^在這些方程中對任意一個(gè)因子假定一個(gè)任意的值（如等等），再求解其余的“”個(gè)未知因子，這樣就可求得所有空格（非基變量）的檢驗(yàn)數(shù)。仍以表4-6中給出的初始基可行解（最小元素法所給出的初始方案）為例，討論位勢法求解非基變量檢驗(yàn)數(shù)的過程。第一步：把方案表中基變量格填入其相應(yīng)的運(yùn)價(jià)并令；讓每一個(gè)基變量都有，可求得所有的位勢，如表4-31所示。表4-31甲乙丙丁A3100B12-1C45-529310第二步：利用計(jì)算各非基變量的檢驗(yàn)數(shù)，結(jié)果見表4-30。2.3方案的優(yōu)化在負(fù)檢驗(yàn)數(shù)中找出最小的檢驗(yàn)數(shù)，該檢驗(yàn)數(shù)所對應(yīng)的變量即為入基變量。在入基變量所處的閉合回路上，賦予入基變量最大的增量，即可完成方案的優(yōu)化。在入基變量有最大增量的同時(shí)，一定存在原來的某一基變量減少為“0”，該變量即為出基變量。切記出基變量的“0”運(yùn)量要用“空格”來表示，而不能留有“0”。在表4-30中，故選擇為入基變量。在入基變量所處的閉合回路上（如表4-32所示），賦予最大的增量“1”，相應(yīng)地有出基、。利用閉合回路法或位勢法計(jì)算各空格（非基變量）的檢驗(yàn)數(shù)，可得表4-33（同伏格爾法的初始解表4-23）。表4-32甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 2437B3s22 = 11s24 = -14Cs31 = 106s33 = 1239銷量（bj）3656表4-33甲乙丙丁產(chǎn)量（ai）As11 = 1s12 = 2527B3s22 = 2s23 = 114Cs31 = 96s33 = 1239銷量（bj）3656由于表4-33中的檢驗(yàn)數(shù)均大于等于零，所以表4-33（同伏格爾法所給出的初始解表4-23）給出的方案是最優(yōu)方案，這個(gè)最優(yōu)方案的運(yùn)費(fèi)是85個(gè)單位。3運(yùn)輸問題的拓展運(yùn)輸問題是符合一類數(shù)學(xué)模型問題的集合，它不僅可以解決產(chǎn)品運(yùn)輸問題，也可以解決符合這類模型特征的非產(chǎn)品運(yùn)輸問題；此外，運(yùn)輸問題并不要求一定有產(chǎn)銷平衡的限制。本節(jié)將對這些運(yùn)輸問題的拓展問題進(jìn)行討論。3.1產(chǎn)大于銷的運(yùn)輸問題總產(chǎn)量大于總銷量的運(yùn)輸問題即為產(chǎn)大于銷的運(yùn)輸問題。產(chǎn)大于銷的情況是經(jīng)常發(fā)生的，此時(shí)的運(yùn)輸問題是在滿足需求的前提下，使總運(yùn)費(fèi)最小。在實(shí)際問題中，產(chǎn)大于銷意味著某些產(chǎn)品被積壓在倉庫中?？梢赃@樣設(shè)想，如果把倉庫也看成是一個(gè)假想的銷地，并令其銷量剛好等于總產(chǎn)量與總銷量的差；那么，產(chǎn)大于銷的運(yùn)輸問題不就轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題了嗎？假想一個(gè)銷地，相當(dāng)于在原產(chǎn)銷關(guān)系表上增加一列。接下來我們關(guān)心的問題自然是這一假想列所對應(yīng)的運(yùn)價(jià)。由于假想的銷地代表的是倉庫，而我們優(yōu)化的運(yùn)費(fèi)是產(chǎn)地與銷地間的運(yùn)輸費(fèi)用，并不包括廠內(nèi)的運(yùn)輸費(fèi)用；所以假想列所對應(yīng)的運(yùn)價(jià)都應(yīng)取為“0”。至此，我們已經(jīng)將產(chǎn)大于銷的運(yùn)輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題，進(jìn)一步的求解可利用上節(jié)介紹的表上作業(yè)法來完成。例4-2 將表4-34所示的產(chǎn)大于銷的運(yùn)輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題表4-34甲乙丙丁產(chǎn)量（ai）A3113107B19284C7410512銷量（bj）3656此運(yùn)輸問題的總產(chǎn)量為23、總銷量為20，所以假設(shè)一個(gè)銷地戊并令其銷量剛好等于總產(chǎn)量與總銷量的差“3”。取假想的戊列所對應(yīng)的運(yùn)價(jià)都為“0”，可得表4-35所示的產(chǎn)銷平衡運(yùn)輸問題。表4-35甲乙丙丁戊產(chǎn)量（ai）A31131007B192804C74105012銷量（bj）365633.2銷大于產(chǎn)的運(yùn)輸問題總銷量大于總產(chǎn)量的運(yùn)輸問題即為銷大于產(chǎn)的運(yùn)輸問題。銷大于產(chǎn)的運(yùn)輸問題追求的目標(biāo)是在最大限度供應(yīng)的前提下，使總運(yùn)費(fèi)最小。同產(chǎn)大于銷的問題一樣，可以這樣設(shè)想，假想一個(gè)產(chǎn)地，并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差；那么，銷大于產(chǎn)的運(yùn)輸問題不也同樣可以轉(zhuǎn)換成產(chǎn)銷平衡的運(yù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)輸問題轉(zhuǎn)換成了產(chǎn)銷平衡的運(yùn)輸問題。例4-3 將表4-36所示的銷大于產(chǎn)的運(yùn)輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題表4-36甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059銷量（bj）11656此運(yùn)輸問題的總產(chǎn)量為20、總銷量為28，所以假設(shè)一個(gè)產(chǎn)地D并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差“8”。令假想的D行所對應(yīng)的運(yùn)價(jià)都為“0”，可得表4-37所示的產(chǎn)銷平衡運(yùn)輸問題。表4-37甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059D00008銷量（bj）116563.3運(yùn)輸問題的應(yīng)用舉例例4-4 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥需求，假定等量化肥在這些地區(qū)的使用效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的單位運(yùn)價(jià)如表4-38所示，試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。表4-38（單位：萬噸）地區(qū)1地區(qū)2地區(qū)3地區(qū)4年產(chǎn)量化肥廠A1613221750化肥廠B1413191560化肥廠C192023M50年需要量最低需求3070010最高需求507030不限這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬噸，四個(gè)地區(qū)的最低需求為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，除滿足地區(qū)1、地區(qū)2和地區(qū)3的最低需求外，地區(qū)4每年最多能分配到60（）萬噸，這樣其不限的最高需求可等價(jià)認(rèn)為是60萬噸。按最高需求分析，總需求為210萬噸，大于總產(chǎn)量160萬噸，將此問題定義為銷大于產(chǎn)的運(yùn)輸問題。為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠D，令其年產(chǎn)量為50（）萬噸。各地區(qū)的需要量包含最低和最高兩部分：如地區(qū)1，其中30萬噸是最低需求，故這部分需求不能由假想的化肥廠D來供給，因此相應(yīng)的運(yùn)價(jià)定義為任意大正數(shù)M；而另一部分20萬噸滿足與否都是可以的，因此可以由假想化肥廠D來供給，按前面講的，令相應(yīng)運(yùn)價(jià)為“0”。凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個(gè)地區(qū)來看待，這樣可以將表4-38所示的運(yùn)輸問題轉(zhuǎn)換為表4-39所示的運(yùn)輸問題。表4-39（單位：萬噸）地區(qū)1地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)4年產(chǎn)量化肥廠A16161322171750化肥廠B14141319151560化肥廠C19192023MM50化肥廠DM0M0M050年需要量302070301050用表上作業(yè)法計(jì)算，可以求得這個(gè)問題的最優(yōu)方案，如表4-40所示。表4-40 （單位：萬噸）地區(qū)1地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)4年產(chǎn)量化肥廠A5050化肥廠B20103060化肥廠C3020050化肥廠D302050年需要量302070301050例4-5 某產(chǎn)品今后四年的年度生產(chǎn)計(jì)劃安排問題。已知前兩年這種產(chǎn)品的生產(chǎn)費(fèi)用為每件10元，后兩年為每件15元。四年對該產(chǎn)品的需求分別為300、700、900和800件，而且需求必須得到滿足。工廠生產(chǎn)該產(chǎn)品的能力是每年700件；此外，工廠可以在第二、第三兩個(gè)年度里組織加班，加班期間內(nèi)可生產(chǎn)該種產(chǎn)品200件，每件生產(chǎn)費(fèi)用比正常時(shí)間里的增加5元。多余的產(chǎn)品可以以每年每件3元的費(fèi)用儲存。問如何制定生產(chǎn)計(jì)劃，才能在保證需求的前提下使總費(fèi)用最小。解：將此問題作為運(yùn)輸問題來處理，產(chǎn)品的年度生產(chǎn)為產(chǎn)地、年度需求為銷地并設(shè)：第1年生產(chǎn)的第年需要的產(chǎn)品數(shù)量（）；第2年正常時(shí)間生產(chǎn)的第年需要的產(chǎn)品數(shù)量（）；第2年加班時(shí)間生產(chǎn)的第年需要的產(chǎn)品數(shù)量（）；第3年正常時(shí)間生產(chǎn)的第年需要的產(chǎn)品數(shù)量（）；第3年加班時(shí)間生產(chǎn)的第年需要的產(chǎn)品數(shù)量（）；第4年生產(chǎn)的第年需要的產(chǎn)品數(shù)量（）；四年的總銷量是2700件，按組織加班考慮，總產(chǎn)量是3200件，總產(chǎn)量大于總銷量。假設(shè)一個(gè)銷地D，等價(jià)的平衡運(yùn)輸問題如表4-41所示。此時(shí)這一問題完全可以通過表上作業(yè)法求解了，求解略。表4-41第1年第2年第3年第4年假設(shè)銷地D產(chǎn) 量第1年101316190700第2年M1013160700第2年（加）M1518210200第3年MM15180700第3年（加）MM20230200第4年MMM150700銷 量3007009008005003200表4-42貨物起點(diǎn)終點(diǎn)車次起點(diǎn)終點(diǎn)車次起點(diǎn)終點(diǎn)車次磚A1A311A1A52A1A66砂子A2A114A2A33A2A63爐灰A3A19A4A14塊石A3A47A3A65卵石A4A28A4A53木材A5A22鋼材A6A44例4-6 在A1、A2、A3、A4、A5和A6六個(gè)經(jīng)濟(jì)區(qū)之間有磚、砂子、爐灰、塊石、卵石、木材和鋼材七種物資需要運(yùn)輸。具體的運(yùn)輸需求如表4-42所示，各地點(diǎn)間的路程（公里）見表4-43，試確定一個(gè)最優(yōu)的汽車調(diào)度方案。表4-43 到從A2A3A4A5A6A121191315A22101410A3459A4416A56表4-44A1A2A3A4A5A6出車數(shù)1920211524來車數(shù)27101411514平衡數(shù)+8-10-7-4+3+10汽車的最優(yōu)調(diào)度實(shí)質(zhì)上就是空車行駛的公里數(shù)最少。先構(gòu)造如表4-44所示的各地區(qū)汽車出入平衡表，表中“十”號表示該點(diǎn)產(chǎn)生空車，“”號表示該點(diǎn)需要調(diào)進(jìn)空車。平衡結(jié)果A1、A5、A6除裝運(yùn)自己的貨物外，可多出空車21車次；A2、A3、A4缺21車次。按最小空駛調(diào)度，可構(gòu)造表4-45所示的運(yùn)輸問題數(shù)據(jù)表