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

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